python – 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

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
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="nn")

    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 '}decisiven"
        )

    board.add_and_update_state(next_move)
    print(board, end="n")
    print(board.is_game_over())