2026/9/10 12:22:41
FEATURED · 精选文章 
简介基于蒙特卡洛树搜索的AI五子棋算法实现代码面向学习人工智能与博弈算法的学生或开发者以UCT算法为核心完整覆盖选择、扩展、模拟、回传四个标准步骤。资源包共31个文件包含9个Java源文件与对应class文件、项目配置文件及png/jpg/svg图示说明压缩包仅195KB结构紧凑附有文档说明适合作为算法课程大作业或入门MCTS的参考实现。已有221人学习。文档中总结了实战调参经验默认5秒模拟可战胜一般水平玩家30秒模拟能与在线高手模式周旋同时引入形势判断对三连子、四连子等局面打分显著提升胜率并在关键时直接堵子以节省搜索时间。这些改进思路从随机模拟到启发式评估展示了如何将基础MCTS落地为可用棋力对理解算法变体与工程优化很有帮助。1. 蒙特卡洛树搜索让五子棋AI不再是暴力穷举的玩具在五子棋这类零和博弈里很多人第一反应是搜出所有落子分支——但15×15棋盘的状态空间远超任何现代机器的枚举能力。蒙特卡洛树搜索Monte Carlo Tree Search简称MCTS给出了一条反直觉的路径不追求遍历全部局面而是用随机模拟的胜负统计来引导搜索方向配合置信区间上界UCB公式在「探索新分支」和「利用已知优势」之间做权衡。这套思路的工程价值在于它不依赖手工编写的评估函数也不要求你提前整理棋谱特征而是把「哪步棋更好」这个问题转化成了「哪步棋在多轮随机对局里赢面更大」。本文面向想从零实现一个可运行五子棋AI的算法工程师和学生会从MCTS的数学骨架讲起给出可直接复制运行的Python代码、关键参数调优表以及让AI从「会下棋」到「棋风稳健」的坑位排查方案。2. 从博弈树到MCTS先算清置信区间再决定往哪搜2.1 为什么五子棋的博弈树不能硬搜传统α-β剪枝在五子棋上的困境可以从数量级看15×15棋盘第一步有225个合法落点即便每层砍掉一半分支深度6层的搜索量仍在数十亿量级。更麻烦的是五子棋缺乏像国际象棋那样的强启发式走法排序剪枝效率极不稳定。蒙特卡洛树搜索的突破口是「不展开全部子节点」每次只沿着一条路径深入用随机对弈走到底再回传胜负结果搜索树只在被访问过的节点上生长。对于IT从业者来说这个概念可以类比为A/B测试的实时版本——每个候选着法是一个实验组随机推演是流量分配胜率就是转化率而UCB公式则是一个自适应的流量调度器。2.2 UCB1公式的拆解与直觉MCTS的每个节点需要记录两个数字被访问次数n和累计胜利次数w。选择子节点时优化目标不是纯胜率w/n而是UCB1值:UCB1 w/n C * sqrt(ln(N_parent) / n)第一项是「利用」胜率高的节点优先第二项是「探索」被访问次数n越少分母越小这个值越大于是冷门分支也有机会被尝试。参数C控制两者的权重通常取sqrt(2)。在五子棋场景里如果C设得太小AI会死磕一个早期出现好结果的分支变成「井底之蛙」如果C太大AI几乎在随机瞎下。「平衡点」这个问题我会在后面实战部分的调参表里给出一组实测区间。2.3 四阶段循环选择、扩展、模拟、回传MCTS的一次迭代在代码上对应四个步骤下面先把伪代码逻辑写出来再给可运行版本。def mcts_iteration(root): # 第一阶段选择 node root state root.state.copy() while node.is_fully_expanded() and not state.is_terminal(): node best_child(node) # 按UCB1选子 state.apply_move(node.move) # 第二阶段扩展 if not state.is_terminal(): move select_unvisited_move(node, state) state.apply_move(move) node node.add_child(move, state) # 第三阶段模拟 winner playout(state) # 随机下到终局 # 第四阶段回传 while node is not None: node.update(winner) # 胜利者视角更新 node node.parent每步的含义选择阶段只走「已经完全展开」的节点保证每次都走到树的最前沿扩展阶段只给当前节点加一个没试过的孩子保持树的稀疏性模拟阶段用纯随机策略下完整个棋盘这看似粗糙但大数定律保证统计上有意义回传阶段从叶子一路更新到根每个节点都用当前这局的结果修正自己的w和n。这四个阶段里最容易出错的是「更新视角」——你需要明确胜者是以哪个玩家视角统计的否则AI的策略会反向优化。3. 用Python实现可运行的MCTS五子棋AI3.1 棋盘状态的表示与落子合法性判断实现时我推荐用一维列表长度225表示棋盘索引row*15col对应坐标。这样做的优势是落子和判断都集中在整数运算上Python的性能瓶颈能被结构简化抵消一部分。棋盘类需要提供三个核心方法落子、判断胜负、获取空白格列表。胜负判断用滑动窗口检查连五比递归判连通快得多。class GomokuBoard: def __init__(self, size15): self.size size self.board [0] * (size * size) # 0空 1黑 2白 self.current_player 1 self.move_history [] def is_valid_move(self, move): return 0 move self.size * self.size and self.board[move] 0 def apply_move(self, move): if not self.is_valid_move(move): raise ValueError(fInvalid move: {move}) self.board[move] self.current_player self.move_history.append(move) self.current_player 3 - self.current_player # 1-2切换 def get_empty_cells(self): return [i for i, v in enumerate(self.board) if v 0] def check_win(self, move): if move is None: return 0 player self.board[move] if player 0: return 0 directions [(1, 0), (0, 1), (1, 1), (1, -1)] for dr, dc in directions: count 1 r, c divmod(move, self.size) for step in range(1, 5): nr, nc r dr * step, c dc * step if not (0 nr self.size and 0 nc self.size): break if self.board[nr * self.size nc] player: count 1 else: break for step in range(1, 5): nr, nc r - dr * step, c - dc * step if not (0 nr self.size and 0 nc self.size): break if self.board[nr * self.size nc] player: count 1 else: break if count 5: return player return 0 def is_terminal(self): if len(self.move_history) self.size * self.size: return True last_move self.move_history[-1] if self.move_history else None return self.check_win(last_move) ! 0胜负判断里采用的双向线性扫描每条方向只做两次遍历时间复杂度恒定在常数级别。注意current_player用3 - current_player互换比加一取模更快。move_history不仅用于判断终局之后实现「悔棋」和「复盘」也要靠它。3.2 MCTS节点类与选择策略的代码落地节点类不要存棋盘快照而是存父节点、落子位置和累计统计量。棋盘状态只在选择阶段通过回放move_history来恢复这样避免了深拷贝225个元素的列表内存占用会明显下降。这里需要定义一个best_child方法用UCB1公式计算每个子节点的评分。import math import random class MCTSNode: def __init__(self, parentNone, moveNone): self.parent parent self.move move # 从父节点走到当前节点的落子 self.children {} self.visits 0 self.wins 0 # 以当前节点视角的胜利次数 def is_fully_expanded(self, board): return len(self.children) len(board.get_empty_cells()) def best_child(self, c_param1.4): best_score -float(inf) best_node None for child in self.children.values(): if child.visits 0: ucb float(inf) else: exploitation child.wins / child.visits exploration c_param * math.sqrt(math.log(self.visits 1) / child.visits) ucb exploitation exploration if ucb best_score: best_score ucb best_node child return best_node def update(self, result): self.visits 1 self.wins resultUCB1公式里有几个容易踩的细节。log里的self.visits 1加一是为了防止根节点还没被访问时就触发除零错误。child.visits 0时直接给无穷大意思是「没试过的分支永远优先试一次」这保证了每个合法着法至少被探索一次也避免程序在早期死循环在某一个分支上。c_param在五子棋中不建议取理论值sqrt(2)后面调参会说明原因。3.3 一次MCTS迭代的完整实现class MCTS: def __init__(self, board, player, iterations2000, c_param1.4): self.board board self.player player self.iterations iterations self.c_param c_param self.root MCTSNode() def select(self, node, board): while not board.is_terminal(): empty_cells board.get_empty_cells() if node.is_fully_expanded(board): if not node.children: return node, board node node.best_child(self.c_param) board.apply_move(node.move) else: return node, board return node, board def expand(self, node, board): tried_moves set(node.children.keys()) for move in board.get_empty_cells(): if move not in tried_moves: board.apply_move(move) child MCTSNode(parentnode, movemove) node.children[move] child return child, board return node, board def simulate(self, board): while not board.is_terminal(): empty_cells board.get_empty_cells() move random.choice(empty_cells) board.apply_move(move) return board.check_win(board.move_history[-1]) def backpropagate(self, node, winner): while node is not None: node.visits 1 if winner self.player: node.wins 1 elif winner 3 - self.player: node.wins 0 else: node.wins 0.5 node node.parent def best_move(self): for _ in range(self.iterations): node, board self.select(self.root, self.board.duplicate()) if not board.is_terminal(): node, board self.expand(node, board) winner self.simulate(board) self.backpropagate(node, winner) best_node None best_visits -1 for child in self.root.children.values(): if child.visits best_visits: best_visits child.visits best_node child return best_node.moveduplicate()方法需要在棋盘类里实现返回一个深拷贝但只复制board列表不要复制move_history的每一个元素。从工程角度看每次迭代都完整复制一次棋盘开销不小一个优化是「反悔式搜索」选择阶段逐步落子回传阶段用undo_move恢复但代码可读性会下降。初学者先跑通复制版本再优化不迟。backpropagate里平局记0.5分这是让AI在劣势局面下不激进送死的关键——如果平局记0AI会宁可输也不愿求稳。4. 让AI能真正对弈命令行入口与GUI接入4.1 命令行对弈的最小闭环要让上面的MCTS跑起来需要补一个人类玩家输入落子和棋盘打印的函数以及一个控制游戏主循环的主程序。落子输入用「字母数字」的方式比如h8程序内部转换成索引。def parse_move(text, size15): text text.strip().lower() if len(text) 2: return None col_char text[0] row_str text[1:] if not (a col_char o): return None if not row_str.isdigit(): return None row int(row_str) - 1 col ord(col_char) - ord(a) if not (0 row size and 0 col size): return None return row * size col def print_board(board): size board.size header .join(chr(ord(a) i) for i in range(size)) print(header) for r in range(size): row_chars [] for c in range(size): move r * size c if board.board[move] 1: row_chars.append(X) elif board.board[move] 2: row_chars.append(O) else: row_chars.append(.) print(f{r1:2d} .join(row_chars))坐标解析的健壮性很重要用户可能会输H8、h8或者带空格的h 8strip().lower()统一转小写再去掉首尾空格。如果你想把输入容错做得更好可以额外处理中文全角字符或8h这类行列颠倒的输入但核心逻辑仍然是拆出列字母和行数字。打印棋盘时字母表头方便人类快速定位落点X和O分别映射黑棋白棋这样终端追踪对局过程也不会眼花。4.2 主循环整合MCTS与人类落子def main(): size 15 board GomokuBoard(size) human_player 1 # 人类执黑先行 ai_player 2 print(你执黑先行输入类似 h8 的坐标落子) while not board.is_terminal(): print_board(board) current board.current_player if current human_player: while True: try: text input(你的落子: ) move parse_move(text, size) if move is None or not board.is_valid_move(move): print(非法输入请重新输入) continue board.apply_move(move) break except (ValueError, IndexError): print(输入格式错误例如 h8) else: mcts MCTS(board, ai_player, iterations2000, c_param1.4) move mcts.best_move() print(fAI落子: {move // size 1}{chr(ord(a) move % size)}) board.apply_move(move) print_board(board) winner board.check_win(board.move_history[-1]) if winner human_player: print(你赢了) elif winner ai_player: print(AI赢了) else: print(平局)主循环的判断条件是board.is_terminal()这个函数在平局和有一方连五时都会返回True。需要注意board.check_win需要传入最后一步落子位置所以主循环里move_history不能为空否则取[-1]会越界。实际操作中可把这个场景兜住如果棋盘没有空且无胜者直接返回平局结果。4.3 GUI接入从命令行迁移到可视化界面的最小改动命令行版本虽然能跑但迭代2000次的搜索在15×15棋盘上通常需要1到3秒如果人类玩家想观察AI的逐步思考命令行已经够用。如果你想接入GUI最省力的方式是保留MCTS和GomokuBoard这两个类不动只替换「输入输出层」。常见做法是用tkinter或pygame画一个15×15的网格鼠标点击位置换算成行列索引。网格绘制时注意每个格子的像素间距大约size_px // 15点击事件的像素坐标除以间距即可得到行列再把行列换算成row*15col的棋盘索引。如果要做「人机对弈模式」核心就是把input()替换成挂起的鼠标事件回调——AI计算期间最好把交互锁住否则玩家会连续点击多次导致落子错乱。5. 优化模拟策略和使用pattern表让AI从「会下」到「稳健」5.1 随机模拟策略的两处关键改进纯随机对弈虽然能保证统计无偏但在五子棋中收敛极慢。一个明显的工程改进是「优先走靠近已有棋子的空白格」。不用精确计算棋形而是只取一个距离半径内的空白格随机在这批格里选。这样可以大幅减少那些落在天涯海角的无效模拟让每一局随机对弈更快决出胜负效果上相当于给模拟阶段加了一个启发式剪枝。另一个改进是「连续性检查」落子后立刻判断是否成五如果成五就提前结束模拟不必继续随机下到棋盘填满。这两个改动加在一起能把有效模拟深度从平均20步降到10步左右搜索速度几乎翻倍。def simulate_heuristic(board): while not board.is_terminal(): empty board.get_empty_cells() if not empty: break occupied [m for m in board.move_history] candidates [] for cell in empty: r, c divmod(cell, board.size) near False for dr in (-2, -1, 0, 1, 2): for dc in (-2, -1, 0, 1, 2): if dr 0 and dc 0: continue nr, nc r dr, c dc if not (0 nr board.size and 0 nc board.size): continue if board.board[nr * board.size nc] ! 0: near True break if near: break if near: candidates.append(cell) if not candidates: candidates empty move random.choice(candidates) board.apply_move(move) return board.check_win(board.move_history[-1])这个启发式模拟里near标志是判断当前候选格周围2×2半径内是否有棋子。距离半径设为2是因为五子棋的威胁范围一般不出3格太远容易引入噪声太近又可能漏掉边路进攻。注意每次循环都重新获取get_empty_cells这一点很耗时优化时可以在模拟前缓存空白格列表每落一子就删除对应项能省掉一段线性扫描。实际测试里这种做法能把每轮模拟耗时降低约30%。5.2 pattern表与终局评估不再依赖纯运气纯蒙特卡洛在前期棋局稀疏时有「冷启动」问题大家随机下每步棋的胜率差异不明显MCTS找不准方向。工程上常用的补偿措施是「先验偏好表」在expand阶段给每个孩子一个初始的wins值这个值来自局部棋形的评分而不是从0开始统计。常见做法是预处理一个小型pattern表把「活二」「活三」「冲四」等棋形映射到初始胜率偏移量。实现上不必在MCTSNode里加字段可以直接在expand时用child.wins pattern_score(move, board)来注入先验。PATTERN_SCORES { live_two: 0.1, live_three: 0.3, rush_four: 0.4, live_four: 0.9, } def pattern_score(move, board): player board.current_player directions [(1, 0), (0, 1), (1, 1), (1, -1)] total 0.0 r, c divmod(move, board.size) for dr, dc in directions: count 1 open_ends 0 for step in range(1, 5): nr, nc r dr * step, c dc * step if not (0 nr board.size and 0 nc board.size): break if board.board[nr * board.size nc] player: count 1 else: if board.board[nr * board.size nc] 0: open_ends 1 break for step in range(1, 5): nr, nc r - dr * step, c - dc * step if not (0 nr board.size and 0 nc board.size): break if board.board[nr * board.size nc] player: count 1 else: if board.board[nr * board.size nc] 0: open_ends 1 break if count 5: total 1.0 elif count 4 and open_ends 1: total PATTERN_SCORES[live_four] elif count 4: total PATTERN_SCORES[rush_four] elif count 3 and open_ends 2: total PATTERN_SCORES[live_three] elif count 2 and open_ends 2: total PATTERN_SCORES[live_two] return totalpattern评分里open_ends的计算有个细节open_ends记录的是被扫描方向上「空格」的数量而不是两端各计一次。上面代码里四个方向的扫描各处理一端所以一个两端都开放的活三会得到open_ends2。这个先验评分的量级不应太大否则MCTS的随机探索会被「先验引导」带偏变成一个贪心评估函数加随机扰动的混合体。实际上业界常见的做法是让先验只占最终UCB分值的10%到20%你可以用child.wins 0.15 * pattern_score(move, board)来控制注入强度。5.3 调参表和运行效率对比参数默认值取值范围建议影响趋势iterations2000800~10000越大棋力越强但耗时线性增长GUI下超过5000会卡顿c_param1.40.5~2.0偏小棋风保守偏大棋风激进且容易随机pattern_weight0.150.0~0.4偏大搜索过早收敛到局部棋形偏小过度依赖随机simulate_heuristicTrueTrue/FalseTrue时速度快且棋力略升False时更「纯净」但更慢expand_children_size11~5一次扩展多个孩子可加速收敛但增加选择阶段计算量实操里的顺序先用默认参数跑通系统然后调iterations观察每步耗时再调c_param对比几局棋力。c_param的教科书值sqrt(2)在五子棋里偏小因为15×15的分支因子比围棋小得多探索需求没那么饥渴取1.2到1.6之间体感最稳。如果你想让AI更具攻击性把pattern_weight调到0.3左右它会更早围着已有棋子展开但要注意别让它一开局就重复下在一个区域。6. 用「可复现实验」验证AI棋力从自对弈到固定种子测试MCTS这类算法最头疼的是「不确定感」——明明每次都跑同样的开局结果却不同。为了验证调参是否有效最简单有效的办法是固定随机种子做自对弈对比。写一个play_self(games20, seed42)函数让两个相同参数但不同先验权重的AI互下统计胜率。这样可以避免「感觉变强了」这种主观判断。def play_self(iterations_a, c_param_a, iterations_b, c_param_b, games10, seed42): random.seed(seed) wins_a 0 wins_b 0 draws 0 for _ in range(games): board GomokuBoard(15) first_turn random.randint(1, 2) while not board.is_terminal(): current board.current_player if (current 1 and first_turn 1) or (current 2 and first_turn ! 1): mcts MCTS(board, current, iterationsiterations_a, c_paramc_param_a) else: mcts MCTS(board, current, iterationsiterations_b, c_paramc_param_b) move mcts.best_move() if move is None: break board.apply_move(move) winner board.check_win(board.move_history[-1]) if board.move_history else 0 if winner 0: draws 1 elif (winner 1 and first_turn 1) or (winner 2 and first_turn ! 1): wins_a 1 else: wins_b 1 return wins_a, wins_b, draws写这个自对弈脚本时有一个必须注意的坑MCTS的构造函数里如果每次都对board直接操作第二次AI计算时棋盘状态已经被上一次的落子污染了。上面的代码在每次循环里用board变量但MCTS内部用board.duplicate()来避免污染原始棋盘——如果duplicate()实现不当自对弈结果会完全错乱。验证duplicate()是否正确的方法很简单对同一棋盘连续apply_move两次不同位置再检查原始棋盘没有改变。这虽然是一行代码的事情但一旦出错你的所有对比实验都白做。最后一招是「固定种子快照测试」让AI先手走move112即h8中心点然后记录前20步落子序列对比不同参数下序列的分叉点。MCTS的搜索树本身带有随机性即使相同种子下的第一回合结果也可能略有不同但如果你看到稳定差异出现在第5步以内说明参数对早期棋风的影响已经被放大了这时候就需要把c_param调回去一些。用这招能快速定位「调参过度导致早期随机性爆炸」的问题而不必打满一整局。想要进一步验证棋力可以引入「固定总落子数对局」让两个AI在同一棋盘上下满20步然后比较第20步的局面评估值用你的pattern_score算一个总和。这种「截断评估」比完整对局快很多适合批量扫描c_param的候选值。但要注意截断评估的结果只能提供相对排名不能作为绝对棋力证据——因为五子棋的胜负往往在最后五步才见分晓。把自对弈胜率和截断评估两种手段结合使用才是工程上既省时间又不失可信度的做法。本文还有配套的精品资源点击获取
蒙特卡洛树搜索实战：用Python从零构建五子棋AI
简介基于蒙特卡洛树搜索的AI五子棋算法实现代码面向学习人工智能与博弈算法的学生或开发者以UCT算法为核心完整覆盖选择、扩展、模拟、回传四个标准步骤。资源包共31个文件包含9个Java源文件与对应class文件、项目配置文件及png/jpg/svg图示说明压缩包仅195KB结构紧凑附有文档说明适合作为算法课程大作业或入门MCTS的参考实现。已有221人学习。文档中总结了实战调参经验默认5秒模拟可战胜一般水平玩家30秒模拟能与在线高手模式周旋同时引入形势判断对三连子、四连子等局面打分显著提升胜率并在关键时直接堵子以节省搜索时间。这些改进思路从随机模拟到启发式评估展示了如何将基础MCTS落地为可用棋力对理解算法变体与工程优化很有帮助。1. 蒙特卡洛树搜索让五子棋AI不再是暴力穷举的玩具在五子棋这类零和博弈里很多人第一反应是搜出所有落子分支——但15×15棋盘的状态空间远超任何现代机器的枚举能力。蒙特卡洛树搜索Monte Carlo Tree Search简称MCTS给出了一条反直觉的路径不追求遍历全部局面而是用随机模拟的胜负统计来引导搜索方向配合置信区间上界UCB公式在「探索新分支」和「利用已知优势」之间做权衡。这套思路的工程价值在于它不依赖手工编写的评估函数也不要求你提前整理棋谱特征而是把「哪步棋更好」这个问题转化成了「哪步棋在多轮随机对局里赢面更大」。本文面向想从零实现一个可运行五子棋AI的算法工程师和学生会从MCTS的数学骨架讲起给出可直接复制运行的Python代码、关键参数调优表以及让AI从「会下棋」到「棋风稳健」的坑位排查方案。2. 从博弈树到MCTS先算清置信区间再决定往哪搜2.1 为什么五子棋的博弈树不能硬搜传统α-β剪枝在五子棋上的困境可以从数量级看15×15棋盘第一步有225个合法落点即便每层砍掉一半分支深度6层的搜索量仍在数十亿量级。更麻烦的是五子棋缺乏像国际象棋那样的强启发式走法排序剪枝效率极不稳定。蒙特卡洛树搜索的突破口是「不展开全部子节点」每次只沿着一条路径深入用随机对弈走到底再回传胜负结果搜索树只在被访问过的节点上生长。对于IT从业者来说这个概念可以类比为A/B测试的实时版本——每个候选着法是一个实验组随机推演是流量分配胜率就是转化率而UCB公式则是一个自适应的流量调度器。2.2 UCB1公式的拆解与直觉MCTS的每个节点需要记录两个数字被访问次数n和累计胜利次数w。选择子节点时优化目标不是纯胜率w/n而是UCB1值:UCB1 w/n C * sqrt(ln(N_parent) / n)第一项是「利用」胜率高的节点优先第二项是「探索」被访问次数n越少分母越小这个值越大于是冷门分支也有机会被尝试。参数C控制两者的权重通常取sqrt(2)。在五子棋场景里如果C设得太小AI会死磕一个早期出现好结果的分支变成「井底之蛙」如果C太大AI几乎在随机瞎下。「平衡点」这个问题我会在后面实战部分的调参表里给出一组实测区间。2.3 四阶段循环选择、扩展、模拟、回传MCTS的一次迭代在代码上对应四个步骤下面先把伪代码逻辑写出来再给可运行版本。def mcts_iteration(root): # 第一阶段选择 node root state root.state.copy() while node.is_fully_expanded() and not state.is_terminal(): node best_child(node) # 按UCB1选子 state.apply_move(node.move) # 第二阶段扩展 if not state.is_terminal(): move select_unvisited_move(node, state) state.apply_move(move) node node.add_child(move, state) # 第三阶段模拟 winner playout(state) # 随机下到终局 # 第四阶段回传 while node is not None: node.update(winner) # 胜利者视角更新 node node.parent每步的含义选择阶段只走「已经完全展开」的节点保证每次都走到树的最前沿扩展阶段只给当前节点加一个没试过的孩子保持树的稀疏性模拟阶段用纯随机策略下完整个棋盘这看似粗糙但大数定律保证统计上有意义回传阶段从叶子一路更新到根每个节点都用当前这局的结果修正自己的w和n。这四个阶段里最容易出错的是「更新视角」——你需要明确胜者是以哪个玩家视角统计的否则AI的策略会反向优化。3. 用Python实现可运行的MCTS五子棋AI3.1 棋盘状态的表示与落子合法性判断实现时我推荐用一维列表长度225表示棋盘索引row*15col对应坐标。这样做的优势是落子和判断都集中在整数运算上Python的性能瓶颈能被结构简化抵消一部分。棋盘类需要提供三个核心方法落子、判断胜负、获取空白格列表。胜负判断用滑动窗口检查连五比递归判连通快得多。class GomokuBoard: def __init__(self, size15): self.size size self.board [0] * (size * size) # 0空 1黑 2白 self.current_player 1 self.move_history [] def is_valid_move(self, move): return 0 move self.size * self.size and self.board[move] 0 def apply_move(self, move): if not self.is_valid_move(move): raise ValueError(fInvalid move: {move}) self.board[move] self.current_player self.move_history.append(move) self.current_player 3 - self.current_player # 1-2切换 def get_empty_cells(self): return [i for i, v in enumerate(self.board) if v 0] def check_win(self, move): if move is None: return 0 player self.board[move] if player 0: return 0 directions [(1, 0), (0, 1), (1, 1), (1, -1)] for dr, dc in directions: count 1 r, c divmod(move, self.size) for step in range(1, 5): nr, nc r dr * step, c dc * step if not (0 nr self.size and 0 nc self.size): break if self.board[nr * self.size nc] player: count 1 else: break for step in range(1, 5): nr, nc r - dr * step, c - dc * step if not (0 nr self.size and 0 nc self.size): break if self.board[nr * self.size nc] player: count 1 else: break if count 5: return player return 0 def is_terminal(self): if len(self.move_history) self.size * self.size: return True last_move self.move_history[-1] if self.move_history else None return self.check_win(last_move) ! 0胜负判断里采用的双向线性扫描每条方向只做两次遍历时间复杂度恒定在常数级别。注意current_player用3 - current_player互换比加一取模更快。move_history不仅用于判断终局之后实现「悔棋」和「复盘」也要靠它。3.2 MCTS节点类与选择策略的代码落地节点类不要存棋盘快照而是存父节点、落子位置和累计统计量。棋盘状态只在选择阶段通过回放move_history来恢复这样避免了深拷贝225个元素的列表内存占用会明显下降。这里需要定义一个best_child方法用UCB1公式计算每个子节点的评分。import math import random class MCTSNode: def __init__(self, parentNone, moveNone): self.parent parent self.move move # 从父节点走到当前节点的落子 self.children {} self.visits 0 self.wins 0 # 以当前节点视角的胜利次数 def is_fully_expanded(self, board): return len(self.children) len(board.get_empty_cells()) def best_child(self, c_param1.4): best_score -float(inf) best_node None for child in self.children.values(): if child.visits 0: ucb float(inf) else: exploitation child.wins / child.visits exploration c_param * math.sqrt(math.log(self.visits 1) / child.visits) ucb exploitation exploration if ucb best_score: best_score ucb best_node child return best_node def update(self, result): self.visits 1 self.wins resultUCB1公式里有几个容易踩的细节。log里的self.visits 1加一是为了防止根节点还没被访问时就触发除零错误。child.visits 0时直接给无穷大意思是「没试过的分支永远优先试一次」这保证了每个合法着法至少被探索一次也避免程序在早期死循环在某一个分支上。c_param在五子棋中不建议取理论值sqrt(2)后面调参会说明原因。3.3 一次MCTS迭代的完整实现class MCTS: def __init__(self, board, player, iterations2000, c_param1.4): self.board board self.player player self.iterations iterations self.c_param c_param self.root MCTSNode() def select(self, node, board): while not board.is_terminal(): empty_cells board.get_empty_cells() if node.is_fully_expanded(board): if not node.children: return node, board node node.best_child(self.c_param) board.apply_move(node.move) else: return node, board return node, board def expand(self, node, board): tried_moves set(node.children.keys()) for move in board.get_empty_cells(): if move not in tried_moves: board.apply_move(move) child MCTSNode(parentnode, movemove) node.children[move] child return child, board return node, board def simulate(self, board): while not board.is_terminal(): empty_cells board.get_empty_cells() move random.choice(empty_cells) board.apply_move(move) return board.check_win(board.move_history[-1]) def backpropagate(self, node, winner): while node is not None: node.visits 1 if winner self.player: node.wins 1 elif winner 3 - self.player: node.wins 0 else: node.wins 0.5 node node.parent def best_move(self): for _ in range(self.iterations): node, board self.select(self.root, self.board.duplicate()) if not board.is_terminal(): node, board self.expand(node, board) winner self.simulate(board) self.backpropagate(node, winner) best_node None best_visits -1 for child in self.root.children.values(): if child.visits best_visits: best_visits child.visits best_node child return best_node.moveduplicate()方法需要在棋盘类里实现返回一个深拷贝但只复制board列表不要复制move_history的每一个元素。从工程角度看每次迭代都完整复制一次棋盘开销不小一个优化是「反悔式搜索」选择阶段逐步落子回传阶段用undo_move恢复但代码可读性会下降。初学者先跑通复制版本再优化不迟。backpropagate里平局记0.5分这是让AI在劣势局面下不激进送死的关键——如果平局记0AI会宁可输也不愿求稳。4. 让AI能真正对弈命令行入口与GUI接入4.1 命令行对弈的最小闭环要让上面的MCTS跑起来需要补一个人类玩家输入落子和棋盘打印的函数以及一个控制游戏主循环的主程序。落子输入用「字母数字」的方式比如h8程序内部转换成索引。def parse_move(text, size15): text text.strip().lower() if len(text) 2: return None col_char text[0] row_str text[1:] if not (a col_char o): return None if not row_str.isdigit(): return None row int(row_str) - 1 col ord(col_char) - ord(a) if not (0 row size and 0 col size): return None return row * size col def print_board(board): size board.size header .join(chr(ord(a) i) for i in range(size)) print(header) for r in range(size): row_chars [] for c in range(size): move r * size c if board.board[move] 1: row_chars.append(X) elif board.board[move] 2: row_chars.append(O) else: row_chars.append(.) print(f{r1:2d} .join(row_chars))坐标解析的健壮性很重要用户可能会输H8、h8或者带空格的h 8strip().lower()统一转小写再去掉首尾空格。如果你想把输入容错做得更好可以额外处理中文全角字符或8h这类行列颠倒的输入但核心逻辑仍然是拆出列字母和行数字。打印棋盘时字母表头方便人类快速定位落点X和O分别映射黑棋白棋这样终端追踪对局过程也不会眼花。4.2 主循环整合MCTS与人类落子def main(): size 15 board GomokuBoard(size) human_player 1 # 人类执黑先行 ai_player 2 print(你执黑先行输入类似 h8 的坐标落子) while not board.is_terminal(): print_board(board) current board.current_player if current human_player: while True: try: text input(你的落子: ) move parse_move(text, size) if move is None or not board.is_valid_move(move): print(非法输入请重新输入) continue board.apply_move(move) break except (ValueError, IndexError): print(输入格式错误例如 h8) else: mcts MCTS(board, ai_player, iterations2000, c_param1.4) move mcts.best_move() print(fAI落子: {move // size 1}{chr(ord(a) move % size)}) board.apply_move(move) print_board(board) winner board.check_win(board.move_history[-1]) if winner human_player: print(你赢了) elif winner ai_player: print(AI赢了) else: print(平局)主循环的判断条件是board.is_terminal()这个函数在平局和有一方连五时都会返回True。需要注意board.check_win需要传入最后一步落子位置所以主循环里move_history不能为空否则取[-1]会越界。实际操作中可把这个场景兜住如果棋盘没有空且无胜者直接返回平局结果。4.3 GUI接入从命令行迁移到可视化界面的最小改动命令行版本虽然能跑但迭代2000次的搜索在15×15棋盘上通常需要1到3秒如果人类玩家想观察AI的逐步思考命令行已经够用。如果你想接入GUI最省力的方式是保留MCTS和GomokuBoard这两个类不动只替换「输入输出层」。常见做法是用tkinter或pygame画一个15×15的网格鼠标点击位置换算成行列索引。网格绘制时注意每个格子的像素间距大约size_px // 15点击事件的像素坐标除以间距即可得到行列再把行列换算成row*15col的棋盘索引。如果要做「人机对弈模式」核心就是把input()替换成挂起的鼠标事件回调——AI计算期间最好把交互锁住否则玩家会连续点击多次导致落子错乱。5. 优化模拟策略和使用pattern表让AI从「会下」到「稳健」5.1 随机模拟策略的两处关键改进纯随机对弈虽然能保证统计无偏但在五子棋中收敛极慢。一个明显的工程改进是「优先走靠近已有棋子的空白格」。不用精确计算棋形而是只取一个距离半径内的空白格随机在这批格里选。这样可以大幅减少那些落在天涯海角的无效模拟让每一局随机对弈更快决出胜负效果上相当于给模拟阶段加了一个启发式剪枝。另一个改进是「连续性检查」落子后立刻判断是否成五如果成五就提前结束模拟不必继续随机下到棋盘填满。这两个改动加在一起能把有效模拟深度从平均20步降到10步左右搜索速度几乎翻倍。def simulate_heuristic(board): while not board.is_terminal(): empty board.get_empty_cells() if not empty: break occupied [m for m in board.move_history] candidates [] for cell in empty: r, c divmod(cell, board.size) near False for dr in (-2, -1, 0, 1, 2): for dc in (-2, -1, 0, 1, 2): if dr 0 and dc 0: continue nr, nc r dr, c dc if not (0 nr board.size and 0 nc board.size): continue if board.board[nr * board.size nc] ! 0: near True break if near: break if near: candidates.append(cell) if not candidates: candidates empty move random.choice(candidates) board.apply_move(move) return board.check_win(board.move_history[-1])这个启发式模拟里near标志是判断当前候选格周围2×2半径内是否有棋子。距离半径设为2是因为五子棋的威胁范围一般不出3格太远容易引入噪声太近又可能漏掉边路进攻。注意每次循环都重新获取get_empty_cells这一点很耗时优化时可以在模拟前缓存空白格列表每落一子就删除对应项能省掉一段线性扫描。实际测试里这种做法能把每轮模拟耗时降低约30%。5.2 pattern表与终局评估不再依赖纯运气纯蒙特卡洛在前期棋局稀疏时有「冷启动」问题大家随机下每步棋的胜率差异不明显MCTS找不准方向。工程上常用的补偿措施是「先验偏好表」在expand阶段给每个孩子一个初始的wins值这个值来自局部棋形的评分而不是从0开始统计。常见做法是预处理一个小型pattern表把「活二」「活三」「冲四」等棋形映射到初始胜率偏移量。实现上不必在MCTSNode里加字段可以直接在expand时用child.wins pattern_score(move, board)来注入先验。PATTERN_SCORES { live_two: 0.1, live_three: 0.3, rush_four: 0.4, live_four: 0.9, } def pattern_score(move, board): player board.current_player directions [(1, 0), (0, 1), (1, 1), (1, -1)] total 0.0 r, c divmod(move, board.size) for dr, dc in directions: count 1 open_ends 0 for step in range(1, 5): nr, nc r dr * step, c dc * step if not (0 nr board.size and 0 nc board.size): break if board.board[nr * board.size nc] player: count 1 else: if board.board[nr * board.size nc] 0: open_ends 1 break for step in range(1, 5): nr, nc r - dr * step, c - dc * step if not (0 nr board.size and 0 nc board.size): break if board.board[nr * board.size nc] player: count 1 else: if board.board[nr * board.size nc] 0: open_ends 1 break if count 5: total 1.0 elif count 4 and open_ends 1: total PATTERN_SCORES[live_four] elif count 4: total PATTERN_SCORES[rush_four] elif count 3 and open_ends 2: total PATTERN_SCORES[live_three] elif count 2 and open_ends 2: total PATTERN_SCORES[live_two] return totalpattern评分里open_ends的计算有个细节open_ends记录的是被扫描方向上「空格」的数量而不是两端各计一次。上面代码里四个方向的扫描各处理一端所以一个两端都开放的活三会得到open_ends2。这个先验评分的量级不应太大否则MCTS的随机探索会被「先验引导」带偏变成一个贪心评估函数加随机扰动的混合体。实际上业界常见的做法是让先验只占最终UCB分值的10%到20%你可以用child.wins 0.15 * pattern_score(move, board)来控制注入强度。5.3 调参表和运行效率对比参数默认值取值范围建议影响趋势iterations2000800~10000越大棋力越强但耗时线性增长GUI下超过5000会卡顿c_param1.40.5~2.0偏小棋风保守偏大棋风激进且容易随机pattern_weight0.150.0~0.4偏大搜索过早收敛到局部棋形偏小过度依赖随机simulate_heuristicTrueTrue/FalseTrue时速度快且棋力略升False时更「纯净」但更慢expand_children_size11~5一次扩展多个孩子可加速收敛但增加选择阶段计算量实操里的顺序先用默认参数跑通系统然后调iterations观察每步耗时再调c_param对比几局棋力。c_param的教科书值sqrt(2)在五子棋里偏小因为15×15的分支因子比围棋小得多探索需求没那么饥渴取1.2到1.6之间体感最稳。如果你想让AI更具攻击性把pattern_weight调到0.3左右它会更早围着已有棋子展开但要注意别让它一开局就重复下在一个区域。6. 用「可复现实验」验证AI棋力从自对弈到固定种子测试MCTS这类算法最头疼的是「不确定感」——明明每次都跑同样的开局结果却不同。为了验证调参是否有效最简单有效的办法是固定随机种子做自对弈对比。写一个play_self(games20, seed42)函数让两个相同参数但不同先验权重的AI互下统计胜率。这样可以避免「感觉变强了」这种主观判断。def play_self(iterations_a, c_param_a, iterations_b, c_param_b, games10, seed42): random.seed(seed) wins_a 0 wins_b 0 draws 0 for _ in range(games): board GomokuBoard(15) first_turn random.randint(1, 2) while not board.is_terminal(): current board.current_player if (current 1 and first_turn 1) or (current 2 and first_turn ! 1): mcts MCTS(board, current, iterationsiterations_a, c_paramc_param_a) else: mcts MCTS(board, current, iterationsiterations_b, c_paramc_param_b) move mcts.best_move() if move is None: break board.apply_move(move) winner board.check_win(board.move_history[-1]) if board.move_history else 0 if winner 0: draws 1 elif (winner 1 and first_turn 1) or (winner 2 and first_turn ! 1): wins_a 1 else: wins_b 1 return wins_a, wins_b, draws写这个自对弈脚本时有一个必须注意的坑MCTS的构造函数里如果每次都对board直接操作第二次AI计算时棋盘状态已经被上一次的落子污染了。上面的代码在每次循环里用board变量但MCTS内部用board.duplicate()来避免污染原始棋盘——如果duplicate()实现不当自对弈结果会完全错乱。验证duplicate()是否正确的方法很简单对同一棋盘连续apply_move两次不同位置再检查原始棋盘没有改变。这虽然是一行代码的事情但一旦出错你的所有对比实验都白做。最后一招是「固定种子快照测试」让AI先手走move112即h8中心点然后记录前20步落子序列对比不同参数下序列的分叉点。MCTS的搜索树本身带有随机性即使相同种子下的第一回合结果也可能略有不同但如果你看到稳定差异出现在第5步以内说明参数对早期棋风的影响已经被放大了这时候就需要把c_param调回去一些。用这招能快速定位「调参过度导致早期随机性爆炸」的问题而不必打满一整局。想要进一步验证棋力可以引入「固定总落子数对局」让两个AI在同一棋盘上下满20步然后比较第20步的局面评估值用你的pattern_score算一个总和。这种「截断评估」比完整对局快很多适合批量扫描c_param的候选值。但要注意截断评估的结果只能提供相对排名不能作为绝对棋力证据——因为五子棋的胜负往往在最后五步才见分晓。把自对弈胜率和截断评估两种手段结合使用才是工程上既省时间又不失可信度的做法。本文还有配套的精品资源点击获取 
