Soma Zero Tutorials
🔍 搜索功能尚未开启，敬请期待。

2.6 Zobrist 哈希与置换表

这一节给引擎装一个“记忆”。搜索里有大量重复劳动——同一个局面被反复算很多遍。我们用 Zobrist 哈希给每个局面发一个指纹，再用置换表把算过的结果缓存下来，让搜索再快一截。这是经典引擎提速的标配，也是本章经典路线的收尾——之后我们就要请出神经网络了。

一、动机：同一个局面，被翻来覆去算了多少遍

有个现象叫换位（transposition）：不同的落子顺序，可能走到完全相同的棋盘。比如我先下 A 再下 B，和先下 B 再下 A，结果是同一个局面。搜索时这两条路会各自把这个局面从头再算一遍，乃至它底下整棵子树都重算——浪费惊人。

道理和第一章 MCTS 一样朴素：算过的东西，记下来，别再算第二遍。但要“记”，先得能快速回答一个问题：“这个局面我之前见过吗？”逐格比对整个棋盘太慢，我们需要给每个局面一个能瞬间比对的指纹。

二、Zobrist 哈希：给局面一个可增量更新的指纹

Zobrist 哈希的构造很巧妙：开局时，给“每个交叉点 × 每种颜色”都随机生成一个 64 位大整数；一个局面的哈希，就是把盘上所有棋子对应的随机数全部异或（XOR）起来。

import random
random.seed(42)
# 给 (每个点, 每种颜色) 配一个随机 64 位数：[点编号][0=黑, 1=白]
ZOBRIST = [[random.getrandbits(64) for _ in range(2)] for _ in range(N * N)]

它的妙处在于增量更新。XOR 有个性质：同一个数异或两次就抵消还原。所以落子时，只要把这个子的随机数异或进当前哈希；悔子时，再异或一次就还原了——每次落子/悔子都是 O(1) 的一次异或，不必重算整盘：

def toggle(h, pos, color_idx):
    """落子或悔子时更新哈希：异或进去；再调用一次就还原（XOR 自反）。"""
    return h ^ ZOBRIST[pos][color_idx]

于是搜索一路深入、回溯时，哈希值几乎零成本地跟着维护好了。这正配合上一节 VCF 里那种“play 一步、递归、再 undo”的节奏。

三、置换表：把算过的局面缓存起来

有了指纹，置换表（Transposition Table, TT）就是一个以哈希为键的字典，存下每个算过的局面的结果：搜了多深、得分多少、最佳着法是什么。搜索每个节点前先查表，命中且之前算得比现在还深（结果更可信）就直接复用，省掉整棵子树：

TT = {}   # 局面哈希 -> (depth, value, best_move)

def alphabeta(engine, depth, alpha, beta):
    h = engine.hash
    entry = TT.get(h)
    if entry is not None and entry["depth"] >= depth:
        return entry["value"]            # 命中：之前算得更深，直接复用

    # …… 正常的 α-β 搜索，得到 value 和 best_move ……

    TT[h] = {"depth": depth, "value": value, "best_move": best_move}  # 存回去
    return value

这里还有个和迭代加深（2.2）的绝佳配合：置换表里存的 best_move，正好可以喂给下一轮更深搜索做走子排序的首选——查表既省了重复计算，又顺手提供了“上次觉得最好的一手”。算过的不重算、且记住的好棋优先试，两个好处一举两得。（实战的 TT 还会区分“精确值/上界/下界”三种情形，并在内存满时淘汰旧条目，这些细节你跑通后再补即可。）

四、反思：经典引擎到顶了，但它的“棋感”是人给的

到这里，我们的经典五子棋引擎已经相当完整：会评估（2.3）、剪枝凶（2.4）、能算杀（2.5）、有记忆（2.6）。在自由规则下，它足以痛击绝大多数人类。这是一座扎实的高峰。

但请注意它棋力的来源：那套棋型权重、那些评估规则，全是我们人类手把手喂给它的。这意味着——它的上限，被我们对五子棋的理解死死卡住了。我们没想到的棋理，它也学不会；我们权重调偏了，它就跟着偏。一个自然的问题浮出水面：能不能不靠人写规则，让程序自己从对弈中把“什么局面好”学出来？

这个问题，第一章的迷你 AlphaZero 已经给过答案。下一节，我们就把那套“自我进化的飞轮”从井字棋放大到真正的 15×15，让你的 5070 Ti 火力全开。

五、小结与下一节

  • 换位：不同落子顺序到达同一局面，重复搜索浪费巨大。
  • Zobrist 哈希：点×色各配随机数，局面哈希 = 所有棋子随机数的 XOR；靠 XOR 自反性 O(1) 增量更新。
  • 置换表：以哈希为键缓存 (深度, 值, 最佳着法)；命中且更深则复用，还为迭代加深提供首选走法。
  • 经典路线封顶：评估/剪枝/算杀/缓存齐全，已能痛击人类——但棋感全靠人写，上限受限。

经典路线到此圆满。下一节 2.7 AlphaZero 自对弈强化学习，是本章的主力训练章：我们把第一章的迷你 AlphaZero 扩展到 15×15，在 5070 Ti 上真刀真枪训练数天，让引擎自己学出连我们都没教过的棋感。