Tic-tac-toe in Erlang — game space symmetries
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 is also a smaller Erlang module for analyzing game-space symmetries called tic_count.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
Game space symmetries
I’ve written about how the tic-tac-toe program tic.erl does not attempt to be efficient when calculating next moves. In Game space search I describe how the program traverses 255,168 paths and visits 549,945 nodes to fully analyze the game space.
The tic-tac-toe game space is a directed graph with one starting node (the empty board). Traversing a link in the graph is the same as putting an X or O on the board. The starting node has 9 links out and no links in, and all winning and tie-game nodes have only links in and no links out.
Each path though the graph represents a game played from start to finish, which means there are 255,168 possible games. And each node in the graph is a tic-tac-toe board with X and O marks. The tic-tac-toe program searches all 255,168 game paths depth-first, producing and evaluating 549,945 boards along the way. One more if you count the starting empty board.
And that’s just to figure out the first move (starting from an empty board).
If you played all 255,168 games on paper you’d evaluate a lot more than 549,946 boards along the way (probably about 2 million assuming games average 8 moves). But the computer traverses depth-first, so the early boards are only visited a few times. In a depth-first traversal, the starting empty board and the 9 one-X and 72 one-X plus one-O boards are visited only once. The 252 two-X one-O boards are visited twice, the 756 two-X two-O boards are visited 4 times, etc. There are 362,880 ways to put 5 Xs and 4 Os on a tic-tac-toe board (assuming you first mark an X, then an O, then an X, etc). And you’d traverse 986,410 boards if you searched those 362,880 paths through the directed graph depth first. (These two numbers are explained below.) The reason there are only 255,168 game paths instead of 362,880 is because tic-tac-toe games end early when someone gets three in a row. You don’t always have to put 9 marks on the board.
Eliminating equivalent rotations and reflections
Thinking about these numbers and the game space made me curious. Just how big is the tic-tac-toe game space if you factor out all board rotations and reflections. Each tic-tac-toe board can be rotated and reflected 8 ways, and all 8 can be considered equivalent. To get some answers I hacked up tic_count:report() in tic_count.erl. Here’s what it looks like when I run it.
Erlang (BEAM) emulator version 5.6.5 [smp:2] [async-threads:0]
Eshell V5.6.5 (abort with ^G)
1> c( 'c:/src/erlang/tic/tic_count').
{ok,tic_count}
2> tic_count:report( ).
After ply 0:
0 winning boards
1 continuing boards
After ply 1:
0 winning boards
3 continuing boards
After ply 2:
0 winning boards
12 continuing boards
After ply 3:
0 winning boards
38 continuing boards
After ply 4:
0 winning boards
108 continuing boards
After ply 5:
21 winning boards
153 continuing boards
After ply 6:
21 winning boards
183 continuing boards
After ply 7:
58 winning boards
95 continuing boards
After ply 8:
23 winning boards
34 continuing boards
After ply 9:
12 winning boards
3 continuing boards
ok
3>
Here’s the same data in tabular form. The last column shows how many possible boards there are at each ply, not treating rotated and reflected boards as equivalent and not pruning out games there were won before 9 moves. So the last column gives us an idea of how effective these two game-space trimming techniques are.
| Number of marks on board | Number of winning boards | Number of continuing boards | Total number of boards | Potential number of boards |
|---|---|---|---|---|
| 0 (0+0) | 0 | 1 | 1 | 1 |
| 1 (1+0) | 0 | 3 | 3 | 9 |
| 2 (1+1) | 0 | 12 | 12 | 72 |
| 3 (2+1) | 0 | 38 | 38 | 252 |
| 4 (2+2) | 0 | 108 | 108 | 756 |
| 5 (3+2) | 21 | 153 | 174 | 1260 |
| 6 (3+3) | 21 | 183 | 204 | 1680 |
| 7 (4+3) | 58 | 95 | 153 | 1260 |
| 8 (4+4) | 23 | 34 | 57 | 630 |
| 9 (5+4) | 12 | (ties) 3 | 15 | 126 |
| Totals | 135 | 630 | 765 | 6,055 |
The first row represents the empty tic-tac-toe board with no Xs or Os.
The second row tells us there are only 3 first moves possible, after eliminating equivalent rotations and reflections.
The 9-mark row tells us there are only 3 tied (cat) boards possible, after eliminating rotations and reflections. Which means there are 138 final boards since there are 135 winning boards.
The 630 in the last row counts all continuing boards, including the initial blank board, and all ties. Subtracting out the ties tells us there are 627 boards that are not finished games.
To calculate the numbers in the last column you use the formula (9 choose Nx)*((9 – Nx) choose No). So when there’s 5 marks on the board, Nx is 3 and No is 2 and the formula yields (9!/6!3!)(6!/4!2!) or 84*15 which is 1260. Which means there are 1260 tic-tac-toe boards with 3 Xs and 2 Os. Which reduces to 174 boards once you get rid of all redundant rotations and reflections.
Above I mentioned there are 362,880 ways to put 5 Xs and 4 Os on a tic-tac-toe board. This is the same as (5!)(4!)(126), where 126 (from the table above) is the number of possible 5-X 4-O boards.
I also said you’d traverse 986,410 boards if you depth-first searched those 362,880 paths through the directed graph. That number is also from the last column, and is (0!)(0!)(1) + (1!)(0!)(9) + (1!)(1!)(72) + (2!)(1!)(252) + (2!)(2!)(756) + (3!)(2!)(1260) + (3!)(3!)(1680) + (4!)(3!)(1260) + (4!)(4!)(630) + (5!)(4!)(126).
Possible board states
The code in tic_count.erl can also print out sets of intermediate boards. Here are the three possible one-move boards, after rotations and reflections are weeded out.
5> tic_count:report_continuing_boards( 1). X.. ... ... .X. ... ... ... .X. ... ok 6>
Here are the three possible cat game (tie game) boards, again after eliminating equivalent rotations and reflections.
6> tic_count:report_continuing_boards( 9). XXO OOX XXO XXO OOX XOX XOX OXX OXO ok 7>
And here are the 12 possible winning games after 9 moves. Some of them are pretty unnatural, but they are all possible to achieve in tic-tac-toe with enough cooperation between the players.
7> tic_count:report_winning_boards( 9). XXX OOX OXO XXX OOX OOX XXO XXO OOX XXO XOO XOX XXO OXX OOX XOX OXO XXO XOX OXO XOX XOO XXX XOO XOO XXX OXO XOO XXX OOX XOO OXO XXX OXO XXX OXO ok 8>
Conclusion
We’ve seen that you can reduce the size of the tic-tac-toe game space quite a bit by taking into account simple board rotation/reflection symmetries. We can reduce the number of nodes (boards) in the entire tic-tac-toe game tree directed graph from about 5 or 6 thousand to 765.
765 nodes still makes a pretty big directed graph. You have to remember, however, this describes ALL possible games, no matter how pathological. This number decreases greatly if you can assume one player (the computer program) never makes a move that can lead to a loss, or lets a win slip away. You could still keep all the smart moves in the game-space graph and let the computer choose randomly between them.
This means that if the computer moves first, there will be no winning boards in the game space with 2, 4, 6, or 8 marks on the board. If the computer moves second there will be no winning boards with 1, 3, 5, 7, or 9 marks.
You can reduce the size of the game-space graph even more by choosing the next move ahead of time for every possible board the computer will face. This means that, if the computer moves first, there is only one possible board with 1 mark, and either 2 or 5 possible boards with 2 marks. If the computer moves 2nd there will be only 3 possible boards with 2 marks.
So this analysis is not complete. I don’t know how much you can reduce the directed graph of the game space where one of the players is the computer, but I suspect you could get it down to about 30 or 40 boards.
Another way to reduce the size of the game-space graph is to allow wild-cards in the board descriptions at each node. This is probably important for more complicated games where you evaluate larger board patterns, but of course in tic-tac-toe it is just a programming exercise.
When you calculate game graphs and allowed moves ahead of time in a game like tic-tac-toe you can save yourself a lot of brute force calculation later. It’s like programming experience into the program, so it knows how to handle certain situations ahead of time and doesn’t have to pause and think through all move starting from first principles. But you lose some flexibly too. The tic.erl program is pure brute force. But it can deal with any situation. It doesn’t mind if you decide to put down two or 3 Xs in a row, or erase marks, or skip turns. It doesn’t mind if you start out playing X but then switch to playing O after 2 turns.
It never complains, and it’s always ready to play no matter how many rules you’ve broken. It’s cool with whatever you want to do.
Comments
Leave a Reply