TicTacToe AI needs optimization

Question

How do I condense this gigantic monster into something more manageable? I heard about command pattern but I can't figure out how to use it. What other solutions are there?

public void AI(){
 count++;
 if(count % 2 == 0){
 letter = "O";
 }
 if(((buttons[1].getText().equals("X") && buttons[2].getText().equals("X"))
 || (buttons[3].getText().equals("X") && buttons[6].getText().equals("X"))
 || (buttons[4].getText().equals("X") && buttons[8].getText().equals("X")))
 && buttons[0].getText().equals("")
 ){
 buttons[0].setText("O");
 buttons[0].setEnabled(false);
 } else if(((buttons[0].getText().equals("X") && buttons[2].getText().equals("X"))
 || (buttons[4].getText().equals("X") && buttons[7].getText().equals("X")))
 && buttons[1].getText().equals("")
 ){
 buttons[1].setText("O");
 buttons[1].setEnabled(false);
 } else if(((buttons[0].getText().equals("X") && buttons[1].getText().equals("X"))
 || (buttons[4].getText().equals("X") && buttons[6].getText().equals("X"))
 || (buttons[5].getText().equals("X") && buttons[8].getText().equals("X")))
 && buttons[2].getText().equals("")
 ){
 buttons[2].setText("O");
 buttons[2].setEnabled(false);
 } else if(((buttons[4].getText().equals("X") && buttons[5].getText().equals("X"))
 || (buttons[0].getText().equals("X") && buttons[6].getText().equals("X")))
 && buttons[3].getText().equals("")
 ){
 buttons[3].setText("O");
 buttons[3].setEnabled(false);
 } else if(((buttons[0].getText().equals("X") && buttons[8].getText().equals("X"))
 || (buttons[1].getText().equals("X") && buttons[7].getText().equals("X"))
 || (buttons[3].getText().equals("X") && buttons[5].getText().equals("X"))
 || (buttons[2].getText().equals("X") && buttons[6].getText().equals("X")))
 && buttons[4].getText().equals("")
 ){
 buttons[4].setText("O");
 buttons[4].setEnabled(false);
 } else if(((buttons[2].getText().equals("X") && buttons[8].getText().equals("X"))
 || (buttons[3].getText().equals("X") && buttons[4].getText().equals("X")))
 && buttons[5].getText().equals("")
 ){
 buttons[5].setText("O");
 buttons[5].setEnabled(false);
 } else if(((buttons[0].getText().equals("X") && buttons[3].getText().equals("X"))
 || (buttons[4].getText().equals("X") && buttons[2].getText().equals("X"))
 || (buttons[7].getText().equals("X") && buttons[8].getText().equals("X")))
 && buttons[6].getText().equals("")
 ){
 buttons[6].setText("O");
 buttons[6].setEnabled(false);
 } else if(((buttons[6].getText().equals("X") && buttons[8].getText().equals("X"))
 || (buttons[1].getText().equals("X") && buttons[4].getText().equals("X")))
 && buttons[7].getText().equals("")
 ){
 buttons[7].setText("O");
 buttons[7].setEnabled(false);
 } else if(((buttons[2].getText().equals("X") && buttons[5].getText().equals("X"))
 || (buttons[4].getText().equals("X") && buttons[0].getText().equals("X"))
 || (buttons[6].getText().equals("X") && buttons[7].getText().equals("X")))
 && buttons[8].getText().equals("")
 ){
 buttons[8].setText("O");
 buttons[8].setEnabled(false);
 } else if(((buttons[1].getText().equals("O") && buttons[2].getText().equals("O"))
 || (buttons[3].getText().equals("O") && buttons[6].getText().equals("O"))
 || (buttons[4].getText().equals("O") && buttons[8].getText().equals("O")))
 && buttons[0].getText().equals("")
 ){
 buttons[0].setText("O");
 buttons[0].setEnabled(false);
 } else if(((buttons[0].getText().equals("O") && buttons[2].getText().equals("O"))
 || (buttons[4].getText().equals("O") && buttons[7].getText().equals("O")))
 && buttons[1].getText().equals("")
 ){
 buttons[1].setText("O");
 buttons[1].setEnabled(false);
 } else if(((buttons[0].getText().equals("O") && buttons[1].getText().equals("O"))
 || (buttons[4].getText().equals("O") && buttons[6].getText().equals("O"))
 || (buttons[5].getText().equals("O") && buttons[8].getText().equals("O")))
 && buttons[2].getText().equals("")
 ){
 buttons[2].setText("O");
 buttons[2].setEnabled(false);
 } else if(((buttons[4].getText().equals("O") && buttons[5].getText().equals("O"))
 || (buttons[0].getText().equals("O") && buttons[6].getText().equals("O")))
 && buttons[3].getText().equals("")
 ){
 buttons[3].setText("O");
 buttons[3].setEnabled(false);
 } else if(((buttons[0].getText().equals("O") && buttons[8].getText().equals("O"))
 || (buttons[1].getText().equals("O") && buttons[7].getText().equals("O"))
 || (buttons[3].getText().equals("O") && buttons[5].getText().equals("O"))
 || (buttons[2].getText().equals("O") && buttons[6].getText().equals("O")))
 && buttons[4].getText().equals("")
 ){
 buttons[4].setText("O");
 buttons[4].setEnabled(false);
 } else if(((buttons[2].getText().equals("O") && buttons[8].getText().equals("O"))
 || (buttons[3].getText().equals("O") && buttons[4].getText().equals("O")))
 && buttons[5].getText().equals("")
 ){
 buttons[5].setText("O");
 buttons[5].setEnabled(false);
 } else if(((buttons[0].getText().equals("O") && buttons[3].getText().equals("O"))
 || (buttons[4].getText().equals("O") && buttons[2].getText().equals("O"))
 || (buttons[7].getText().equals("O") && buttons[8].getText().equals("O")))
 && buttons[6].getText().equals("")
 ){
 buttons[6].setText("O");
 buttons[6].setEnabled(false);
 } else if(((buttons[6].getText().equals("O") && buttons[8].getText().equals("O"))
 || (buttons[1].getText().equals("O") && buttons[4].getText().equals("O")))
 && buttons[7].getText().equals("")
 ){
 buttons[7].setText("O");
 buttons[7].setEnabled(false);
 } else if(((buttons[2].getText().equals("O") && buttons[5].getText().equals("O"))
 || (buttons[4].getText().equals("O") && buttons[0].getText().equals("O"))
 || (buttons[6].getText().equals("O") && buttons[7].getText().equals("O")))
 && buttons[8].getText().equals("")
 ){
 buttons[8].setText("O");
 buttons[8].setEnabled(false);
 } else {
 boolean testing = true;
 for(int i = 0; i < 9; i++){
 if(buttons[i].getText().equals("") && testing == true){
 buttons[i].setText("O");
 buttons[i].setEnabled(false);
 testing = false;
 }
 } 
 }
}

• Paul Medcraft: There are some interesting articles online about applying the Minimax algorithm to Tic Tac Toe, well worth a read. Here's one, for example: neverstopbuilding.com/minimax

Answer 1

The code is full of repetition that can be removed. By just adding these two methods, it becomes much more readable.

private boolean IsValue(int buttonNumber, String value) {
 return buttons[buttonNumber].getText().equals(value);
}
private void SetValue(int buttonNumber, String value) {
 buttons[buttonNumber].setText(value);
 buttons[buttonNumber].setEnabled(false);
}

This changes the first block to be:

if (((IsValue(1, "X") && IsValue(2, "X"))
 || (IsValue(3, "X") && IsValue(6, "X"))
 || (IsValue(4, "X") && IsValue(8, "X")))
 && IsValue(0, "")) {
 SetValue(0, "O");
}
// ...

---

In a game of tic tac toe, there are three valid states of a cell. Empty, X, and O. However, in you application, a cell is represented by a String. That means there are an unlimited number of values that could be stored. Instead, you can define an enum that will ensure no invalid values are possible. This will mean you need to do a little more work when converting between business logic and the UI, but this can be encapsulated into functions that simplify the majority of the application.

---

You start out by optionally setting a value to letter, but never use it.

---

The logic is hard coded to check for X and insert O. What happens if the player wants to be O? You AI code no longer works.

• TheQuantumBros: Should the SetValue method be void since it returns nothing? Or what would you return?
• unholysampler: Good catch. I had just copied the first method and missed that when changing it. The code has been updated.
• TheQuantumBros: Also letter is used in a different portion of the code, the block using letter that I had in my AI was useless, so I deleted it.
• Falco: I would probably even try to shorten it more, by making IsValue a variadic funtion: IsValue(String letter, int... fields) and then check if all the fields are set to letter. Then the block becomes: IsValue("",0) && (IsValue("X",1,2) || IsValue("X",3,6) || IsValue("X", 4,8))
• Simon Forsberg: For the record, this is Java, the methods should be named isValue and setValue

Answer 2

So what your AI is basically doing is looking for two in a row, and then block that row, right?

In that case the first thing I would do is split your code up in two methods: setAI - which actually performs the move of the AI - and findBlockable - which finds a field that blocks three in a row. [you can see if you can come up with better names.]

I'm also assuming that the count and testing parts of your code aren't actually used? In that case I would remove them.

Different Structure

In general, I would consider a matrix as structure, not an array (because that's what the field is). Then, you could access it as buttons[x][y], which makes a lot more sense. And then your problem is solved by just iterating over x (for horizontal), y (for vertical), and x and y (for diagonally) and counting the pieces that are set.

You could also map your array indices to matrix indices if you want to, and then use this approach.

With your structure

But lets stick with your approach. You have a field like this:

0 1 2
3 4 5
6 7 8

So each field is separated by 3 from it's vertical neighbor, by 4 from it's diagonal neighbor, and by one from its horizontal neighbor. So your code might look something like this:

public boolean blocksTwoInARow(int i, Button[] buttons) {
 // check horizontal
 if (blocksTwoInARowHelper(i, buttons, 1)) {
 return true;
 }
 // check vertical
 else if (blocksTwoInARowHelper(i, buttons, 3)) {
 return true; 
 }
 // check diagonal
 else if (blocksTwoInARowHelper(i, buttons, 4)) {
 return true;
 }
 return false;
}
public boolean blocksTwoInARowHelper(int i, Button[] buttons, int steps) {
 // TODO bounds check
 int neighborCount = 0;
 for (int j = i - 2*steps; j < i + 2*steps; j+=steps) {
 if (j >= 0 && j < array.length && "0".equals(buttons[j].getText())) {
 neighborCount++;
 }
 }
 return neighborCount == 2; 
}

And then be used like this:

for(int i = 0; i < buttons.length; i++){
 if (blocksTwoInARow(i, buttons)) {
 buttons[i].setText("O");
 buttons[i].setEnabled(false);
 break;
 }
}

[again, those names are just placeholders, I'm sure you can come up with better once.]

I actually think that your code is more readable, but if you plan on extending your field, this might be more adaptable (although if you do plan on extending the code, I would really go with a matrix).

By the way, tic tac toe is a solved game, so you could hardcode these rules to make a perfect AI. That's of course a bit boring. If you are interested in AI, you should take a look at the min-max / alpha beta pruning algorithm.

• TheQuantumBros: When I try to use this correction the Helper method is giving an index out of bound error: -4
• tim: @TheQuantumBros that's why I left the TODO in there :) You have to check first if j is inside the bounds of the array. I updated the code.

Answer 3

Model

I would highly recommend that you abstract the tic-tac-toe model from whatever rendering that you are doing. It looks like you have the board represented by buttons. I suppose this is fine for testing, but it makes the code very ugly. Repeated calls like this:

buttons[2].getText().equals("X")
buttons[6].getText().equals("X")
buttons[0].setText("O");
buttons[0].setEnabled(false);

Are not good because you are asking your rendering for information about the state of the tic-tac-toe board.

I would advise that you separate the entire model from the rendering, whether that rendering be buttons, sprites, or even the console. This means creating things such as a tic-tac-toe game, board, and players. The Game object could have the Board and the Players as objects. The Board object could possibly be represented as rows and columns, and could contain Square (or Tile or GamePiece) objects, which would have the states such as X, O and Empty.

The Game would wait for calls from each player asking for its Move, which could also be represented as a class. Then the Game would perform that Move on the Board and process the results. In this way, the Player could be easily swapped out for an AIPlayer without having to change anything else. If you had a human player, your renderer or scene or whatever you have at the top level could create those Move objects based on the actions of the player, and pass those to the Game. Then, the renderer could read the updated Board and then render that on the screen.

In this way, you could swap out the rendering later to anything that you want without changing the tic-tac-toe game model at all.

---

Confusing Code

This block of code doesn't make much sense:

count++;
if(count % 2 == 0){
 letter = "O";
}

It looks like you are trying to decide which player it is, but I am not sure. If that is the case, I would possibly pass that information as an argument into the method, or change the variable names to indicate what is actually happening here.

This one is confusing too:

 boolean testing = true;
 for(int i = 0; i < 9; i++){
 if(buttons[i].getText().equals("") && testing == true){
 buttons[i].setText("O");
 buttons[i].setEnabled(false);
 testing = false;
 }
 } 

If there is some kind of testing mode for the game, I think this should be extracted to another method and called separately.

• TheQuantumBros: The first block was for a 2 player version, since I started with that, I forgot to delete that code, the second block the only reason I used the testing boolean is since I needed a way for it to make sure the AI only takes one turn, if you know a better way to implement that I'd love to hear, I'm still pretty new to Java. Only taken 1 semester of AP: CS (Still in High School)
• tim: @TheQuantumBros I overlook the meaning of that part as well. You might want to extract it to a method like takeFirstValidMove. And you could use break; to end the loop and thus only make one move.

Answer 4

A while back, I did a research internship on Grammatical Evolution (GE) (which is, simply put, a genetic algorithm using a grammar to generate the phenotypes) which may give you good directions to improve your AI. The whole genetic algorithm thing is a bit complicated (and requires an opponent, that you don't seem to have), but the logic of GE may be of some help to you.

The idea was to see how much intelligence was necessary in the grammar to produce "intelligent" agents. First attempt was quite similar to what you've done : the two methods (words in terms of GE) implemented and available to develop behaviors were valueAt (see what value is at a specific cell) and setValueAt (draw a X or O at a specific position), along with the usuals if, else and else if of the language. This turned out to be a very long process to get intelligent agents and honestly, they were not even so clever. So we decided to put a little more intelligence into the grammar and added the methods : holePosition (finds if there is somewhere a hole that could mean loosing or winning if filled by a X or O) and the very usefull LShapeDetector (3 corners out of 4 are taken by the same symbol, usually meaning that you're about to loose or win), along with a few others. And after a few evolutions, the agent produced were able to beat my supervisor's code (that was supposed to be unbeatable of course) with quite simple behaviors.

All that to say, if you define good methods, the decision part can be limited to a few lines of easily readable conditions. Of course you will have a lot of lines of method definition, but the important part is the decision process. And do not hesitate to use symmetry in your definitions (using modulos and stuff like that), it will greatly reduce the number of conditions you have to write.

Edit : for the sake of completeness, following is the complete grammar that I used for the evolutions of agents. Contrary to what I thought, we did consider that the L shape detection was a little bit too intelligent, but you don't have to consider that aspect. My report on that subject is available upon request.

<rules> ::= <rules> <rule> | <rule>
<rule> ::= ifelse <state> [ <op> ] [ <op> ]
<state> ::= <state> <operator> <property>|<property>
<operator> ::= and | or
<op> ::= make-the-move (<patch>) 0
<property> ::= <patch_state> <patch> | gap-in-a-row? | free-corner?
<patch_state> ::= patch-is-free? | my-patch? | opponent-patch?
<patch> ::= patch <center> | patch <corner> | patch <cardinal> | free-corner | random-patch | opposite <patch> | gap-in-a-row | free-neighbor <patch> | opposite-corner
<corner> ::= 0 0|0 2|2 0|2 2
<cardinal> ::= 0 1|1 0|2 1|1 2
<center> ::= 1 1

• Simon Forsberg: This is very interesting for me. I'd love to read up more about what you accomplished here! (I am familiar with Genetic Algorithms)
• Loufylouf: Here is the full report : dropbox.com/s/xsy61z7xqhkfjpy/report.pdf?dl=0