Yesterday I got linked to an article with interview questions for engineers and problem solvers at google including this one about tic-tac-toe.
The problem is to write a function which takes as arguments a Game of tic-tac-toe and a player, and returns whether the player has won the game. As an extension I wanted to do it in the most efficient way I could.
My first thought on reading it was that an sequence of bits could be used to store the state of the game for each player. Then the is_winner(Game, player) function would only have to test the bits for that player to see if the Xs or Os are in the right place to declare a win. As that would mean nine bits for each player, you would either need two 8 bit words each, or one each with a third shared between them to represent the extra bit.
Eventually I managed to squeeze the game into two 8-bit words which contain the state of play, but before I post and describe mine, I’ll give others the opportunity to do the same. To prevent cheating and so you know I didn’t steal your idea, make sure to save this somewhere I can’t tamper with it:
$ sha1sum tic_tac_toe.cpp
70ef68844d3173dd4363ff544e24aa57c28a7b52 tic_tac_toe.cpp
Steveire's Blog 
December 6, 2009 at 5:17 pm |
The secret number is 14.264, right?
December 6, 2009 at 5:23 pm |
Mike, you are remarkably not-far-off.
December 6, 2009 at 8:20 pm |
You forgot to round up, you would need 15 bits or log2(19,683) bits to encode 9 squares of empty, X, or O. There might be a saving by assuming a non-empty board. There can only be between 3 and 5 Os for an O win, and 3 and 4 Xs for an X win, so you would only need to test after O’s third go.
You only care about 8 winning states, if the squares are 9 bits labelled A to I (from top left): win = ABC + DEF + GHI + ADG + BEH + CFI + AEI + CEG.
If you store turns as the number of empty spaces from the top left: O would need 0 to 9 first go (10); X: 0 to 8 (9); O: 0 to 7 (8); … X: 0 to 2 (3); O 0 to 1 (2) ==> 10! = 3,628,800 less than 22 bits. Or turn number 0 to 9 and first go 0 to 8 empty spaces ==> 9 x 9! = 3,265,920 still less than 22 bits.
December 6, 2009 at 10:17 pm |
Interesting approach.
Actually Mikes number was close to another number which is not directly related to the puzzle. I hadn’t even considered checking the game state against one of the 19683 ways Xs Os and spaces could be arranged in a 9×9 grid. Infact it’s far fewer by the time impossible states are eliminated, so it’s probably possible to get more efficient than I thought.
I don’t think I undertand your logic with the number of turns though. “O would need 0 to 9 first go (10);” Do you mean that O can be placed in any of 9 squares at the start, i.e., 0 to 8? Or have I misunderstood entirely?
December 7, 2009 at 9:07 pm |
If you just have to make is_winner() fast, you can choose a data structure that contains, by construction, some bits for the winner.
Is that cheating? 🙂
December 8, 2009 at 2:31 am |
I don’t think there is much mileage in it, but Storing by turns would require a skip-over of 9 empty squares and place O, if the board were all empty, if you are not storing the number of goes. That is, before the first go, on the zeroth go: 9 empty squares, after the first go 8 empty squares, after the 2nd, 3rd, 4th, 5th, 6th, 7th, 8th, 9th go there would be 7, 6, 5, 4, 3, 2, 1, 0 empty squares. If you do store the number of goes, then there are 8, 7, 6, 5, 4, 3, 2, 1, 0, after the 1st, 2nd, …8th, 9th go.
Gof is right, probably the easiest data structure to check, is just 9 bits for the recently placed either O or X. The current state can be encoded as two 9 bit numbers: one for any Os placed and one for any Xs placed.
The whole state of the board can be stored in a nine digit base 3 number, which requires 15 bits
December 8, 2009 at 4:36 am |
To save the complete game state (including all possibly invalid states) you would need log_2(3^9) = 15,x bits. You can even store the current player in there if you multiply by 2 and use the LSB for the player ID.
You can, however, also save a number for each player’s turn on what field he puts his mark. So the first number would have to be in the range [0..8], the second [0..7] (because one field is already taken) and so on until you have “stored” 9 numbers. You need 3 bits for moves 1 to 5 and then only 2 bits. Without clever coding this comes out as > 16 bits so you’d have to squeeze this somehow.
I think with the first coding, however, you already put a state in 16 bits so this should be close to your solution.
what do i win? 😉
-Darkstar