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.

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

1 Comment 

Comments

One Response to “Tic-tac-toe in Erlang — game space search”

  1. Blank Board Game. | 7Wins.eu on June 28th, 2009 8:39 am

    [...] Tic-tac-toe in Erlang — game space search : Code Obscurata [...]

Leave a Reply