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
speedI thought doing bitwise operations would be the fastest way to tackle this game, but my code is still very slow. In particular the linesself.__state = bit_clear(self.__state, GAME_ON) self.__state = bit_clear(self.__state, PLAYERX) self.__state = bit_clear(self.__state, PLAYERO)are egregiously slow.
stateI am going to stuff theBitBoardclass 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
MASK = 0b00000000000000001111111111111111
MASKX = 0b00000011111111100000000000000000
MASKO = 0b00000000000000000000000111111111
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())
def add_O(self, move):
return bit_set(self.__state, move)
def add_X(self, 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 add(self, move):
return self.add_X(move) if self.its_player_Xs_turn() else self.add_O(move)
def remove(self, move=None):
move = move if move else self.last_move
state = self.remove_X(move)
return self.remove_O(move, state)
def add_and_update_state(self, move):
self.last_move = move
self.last_state = self.__state
self.state = self.add(move)
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}}"
elif self._is_O_equal_to(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]
board.add_and_update_state(move)
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"
)
board.add_and_update_state(next_move)
print(board, end="\n")
print(board.is_game_over())
