Shall we play a game?

My solution to yesterdays tic tac toe problem is here.

The trick is explained in the comment at the top, but essentially I am storing the positions of markers for ‘X’ and ‘O’ only from the first 8 positions in the grid so that it takes up only 8 bits for each player. The state of the 9th box in the game is discovered by using a population count on both players game states and determining which if any is missing a mark. This requires the extra information of which player was last to make a move. You could call that cheating, but it does work, and the simulation is there to prove it.

The simulation runs 1 million games of tic tac toe in 14.905 seconds on my laptop. Not bad really. It’s good to get into the spirit of optimization now that we’re in bug fixing mode for 4.4. There’s lots of good tips in Jon Bentley’s Programming Pearls. I highly recommend it to anyone interested in this stuff.

As an exercise for the reader, modify the example to pick the best available position each time instead of a random box to place a mark.

Anyway, onto my next project, Global Thermonuclear War…

3 Responses to “Shall we play a game?”

  1. ComputerDruid Says:

    Props for the wargames reference

  2. Mike Says:

    If you can represent the board in just 2 bytes (let’s call them A and B), I wonder if there is a binary operation that let’s you determine the winner just be evaluating A op B.

    If not, maybe you can persuade chipmakers to include one in SSE6 or something 😉

  3. steveire Says:

    Not really Mike.

    The way I determined the winner was by evaluating A, B, and the player that played most recently. If you only have A and B, you could tell that a player won in 6 of the 8 winning scenarios. For the other two though you’d get false negatives.

    Probably not a compelling enough reason for chipmakers to add to their designs :).

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: