★ FEATURED ARTICLE 简介棋类博弈是人工智能中经典且易于上手的研究场景。从国际象棋到各类棋类变体博弈树搜索与剪枝算法构成了许多AI程序的核心。爱因斯坦棋是一种5×5小棋盘上的棋类变体规则简洁但战术丰富非常适合作为棋类AI的入门实验场。围绕这一棋盘可以用Python搭建一套完整可对弈的棋类引擎涵盖走法生成、将军判定、minimax搜索、alpha-beta剪枝、评估函数与迭代加深等关键技术。通过参数调优与批量自我对弈验证开发者能够快速掌握搜索算法在具体博弈项目中的工程落地方法并规避规则版本差异、棋子阻挡判断、GUI线程卡死等常见陷阱。从简单棋类入手理解AI决策原理是通往更复杂棋类与强化学习路径的务实起点。1. 爱因斯坦棋一个比国际象棋更容易上手的AI实验场如果你手上有一块5x5的棋盘和双方各5枚棋子别急着摆国际象棋——试试爱因斯坦棋。这个常被称为“小国际象棋”的变体规则是每方拥有王、后、车、象、马各一枚没有兵也没有升变30秒就能讲完规则但搜索空间和战术组合又足以让AI程序忙一阵子。我最早接触它是在给一个教学项目找棋类引擎时标准国际象棋的走法生成和评估太成熟拿来练手没有挑战而爱因斯坦棋足够新没有现成满大街的开局库反而适合把决策树、剪枝、评估函数这些概念从头跑一遍。这篇笔记会从规则说清楚给出一套Python实现再把AI搜索的调参经验和你容易踩的坑一次性摊开。2. 爱因斯坦棋规则拆解为什么5x5棋盘是天然的AI测试床网上的爱因斯坦棋规则有不少版本有的用6x6棋盘有的加了兵和升变甚至还有人把它和“爱因斯坦谜题”混在一起。为了避免代码对着一个永远跑不起来的黑匣子发呆我先把这套实现所采用的规则固定下来棋盘为5行5列双方各持5枚棋子目标是将死对方王。你可以在这个基础上小幅调整后面我会明确指出哪个地方最容易受版本差异影响。2.1 棋盘、棋子与初始布局把物理规则变成数据字典棋盘坐标用(row, col)表示白方初始在第0行黑方初始在第4行中间三行空置。双方棋子从左到右分别是车、马、象、后、王黑方从自己的视角看也是车、马、象、后、王所以从镜像角度看黑方的排列是王、后、象、马、车。我把棋子的移动能力先汇总成一张表方便后面写方向向量时对照棋子数量走法距离越子王1横竖斜八个方向1格否后1横竖斜八个方向任意格否车1横竖四个方向任意格否象1斜向四个方向任意格否马1L形横走2竖走1或相反1步是为什么把王和后都放在5格的行里因为5列刚好放满5枚棋子没有兵的位置也就没有过路兵、升变、王车易位这些“边角规则”。对于AI程序来说状态空间比标准国际象棋小几个数量级但棋子走法仍然有“阻挡”“仅马可越子”的判定足够练习走法生成器的健壮性。在代码里我习惯用枚举表示棋子类型而不是字符串因为枚举在debug时更直观还能避免手写字符大小写带来的混乱。下面这段是初始布局的最小表示# constants.py import enum WHITE, BLACK 0, 1 class Kind(enum.Enum): KING K QUEEN Q ROOK R BISHOP B KNIGHT N def empty_board(): return [[None for _ in range(5)] for _ in range(5)] def initial_board(): board empty_board() # 白方 row 0黑方 row 4 top [Kind.ROOK, Kind.KNIGHT, Kind.BISHOP, Kind.QUEEN, Kind.KING] bottom [Kind.KING, Kind.QUEEN, Kind.BISHOP, Kind.KNIGHT, Kind.ROOK] for c, kind in enumerate(top): board[0][c] kind for c, kind in enumerate(bottom): board[4][c] kind return board这里把board直接存Kind枚举空位存None。这个版本的代码只记录棋子种类还没记录颜色真实引擎里必须额外用一个数组或把颜色编进棋子类。我特意先展示这种“半成品”是想说明一个取舍棋盘只有25格用二维列表足够快没必要在入门阶段上位棋盘bitboard。位棋盘在8x8棋盘上能大幅加速并行位运算但在这里反而会增加调试成本尤其对于刚接触棋类编程的人你会发现自己一整天都在算位掩码。2.2 走法与胜负将军、将死、还有“送将”违例大多数棋类走法生成都要分两步走先生成“伪合法走法”再过滤掉会让己方王被吃的走法。许多人一上来就写递归生成器却忘了送将检查最后AI会走出把自己的王送到对方嘴里的棋那感觉就像看了半天棋谱发现第一步就是错的。伪合法走法指的是“按照棋子移动规则走完不越界且不落到己方棋子上的走法”。它不管走完之后自己王是否处于被攻击状态。比如王从角落走到中心如果对方车正好控制这一行这个走法在伪合法阶段会被放进列表但在第二阶段的合法性过滤时必须删掉。过滤逻辑很简单模拟每一步然后调用将军判定函数如果己方王在对手攻击范围内该走法不合法。这一步会反复执行所以将军判定一定要写得高效。判断一个格子是否被某颜色棋子攻击通常用反向扫描站在目标格子上逆推是否有棋子能按自己的走法到达这里。棋盘小直接枚举对手所有棋子的攻击目标也行。下面是一个更贴近代码的思路def is_square_attacked(board, r, c, by_color): # 枚举 by_color 的所有棋子检查它们能否一步到达 (r,c) # 注意马不需要检查中间阻挡车、象、后必须检查路径是否被堵 for each piece owned by by_color: if piece_can_reach(board, piece, r, c): return True return False将军与将死的判定不能只用“能吃到王”来推。正确顺序是先获取当前玩家的全部合法走法列表如果列表为空再检查己方王是否正被攻击——被攻击就是将死否则就是无棋可动。在国际象棋标准规则里无棋可动判和棋但在爱因斯坦棋的某些流传版本里无棋可动直接判负。我建议在代码里做成配置项因为我见过同一个项目里两种写法都有人用最后在判负判和上吵了三天。3. 用 Python 写出可对弈的爱因斯坦棋走法生成与状态管理现在进入能跑的代码。我采用一个自定义Piecedataclass来同时记录种类和颜色比单纯存枚举更完整。棋盘状态就用二维列表每格元素是Piece或None。这一章给出的代码可以直接复用也可以作为你写其他小型棋类引擎的骨架。3.1 棋盘类设计从格子坐标到合法走法列表先定义基础类和棋盘初始化from dataclasses import dataclass from enum import Enum class Kind(Enum): KING K QUEEN Q ROOK R BISHOP B KNIGHT N WHITE, BLACK 0, 1 dataclass(frozenTrue) class Piece: kind: Kind color: int def __str__(self): return self.kind.value if self.color WHITE else self.kind.value.lower() class EinsteinBoard: def __init__(self): self.board self._initial_board() self.turn WHITE self.state_stack [] # 悔棋/搜索用 def _initial_board(self): board [[None for _ in range(5)] for _ in range(5)] top [Kind.ROOK, Kind.KNIGHT, Kind.BISHOP, Kind.QUEEN, Kind.KING] bottom [Kind.KING, Kind.QUEEN, Kind.BISHOP, Kind.KNIGHT, Kind.ROOK] for c, kind in enumerate(top): board[0][c] Piece(kind, WHITE) for c, kind in enumerate(bottom): board[4][c] Piece(kind, BLACK) return boardPiece是frozen dataclass保证哈希和比较都可靠后面在走法集合里做去重很方便。state_stack用来配合悔棋和AI搜索时的状态回退这个设计在3.2里会展开。核心的走法生成器按“方向向量最大步数”来组织。车、象、后能走任意格但中途遇到棋子就必须停马直接跳到目标格不受阻挡。我写了一个_attacks_from函数它会返回一个棋子能到达的所有格子def _attacks_from(self, r, c): piece self.board[r][c] if piece is None: return [] vectors { Kind.KING: [(1,0,1),(-1,0,1),(0,1,1),(0,-1,1), (1,1,1),(1,-1,1),(-1,1,1),(-1,-1,1)], Kind.QUEEN: [(1,0,5),(-1,0,5),(0,1,5),(0,-1,5), (1,1,5),(1,-1,5),(-1,1,5),(-1,-1,5)], Kind.ROOK: [(1,0,5),(-1,0,5),(0,1,5),(0,-1,5)], Kind.BISHOP: [(1,1,5),(1,-1,5),(-1,1,5),(-1,-1,5)], Kind.KNIGHT: [(2,1,1),(2,-1,1),(-2,1,1),(-2,-1,1), (1,2,1),(1,-2,1),(-1,2,1),(-1,-2,1)], } result [] for dr, dc, max_step in vectors[piece.kind]: for step in range(1, max_step 1): nr, nc r dr * step, c dc * step if not (0 nr 5 and 0 nc 5): break target self.board[nr][nc] if target is None: result.append((nr, nc)) elif target.color ! piece.color: result.append((nr, nc)) break else: break return result这里有个细节马的方向向量步长为1但用了(2,1)这种二元组和max_step1的组合所以马不会进入“连续走多步”的路径检查。其他棋子的max_step设为5但棋盘只有5行所以range(1, 6)也会自然越界退出。这个实现简单缺点是每次都要重新构造vectors字典如果你追求性能可以把这个字典提到类属性或模块常量里避免高频搜索时反复分配。有了单子走法再汇总整个棋盘所有己方棋子的伪合法走法然后逐条模拟并过滤送将def get_legal_moves(self, color): pseudo [] for r in range(5): for c in range(5): piece self.board[r][c] if piece is None or piece.color ! color: continue for tr, tc in self._attacks_from(r, c): pseudo.append((r, c, tr, tc)) legal [] for move in pseudo: state self._snapshot() self._apply_move(*move) if not self.is_in_check(color): legal.append(move) self._restore(state) return legal_snapshot和_restore这对方法在3.2里实现作用是对整盘状态做深拷贝。为什么要深拷贝因为棋盘只有25格拷贝一次开销极小而且能避免增量回退时的边界错误——比如你吃掉对方马之后悔棋要恢复如果你不拷贝就得额外保存“吃掉的棋子是什么”逻辑容易漏。3.2 落子、吃子与悔棋状态栈和“悔棋”按钮的实现def _snapshot(self): import copy return (copy.deepcopy(self.board), self.turn) def _restore(self, state): self.board, self.turn state def _apply_move(self, r, c, tr, tc): self.board[tr][tc] self.board[r][c] self.board[r][c] None self.turn BLACK if self.turn WHITE else WHITE def push_move(self, move): self.state_stack.append(self._snapshot()) self._apply_move(*move) def undo(self): 悔棋回退到上一个状态并取出栈顶状态。 if self.state_stack: self.board, self.turn self.state_stack.pop() return True return Falsepush_move在落子前快照再落子。undo用于GUI里的“悔棋”按钮也用于AI搜索时的回退。你可能会担心深拷贝会让搜索变慢但实测在5x5棋盘上一次deepcopy大约几微秒一次alpha_beta搜索几千个节点总耗时不过几十毫秒完全可以接受。如果你以后要移植到C或要做更深的搜索再改成“保存被吃棋子起点”的增量回退不迟。有一点要提醒如果你在搜索循环里用push_move和undo每次进入子节点都要_snapshot那栈会越积越大。正确做法是直接用_apply_move_restore不要经过state_stack。所以我在3.1的走法过滤里用的是_snapshot和_restore而不是push_move。搜索时的回退应该手动保存旧状态而不是依赖undo因为undo面向的是人机对弈的“悔棋栈”两套栈不能混用。3.3 命令行对弈最小可玩版本跑起来既然有了棋盘和走法先用命令行跑一个能双人对战的版本。输入格式是r c tr tc从起点到终点q退出def print_board(board): for r in range(5): row [] for c in range(5): p board.board[r][c] row.append(str(p) if p else .) print( .join(row)) def main(): b EinsteinBoard() while True: print_board(b) print(Turn:, White if b.turn WHITE else Black) moves b.get_legal_moves(b.turn) if not moves: print(No legal moves. Game over.) break cmd input(enter move: r c tr tc (q to quit): ) if cmd.strip().lower() q: break try: r, c, tr, tc map(int, cmd.split()) except ValueError: print(bad input) continue move (r, c, tr, tc) if move not in moves: print(illegal move) continue b.push_move(move) opponent BLACK if b.turn WHITE else WHITE if b.is_in_check(opponent): print(Check!)这个主循环没有任何AI但它能帮你验证规则自己跟自己下几盘检查有没有走法漏生成有没有把无棋可动判成将死。命令行版本是后面加AI的基础不要跳过。4. 给爱因斯坦棋装上大脑minimax 搜索与 alpha-beta 剪枝的参数调优黑白棋、五子棋、国际象棋的AI思路在爱因斯坦棋上完全通用核心就是带剪枝的深度优先搜索。不要一上来就上强化学习因为爱因斯坦棋是完美信息确定状态搜索树小到能用经典方法解没必要让一局棋的训练时间长得像练一个深度网络。4.1 先算复杂度为什么要剪枝而不是直接上强化学习我粗略统计过空棋盘中间位置的车大约能走8格象能走4格左右后能走8到10格马最多8格王3格。平均每个棋子大约能走6到8步每方5个棋子分支因子B大约在10到15之间。这是可观的。如果做4层深度搜索B15时未剪枝的叶子节点是15^450625非常轻松6层深度是15^6≈1130万单层遍历勉强能算但已经不够优雅。alpha-beta剪枝在理想情况下能把复杂度从O(B^d)降到O(B^(d/2))也就是搜索同样深度只需要大约sqrt(1130万)≈3400个节点完全可以在毫秒级完成。因此先写minimax和alpha-beta是你投入产出比最高的方案。那么强化学习呢它的价值在于棋类状态特征复杂、评估函数难以手工设计或者你需要一个能从自我对弈中自动学习评估的网络。但爱因斯坦棋棋盘小、棋子少一个几十行的评估函数已经够用强化学习要处理奖励稀疏、回合长、对局数量大这些工程问题不适合作为入门首选。4.2 最小可用的评估函数子力位置机动性评估函数是AI风格的“黑匣子”但我们可以先手工打开它。最简单的评估用子力价值后9分、车5分、象3分、马3分、王10000分因为王被吃了游戏结束。在此基础上给靠近中心的棋子加一点点位置分因为中心控制力更强。代码长这样PIECE_VALUES { Kind.KING: 10000, Kind.QUEEN: 9, Kind.ROOK: 5, Kind.BISHOP: 3, Kind.KNIGHT: 3, } POSITION_BONUS [ [0, 1, 2, 1, 0], [1, 2, 3, 2, 1], [2, 3, 4, 3, 2], [1, 2, 3, 2, 1], [0, 1, 2, 1, 0], ] def evaluate(board): score 0 for r in range(5): for c in range(5): p board.board[r][c] if p is None: continue bonus POSITION_BONUS[r][c] if p.color WHITE else POSITION_BONUS[4 - r][4 - c] value PIECE_VALUES[p.kind] bonus * 0.1 score value if p.color WHITE else -value return score if board.turn WHITE else -scorebonus * 0.1是为了让位置分远小于一个兵的价值不至于出现“为了抢中心而白送一个马”的蠢事。实际上这个0.1本身就是可以调的参数我建议在0.05到0.3之间实验。更大的系数会让AI更激进地抢占中心但容易忽视子力安全。机动性评估没有写进代码因为计算合法走法数量在搜索中已经天然存在不需要额外统计。如果你发现AI总是走成僵局再考虑加上“己方合法走法数减去对方合法走法数”这一项。但记住评估函数不是越复杂越好加项越多越难调你先跑通0.1版再说。4.3 迭代加深与超时控制三个必调参数正式对弈时你不能只固定搜索深度因为不同局面复杂度不一样。常见做法是迭代加深从深度1开始逐步加深直到时间预算用完采用最近一次完整搜索的最佳走法。这样你能精确控制在3秒内返回一步棋而不是在最差局面里卡死。import time def alpha_beta(board, depth, alpha, beta, maximizing): moves board.get_legal_moves(board.turn) if depth 0 or not moves: return evaluate(board) if maximizing: value -float(inf) for move in moves: board._apply_move(*move) value max(value, alpha_beta(board, depth - 1, alpha, beta, False)) board._restore((board_copy_state, board.turn)) # 需要保存状态 alpha max(alpha, value) if alpha beta: break return value else: value float(inf) for move in moves: board._apply_move(*move) value min(value, alpha_beta(board, depth - 1, alpha, beta, True)) board._restore((board_copy_state, board.turn)) beta min(beta, value) if alpha beta: break return value上面这段代码省略了_apply_move前后的状态保存实际使用时你需要在每次进入子节点前把board.board和board.turn存到临时变量里。我在这里不展开完整搜索类因为它和标准国际象棋AI完全一致。关键是下面的迭代加深循环def iterative_deepening(board, time_budget2.0, max_depth6): deadline time.time() time_budget best_move None depth 1 while depth max_depth and time.time() deadline: # 每层先保存一个候选最佳走法层结束才更新 current_best None best_value -float(inf) for move in board.get_legal_moves(board.turn): board.push_move(move) value alpha_beta(board, depth - 1, -float(inf), float(inf), False) board.undo() if value best_value: best_value value current_best move if current_best is not None: best_move current_best depth 1 return best_move这里三个必调参数是参数推荐起点作用调整方向max_depth6硬性最大深度上限防止时间预算失效时无限加深想棋力更强就加到8但要配合更快的走法生成time_budget2.0秒每次落子的时间预算实时对战设1秒分析模式可设5秒evaluation_coeff0.1位置分系数影响评估函数的激进度0.05保稳0.3冒险吃中心迭代加深还有一个隐藏好处如果你实现了“上一步搜索的最佳走法在开局库附近”它可以用在启发排序里让alpha-beta剪枝更容易触发。不过在爱因斯坦棋上你先把这三个参数调好已经能打败绝大多数随便下棋的人类玩家。5. 避坑指南爱因斯坦棋实现中的 5 个常见翻车现场这一章是血泪经验。我确实在这些地方翻过车每次都要花至少一个晚上排查。按现象→原因→解决的方式写希望你不用走回头路。5.1 规则版本不同兵/升变引发的连锁反应现象从网上下载的“爱因斯坦棋”代码开局第一排除了重子以外还有一排兵走几步就报索引越界。原因爱因斯坦棋本身有多个变体有的版本是6x6棋盘加兵有的版本甚至允许兵升变。解决入手前先确认规则版本。如果你手中的项目确实带兵就在Kind里加PAWN并在_attacks_from里实现兵的单步前进和斜吃同时处理升变。如果按我这套无兵规则遇到“对方底线出现第6个子”要直接报错防止静默bug。5.2 重复局面与“无棋可动”把和棋判成输棋怎么办现象AI走到只剩两个王时程序提示“Game over”但明明合法走法没了王也没被将军应该是和棋。原因我在刚开始写胜负判定时只检查了legal_moves为空就判定对方赢了没进一步查王的攻击状态。解决把将死和无棋可动分开。先判断len(legal_moves)0再用is_in_check检查当前玩家王是否被攻击。无棋可动默认判和但保留一个STALEMATE_IS_LOSS开关应对那些把“无棋可动”当输棋的规则版本。5.3 马能跳其他棋子不能穿人实现阻挡时的边界错误现象AI在残局里经常用车穿过自己的兵走到后方评估分看起来很高但按规则就是非法走法。原因_attacks_from里车、象、后沿方向逐格走但我的第一版没有在碰到第一个棋子后break导致继续扫描后方格子。马则不需要检查路径所以马的逻辑是独立的。解决在伪合法走法生成时遇到第一个非空格就分支若是我方棋子停止若是对方棋子记录格子并停止。马的马步直接跳过该检查。一个快速自测是在5x5棋盘上把车围在中心一圈棋子车应该一个格都走不出去。5.4 GUI线程卡死递归搜索别放在渲染线程现象在Qt里点“AI下棋”按钮后整个窗口变成“未响应”点哪都没反应要等好几秒才恢复。原因AI搜索的alpha_beta是同步递归主线程被占满事件循环无法刷新。解决把搜索放到子线程用queue或者信号把结果传回UI。更简单的做法是先用命令行版本验证AI再接GUI。我自己的习惯是让AI计算线程每次只搜一个深度等迭代加深结束后回到主线程更新棋盘。如果不想引入多线程至少要在搜索循环中插入time.sleep(0)或QCoreApplication.processEvents()但这不是根治只是喘口气。5.5 评估函数像玄学用自我对弈代替肉眼调参现象我把位置分系数从0.1改成0.3肉眼看了几局觉得AI更凶了但和人下反倒输多赢少。原因肉眼评估有巨大偏差位置分过高让AI为了占中心狂送棋子。解决把两个不同参数的AI放在一起自我对弈200局统计胜负和平局。胜率差异不到5%时基本可以认为是噪声跑满200局再看通常能找到趋势。不要只调一个参数就下结论至少要用固定对手和固定随机种子跑批量对局。这也是我后来养成的习惯任何评估函数的改动都要用--games参数跑批量测试不凭“感觉还不错”上线。6. 进阶玩法从“会下”到“下得好”的验证闭环现在你已经有一个能下棋、能搜索、能悔棋的程序。想让它更强不用急着换强化学习框架先把这三个进阶动作做扎实。6.1 用自我对弈生成离线数据反哺评估函数把两个不同评估参数的AI写进同一个脚本里让它们自动对弈200局记录每局的走法序列、棋子被吃情况和最终结果。你不需要人工标注因为胜负天然就是标签。用这些对局可以回归出“哪种子力比值更优”的经验值甚至可以训练一个简单的线性评估模型替代原来拍脑袋的PIECE_VALUES。6.2 做个开局库前5步不再“天马行空”棋盘这么小AI搜到第4层时已经能稳定判断前几步。但为了节省时间预算你可以用高深度AI离线生成前5步的最优走法存成一个字典键是“棋盘状态”值是好走法。对局时前5步直接查表把时间预算留给中残局。我自己试过用8层搜索跑一晚上能覆盖绝大多数前期变体线上AI前5步的思考时间直接降到0。6.3 验证方法让两个AI打一场用胜率和平均回合数说话不要再用“哪一步让我感觉厉害”来验证。正确做法是用同一套引擎、不同参数跑200局记录胜率、平均回合数、每步平均耗时。表格比感觉可靠得多版本胜率平均回合平均耗时v0.1 位置系数0.158%42.31.8sv0.2 位置系数0.342%38.71.9s这组数据一眼就能看出位置系数0.1更稳。那怎么选我会把胜率作为第一指标平均回合数作为调优参考因为快速赢棋不一定意味着棋力强。慢慢养成这个习惯后你会发现所谓“棋感”变成了可重复的实验而不是玄学。希望这套从规则到验证的流程能让你在下一个棋类项目里少花几个通宵。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
