Tic-tac-toe in Erlang — full 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:

Full game space

In my last post (Tic-tac-toe in Erlang — game space symmetries) I talk about how many tic-tac-toe boards there are in the entire tic-tac-toe game space. Using the Erlang function tic_count:report() in tic_count.erl, I put together the following table of all the possible boards in the tic-tac-toe game space.

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

This table treats all rotated and reflected boards as equivalent. The last-column calculation is explained in original post, where this table first appeared.

The last column shows how many possible boards there are at each ply, not treating rotated and reflected boards as equivalent and NOT PRUNING boards that don’t appear in the game space. A board with three-in-a-rows for both X and O is not in the tic-tac-toe game space but is still counted in the last column.

So what are the actual board counts for the game space when you don’t factor out rotations and reflections? The last column above was meant as an estimate, but really it’s an upper bound. I assumed it wouldn’t be too far wrong, but I wasn’t sure.

To find out I wrote a simple program. It’s in tic_game_space.erl if you want to see it. It reports the un-rotated/un-reflected board counts as follows.

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 9 9 9
2 (1+1) 0 72 72 72
3 (2+1) 0 252 252 252
4 (2+2) 0 756 756 756
5 (3+2) 120 1140 1260 1260
6 (3+3) 148 1372 1520 1680
7 (4+3) 444 696 1140 1260
8 (4+4) 168 222 390 630
9 (5+4) 62 (ties) 16 78 126
Totals 942 4,536 5,478 6,055

The 9-mark row tells us there are 16 tied (cat) boards possible, including all rotations and reflections as separate boards. Which means there are 958 final boards (942 winning boards and 16 ties).

The 4536 in the last row counts all continuing boards, including the initial blank board, and the 16 ties. Subtracting out the ties tells us there are 4520 boards that are not finished games.

Since there are 6055 possible boards and only 5478 boards in the actual game space, there must be 577 boards with the right number of Xs and Os that you’ll never see in a legal game of tic-tac-toe. All have at least 3 Xs and 3 Os. 48 (126 – 78) have no empty spots.

The reports from tic_game_space.erl provide a little more detail, so I’ll list them here. First we instruct the program to treat rotations and reflections as different.

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:report0( ).
Full tic-tac-toe game space:
  Player 1: all moves
  Player 2: all moves

  Total number of game paths: 255168

  Total number of boards: 5478
    Player 1 winning boards : 626
    Player 2 winning boards : 316
    Player 1 must respond to: 2423
    Player 2 must respond to: 2097
    Tie boards              : 16

  Total number of boards can also be broken down as:
    Initial board count        : 1
    Boards produced by player 1: 2739
    Boards produced by player 2: 2738

ok
3> tic_game_space:report0( ply_overview).
Full tic-tac-toe game space:
  Player 1: all moves
  Player 2: all moves

  Player 1 moves, leading to ply 1
    9 boards (all continue to ties)
  Player 2 moves, leading to ply 2
    72 boards (all continue)
      24 boards lead to ties
      48 boards lead to a win by player 1
  Player 1 moves, leading to ply 3
    252 boards (all continue)
      138 boards lead to ties
      64 boards lead to a win by player 1
      50 boards lead to a win by player 2
  Player 2 moves, leading to ply 4
    756 boards (all continue)
      136 boards lead to ties
      36 boards lead to a win by player 2
      584 boards lead to a win by player 1
  Player 1 moves, leading to ply 5
    1260 boards (1140 continuing)
      120 boards won by player 1
      264 boards lead to ties
      336 boards lead to a win by player 1
      540 boards lead to a win by player 2
  Player 2 moves, leading to ply 6
    1520 boards (1372 continuing)
      148 boards won by player 2
      200 boards lead to ties
      116 boards lead to a win by player 2
      1056 boards lead to a win by player 1
  Player 1 moves, leading to ply 7
    1140 boards (696 continuing)
      444 boards won by player 1
      200 boards lead to ties
      80 boards lead to a win by player 1
      416 boards lead to a win by player 2
  Player 2 moves, leading to ply 8
    390 boards (222 continuing)
      168 boards won by player 2
      80 boards lead to ties
      142 boards lead to a win by player 1
  Player 1 moves (last move)
    16 tie boards
    62 boards won by player 1
ok

These break up board counts between between the first and second player, and report predictions as well as final board totals.

Here is the same report, but treating rotations and reflections the same. These numbers agree with the first table above, and with the counts reported in the last post.

Eshell V5.6.5  (abort with ^G)
1> c( 'c:/src/erlang/tic_game_space').
{ok,tic_game_space}
2> tic_game_space:report0( ).
Full tic-tac-toe game space:
  Player 1: all moves
  Player 2: all moves

  Total number of game paths: 26830

  Total number of boards: 765
    Player 1 winning boards : 91
    Player 2 winning boards : 44
    Player 1 must respond to: 338
    Player 2 must respond to: 289
    Tie boards              : 3

  Total number of boards can also be broken down as:
    Initial board count        : 1
    Boards produced by player 1: 383
    Boards produced by player 2: 381

ok
3> tic_game_space:report0( ply_overview).
Full tic-tac-toe game space:
  Player 1: all moves
  Player 2: all moves

  Player 1 moves, leading to ply 1
    3 boards (all continue to ties)
  Player 2 moves, leading to ply 2
    12 boards (all continue)
      5 boards lead to ties
      7 boards lead to a win by player 1
  Player 1 moves, leading to ply 3
    38 boards (all continue)
      21 boards lead to ties
      9 boards lead to a win by player 1
      8 boards lead to a win by player 2
  Player 2 moves, leading to ply 4
    108 boards (all continue)
      18 boards lead to ties
      5 boards lead to a win by player 2
      85 boards lead to a win by player 1
  Player 1 moves, leading to ply 5
    174 boards (153 continuing)
      21 boards won by player 1
      35 boards lead to ties
      46 boards lead to a win by player 1
      72 boards lead to a win by player 2
  Player 2 moves, leading to ply 6
    204 boards (183 continuing)
      21 boards won by player 2
      27 boards lead to ties
      17 boards lead to a win by player 2
      139 boards lead to a win by player 1
  Player 1 moves, leading to ply 7
    153 boards (95 continuing)
      58 boards won by player 1
      27 boards lead to ties
      12 boards lead to a win by player 1
      56 boards lead to a win by player 2
  Player 2 moves, leading to ply 8
    57 boards (34 continuing)
      23 boards won by player 2
      11 boards lead to ties
      23 boards lead to a win by player 1
  Player 1 moves (last move)
    3 tie boards
    12 boards won by player 1
ok

These board counts describe the entire tic-tac-toe game space, and include plenty of unlikely and perverse games. But what if you remove some of these unusual games? How much do you reduce the game space? I’ll report on that in the next post.

March 6, 2009 | Filed Under analysis, download, erlang, sample code, tic tac toe, tutorial

Leave a Comment 

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.

February 18, 2009 | Filed Under analysis, erlang, sample code, tic tac toe, tutorial

Leave a Comment 

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.

February 16, 2009 | Filed Under analysis, erlang, multi-thread, parallel processing, sample code, tic tac toe, tutorial

2 Comments 

← Previous Page — Next Page →