项目代码:https://github.com/yicongl1/Gopher-and-Dodo

Gopher 和 Dodo 都是六边形棋盘上的双人棋。写这类游戏,第一件事不是搜索,而是把“格子、邻居、合法着法”这三件事定义清楚——定义错了,后面的 Minimax 再漂亮也没用。

这篇讲 IA02 项目里的棋盘建模,以及两款游戏各自的合法着法。

用两个坐标表示六边形

六边形网格有很多种坐标系统。项目用的是轴向坐标(axial coordinates):每个格子是 (x, y),第三个轴隐含为 z = -x - y,三者满足 x + y + z = 0。

这样做的直接好处是:六个邻居只需要六个固定偏移:

directions = [(1, 0), (1, 1), (0, 1), (-1, 0), (-1, -1), (0, -1)]

不需要三角函数,也不需要为“平顶”和“尖顶”写两套逻辑。

棋盘边界也不是简单的矩形,而是三条轴上的范围:

def is_within_bounds(cell, hex_size):
    x, y = cell
    return (-hex_size < x < hex_size
            and -hex_size < y < hex_size
            and -hex_size < -x + y < hex_size)

-x + y 就是第三个轴的约束。尺寸为 n 的棋盘共有:

3n(n-1) + 1

个格子:n=4 是 37 格,n=6 是 91 格。

Gopher:一条规则,两个条件

Gopher 的规则很短:

  • 红方第一手可以下在任意空格;
  • 之后每步必须与恰好一枚敌子相邻,且与零枚己子相邻;
  • 不能跳过;
  • 最后成功落子的一方获胜。

翻译成代码,就是遍历所有敌子的邻格,保留同时满足两个条件的空格:

if (is_within_bounds(new_cell, hex_size)
        and (new_cell, EMPTY) in state
        and not count_neighbors(state, new_cell, player)
        and count_neighbors(state, new_cell, cell_player) == 1):
    legals.append(new_cell)

count_neighbors(state, cell, player) 会数出 cell 周围属于 player 的棋子数量。于是:

  • not count_neighbors(..., player) → 零个己方邻居;
  • count_neighbors(..., enemy) == 1 → 恰好一个敌方邻居。

规则和代码几乎一一对应,这是这个项目里我觉得最舒服的一段。

Dodo:方向随颜色变,目标格必须为空

Dodo 的棋子只能向前走,红蓝两方的前进方向相反:

red_directions  = [(1, 0), (1, 1), (0, 1)]
blue_directions = [(-1, 0), (-1, -1), (0, -1)]

对每个己方棋子,检查三个方向上的目标格是否在界内且为空:

if is_within_bounds(new_cell, hex_size) and (new_cell, EMPTY) in state:
    legals.append((cell, new_cell))

注意 Dodo 的着法是 (起点, 终点),而 Gopher 的着法只是一个格子。状态转移也要分别处理:

if game == DODO_STR:
    start, end = action
    new_state[new_state.index((start, player))] = (start, EMPTY)
    new_state[new_state.index((end, EMPTY))] = (end, player)
else:
    new_state[new_state.index((action, EMPTY))] = (action, player)

还有一个反直觉的规则:轮到你却没有合法着法时,你获胜。所以“合法着法为空”在 Dodo 里是胜利条件,在 Gopher 里却是失败条件。这个差异会影响评估函数,后面会单独讲。

用列表存状态,代价是什么

状态是一个 list[(cell, player)]:

State = list[tuple[Cell, Player]]

读写都要 (cell, player) in state 或 state.index(...),这两步都是线性扫描。legals 对每个棋子、每个方向都要查一次,实际复杂度接近 O(n⁴)。

如果重做,我会改成:

board = {(x, y): player}   # O(1) 查格子

再加一个 pieces[player] 的集合,遍历己方棋子时就不用扫全盘。这样 legals 能降到接近 O(n²),搜索深度也能再往上推一层。

一点验证

写完之后我做了几组最小的自检:

  • n=4 生成 37 格,n=6 生成 91 格;
  • Dodo n=4 双方各 13 子,n=6 各 26 子;
  • Dodo n=4 初始局面红蓝各有 13 个合法着法,n=6 各 21 个;
  • Gopher 空棋盘红方没有“规则意义”的合法着法,代码兜底下 (0,0);之后蓝方有 6 个合法着法。

这些数字比“跑起来没报错”更能说明规则实现是对的。

仓库:https://github.com/yicongl1/Gopher-and-Dodo