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:

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.

Tic-tac-toe in Erlang — parallel processing

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. The source file and this tutorial are organized as follows:

Parallel processing

One of the great things about Erlang is how easy it is to experiment with multi-processing. Or multi-threading. In Erlang there’s not much difference because you don’t work with global variables and mutable data structures. So you don’t have to worry about locking. Most of the time.

In Erlang it’s easy and cheap to start a new “process”. Remember an Erlang process is not an operating system process. An Erlang process is much lighter weight. You can have tens of thousands of them running in parallel on your underpowered laptop and not even notice.

It starts to affect your thinking.

And since we’re looking at a tic-tac-toe sample program with next move calculations and predictions, let’s see how we can take the massively inefficient game space search and make it massively parallel too.

Original implementation

Remember the functions to search the game space chain like this:

The calc_all_outcomes(..) function is just waiting to be parallelized (is that a word?). It is where the search space branches. With comments and asserts stripped out the Erlang code looks like this.

calc_all_outcomes( Board, Xo, Countdown, Outcome_start ) ->
  [ given_move_predict_outcome(
        Board, Xo, Pos, Countdown, Outcome_start)
    || Pos <- lists:seq( 1, 9) ].

Or you might find it easier to read if expressed with map instead of as a list comprehension. I like map myself, I'm used it so long it's like an old friend. But the two forms are equivalent.

calc_all_outcomes( Board, Xo, Countdown, Outcome_start ) ->
  lists:map(
    fun( Pos ) ->
      given_move_predict_outcome(
        Board, Xo, Pos, Countdown, Outcome_start)
    end,
    lists:seq( 1, 9))

Parallel implementation

We can implement this as a function that starts up 9 processes, and then waits for them all to finish and send back results. This is a pretty standard transformative pattern: re-interpreting a map as a scatter to start the processes, and then a gather to bring all the results back home.

calc_all_outcomes( Board, Xo, Countdown, Outcome_start ) ->
  Pid_parent = self( ),

  Scatter_fn =
    fun( Pos ) ->
      spawn(
        fun( ) ->
          % Send results back to parent
          Pid_parent !
            { Pos,
              given_move_predict_outcome(
                Board, Xo, Pos, Countdown, Outcome_start)
            }
        end)
    end,

  Gather_fn =
    fun( Pos ) ->
      receive { Pos, Outcome_predicted } ->
        Outcome_predicted
      end
    end,

  % Start 9 processes
  lists:foreach( Scatter_fn, lists:seq( 1, 9)),

  % Gather and order 9 results
  lists:map( Gather_fn, lists:seq( 1, 9))

You can also express this as nested list comprehensions. The code is way cool even if it's a little more difficult to understand.

calc_all_outcomes( Board, Xo, Countdown, Outcome_start ) ->
  Pid_parent = self( ),
  [ receive {Pos, Outcome_predicted} ->
      Outcome_predicted
    end
    || Pos <-
       [ Pos
         || Pos <- lists:seq( 1, 9),
            is_pid(
              spawn(
                fun( ) ->
                  Pid_parent !
                    { Pos,
                      given_move_predict_outcome(
                        Board, Xo, Pos,
                        Countdown, Outcome_start)
                    }
                end)) ]]

Not-so parallel implementation

The thing to remember is to get all the processes going before listening for any return messages. When I first implemented this function I forgot that and came up with this wrong implementation.

% Incorrect implementation:
calc_all_outcomes( Board, Xo, Countdown, Outcome_start ) ->
  Pid_parent = self( ),
  lists:map(
    fun( Pos ) ->
      spawn(
        fun( ) ->
          Pid_parent !
            given_move_predict_outcome(
              Board, Xo, Pos, Countdown, Outcome_start)
        end),
      receive Outcome_predicted -> Outcome_predicted end
    end,
    lists:seq( 1, 9))

This spawns a process, and then waits for its results before spawing the next one. This actually works fine (and is barely slower than the original non-parallel implementation), but it never has more than 9 processes alive (and one running) at a time.

Analysis

So, how did this work? Wellllll, in game space search I mention that given_move_predict_outcome(..) is evaluated 2,653,002 times if you fully predict all outcomes for an empty board. Which means the parallel code above will spawn 2,653,002 Erlang processes, all of which can potentially be running at the same time. Which is a little breathtaking.

And it's a little too much. Erlang on my system can't do it. (It has no problem with the "wrong" implementation given above though. That also spawns 2,653,002 processes, but never more than 9 at a time.)

But the code in tic.erl never predicts an empty board. It only predicts after at least one mark is down. Which means it would never try to spawn more than 308,817 processes.

And, not surprisingly, that's still too many. Erlang chokes.

But you CAN run the above code with two marks (an X and an O) on the tic-tac-toe board. In that case Erlang only has to spawn 30 or 40 thousand processes, all running at the same time. That's still pretty impressive. On my setup I max out at about 80,000 simultaneous processes.

Final thoughts

Working with something like Erlang, where it's easy to spawn thousands of processes, influences how you think and how you experiment. It let's you ask how you can solve a problem using a bunch of communicating agents, or using a fabric of processes interconnected in a specific hardware architecture. It let's you test ideas and gain a clearer understanding of how a parallel solution might work. If I were designing a parallel system that I eventually going to implement in C and MPI/OpenMP/CUDA, I'd consider starting with prototyping and concept checking on an Erlang testbed. It'd help catch mistakes and highlight problems early on.

Tic-tac-toe in Erlang — game space search

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. The source file and this tutorial are organized as follows:

Game space search

If you look at the code in the next move calculations and predictions section, you’ll see the functions chain like this.

This is how the program searches the game space. It searches exhaustively, all the way down to finished games. It does not prune the search tree, or estimate the value of intermediate boards, or look for symmetries. It evaluates the same board layout many times over.

So how inefficient is this brute-force solution?

The recursion is not deep since all games are over in 9 moves or less, but it is wide. If you ignored collisions and games that ended early you’d end up looking at 387,420,489 (9 to the 9th power) leaf states, each representing a path thru the game space. Getting rid of collisions reduces that number to 362,880 (9 factorial), assuming you start with a blank board. Still a big number, but more than 1000 times smaller than the original.

But 362,880 still looks pretty big compared to all the possible full boards. There are only (9 choose 5) ((9! / (5!)(4!)) -> 126) ways to arrange 5 Xs and 4 Os on a tic-tac-toe board.

If you also trim back game paths that are won or lost before 9 moves, you end up with 255,168 leaf states (paths through the game space), 209,088 winning games and 46,080 ties. Again, this assumes you start with an empty board and calculate outcomes for each of the 9 starting spots.

Another measure of the search space is to count the nodes of the search space instead of just the leaves. We can do that by counting how many times given_move_predict_outcome(..) is evaluated. Starting with an empty board, calling predict_outcomes(..) will visit 2,653,002 nodes in the search tree, although most of them are collisions. 549,945 are not collisions, including 255,168 won/lost/tied boards and games that are not yet decided.

These numbers all assume we are predicting the outcome for all 9 positions on an empty board. The numbers drop quickly after you X a single spot. The following table shows how putting a single mark on the tic-tac-toe board reduces the game search space dramatically.

Empty board Board with single corner X Board with single side X Board with center X
All nodes in game-space
search tree
2,653,002 287,757 308,817 266,697
All boards in
search tree
(nodes excluding collisions)
549,945 59,704 63,904 55,504
Undecided boards 294,777 31,972 34,312 29,632
Decided boards
(won, lost, or tied)
255,168 27,732 29,592 25,872
Winning and
losing boards
209,088 22,548 24,408 21,264
Tied boards
(cat games)
46,080 5,184 5,184 4,608

When you search the game space tree for an empty board, you end up with tie-game predictions for starting moves in each of the 9 open spaces. So I coded that into tic.erl (the tic-tac-toe program in Erlang). At first I wasn’t going to include even that simple optimization (optimization was not the goal), but without it the program pauses for a couple seconds when you start a new game. Apparently calling a couple functions 2,653,002 times isn’t instantaneous.

But any way you slice it, you have admit we’re doing an awful lot of work for a game with only 126 final board positions. And that’s not even counting rotation and reflection redundancies and games that end before the board is full. There’s no way you could call this efficient.

But in this case it doesn’t really matter. It’s efficient enough for a sample program.

Next Page →