我现在在学习制作一个五子棋AI脚本，使用极小极大搜索（minimax）算法，并结合 α-β 剪枝以及其他方法来提高性能。就目前而言，我已经在项目中实现了一个置换表。问题是，这个表的命中率大约只有1% 到4%，我觉得相当低。

于是我先做一个Zobrist哈希表，

import random

BOARD_SIZE = 19

zobrist_table = [[[random.getrandbits(64) for _ in range(3)] 
                  for _ in range(BOARD_SIZE)] 
                 for _ in range(BOARD_SIZE)]

def get_initial_hash(grid):
    h = 0
    for r in range(BOARD_SIZE):
        for c in range(BOARD_SIZE):
            piece = grid[r][c]
            if piece != ' ':
                h = update_hash(piece, r, c)
    return h

def update_hash(player, row, col, current_hash):
    p_idx = 1 if player == 'X' else 2
    current_hash ^= zobrist_table[row][col][p_idx]
    return current_hash

随后我将它集成到五子棋实现中的棋盘类里，

def __init__(self, grid=None):
        self.rows = ROWS
        self.cols = COLS
        self.current_hash = 0

        if grid:
            self.grid = grid
            self.current_hash = get_initial_hash(self.grid)
        else:
            self.grid = [[' ' for _ in range(self.cols)] for _ in range(self.rows)]

    def set_move(self, move, player):
        if self.grid[move.row][move.col] == ' ':
            self.grid[move.row][move.col] = player
            self.current_hash = update_hash(player, move.row, move.col, self.current_hash)
            return True
        return False

    def undo_move(self, move):
        player = self.grid[move.row][move.col]
        if player != ' ':
            self.current_hash = update_hash(player, move.row, move.col, self.current_hash)
            self.grid[move.row][move.col] = ' '

然后在剪枝函数中，我通过以下方式来更新哈希值

state_key = board.current_hash
    if state_key in transposition_table:
        cached_depth, cached_score = transposition_table[state_key]
        if cached_depth >= depth:
            return cached_score

并在剪枝函数的末尾，我执行了

transposition_table[state_key] = (depth, value)

我不太确定自己哪里做错了，请你如果发现，请指出来。

解决方案

首先，错误在这里：

def get_initial_hash(grid):
    h = 0
    for r in range(BOARD_SIZE):
        for c in range(BOARD_SIZE):
            piece = grid[r][c]
            if piece != ' ':
                update_hash(piece, r, c)
    return h

你从不保存返回的哈希值，因此这个函数总是返回 0。

应该是：

def get_initial_hash(grid):
    h = 0
    for r in range(BOARD_SIZE):
        for c in range(BOARD_SIZE):
            piece = grid[r][c]
            if piece != ' ':
                h = update_hash(piece, r, c, h)
    return h

其次，你的置换表对于 α-β 剪枝来说过于简单。
在有剪枝的情况下，缓存的分数并不总是一个精确值。有时它只是一个下界或上界。因此仅存储：

(depth, score)

可能会得到较弱的结果。通常你还会存一个标志，类似于exact / lower / upper。

此外，在五子棋中，1% 到4% 的命中率并不一定就是糟糕的。如果着法排序较弱且分支较大，置换表的命中就可能非常罕见。