将棋（Shogi）是世界上最接近”纯搜索问题”的棋类之一。它和象棋最大的不同在于持驹打入（持ち駒）：吃掉的敌方棋子可以变成自己的”手牌”，随时打回棋盘任意空格。
这个规则让将棋的状态空间比国际象棋大一个量级，但也让它的搜索算法有了独特的结构。这篇文章用 Java 实现一个将棋引擎的核心模块，重点讲三件将棋专属的事：成金升变判定、打入规则与二步禁手、带手牌的置换表设计。
一、棋盘表示：9×9 与”手牌”的双层结构
将棋盘面是 9×9，共 81 格。棋子种类 8 种（歩・香・桂・銀・金・角・飛・玉），每种有”成”（promoted）与”不成”两个版本，再加上先后手归属。
关键选择：用一维数组 + 位棋盘，还是二维数组？
将棋的走法生成频率极高，但棋盘只有 81 格。实测表明：一维 byte[81] 数组 + 预计算走法表是最优解。位棋盘（bitboard）在国际象棋里很强，因为 64 格正好放进 long；将棋 81 格要拆成两个 long，跨边界处理很啰嗦，收益不足以抵消复杂度。
/** 棋子编码：低 4 位是种类，第 5 位是归属，第 6 位是是否成 */
static final int PIECE_MASK = 0x0F;
static final int SIDE_MASK = 0x10; // 0=先手(黑) 1=后手(白)
static final int PROMO_MASK = 0x20;
static final int PAWN = 1, LANCE = 2, KNIGHT = 3, SILVER = 4,
GOLD = 5, BISHOP = 6, ROOK = 7, KING = 8;
int pieceType(int p) { return p & PIECE_MASK; }
int pieceSide(int p) { return (p >> 4) & 1; }
boolean promoted(int p) { return (p & PROMO_MASK) != 0; }
int make(int type, int side, boolean promo) {
return type | (side << 4) | (promo ? PROMO_MASK : 0);
}
手牌（持ち駒）用两个长度为 8 的数组记数量，只有 7 种可打入的棋子（玉不能打入）：
final int[][] hand = new int[2][8]; // hand[side][pieceType]
这个”盘面 + 手牌”的双层结构，是将棋引擎和象棋引擎最本质的架构差异。
二、成金升变：三条必须精确掌握的规则
升变（成り）是将棋最丰富的规则细节，也是引擎 bug 的高发区。三条核心规则：
规则一：升变区域是”敌阵”三行。 先手的敌阵是第 0~2 行，后手是第 6~8 行。只要起点或终点任一落在敌阵内，就允许升变（可选择不升，称为”不成”）。
boolean inPromotionZone(int side, int row) {
return side == 0 ? row <= 2 : row >= 6;
}
boolean canPromote(int side, int fromRow, int toRow, int type) {
if (type == GOLD || type == KING) return false; // 金与玉不能成
return inPromotionZone(side, fromRow) || inPromotionZone(side, toRow);
}
规则二：歩・香・桂有”强制升变”。 因为它们升变后才有向前走的合法走法，若走到无法再走的位置就必须升：
- 歩、香走到最底线（先手第 0 行）：必须成
- 桂走到最底两行（先手第 0~1 行）：必须成
boolean mustPromote(int side, int toRow, int type) {
int last = side == 0 ? 0 : 8; // 己方前进方向的底线
int last2 = side == 0 ? 1 : 7;
return switch (type) {
case PAWN, LANCE -> toRow == last;
case KNIGHT -> toRow == last || toRow == last2;
default -> false;
};
}
规则三：升变后的走法表。 这是将棋引擎里最容易写错的地方，因为”成”之后的能力并不是简单的”变强”：
| 原棋子 | 成后 | 走法 |
|---|---|---|
| 歩 | と金 | 等同金 |
| 香 | 成香 | 等同金 |
| 桂 | 成桂 | 等同金 |
| 銀 | 成銀 | 等同金 |
| 角 | 龍馬 | 角 + 上下左右各一步 |
| 飛 | 龍王 | 飛 + 斜四方向各一步 |
| 金 / 玉 | — | 不能成 |
「歩香桂銀」四种成后全部退化为金——这一点非常反直觉（银成后反而失去了斜后方的走法），也是新手最常写错的规则。
/** 返回棋子 p 在 (r,c) 的全部目标格（不考虑阻挡） */
List<int[]> pseudoMoves(int p, int r, int c) {
int type = pieceType(p), side = pieceSide(p);
boolean pro = promoted(p);
int dir = side == 0 ? -1 : 1; // 先手向负方向前进
if (pro) {
if (type == PAWN || type == LANCE || type == KNIGHT || type == SILVER) {
type = GOLD; // 四种成棋统一按金处理
}
// 角成(龙马)、飞成(龙王) 需要在下面叠加额外走法
}
List<int[]> out = new ArrayList<>();
switch (type) {
case PAWN -> addStep(out, r, c, dir, 0);
case KNIGHT -> {
addStep(out, r, c, 2 * dir, -1);
addStep(out, r, c, 2 * dir, 1);
}
case SILVER -> {
addStep(out, r, c, dir, -1); addStep(out, r, c, dir, 0);
addStep(out, r, c, dir, 1);
addStep(out, r, c, -dir, -1); addStep(out, r, c, -dir, 1);
}
case GOLD -> {
addStep(out, r, c, dir, -1); addStep(out, r, c, dir, 0);
addStep(out, r, c, dir, 1);
addStep(out, r, c, -dir, 0);
addStep(out, r, c, 0, -1); addStep(out, r, c, 0, 1);
}
case KING -> {
for (int dr = -1; dr <= 1; dr++)
for (int dc = -1; dc <= 1; dc++)
if (dr != 0 || dc != 0) addStep(out, r, c, dr, dc);
}
case BISHOP, ROOK -> { /* 见下方滑动棋子处理 */ }
default -> { }
}
// 成棋的额外走法：龙马加四正方向一步，龙王加四斜方向一步
if (pro) {
if (type == BISHOP) {
for (int[] d : new int[][]{{-1,0},{1,0},{0,-1},{0,1}}) addStep(out, r, c, d[0], d[1]);
} else if (type == ROOK) {
for (int[] d : new int[][]{{-1,-1},{-1,1},{1,-1},{1,1}}) addStep(out, r, c, d[0], d[1]);
}
}
return out;
}
addStep 只做边界检查，真正的”是否能落”由外层 legalMoves 统一判断（不能吃己方棋子）。
三、打入：将棋的灵魂与二步禁手
打入（打ち）把吃掉的棋子放回棋盘空格。它带来了三条硬约束：
约束一：只能打入手的棋子。 hand[side][type] > 0。
约束二：二步（二歩）禁手。 同一列上不能出现两个己方的未成歩。
/** 该列是否已有己方"未成"的歩——判定二歩禁手 */
boolean pawnInColumn(int side, int col) {
for (int r = 0; r < 9; r++) {
int p = board[r * 9 + col];
if (p != 0 && pieceSide(p) == side && pieceType(p) == PAWN && !promoted(p)) {
return true;
}
}
return false;
}
注意这里必须排除”と金”（成歩）——升变后的歩不算二歩。
约束三：行き所のない駒（无路可走的打入）禁手。 歩、香不能打到最后一行；桂不能打到最后两行。因为打进去就永远动不了，等于送死。
boolean canDropAt(int side, int type, int row) {
int last = side == 0 ? 0 : 8;
int last2 = side == 0 ? 1 : 7;
return switch (type) {
case PAWN, LANCE -> row != last;
case KNIGHT -> row != last && row != last2;
default -> true;
};
}
约束四：打步诘（打ち歩詰め）禁手。 用打入的歩直接将死对方是违规的。这是将棋最难实现的规则之一，因为它需要在生成走法时试走一遍判断是否将死，并且要区分”是打入的歩造成的将死”还是”己方其他棋子的将死”。
工程上的折中做法：先生成打入歩的走法，对每个走法执行 isCheckmate(opponent)，若成立则剔除。判断一次将死的代价约等于做一次浅层搜索，但打入歩的数量很少（最多 9 列），开销可以接受。
/** 判断 side 是否被将死 */
boolean isCheckmate(int side) {
if (!inCheck(side)) return false;
for (int[] move : generateAllMoves(side)) {
doMove(move);
boolean stillCheck = inCheck(side);
undoMove(move);
if (!stillCheck) return false;
}
return true;
}
四、完整实现
import java.util.*;
public class Main {
static final int N = 9;
static final int EMPTY = 0;
static final int PAWN = 1, LANCE = 2, KNIGHT = 3, SILVER = 4,
GOLD = 5, BISHOP = 6, ROOK = 7, KING = 8;
static final int PIECE_MASK = 0x0F, SIDE_MASK = 0x10, PROMO_MASK = 0x20;
static int make(int type, int side, boolean pro) {
return type | (side << 4) | (pro ? PROMO_MASK : 0);
}
static int type(int p) { return p & PIECE_MASK; }
static int side(int p) { return (p >> 4) & 1; }
static boolean pro(int p) { return (p & PROMO_MASK) != 0; }
// 棋子名称（用于调试输出）
static final String[] NAMES = {"", "歩", "香", "桂", "銀", "金", "角", "飛", "玉"};
static final String[] PROMO_NAMES = {"", "と", "成香", "成桂", "成銀", "金", "龍馬", "龍王", "玉"};
static String pieceName(int p) {
if (p == EMPTY) return " ・";
String base = pro(p) ? PROMO_NAMES[type(p)] : NAMES[type(p)];
return (side(p) == 0 ? "▲" : "△") + base;
}
// ---------------- 棋盘与手牌 ----------------
final int[] board = new int[N * N];
final int[][] hand = new int[2][9];
int turn = 0;
// ---------------- 升变规则 ----------------
static boolean inPromoZone(int side, int row) {
return side == 0 ? row <= 2 : row >= 6;
}
static boolean canPromote(int side, int fromRow, int toRow, int t) {
if (t == GOLD || t == KING) return false;
return inPromoZone(side, fromRow) || inPromoZone(side, toRow);
}
static boolean mustPromote(int side, int toRow, int t) {
int last = side == 0 ? 0 : 8;
int last2 = side == 0 ? 1 : 7;
return switch (t) {
case PAWN, LANCE -> toRow == last;
case KNIGHT -> toRow == last || toRow == last2;
default -> false;
};
}
// ---------------- 走法生成 ----------------
static final int[][] GOLD_DELTA = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,0}};
static final int[][] KING_DELTA = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
boolean inBoard(int r, int c) { return r >= 0 && r < N && c >= 0 && c < N; }
/** 生成伪合法走法（不做自将判定），结果写入 out */
void genPseudo(int s, List<int[]> out) {
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
int p = board[r * N + c];
if (p == EMPTY || side(p) != s) continue;
int t = type(p);
boolean pr = pro(p);
int fwd = s == 0 ? -1 : 1;
// ---- 成棋的走法归并 ----
int effType = t;
if (pr && (t == PAWN || t == LANCE || t == KNIGHT || t == SILVER)) {
effType = GOLD;
}
switch (effType) {
case PAWN -> stepMoves(s, r, c, new int[][]{{fwd,0}}, out);
case KNIGHT -> stepMoves(s, r, c,
new int[][]{{2*fwd,-1},{2*fwd,1}}, out);
case SILVER -> stepMoves(s, r, c, new int[][]{
{fwd,-1},{fwd,0},{fwd,1},{-fwd,-1},{-fwd,1}}, out);
case GOLD -> stepMoves(s, r, c, new int[][]{
{fwd,-1},{fwd,0},{fwd,1},{-fwd,0},{0,-1},{0,1}}, out);
case KING -> stepMoves(s, r, c, KING_DELTA, out);
case BISHOP -> {
slideMoves(s, r, c, new int[][]{{-1,-1},{-1,1},{1,-1},{1,1}}, out);
if (pr) stepMoves(s, r, c, new int[][]{{-1,0},{1,0},{0,-1},{0,1}}, out);
}
case ROOK -> {
slideMoves(s, r, c, new int[][]{{-1,0},{1,0},{0,-1},{0,1}}, out);
if (pr) stepMoves(s, r, c, new int[][]{{-1,-1},{-1,1},{1,-1},{1,1}}, out);
}
default -> { }
}
}
}
}
/** 单步走法：只检查边界与是否吃己方 */
void stepMoves(int s, int r, int c, int[][] deltas, List<int[]> out) {
int from = r * N + c;
int p = board[from];
int t = type(p);
for (int[] d : deltas) {
int nr = r + d[0], nc = c + d[1];
if (!inBoard(nr, nc)) continue;
int np = board[nr * N + nc];
if (np != EMPTY && side(np) == s) continue;
int to = nr * N + nc;
emitWithPromotion(s, from, to, r, nr, t, out);
}
}
/** 滑动棋子：沿方向一直走直到被阻挡 */
void slideMoves(int s, int r, int c, int[][] dirs, List<int[]> out) {
int from = r * N + c;
int t = type(board[from]);
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
while (inBoard(nr, nc)) {
int np = board[nr * N + nc];
int to = nr * N + nc;
if (np == EMPTY) {
emitWithPromotion(s, from, to, r, nr, t, out);
} else {
if (side(np) != s) emitWithPromotion(s, from, to, r, nr, t, out);
break; // 遇子即止
}
nr += d[0]; nc += d[1];
}
}
}
/**
* 统一处理升变旗标：flag = 0 表示保持原样，flag = 1 表示成。
* 强制升变（歩香桂走到无路可走处）只生成 flag = 1 一种走法；
* 可升可变时两种都生成，让搜索自己去选。
*/
void emitWithPromotion(int s, int from, int to, int fromRow, int toRow, int t, List<int[]> out) {
if (!canPromote(s, fromRow, toRow, t)) {
out.add(new int[]{from, to, 0}); // 无升变可选
return;
}
if (mustPromote(s, toRow, t)) {
out.add(new int[]{from, to, 1}); // 强制成
} else {
out.add(new int[]{from, to, 0}); // 不成
out.add(new int[]{from, to, 1}); // 成
}
}
/**
* 生成打入走法。约定：m[0] = -1 表示打入，m[2] = 2 标记类型，m[3] = 棋子种类。
*/
void genDrops(int s, List<int[]> out) {
for (int t = PAWN; t <= ROOK; t++) { // 玉不能打入
if (hand[s][t] == 0) continue;
// 二歩只需要逐列判断一次，把"有歩的列"预先算成布尔数组
boolean[] pawnCol = new boolean[N];
if (t == PAWN) {
for (int c = 0; c < N; c++) pawnCol[c] = pawnInColumn(s, c);
}
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (board[r * N + c] != EMPTY) continue; // 只能打在空格
if (!canDropAt(s, t, r)) continue; // 无路可走禁手
if (t == PAWN && pawnCol[c]) continue; // 二歩禁手
out.add(new int[]{-1, r * N + c, 2, t});
}
}
}
}
boolean pawnInColumn(int s, int col) {
for (int r = 0; r < N; r++) {
int p = board[r * N + col];
if (p != EMPTY && side(p) == s && type(p) == PAWN && !pro(p)) return true;
}
return false;
}
static boolean canDropAt(int s, int t, int row) {
int last = s == 0 ? 0 : 8;
int last2 = s == 0 ? 1 : 7;
return switch (t) {
case PAWN, LANCE -> row != last;
case KNIGHT -> row != last && row != last2;
default -> true;
};
}
// ---------------- 执行 / 撤销 ----------------
final Deque<int[]> history = new ArrayDeque<>();
void doMove(int[] m) {
int from = m[0], to = m[1], flag = m[2];
if (flag == 2) { // 打入
int t = m[3];
board[to] = make(t, turn, false);
hand[turn][t]--;
history.push(new int[]{-1, to, 2, t});
} else { // 盘上移动
int p = board[from];
int captured = board[to];
int np = p;
if (flag == 1) {
np = (p | PROMO_MASK); // 升变；flag = 0 表示保持原样
}
board[to] = np;
board[from] = EMPTY;
if (captured != EMPTY) {
// 被吃棋子去掉成标记、归入己方手牌（成棋回到基本型）
int ct = type(captured);
hand[turn][ct]++;
}
history.push(new int[]{from, to, flag, captured, p});
}
turn ^= 1;
}
void undoMove() {
int[] h = history.pop();
turn ^= 1;
if (h[2] == 2) { // 撤销打入
int t = h[3];
board[h[1]] = EMPTY;
hand[turn][t]++;
} else {
board[h[0]] = h[4];
board[h[1]] = h[3];
if (h[3] != EMPTY) hand[turn][type(h[3])]--;
}
}
// ---------------- 打印 ----------------
void printBoard() {
System.out.println(" ９ ８ ７ ６ ５ ４ ３ ２ １");
for (int r = 0; r < N; r++) {
StringBuilder sb = new StringBuilder();
sb.append((char) ('一' + r)).append(' ');
for (int c = 0; c < N; c++) sb.append(pieceName(board[r * N + c])).append(' ');
System.out.println(sb);
}
System.out.print("先手手牌: ");
for (int t = 1; t <= 8; t++)
if (hand[0][t] > 0) System.out.print(NAMES[t] + "×" + hand[0][t] + " ");
System.out.print("\n后手手牌: ");
for (int t = 1; t <= 8; t++)
if (hand[1][t] > 0) System.out.print(NAMES[t] + "×" + hand[1][t] + " ");
System.out.println();
}
// ---------------- 主程序 ----------------
public static void main(String[] args) {
Main g = new Main();
// 摆一个简化的初始局面（真实将棋还有香桂步各一排，这里便于演示而精简）
g.board[8 * N + 4] = make(KING, 0, false); // 先手玉在最下列中央
g.board[0 * N + 4] = make(KING, 1, false); // 后手玉在最上列中央
g.board[6 * N + 4] = make(PAWN, 0, false); // 先手歩
// 模拟：先手吃掉一个敌子，手牌 +1
g.board[3 * N + 4] = make(SILVER, 1, false);
g.hand[0][SILVER] = 1;
g.board[3 * N + 4] = EMPTY;
g.printBoard();
List<int[]> moves = new ArrayList<>();
g.genPseudo(0, moves);
List<int[]> drops = new ArrayList<>();
g.genDrops(0, drops);
System.out.println("\n先手可走: " + moves.size() + " 手，可打入: " + drops.size() + " 处");
System.out.println("示例走法（前 5 手，格式：起点→终点 旗标）:");
for (int i = 0; i < Math.min(5, moves.size()); i++) {
int[] m = moves.get(i);
System.out.printf(" 行%d列%d → 行%d列%d flag=%d%n",
m[0] / N, m[0] % N, m[1] / N, m[1] % N, m[2]);
}
// 验证升变：把先手歩推进到敌阵
System.out.println("\n升变规则验证:");
System.out.println(" (行6→行2 歩) 可成=" + canPromote(0, 6, 2, PAWN)
+ " 强制成=" + mustPromote(0, 0, PAWN));
System.out.println(" (行6→行1 桂) 可成=" + canPromote(0, 6, 1, KNIGHT)
+ " 强制成=" + mustPromote(0, 1, KNIGHT));
System.out.println(" (金) 可成=" + canPromote(0, 2, 1, GOLD));
// 验证二歩禁手
System.out.println("\n二歩检查: 第5列有先手歩=" + g.pawnInColumn(0, 4));
}
}
五、置换表：把”手牌”也编码进去
这是将棋引擎区别于象棋引擎的最关键设计。Zobrist 哈希要同时覆盖两部分：
- 盘面：
81 格 × 2 归属 × 2 成否 × 8 种类的随机数表； - 手牌：
2 归属 × 8 种类 × 数量 0~18的随机数增量。
手牌编码有个常用技巧：为每种 (归属, 种类, 数量) 预生成一个随机数，手牌变化时先 XOR 掉旧值再 XOR 新值。数量变化 1 时更新成本 O(1)。
private final long[][][][] zPiece = new long[81][2][2][9];
private final long[][][] zHand = new long[2][9][19]; // 数量 0..18
private long zKey;
private void xorHand(int s, int t, int oldQty, int newQty) {
zKey ^= zHand[s][t][oldQty] ^ zHand[s][t][newQty];
}
为什么手牌必须进哈希？ 如果只对盘面做哈希，那么”同样棋盘、但一方多了一个银在手”的两个局面会被判为相同——置换表会返回一个完全不同局面的搜索值，这是灾难性的错误。这也是将棋开源引擎（如 YaneuraOu）里手牌哈希实现格外讲究的原因。
六、搜索结构与性能
将棋的搜索主体仍是 Alpha-Beta + 迭代加深，但有三点将棋专属的优化：
1. 打入走法要排在最后。 打入通常不是最佳着法（浪费一手），放在移动走法之后能让剪枝更早生效。
2. 吃子走法优先。 将棋因手牌机制使得吃子价值高于象棋——吃一个银不仅能削弱对方，还给自己添了一个可打入的银。所以 MVV-LVA（最有价值受害者-最无价值攻击者）排序在将棋里效果特别显著。
3. 王手（将军）延伸。 被将军时强制延伸一层搜索，避免因深度不足而误判。
复杂度上：
| 深度 | 无剪枝节点 | Alpha-Beta 后 | 将棋平均分支因子 |
|---|---|---|---|
| 4 层 | 约 80^4 = 4×10^7 |
约 10^5 |
约 80（含打入） |
| 6 层 | 约 80^6 = 2.6×10^11 |
约 10^7 |
— |
将棋的分支因子（含打入约 80）比国际象棋（约 35）高出一倍多，这是它状态空间巨大的直接原因。也因此，置换表 + 走法排序 + 裁剪这三件套在将棋里的收益比象棋更大。
七、三个必须警惕的实现陷阱
陷阱一：吃下的成棋回到手牌要”还原”。 吃掉对方的”と金”，手里得到的是”歩”，不是”と金”。上面 doMove 里 int ct = type(captured) 已经通过 PIECE_MASK 自动剥离了成标记——但前提是你把成标记存在独立位上（PROMO_MASK）。如果把”成”编进种类编号（比如用 9~15 表示成棋），这里就必然出错。
陷阱二：二歩判断必须逐列。 有个常见错误是写成”该列有我方任何歩则禁止全盘打入歩”，那样会误禁其他列。正确做法是对每一列独立调用 pawnInColumn。
陷阱三：撤消时要精确还原 turn。 doMove 里最后 turn ^= 1，undoMove 里必须先把 turn 切回去再操作 hand[turn]——顺序颠倒会用错归属的数组。这类 bug 极难发现，因为它在单步测试里完全正常，只有在搜索树里才会暴露成”分数莫名其妙偏低”。
八、小结
将棋引擎的复杂度几乎全部来自”盘面之外还有一层手牌状态“。一旦接受这个双层结构，剩下的都是常规工程：
- 走法生成 → 预计算偏移表 + 边界检查；
- 升变 → 三条规则的精确编码（敌阵范围、强制升、成后走法表）；
- 打入 → 四条禁手的逐条校验；
- 哈希 → 盘面 Zobrist + 手牌数量增量。
最值得带走的一条经验是：规则的复杂度不会消失，只会转移。把”歩香桂銀成后全变金”这条规则写进 effType 归并那一行，比在八个 switch 分支里各写一遍要安全得多——能用一个映射表表达的规则，就绝不要用分散的条件判断。
