Big Dice Games Presents
Tic Tac Toe
Tic Tac Toe
As an exercise in playing around with Adversarial AI techniques, I
implemented Tic-Tac-Toe. It's also a chance to get the hang of using
pyglet, a "windowing and
multimedia library for Python".
There are 4 different computer opponents implemented:
- random - simply plays randomly. Not a very challenging
opponent.
- minimax - brute force minimaxing, evaluating as much of the
tree as it can in 5 seconds. Maintains a "transposition table" to
minimize the cost of re-searching already visited nodes.
- alpha-beta - alpha beta pruner, with transposition
table. By searching more efficiently, it ought to be able to search
deeper than simple minimax, above.
- MTD(f) - An implementation of Aske Plaat's
algorithm, which should be even more efficient.
Also potentially of interest, I mapped out the entire game tree of Tic
Tac Toe here.
If you have questions or comments about the game, please contact me at
dave at bigdicegames
dot com