This is a solver for tic-tac-toe, written in C++.
The program
(1) searches the game tree using a minimax algorithm with or without alpha-beta pruning (depending on the macro AB_PRUNE in TicTacToe.h);
(2) allows the user to play against the computer.
The compiler must support the C++11 standard to compile, e.g. modern versions of GCC or Visual Studio.
On Windows, open the Visual Studio solution TicTacToe.sln.
On Linux,
make
bin/tictactoe
For a terminal state with n moves (5 <= n <= 9), the payoff v of the MAX player is evaluated with the following rule:
- If MAX wins, v = +(10 - n)
- If MIN wins, v = -(10 - n)
- If the game is drawn, v = 0
In contrast to a naive three-valued evalution function, this design favors fast wins and slow losses, and therefore avoids unreasonable moves.
As expected, the minimax profit for both MAX and MIN player is 0, i.e. the game ends in a draw if both player plays perfectly.
An unpruned search takes ~100 ms.
Statistics:
| Ply | MAX | MIN |
|---|---|---|
| 1 | 0 | 0 |
| 2 | 0 | 0 |
| 3 | 0 | 0 |
| 4 | 0 | 0 |
| 5 | 1440 | 0 |
| 6 | 0 | 5328 |
| 7 | 47952 | 0 |
| 8 | 0 | 72576 |
| 9 | 81792 | 0 |
Draws 46080
Leaves 255168
Nodes 549946
An alpha-beta pruned search takes ~5ms.
Statistics:
| Ply | MAX | MIN |
|---|---|---|
| 1 | 0 | 0 |
| 2 | 0 | 0 |
| 3 | 0 | 0 |
| 4 | 0 | 0 |
| 5 | 186 | 0 |
| 6 | 0 | 432 |
| 7 | 1924 | 0 |
| 8 | 0 | 2299 |
| 9 | 2294 | 0 |
Draws 1318
Leaves 8453
Nodes 20866
-
More complex games, e.g. Connect Four, Gomoku, Reversi, checkers, chess, Go
-
Heuristic evaluation function
This software is licensed under the MIT License. See LICENSE.