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…