Java 17 实现爱因斯坦棋 AI：期望极大搜索与置换表

简介：这是一份以爱因斯坦棋为主题的 Java 人工智能对弈项目源码包，面向希望入门棋类 AI 的 Java 学习者、课程设计开发者及博弈算法自学者。项目将棋盘与棋子表示、合法走法判定、游戏循环、控制台输入输出及 AI 决策核心组织为面向对象结构，虽无图形界面，但可通过命令行完成人机对弈，适合用来理解搜索算法、博弈树与评估函数在策略棋类中的落地方式。压缩包共 13 个文件，包含 8 个 class 字节码、4 个 Java 源码及 1 个 bak 备份文件，整体仅 16KB，体量轻便，便于快速解压阅读与二次修改。已有 3458 人学习下载。读者可从中拆解 AI 走法生成、局面评估与搜索剪枝思路，观察线程与控制台交互如何衔接，并据此完成课程实践或小型棋类 AI 改造。

1. 扫一眼就想跑起来：爱因斯坦棋 AI 到底是个什么项目

爱因斯坦棋（Einstein würfelt nicht）这名字听着玄学，规则其实很硬：5×5 棋盘，每方 6 枚编号 1~6 的棋子，每回合掷骰子决定走哪一枚，先摸到对角角落的赢。纯靠人脑算，随机性会把人折磨疯；把决策交给一段 Java 写的人工智能，反而能看清“随机 + 对抗”叠加时博弈搜索该怎么落地。这份资源就是一套能直接编译运行的爱因斯坦棋 AI 对弈工程：规则引擎、期望极大搜索、置换表、控制台交互全在里面，运行时不依赖任何第三方库。适合正在啃 α-β 剪枝、想找个比五子棋更难的练手项目的开发者，也适合想把存量评估函数换成自己思路的人。

2. 工程骨架：纯 Java 17 单模块，为什么敢不挂框架

2.1 技术选型：计算密集型程序不需要容器

对弈程序本质是一段 CPU 密集的纯计算，没有 HTTP 入口、没有数据库、没有对象生命周期管理，把 Spring 引进来只会换来十几秒启动和一堆用不上的注解。这个项目最终定在 JDK 17 + Maven 单模块：record用来写走法值对象，switch表达式用来解析命令行参数，instanceof模式匹配在渲染层判断空格和棋子，代码量比 Java 8 风格少一大截。

JDK 版本上有踩坑点：record是 16 才转正，switch表达式 14 转正，如果你本机还挂着 JDK 11，mvn package会在编译期直接报“不支持的模式匹配”。pom.xml里我用maven.compiler.release而不是source/target，原因是release会连 JDK 内部 API 一起做校验，避免你在开发机上能编译、换台机器就跑不起来。测试只用 JUnit 5，不引 Mockito，规则引擎是纯函数式的输入输出，给了棋盘就该返回确定的走法集合，没有需要打桩的依赖。

打包环节用maven-shade-plugin打成 fat jar。这里不上spring-boot-maven-plugin也不用assembly，shade 的 Manifest 转换器能直接把Main-Class写进清单，java -jar一条命令就能起。整个 jar 出来不到 1MB，扔到任何装了 JDK 17 的机器上都能跑。

<properties> <!-- 用 release 而不是 source/target，编译期就能发现用了高版本 API --> <maven.compiler.release>17</maven.compiler.release> <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding> </properties> <build> <plugins> <plugin> <groupId>org.apache.maven.plugins</groupId> <artifactId>maven-shade-plugin</artifactId> <version>3.5.1</version> <executions> <execution> <phase>package</phase> <goals><goal>shade</goal></goals> <configuration> <transformers> <transformer implementation="org.apache.maven.plugins.shade.resource.ManifestResourceTransformer"> <!-- 写死入口类，省掉 -cp 参数 --> <mainClass>com.example.einstein.Main</mainClass> </transformer> </transformers> </configuration> </execution> </executions> </plugin> </plugins> </build>

<phase>package</phase>表示 shade 绑在打包阶段之后执行，ManifestResourceTransformer是唯一必须的转换器，不加它打出来的 jar 里META-INF/MANIFEST.MF没有Main-Class，java -jar会直接甩一句no main manifest attribute。版本号写死在配置里是为了让构建可复现，不建议用LATEST。

2.2 包结构与职责划分

项目按“状态 / 规则 / 搜索 / 界面”四层切包，没有为了分层而分层。核心约束是：core包不许 importai包，ai包不许 importui包。这条线守住了，规则引擎就能脱离 AI 单独跑单元测试，AI 也能脱离控制台被自对弈脚本批量调用。

Board设计成不可变的，apply(Move)返回新对象而不是原地修改。这一条看起来浪费内存，但对搜索是必需的：期望极大搜索同一层要展开 6 个骰子分支，每个分支下还有若干走法，如果共享可变棋盘，回溯时漏还原一格，整个搜索结果就是错的，而且这种 bug 极难定位——现象是 AI 偶尔走一步莫名其妙的棋，你把日志打满也复现不出来。

2.3 三条命令跑起来

Main的参数解析刻意手写，不引 picocli，总共二十行。可调参数就三个：搜索深度、先后手、是否打印搜索统计。

package com.example.einstein; public final class Main { public static void main(String[] args) { int depth = 4; // 默认深度 4，笔记本上单步约 200ms boolean humanFirst = true; // 默认玩家执红先手 boolean verbose = false; for (int i = 0; i < args.length; i++) { switch (args[i]) { case "-d", "--depth" -> depth = Integer.parseInt(args[++i]); case "--ai-first" -> humanFirst = false; case "-v", "--verbose" -> verbose = true; default -> System.out.println("未知参数: " + args[i]); } } new ConsoleUI(depth, humanFirst, verbose).run(); } }

深度参数是唯一影响体验的旋钮。深度 3 大概几十毫秒一步，但 AI 会走出“能赢不赢”的棋；深度 5 在普通笔记本上单步 1~3 秒，棋力明显上一个台阶；深度 7 以上不加置换表会卡到十几秒。--ai-first用来让 AI 执红先走，方便你观察它的开局偏好。

mvn -q clean package java -jar target/einstein-chess-1.0.0.jar -d 4 java -jar target/einstein-chess-1.0.0.jar -d 6 --ai-first -v

启动后控制台会打印一个 5×5 的字符棋盘，红方棋子用1~6表示，蓝方用a~f，空格是.。每回合先掷骰子，打印出“掷出 N，可用棋子 [N]”，然后列出这枚棋子所有合法落点，输入from-to形式的坐标即可。

红方 你 | 回合 3 . . . . . . . . . . . . . 3 . . 6 . . . . . 4 . . 1 掷出 4，可用棋子: [4] 可走: 4-2 -> 3-2 4-2 -> 3-1 4-2 -> 4-1 请输入 (行 列 行 列):

坐标是 0 基的行 列，四个数字空格分隔。输了不用重启，回车后自动重开一局。这套交互谈不上好用，但胜在零依赖，SSH 到任何一台机器上都能下。

3. 规则引擎拆解：一枚棋子从掷出到落地的完整链路

3.1 棋盘表示：一个 5×5 int 数组加一张位置索引

棋盘的存储方案直接影响搜索速度。最朴素的做法是int[5][5]，正数红方、负数蓝方。但搜索时高频操作是“编号为 3 的红子在哪”，遍历 25 格找一遍等于白白浪费。所以我在Board里额外维护一张pos[2][7]索引表，第一维 0 是红、1 是蓝，第二维按棋子编号 1~6 索引，值存r * 5 + c，-1表示这枚棋子已经被吃。

public final class Board { public static final int SIZE = 5; public static final int RED = 1; public static final int BLUE = -1; private static final int NONE = -1; private final int[][] grid = new int[SIZE][SIZE]; // 正数红方，负数蓝方，0 空 private final int[][] pos = new int[2][7]; // 位置索引，值 = r*5+c public Board() { for (int[] row : pos) java.util.Arrays.fill(row, NONE); } /** 拷贝构造：搜索每展开一步都走这里，必须深拷贝 */ public Board(Board o) { for (int r = 0; r < SIZE; r++) this.grid[r] = o.grid[r].clone(); for (int s = 0; s < 2; s++) this.pos[s] = o.pos[s].clone(); } public static Board initial() { Board b = new Board(); // 红方从右下角出发，目标 (0,0)；蓝方镜像，目标 (4,4) int[][] redCells = {{4,4},{4,3},{3,4},{4,2},{2,4},{3,3}}; int[][] blueCells = {{0,0},{0,1},{1,0},{0,2},{2,0},{1,1}}; for (int i = 0; i < 6; i++) { b.put(RED, i + 1, redCells[i][0], redCells[i][1]); b.put(BLUE, i + 1, blueCells[i][0], blueCells[i][1]); } return b; } private void put(int side, int no, int r, int c) { grid[r][c] = side * no; pos[side == RED ? 0 : 1][no] = r * SIZE + c; } public int rowOf(int side, int no) { int p = pos[side == RED ? 0 : 1][no]; return p == NONE ? -1 : p / SIZE; } public int colOf(int side, int no) { int p = pos[side == RED ? 0 : 1][no]; return p == NONE ? -1 : p % SIZE; } public int cell(int r, int c) { return grid[r][c]; } public boolean alive(int side, int no) { return pos[side == RED ? 0 : 1][no] != NONE; } public Board apply(Move m) { Board n = new Board(this); int eaten = grid[m.toR()][m.toC()]; int side = m.piece() > 0 ? RED : BLUE; int no = Math.abs(m.piece()); n.grid[m.fromR()][m.fromC()] = 0; n.grid[m.toR()][m.toC()] = m.piece(); // 目标格直接覆盖，等于吃子 n.pos[side == RED ? 0 : 1][no] = m.toR() * SIZE + m.toC(); if (eaten != 0) { // 被吃的棋子在索引表里抹掉 n.pos[eaten > 0 ? 0 : 1][Math.abs(eaten)] = NONE; } return n; } }

apply里最容易写错的是吃子分支：grid那一格被覆盖成新棋子，但对方棋子的pos索引如果不置-1，后续alive()会返回true，骰子掷到那个编号时程序还以为这枚棋子活着，rowOf却返回一个早已被占的旧坐标。这类 bug 不会崩溃，只会让 AI 在残局阶段突然“忘记”某些棋子已经死了，然后慌乱地乱走。

apply的另一个细节是必须先读eaten再覆盖。我第一次写的时候顺序反了，先写grid[to] = piece再读目标格，结果永远读到自己的棋子，吃子判定彻底失效，AI 一局都赢不了。

3.2 骰子映射：被吃掉的棋子该怎么“继承”点数

规则的核心机制在这里：掷出点数 N，如果己方编号为 N 的棋子还活着，那就必须走它；如果已经被吃掉，就找编号最接近的存活棋子替代，差值相等时（比如掷出 3，2 和 4 都活着）由当前行动方二选一。这个“继承”机制是爱因斯坦棋区别于普通棋类的关键，也是 AI 搜索分支数暴涨的根源。

/** 返回本轮可选择的己方棋子编号；通常只有 1 个，等距时 2 个 */ public static List<Integer> candidates(Board b, int side, int dice) { if (b.alive(side, dice)) return List.of(dice); // 编号正好活着，唯一选项 List<Integer> res = new ArrayList<>(2); for (int gap = 1; gap <= 5; gap++) { // 距离从 1 开始向外扩 if (dice - gap >= 1 && b.alive(side, dice - gap)) res.add(dice - gap); if (dice + gap <= 6 && b.alive(side, dice + gap)) res.add(dice + gap); if (!res.isEmpty()) return res; // 找到最近一层就停，不要继续扩 } return res; // 极端情况：该方棋子全灭，返回空 }

gap从 1 递增是为了保证“最近优先”。如果先收集完所有存活编号再排序，虽然结果一样，但多一次排序开销，而这段代码在搜索里一秒被调用几十万次。if (!res.isEmpty()) return res是关键：一旦在某个距离层找到棋子，更远的编号就不再考虑。

参数side传的是Board.RED（1）或Board.BLUE（-1），内部的alive会翻译成索引 0/1。dice参数不要传负数或 0，调用方保证骰子在 1~6 之间。

提示：有些实现把“等距二选一”简化成固定选小的那个，棋力会掉一截。因为等距时两枚棋子的位置往往一攻一守，强制选小的那个等于放弃了一半战术选择。

3.3 走法生成与胜负判定

方向规则很简单：红方目标在左上角，所以只能向上、向左、向左上走；蓝方镜像，只能向下、向右、向右下。这意味着一枚棋子永远不会后退，所有走法都是单调逼近目标，棋盘上的冲突集中在中场。

public final class RuleEngine { private static final int[][] RED_DIRS = {{-1,0},{0,-1},{-1,-1}}; private static final int[][] BLUE_DIRS = {{ 1,0},{0, 1},{ 1, 1}}; public static List<Move> legalMoves(Board b, int side, int no) { int r = b.rowOf(side, no), c = b.colOf(side, no); if (r < 0) return List.of(); // 棋子已死 int[][] dirs = (side == Board.RED) ? RED_DIRS : BLUE_DIRS; List<Move> out = new ArrayList<>(3); for (int[] d : dirs) { int nr = r + d[0], nc = c + d[1]; if (nr < 0 || nr >= Board.SIZE || nc < 0 || nc >= Board.SIZE) continue; int target = b.cell(nr, nc); if (target * side > 0) continue; // 同号相乘为正 -> 自己人，跳过 out.add(new Move(r, c, nr, nc, side * no, target != 0)); } return out; } /** 返回获胜方，0 表示未结束 */ public static int winner(Board b) { for (int no = 1; no <= 6; no++) { if (b.rowOf(Board.RED, no) == 0 && b.colOf(Board.RED, no) == 0) return Board.RED; if (b.rowOf(Board.BLUE, no) == 4 && b.colOf(Board.BLUE, no) == 4) return Board.BLUE; } return 0; } }

target * side > 0这行是整个走法生成里最省事的一笔：红方side=1，遇到正数（红子）相乘为正，跳过；蓝方side=-1，遇到负数相乘也为正，同样跳过。空格是 0，相乘为 0，可以走；对方棋子相乘为负，可以吃。一行判掉三种情况，不用写if-else链。

winner每步都要调，搜索里也在调，所以它遍历的是 12 个编号而不是 25 个格子。红方棋子到达(0,0)即胜，蓝方到达(4,4)即胜，不看是哪一枚。这里有个容易被忽略的规则细节：如果一枚棋子吃掉了对方棋子并落在对方的目标格上，同样算赢。所以apply之后必须重新判一次胜负，不能只看落点是不是空。

4. AI 内核：期望极大搜索怎么处理那颗骰子

4.1 评估函数：三个权重决定 AI 的全部性格

评估函数是整个 AI 里唯一带“审美”的部分，搜索只负责在给定审美下找最优。这个项目用了三项特征：棋子存活、到目标的曼哈顿距离、被吃惩罚。看起来简单，权重配比却决定了 AI 是激进还是保守。

public final class Evaluator { private static final int BASE = 120; // 每枚存活棋子的基础分 private static final int DIST = 12; // 每远离目标一格扣的分 private static final int EATEN = 260; // 被吃掉一枚棋子的惩罚 public static int evaluate(Board b, int side) { int red = 0, blue = 0; for (int no = 1; no <= 6; no++) { int rr = b.rowOf(Board.RED, no), rc = b.colOf(Board.RED, no); if (rr < 0) red -= EATEN; else red += BASE - (rr + rc) * DIST; // 红方目标 (0,0) int br = b.rowOf(Board.BLUE, no), bc = b.colOf(Board.BLUE, no); if (br < 0) blue -= EATEN; else blue += BASE - ((4 - br) + (4 - bc)) * DIST; // 蓝方目标 (4,4) } int score = red - blue; return side == Board.RED ? score : -score; // 统一成「当前行动方越大越好」 } }

参数含义：BASE是棋子存在感，DIST是推进一步的价值，EATEN是丢一枚的代价。三者之间存在隐式换算关系：EATEN / DIST ≈ 21，意思是“为了推进 21 格可以牺牲一枚棋子”，但这个换算其实不成立，因为一步最多推进 1 格，21 步的收益在某些残局里确实抵得上一枚子。调大EATEN，AI 会变得极度爱惜棋子，宁愿不推进也不冒险；调小EATEN，AI 会疯狂冲线，哪怕被吃光也要抢那一步。

return side == Board.RED ? score : -score这一行是 negamax 的约定：永远返回“当前行动方视角”的分数。红方行动时希望分数越大越好，蓝方行动时红方的好局面对它是坏局面，所以取负。少了这一行，搜索会陷入“双方都觉得自己在赢”的荒谬状态。

注意：距离用的是曼哈顿距离，斜走一步同时减少两个坐标，所以DIST在斜走时会“赚一倍”。这不是 bug，是设计——斜走更快，就该被鼓励。

4.2 期望极大：把骰子当成概率节点

纯 Minim

本文还有配套的精品资源，点击获取