TicTacToe AI Making Incorrect Decisions

Question

A little background: as a way to learn multinode trees in C++, I decided to generate all possible TicTacToe boards and store them in a tree such that the branch beginning at a node are all boards that can follow from that node, and the children of a node are boards that follow in one move. After that, I thought it would be fun to write an AI to play TicTacToe using that tree as a decision tree.

TTT is a solvable problem where a perfect player will never lose, so it seemed an easy AI to code for my first time trying an AI.

Now when I first implemented the AI, I went back and added two fields to each node upon generation: the # of times X will win & the # of times O will win in all children below that node. I figured the best solution was to simply have my AI on each move choose and go down the subtree where it wins the most times. Then I discovered that while it plays perfect most of the time, I found ways where I could beat it. It wasn't a problem with my code, simply a problem with the way I had the AI choose it's path.

Then I decided to have it choose the tree with either the maximum wins for the computer or the maximum losses for the human, whichever was more. This made it perform BETTER, but still not perfect. I could still beat it.

So I have two ideas and I'm hoping for input on which is better:

1) Instead of maximizing the wins or losses, instead I could assign values of 1 for a win, 0 for a draw, and -1 for a loss. Then choosing the tree with the highest value will be the best move because that next node can't be a move that results in a loss. It's an easy change in the board generation, but it retains the same search space and memory usage. Or...

2) During board generation, if there is a board such that either X or O will win in their next move, only the child that prevents that win will be generated. No other child nodes will be considered, and then generation will proceed as normal after that. It shrinks the size of the tree, but then I have to implement an algorithm to determine if there is a one move win and I think that can only be done in linear time (making board generation a lot slower I think?)

Which is better, or is there an even better solution?

Answer 1

Your existing algorithm is good, except you are forgetting one thing. Never choose any path where a move by the other player results in you being unable to at least tie.

So basically, discard any branch where the players next move could result in an un-tieable situation and then run your existing algorithm. This results in the highest chance of winning against a non-perfect opponent, while removing the possibility of losing.

Answer 2

Tic-Tac-Toe can be solved using a greedy algorithm and doesn't really require a decision tree.

If you want to continue using your current algorithm, do as patros suggests, and minimize the possibility of losing at each decision.

If you want a simpler approach have the AI do the following each turn:

1. Complete a winning Tic-Tac-Toe if possible.
2. Block an opposing Tic-Tac-Toe if possible.

3. Rate each square for its desirability, for each other taken square (by the AI) on a line, add one point of desirability for that square. For each square taken by the opponent, remove one point of desirability.

   For example, if the board is currently:

   _|O|X
   _|X|_
   O| |
   

   The top-left corner has a desirability of 0 (1 for the X in the same row, and 1 for the X in the diagonal, but -1 for each of the Os).

4. Play on the most desirable square. Breaking ties arbitrarily.

   In the example from above, the AI would choose the mid-right square, since it has a desirability of 2, which would lead to a win the following turn.

5. If the game has just begun, play the center square, if the center square is taken, choose a corner at random.

6. Win (or tie).

This was my grade 10 Visual Basic term project. It's impossible to beat and requires far less memory than storing a decision tree.

Answer 3

The "naive" way to do this (for an arbitrary game where two players take turns doing a move) is to try each possible move recursively until you end up with a board where one is the winner, then back-track upwards in the tree marking the nodes as "O wins", "X wins" or "draw".

Each time you step up (one such step is usually called a ply), depending on who's move it is, assume the player chooses the move that is best for him/her. Since you are moving from the leaves and upwards, you will always know the optimum possible results for each child node.

When counting the number of possible winning or losing boards in a subtree, you are essentially assuming that each player will always make a random move. As you noted, this will not be very effective if you play against a smart player. The scheme I outlined above instead assumes that the opponent always makes a perfect move, trying to win.

Answer 4

The (usually) correct way to implement AI based on a decision tree is to use the "Minimax" algorithm:

1. Assign each leaf node a score (+1=player wins, -1=player loses, 0=tie)

2. Work your way up the tree, applying the following rules to each node:

   • For even depths (when the player would make a move), pick the child with the highest score, and copy that score to the node.
   • For odd depths (when the computer would make a move), pick the child with the lowest score, and copy that score to the node.

Of course, even and odd might need to be reversed, depending on who you decide goes first.

You can read more at:

• http://ai-depot.com/articles/minimax-explained/
• http://en.wikipedia.org/wiki/Minimax