# Representing Tic-Tac-Toe using a binary BitBoard

So I have been learning more about binary numbers lately, particularly in related to describing a gamestate. While perhaps chess is the most natural candidate I wanted to start of with something simpler. So I choose tic tac toe. For reference I used the following source, bit it not required to understand my post.

To challenge myself, I wanted the entire game logic + board state to be deducible from a single 32 bit integer; henceforth referred to as gamestate or simply state.

STATE = 0b11100000000000001000000000000000

• The first bit shows if the current board is active or not, e.g if you can play on it.
• The second and third bit will show who the winner is after the game is over.
• The one in the middle is not really desired, but I had to keep it there to be able to feed the state into a dict to figure out which squares are available.
• 9 bits are kept for X and 9 bits are kept for O

Speed is very important as I am going to build this into a bigger project running minimax or other heuristics over the code.

I am looking for feedback on two particular issues

• speed I thought doing bitwise operations would be the fastest way to tackle this game, but my code is still very slow. In particular the lines

self.__state = bit_clear(self.__state, GAME_ON)
self.__state = bit_clear(self.__state, PLAYERX)
self.__state = bit_clear(self.__state, PLAYERO)


are egregiously slow.

• state I am going to stuff the BitBoard class into an AI (minimax), and therefore tried to have a state that was easy to handle and pass around. I am not sure I accomplished this. Any tips on how to improve the handling of state under the given restrictions would be lovely.

Any any speed -- or other QoL -- improvements to managing tic-tac-toe logic (win, draw, whose turn it is) + board state using a single 32 bit integer would be much appreciated.

### Current state of code

import termcolor  # Used for colored output

def bit_shift(n):
return 1 << n

def bit_set(number, n):
"""
Setting a bit

Use the bitwise OR operator (|) to set a bit.

That will set the nth bit of number. n should be zero, if you want to set the
1st bit and so on upto n-1, if you want to set the nth bit.
"""

return number | (1 << n)

def bit_clear(number, n):
"""
Clearing a bit

Use the bitwise AND operator (&) to clear a bit.

That will clear the nth bit of number. You must invert the bit string with the
bitwise NOT operator (~), then AND it.
"""

return number & ~(1 << n)

def bit_toggle(number, n):
"""
Toggling a bit

The XOR operator (^) can be used to toggle a bit.
That will toggle the nth bit of number.
"""

return number ^ (1 << n)

def bit_check(number, n):
"""
Checking a bit

To check a bit, shift the number n to the right, then bitwise AND it:

That will put the value of the nth bit of number into the variable bit.
Changing the nth bit to x

"""

bit = (number >> n) & 1
return bit == 1

def bit_change(number, n, x):
"""
Changing a bit

Setting the nth bit to either 1 or 0 can be achieved with the following on
a 2's complement C++ implementation:

(number & ~(1 << n)) will clear the nth bit and (x << n) will set the nth bit to x.
"""

return (number & ~(1 << n)) | (x << n)

def states_are_equal(state_a, state_b):
return state_a & state_b == state_b

# Initialize a 32bit value for the board state
STATE = 0b11100000000000001000000000000000
GAME_ON = 0b10000000000000000000000000000000
PLAYERX = 0b01000000000000000000000000000000
PLAYERO = 0b00100000000000000000000000000000
X_O_BITLEN = 16  # How long are the X and O bits in state
PLAYER_BIT = 15
#
# Stores all ways to win when you fill inn a square
ROW1 = 0b0000000000000111
ROW2 = 0b0000000000111000
ROW3 = 0b0000000111000000
COL1 = 0b0000000100100100
COL2 = 0b0000000010010010
COL3 = 0b0000000100100100
DIAG1 = 0b0000000100010001
DIAG2 = 0b0000000001010100
#
WINNING_ = {
0: [ROW1, COL1, DIAG1],
1: [ROW1, COL2],
2: [ROW1, COL3, DIAG2],
3: [ROW2, COL1],
4: [ROW2, COL2, DIAG1, DIAG2],
5: [ROW2, COL3],
6: [ROW3, COL1, DIAG2],
7: [ROW3, COL2],
8: [ROW3, COL3, DIAG1],
}
#
# Stores all available squares for the 2**9 possible 3x3 boards
AVAILABLE_MOVES_ = {}
bitlen = 0b1110000000000000
for number in range(2 ** 9):
bin_str = str(bin(number + bitlen))[-9:]
AVAILABLE_MOVES_[number + bitlen] = sorted(
8 - index for index, char in enumerate(bin_str) if char == "0"
)

class BitBoard:
"""
Simulates a tic tac toe board using a 32 bit integer as state:
STATE = 0b11100000000000001000000000000000
1
The first bit the bit deciding if the game is still active
1
The second bit is deciding whose turn it is
11
The second and third bit decide whose won after the game is done
00 = draw, 10 = X won, 01 = O won

STATE = 0b11100000000000001000000000000000
\           / \             /
X              O
"""

def __init__(self, state=None, symbol_X="X", symbol_O="O"):

self.symbol_X = symbol_X
self.symbol_O = symbol_O

self.last_state = None
self.last_move = None
self.rows = 3
self.columns = 3
self.max_width = 1

if state:
self.state = state
else:
self.__state = STATE

def _shift_X(self, state=None):
state = state if state else self.state
return state >> X_O_BITLEN

def _shift_O(self):
return self.state << X_O_BITLEN

def _is_X_equal_to(self, state_a, state=None):
state = state if state else self.state
return states_are_equal(self._shift_X(state), state_a)

def _is_O_equal_to(self, state_a, state=None):
state = state if state else self.state
return states_are_equal(state, state_a)

def _X_or_O(self):
return self.__state | self._shift_X()

def get_available_squares(self):
return AVAILABLE_MOVES_[self._X_or_O() & MASK]

def count_available_squares(self):
return len(self.get_available_squares())

return bit_set(self.__state, move)

return bit_set(self.__state, move + X_O_BITLEN)

def remove_O(self, move=None, state=None):
state = state if state else self.state
move = move if move else self.last_move
return bit_clear(state, move)

def remove_X(self, move=None, state=None):
state = state if state else self.state
move = move if move else self.last_move
return bit_clear(state, move + X_O_BITLEN)

def its_player_Xs_turn(self):
return bit_check(self.__state, PLAYER_BIT)

def remove(self, move=None):
move = move if move else self.last_move
state = self.remove_X(move)
return self.remove_O(move, state)

self.last_move = move
self.last_state = self.__state

def remove_and_update_state(self, move=None):
move = move if move else self.last_move
self.last_move = None
self.last_state = self.__state
self.state = self.remove(move)

def change_2_last_state(self):
if self.last_state:
self.__state, self.last_state = self.last_state, self.__state

def change_player(self, player):
# Use 0 for first player, 1 for second
self.__state = bit_change(self.state, PLAYER_BIT, player)

def toggle_player(self, state=None):
self.__state = bit_toggle(self.state, PLAYER_BIT)

def is_game_over(self):
return bit_check(self.__state, GAME_ON)

def is_game_draw(self):
if not self.is_game_over():
return False
return not self.is_X_winner() and not self.is_O_winner()

def is_X_winner(self):
if not self.is_game_over():
return False
return bit_check(self.__state, PLAYERX)

def is_O_winner(self):
if not self.is_game_over():
return False
return bit_check(self.__state, PLAYERO)

def is_move_decisive(self, move=None):
state = self.add(move) if move else self.__state
move = move if move else self.last_move
if self.its_player_Xs_turn():
state_x = state >> PLAYER_BIT - 1
for win_state in WINNING_[move]:
if states_are_equal(state_x, win_state):
return True
else:
for win_state in WINNING_[move]:
if self._is_O_equal_to(win_state, state):
return True
return False

def is_game_drawn(self, move=None):
if self.is_move_decisive(move):
return False
available_squares = self.count_available_squares() - (1 if move else 0)
return not available_squares

@property
def state(self):
return self.__state

@state.setter
def state(self, state):
self.__state = state
if self.is_move_decisive(self.last_move):
self.__state = bit_toggle(self.__state, GAME_ON)
self.__state = bit_clear(
self.__state, PLAYERX if self.its_player_Xs_turn() else PLAYERO
)
elif not self.count_available_squares():
self.__state = bit_clear(self.__state, GAME_ON)
self.__state = bit_clear(self.__state, PLAYERX)
self.__state = bit_clear(self.__state, PLAYERO)
else:
self.toggle_player()

def __repr__(self):
return bin(self.__state)

def __str__(self):
X = termcolor.colored(self.symbol_X, "red", attrs=["bold"])
O = termcolor.colored(self.symbol_O, "blue", attrs=["bold"])
border = ""
sep = " "
empty = "."
counter = 0

column_lst = [empty for _ in range(self.columns)]
board_matrix = [column_lst for _ in range(self.rows)]
row_list = []
for x in range(self.rows):
for y in range(self.columns):
mask = bit_shift(y + x * self.columns)
if self._is_X_equal_to(mask):  # mask << X_O_BITLEN & self.__state:
board_matrix[x][y] = f"{X:>{self.max_width}}"
board_matrix[x][y] = f"{O:>{self.max_width}}"
else:
board_matrix[x][y] = f"{counter:>{self.max_width}}"
counter += 1
row_list.append(border + sep.join(board_matrix[x][:]) + border)
return "\n".join(row_list)

if __name__ == "__main__":

# Just some temp code to show off how the bit board works
board = BitBoard()
# print(board, end="\n\n")

moves = [1, 2, 3, 5, 0, 7, 4, 8]
for index in range(len(moves) - 1):
move, next_move = moves[index], moves[index + 1]
print(board, end="\n")
print("available squares = ", board.get_available_squares())
print(
f"The move {next_move} will be{' ' if board.is_move_decisive(next_move) else ' not '}decisive\n"
)

print(board, end="\n")
print(board.is_game_over())

• This is certainly more interesting that the typical tic-tac-toe question – worth an upvote! It would be better still if you were to provide more details on your benchmarking: how are you measuring speed (include that code in your question, if possible), and why do you think that your program is fast or slow (compared to what)? In my experience, the most interesting benchmarking questions, meaning the ones I've learned the most from, are comparative (why is code-X faster/slower than code-Y) rather than abstract (why is this code slow/fast). Anyway, I hope you get some good answers.
– FMc
Commented Jun 11, 2021 at 23:51
• @FMc If you try to run the code it hangs for about a second when achieving tic-tac-toe xD Commenting the aformentioned lines makes the line program run in an instant. This gives me a clear indication that the way i set, change and clear bits could be done better =) Thank you for liking my question! Commented Jun 11, 2021 at 23:57

• You have too many functions, making your code really hard to understand.
• You're being too helpful at the cost of maintainability. You don't need state if state else self.state in most functions. Just demand the consumer of the function to pass the correct value in.
• Your code is WET, you're duplicating code across *_O and *_X functions.
def remove_O(self, move=None, state=None):
state = state if state else self.state
move = move if move else self.last_move
return bit_clear(state, move)

def remove_X(self, move=None, state=None):
state = state if state else self.state
move = move if move else self.last_move
return bit_clear(state, move + X_O_BITLEN)

def remove(self, move=None):
move = move if move else self.last_move
state = self.remove_X(move)
return self.remove_O(move, state)


The only calls to remove_O and remove_X are in remove. You're already passing move, so the turnery is a waste of both human (reading) and computer (executing) time. Additionally passing self.state to remove_X would allow you to cut out 4 of the 9 lines of code. Then we can see remove_X and remove_O are really just calls to bit_clear. Do the same to remove's move and we've just cut out so much of your code.

def remove(self, move):
state = bit_clear(self.state, move + X_O_BITLEN)
return bit_clear(state, move)


As such lets apply 4 rules to your code:

1. Remove all 'helper' turneries.
2. Inline any function only used once.
3. Inline all global bit_* functions.
4. Remove any unused functions.
import termcolor  # Used for colored output

def states_are_equal(state_a, state_b):
return state_a & state_b == state_b

# Initialize a 32bit value for the board state
STATE = 0b11100000000000001000000000000000
GAME_ON = 0b10000000000000000000000000000000
PLAYERX = 0b01000000000000000000000000000000
PLAYERO = 0b00100000000000000000000000000000
X_O_BITLEN = 16  # How long are the X and O bits in state
PLAYER_BIT = 15
#
# Stores all ways to win when you fill inn a square
ROW1 = 0b0000000000000111
ROW2 = 0b0000000000111000
ROW3 = 0b0000000111000000
COL1 = 0b0000000100100100
COL2 = 0b0000000010010010
COL3 = 0b0000000100100100
DIAG1 = 0b0000000100010001
DIAG2 = 0b0000000001010100
#
WINNING_ = {
0: [ROW1, COL1, DIAG1],
1: [ROW1, COL2],
2: [ROW1, COL3, DIAG2],
3: [ROW2, COL1],
4: [ROW2, COL2, DIAG1, DIAG2],
5: [ROW2, COL3],
6: [ROW3, COL1, DIAG2],
7: [ROW3, COL2],
8: [ROW3, COL3, DIAG1],
}
#
# Stores all available squares for the 2**9 possible 3x3 boards
AVAILABLE_MOVES_ = {}
bitlen = 0b1110000000000000
for number in range(2 ** 9):
bin_str = str(bin(number + bitlen))[-9:]
AVAILABLE_MOVES_[number + bitlen] = sorted(
8 - index for index, char in enumerate(bin_str) if char == "0"
)

class BitBoard:
def __init__(self, state=None, symbol_X="X", symbol_O="O"):
self.symbol_X = symbol_X
self.symbol_O = symbol_O
self.last_state = None
self.last_move = None
self.rows = 3
self.columns = 3
self.max_width = 1

if state:
self.state = state
else:
self.__state = STATE

def get_available_squares(self):
return AVAILABLE_MOVES_[(self.__state | self.__state >> X_O_BITLEN) & MASK]

def remove(self, move):
return self.__state & ~((1 << move) | (1 << move + X_O_BITLEN))

def its_player_Xs_turn(self):
return self.__state & (1 << PLAYER_BIT)

if self.its_player_Xs_turn():
move += X_O_BITLEN
return self.__state | (1 << move)

self.last_move = move
self.last_state = self.__state

def toggle_player(self):
self.__state ^= 1 << PLAYER_BIT

def is_game_over(self):
return bool(self.__state & (1 << GAME_ON))

def is_move_decisive(self, move=None):
state = self.add(move) if move else self.__state
move = move if move else self.last_move
if self.its_player_Xs_turn():
state_x = state >> PLAYER_BIT - 1
for win_state in WINNING_[move]:
if states_are_equal(state_x, win_state):
return True
else:
for win_state in WINNING_[move]:
if states_are_equal(state, win_state):
return True
return False

@property
def state(self):
return self.__state

@state.setter
def state(self, state):
self.__state = state
if self.is_move_decisive(self.last_move):
self.__state ^= 1 << GAME_ON
self.__state &= ~(1 << (PLAYERX if self.its_player_Xs_turn() else PLAYERO))
elif not len(self.get_available_squares()):
self.__state &= ~((1 << GAME_ON) | (1 << PLAYERX) | (1 << PLAYERO))
else:
self.toggle_player()

def __repr__(self):
return bin(self.__state)

def __str__(self):
X = termcolor.colored(self.symbol_X, "red", attrs=["bold"])
O = termcolor.colored(self.symbol_O, "blue", attrs=["bold"])
border = ""
sep = " "
empty = "."
counter = 0

column_lst = [empty for _ in range(self.columns)]
board_matrix = [column_lst for _ in range(self.rows)]
row_list = []
for x in range(self.rows):
for y in range(self.columns):
mask = 1 << (y + x * self.columns)
if states_are_equal(self.__state >> X_O_BITLEN, mask):
board_matrix[x][y] = f"{X:>{self.max_width}}"
elif states_are_equal(self.__state, mask):  # mask & self.__state
board_matrix[x][y] = f"{O:>{self.max_width}}"
else:
board_matrix[x][y] = f"{counter:>{self.max_width}}"
counter += 1
row_list.append(border + sep.join(board_matrix[x][:]) + border)
return "\n".join(row_list)

if __name__ == "__main__":

# Just some temp code to show off how the bit board works
board = BitBoard()
# print(board, end="\n\n")

moves = [1, 2, 3, 5, 0, 7, 4, 8]
for index in range(len(moves) - 1):
move, next_move = moves[index], moves[index + 1]
print(board, end="\n")
print("available squares = ", board.get_available_squares())
print(
f"The move {next_move} will be{' ' if board.is_move_decisive(next_move) else ' not '}decisive\n"
)

print(board, end="\n")
print(board.is_game_over())

• The code isn't the prettiest. The excessive amount of (1 << GAME_ON) is making the code a little on the more ugly side.

• When inlining the functions the code (1 << GAME_ON) just smelt off to me. I thought I broke your code, however I hadn't.

The bit length of your state when you're at game over isn't 64. Instead the bit length is 2147483649. Which is coming from using (1 << GAME_ON) instead of just using GAME_ON.

>>> GAME_ON = 0b10000000000000000000000000000000
>>> (1 << GAME_ON).bit_length()
2147483649

• Upon fixing the 1 << ... bug we're instantly met with a new one.

Traceback (most recent call last):
return AVAILABLE_MOVES_[(self.__state | self.__state >> X_O_BITLEN) & MASK]
KeyError: 8383


The cause of the issue is you, for some reason, prefixed every move with 0b1110000000000000. If we just remove the prefix and use & MASK0 we've fixed the bug. And now the code takes so much less time to run. As we're probably bound by print rather than 1 << ... now.

• Additionally fixing the bits shows your is_game_over check is actually wrong. If the initial state is:

STATE   = 0b11100000000000000000000000000000


And your check is:

return bool(self.__state & GAME_ON)


Then either the name of the function or the return are inverted.

import termcolor  # Used for colored output

def states_are_equal(state_a, state_b):
return state_a & state_b == state_b

# Initialize a 32bit value for the board state
STATE   = 0b11100000000000001000000000000000
GAME_ON = 0b10000000000000000000000000000000
PLAYERX = 0b01000000000000000000000000000000
PLAYERO = 0b00100000000000000000000000000000
PLAYER  = 0b00000000000000001000000000000000

X_O_BITLEN = 16

# Stores all ways to win when you fill inn a square
ROW1    = 0b0000000000000111
ROW2    = 0b0000000000111000
ROW3    = 0b0000000111000000
COL1    = 0b0000000100100100
COL2    = 0b0000000010010010
COL3    = 0b0000000100100100
DIAG1   = 0b0000000100010001
DIAG2   = 0b0000000001010100

WINNING_ = {
0b000000001: [ROW1, COL1, DIAG1],
0b000000010: [ROW1, COL2],
0b000000100: [ROW1, COL3, DIAG2],
0b000001000: [ROW2, COL1],
0b000010000: [ROW2, COL2, DIAG1, DIAG2],
0b000100000: [ROW2, COL3],
0b001000000: [ROW3, COL1, DIAG2],
0b010000000: [ROW3, COL2],
0b100000000: [ROW3, COL3, DIAG1],
}

# Stores all available squares for the 2**9 possible 3x3 boards
AVAILABLE_MOVES_ = {}
for number in range(2 ** 9):
bin_str = f"{number:09b}"
AVAILABLE_MOVES_[number] = sorted(
8 - index for index, char in enumerate(bin_str) if char == "0"
)

class BitBoard:
"""
Simulates a tic tac toe board using a 32 bit integer as state:
STATE = 0b11100000000000001000000000000000
1
The first bit the bit deciding if the game is still active
1
The second bit is deciding whose turn it is
11
The second and third bit decide whose won after the game is done
00 = draw, 10 = X won, 01 = O won

STATE = 0b11100000000000001000000000000000
\           / \             /
X              O
"""

def __init__(self, state=None, symbol_X="X", symbol_O="O"):
self.symbol_X = symbol_X
self.symbol_O = symbol_O
self.last_state = None
self.last_move = None
self.rows = 3
self.columns = 3
self.max_width = 1

if state:
self.state = state
else:
self.__state = STATE

def get_available_squares(self):
return AVAILABLE_MOVES_[(self.__state | self.__state >> X_O_BITLEN) & MASKO]

def toggle_player(self):
self.__state ^= PLAYER

def its_player_Xs_turn(self):
return self.__state & PLAYER

if self.its_player_Xs_turn():
move <<= X_O_BITLEN
return self.__state | move

self.last_move = move
self.last_state = self.__state

def is_game_over(self):
return not self.__state & GAME_ON

def is_move_decisive(self, move):
if self.its_player_Xs_turn():
state >>= X_O_BITLEN
for win_state in WINNING_[move]:
if states_are_equal(state, win_state):
return True
return False

@property
def state(self):
return self.__state

@state.setter
def state(self, state):
self.__state = state
if self.is_move_decisive(self.last_move):
self.__state ^= GAME_ON
self.__state &= ~(PLAYERX if self.its_player_Xs_turn() else PLAYERO)
elif not len(self.get_available_squares()):
self.__state &= ~(GAME_ON | PLAYERX | PLAYERO)
else:
self.toggle_player()

def __repr__(self):
return bin(self.__state)

def __str__(self):
X = termcolor.colored(self.symbol_X, "red", attrs=["bold"])
O = termcolor.colored(self.symbol_O, "blue", attrs=["bold"])
border = ""
sep = " "
empty = "."
counter = 0

column_lst = [empty for _ in range(self.columns)]
board_matrix = [column_lst for _ in range(self.rows)]
row_list = []
for x in range(self.rows):
for y in range(self.columns):
mask = 1 << (y + x * self.columns)
if states_are_equal(self.__state >> X_O_BITLEN, mask):
board_matrix[x][y] = f"{X:>{self.max_width}}"
elif states_are_equal(self.__state, mask):  # mask & self.__state
board_matrix[x][y] = f"{O:>{self.max_width}}"
else:
board_matrix[x][y] = f"{counter:>{self.max_width}}"
counter += 1
row_list.append(border + sep.join(board_matrix[x][:]) + border)
return "\n".join(row_list)

if __name__ == "__main__":

# Just some temp code to show off how the bit board works
board = BitBoard()
# print(board, end="\n\n")

moves = [1, 2, 3, 5, 0, 7, 4, 8]
moves = [1 << m for m in moves]
for index in range(len(moves) - 1):
move, next_move = moves[index], moves[index + 1]
print(board, end="\n")
print("available squares = ", board.get_available_squares())
print(
f"The move {next_move} will be{' ' if board.is_move_decisive(next_move) else ' not '}decisive\n"
)

print(board, end="\n")
print(board.is_game_over())


The code has some more improvements to be made. But I'm going to stop my answer here, since the code now runs as intended and isn't super slow.

• Great comments! I will read them carefully and post a follow up question. I guess a broader question is what my BitBoard class should know or care about? My broader idea (which I clearly was not able to do) was to minimize overhang. Meaning BitBoard should not care whether a move is valid, nor whether the game is still running, just set the proper state. I am open to suggestions but checking (and not just setting) GAME_ON for every function seems excessive when I am going to put this into an minimax algorithm. I built a TicTacClass for move and state validation (not included here) =) Commented Jun 12, 2021 at 12:40
• @N3buchadnezzar "what my BitBoard class should know or care about?" Is exactly the question I stopped before. I have a few ideas, but explaining them would take a while and would be worthy of a new answer. "checking GAME_ON for every function seems excessive" and you'd be correct, I think your state setter is causing your BitBoard class to loose sight of what you intend it to be. I think having BitBoard and TicTacClass are good separations but I think you've not delegated enough to TicTacClass. Commented Jun 12, 2021 at 12:48

# Bugs

## COL1 == COL3

This will make it hard to win in one of those two columns!

## if move

Your mainline will call board.add_and_update_state(move) with move = 0, which in turn calls various other methods with move = 0.

Functions like is_move_decisive() use statements like move = move if move else self.last_move, which therefore replaces move with self.last_move for the rest of the function if move is a false value, like 0. When called with next_move = 0, is_move_decisive() won’t call self.add(move), but rather uses the unmodified state.

You probably intended if move is not None.

Using a default argument to mean the last move for some functions and the current state for others (no move) is code confusing. Be explicit.