从零实现五子棋AI：极小化极大算法与Alpha-Beta剪枝实战

1. 项目概述：从零构建一个能打的五子棋AI

最近在整理自己的游戏项目时，重新审视了一个用纯JavaScript写的五子棋AI。这个项目麻雀虽小，五脏俱全，它没有依赖任何外部库，却实现了一个在标准15x15棋盘上颇具挑战性的对手。核心思路很经典：极小化极大算法搭配Alpha-Beta剪枝，再结合一个精心设计的模式评估函数。听起来像是教科书内容？但真正让它从“玩具”变成“对手”的，是几个关键的工程优化：将搜索范围限制在已有棋子的周围，以及一个高效的胜利检测算法。正是这些细节，让深度为4的搜索（在开局阶段通常只评估几千个局面而非数十亿）能在浏览器中实时运行，做出既进攻犀利又防守稳健的决策。如果你对算法如何落地到具体游戏、如何权衡性能与智能感兴趣，这个项目是个很好的切片。接下来，我会拆解它的每一个核心模块，分享在实现过程中“踩过的坑”和“悟出的道”。

2. 核心算法与评估体系设计

2.1 为什么是极小化极大与Alpha-Beta剪枝？

五子棋的规则极简，但博弈树却庞大得可怕。一个15x15的棋盘有225个空位，假设平均每步有50个合理着法（实际开局更多），那么仅仅向前看4步（4层深度），朴素地遍历所有可能局面，数量级是50^4，也就是数百万到数千万。这对于浏览器端的JavaScript来说是不可承受之重。

因此，极小化极大算法成为了基础框架。其思想是模拟双方都是绝对理性的对手：我方（最大化玩家）总是选择对自己评估分数最高的走法，而对方（最小化玩家）总是选择对我方评估分数最低（即对他最有利）的走法。通过递归，我们可以从叶子节点（达到搜索深度或终局）倒推回来，得到当前局面下对于我方而言的“最优”走法。

但光有极小化极大还不够，它依然需要遍历大量无用分支。Alpha-Beta剪枝是它的“加速器”。它引入了两个值：alpha代表我方至少能保证得到的最好分数，beta代表对方至少能保证我方得到的最差分数。在搜索过程中，如果发现某个分支的结果对于当前玩家来说已经不可能比已知的最佳选择更好（即出现beta <= alpha的情况），那么就可以果断“剪掉”这个分支及其所有子节点，不再继续搜索。剪枝的效率极度依赖于着法顺序——如果能优先搜索那些看起来最有希望的走法（比如能形成活三或冲四的棋），就能更早地触发剪枝条件，从而大幅提升搜索速度。在我的实现中，通过评估函数对候选着法进行预排序，显著提升了剪枝效率。

2.2 模式评估函数：AI的“棋感”

评估函数是AI的“眼睛”和“大脑”，它负责给任何一个非终局局面打一个分数，分数越高对我方越有利。一个糟糕的评估函数会让搜索算法在错误的道路上狂奔，而一个好的评估函数则能赋予AI真正的“棋感”。

我采用的是一种基于棋形模式的评估方法。核心是扫描棋盘上的每一行、每一列和两条对角线，识别出连续的同色棋子串（我们称之为“模式”），并根据其长度和“开放性”来赋分。

开放性的定义至关重要：它指的是这个连续棋子串的两端是否都是空位。一个两端都空的“活二”远比一端被堵死的“死二”有潜力。具体的评分表我经过多次对弈调试，大致如下：

注意：这里“活三”的分数（1000）与“冲四”相同，是基于五子棋的实战逻辑。一个真正的“活三”（两头都不被堵）意味着下一手棋可以形成一个“活四”，而“活四”是必胜的。因此，在实战中，应对对方的“活三”是迫在眉睫的防守要点，其威胁等级与“冲四”相当。

整个棋盘的最终得分并不是简单地将所有我方棋形分数相加。我采用了一个带有轻微防守倾向的加权差分：最终分数 = 我方所有模式总分 - 对方所有模式总分 * 1.1。这个1.1的系数是一个经验值，意味着AI会稍微高估对手的威胁。这样做的目的是防止AI过于激进地构建自己的进攻，而忽略了对手正在形成的致命攻击。在实际对弈中，这使AI的走法显得更加均衡和稳健。

2.3 关键性能优化：移动生成限制

这是让深度搜索变得可行的最关键优化，没有之一。在棋盘空旷的开局，一个新手AI可能会傻傻地评估225个空位。但稍微想一下就知道，在正常棋局中，有价值的落子点一定是在已有棋子周围的，不可能突然跑到一个孤零零的角落去下一子。

因此，我实现了getNearbyCells函数。它的逻辑是：遍历所有空位，检查以该空位为中心、半径为R（通常设为2）的矩形区域内，是否存在任何棋子（无论是己方还是对方的）。如果存在，则认为这个空位是“邻近”现有战场的，纳入候选着法列表；否则，直接忽略。

这个简单的策略将搜索的广度从O(N²)（N为棋盘边长）降低到了O(K)，其中K只与棋盘上已落子的数量和分布有关。在开局几步之后，候选点通常只有20-40个，相比225个全盘搜索，分支因子降低了近一个数量级。这使得搜索深度得以从2层提升到4层，AI的棋力产生了质的飞跃。

实操心得：半径R的选择是个权衡。R=1可能过于局限，AI可能会忽略一些稍远但关键的连接点。R=2在实践中被证明是一个甜点，它能覆盖绝大多数战术可能性。你也可以考虑动态半径，在棋子密集的区域减小半径，在稀疏区域增大半径，但这会引入额外的计算开销。对于这个项目，固定的R=2在性能和棋力之间取得了很好的平衡。

3. 工程实现与代码拆解

3.1 棋盘表示与游戏状态管理

我选择使用一个二维数组来表示棋盘，例如let board = new Array(15).fill(0).map(() => new Array(15).fill(0));。用0表示空，1表示黑棋，-1表示白棋（或反之）。这种表示法直观，且访问任意位置状态的时间复杂度是O(1)。

游戏状态管理除了棋盘数组，还需要记录当前轮到哪方下子、历史着法（用于悔棋）、以及最后一步落子的位置（用于高亮和高效获胜判定）。将这些状态集中在一个对象里管理，有利于保持代码的清晰度和可测试性。

class GomokuGame { constructor(size = 15) { this.size = size; this.board = this.createEmptyBoard(); this.currentPlayer = 1; // 1 for black, -1 for white this.gameOver = false; this.winner = null; this.moveHistory = []; // 记录每一步的 [row, col, player] this.lastMove = null; // [row, col] } createEmptyBoard() { return Array.from({ length: this.size }, () => new Array(this.size).fill(0)); } makeMove(row, col) { if (this.gameOver || this.board[row][col] !== 0) { return false; // 非法着法 } this.board[row][col] = this.currentPlayer; this.lastMove = [row, col]; this.moveHistory.push([row, col, this.currentPlayer]); if (this.checkWin(row, col)) { this.gameOver = true; this.winner = this.currentPlayer; } else if (this.isBoardFull()) { this.gameOver = true; // 平局 } else { this.currentPlayer *= -1; // 切换玩家 } return true; } }

3.2 高效获胜检测算法

在每次落子后都需要检查是否获胜。最笨的方法是每次扫描整个棋盘，检查所有可能的五连珠，复杂度是O(N²)且常数很大。但我们可以做得更好：既然只有最新的一步棋可能改变胜负，那么只检查这一步棋相关的连线就足够了。

checkWin函数以最后落子点(row, col)为中心，沿着四个方向（水平、垂直、主对角线、副对角线）分别向两边延伸计数。

function checkWin(board, row, col, player) { const directions = [ [0, 1], // 水平向右 [1, 0], // 垂直向下 [1, 1], // 主对角线右下 [1, -1] // 副对角线左下 ]; for (const [dr, dc] of directions) { let count = 1; // 当前位置已经有一颗棋子 // 向正方向延伸计数 let r = row + dr; let c = col + dc; while (r >= 0 && r < board.length && c >= 0 && c < board[0].length && board[r][c] === player) { count++; r += dr; c += dc; } // 向负方向延伸计数 r = row - dr; c = col - dc; while (r >= 0 && r < board.length && c >= 0 && c < board[0].length && board[r][c] === player) { count++; r -= dr; c -= dc; } if (count >= 5) { return true; } } return false; }

这个算法的复杂度是O(1)，因为每个方向最多检查4个格子（因为要形成五连，从中心点向一边最多延伸4格）。这是一个巨大的性能提升，尤其是在频繁调用的时候。

3.3 极小化极大与Alpha-Beta剪枝的核心实现

这是AI的“大脑”。函数minimax是一个递归函数，它接收当前棋盘、搜索深度、当前是最大化还是最小化玩家、当前玩家标识以及alpha、beta值。

function minimax(board, depth, isMaximizing, currentPlayer, alpha, beta) { // 终止条件：达到深度或游戏结束 if (depth === 0 || isTerminal(board)) { return evaluateBoard(board, currentPlayer); // 评估函数 } // 生成候选着法：只考虑已有棋子周围的点 const moves = getNearbyCells(board, 2); // 对着法进行排序：好的着法先搜索，能提高剪枝效率 moves.sort((a, b) => { // 简单启发式：靠近棋盘中心或能形成更高分模式的点优先 // 这里可以预评估一下，但为了性能，我有时仅按简单规则排序，有时不排序 return 0; }); if (isMaximizing) { let maxEval = -Infinity; for (const [row, col] of moves) { // 模拟落子 board[row][col] = currentPlayer; const evaluation = minimax(board, depth - 1, false, currentPlayer, alpha, beta); // 撤销落子（回溯） board[row][col] = 0; maxEval = Math.max(maxEval, evaluation); alpha = Math.max(alpha, evaluation); if (beta <= alpha) { break; // Beta剪枝 } } return maxEval; } else { let minEval = Infinity; for (const [row, col] of moves) { board[row][col] = -currentPlayer; // 对手落子 const evaluation = minimax(board, depth - 1, true, currentPlayer, alpha, beta); board[row][col] = 0; minEval = Math.min(minEval, evaluation); beta = Math.min(beta, evaluation); if (beta <= alpha) { break; // Alpha剪枝 } } return minEval; } }

在实际调用时，我们遍历所有候选着法，为每一个着法调用minimax，并记录返回的评估值。选择评估值最高的着法作为AI的决策。为了获得最佳着法，外层需要稍作修改，不仅返回分数，也返回对应的着法坐标。

注意事项：递归函数中的棋盘状态修改必须使用“回溯”法，即在递归调用前修改棋盘，调用后立即恢复。直接传递棋盘的深拷贝（如JSON.parse(JSON.stringify(board))）在JavaScript中虽然安全，但会带来巨大的内存和性能开销，在深度搜索中不可行。因此，“修改-递归-恢复”是标准做法。

4. 深度优化与实战调试经验

4.1 迭代加深与超时控制

即使有了剪枝和移动限制，深度为4的搜索在某些复杂中盘局面下也可能耗时超过1秒，影响用户体验。一个实用的技巧是迭代加深。我们不直接进行深度为4的搜索，而是先进行深度为1的搜索，然后深度2，深度3，最后深度4。这样做有两个好处：

1. 时间控制：我们可以在每次深度增加后检查是否超时。如果超时，就返回上一次深度（如深度3）的最佳结果。这样能保证AI总是在有限时间内做出反应，避免“卡死”。
2. 着法排序：浅层搜索的结果（最佳着法）可以为更深层的搜索提供极好的着法排序参考，从而显著提升Alpha-Beta剪枝的效率。

在JavaScript中，我们可以用Promise.race和setTimeout来实现一个简单的超时控制：

async function findBestMoveWithTimeout(board, player, maxDepth, timeLimit = 3000) { let bestMove = null; let bestScore = -Infinity; for (let currentDepth = 1; currentDepth <= maxDepth; currentDepth++) { const searchPromise = new Promise(resolve => { // 在一个Web Worker或setImmediate/timeout中执行搜索，避免阻塞UI setTimeout(() => { const [score, move] = iterativeDeepeningSearch(board, player, currentDepth); if (move) { bestMove = move; bestScore = score; } resolve(); }, 0); }); const timeoutPromise = new Promise((_, reject) => setTimeout(() => reject(new Error('Timeout')), timeLimit) ); try { await Promise.race([searchPromise, timeoutPromise]); } catch (error) { if (error.message === 'Timeout') { console.log(`搜索深度 ${currentDepth} 超时，使用深度 ${currentDepth-1} 的结果`); break; // 跳出循环，使用上一次深度的结果 } } } return bestMove; }

4.2 评估函数的精细化调优

评估函数是AI的“灵魂”，它的调优是一个经验性的过程。除了之前提到的模式分数，还有几个方面可以优化：

1. 位置权重：棋盘中心的位置通常比边角更有价值。可以在计算模式分数后，乘以一个基于位置的基础权重矩阵。例如，中心点权重为1.2，边角点权重为0.8。这能引导AI在开局阶段向中心发展，抢占有利地形。
2. 模式组合的奖励：有时两个独立的“活二”可能不如一个“活三”，但两个形成“跳活三”或构成某种进攻形状的“活二”可能威力更大。评估函数可以加入对特定组合模式的识别和额外加分，但这会大大增加复杂性。
3. 防守紧迫度计算：当前的评估是静态的。可以加入一个动态因子：如果检测到对手有“活三”或“冲四”，则大幅提高我方在防守点附近落子的评估分数，甚至临时增加搜索深度来穷尽防守变化。这能让AI的防守显得更加“敏锐”。

在我的实现中，我主要采用了静态模式评估加轻微防守加权（乘以1.1），并在多次与自己对弈后微调了分数表。例如，最初“活三”的分数设得较低，导致AI经常忽略防守对方的活三，调整后防守意识明显增强。

4.3 不同难度级别的实现

项目提供了三个难度级别，这主要是通过控制搜索深度来实现的：

• 简单 (Easy)：深度为1。AI只看一步，选择当前评估分数最高的着法。棋力很弱，相当于只懂基本棋形的玩家。
• 中等 (Medium)：深度为2。AI能看到自己走一步、对方走一步后的局面。棋力尚可，能完成基本的进攻和防守。
• 困难 (Hard)：深度为4。AI能看到两步之后的局面（我方-对方-我方-对方）。这是性能允许下的一个平衡点，能进行一些简单的战术组合和陷阱识别，对业余玩家构成足够挑战。

实操心得：设置难度不仅仅是改个深度参数。对于“简单”难度，甚至可以完全禁用搜索，只使用一个贪婪的评估函数（即选择立即能带来最高分数提升的着法），这样反应速度极快，且棋力符合预期。对于“困难”难度，可以结合迭代加深和更精细的着法排序。让用户感受到不同难度级别之间清晰的棋力梯度，是提升游戏体验的关键。

5. 常见问题、调试技巧与性能瓶颈

5.1 AI反应慢或卡顿

这是最常见的问题。排查步骤如下：

1. 检查搜索深度：首先确认当前设置的搜索深度。在15x15棋盘上，深度超过4（特别是开局）很可能导致性能问题。可以通过控制台打印每步搜索评估的节点数来监控。
2. 验证移动生成限制：在搜索函数开头打印getNearbyCells返回的候选点数量。如果开局第一步就返回了上百个点，那么你的限制函数可能有问题（比如半径设得太大，或者逻辑错误）。正常开局几步后应在20-50个点左右。
3. 分析评估函数性能：evaluateBoard函数会被调用数百万次。确保它尽可能高效。避免在评估函数内部进行动态内存分配（如创建新数组），尽量使用预分配的变量和循环。如果模式扫描是性能热点，可以考虑使用增量更新（只评估因最新一步棋而改变的那些行和列），但这会极大增加代码复杂度。
4. 使用性能分析工具：使用浏览器开发者工具的Performance面板录制一段时间内的操作，查看火焰图，找到最耗时的函数调用。很可能是minimax或evaluateBoard。

5.2 AI看似“很傻”，走明显坏棋

1. 评估函数缺陷：这是最可能的原因。检查你的模式识别是否正确，特别是“开放性”的判断。一个常见的错误是把“被己方棋子挡住一端”的模式错误地判断为更开放。使用一个调试界面，在AI思考后打印出它对前几个候选着法的评估分数，看是否与你的棋感相符。
2. 搜索深度不足：有些坏棋是“短视”的结果。AI可能看到了眼前能形成一个“活三”，但没有看到对方下一步可以形成“冲四”反杀。尝试增加搜索深度，看问题是否改善。如果因性能无法增加深度，可以考虑在评估函数中加入一些“前瞻性”的惩罚项，例如对给对方留下“活三”机会的着法扣分。
3. Alpha-Beta剪枝错误：如果剪枝逻辑有bug，可能会导致AI剪掉了本应搜索的最佳分支。确保你的alpha和beta值在递归调用中正确传递和更新。一个简单的调试方法是暂时禁用剪枝（注释掉if (beta <= alpha) break;），如果AI棋力变强了，那剪枝逻辑很可能有问题。

5.3 平局或胜负判断异常

1. 获胜检测逻辑错误：重点检查checkWin函数。编写单元测试，覆盖各种获胜情况：水平五连、垂直五连、两种对角线五连、以及从不同位置开始的五连。确保边界情况（例如棋子落在棋盘边缘）也能正确检测。
2. 棋盘满员平局逻辑：isBoardFull函数应遍历整个棋盘。确保它只在游戏未分胜负时被调用。
3. 游戏状态同步：确保gameOver和winner状态变量在checkWin返回true时被正确设置，并且在重置游戏时被正确清零。

5.4 性能优化速查表

关于Web Worker的提示：这是将复杂计算移出主线程、保证页面流畅响应的标准做法。你可以将整个minimax搜索函数、棋盘状态等打包成一个消息发送给Worker。Worker计算完成后，将最佳着法坐标发回主线程。这样，即使在AI“深思”时，用户界面依然可以响应（如显示思考动画）。这是生产级游戏AI的必备优化。

实现这个五子棋AI的过程，是一个将经典算法理论转化为实际可运行代码的典型缩影。它让我再次体会到，在软件工程中，“正确的算法”和“高效的实现”之间，往往隔着无数个细节的优化。从数亿个不可能的局面，通过移动限制和剪枝优化到几千个可评估的局面；从一个静态死板的评估，通过分数微调和防守加权变成一个有点“意识”的对手——每一步优化都带来了肉眼可见的棋力提升。最后，将所有这些封装成一个无依赖、可交互的网页应用，看到它能在浏览器里流畅运行并与我对弈，这种成就感是纯粹的。如果你也想深入理解博弈树搜索，亲手实现一个会下棋的AI，五子棋是一个近乎完美的起点。它的规则简单到足以让你专注于算法本身，而它的策略深度又足以让优化充满挑战和乐趣。