On Storing State of Tic-tac-toe

Following up on a post I wrote a couple of days ago about storing state in an int, I wrote a tic-tac-toe game in C that did just that.

The first version used two shorts, one for the X player and the other for the O. This worked great, and it has the clear advantage of being more readable than that of storing the entire state in one int.

Using Two shorts

The crux is that the state for one player can fit in a short (if the possible number of moves is greater than the storage capacity of the type, then this method is not possible). Since there are nine possible plays for a player, this fits neatly into 9 bits, where each bit, as a power of two, represents one of the positions on the board.

When a player makes a move, the bit that maps to that position is turned on:

void play(short player, short *x, short *o) {
char buf;

printf("Your play [%c]: ", player % 2 ? 'X' : 'O');
fgets(buf, 3, stdin);

int move = atoi(buf);

if (player % 2) {
if ((*x & (1 << move)) == 0)
*x |= 1 << move;
} else {
if ((*o & (1 << move)) == 0)
*o |= 1 << move;
}
}

The important bits (rimshot) are checking if the play has already been made and, if not, adding it to state. This is done using logical AND and OR, respectively:

...

if ((*x & (1 << move)) == 0)
*x |= 1 << move;

...

The code then checks to see if there is a winner. How is this done? We again use our friend logical AND, comparing each winning state against the current player state:

short is_winner(int *winners, short *x, short *o) {
short k = 0;
char winner = '\0';

while (*(winners + k)) {
int w = *(winners + k);

if ((w & *x) == w) {
winner = 'X';
break;
}

if ((w & *o) == w) {
winner = 'O';
break;
}

k++;
}

...
}

If the short containing the player’s state equals one of the elements in the array, we know we’ve found a winner. Magic!

The function above uses pointer arithmetic to move through the winners array.

Here are the eight possible winning states:

int winners[] = {
// Across.
7, 56, 448,

// Down.
73,
146,
292,

// Diagonal.
273,
84
};

How I determined the winners array.

Let’s think of the board like this:

+---------+
|0 | 1 | 2|
|---------|
|3 | 4 | 5|
|---------|
|6 | 7 | 8|
+---------+

There are eight different ways a player can win the game: across (3), down (3), and diagonally (2).

Now, here’s the important bit: the numbers represent the number of left shifts. For example, the total number of “on” bits for the across wins are computed like this:

1 << 0 = 1 1 << 1 = 2 1 << 2 = 4 = 7 bits

1 << 3 = 8 1 << 4 = 16 1 << 5 = 32 = 56 bits

1 << 6 = 64 1 << 7 = 128 1 << 8 = 256 = 448 bits

( Note that all the left shifts compute to powers of two. )
Indeed, those are the first three elements in the winners array.

Recall that ANDing a value against another that has the same bits in common will produce that number.

Weeeeeeeeeeeeeeeeeeeeee

Using an int

Why not use an int? As regards space, it’s obviously the same as two shorts, so no difference (or optimization) there, but it would be nice to have all state stored in just one location rather than two. And why shouldn’t I get what I want?

We only need to make a minor change to the first version to achieve this goal, which will be to fiddle with the state to capture the higher bits of the int. Now, instead of two separate states, we’ll have the X values in the lower two bytes and the 0 in the upper two bytes. Once we do this, all of the offsets in the other functions will just work.

Let’s take an example where our one int state variable contains the value 458794. It looks like the following in bits:

00000000 00000111 00000000 00101010

Remember, these four bytes hold the state for both players. The state for X occupies the lower two bytes and O the higher.

Since we only want O’s state, we right-shift 16 bits, essentially “chopping off” the two low bytes that we don’t need:

00000000 00000111

Then, we just do the same bitwise operations as the first version. Remember, once we get the state down to a short, everything will just work.

Kool moe dee.

We just need to do this everywhere there is an operation on O’s state. In fact, the change to do this simply looks like:

short o = *state >> 16;

And when O makes a play, we’ll write it to state by shifting back 16 bits and then ORing the bits, which has the same effect as adding to the state.

*state |= o << 16;

Those are some pretty sweet taters!

Here’s the code for the second version.

Conclusion

This is some of the most fun I’ve had programming. I love bit fiddling, and if you don’t feel the same, then as a licensed psychiatrist I can definitely say without hesitation that there is something seriously wrong with you.

Also, it goes without saying that these types of operations are language agnostic, so hopefully you don’t think that it doesn’t apply to your high-level language.