| Tic-Tac-Toe | ||
| ... OR ... | ||
Tic-Tac-Toe is a two player game played on a 3 x 3 grid. The players are identified by the markings X and O and take alternating turns placing their mark on any open square of the board. The X player always makes the first mark.
A player wins by completing a line of 3 marks. The lines may run horizontally, vertically, or diagonally.
If all of the squares of the board are filled with no winner then the game is a draw.
Tic-Tac-Toe is a marvelously simple game that easily lends itself to brute force analysis. There are only a total of 262,737 possible games that can be played; the number of games is not 9! = 362,880 because the game has early-end states starting on the fifth move. If symmetry were to be considered then number of states would be far smaller ... but considering symmetry isn't very "brute force".
The solver starts with a given board state and, for each open square, evaluates all possible endings if the current player takes that square. This results in a factorial reduction of moves to analyze, as shown below:
| Move | Player | Number of States | Starting board | Ending board |
| 1 | X | 262,728 | - - - - - - - - - |
- - - - X - - - - |
| 2 | O | 25,880 | - - - - X - - - - |
O - - - X - - - - |
| 3 | X | 3,198 | O - - - X - - - - | O - - - X - - - X |
| 4 | O | 543 | O - - - X - - - X |
O - - - X - O - X |
| 5 | X | 91 | O - - - X - O - X |
O - - X X - O - X |
| 6 | O | 25 | O - - X X - O - X |
O - - X X O O - X |
| 7 | X | 9 | O - - X X O O - X |
O X - X X O O - X |
| 8 | O | 4 | O X - X X O O - X |
O X - X X O O O X |
| 9 | X | 1 | O X - X X O O X X |
O X X X X O O O X |
The game grossly favors player X - the first mover.
On the first move if player X takes the center square they have an incredible advantage over player O. But even the other squares provide a substantial advantage:
| X takes | Win | Loss | Draw | Advantage |
| Center | 15,648 | 5,616 | 4,608 | 2.8 : 1 |
| Corner | 14,652 | 7,896 | 5,184 | 1.8 : 1 |
| Outside Middle | 14,232 | 10,176 | 5,184 | 1.4 : 1 |
As clearly shown, taking the center provides twice the winning potential as taking the worst first move - but even X's worst first move still provides 40% more winning potential than player O. Player X continues to maintain such an advantage on their next move. Assuming X seizes the center and O takes a corner (both players taking their best first moves), X increases their lead to a best-case 3:1. And their worst-case move is still very high at 1.8:1.
In fact, assuming both players play the moves that follow the highest victory path, player X maintains a lead throughout the game. Fortunately for player O, however, if play follows the highest victory path for both players then the game will end in a draw. It is possible for player O to win but it would require player X taking clearly non-optimal path for themself.