简介这份资源是一套面向人工智能初学者与棋类算法爱好者的五子棋AI程序核心围绕alpha-beta剪枝算法实现人机对弈帮助读者理解极小极大搜索、剪枝优化与棋局评估函数的设计思路。压缩包共112个文件约3.3MB以h头文件与cpp源文件为主辅以obj、sbr等编译中间文件及exe可执行程序另含ico、bmp等界面资源结构上覆盖C语言与VC6.0两个版本便于对照学习面向对象与过程式两种实现方式。程序还包含禁手规则判定与倒计时功能贴近正式比赛场景。目前已有2134人学习下载适合希望从零理解博弈树搜索、评估函数与剪枝策略的开发者参考也可作为课程设计或棋类AI入门的实践素材。1. 从「能下」到「会算」alpha-beta 剪枝五子棋到底在解决什么很多人第一次写五子棋 AI都会掉进同一个坑让程序把每一步都算到底结果搜索树爆炸电脑风扇狂转棋盘上却迟迟不落子。人工智能 alpha-beta 剪枝五子棋程序要解决的核心问题不是「怎么判断五子连珠」而是「在有限时间里怎么把明显没用的分支提前砍掉把算力留给真正有威胁的走法」。它适合两类人一类是想理解博弈树搜索到底怎么落地的开发者另一类是已经能写出极大极小搜索、但发现程序慢到没法玩的同学。我见过太多 Demo 卡在「深度一开就卡死」这一步其实不是算法难而是剪枝顺序和评估函数没配合好。这一章先把边界划清楚alpha-beta 不是新算法它只是极小极大搜索的一种加速形式前提是分支能排序、评估能打分。2. 博弈树、评估函数与剪枝窗口先把三个概念钉死2.1 为什么五子棋的搜索树不能硬搜到底五子棋棋盘常见 15×15空位约 225 个。如果每一步都穷举所有空位第一层 225 个分支第二层 224 个第三层 223 个深度 4 就已经是 225×224×223×222 这个量级任何单机程序都扛不住。真实对局里绝大多数空位是废棋真正值得算的只有已有棋子周围 1 到 2 格的范围。所以第一步不是写剪枝而是做「候选点生成」只保留邻近已有棋子的空位把分支从 200 多压到 20 到 40。这个预处理做不好后面 alpha-beta 再漂亮也救不回来。常见做法是维护一个候选点集合每次落子后把该点周围 2 格内的空位加入集合同时去重。这样分支因子能稳定在 30 以内深度 6 到 8 才有希望。我一般会再加一条如果某点周围 1 格内有对方棋子优先级调高因为它更可能形成阻挡或反击。2.2 评估函数剪枝砍得对不对全看它打分准不准alpha-beta 只负责「不搜索注定被淘汰的分支」但哪个分支该淘汰是评估函数说了算。五子棋的评估通常按棋型打分活四、冲四、活三、眠三、活二、眠二各自给不同分值。一个可用的起步分值表如下棋型说明建议分值连五已经五连10000000活四两端开放的四100000冲四一端被封的四10000活三两端开放的三8000眠三一端被封的三500活二两端开放的二300眠二一端被封的二50评估函数要做的是遍历棋盘上所有线段横、竖、两个斜向统计双方棋型然后用自己的总分减对方总分。注意分值不是绝对的活三给 8000 还是 10000 会直接影响 AI 是偏进攻还是偏防守。我一般会让进攻分略高于防守分否则 AI 容易变得畏手畏脚。2.3 alpha-beta 的窗口到底在剪什么极小极大搜索里MAX 层想拿最大分MIN 层想拿最小分。alpha 是 MAX 层当前能保证的最好值beta 是 MIN 层当前能保证的最坏值。搜索过程中如果某个节点发现 beta alpha说明这个分支对上层来说已经没有继续看的价值直接返回。这就是剪枝。用伪代码表达核心逻辑def alphabeta(board, depth, alpha, beta, is_max): # 到达叶子节点或深度耗尽返回评估分 if depth 0 or game_over(board): return evaluate(board) if is_max: value -INF for move in generate_moves(board): board.place(move, AI) # 递归搜索下一层注意 alpha 和 beta 的传递 score alphabeta(board, depth - 1, alpha, beta, False) board.undo(move) value max(value, score) alpha max(alpha, value) # 关键剪枝beta alpha 时MIN 层不会选这个分支 if beta alpha: break return value else: value INF for move in generate_moves(board): board.place(move, HUMAN) score alphabeta(board, depth - 1, alpha, beta, True) board.undo(move) value min(value, score) beta min(beta, value) if beta alpha: break return value这段代码里alpha和beta是剪枝窗口generate_moves返回候选点evaluate返回当前局面打分。剪枝发生在beta alpha那一刻意味着这个分支的分数已经不可能影响上层决策。参数上初始调用一般传alpha -INF、beta INF深度根据性能调常见 4 到 8。3. 把 alpha-beta 五子棋跑起来候选点、排序与迭代加深3.1 候选点生成别让 AI 在空棋盘上瞎算候选点生成直接决定搜索宽度。我一般用「邻近半径 2」策略只考虑距离任意已有棋子曼哈顿距离不超过 2 的空位。实现时可以用一个集合每次落子后更新。def generate_moves(board, radius2): moves set() for (r, c) in board.occupied: for dr in range(-radius, radius 1): for dc in range(-radius, radius 1): nr, nc r dr, c dc # 只保留棋盘内且为空的位置 if board.in_bounds(nr, nc) and board.is_empty(nr, nc): moves.add((nr, nc)) return list(moves)逻辑说明board.occupied是已落子位置集合遍历每个已落子点周围半径 2 的范围把空位加入候选。参数radius控制搜索宽度半径 1 更快但可能漏掉远距离好点半径 2 是常见折中。如果候选点还是太多可以再加一层过滤只保留周围 1 格内有棋子的点。3.2 走法排序剪枝效率的命门alpha-beta 的剪枝量极度依赖走法顺序。如果先搜好棋剪枝会大量发生如果先搜废棋剪枝几乎不发生。所以生成候选点后必须按「威胁程度」排序。常见做法是给每个候选点算一个启发分如果落子后能形成活四或冲四排最前其次是活三再次是普通邻近点。def order_moves(board, moves, player): scored [] for move in moves: board.place(move, player) # 用评估函数快速打分作为排序依据 score evaluate(board) board.undo(move) scored.append((score, move)) # 按分数从高到低排序让好棋先被搜索 scored.sort(reverseTrue, keylambda x: x[0]) return [move for _, move in scored]这里用完整评估函数排序会慢实战中常用简化版只统计该点四个方向上的连续棋子数快速给出启发分。参数上排序不需要绝对精确只要把「明显好」的走法排前面就行。3.3 迭代加深让 AI 在时间限制内给出答案固定深度搜索有个问题深度设浅了棋力弱设深了可能超时。迭代加深的思路是先搜深度 2再搜深度 4再搜深度 6每次用上一轮的结果给本轮排序。这样即使时间到了也能拿到一个较浅但可用的结果。def search_with_iterative_deepening(board, max_depth, time_limit): best_move None start time.time() for depth in range(2, max_depth 1, 2): # 用上一轮最佳走法优先排序提升剪枝效率 move alphabeta_root(board, depth, best_move) if time.time() - start time_limit: break best_move move return best_move参数说明max_depth是最大深度time_limit是时间上限秒。alphabeta_root是根节点搜索内部会调用前面的alphabeta。注意迭代加深不是必须的但它是让程序「稳定不超时」的最实用手段。4. 避坑与排查alpha-beta 五子棋最常见的 5 个翻车点4.1 剪枝后棋力反而下降现象加了 alpha-beta搜索深度上去了但 AI 下棋变笨经常漏掉对方的活三。原因评估函数在剪枝后暴露了偏差原本靠穷举能兜住的局面现在被错误剪掉。解决先关掉剪枝用纯极小极大跑几局确认评估函数本身合理再开剪枝对比同一局面的打分差异。如果差异大说明排序或评估有问题。4.2 候选点半径设成 1AI 不会下远点现象AI 只会在棋子堆里落子遇到需要提前布局的局面就乱下。原因半径 1 的候选点太窄远距离的活二、活三起点被排除。解决把半径调到 2或者在评估函数里对「潜在连线」加分让远点也能进入候选。4.3 递归深度一开大就栈溢出现象深度设到 10 以上程序直接崩。原因递归层数太深Python 默认递归限制约 1000但每层还有循环和临时变量实际能撑的深度有限。解决用迭代加深控制深度或者把递归改成显式栈。更常见的做法是深度不超过 8靠排序和剪枝提升棋力。4.4 评估函数每次全盘扫描慢到没法用现象搜索 3 层就要好几秒。原因evaluate每次遍历整个棋盘所有线段调用次数太多。解决增量更新。落子时只更新该点四个方向的棋型分撤销时恢复。这样评估从 O(棋盘) 降到 O(1) 附近。4.5 先手优势被评估函数吃掉现象AI 执先手时畏缩执后手时又过于激进。原因评估函数没有区分先后手或者攻防分值不对称。解决在根节点搜索时给先手方一个小的固定加分或者在评估里让「轮到谁走」影响棋型权重。这个调整很玄学需要跑几十局慢慢调。5. 进阶技巧用置换表和静态搜索把棋力再抬一档5.1 置换表别重复算同一个局面搜索树里不同走法顺序可能到达同一个局面。置换表就是用一个哈希表缓存「局面 → 分数、深度、标志」。下次遇到相同局面直接查表省掉重复搜索。def alphabeta_with_tt(board, depth, alpha, beta, is_max, tt): key board.zobrist_hash() if key in tt: entry tt[key] # 只有缓存深度足够时才直接返回 if entry.depth depth: return entry.score # ... 正常搜索逻辑 ... tt[key] TTEntry(value, depth, flag) return value参数说明zobrist_hash是局面的哈希值TTEntry存分数、深度和标志精确值/上界/下界。注意置换表要配合迭代加深用否则缓存命中率低。5.2 静态搜索解决「地平线效应」固定深度搜索有个毛病搜索到深度 0 时局面可能正处在吃子或连珠的中间评估函数给出一个虚高分导致 AI 误判。静态搜索的做法是在深度 0 时不直接评估而是继续搜「强制走法」比如冲四、活四直到局面稳定。def quiescence(board, alpha, beta, is_max): # 先拿静态评估作为保底 stand_pat evaluate(board) if is_max: if stand_pat beta: return beta alpha max(alpha, stand_pat) for move in generate_forced_moves(board): board.place(move, AI) score quiescence(board, alpha, beta, False) board.undo(move) if score beta: return beta alpha max(alpha, score) return alpha # MIN 层对称处理这段代码只搜强制走法不搜普通空位所以不会爆炸。参数上generate_forced_moves只返回能形成冲四或活四的点。静态搜索通常加在 alpha-beta 的叶子节点上能明显减少「明明能赢却判和」的情况。5.3 一个我常用的调参习惯我调五子棋 AI 时不会一上来就开深度 8。先固定深度 4把评估函数和排序调到「能稳定赢随机走子」再开迭代加深观察每轮耗时。如果深度 6 耗时超过 1 秒就先优化候选点生成和增量评估而不是继续加深度。血泪经验是剪枝效率的瓶颈往往不在剪枝本身而在走法排序和评估速度。把这两个做好深度 6 的棋力已经能打赢大多数业余玩家。希望帮到你。本文还有配套的精品资源点击获取