Tic-Tac-Toe Minimax Algorithm
Do you know how AI for Chess or Checkers work? If not - here is an exercise just for you! Though we are going to use simpler game of Tic-Tac-Toe to demonstrate the algorithm.
So, how should program play the game like Chess or Tic-Tac-Toe (e.g. the game with "full information")? The core idea is similar to how the human (grandmaster) plays:
So simple! But how to "assess" position? Let us agree that assessment is expressed as a single numeric
0 meaning that neither side is doing better, positive if the
first player is winning
and negative if the
second is winning.
For game like chess good assessment function could be built simply by counting remaining pieces (i.e.
1 for pawn,
2.5 for knight,
3 for bishop etc and black score negative values respectively).
With Tic-Tac-Toe the matter is simpler. Let us score
1 for position where Crosses have won (i.e. have
three in a line) and
-1 for position where Noughts have won.
Is it sufficient?
No. If we check only all possible moves for one side, we will probably fail to find good solution. For example with chess we probably will find that "best move" is to capture enemy's Knight with a Queen but we miss that on the next move the opponent can recapture our Queen with a pawn.
For Tic-Tac-Toe it is quite possible that single move does not lead to win so we get
0-s for every
move and have no idea what to choose.
So we shoud go recursive. Really, let us for every move of ours then check every possible response of the opponent. Suppose that opponent will choose the best continuation for him (and the worst for us).
We can continue such recursive search for any number of moves in depth. However for chess usually we limit this depth (otherwise it will be endless search) - while in Tic-Tac-Toe we really can explore every variant to the end.
So that is how the algorithm should look in pseudocode:
# 'side' is either 1 or -1 (for 1-st and 2-nd player respectively) function assess(side): if some side have won: return this side endif bestMove = null bestValue = -1000000 for each (move from allPossibleMoves): makeMove(move) value = assess(-side) takeBack(move) if value * side > bestValue: bestValue = value * side bestMove = move endif endfor return bestValue * side
We leave it up to you to understand how it works in details (according to explanations above) and implement it yourself for Tic-Tac-Toe game.
You will be given several positions in Tic-Tac-Toe game (defined by the sequence of first moves) -
and you are to calculate assessments for every possible move. We will mark moves with cell indices
0..8 of the cells as in this diagram:
| | 0 | 1 | 2 | | -----+-----+----- | | 3 | 4 | 5 (cell_index = Y * 3 + X) | | -----+-----+----- | | 6 | 7 | 8 | |
So that sequence of moves
4 0 2 for example means that firstly
X-s is put into central cell,
O goes into upper-left corner and next
X - into the upper right corner. We agree that
X-s always start the game.
Input data will contain the number of test-cases in the first line.
Next lines will contain sequences of moves for each test case (starting from the empty board each time).
Answer should tell for each position the assessments of moves to every of
9 cells. Assessments
should be expressed as digits
2. Of them
2 means that side to move (either
will win if it puts its mark to given cell,
1 means that draw could be secured and
0 means that
either this cell is already not-empty, or move to it allows the opponent to win the game. Digits
should be written without spaces, e.g.
010102000 means that move to cell
3 leads to draw
and move to cell
5 leads to victory.
Of course phrases "side will win", "side will secure a draw" or "opponent will win" assume that both sides make further moves in optimal way.
input data: 3 1 8 7 7 1 5 3 4 8 7 2 1 3 answer: 000020000 101000100 000021202
Let us analyse these cases.
- X - - - - - X 0
Now it is the move for
O-s. Obviously if they will not take the central cell (
# 4) the crosses
then can win on the very next move. That is why assessment for every cell except
if Noughts will go this way, the crossess are forced to go to cell
0 and the noughts make a
fork putting their mark into cell
2, thus gaining a victory.
- 0 - 0 X X - X 0
Here we simply have just
3 possible moves - and after any of them neither of sides can win -
really we have to put two more
X-s and one more
O - but there is no way to put them so any of
them make a line of three.
- X 0 0 - - - X -
X-s are to move. If they go to cell
0, then opponent takes center with a fork, so it is
a way to lose the game.
Putting the mark into cell
4 makes immediate win, while going to
8 leaves the fork against
noughts, so all these moves win.
At last, if we put
X to cell
O-s will take the center and the rest of the game is
0) making a draw.