This is my Tic Tac Toe based games playground
Tic Tac Toe
The Tic Tac Toe page is a implementation of the classical Tic Tac Toe game.
The "Game" section allows a player to play against different AI opponent. Buttons also allow the
player to use one of the AIs to play their move.
- random is a dumb AI where the next move is chosen randomly amongst the valid moves
- hardcodedrules is a strategy based on
Newell and Simon's 1972 tic-tac-toe program
as described on Wikipedia. This version does not look for move creating forks or blocking
the opponent's forks making it easy to beat.
- hardcodedrulesComplete is based on the previous strategy but it also checks for forks
and try to block opponent's fork. However my implementation of this last check is not complete
and thus the AI is not perfect, it can lose some games.
- minmax is an implementation of
the minmax algorith is according to my tests
it is a perfect opponent which never loses.
The "Generator" section can be used to make the AIs play several games against each other. The
interesting use case is to compare the performances of the different AIs against a random
player. This is by this means that I empirically determined that my hard coded rules strategies
are not perfect unlike my minmax strategy.
The "Analyzer" section is used for debugging and writting tests. It allows the users to create
any tic tac toe board and visualize some information like the bynary representation of each
player's move
Gobblet
Gobblet is a tic tac toe game with pieces of different dimensions,
inspired by Gobblet played
on a 3x3 board. Players take turns to place a piece on the board or move their piece that already
is on the board. Bigger pieces can be placed so that they cover smaller ones and a player wins by
aligning 3 pieces.
In the "Game" section you can play against different level of AIs. None of them are perfect.
Buttons allow the player to use one of the AIs to play their move.
- random is a simple random AI which choose one of the possible moves.
- win_or_random Checks all the possible moves it can do, if one of them creates a win for
the AI then it plays it otherwise it plays a random move amongst the possible ones.
- euristic makes a very simple choice based on the euristic value of the next move.
- For the current state compute all the possible moves.
- Score each move with a euristic
- Select the move with the highest score
This strategy is not very good because it doesn't consider the future It will only play a winning
move if one is possible. Since it doesn't check the next opponent's move it sometimes play losing
moves. However since the euristic favorise more interesting cells (center and corners) it is
a bit better than the win_or_random strat
- minmax is a classical minmax strategy. No pruning is implemented so the max depth is set
to 2 because for higher depths the response time gets quite long.
- negamax is an implementation of the
negamax algorithm. As
expected it yields the same results as the minmax strategy but its code is simpler. The
performance remains the same as minmax with the same max depth.
- alphabeta
is an incomplete
minmax with alphabeta pruning strategy
. Here the children are not ordered via an evaluation fonction, the children are ordered in
a consistent but random order. That makes the alpha-beta pruning unefficient and it only improve
the performance to allow a depth of 3.
- alphabeta_with_order aims to fix the previous solution by ordering the children depending
on a score attributed by a custom evaluation function. However the implementation is incomplete
and probably buggy so the AI is not perfect.
The "Runner" section allows to make the AIs play games against each other and get statistics of
these games.
Misere
The Misere page a variant of Tic Tac Toe where the player wins if the opponent
aligns 3 pieces. The "Game" section allows a player to play against different AI opponent. Only the
random and minmax are implemented because they reused the code of the regular Tic Tac Toe AI.
Some interesting readings: