基于α-β剪枝的五子棋人机对战：博弈树与评估函数实战解析

简介这是一套基于Python实现的五子棋人机对战完整项目面向正在学习人工智能博弈算法、搜索策略或pygame游戏开发的初学者与进阶学习者。程序以pygame搭建交互界面核心通过极大极小值搜索驱动电脑走子并引入α-β剪枝大幅提升搜索效率配合精心设计的评估函数使AI具备一定的棋力同时完整覆盖先后手选择、胜负判定、棋盘落子与信息展示等基础交互功能。压缩包共3个文件包含2个Python源码主程序和1个txt代码说明文档整体仅15KB体量结构精简、逻辑清晰便于通读源码理解搜索树构建与剪枝判断的完整流程。目前已有4704人学习浏览资源提供了从算法设计到界面落地的全流程代码读者可直接运行体验人机对战也可对照源码细致理解极大极小值搜索、α-β剪枝、评估函数等关键模块的实现细节作为课程设计或算法练手的参考素材。1. 基于α-β剪枝的五子棋人机对战这颗脑子是怎么骗过你的五子棋好像是个规则简单到不能再简单的游戏但你真去实现一个“能赢你”的AI就会发现棋盘上每一条线都是陷阱。这个项目的核心可以用一句话说透它用α-β剪枝把博弈树里那些注定吃亏的分支剪掉让电脑在每回合几千种落子可能里快速挑出一个不吃亏的位置。相比“只盯着眼前连成五子”的贪心AI它下棋时会多往前看四到六步甚至故意堵你活三的活口。我拆这个项目时最有感触的是真正让它变聪明的不是pygame画了几个圆而是AI模块里那几十行递归函数。它适合三类人——复现课设的大学生、想看懂博弈树实际效果的算法初学者、想拿五子棋当起点改造成其他棋类AI的开发者。2. 项目全景与运行环境从目录结构到敲下第一条命令2.1 项目技术栈与架构分层这个项目是典型的单文件风格但功能边界划得很清晰。整体上分为三层界面层由pygame负责渲染棋盘、处理鼠标点击和窗口事件业务逻辑层维护棋局数据、判定五子连珠、切换回合AI层是整颗大脑基于α-β剪枝的搜索树配合局面评估函数决定机器人的下一步落点。三层之间通过一个Game类串起来main.py里初始化这个类然后在主循环里不断刷新界面并喂给它事件。技术选型上没有任何花架子Python 3.x pygame。搜索树部分用的是递归没有引入Numpy棋盘直接用一个二维列表维护长度15的列表套15个元素。棋子的颜色用1和2表示黑棋先手0代表空位。这种朴素表示的好处是代码逻辑好追踪坏处是评估函数必须手写大量的方向扫描逻辑后面你会看到代码在这部分最绕。pip install pygame2.5.2这个版本号是我项目里锁定的。pygame新版本在窗口缩放和字体渲染上有细微差异如果只是跑这个五子棋2.5.2足够稳定。装完依赖后进入项目根目录执行python main.py窗口会弹出左侧是15×15棋盘点击交叉点落子黑棋由你控制白棋由AI控制。按下R键可以重置一局。2.2 目录结构与模块职责拆开压缩包后你会发现文件结构清晰到让人舒服gobang/ ├── main.py # 程序入口窗口初始化和主循环 ├── game.py # 游戏逻辑棋盘数据、落子校验、胜负判断 ├── ai.py # AI模块评估函数 α-β剪枝搜索 └── config.py # 常量配置棋盘尺寸、格距、棋子颜色、搜索深度config.py里深藏着一个重要的参数AI搜索深度。我拆的这份代码里默认是4意味着电脑会模拟自己和对手往后各下两步。如果你的电脑性能不错可以改成6AI的棋力会明显上一个小台阶但落子耗时也会从几十毫秒涨到两三秒。如果手头有没写完作业的紧迫感把这个参数调小到2瞬间就能跑出“新手玩家”的感觉。game.py里真正让AI能“看得懂局面”的接口是一个名为get_valid_moves的函数它返回所有空位坐标。更精彩的是AI并不会在全部225个空位上搜索而是只考虑“周围八格内有棋子的空位”这一步把搜索树的分支因子降了不止一个量级。我在后面第3章会连代码带逻辑一起拆开讲。2.3 运行体验与初始状态第一次跑起来时你会看到棋盘格线画得整整齐齐左上角显示红蓝两色指示当前轮到谁。AI在思考时会短暂停顿这个过程正是α-β剪枝在递归搜索中做比较运算的耗时窗口。轮到AI行动时程序会走这样一条链路main.py检测到当前回合是AI调用ai.get_best_move(game)这个函数内部展开一棵搜索树然后返回一个(row, col)坐标主循环拿到坐标后更新棋盘数组再重新绘制界面。如果你运行的是我最开始接触的那版代码可能会发现一个反直觉的现象——AI先手时会选择正中央的天元开局后手时会选择紧贴你第一颗棋子的斜对角位置。这不是巧合而是评估函数认为“靠近已有棋子”的局面更有价值。这个设计决策我在评估函数章节会展开说清楚。3. 核心AI模块拆解α-β剪枝如何让人机变聪明3.1 胜利判定与棋局表示在讲解AI搜索之前先看一个所有逻辑的基石如何判定某方获胜。这部分代码在game.py里写法是遍历每个落子点检查四个方向水平、垂直、两条对角线上连续同色棋子的数量def check_win(board, row, col, player): 检查在(row, col)落子后player是否胜利 directions [(1, 0), (0, 1), (1, 1), (1, -1)] for dr, dc in directions: count 1 # 正方向延伸 r, c row dr, col dc while 0 r 15 and 0 c 15 and board[r][c] player: count 1 r dr c dc # 反方向延伸 r, c row - dr, col - dc while 0 r 15 and 0 c 15 and board[r][c] player: count 1 r - dr c - dc if count 5: return True return False这个函数在项目里被调用得很频繁玩家落子后调用它AI每一步搜索的叶子节点也调用它。count初始化为1是因为落子点本身就占了一个格子。四个方向就覆盖了五子棋所有的直线连珠可能。反向延伸时坐标偏移取负配合while循环里的边界检查保证不会数组越界。整段代码没有用奇技淫巧但对于这个项目的体量可读性比性能重要得多。3.2 评估函数设计从贪心到局面研判α-β剪枝的好坏一半取决于剪枝本身一半取决于评估函数。如果评估函数只能识别“已经有四颗连子”那AI只会追杀眼前的活四完全不懂布局。这份项目的评估函数写得相当有层次核心思路是扫描每一行、每一列、每一条对角线把连续的玩家棋子看作一个得分片段按长度和两端状态赋予不同权重def evaluate_line(line, player): 计算一条线上player的得分 line: 一个方向上15个格子的状态列表 score 0 opponent 3 - player for i in range(len(line)): if line[i] ! player: continue # 往右统计连续棋子数 length 1 while i length len(line) and line[i length] player: length 1 # 判断两端状态0为空位1为对方棋子2为边界 left line[i - 1] if i 0 else 2 right line[i length] if i length len(line) else 2 open_ends 0 if left 0: open_ends 1 if right 0: open_ends 1 # 根据连子数和开放端给分 if length 5: score 100000 elif length 4: if open_ends 2: score 50000 # 活四无解 elif open_ends 1: score 10000 # 冲四 elif length 3: if open_ends 2: score 5000 # 活三潜力大 elif open_ends 1: score 1000 # 眠三 elif length 2: if open_ends 2: score 500 elif open_ends 1: score 100 i length return score这段代码把“活三”看得比“冲四”轻是有讲究的——活三下一步能变成活四活四无论如何都会被对方封堵不及得分自然要拉开差距。i length让循环跳过已经统计过的连续棋子避免重复计算。open_ends 2表示两端都空这是棋局里最有威胁的形状。整体评估时对每个位置计算己方得分加上一个惩罚系数乘以对方得分惩罚系数在config.py里叫attack_weight默认0.8。3.3 α-β剪枝搜索博弈树上的决策灵魂这是整个项目含金量最高的代码AI能不能看穿你的套路全靠这个递归函数。它的核心思路是在搜索树上维护两个值——α表示己方目前能保证的最低分β表示对方能保证的最高分。当某一层的估值超过了β对手就不会选择这条分支剪掉它继续搜索的意义def alphabeta(board, depth, alpha, beta, is_maximizing, player): board: 当前棋盘 depth: 剩余搜索深度 alpha: 己方能得到的最低分 beta: 对方能接受的最高分 is_maximizing: True表示当前轮AI落子False模拟对手落子 valid_moves get_candidate_moves(board) if depth 0 or not valid_moves: return evaluate_board(board, player) if is_maximizing: max_eval -float(inf) for row, col in valid_moves: board[row][col] player eval alphabeta(board, depth - 1, alpha, beta, False, player) board[row][col] 0 max_eval max(max_eval, eval) alpha max(alpha, eval) if beta alpha: break # 剪枝对手不会让局面走到这一步 return max_eval else: min_eval float(inf) opponent 3 - player for row, col in valid_moves: board[row][col] opponent eval alphabeta(board, depth - 1, alpha, beta, True, player) board[row][col] 0 min_eval min(min_eval, eval) beta min(beta, eval) if beta alpha: break return min_evalget_candidate_moves的作用前面提到过只返回已有棋子邻域内的空位很多教学版五子棋忽略这个优化导致深度调到4就跑不动。在递归落子之后代码立刻把位置重置为0这是回溯的必经步骤漏掉会让棋盘数据越搜越乱。剪枝的发生时机藏在if beta alpha处一旦发现对手正选择的路径已经不可能比之前更好就直接跳出循环。顶层的调用逻辑会遍历每个候选点执行alphabeta(board, depth, -inf, inf, True, player)然后把返回分最高的那个点作为AI的落子def get_best_move(board, player, depth4): AI入口遍历候选点返回(行, 列) valid_moves get_candidate_moves(board) best_score -float(inf) best_move valid_moves[0] for row, col in valid_moves: board[row][col] player score alphabeta(board, depth - 1, -float(inf), float(inf), False, player) board[row][col] 0 if score best_score: best_score score best_move (row, col) return best_move你可能会问为什么不在递归里把depth直接传成4而要在这里减一。因为顶层节点没有“对手回应”的概念它就是纯粹的决策点消耗一层深度给对手做模拟回应语义更清晰。分数对比用而不是保证在相等局面下优先选择靠前的点棋盘扫描顺序天然偏向左上角。4. 对战逻辑与pygame界面从棋盘渲染到落子交互4.1 棋盘初始化与棋子绘制pygame的职责在项目里非常纯粹画出15×15的格子接受鼠标点击把黑白棋子显示成圆形。config.py里定义了几个关键常量——格子尺寸CELL_SIZE 40棋盘左上角起始坐标MARGIN 30这样整个窗口尺寸就是MARGIN * 2 CELL_SIZE * 14。这么算是因为15条线之间只有14个格子间距。绘制棋盘的代码核心在main.py的draw_board()里def draw_board(screen, board): screen.fill((240, 200, 120)) # 木色背景 for row in range(15): for col in range(15): x MARGIN col * CELL_SIZE y MARGIN row * CELL_SIZE # 先画交叉点附近的方形小格子增强棋盘纹理感 pygame.draw.rect(screen, (200, 160, 90), (x - 18, y - 18, 36, 36)) for i in range(15): start MARGIN i * CELL_SIZE pygame.draw.line(screen, (0, 0, 0), (MARGIN, start), (MARGIN 14 * CELL_SIZE, start), 2) pygame.draw.line(screen, (0, 0, 0), (start, MARGIN), (start, MARGIN 14 * CELL_SIZE), 2) for row in range(15): for col in range(15): if board[row][col] 1: pygame.draw.circle(screen, (0, 0, 0), (MARGIN col * CELL_SIZE, MARGIN row * CELL_SIZE), 16, 0) elif board[row][col] 2: pygame.draw.circle(screen, (255, 255, 255), (MARGIN col * CELL_SIZE, MARGIN row * CELL_SIZE), 16, 0)画线时有个容易翻车的细节range(15)画15条线最后一个点坐标是MARGIN 14 * CELL_SIZE不是MARGIN 15 * CELL_SIZE否则棋盘会整体向右下偏移一格。我最早自己写的时候就在这里吃过亏棋子落在线上的位置对不齐。棋子圆形的半径16比格子的一半略小多边形边缘留出缝隙视觉上更接近真实棋盘也方便观察相邻棋子是否连成一条线。4.2 主循环事件处理与回合调度main.py的主循环是一个标准的pygame事件框架在里面处理两种核心事件鼠标点击和键盘按键。鼠标事件只对玩家回合生效AI回合的所有鼠标点击会被忽略。判断点击是否落到棋盘范围内需要把像素坐标转换到格子坐标def pixel_to_grid(x, y): 像素坐标转棋盘行列精确到最近交叉点 if x MARGIN - 20 or y MARGIN - 20: return -1, -1 if x MARGIN 14 * CELL_SIZE 20 or y MARGIN 14 * CELL_SIZE 20: return -1, -1 col round((x - MARGIN) / CELL_SIZE) row round((y - MARGIN) / CELL_SIZE) if 0 row 15 and 0 col 15: return row, col return -1, -1注意这里用round而不是int截断。如果用int点击两个交叉点中间的位置时会落到左边的格子体验很生硬。round是四舍五入到最近交叉点同时用MARGIN - 20做了20像素的容错鼠标在棋盘边缘稍微偏出也能正确落子。20这个值比半个格子小不会造成相邻位置误判。主循环的回合调度逻辑如下如果当前是玩家回合等待鼠标点击点击合法位置后落子、检查胜负、切换回合。如果变成AI回合调用get_best_move拿到落点、落子、检查胜负再把回合切回给玩家。胜负检查后如果发现胜者弹出一个pygame对话框同时把game_over标志置为True之后的点击不再响应。4.3 人机对战体验与平局处理对弈体验上最影响手感的是AI思考时界面是否卡顿。这份代码直接在AI落子前调用pygame.display.flip()刷新一次界面让玩家看到自己的棋子已经落定再进入AI计算。如果你的电脑在深度4下要算两秒以上会感觉棋盘短暂“冻结”这是正常现象。如果想优化可以把config.py里的SEARCH_DEPTH改成3AI反应会明显更快但棋力会下降一截。平局处理也是容易被忽略的一块。15×15棋盘有225个交叉点但AI搜索只看有邻居的空位所以平局在实际游戏中很少出现。代码里维护了一个empty_blocks变量每落一子减一减到零且无人获胜时宣布平局。这块逻辑虽然简单但在AI对AI的调试场景里非常有用——我在测试评估函数时经常出现双方互堵、最后下满棋盘的情况。5. 常见问题与避坑搜索太慢、剪枝失效与棋盘玄学5.1 现象AI落子偶尔慢得离谱你明明把深度设成了4大部分情况下AI半秒内落子有一两次却卡了三秒以上。原因并不复杂α-β剪枝的剪枝效果依赖节点访问顺序。如果候选点排列是随机的剪枝率就低搜索树接近于全量展开。解决评估函数算一次当前局面的每个候选点得分按从高到低排序再喂给alphabeta。这个“启发式排序”能让剪枝命中率大幅提升。我在项目里用一个简单的candidate.sort(keyscore_point, reverseTrue)就解决了问题搜索时间从三秒降回半秒。5.2 现象AI在某个局部会“抽风”下出低级失误有次我调试时发现AI已经连成三颗下一手甚至可以成活四但AI偏偏跑去堵对手的一个眠三。追踪后发现问题出在评估函数的对称性不够——evaluate_line对己方棋子和对手棋子的评估逻辑完全一致但缺少“攻击权重”的区分。如果对方得分的惩罚系数过低AI就会低估对手的威胁。解决在config.py把attack_weight从0.8调到1.2AI会更倾向于堵对手的活三。这不是标准答案而是每个棋类AI都要凭手感调的超参数。5.3 现象剪枝后和没剪枝的结果不一样信任α-β剪枝的新手最容易遇到这个困惑明明剪掉的分支里可能存在更好的走法为什么剪完结果还会一样其实这是α-β剪枝的正确性质——只要评估函数一致、搜索深度一致剪掉的分支不会影响根节点的最佳走法。如果你发现剪枝后AI走法变了核心原因多半是剪枝条件写成了if beta alpha漏掉了相等的情况。严格写法是因为相等时当前节点不需要继续搜索剪掉它不损失正确性。解决改掉这一行问题消失。5.4 现象pygame窗口弹出后闪退或黑屏运行main.py时窗口闪现后直接退出大概率是循环里没有pygame.event.get()。如果你自定义过代码把事件循环删掉就会触发这个问题——pygame窗口会认为无响应而自动关闭。我习惯在初始化后单独写一个running True的死循环内部每一帧都执行pygame.event.get()并遍历。解决检查主循环是否存在且完整初始的pygame.init()与pygame.display.set_mode是否都在调用栈之前。5.5 现象AI先手时总是下同样的位置开局单调这不是bug是评估函数对“中心位置”赋予了天然加分而中心只有一个天元点。AI每次先手下天元后手贴着玩家落子本质都是局部最优。解决给评估函数加一个多样性格子项——比如连续多局让AI在第二梯队位置随机选择。在顶层调用get_best_move时收集分数在前20%的候选点再随机选一个。加深“不可预测性”会给对弈体验带来质的变化。6. 二次开发进阶把一局棋改成可以调的引擎拆完这个项目你会发现它其实是一个骨架完整、逻辑清晰的博弈AI框架换皮就能改造成其他棋类。我实际在这个项目上做过三个改造改动量小且见效快。第一个改造是开放难度选择界面。在config.py里定义几个档位比如深度2简单、深度4普通、深度6困难。修改main.py里对SEARCH_DEPTH的引用在启动时加一个询问窗口点击对应难度后再初始化棋盘。第二个改造是调整评估函数的权重参数——把open_ends 2的活三、活四分数调高AI会更倾向主动进攻调低则偏向保守防守。这本质上是把玄学参数显式暴露成可调旋钮。第三个改造是加入棋谱记录每次落子把坐标写进一个history.txt文件重开棋局时读取并复盘。代码层面最值得扩展的地方是get_candidate_moves。现在它只关注有邻居的空位但如果你想做一个更聪明的AI可以在这个函数里加入“跳格进攻”——在有连续两子的一侧隔一格的空位也加入候选。这个改动不影响剪枝逻辑却能显著提高AI寻找跳活三的能力。另一个扩展空间在胜负判定目前的check_win只检查五子如果你想让AI支持禁手规则可以在这基础上增加双三、双四检测改动量控制在几十行内。从那以后我每次改动AI相关代码都会强制自己先在纸面上画一遍小棋盘推演再跑机器对局测试。评估函数的权重调整必须记录在案否则隔几天再回来改参数根本分不清上一次是调高了攻击性还是调低了防守权重。搜索深度也不是越大越好硬件瓶颈会在深度大于8时暴露无遗学会在“棋力”与“响应时间”之间找平衡才是这个项目的真正内核。希望帮到你。本文还有配套的精品资源点击获取