A Tic-Tac-Toe game using bitboards to store player state.
What is a bitboard you might ask? It is a data structure that represents player positions on a board by using a series of bits.
Here is an example of how individual bits correspond to positions on a tic-tac board (3x3 grid),
1 | 2 | 3
---|---|--- 1|2|3|4|5|6|7|8|9 -> Position on Board
4 | 5 | 6 -> 1|0|0|0|1|0|0|0|1 -> Occupying Bit
---|---|---
7 | 8 | 9
Let’s transform that same bit sequence from above to better represent a board.
1 | 0 | 0
100 ---|---|---
100010001 -> 010 -> 0 | 1 | 0
001 ---|---|---
0 | 0 | 1
See how each individual bit corresponds to a place on the board after we’ve wrapped it around to form a square, this is a bitboard.
Let implement this in C
Now since there isn’t a datatype in C that is 9 bits long we’ll need to use a full blown integer which is 16 bits long ¯\_(ツ)_/¯
Two boards one for each player (X's and O's):
int bitboard[2] = {0, 0};
Why use bitboards to represent the game state? They are fast and relatively easy to manipulate.
For example to check a horizontal win for each player board we shift (>>) the bitboard over a few places and run an and (&) operation. If the value is greater than 1 we have a win:
int check_win_horizontal(int bitboard)
{
return ((bitboard) & (bitboard >> 1) & (bitboard >> 2));
}
The function above checks for horizontal wins, here’s how:
111000000 RIGHT-SHIFT 1 place(s)
= 011100000
111000000 RIGHT-SHIFT 2 place(s)
= 001110000
111000000 (original Bitboard)
011100000 (bitboard right-shifted 1 place)
AND 001110000 (bitboard right-shifted 2 places)
= 001000000 (1 bit set makes this a “true” value)
If we represent the bits from above as a board by wrapping after 3 characters
111 011 001 001
000 & 100 & 110 = 000
000 000 000 000
Simply put if there is overlap in placement after shifting the board a couple times places we know there were three in a row.
Cool! as you can see bitboards are powerful in that they can be manipulated using fast low level operations, here is another example of bitboards in a match 4 implentation.
You can download the source code here (from github).