Tic-tac-toe in Erlang — smart game space
This is part of an Erlang tutorial built around a tic-tac-toe program. The program is stuffed into one file, called tic.erl and available here.
There are also smaller Erlang modules for analyzing game-spaces called tic_count.erl and tic_game_space.erl.
The tutorial is organized as follows:
- Introduction
- Top-level loop
- User input
- Board display
- Board abstraction
- Game abstraction
- Next move calculations and predictions
- Predicted outcome abstraction
- Utilities to introduce randomness
- Macros for testing and debugging
Smart game space
In the previous post we talk about the full tic-tac-toe game space and all possible board arrangements. The tic_game_space:report0() function from tic_game_space.erl tells us there are 255,168 possible tic-tac-toe games and 5478 distinct tic-tac-toe board arrangements. Or if we treat all rotations and reflections of a board as equal, those counts are reduced to 26,830 games and 765 boards.
But some of these games are very unlikely, and require one or both players to pass up obvious wins and make other mistakes. Most players are unlikely to ever encounter many of these boards without perverse effort. So the question arises, how big is tic-tac-toe if you assume the players are rational.
There is code in tic_game_space.erl to answer that question. Starting from the full game space, the function smart_game_space(..) is able to strip out all the unwise moves and leave us with only the “smart” game paths. The number of boards for each ply in the smart game space is given in the following table.
| Number of marks on board | Number of boards treating rotations and reflections as unique | Number of boards treating rotations and reflections as equal |
|---|---|---|
| 0 (0+0) | 1 | 1 |
| 1 (1+0) | 9 | 3 |
| 2 (1+1) | 24 | 5 |
| 3 (2+1) | 102 | 16 |
| 4 (2+2) | 136 | 18 |
| 5 (3+2) | 176 | 23 |
| 6 (3+3) | 180 | 24 |
| 7 (4+3) | 164 | 22 |
| 8 (4+4) | 76 | 10 |
| 9 (5+4) | 16 | 3 |
| Totals | 884 | 125 |
All smart games end after 9 moves in a tie so there are no winning boards in this game space. You can only win in tic-tac-toe if the other player makes a mistake.
The number of boards is reduced from 5478 in the full game space to 884 in the smart game space. In the modulo all-reflections-rotations game space the board count is reduced from 765 to 125.
The reports from tic_game_space.erl provide more details. For example, we learn there are only 3584 games in the smart game space, reduced from 255,168 in the full space. Here are the reports that treat rotated and reflected boards as unique.
Eshell V5.6.5 (abort with ^G)
1> c( 'c:/src/erlang/tic_game_space',
1> {d, no_rotation_relection_collapse}).
{ok,tic_game_space}
2> tic_game_space:report1( ).
Smart tic-tac-toe game space:
Player 1: all smart moves
Player 2: all smart moves
Total number of game paths: 3584
Total number of boards: 884
Player 1 winning boards : 0
Player 2 winning boards : 0
Player 1 must respond to: 417
Player 2 must respond to: 451
Tie boards : 16
Total number of boards can also be broken down as:
Initial board count : 1
Boards produced by player 1: 467
Boards produced by player 2: 416
ok
3> tic_game_space:report1( ply_overview).
Smart tic-tac-toe game space:
Player 1: all smart moves
Player 2: all smart moves
Player 1 moves, leading to ply 1
9 boards (all continue to ties)
Player 2 moves, leading to ply 2
24 boards (all continue to ties)
Player 1 moves, leading to ply 3
102 boards (all continue to ties)
Player 2 moves, leading to ply 4
136 boards (all continue to ties)
Player 1 moves, leading to ply 5
176 boards (all continue to ties)
Player 2 moves, leading to ply 6
180 boards (all continue to ties)
Player 1 moves, leading to ply 7
164 boards (all continue to ties)
Player 2 moves, leading to ply 8
76 boards (all continue to ties)
Player 1 moves (last move)
16 tie boards
ok
Here are the reports that treat rotated and reflected boards as equal. The boards in the first three plys are also listed. Notice there are only 336 games in the game space, down from 26,830 in the full game space.
Eshell V5.6.5 (abort with ^G)
1> c( 'c:/src/erlang/tic_game_space').
{ok,tic_game_space}
2> tic_game_space:report1( ).
Smart tic-tac-toe game space:
Player 1: all smart moves
Player 2: all smart moves
Total number of game paths: 336
Total number of boards: 125
Player 1 winning boards : 0
Player 2 winning boards : 0
Player 1 must respond to: 58
Player 2 must respond to: 64
Tie boards : 3
Total number of boards can also be broken down as:
Initial board count : 1
Boards produced by player 1: 67
Boards produced by player 2: 57
ok
3> tic_game_space:report1( ply_overview).
Smart tic-tac-toe game space:
Player 1: all smart moves
Player 2: all smart moves
Player 1 moves, leading to ply 1
3 boards (all continue to ties)
Player 2 moves, leading to ply 2
5 boards (all continue to ties)
Player 1 moves, leading to ply 3
16 boards (all continue to ties)
Player 2 moves, leading to ply 4
18 boards (all continue to ties)
Player 1 moves, leading to ply 5
23 boards (all continue to ties)
Player 2 moves, leading to ply 6
24 boards (all continue to ties)
Player 1 moves, leading to ply 7
22 boards (all continue to ties)
Player 2 moves, leading to ply 8
10 boards (all continue to ties)
Player 1 moves (last move)
3 tie boards
ok
4> tic_game_space:report1( 0).
Smart tic-tac-toe game space:
Player 1: all smart moves
Player 2: all smart moves
Boards in ply 0
... X.. .X. ...
... -> ... ... .X.
... ... ... ...
ok
5> tic_game_space:report1( 1).
Smart tic-tac-toe game space:
Player 1: all smart moves
Player 2: all smart moves
Boards in ply 1
X.. X..
... -> .O.
... ...
.X. OX. .X. .X.
... -> ... .O. ...
... ... ... .O.
... O..
.X. -> .X.
... ...
ok
6> tic_game_space:report1( 2).
Smart tic-tac-toe game space:
Player 1: all smart moves
Player 2: all smart moves
Boards in ply 2
X.. XX. X.X X.. X..
.O. -> .O. .O. .OX .O.
... ... ... ... ..X
OX. X.O X.. OX. OX.
... -> ..X ..X X.. .X.
... ... ..O ... ...
O.. X.O X.. OX. O..
.X. -> .X. .X. .X. .XX
... ... ..O ... ...
.X. XX. X.. .X.
.O. -> .O. .OX XO.
... ... ... ...
.X. XX. XO. .X. .X.
... -> ... ... X.O .X.
.O. .O. .X. ... .O.
ok
It’s interesting to see that the first player can start anywhere, but the 2nd player’s first move is constrained. If the first player starts in the middle, the 2nd player must play a corner to avoid losing. If the 1st player starts in the corner the 2nd player must respond by marking the middle. And if the first player starts on the side, the 2nd player must play a corner next to the first player’s mark, or play the middle, or play the side directly opposite.
The listing of the boards for ply 8 (which isn’t shown here) also includes one board where the middle is the one space not filled in. I didn’t expect to see this — I assumed the middle would always be marked after the first 3 or 4 ply. Even tic-tac-toe can hold surprises.
Hmmm, the Wikipedia entry for tic-tac-toe mentions some people also treat a Y-shaped arrangement of marks as a win. I wonder how that affects the game space?
Comments
Leave a Reply