使用二进制BitBoard表示Tic-Tac-Toe

Question

因此，我最近学到了更多关于二进制数的知识，特别是在描述游戏状态方面。虽然国际象棋也许是我最自然的选择，但我想从更简单的东西开始。所以我选择了抽搐脚趾。作为参考，我使用了以下来源，比特它不需要了解我的帖子。

To挑战了我自己，我希望整个游戏逻辑+板状态可以从单个32位整数中还原出来；从此以后称为游戏状态或简单状态。

STATE = 0b11100000000000001000000000000000

• 第一位显示当前板是否处于活动状态，例如，您是否可以在其上播放。
• 第二和第三位将显示谁是胜利者后，游戏结束。
• 中间的那个并不是真正想要的，但我必须把它保存在那里，这样才能把状态反馈到一个小块中，以确定哪些方块是可用的。
• 9位为X保留，9位为O位

Speed是非常 important，因为我将把它构建成一个更大的项目，在代码上运行minimax或其他启发式方法。

我正在寻求关于两个特定问题的反馈意见。

• <#>speed我认为按位操作将是解决此游戏的最快方法，但我的代码仍然非常慢。特别是，直线self.__state = bit_clear( self.__state，GAME_ON) self.__state = bit_clear(self.__state，PLAYERX) self.__state= bit_clear(self.__state，PLAYERO)异常缓慢。
• state我将把BitBoard类填充到AI (minimax)中，从而尝试具有易于处理和传递的状态。我不确定我完成了这件事。任何关于如何改进在给定限制下的状态处理的提示都是很好的。

任何速度-或其他QoL -改进管理tic逻辑(win，state，谁轮到它)+板状态使用一个32位整数将是非常感激的。

代码

的当前状态

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())

Answer 1

• 您有太多的功能，使您的代码真的很难理解。
• 以可维护性为代价，你太有帮助了。在大多数函数中，您不需要state if state else self.state。只需要求使用者的函数传递正确的值。
• 您的代码是湿的，您正在跨*_O和*_X函数复制代码。

def remove_O(self，move=None，state=None)：state = state if state self.state self.state = move if self.state self.last_move返回bit_clear( state，move) def remove_X(self，move=None，state=None)：state = state if self.state move = move if self.state self.last_move bit_clear(state，move + X_O_BITLEN) def remove(self，move=None，state=None)move=None)：移动=移动如果移动其他self.last_move状态=self.remove_X(移动)返回self.remove_O(移动，状态)

对remove_O和remove_X的唯一调用都在remove中。您已经通过了move，所以turnery浪费了人类(阅读)和计算机(执行)时间。此外，将self.state传递给remove_X将允许您从9行代码中删除4行代码。然后我们可以看到remove_X和remove_O实际上只是对bit_clear的调用。对remove's move也这样做，我们刚刚删除了大量的代码。

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

因此，让我们将4条规则应用于代码：

1. 移除所有的“帮手”图勒。
2. 内联任何函数只使用一次。
3. 内联所有全局bit_*函数。
4. 删除任何未使用的函数。

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
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:
    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)

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

    def add_and_update_state(self, move):
        self.last_move = move
        self.last_state = self.__state
        self.state = self.add(move)

    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("inner.add_and_update_state")
        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())

• 代码不是最漂亮的。过多的(1 << GAME_ON)使代码变得更加丑陋。
• 当插入函数时，代码(1 << GAME_ON)就会对我产生影响。我以为我破坏了你的代码，但是我没有。当你在游戏结束时，你的状态的比特长度不是64。相反，位长是2147483649。它来自于使用(1 << GAME_ON)而不是仅仅使用GAME_ON。>>> GAME_ON =0b100000000000000000000000000000 >>> (1 << GAME_ON).bit_length() 2147483649
• 在修复1 << ...错误后，我们立即会遇到一个新的错误。回溯(最近一次调用)：返回AVAILABLE_MOVES_ KeyError: 8383问题的原因是由于某种原因，您用0b1110000000000000作为每个动作的前缀。如果我们只删除前缀并使用& MASK0，我们就修复了这个bug。现在代码运行所需的时间要少得多。因为我们现在可能受到print而不是1 << ...的束缚。
• 此外，修复比特显示您的is_game_over检查实际上是错误的。如果初始状态为: state =0b11100000000000000000000000，而您的检查是: return (self.__state& GAME_ON)，则函数的名称或返回都会倒置。

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
MASK    = 0b00000000000000001111111111111111
MASKX   = 0b00000011111111100000000000000000
MASKO   = 0b00000000000000000000000111111111
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

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

    def add_and_update_state(self, move):
        self.last_move = move
        self.last_state = self.__state
        self.state = self.add(move)

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

    def is_move_decisive(self, move):
        state = self.add(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("inner.add_and_update_state")
        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())

代码还有更多的改进要做。但是我要在这里停止我的回答，因为代码现在按预期运行，而且不是超慢的。