简介一套基于 Java Swing 的象棋游戏源码利用极大极小值搜索算法实现人机对弈并配有完整的文档说明。适合正在准备课程设计、毕业设计的计算机专业学生也适合需要 Java 项目实战练习的开发者可有效解决 Java GUI 开发、博弈树搜索、棋局评估与代码架构设计等综合性问题。整个资源包共 150 个文件压缩后仅 3.03MB。其中 74 个 Java 源文件构成核心代码覆盖棋盘绘制、走法合法性判断、局面评估、AI 搜索等功能32 张 jpg 与 8 张 png 作为界面和棋子素材24 个 wav 提供落子、胜利等音效6 个 markdown 文档便于快速理解项目结构另有 xml、properties 等配置文件辅助程序运行。目前已有 242 人学习。拿到手即可直接运行体验人机对战同时通过源码和文档理解极大极小值算法及 Alpha-Beta 剪枝的实际应用也能在此基础之上二次开发用于课程作业、期末大作业或毕业设计演示。1. 一个 Java Swing 象棋游戏为什么值得你打开这份源码如果你正在找“基于 java swing 的象棋游戏源码(极大极小值搜索算法实现人机对弈)”这种项目多半不是单纯想下棋而是想搞明白一件事让电脑“会下棋”的那套搜索逻辑到底是怎么写出来的。这份源码的卖点恰恰不在 Swing 界面本身而在“极大极小值搜索算法”这几个字上——它是棋类 AI 最经典、最容易读懂、也最适合拿来当算法入门的一条路径。用 Java Swing 做前端只是让这套算法有了一个能看、能点、能跑起来的壳。它能解决你什么问题如果你在学数据结构与算法或者刚接触博弈类 AI直接啃框架源码容易迷失在工程细节里而这个项目把博弈树搜索、评估函数、走法生成、人机交互全部浓缩在一个可运行的游戏里。适合的人群很明确想理解 Minimax 和剪枝原理的在校学生、要做课程设计的开发者、以及准备用棋类 AI 做面试项目的从业者。我用类似的思路做过几个棋类 Demo可以负责任地说这个方向性价比极高——跑通它你就等于打通了棋类 AI 的一条完整链路。下面从棋盘模型开始一步步拆开这份源码最核心的部分。2. 先看懂棋盘和走法极大极小搜索的地基搜索算法的本质是“枚举所有可能的走法然后选一个最好的”。如果走法生成器写错了或者棋盘状态表示混乱那么再聪明的搜索算法也是白搭。所以看这份源码时第一件事不是去读搜索函数而是先看棋盘是怎么建模的、走法是怎么生成的。2.1 用一维数组表示棋局红黑双方的建模约定常见做法是用长度为 90 的字节数组表示十行九列的棋盘下标 0 到 89数组里存棋子类型和归属方。为什么不用二维数组因为一维数组在 Java 里读写更快而且下标可以直接用来判断棋盘边界避免每一层递归都做二维索引换算。源码或“红方走棋”代码通常长这样byte[] board new byte[90]; // 棋子编码约定0空1红帅2红仕3红相4红马5红车6红炮7红兵 // 黑方用负值-1黑将-2黑士-3黑象-4黑马-5黑车-6黑炮-7黑卒 // 例如红车放在左下角board[9 * 9 0] 5;这个编码方案的好处是判断棋子属于哪一方只需要看值大于 0 还是小于 0判断是否为空只需要看是否等于 0。拆包棋盘时注意两个细节。第一黑方的坐标是从对方视角看的行号 0 到 9 映射时要把方向倒过来否则会出现黑方棋子“倒着走”的玄学问题第二数组下标运算时必须把边界检查写进走法生成器而不是写进搜索循环因为搜索循环里每展开一个节点就要调一次走法生成多一次数组越界检查就是一次性能损耗。2.2 走法生成器给搜索树提供分支走法生成器是搜索算法的数据来源它的职责简单说就是给定一个棋盘状态和一个棋子位置算出所有合法落点。不同棋子的规则差异很大车的走法最直白马和相则有“腿”和“塞象眼”的约束。以车为例标准写法如下private void generateRookMoves(int from, ListInteger moves, byte[] board) { int row from / 9, col from % 9; int[][] dirs {{1,0},{-1,0},{0,1},{0,-1}}; for (int[] d : dirs) { int nr row d[0], nc col d[1]; while (nr 0 nr 10 nc 0 nc 9) { int dest nr * 9 nc; if (board[dest] 0) { moves.add(dest); // 空位可以走 } else { if (isOpponent(board[dest], board[from])) moves.add(dest); // 吃子 break; // 碰到棋子就停下车不能越子 } nr d[0]; nc d[1]; } } }这里有个性能细节moves用一个ArrayListInteger或自定义的int[] size复用不要在递归里频繁 new 集合对象否则 GC 压力会拖慢搜索。兵卒的规则要注意方向性——红方兵只能向上黑方卒只能向下过河之后才能左右移动很多初版实现会漏掉“未过河不能左右走”这个条件导致 AI 走出离谱的棋。马和相是走法生成里最容易写错的两个棋子。马的“马脚”判断如果目标位置在 from 的上下方向位移两格则马脚在中间那个点如果左右位移两格则马脚在中间左右点。相的“塞象眼”相走田字中间交叉点不能有子。另外相不能过河这在生成器里要用行号一次性过滤掉别让搜索跑到一半才发现不合法那样会白白浪费一层深度。3. 人机博弈核心极大极小值与 Alpha-Beta 剪枝的落地写法这一章是整个项目的心脏。极大极小值搜索的思路是假设对方也足够聪明每次都会走对它最有利的棋那么我方选棋时就要在“我走完这步后对方能拿到的最好局面”里挑一个对我方最不利的——也就是极小化对方的最大收益。这句话读起来拗口落到代码上却很简单关键在评估函数和递归终止条件。3.1 从评估函数入手先把“局面好坏”量化评估函数决定了 AI 的“价值观”它认为车值 600 分马值 300 分兵值 100 分位置好的马再多加 20 分这些权重加起来就是当前局面对某一方的评分。源码里一般会有一个evaluate()方法类似这样private int evaluate(byte[] board) { int score 0; for (int i 0; i 90; i) { int piece board[i]; if (piece 0) continue; int value pieceValue(Math.abs(piece)); if (piece 0) { score value; score positionBonus(piece, i); // 红方按原始坐标查位置表 } else { score - value; score - positionBonus(-piece, mirrorIndex(i)); // 黑方需要镜像棋盘 } } return score; }这个函数是搜索算法的“黑匣子”输入——它返回的值越正表示越利于红方越负表示越利于黑方。初次读这份源码时要注意它有没有对黑方做棋盘镜像。因为黑方棋子的位置评估表不能直接复用红方的比如红车在底线是好位置黑车在它的底线同样是中心区域的好位置如果不镜像AI 会认为黑车待在角落是好事属于低级错误。位置表的本质是静态估值常见做法是给兵、马、炮各设计一张 10x9 的加分表。马在棋盘中心要比在边角有更强的控制力所以中心区域的表值通常是 10 到 20兵过河后加分明显但卒在对方底线时反而容易被困适当降权。网上流传的那套“象棋百科全书”估值表可以直接用但初始来源都一样数值微调影响不大。3.2 极大极小搜索的递归实现与深度控制评估函数有了接下来就是递归搜索。伪代码并不复杂如果当前深度为 0 或者已经分出胜负就返回评估值否则生成所有走法逐个模拟递归调用对方视角的搜索然后取最大或最小值。参考写法private int minimax(byte[] board, int depth, boolean isRedTurn) { int winner checkWinner(board); if (winner ! 0) return winner 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE; if (depth 0) return evaluate(board); ListInteger moves generateMoves(board, isRedTurn); int best isRedTurn ? Integer.MIN_VALUE : Integer.MAX_VALUE; for (int move : moves) { makeMove(board, move); int score minimax(board, depth - 1, !isRedTurn); unmakeMove(board, move); if (isRedTurn) best Math.max(best, score); else best Math.min(best, score); } return best; }makeMove和unmakeMove是成对出现的这是回溯的关键。如果不做还原搜索完一条分支后棋盘状态就乱了后续分支的结果全部失真——这是新手最容易犯的错误只做“走子”不做“悔棋”。这份源码的正确设计是记录被吃掉的棋子类型走完棋后反向恢复。另外深度参数调 4 是安全值加了剪枝以后可以上 5 到 6如果你的电脑性能一般深度 4 已经能打败大多数纯随机落子的玩家了。还有一个细节搜索到底层时不要只返回静态评估值最好做一次“扩展检查”。比如当前局面已经被将军哪怕深度用完了也要尝试多走一步捉王否则 AI 会忽视杀棋。常见做法是if (checkSideToMove(board, isRedTurn)) depth 1相当于军情紧急时自动加深一层。3.3 Alpha-Beta 剪枝让搜索深度从 3 层提到 5 层纯极大极小搜索的问题是节点数随着深度指数爆炸平均分支因子大约 384 层就是 38 的 4 次方约 200 万个节点Java 里跑一次要好几秒。Alpha-Beta 剪枝可以在不改变结果的前提下砍掉大约一半到三分之二的节点。核心思路是维护两个值alpha 表示红方目前已经能保证的最低收益beta 表示黑方可以接受的最大损失当某个节点上alpha beta时就剪枝因为后续分支已经不可能影响最终决策。private int alphaBeta(byte[] board, int depth, int alpha, int beta, boolean isRedTurn) { int winner checkWinner(board); if (winner ! 0) return winner 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE; if (depth 0) return quiescenceSearch(board, isRedTurn, alpha, beta); ListInteger moves generateMoves(board, isRedTurn); // 将走法按“吃大子优先”排序剪枝效果会好很多 sortMovesByCapturedValue(moves, board); int best isRedTurn ? Integer.MIN_VALUE : Integer.MAX_VALUE; for (int move : moves) { makeMove(board, move); int score alphaBeta(board, depth - 1, alpha, beta, !isRedTurn); unmakeMove(board, move); if (isRedTurn) { best Math.max(best, score); alpha Math.max(alpha, best); } else { best Math.min(best, score); beta Math.min(beta, best); } if (alpha beta) break; // 剪枝 } return best; }剪枝顺序极其重要。如果每次都先尝试吃车的走法alpha 值会迅速抬高剪掉的节点就多。反过来如果先从边角兵开始试alpha 迟迟不涨剪枝效果约等于零。这就是为什么sortMovesByCapturedValue一行注释背后藏着决定性作用——不排序的剪枝可能砍 10%排序后能砍 70%搜索速度差距肉眼可见。4. 把搜索线程接进 Swing 界面一步棋的完整链路算法写完了最终要落在界面上。Swing 和搜索线程的接缝处是最容易翻车的地方常见做法是用户点击棋盘 - 走子 - 在单独线程里跑 alphaBeta - 拿到结果后切回事件调度线程更新界面。4.1 事件响应与耗时操作的线程处理很多人第一次写这个项目时直接在鼠标点击事件里调用alphaBeta界面立刻就冻结鼠标也点不动只能眼睁睁看着窗口失去响应。为什么因为 Swing 的事件处理线程EDT同时负责任何重绘你在 EDT 里跑一个几秒钟的搜索整个窗口就卡死了。正确写法是private void handleUserMove(int from, int to) { makeMove(currentBoard, from, to); updateBoardUI(currentBoard); aiThinking true; new Thread(() - { int bestMove alphaBetaRoot(currentBoard, 4); SwingUtilities.invokeLater(() - { applyBestMove(bestMove); aiThinking false; }); }).start(); }这个结构里有两个关键点搜索线程采用普通守护线程即可不需要线程池更新界面必须用SwingUtilities.invokeLater否则界面状态和棋盘数据不同步Swing 内部变量并不是线程安全的会静默出错。这里还有一个常见坑用户连点时aiThinking标志位要判断防止线程还没算完又启动第二个导致棋局错乱。4.2 落子、悔棋、胜负判断的联动落子不只是改棋盘数组还要把“吃掉的子”“起点终点”推入一个历史栈悔棋才能回退。常见的做法是用两个栈一个存走法一个存被吃棋子类型悔棋时依次弹栈恢复。注意胜负判断要放在走子之后立即执行否则可能出现“AI 已经将死却不宣布赢棋”的情况。胜负判定在这个项目里通常不查全盘只看帅是否被吃或是否被将军到无处可走。简单可靠的方案是每次走子后扫描全盘如果对方的帅/将不在棋盘上直接判胜如果被将军尝试枚举对方所有合法走法看有没有能解将的没有就判负。这个逻辑虽然效率不高但配合深度搜索完全够用而且出错概率低。用“红方有没有合法走法”来判断将死比单纯判断“是否被将军”更准确因为有的局面虽然有合法走法但全是送死这步检查能避免错误的胜负判定。5. 象棋对弈实战避坑5 个让 AI “翻车”的细节5.1 AI 的第一步永远只走一个固定的棋现象不管执红执黑AI 先手永远走同一着比如中炮或者跳那个位置的马换个棋盘位置也一样。原因搜索树深度不够时开局几步的评估分数差距极小如果走法生成器没有对棋子位置做随机扰动或者生成顺序固定AI 就永远选第一个最大值分支。解决在走法生成阶段加入一个权重微调比如给每条走法加一个 0 到 1 的随机数乘 5加到评估分数上这个量级不影响大局判断但能显著增加开局多样性避免显得死板。5.2 马和相走法的“蹩腿”“塞象眼”检测漏判现象AI 的马可以隔着子跳出去相也能在没有“象眼”的情况下过河。原因走法生成器只做了目标位置的边界判断没有检查马脚和象眼位置是否有棋子。解决在生成器内部对马的八个方向分别检查“马脚”位置相的四个方向分别检查田字中心点。并且要把这种检查放在搜索前不要在makeMove里二次校验否则搜索速度会恶化。5.3 搜索太慢一步棋要等半分钟现象AI 每步耗时极长用户以为是界面卡死。原因剪枝顺序混乱逼着搜索几乎遍历所有节点或者makeMove里做大量对象分配或者每一步都重新 new 一个ArrayList存走法。解决把走法排序放在剪枝搜索前优先尝试吃大子方向走法列表用复用的int[] size如果还不够把深度从 5 退回 4或者引入置换表缓存局面评估。注意这里说的置换表不是必须的先检查前两项优化效果立竿见影。5.4 AI 在残局阶段出现“送吃”的愚蠢走法现象进入残局AI 会主动把车送到对方马嘴里或者把帅走到对方炮的火线上。原因搜索深度不足导致它看不到两步以上的杀棋或者静态评估函数没有把“被将军”计入惩罚。解决启动将军搜索当当前走法导致己方被将军时候选落子直接给一个大负分惩罚或者把搜索深度在残局时动态加一。另一个有效策略是引入“历史启发”如果某步棋在之前的分支里造成过吃子排序时给它加分这是零成本提速。5.5 提示“悔棋”之后 AI 走出的棋不变或者界面棋盘错乱现象悔棋一次后重新走棋AI 给出和上次完全相同的应对有时界面棋盘上出现多子或少子的怪象。原因悔棋只恢复了棋盘数组但没恢复搜索里的历史栈快照或者历史栈里只记录了走法没记录被吃子恢复后棋盘状态错乱。解决悔棋操作的完整操作序列是弹出走法、把目标位置恢复为被吃棋子、把起点恢复为走子棋子、恢复当前轮次。建议在悔棋后打印一次棋盘哈希值对比悔棋前后的局面是否一致不一致立即报警这个习惯能快速定位到底哪一步恢复了。6. 想验证 AI 强度自己改评估函数权重的三条路子把这个项目跑通只是第一步真正让你能写进简历的技能是“你会调参、会验证、会扩展”。第一条路子是改变子力分值。默认分值表通常写着 车600、马300、炮300、兵100。你把马改成 350、炮改成 250AI 风格立刻就会变了——它会更积极地跳马而不是用炮兑子。怎么验证改得对不对让不同权重的 AI 自己下十盘统计胜率。我一般会写一个自动对弈脚本让红黑两方都调用同一个搜索类但传不同权重连续跑几十盘胜率过六成才算有效改动。第二条路子是改造评估函数的“位置加成表”。最常见的做法是为兵设计一张“过河推进表”兵在河界对岸加 10 分越深入对方腹地分数递增。但要注意这个表不能设计得太激进否则 AI 会在残局里一门心思拱兵把车马全扔在一边属于“局部最优害了全局”。这时候你要会看对局记录——每一手棋是什么评估分是多少哪一手因为兵权重过高而错过吃车机会这种复盘能力比调参本身更值钱。第三条路子最有挑战性但也最能体现你对极大极小值搜索的理解给搜索加置换表。搜索同一个局面时如果之前已经算过这个深度下的评估值直接复用不用重新计算。实现要点是棋局哈希值的设计可以用 Zobrist 哈希每个棋子、每个位置给一个随机数落子时异或更新。最后分享一个我的习惯拿到任何棋类 AI 源码第一件事就是关掉剪枝把搜索深度从 4 直接拉到 3跑一遍基准测试记录耗时然后开剪枝深度拉回 4再记录耗时。这两个数据一对比你就能直观看到剪枝对你的分支因子到底有多大改善。这个数据比任何源码分析都更有说服力。还有一个教训当初我第一版评估函数里忘了给黑方镜像位置表结果 AI 执黑时明显偏科输多赢少找了两天才定位到问题。后来我养成了一个习惯任何棋盘相关的对称操作一律用单元测试固定住边界情况再也不用靠肉眼复盘来赌代码没有低级错误。这样一套流程下来你收获的不只是能跑的人机对弈游戏而是一套完整的博弈算法调试方法论希望帮到你。本文还有配套的精品资源点击获取
简介一套基于 Java Swing 的象棋游戏源码利用极大极小值搜索算法实现人机对弈并配有完整的文档说明。适合正在准备课程设计、毕业设计的计算机专业学生也适合需要 Java 项目实战练习的开发者可有效解决 Java GUI 开发、博弈树搜索、棋局评估与代码架构设计等综合性问题。整个资源包共 150 个文件压缩后仅 3.03MB。其中 74 个 Java 源文件构成核心代码覆盖棋盘绘制、走法合法性判断、局面评估、AI 搜索等功能32 张 jpg 与 8 张 png 作为界面和棋子素材24 个 wav 提供落子、胜利等音效6 个 markdown 文档便于快速理解项目结构另有 xml、properties 等配置文件辅助程序运行。目前已有 242 人学习。拿到手即可直接运行体验人机对战同时通过源码和文档理解极大极小值算法及 Alpha-Beta 剪枝的实际应用也能在此基础之上二次开发用于课程作业、期末大作业或毕业设计演示。1. 一个 Java Swing 象棋游戏为什么值得你打开这份源码如果你正在找“基于 java swing 的象棋游戏源码(极大极小值搜索算法实现人机对弈)”这种项目多半不是单纯想下棋而是想搞明白一件事让电脑“会下棋”的那套搜索逻辑到底是怎么写出来的。这份源码的卖点恰恰不在 Swing 界面本身而在“极大极小值搜索算法”这几个字上——它是棋类 AI 最经典、最容易读懂、也最适合拿来当算法入门的一条路径。用 Java Swing 做前端只是让这套算法有了一个能看、能点、能跑起来的壳。它能解决你什么问题如果你在学数据结构与算法或者刚接触博弈类 AI直接啃框架源码容易迷失在工程细节里而这个项目把博弈树搜索、评估函数、走法生成、人机交互全部浓缩在一个可运行的游戏里。适合的人群很明确想理解 Minimax 和剪枝原理的在校学生、要做课程设计的开发者、以及准备用棋类 AI 做面试项目的从业者。我用类似的思路做过几个棋类 Demo可以负责任地说这个方向性价比极高——跑通它你就等于打通了棋类 AI 的一条完整链路。下面从棋盘模型开始一步步拆开这份源码最核心的部分。2. 先看懂棋盘和走法极大极小搜索的地基搜索算法的本质是“枚举所有可能的走法然后选一个最好的”。如果走法生成器写错了或者棋盘状态表示混乱那么再聪明的搜索算法也是白搭。所以看这份源码时第一件事不是去读搜索函数而是先看棋盘是怎么建模的、走法是怎么生成的。2.1 用一维数组表示棋局红黑双方的建模约定常见做法是用长度为 90 的字节数组表示十行九列的棋盘下标 0 到 89数组里存棋子类型和归属方。为什么不用二维数组因为一维数组在 Java 里读写更快而且下标可以直接用来判断棋盘边界避免每一层递归都做二维索引换算。源码或“红方走棋”代码通常长这样byte[] board new byte[90]; // 棋子编码约定0空1红帅2红仕3红相4红马5红车6红炮7红兵 // 黑方用负值-1黑将-2黑士-3黑象-4黑马-5黑车-6黑炮-7黑卒 // 例如红车放在左下角board[9 * 9 0] 5;这个编码方案的好处是判断棋子属于哪一方只需要看值大于 0 还是小于 0判断是否为空只需要看是否等于 0。拆包棋盘时注意两个细节。第一黑方的坐标是从对方视角看的行号 0 到 9 映射时要把方向倒过来否则会出现黑方棋子“倒着走”的玄学问题第二数组下标运算时必须把边界检查写进走法生成器而不是写进搜索循环因为搜索循环里每展开一个节点就要调一次走法生成多一次数组越界检查就是一次性能损耗。2.2 走法生成器给搜索树提供分支走法生成器是搜索算法的数据来源它的职责简单说就是给定一个棋盘状态和一个棋子位置算出所有合法落点。不同棋子的规则差异很大车的走法最直白马和相则有“腿”和“塞象眼”的约束。以车为例标准写法如下private void generateRookMoves(int from, ListInteger moves, byte[] board) { int row from / 9, col from % 9; int[][] dirs {{1,0},{-1,0},{0,1},{0,-1}}; for (int[] d : dirs) { int nr row d[0], nc col d[1]; while (nr 0 nr 10 nc 0 nc 9) { int dest nr * 9 nc; if (board[dest] 0) { moves.add(dest); // 空位可以走 } else { if (isOpponent(board[dest], board[from])) moves.add(dest); // 吃子 break; // 碰到棋子就停下车不能越子 } nr d[0]; nc d[1]; } } }这里有个性能细节moves用一个ArrayListInteger或自定义的int[] size复用不要在递归里频繁 new 集合对象否则 GC 压力会拖慢搜索。兵卒的规则要注意方向性——红方兵只能向上黑方卒只能向下过河之后才能左右移动很多初版实现会漏掉“未过河不能左右走”这个条件导致 AI 走出离谱的棋。马和相是走法生成里最容易写错的两个棋子。马的“马脚”判断如果目标位置在 from 的上下方向位移两格则马脚在中间那个点如果左右位移两格则马脚在中间左右点。相的“塞象眼”相走田字中间交叉点不能有子。另外相不能过河这在生成器里要用行号一次性过滤掉别让搜索跑到一半才发现不合法那样会白白浪费一层深度。3. 人机博弈核心极大极小值与 Alpha-Beta 剪枝的落地写法这一章是整个项目的心脏。极大极小值搜索的思路是假设对方也足够聪明每次都会走对它最有利的棋那么我方选棋时就要在“我走完这步后对方能拿到的最好局面”里挑一个对我方最不利的——也就是极小化对方的最大收益。这句话读起来拗口落到代码上却很简单关键在评估函数和递归终止条件。3.1 从评估函数入手先把“局面好坏”量化评估函数决定了 AI 的“价值观”它认为车值 600 分马值 300 分兵值 100 分位置好的马再多加 20 分这些权重加起来就是当前局面对某一方的评分。源码里一般会有一个evaluate()方法类似这样private int evaluate(byte[] board) { int score 0; for (int i 0; i 90; i) { int piece board[i]; if (piece 0) continue; int value pieceValue(Math.abs(piece)); if (piece 0) { score value; score positionBonus(piece, i); // 红方按原始坐标查位置表 } else { score - value; score - positionBonus(-piece, mirrorIndex(i)); // 黑方需要镜像棋盘 } } return score; }这个函数是搜索算法的“黑匣子”输入——它返回的值越正表示越利于红方越负表示越利于黑方。初次读这份源码时要注意它有没有对黑方做棋盘镜像。因为黑方棋子的位置评估表不能直接复用红方的比如红车在底线是好位置黑车在它的底线同样是中心区域的好位置如果不镜像AI 会认为黑车待在角落是好事属于低级错误。位置表的本质是静态估值常见做法是给兵、马、炮各设计一张 10x9 的加分表。马在棋盘中心要比在边角有更强的控制力所以中心区域的表值通常是 10 到 20兵过河后加分明显但卒在对方底线时反而容易被困适当降权。网上流传的那套“象棋百科全书”估值表可以直接用但初始来源都一样数值微调影响不大。3.2 极大极小搜索的递归实现与深度控制评估函数有了接下来就是递归搜索。伪代码并不复杂如果当前深度为 0 或者已经分出胜负就返回评估值否则生成所有走法逐个模拟递归调用对方视角的搜索然后取最大或最小值。参考写法private int minimax(byte[] board, int depth, boolean isRedTurn) { int winner checkWinner(board); if (winner ! 0) return winner 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE; if (depth 0) return evaluate(board); ListInteger moves generateMoves(board, isRedTurn); int best isRedTurn ? Integer.MIN_VALUE : Integer.MAX_VALUE; for (int move : moves) { makeMove(board, move); int score minimax(board, depth - 1, !isRedTurn); unmakeMove(board, move); if (isRedTurn) best Math.max(best, score); else best Math.min(best, score); } return best; }makeMove和unmakeMove是成对出现的这是回溯的关键。如果不做还原搜索完一条分支后棋盘状态就乱了后续分支的结果全部失真——这是新手最容易犯的错误只做“走子”不做“悔棋”。这份源码的正确设计是记录被吃掉的棋子类型走完棋后反向恢复。另外深度参数调 4 是安全值加了剪枝以后可以上 5 到 6如果你的电脑性能一般深度 4 已经能打败大多数纯随机落子的玩家了。还有一个细节搜索到底层时不要只返回静态评估值最好做一次“扩展检查”。比如当前局面已经被将军哪怕深度用完了也要尝试多走一步捉王否则 AI 会忽视杀棋。常见做法是if (checkSideToMove(board, isRedTurn)) depth 1相当于军情紧急时自动加深一层。3.3 Alpha-Beta 剪枝让搜索深度从 3 层提到 5 层纯极大极小搜索的问题是节点数随着深度指数爆炸平均分支因子大约 384 层就是 38 的 4 次方约 200 万个节点Java 里跑一次要好几秒。Alpha-Beta 剪枝可以在不改变结果的前提下砍掉大约一半到三分之二的节点。核心思路是维护两个值alpha 表示红方目前已经能保证的最低收益beta 表示黑方可以接受的最大损失当某个节点上alpha beta时就剪枝因为后续分支已经不可能影响最终决策。private int alphaBeta(byte[] board, int depth, int alpha, int beta, boolean isRedTurn) { int winner checkWinner(board); if (winner ! 0) return winner 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE; if (depth 0) return quiescenceSearch(board, isRedTurn, alpha, beta); ListInteger moves generateMoves(board, isRedTurn); // 将走法按“吃大子优先”排序剪枝效果会好很多 sortMovesByCapturedValue(moves, board); int best isRedTurn ? Integer.MIN_VALUE : Integer.MAX_VALUE; for (int move : moves) { makeMove(board, move); int score alphaBeta(board, depth - 1, alpha, beta, !isRedTurn); unmakeMove(board, move); if (isRedTurn) { best Math.max(best, score); alpha Math.max(alpha, best); } else { best Math.min(best, score); beta Math.min(beta, best); } if (alpha beta) break; // 剪枝 } return best; }剪枝顺序极其重要。如果每次都先尝试吃车的走法alpha 值会迅速抬高剪掉的节点就多。反过来如果先从边角兵开始试alpha 迟迟不涨剪枝效果约等于零。这就是为什么sortMovesByCapturedValue一行注释背后藏着决定性作用——不排序的剪枝可能砍 10%排序后能砍 70%搜索速度差距肉眼可见。4. 把搜索线程接进 Swing 界面一步棋的完整链路算法写完了最终要落在界面上。Swing 和搜索线程的接缝处是最容易翻车的地方常见做法是用户点击棋盘 - 走子 - 在单独线程里跑 alphaBeta - 拿到结果后切回事件调度线程更新界面。4.1 事件响应与耗时操作的线程处理很多人第一次写这个项目时直接在鼠标点击事件里调用alphaBeta界面立刻就冻结鼠标也点不动只能眼睁睁看着窗口失去响应。为什么因为 Swing 的事件处理线程EDT同时负责任何重绘你在 EDT 里跑一个几秒钟的搜索整个窗口就卡死了。正确写法是private void handleUserMove(int from, int to) { makeMove(currentBoard, from, to); updateBoardUI(currentBoard); aiThinking true; new Thread(() - { int bestMove alphaBetaRoot(currentBoard, 4); SwingUtilities.invokeLater(() - { applyBestMove(bestMove); aiThinking false; }); }).start(); }这个结构里有两个关键点搜索线程采用普通守护线程即可不需要线程池更新界面必须用SwingUtilities.invokeLater否则界面状态和棋盘数据不同步Swing 内部变量并不是线程安全的会静默出错。这里还有一个常见坑用户连点时aiThinking标志位要判断防止线程还没算完又启动第二个导致棋局错乱。4.2 落子、悔棋、胜负判断的联动落子不只是改棋盘数组还要把“吃掉的子”“起点终点”推入一个历史栈悔棋才能回退。常见的做法是用两个栈一个存走法一个存被吃棋子类型悔棋时依次弹栈恢复。注意胜负判断要放在走子之后立即执行否则可能出现“AI 已经将死却不宣布赢棋”的情况。胜负判定在这个项目里通常不查全盘只看帅是否被吃或是否被将军到无处可走。简单可靠的方案是每次走子后扫描全盘如果对方的帅/将不在棋盘上直接判胜如果被将军尝试枚举对方所有合法走法看有没有能解将的没有就判负。这个逻辑虽然效率不高但配合深度搜索完全够用而且出错概率低。用“红方有没有合法走法”来判断将死比单纯判断“是否被将军”更准确因为有的局面虽然有合法走法但全是送死这步检查能避免错误的胜负判定。5. 象棋对弈实战避坑5 个让 AI “翻车”的细节5.1 AI 的第一步永远只走一个固定的棋现象不管执红执黑AI 先手永远走同一着比如中炮或者跳那个位置的马换个棋盘位置也一样。原因搜索树深度不够时开局几步的评估分数差距极小如果走法生成器没有对棋子位置做随机扰动或者生成顺序固定AI 就永远选第一个最大值分支。解决在走法生成阶段加入一个权重微调比如给每条走法加一个 0 到 1 的随机数乘 5加到评估分数上这个量级不影响大局判断但能显著增加开局多样性避免显得死板。5.2 马和相走法的“蹩腿”“塞象眼”检测漏判现象AI 的马可以隔着子跳出去相也能在没有“象眼”的情况下过河。原因走法生成器只做了目标位置的边界判断没有检查马脚和象眼位置是否有棋子。解决在生成器内部对马的八个方向分别检查“马脚”位置相的四个方向分别检查田字中心点。并且要把这种检查放在搜索前不要在makeMove里二次校验否则搜索速度会恶化。5.3 搜索太慢一步棋要等半分钟现象AI 每步耗时极长用户以为是界面卡死。原因剪枝顺序混乱逼着搜索几乎遍历所有节点或者makeMove里做大量对象分配或者每一步都重新 new 一个ArrayList存走法。解决把走法排序放在剪枝搜索前优先尝试吃大子方向走法列表用复用的int[] size如果还不够把深度从 5 退回 4或者引入置换表缓存局面评估。注意这里说的置换表不是必须的先检查前两项优化效果立竿见影。5.4 AI 在残局阶段出现“送吃”的愚蠢走法现象进入残局AI 会主动把车送到对方马嘴里或者把帅走到对方炮的火线上。原因搜索深度不足导致它看不到两步以上的杀棋或者静态评估函数没有把“被将军”计入惩罚。解决启动将军搜索当当前走法导致己方被将军时候选落子直接给一个大负分惩罚或者把搜索深度在残局时动态加一。另一个有效策略是引入“历史启发”如果某步棋在之前的分支里造成过吃子排序时给它加分这是零成本提速。5.5 提示“悔棋”之后 AI 走出的棋不变或者界面棋盘错乱现象悔棋一次后重新走棋AI 给出和上次完全相同的应对有时界面棋盘上出现多子或少子的怪象。原因悔棋只恢复了棋盘数组但没恢复搜索里的历史栈快照或者历史栈里只记录了走法没记录被吃子恢复后棋盘状态错乱。解决悔棋操作的完整操作序列是弹出走法、把目标位置恢复为被吃棋子、把起点恢复为走子棋子、恢复当前轮次。建议在悔棋后打印一次棋盘哈希值对比悔棋前后的局面是否一致不一致立即报警这个习惯能快速定位到底哪一步恢复了。6. 想验证 AI 强度自己改评估函数权重的三条路子把这个项目跑通只是第一步真正让你能写进简历的技能是“你会调参、会验证、会扩展”。第一条路子是改变子力分值。默认分值表通常写着 车600、马300、炮300、兵100。你把马改成 350、炮改成 250AI 风格立刻就会变了——它会更积极地跳马而不是用炮兑子。怎么验证改得对不对让不同权重的 AI 自己下十盘统计胜率。我一般会写一个自动对弈脚本让红黑两方都调用同一个搜索类但传不同权重连续跑几十盘胜率过六成才算有效改动。第二条路子是改造评估函数的“位置加成表”。最常见的做法是为兵设计一张“过河推进表”兵在河界对岸加 10 分越深入对方腹地分数递增。但要注意这个表不能设计得太激进否则 AI 会在残局里一门心思拱兵把车马全扔在一边属于“局部最优害了全局”。这时候你要会看对局记录——每一手棋是什么评估分是多少哪一手因为兵权重过高而错过吃车机会这种复盘能力比调参本身更值钱。第三条路子最有挑战性但也最能体现你对极大极小值搜索的理解给搜索加置换表。搜索同一个局面时如果之前已经算过这个深度下的评估值直接复用不用重新计算。实现要点是棋局哈希值的设计可以用 Zobrist 哈希每个棋子、每个位置给一个随机数落子时异或更新。最后分享一个我的习惯拿到任何棋类 AI 源码第一件事就是关掉剪枝把搜索深度从 4 直接拉到 3跑一遍基准测试记录耗时然后开剪枝深度拉回 4再记录耗时。这两个数据一对比你就能直观看到剪枝对你的分支因子到底有多大改善。这个数据比任何源码分析都更有说服力。还有一个教训当初我第一版评估函数里忘了给黑方镜像位置表结果 AI 执黑时明显偏科输多赢少找了两天才定位到问题。后来我养成了一个习惯任何棋盘相关的对称操作一律用单元测试固定住边界情况再也不用靠肉眼复盘来赌代码没有低级错误。这样一套流程下来你收获的不只是能跑的人机对弈游戏而是一套完整的博弈算法调试方法论希望帮到你。本文还有配套的精品资源点击获取
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
