Before we can start implementing the actual artificial intelligence, we need to develop the basic game mechanics. The key element of Tic-tac-toe is obviously the game grid.

As the grid consists of 3x3 fields, we could go with a multidimensional array, where each field would store either a 0 (empty), 1 (X, player 1’s sign) or a 2 (O, player 2’s sign). But multidimensional arrays are difficult to serialize and you can’t do a simple pattern matching against them.

Integer to the rescue

This is why we will use an integer to store the grid. We need 3 different states per field, which we can store using 2 bits each. Given the 9 fields of the grid, we totally need 18 bits (doh, short is only 16-bit, so we will definitely need an integer). The actual bit position is calculated as: (x + (y * 3)) * 2

This makes it also very easy to reset the grid. We just need to set our integer back to 0.

Bitwise operators

Retrieving and setting the value of a field requires some bitwise operations. If we wanted to get the value of field (1, 1) (the center of the grid), we would start by calculating the bits’ position, using the formula above: position = (1 + (1 * 3)) * 2 = 8. That implies, we need bit 8 and 9 to get the actual value. To get this two bits, we will need a mask. The mask is generated by setting bit 8 and bit 9 (the desired bits) to 1: mask = 3 << position. Now we can do an AND to get the bits:

    00 00 01 00 10 10 00 00 01
AND 00 00 00 00 11 00 00 00 00
  = 00 00 00 00 10 00 00 00 00

We now shift the result again, to get the actual value (result >> position), which gives us a 2 decimal. Which is exactly what we expected, yay!

The resulting Java code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public int getField(int x, int y) {
  int position = calcualteBitPosition(x, y);
  int mask = getMask(position);
  return (this.grid & mask) >> position;
}

private int getMask(int position) {
  int mask = 3 << position;
  return mask;
}

private int calcualteBitPosition(int x, int y) {
  int position = (x + y * 3) * 2;
  return position;
}

Come on, make a move!

Say we would like to replace the value of (1, 1) with an X (not a valid game move, but we’ll do it anyway). We would first erase the current value at the given position, using AND with the inverted mask from above:

    00 00 01 00 10 10 00 00 01
AND 11 11 11 11 00 11 11 11 11
  = 00 00 01 00 00 10 00 00 01

Then we would shift the desired value (X, therefore 1) to the desired position and do an OR:

    00 00 01 00 00 10 00 00 01
OR  00 00 00 00 01 00 00 00 00
  = 00 00 01 00 01 10 00 00 01

The resulting Java code:

1
2
3
4

public void setField(int x, int y, int value) {
  int position = calcualteBitPosition(x, y);
  this.grid = (this.grid & ~getMask(position)) | (value << position);
}