Tic-Tac-Toe Bitboards

CPE1704TKS

Board Games are, generally speaking, a collection of position based states and whilst it might seem intuitive for games like draughts, othello, chess, etc to have their positional states encoded in arrays and matrices of integers or floats it isn't efficient and it certainly isn't easy to reason about those states. So, quite early on (1950s and 1960s) it was discovered, and rediscovered, that it is more efficient to represent game states as 1 dimensional collections of bits and, more importantly, much easier and faster to reason about those states using boolean operators.

Such 1D bit arrays are termed bitboards and reach their zenith of complexity and utility in the game of Chess.

But it's not just Chess that can benefit from bitboards so can the humble game of Tic-Tac-Toe (a.k.a. Noughts & Crosses if you're Blighty based).


Some of my oldest non-trivial programming in C, for which I still retain copies, is for the game of Tic-Tac-Toe and it uses, what I thought at the time, was my amazing discovery of bit arrays to calculate win, lose or draw.  It wasn't an amazing discovery as I learned later of its widespread use to the point where it can be considered "obvious to a person having ordinary skill in the art...". Nevertheless, using bit arrays in the simple children's' game of Tic-Tac-Toe can be a pleasant introduction to both bitboards and using boolean logic to reason about games states.

Tic-Tac-Toe Game States

The game of Tic-Tac-Toe is played on a, usually, hand drawn grid of nine squares between 2 players who occupy squares in turn with either an 'X' or a 'O' symbol until either one player can connect 3 of their marks with a straight line (horizontally, vertically or diagonally) or no free squares remain - a draw!

Tic-Tac-Toe Bitboards

The physical 2D grid arrangement of the 9 squares of the Tic-Tac-Toe game whilst convenient for human eyes to play the game, is irrelevant to its logic and maintaining it programmatically is cumbersome and really rather pointless. Rather, two 1D arrays of 9 bits can better represent the game, one each for the 'X' and 'O' player positions. Arbitrarily then, numbering the Tic-Tac-Toe grid squares left-right & top to bottom:

0 1 2
3 4 5
6 7 8

As indices of a bit array (also known as a bit map, bit set, bit string, bit field or bit vector) of true T (1 = occupied) or false F (0 = empty) bits the empty playing grid now looks this:

                    'X'                                                             'O'
 0,1,2,3,4,5,6,7,8          0,1,2,3,4,5,6,7,8
|F|F|F|F|F|F|F|F|F|        |F|F|F|F|F|F|F|F|F|

But, and rather annoyingly, 9 bits do not conveniently fit into a single byte and so 2 bytes must be used for each Tic-Tac-Toe bit board, so in a little-endian system (like most PC and laptop memory due to dominance of Intel) the empty playing grid is a combination of 2 bitboard words of 16 bits each:

                                                                                   'X'
 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |

                                                                                   'O'
 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |


So if 'X' plays first (as is custom) for example into the centre followed by 'O' playing to bottom right:

. . .
. X .
. . O

 Then the bitboards will look like this:


                  'X'                                                        'O'
 0,1,2,3,4,5,6,7,8          0,1,2,3,4,5,6,7,8
|F|F|F|F|T|F|F|F|F|        |F|F|F|F|F|F|F|F|T|

In our little-endian memory model the bit board 16 bits words will be:

                                                                                   'X'
 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
|  |  |  |  |  |  |  |  |  |  |  | 1|  |  |  |  |

                                                                                   'O'
 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
|  |  |  |  |  |  |  | 1|  |  |  |  |  |  |  |  |

Or more simply now as two 16 bit binary numbers:

'X'  0000 0000 0000 1000
'O'  0000 0001 0000 0000

Which, because each 2 bit nybble can be represented by a hexadecimal number, becomes - in easier to read hexadecimal :

'X'  00 00 00 80 
'O'  00 01 00 00

If we combine the 2 'X' and 'O' player position 16 bit words into a convenient* 32 bit integer by arbitrarily setting the low word for 'X'  (player 1) and the high word for 'O'  (for player 2) we get an overarching game state.  Our overall game state is a 32 bit integer - which, whilst not guaranteed in C++, can be specified with the fixed width int32_t type.

The Game State:

                             'O'                                 'X'
bin: 0000 0000 0000 0001 0000 0000 0000 1000 

hex: 00 01 00 00 00 00 00 80

*convenient? Yes! Combining the game states into a single overarching unit gives us something that can be passed around between functions that generate moves, build a mini-max or alpha-beta search tree (more on that another day), score positions and evaluate outcomes as well as permit separation of the internal game model from the view(s) of that model and permit a simple controller required to only manipulate a single compact game state model.

Win, Lose or Draw

Okay, this next section assumes that you are familiar with simple boolean algebra and the boolean operators of your chosen programming language.

The boolean operators we will be using and their C++ (and many others) counter parts:

operator      C++

OR        |

AND       &

XOR       ^

NOT       !

But if you're not sure you could brush up with this lecture or maybe you just need a quick reminder:

4 = 00000100  // 'four' bit set
5 = 00000101  // 'four' bit and 'one' bit set

00000100 (4) & // AND: only keep bits set in both
00000101 (5)
--------
00000100 (4)

00000100 (4) | // OR: keep bits set in either
00000101 (5)
--------
00000101 (5)

00000100 (4) ^ //  EXCLUSIVE OR: keep bits only set in one but not the other
00000101 (5)
--------
00000001 (1)

Draw:

The game of Tic-Tac-Toe is over in a draw if all the squares on the grid are marked and no one has won. So how do you know if all the squares on the grid are marked? Consider this drawn game and its bitboards:

X O X    'X'  0000 0000 1010 1101
X O X    'O'  0000 0001 0101 0010
O X O

Of course, in the case of this and any full grid then for each 0 'empty' (a.k.a. false or unset) bit in one bitboard there is a corresponding 1 'full' (a.k.a. true or set) bit in the opposing bitboard. By combining these bit boards using the OR boolean operator (which in C++ is the vertical bar character | ) we can make a third bitboard C where every bit representing a Tic-Tac-Toe grid square is set:

'X'  0000 0000 1010 1101
           OR
'O'  0000 0001 0101 0010
            =
C  0000 0001 1111 1111

Then by comparing C to hexadecimal 01FF using the AND operator (which in C++ is the ampersand character &) the programmer can test for the state of a finished game that if no side has won must, therefore be a draw: (here the bits_ variable is the game state described above)

    bool drawn(int32_t bits_) { 

        if( ( (bits_ | (bits_ >> 16) ) & 0x01FF) == 0x01FF) { 
        // use the >> bit shift operator to 'slide' the upper 'O' word along

            bits_ = 0; //zero out the board

            std::cout << "It's a draw!!! ʕ·ᴥ·ʔ" << std::endl;

            return true;

        }

        return false;

    }

Whoa! What's with the >> thing?

In C++ the >> is another of the bitwise operators it can 'slide' a memory location to right by the given number of bits. What it puts in the 'holes' at the left depends what was in the top (left most) bit. Conversely the << bitwise operator shifts the memory location to the left by the given number of bits. 

In the drawn(int32_t bits_) testing function it is used to bring the 'O' bitboard (which is 16 bits long) right by 16 bits to be combined with the 'X' bitboard using the OR operator. This result is then compared with the full grid value of hexadecimal 01FF using the AND operator and the result of this is compared with the full grid value 01FF - if they are equal then the grid is full. 

Hang on a minute...

The drawn function only works if the last move to fill the board wasn't a winning move and it has no way of knowing! Yes of course, so before a gamestate can be correctly tested for a draw it must first be tested for a win!

But how do you test for a win?

Win:

The game of Tic-Tac-Toe is won by connecting 3 of your marks in a line, horizontal, vertical or diagonal. It follows then, that for the classical 9 square Tic-Tac-Toe grid, there are only 8 winning board positions:

X X X   . . .   . . .   X . .   . X .   . . X   X . .   . . X

. . .   X X X   . . .   X . .   . X .   . . X   . X .   . X .

. . .   . . .   X X X   X . .   . X .   . . X   . . X   X . .

        3 rows                                           3 columns                               2 diagonals

These 8 winning board states can be represented as 8 winning bitboards that can be stored in an array:

const std::vector<int> wins =

    { 0b0000000000000111,

      0b0000000000111000, // 3 rows

      0b0000000111000000,

      0b0000000100100100,

      0b0000000010010010, // 3 columns

      0b0000000001001001,

      0b0000000100010001, // 2 diagonals

      0b0000000001010100 };

Then these win states can be compared at each turn with the current bitboards of each side to test for a win using the AND boolean operator:

    bool won(int32_t bits_) {

        for(int i = 0; i < wins.size(); ++i) {

            if((bits_ & wins[i]) == wins[i]) {

                std::cout << " X wins!!! ʕ·ᴥ·ʔ" << std::endl;

                return true;

            } else if ((bits_ & (wins[i] << 16)) == (wins[i] << 16)) {

// use the bitshift << operator to slide the win bitboard left 

// to match up with the 'O' bitboard

                std::cout << " O wins!!! ʕ·ᴥ·ʔ" << std::endl;

                return true;

            }

        }

        return false;

    }

WOPR Putting the 'spare' bits to use

In the full implementation the unused parts int32_t game state are used to store which side's turn it is to play (only a single bit is required) (bit 15) and the high bit (bit 31) is used to indicate if the game is still on i.e. no side has yet won, lost or drawn. Using a single bit this way to indicate a binary 'on-off' state is termed a flag.

                        'O'                    'X'
int32_t game state 0000 0000 0000 0000 0000 0000 0000 0000

bit flags: game on & player turn (1 = player 'X', 0 = player 'O')

So, to test the game on flag simply AND the game state with a test value with only the high bit (31) set, this will return true if set, or false if unset: 

    bool game_on(int32_t bits_) {

        return bits_ & 0x80000000; // hexadecimal value of high bit set

    }

But how do you flip the flag bits without messing up the rest of the game state?

Here is where the eXclusive OR operator XOR comes in handy (What is actually happening with the XOR mask?).

We can use the NOT operator (which in C++ is the exclamation mark !) to test that a state has not occured.

Putting it all together

All of which lets the game logic test the game for a win, a draw or to continue play:

//if the game is on and has not been won and has not been drawn
if(game_on(bits_) && !won(bits_) && !drawn(bits_)) {
      
      bits_ ^=  0x8000; 

      // then flip the players turn bit to the opposing side
      // and carry on playing...

}


Whoa! Whats with the && thing?

Okay, so in C++ from perspective of boolean algebra the AND boolean or logical operator is actually the double ampersand && inasmuch as it interprets any non- zero value as TRUE and can be used for reasoning in boolean logic, such as asking a question about whether or not the game is still on and has not been won or drawn. It also performs short-circuiting, as it should for boolean algebra, meaning that if it returns false at any point during an evaluation then any remaining decisions or tests for truth are ignored - as they are now rendered moot by the false value.

In this way then, if the game has been won then it is not tested for a draw:
if(game_on(bits_) && !won(bits_) && !drawn(bits_)) {...


On the other hand the operator that performs the manipulation of bits in a memory location or bitwise operator is the single ampersand & which, if we used that in place of the &&, would result in the drawn testing function being called even if the games was won - which is not logical.
You might  also be wondering about the ^= part? 
That is a tasty bit of C++ syntactic sugar that saves having to write:
bits_ = bits_ ^ 0x8000;


Colophon

Tic-Tac-Toe has been an important part of the history of computer science and its beguiling simplicity belies its utility for learning and practicing some of the key computer science concepts and principles from boolean algebra, via memory models and bitboards to game decision trees. I hope that this has been of some use to anyone interested in these ideas?