Interview Question: Data Structure for Tic-Tac-Toe

by Mikael

Got this recently:

Tic-Tac-Toe decision tree

Tic-Tac-Toe decision tree

How would you design a data structure for the game Tic Tac Toe? The main objective is to provide: A method, as efficient as possible, for checking the board to see if there is a winner.

Hint: Some people may think first of a 2d array, which is very natural (and quite reasonable); to check for a winner, we go through 3 rows, 3 columns and 2 diagonals to see if any of them contains solely X’s or O’s. If you imagine a larger version of the game, this method is asymptotically linear and quite appealing. But Tic-Tac-Toe is 3×3 and we have not been asked to consider larger version. Start counting the number of operations more precisely, and see if you can’t do much much better for this particular case!

Solution: A programmer experienced at thinking on a lower-level should realize that we can do better in terms of the total number of operations on, say, an i386 architecture. The first thing to understand is that the number of possible configurations of the board is quite small, namely 3^9 = 19683. So the entire board can be stored in a single 32-bit word. This could be done in a number of ways, but good enough IMHO is as follows:

Designate two bits to each square of the board, ordered in the normal ways for arrays. I.e. if the board is described as:

1 2 3
4 5 6
7 8 9

The corresponding layout of bits in the word is “112233…99000…” (big-endian). Now create a byte or integer array H with 4^9 = 262144 elements. If the board is described by word W we can access H[W]; as a matter of pre-computation we can easily initialize this so that H[W]=0 if O (circle) is the winner, H[W]=1 if X is the winner and H[W]=2 otherwise.

The bit-pattern W is updated during the course of the game by shift (“<<” in C) operations and masking by bit-wise or (“|” in C), we won’t go into details about that. But by maintaining the board like this, the status of the winner is always accessible through the single (or-so) operation of loading H[W].

I believe this is quite a sufficient answer, but it might also be interesting to think about how the pre-computation of the array might be carried out as efficiently as possible… Do we really have to check every row/column/diagonal for each element? Most certainly not!

Advertisements

3 Responses to “Interview Question: Data Structure for Tic-Tac-Toe”

  1. how to calculate state efficiently?

  2. Reblogged this on coding hangover.

Trackbacks

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: