简介这份资源是一套面向人工智能初学者与棋类游戏开发爱好者的五子棋AI程序核心围绕alpha-beta剪枝算法实现人机对弈帮助读者理解极小极大搜索的优化思路与博弈树剪枝策略。压缩包共112个文件约3.3MB以h头文件、cpp源文件、obj目标文件为主另含exe可执行程序、ico图标、bmp位图及dsw、dsp工程文件覆盖C语言与VC6.0两个版本便于对照编译与调试。程序还实现了禁手规则与倒计时功能涉及三三、四四等专业判定逻辑并附带棋盘界面与棋谱相关素材。目前已有2134人学习下载适合希望从代码层面掌握alpha-beta剪枝、评估函数设计及棋盘状态管理的读者参考也可作为其他棋类AI开发的实践范例。1. 从「能下」到「会算」alpha-beta 剪枝五子棋到底强在哪很多人第一次写五子棋 AI都会掉进同一个坑让程序把每一步都往后推演结果棋盘稍微大一点搜索树就炸了程序卡死。我见过一个模拟项目纯极小化极大搜索Minimax在 15×15 棋盘上跑到第 4 层就撑不住了CPU 直接拉满。问题不在代码写得烂而在搜索空间本身是指数级的——每一层分支因子接近 200四层就是 200 的四次方这个量级没有任何单机扛得住。alpha-beta 剪枝就是来解决这个问题的。它不改变 Minimax 的最终决策结果但能在搜索过程中砍掉大量「明显不需要看」的分支。配合合理的评估函数和走法排序同样时间内搜索深度可以从 4 层拉到 8 层甚至更深。对五子棋这种「一步定生死」的棋类来说多搜两层往往就是从「被吊打」到「能还手」的分水岭。这篇笔记面向两类人一是已经写过基础五子棋、想给 AI 加上真正搜索能力的开发者二是想找一个「搜索算法 博弈评估」完整练手项目的学习者。我会从棋盘表示、评估函数、alpha-beta 实现、走法排序、迭代加深一路讲到实战调参和踩坑代码用 Python 写逻辑清晰方便你直接复现到自己的项目里。2. 棋盘表示与评估函数搜索算法的地基2.1 为什么棋盘表示决定了搜索效率在动手写 alpha-beta 之前必须先想清楚棋盘怎么存。常见做法有三种二维数组、一维数组、位棋盘。二维数组最直观board[x][y]一眼就能看懂但每次搜索都要频繁做边界判断和坐标转换在深层搜索里这些开销会被放大几百倍。我一般推荐用一维数组加偏移量的方式。15×15 棋盘展平成 225 个格子四个方向的邻居用固定偏移量计算省掉大量坐标运算。下面是一个最小可用的棋盘结构BOARD_SIZE 15 DIRECTIONS [(1, 0), (0, 1), (1, 1), (1, -1)] # 横、竖、正斜、反斜 class Board: def __init__(self): self.size BOARD_SIZE self.grid [[0] * BOARD_SIZE for _ in range(BOARD_SIZE)] self.history [] # 落子历史用于悔棋和迭代加深 def place(self, x, y, player): self.grid[x][y] player self.history.append((x, y, player)) def undo(self): x, y, player self.history.pop() self.grid[x][y] 0 def is_empty(self, x, y): return self.grid[x][y] 0 def in_bounds(self, x, y): return 0 x self.size and 0 y self.size这里用二维列表是为了可读性实际跑深层搜索时可以把grid换成一维bytearray索引用x * 15 y内存占用和访问速度都会好一截。history栈是必须的alpha-beta 搜索过程中要反复落子、撤销没有这个栈就没法正确回溯。2.2 评估函数AI 的「价值观」全在这里评估函数决定了 AI 认为什么样的局面是好局面。五子棋的评估通常基于棋型活四、冲四、活三、眠三、活二这些。每种棋型给一个分值扫描全盘统计双方得分差值就是当前局面的评估值。一个常见的做法是只扫描有棋子的位置周围而不是全盘 225 个点都扫。因为五子棋的胜负只和已有棋子附近的区域有关远处空棋盘对评估没有贡献。下面是一个简化但可用的棋型评分表棋型说明建议分值连五五子连珠100000活四两端开放的四连10000冲四一端被封的四连1000活三两端开放的三连1000眠三一端被封的三连100活二两端开放的二连100眠二一端被封的二连10SCORES { five: 100000, open_four: 10000, four: 1000, open_three: 1000, three: 100, open_two: 100, two: 10, } def evaluate(board, player): 从 player 视角评估局面返回分值差 my_score scan_patterns(board, player) opp_score scan_patterns(board, 3 - player) return my_score - opp_scorescan_patterns的实现思路是对每个有棋子的点沿四个方向取出长度为 5 到 9 的窗口匹配棋型。这里有个关键细节——同一个棋型可能被重复统计需要在扫描时做去重或者用「只从棋子序列起点统计」的方式避免。评估函数的质量直接决定 AI 的棋力上限。搜索深度再深如果评估函数把活三和眠三给成一样的分AI 照样会走出莫名其妙的棋。我踩过的坑是早期版本只统计了连子数量没有区分活和眠结果 AI 经常自己把自己的活三堵死。2.3 走法生成只考虑「有意义」的落点如果每一步都遍历 225 个空位搜索树会大得离谱。实际做法是只考虑已有棋子周围 1 到 2 格范围内的空位。这个剪枝在五子棋里非常有效因为远离棋子的位置几乎不可能形成有效进攻或防守。def generate_moves(board, radius2): 生成候选落点只取已有棋子附近的空位 candidates set() for x in range(board.size): for y in range(board.size): if board.grid[x][y] ! 0: for dx in range(-radius, radius 1): for dy in range(-radius, radius 1): nx, ny x dx, y dy if board.in_bounds(nx, ny) and board.is_empty(nx, ny): candidates.add((nx, ny)) return list(candidates)radius取 2 是常见做法取 1 会漏掉一些跳活三的防守点取 3 则候选点太多、搜索效率下降。如果棋盘上还没有棋子直接返回中心点即可。3. alpha-beta 剪枝的核心实现与走法排序3.1 Minimax 到 alpha-beta剪枝到底剪了什么Minimax 的思路是AI 走一步假设对手也走一步双方都选对自己最有利的。AI 层取最大值对手层取最小值递归到指定深度后返回评估值。问题在于很多分支根本不需要展开——如果已经发现某条路会导致对手获得巨大优势那这条路后面的变化就不用看了。alpha 是「当前 MAX 层已经能保证的最小收益」beta 是「当前 MIN 层已经能保证的最大损失」。当 alpha beta 时说明这个分支对双方都没有继续探索的价值直接剪掉。def alpha_beta(board, depth, alpha, beta, maximizing, player): alpha-beta 剪枝搜索 if depth 0 or check_win(board, player) or check_win(board, 3 - player): return evaluate(board, player) moves generate_moves(board) if not moves: return evaluate(board, player) if maximizing: max_eval float(-inf) for x, y in moves: board.place(x, y, player) val alpha_beta(board, depth - 1, alpha, beta, False, player) board.undo() max_eval max(max_eval, val) alpha max(alpha, val) if beta alpha: break # beta 剪枝 return max_eval else: min_eval float(inf) for x, y in moves: board.place(x, y, 3 - player) val alpha_beta(board, depth - 1, alpha, beta, True, player) board.undo() min_eval min(min_eval, val) beta min(beta, val) if beta alpha: break # alpha 剪枝 return min_eval这段代码是整个程序的核心。maximizing为 True 表示当前是 AI 层取最大值并更新 alpha为 False 表示对手层取最小值并更新 beta。剪枝条件beta alpha在两层里都要判断少写一个剪枝效果会差很多。3.2 走法排序让剪枝真正生效的关键alpha-beta 的剪枝效率极度依赖走法顺序。如果先搜索最好的走法剪枝能砍掉大量分支如果先搜索最差的走法剪枝几乎不起作用退化成普通 Minimax。这就是为什么「走法排序」是 alpha-beta 的灵魂。常见做法是给每个候选点做一个快速评分按分数从高到低排序。评分可以用简单的启发式这个点周围有多少己方棋子、多少对方棋子、是否形成活三或冲四。def score_move(board, x, y, player): 快速启发式评分用于走法排序 score 0 for dx, dy in DIRECTIONS: count_my 0 count_opp 0 for step in range(-4, 5): nx, ny x dx * step, y dy * step if not board.in_bounds(nx, ny): continue if board.grid[nx][ny] player: count_my 1 elif board.grid[nx][ny] 3 - player: count_opp 1 score count_my * 2 count_opp return score def ordered_moves(board, player): moves generate_moves(board) moves.sort(keylambda m: score_move(board, m[0], m[1], player), reverseTrue) return moves把ordered_moves替换掉alpha_beta里的generate_moves剪枝效率会有肉眼可见的提升。我实测过一个模拟项目同样深度 6排序前搜索节点数约 120 万排序后降到 8 万左右时间从 3 秒多压到 0.2 秒。3.3 迭代加深让 AI 在有限时间内给出答案固定深度搜索有个问题如果时间不够搜到一半被迫中断结果不可用。迭代加深的思路是先从深度 1 开始搜逐步加深到 2、3、4……每次用上一层的最优走法作为下一层的首选排序依据。这样即使中途超时也能拿到上一层完整搜索的结果。import time def iterative_deepening(board, player, time_limit2.0): 迭代加深搜索返回最佳走法 start time.time() best_move None depth 1 while time.time() - start time_limit: move search_root(board, player, depth) if move is not None: best_move move depth 1 return best_move def search_root(board, player, depth): 根节点搜索返回最佳走法 best_val float(-inf) best_move None for x, y in ordered_moves(board, player): board.place(x, y, player) val alpha_beta(board, depth - 1, float(-inf), float(inf), False, player) board.undo() if val best_val: best_val val best_move (x, y) return best_movetime_limit根据实际需求设一般 1 到 3 秒对交互式对弈比较合适。迭代加深配合走法排序还能让上一层的最优走法在下一层优先被搜索进一步提升剪枝效率。4. 避坑与排查alpha-beta 五子棋最容易翻车的地方4.1 评估函数重复统计导致分值虚高现象AI 在优势局面下突然走出自毁棋评估值显示大优但实际已经输了。原因扫描棋型时同一个连子被多个起点重复统计导致分值虚高AI 误判形势。解决扫描时只从连续棋子的起点开始统计或者用集合记录已统计的棋型位置。4.2 剪枝条件写反导致搜索结果错误现象加了 alpha-beta 之后 AI 棋力反而下降甚至走出明显送死的棋。原因alpha和beta的更新方向写反或者剪枝条件写成alpha beta但更新逻辑不匹配。解决记住 MAX 层更新 alpha、MIN 层更新 beta剪枝条件统一为beta alpha用简单局面手动验证。4.3 走法排序开销过大拖慢搜索现象加了排序之后单步思考时间反而变长。原因score_move里做了太多重复计算每个候选点都重新扫描周围。解决把候选点的启发式分数缓存起来或者用更轻量的评分方式比如只统计相邻 2 格内的棋子数。4.4 迭代加深没有正确复用上一层结果现象迭代加深跑了很多层但每层搜索的走法顺序都是乱的剪枝效果差。原因没有把上一层的最优走法提到下一层候选列表的最前面。解决在search_root里记录上一层的最佳走法下一层排序时把它置顶。4.5 胜负判断遗漏导致搜索到已结束局面现象AI 在已经连五的局面下继续搜索返回无意义的分值。原因alpha_beta入口没有先判断胜负或者判断逻辑只检查了当前落子方。解决每次递归入口同时检查双方是否连五连五直接返回极大或极小值不再继续搜索。5. 进阶技巧让五子棋 AI 再强一截5.1 置换表用哈希缓存已搜索局面搜索过程中很多局面会重复出现只是到达顺序不同。置换表用 Zobrist 哈希把局面映射成一个整数缓存搜索过的深度和分值。命中缓存时直接返回省掉整棵子树的搜索。import random # 预生成 Zobrist 随机数表 ZOBRIST [[[random.getrandbits(64) for _ in range(2)] for _ in range(BOARD_SIZE)] for _ in range(BOARD_SIZE)] def zobrist_hash(board): h 0 for x in range(board.size): for y in range(board.size): if board.grid[x][y] ! 0: h ^ ZOBRIST[x][y][board.grid[x][y] - 1] return h transposition_table {} def alpha_beta_with_tt(board, depth, alpha, beta, maximizing, player): key zobrist_hash(board) if key in transposition_table: cached_depth, cached_val transposition_table[key] if cached_depth depth: return cached_val # ... 原有搜索逻辑 ... # 搜索完成后写入缓存 transposition_table[key] (depth, result) return result置换表要注意深度匹配只有缓存深度大于等于当前需求深度时才能直接用否则只能作为走法排序的参考。表太大会吃内存一般限制在几十万条以内满了就清空或者替换。5.2 算杀模块优先检查一步必胜和一步必防搜索再深也不如直接算杀来得快。在正常搜索之前先做一轮快速扫描如果己方有一步连五直接下如果对方有一步连五直接堵如果己方有活四或双冲四优先考虑。这个模块能大幅减少无谓的深层搜索也能避免 AI 在必胜局面下因为搜索深度不够而错过杀棋。def find_winning_move(board, player): 检查是否存在一步连五的走法 for x, y in generate_moves(board): board.place(x, y, player) if check_win(board, player): board.undo() return (x, y) board.undo() return None def find_blocking_move(board, player): 检查对手是否有一步连五需要堵 return find_winning_move(board, 3 - player)在iterative_deepening入口先调用这两个函数命中就直接返回省掉整轮搜索。这个技巧在实战里非常实用尤其是快棋场景。5.3 参数调优深度、时间、候选半径怎么配参数建议值说明搜索深度6 到 10配合迭代加深动态调整时间限制1 到 3 秒交互式对弈的舒适区间候选半径2取 1 漏防取 3 太慢置换表大小10 万到 50 万条视内存而定评估函数权重活四 冲四 ≈ 活三按棋型威胁程度排序调参没有万能公式我的习惯是先固定深度跑一批对局看 AI 在哪类局面上失误最多再针对性调整评估函数权重。比如发现 AI 经常漏防活三就把活三的分值调高发现 AI 过于保守就把进攻棋型的分值调高。5.4 一个我常用的验证方法改完搜索或评估逻辑后不要只跑一两局就下结论。我一般会写一个自动对弈脚本让新旧两个版本各执先手跑 20 局统计胜率和平均每步耗时。如果新版胜率没有明显提升或者耗时暴涨就说明改动有问题。这个习惯帮我省了很多「感觉变强了但其实没有」的后悔药。def self_play(ai1, ai2, games20): 自动对弈统计胜率 wins {1: 0, 2: 0} for i in range(games): board Board() player 1 if i % 2 0 else 2 while True: move ai1(board, player) if player 1 else ai2(board, player) if move is None: break board.place(move[0], move[1], player) if check_win(board, player): wins[player] 1 break player 3 - player return wins这套流程跑下来alpha-beta 五子棋 AI 的棋力基本能到「普通玩家认真下也不容易赢」的水平。搜索算法本身不复杂难的是评估函数和参数调优这些需要反复试的细节。希望帮到你。本文还有配套的精品资源点击获取