ARTICLE DETAIL

资讯详情

深耕编程入门与网站建设的一线实战洞察。

从棋盘表示到α-β剪枝:打造浏览器端的中国象棋AI引擎

从棋盘表示到α-β剪枝:打造浏览器端的中国象棋AI引擎 简介中国象棋AI人工智能网页版是一套可直接运行的前端AI对弈项目面向算法学习者、前端开发者和人工智能入门者帮助理解博弈树、极大极小值搜索及α-β剪枝算法在实际游戏中的落地方式。整个压缩包共44个文件包含1个HTML入口页面、5个JavaScript脚本、1个CSS样式表、34个PNG棋子和界面素材以及2个JPG图片和1个MD说明文档文件类型覆盖页面结构、交互逻辑、视觉表现与使用说明结构清晰便于按模块阅读。资源包整体仅507KB轻量无依赖打开HTML即可对战体验。该资源已有20596人学习浏览深受开发者关注。通过阅读源码和实际操作读者可以直观看到AI每一步决策背后的搜索流程学习如何用极大极小值评估局面、如何通过α-β剪枝减少无效分支并掌握将AI算法封装进浏览器端的基本方法适合课程设计、毕业设计或算法实验参考。1. 中国象棋 AI 网页版浏览器里能不能跑出人类棋力在地址栏打开一个 HTML 页面点击“开始”棋盘里的中国象棋 AI 随即走子——听起来像个 Demo但它要在一秒内完成 4 到 6 层搜索树的完整攻防计算。中国象棋 AI 网页版的难点不在画棋盘而在 90 个格子的状态表达、着法生成速度和 α-β 剪枝的组织方式。如果这些环节没设计好AI 的每一步都会让页面长时间卡死。我见过不少团队把引擎拆成后端接口前端每走一步就发一次请求把网页版做成远程调用的壳子。网页版象棋 AI 的真正优势恰恰是本地化搜索逻辑用 JavaScript 写在 Worker 里不走网络延迟只取决于浏览器即时编译的执行效率。V8 处理整数循环和位运算的能力足够支撑 6 层左右的实战搜索棋力上限比很多人想象的高。这篇文章面向想从零搭一版“能玩、能调试、棋力不丢人”的网页版象棋 AI 的开发者。你会看到棋盘表示选型、着法生成代码、搜索参数、评估函数标定以及浏览器集成的完整路径每一步都给出可以直接运行的代码和参数。不需要再去对接闭源引擎接口也不需要把搜索放回服务器。2. 棋盘建模与着法生成中国象棋 AI 网页版的决策引擎底座2.1 棋盘表示选型一维数组、0x88 还是 bitboard做中国象棋 AI 网页版第一步不是写搜索而是选棋盘表示。常见的有三种90 格一维数组、0x88 二维数组、bitboard。它们的取舍直接决定后续着法生成和评估函数的写法。方案存储开销越界判断方式开发效率适合场景90 格一维数组90 字节行列换算后判断 0~8、0~9最高快速原型、网页版主体逻辑0x88 二维数组16x16256 字节坐标异或高位快速检查中搜索性能敏感需要极致剪枝bitboard90 bit 一正一负位运算并行低残局库、深度搜索、杀法演算我的建议是网页版优先用 90 格一维数组。理由很直接着法生成时你仍然要写“从坐标走到目标坐标”的循环一维数组配合idx(col, row)换算可读性远好于 0x88 的位运算而两者的边界检查成本差异在 6 层搜索内几乎可以忽略。先跑通棋力再谈位运算优化这是网页版项目最稳的节奏。const BOARD_W 9; const BOARD_H 10; const EMPTY 0; // 红方用正数黑方用负数 const RED_KING 1, RED_ROOK 2, RED_KNIGHT 3; const RED_CANNON 4, RED_BISHOP 5, RED_ADVISOR 6, RED_PAWN 7; const BLACK_KING -1, BLACK_ROOK -2, BLACK_KNIGHT -3; const BLACK_CANNON -4, BLACK_BISHOP -5, BLACK_ADVISOR -6, BLACK_PAWN -7; function idx(col, row) { return row * BOARD_W col; } function inBoard(col, row) { return col 0 col BOARD_W row 0 row BOARD_H; } function createBoard() { return [ 2, 3, 5, 6, 1, 6, 5, 3, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 4, 0, 7, 0, 7, 0, 7, 0, 7, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -7, 0, -7, 0, -7, 0, -7, 0, -7, 0, -4, 0, 0, 0, 0, 0, -4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, -3, -5, -6, -1, -6, -5, -3, -2 ]; }createBoard里行 0 对应红方底线行 9 对应黑方底线。这样红方向前是行号加一黑方向前是行号减一搜索时只需要拿side乘以一个前进方向常量即可。数组里的 0 表示空位负数表示黑方棋子Math.sign(piece)可以快速判断棋子属于哪一方。2.2 着法生成的最小可运行代码着法生成是所有搜索的基础。它要做的事很单纯给定棋盘和走棋方返回所有“可能合法”的着法列表。注意这里说的是“可能合法”因为真正的合法性还需要包含“不能送将”的检查这一步放到makeMove里统一处理更合理。function genMoves(board, side) { const moves []; for (let r 0; r BOARD_H; r) { for (let c 0; c BOARD_W; c) { const p board[idx(c, r)]; if (p EMPTY || Math.sign(p) ! Math.sign(side)) continue; const type Math.abs(p); if (type RED_ROOK) genRookMoves(board, c, r, side, moves); else if (type RED_KNIGHT) genKnightMoves(board, c, r, side, moves); else if (type RED_CANNON) genCannonMoves(board, c, r, side, moves); else if (type RED_PAWN) genPawnMoves(board, c, r, side, moves); else if (type RED_KING) genKingMoves(board, c, r, side, moves); else if (type RED_BISHOP) genBishopMoves(board, c, r, side, moves); else if (type RED_ADVISOR) genAdvisorMoves(board, c, r, side, moves); } } return moves; }车和炮的走法都沿四个方向滑动但吃子规则不同。车最简单遇空位加入着法遇对手棋子吃下并停止遇自己棋子停止。炮的区别在于“跳炮架”移动时不能吃子吃子时必须先隔一个棋子。const ROOK_DIRS [[1,0],[-1,0],[0,1],[0,-1]]; function genRookMoves(board, c, r, side, moves) { for (const [dc, dr] of ROOK_DIRS) { let nc c dc, nr r dr; while (inBoard(nc, nr)) { const target board[idx(nc, nr)]; if (target EMPTY) { moves.push([c, r, nc, nr]); } else { if (Math.sign(target) ! Math.sign(side)) moves.push([c, r, nc, nr]); break; } nc dc; nr dr; } } } function genCannonMoves(board, c, r, side, moves) { for (const [dc, dr] of ROOK_DIRS) { let nc c dc, nr r dr; let jumped false; while (inBoard(nc, nr)) { const target board[idx(nc, nr)]; if (!jumped) { if (target EMPTY) { moves.push([c, r, nc, nr]); } else { jumped true; // 第一个炮架跳过它 } } else { if (target ! EMPTY) { if (Math.sign(target) ! Math.sign(side)) { moves.push([c, r, nc, nr]); // 吃子 } break; // 无论能不能吃这里都停止 } } nc dc; nr dr; } } }炮的代码里jumped是一个状态开关false 时只记录空位移遇到第一个非空子后置为 truetrue 之后不再记录空位只找吃子目标。这个“先找炮架再找靶”的顺序是关键漏掉break会导致炮穿过多个棋子走子。马需要处理蹩马腿。我给每个方向配了一个“腿”的偏移走 2 格之前先判断腿的位置是否为空。const KNIGHT_LEGS [ [1, 2, 0, 1], [-1, 2, 0, 1], [1, -2, 0, -1], [-1, -2, 0, -1], [2, 1, 1, 0], [2, -1, 1, 0], [-2, 1, -1, 0], [-2, -1, -1, 0] ]; function genKnightMoves(board, c, r, side, moves) { for (const [dc, dr, lc, lr] of KNIGHT_LEGS) { const nc c dc, nr r dr; if (!inBoard(nc, nr)) continue; if (board[idx(c lc, r lr)] ! EMPTY) continue; // 蹩马腿 const target board[idx(nc, nr)]; if (target EMPTY || Math.sign(target) ! Math.sign(side)) { moves.push([c, r, nc, nr]); } } }兵和帅、士、象的规则与边界相关。兵的要点是过河后可以横走过河前只能前进且永远不能后退。红兵从行 0 出发向前过河的判断是r 5黑兵则是r 4。function genPawnMoves(board, c, r, side, moves) { const dir side 0 ? 1 : -1; const crossed side 0 ? r 5 : r 4; const targets [[c, r dir]]; if (crossed) { targets.push([c - 1, r], [c 1, r]); } for (const [tc, tr] of targets) { if (!inBoard(tc, tr)) continue; const target board[idx(tc, tr)]; if (target EMPTY || Math.sign(target) ! Math.sign(side)) { moves.push([c, r, tc, tr]); } } }帅和士的九宫限制以及象的田字眼位本质上都是“落点区域判断”。帅只能落在列 3~5 且红方行 0~2、黑方行 7~9 的范围内士同理象则额外要求象眼位置为空。把这些判断封装成inPalace和inOwnSide两个函数代码量不会超过二十行但能显著减少搜索时生成的无效着法。2.3 走子合法性别让将帅照面着法生成器给出的着法里有一些是规则上不允许的走完后己方的帅被对方吃掉或者红帅黑将在同一列直接照面。网页版引擎里最常见的处理方式是在makeMove执行后立即检查“己方是否仍被将军”。function isInCheck(board, side) { const opponent -side; const myKing side 0 ? RED_KING : BLACK_KING; let kr -1, kc -1; for (let r 0; r BOARD_H; r) { for (let c 0; c BOARD_W; c) { if (board[idx(c, r)] myKing) { kr r; kc c; } } } if (kr 0) return true; // 王被吃了 return genMoves(board, opponent).some(([, , tc, tr]) tc kc tr kr); } function makeMove(board, move) { const [fc, fr, tc, tr] move; const moving board[idx(fc, fr)]; const captured board[idx(tc, tr)]; board[idx(tc, tr)] moving; board[idx(fc, fr)] EMPTY; if (isInCheck(board, Math.sign(moving))) { board[idx(fc, fr)] moving; board[idx(tc, tr)] captured; return false; // 送将非法 } return true; }isInCheck的实现是反向扫描生成对方所有着法看是否包含己方帅的坐标。它会重复调用genMoves在深层搜索中会带来一定开销但作为第一版引擎完全够用。后续可以改成“从帅的位置向外攻击”用八个方向的攻击射线代替整表生成性能会有明显提升。注意makeMove返回 false 时调用方必须忽略这个着法。搜索循环里最常见的 bug 就是忘记检查返回值导致引擎走出送将着法。3. 搜索核心在网页版中国象棋 AI 里调好 α-β 剪枝3.1 为什么网页版优先选 α-β 剪枝而不是 MCTS中国象棋 AI 网页版的棋力来源本质是搜索树的展开效率。主流的搜索框架有三种α-β 剪枝、蒙特卡洛树搜索MCTS、基于神经网络的策略价值网络。三者的选择并不是越先进越好而是看你的运行环境和调参成本。方法单步耗时棋力上限调参成本浏览器端适配度α-β 剪枝 迭代加深毫秒到秒级高深度决定上限低调深度和排序高纯计算无外部依赖MCTS秒级起步中高依赖模拟次数中需要调 UCB 常数中大量随机模拟吃 CPU神经网络推理快但训练慢上限最高极高需要训练数据和算力低浏览器推理受格式限制网页版的约束很明确用户不会等十秒AI 必须在 1~3 秒内落子。α-β 剪枝配合良好的着法排序在 5~6 层深度下已经能走出像样的中局招法而且不需要任何训练数据。MCTS 在象棋这类高分支因子的棋种里存在明显的“宽而不深”问题除非配合策略网络引导否则棋力很难超过 α-β。3.2 负极大值实现与迭代加深搜索代码采用负极大值形式这是 α-β 剪枝最常见的写法。评估函数返回当前走棋方的优势分调用时通过取负实现双方的对称搜索。核心代码只有二十行左右但它决定了引擎的几乎全部强度。function alphaBeta(board, depth, alpha, beta, side) { if (depth 0) return evaluate(board, side); const moves genMoves(board, side) .filter((mv) makeMove(board, mv)) // 过滤送将着法 .map((mv) { const score evaluate(board, -side); // 下次序优先评估 undoMove(board, mv); return { mv, score }; }) .sort((a, b) b.score - a.score) // 直觉排序剪枝更高效 .map((item) item.mv); if (moves.length 0) { return isInCheck(board, side) ? -100000 depth : 0; // 将死或困毙 } let best -Infinity; for (const mv of moves) { makeMove(board, mv); const score -alphaBeta(board, depth - 1, -beta, -alpha, -side); undoMove(board, mv); if (score best) best score; if (score alpha) alpha score; if (alpha beta) break; // 剪掉这个分支 } return best; }这段代码里有几个必须注意的细节。第一filter(makeMove)在进入递归前就排除了送将着法避免后续无效展开。第二着法排序用当前的局面静态评估分这个分不需要精确只要能保证“好棋排在前面”剪枝效率就会大幅提升。第三将死返回-100000 depth而不是固定值是让引擎在同样能将死的情况下优先选择更快的杀法。迭代加深是网页版的必选项。它的思路是先搜深度 1再搜深度 2直到时间耗尽或达到设定深度。每一层都可以复用上一层的着法顺序而且能在任意时刻返回当前最优着法让用户感觉 AI 是“连续思考”而不是“卡住算完”。function searchRoot(board, side, maxDepth, timeBudgetMs) { const startTime Date.now(); let bestMove null; // 第一轮先用吃子着法排序之后每轮用上一轮的结果 for (let depth 1; depth maxDepth; depth) { const moves genMoves(board, side) .filter((mv) makeMove(board, mv)); if (moves.length 0) return null; const ordered moves .map((mv) { const score evaluate(board, -side); undoMove(board, mv); return { mv, score }; }) .sort((a, b) b.score - a.score) .map((item) item.mv); let localBest null; let localScore -Infinity; const alpha -Infinity, beta Infinity; for (const mv of ordered) { makeMove(board, mv); const score -alphaBeta(board, depth - 1, -beta, -alpha, -side); undoMove(board, mv); if (score localScore) { localScore score; localBest mv; } if (Date.now() - startTime timeBudgetMs) { return bestMove || localBest; // 超时立即返回保证交互 } } bestMove localBest; } return bestMove; }searchRoot的返回值是[fromCol, fromRow, toCol, toRow]格式的着法。主线程拿到它之后直接更新棋盘、播放走子动画即可。3.3 三个必调参数深度、时间预算、着法排序α-β 剪枝的参数直接影响网页版的用户体验。我常用的默认值如下参数典型值影响调整建议maxDepth5深度每加 1耗时约翻 3~5 倍桌面端 6移动端 4~5timeBudgetMs1500超时即返回当前最优快棋 800挑战模式 3000着法排序策略吃子优先 上轮最佳剪枝率差别巨大必须做不做会慢十倍是否启用置换表否命中率越高搜索越快后续优化再加不影响首版注意迭代加深里的timeBudgetMs检查必须放在每一层循环里而不是只在层之间。放在最外层会让单层搜索超时失控页面卡死。着法排序里的“吃子优先”用 MVV-LVA最大价值吃最小价值子实现起来非常简单给每个被吃棋子一个分数比如车 600、炮 285、马 270低价值棋子吃高价值棋子排前面。不用完整实现先按静态评估排序即可获得约 70% 的收益。4. 评估函数标定把中国象棋 AI 网页版的棋力从“会走”提到“能攻能守”4.1 子力价值表开局残局要有梯度评估函数是搜索引擎之外的另一个棋力来源。它回答“这个局面红方领先多少分”搜索树靠这个分数决定走向。最基础也最有效的部分是子力价值表。棋子基础分值说明帅100000必须给极大值防止引擎白送帅车600进攻防守双重核心炮285开局价值高于马残局下降马270残局价值高于炮士120防守型弱子象120防守型弱子过河兵40过河后牵制力大增未过河兵20价值极低炮和马的分值设计有一个细节开局炮价值高于马残局反过来。首版引擎可以不做这么细直接沿用固定值也能跑出不错的效果但至少要区分“过河兵”和“未过河兵”。很多初版引擎棋力弱不是因为搜索深度不够而是兵过河后和没过河给同样的分AI 永远不推进兵。const PIECE_VALUE { [RED_KING]: 100000, [RED_ROOK]: 600, [RED_CANNON]: 285, [RED_KNIGHT]: 270, [RED_BISHOP]: 120, [RED_ADVISOR]: 120, [RED_PAWN]: 20 }; function evaluate(board, side) { let score 0; for (let r 0; r BOARD_H; r) { for (let c 0; c BOARD_W; c) { const p board[idx(c, r)]; if (p EMPTY) continue; const type Math.abs(p); let value PIECE_VALUE[type]; if (type RED_PAWN) { value r 5 ? 40 : 20; // 过河判断 } score Math.sign(p) * value; } } return side * score; // 从走棋方视角返回 }side传 1 或 -1side * score保证返回的是“当前走棋方领先多少分”。搜索核心里的负极大值写法依赖评估函数始终返回当前走棋方的视角分数。4.2 位置价值表马和兵最吃位置子力价值只能保证 AI 不白送子真正让棋力上一个台阶的是位置价值。位置表是一张 9x10 的二维表给每个棋子在其所在位置额外加减分。马在中心位置和中象位置的分值差异可以到 30 分以上。// 马的简易位置价值表红方视角行 0 为红方底线 const KNIGHT_POS [ [ 0, 0, 0, 0, 0, 0, 0, 0, 0], [ 2, 4, 8, 10, 10, 10, 8, 4, 2], [ 4, 8, 14, 20, 22, 20, 14, 8, 4], [ 6, 12, 22, 30, 34, 30, 22, 12, 6], [ 4, 10, 18, 26, 30, 26, 18, 10, 4], [ 2, 6, 12, 18, 20, 18, 12, 6, 2], [ 0, 2, 6, 10, 12, 10, 6, 2, 0], [ 0, 0, 2, 4, 6, 4, 2, 0, 0], [ 0, 0, 0, 2, 2, 2, 0, 0, 0], [ 0, 0, 0, 0, 0, 0, 0, 0, 0] ];黑方棋子读取位置表时要翻转行号posRow 9 - r否则黑马会被错误地鼓励往自己底线跑。兵的位置表规律性更强越靠近对方九宫越高在二三路斜线位置要加分在边路位置要扣分。这些表不需要用机器学习学历史上经典引擎已经给出过大量成熟数值直接抄来微调即可。4.3 机动性修正让士象和边马不踩空纯子力价值加位置表下出来的棋有个典型问题AI 有时会走“看似得分、实则堵死”的棋比如把炮走到边线、把士拱到无人区。机动性修正的思路很简单一个棋子当前能攻击的格子越多它的实际价值越高。function getPieceScore(board, c, r, side) { const type Math.abs(board[idx(c, r)]); let score PIECE_VALUE[type]; if (type RED_PAWN (side 0 ? r 5 : r 4)) { score 20; // 过河加成 } // 机动性统计该棋子一步能走到的格子数 const tempMoves []; if (type RED_KNIGHT) genKnightMoves(board, c, r, side, tempMoves); else if (type RED_CANNON) genCannonMoves(board, c, r, side, tempMoves); else if (type RED_ROOK) genRookMoves(board, c, r, side, tempMoves); score tempMoves.length * 2; // 每多一个可走格加 2 分 return score; }机动性加分不宜过高2 分一个格子已经足够引导马往中心走。如果加太多引擎会为了“自由度”走出没有实际威胁的闲棋。这个修正本质上是在模拟“子力活性”对一个不依赖大模型训练、纯靠搜索的网页版象棋 AI 来说是性价比极高的补齐方式。5. 网页版集成与验证把搜索搬进 Worker 并测出真实棋力5.1 Web Worker 跑搜索主线程只渲染搜索代码写好后不能直接在主线程里调用。JavaScript 主线程承担着 DOM 渲染和事件响应一旦搜索循环启动浏览器界面会完全冻结。标准做法是把引擎代码放进独立文件用 Web Worker 跑搜索主线程只负责接收结果和渲染棋盘。// worker.js importScripts(engine.js); self.onmessage (e) { const { board, side, maxDepth, timeBudgetMs } e.data; const bestMove searchRoot(board, side, maxDepth, timeBudgetMs); const moveScore bestMove ? evaluate(board, side) : 0; self.postMessage({ bestMove, moveScore }); };主线程里只需要创建 Worker 并维护一个简单的状态机用户点击棋盘后把当前棋盘数组发给 Worker同时把按钮置为“AI 思考中”收到回包后执行着法并恢复交互。const worker new Worker(worker.js); function requestAiMove(board, side) { aiThinking true; worker.postMessage({ board, side, maxDepth: 5, timeBudgetMs: 1500 }); } worker.onmessage (e) { const { bestMove } e.data; if (bestMove) { applyMove(bestMove); // 更新棋盘数据和 DOM switchTurn(); } aiThinking false; renderBoard(); };Worker 的线程模型下board数组通过结构化克隆传递。对 90 格的数组来说开销可以忽略不需要刻意用 transferable buffer。真正值得做的是在 Worker 内部缓存评估表不要每次都重建。5.2 用 FEN 快速验证引擎不吃废棋验证网页版象棋 AI 是否正常最可靠的方法是给一个已知局面检查引擎是否走出明显错误。中国象棋的 FEN 格式可以完整描述局面直接把它转换成棋盘数组。const FEN_MAP { r: -2, n: -3, b: -5, a: -6, k: -1, c: -4, p: -7, R: 2, N: 3, B: 5, A: 6, K: 1, C: 4, P: 7 }; function fenToBoard(fen) { const board new Array(90).fill(EMPTY); const rows fen.split( )[0].split(/); rows.forEach((row, r) { let c 0; for (const ch of row) { if (/\d/.test(ch)) { c Number(ch); } else { board[idx(c, r)] FEN_MAP[ch]; } } }); return board; } const INIT_FEN rnbakabnr/9/1c5c1/p1p1p1p1p/9/9/P1P1P1P1P/1C5C1/9/RNBAKABNR w - - 0 1;对照createBoard()的输出如果fenToBoard(INIT_FEN)和它逐格相等说明 FEN 解析和棋盘数组没有错位。之后可以用残局 FEN 做定向验证比如“双车错”杀局引擎两步内必须走出将杀的着法。5.3 上线前必测的三个局面最后一个具体技巧是自测清单。我每次改完引擎参数都会用三个固定局面跑一遍初始局面验证着法生成无崩溃单车对单士残局验证深度是否够用一将一闲局面验证引擎会不会循环送将。这三个局面覆盖了网页版引擎最常翻车的三类问题数组越界、深度不足导致错失杀棋、重复局面处理缺失。任一局面的最佳着法明显不合理优先检查评估函数的符号和makeMove的合法性判断而不是怀疑剪枝代码。确认基础走法正确后再把maxDepth从 5 调到 6实测单步耗时变化找到当前设备和浏览器条件下的性能边界这个数值就是正式版的默认参数。本文还有配套的精品资源点击获取
返回列表