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 

Comments

Leave a Reply