How do I create a test to see if my A.I. is perfect?

Question

I made a tic tac toe A.I. Given each board state, my A.I. will return 1 exact place to move. I also made a function that loops though all possible plays made with the A.I.

So it's a recursive function that lets the A.I. make a move for a given board, then lets the other play make all possible moves and calls the recursive function in it self with a new board for each possible move.

I do this for when the A.I goes first, and when the other one goes first... and add these together. I end up with 418 possible wins and 115 possible ties, and 0 possible loses.

But now my problem is, how do I maximize the amount of wins? I need to compare this statistic to something, but I can't figure out what to compare it to.

Answer 1

You should start by observing that move 9 is always forced: there is only one empty square on the board. Move can be considered 8 forced as well, because after seven moves there could be exactly three situations:

• O can win on the next move, in which case it takes the win
• Placing an X in either one of the two remaining squares wins the game for X, in which case O has lost regardless of its next move
• X has zero or one path to victory, in which case O blocks to force a draw

This means that the game is over after at most seven moves.

Also observe that there are only three opening moves: the center, a corner, or a side. It does not matter which of the four corners or sides you take, because the board can be rotated to match a "canonical" opening (the upper-left corner or the middle of the top side).

You can now build your state analysis code. Starting with each of the three possible openings, search with backtracking up to six additional moves using all squares that are open by the time you make the move. After each move, analyze the position to see if X or O has already won; mark wins by X as Wx, and wins by O as Wo. The remaining positions are undecided.

Do not explore positions after Wx or Wo: simply return to the prior step, reporting the win by the corresponding side.

When you reach the seventh move, statically analyze the position to decide if it is one of the three situations described above is applicable, marking the position a Wx, Wo, or a Draw.

Now to the most important step: when you backtrack to the move N-1 by the player p,

• If one of the moves that you try is such that all position at the next level becomes Wp, declare the current position a Wp as well.
• If all of the moves that you try lead to the win of the opponent, declare the current position a win for the opponent
• Otherwise, declare the current position a Draw, and return to the prior level.

If you do this right, all three opening positions will be classified as a Draw. You should see some forcible wins after three moves.

Running this procedure classifies each position as a Wx, Wo, or a Draw. If your AI gets you a win for the player p in a position classified as Wp, or gets you a draw in a position classified as a Draw, then your AI is perfect. If, on the other hand, there are positions that are statically classified as Wp in which the AI gets p only a draw, then your AI engine needs an improvement.

---

Additional reading: you can find additional insights into the game in this article describing methods of counting possible games of Tic-Tac-Toe.