六边形棋盘的坐标、邻居与合法着法
项目代码: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 个合法着法。
这些数字比“跑起来没报错”更能说明规则实现是对的。
相关技能
- C++
- Git