中国象棋 AI 策略实现：从启发式评估到 AlphaZero MCTS
中国象棋 AI 策略实现：从启发式评估到 AlphaZero MCTS
井九
发布于 2025-11-22 08:39:27
发布于 2025-11-22 08:39:27
前言：为什么中国象棋 AI 很难？
相比国际象棋，中国象棋的挑战来自多个方面：
- 棋盘更大（90 格），搜索分支爆炸得更快
- 子力规则更特殊：例如炮的隔山打牛、象眼、马脚、不能过河的象
- 局面重复与长将规则更复杂（长将判负、长捉、三次重复和棋）
- 残局变化极深（例如双马士相全 vs 将）
因此，中国象棋 AI 的核心可以概括为：
评估函数 + 剪枝 + 置换表 + 启发式排序 + 搜索算法（AlphaBeta 或 MCTS）
本文将从最基础的策略讲起，一步步构建完整的 AI 策略体系。
demo
一、最简单的 AI：随机走棋
最初级的 AI 写法非常简单：
const moves = generateMoves(board, color);
return moves[Math.floor(Math.random() * moves.length)];特征：
- 不会评估局势
- 不懂送子与吃子
- 完全靠运气
属于“娱乐用 AI”。
二、朴素启发式：子力价值表（Material Value）
为了让 AI 能“吃大子不吃小子”，我们需要引入子力价值：
const VAL = new Int16Array(23);
VAL[R_KING]=10000;
VAL[R_ROOK]=900;
VAL[R_CANNON]=450;
VAL[R_HORSE]=400;
VAL[R_ADV]=120;
VAL[R_ELE]=120;
VAL[R_PAWN]=50;这一层让 AI 具备基本棋力：
- 能主动吃子
- 不乱送子
- 能进行合理交换
但没有位置判断时，兵不过河与兵冲入腹地价值相同，因此棋力依然有限。
三、引入 PST：位置评分（Piece-Square Table）
你提供的代码中包含完整的中国象棋 PST，这是让 AI 棋力大幅提升的关键技术。
PST 的作用：
- 同一枚棋子在不同位置价值不同
- 能表达布局观念
- 能自动学习“兵过河更强”“车抢肋道”等行为
示例：兵的 PST（简化版）：
const PST_PAWN_RED = new Int16Array([
9, 9, 9, 11, 13, 11, 9, 9, 9,
19,24,34, 40, 40, 40,34, 24, 19,
...
]);车的 PST 强调：
- 肋道（C、G 列）
- 河界线路（4、5 行）
const PST_ROOK_RED = new Int16Array([
14,14,12,18,16,18,12,14,14,
16,20,18,24,26,24,18,20,16,
...
]);AI 因此可以自然表现出：
- 车占肋道
- 兵过河强
- 卧槽马
- 炮归家、沉底炮
这是从弱 AI 到中级 AI 的关键步骤。
黑方 PST 的自动翻转技巧
你的实现非常专业：
PST_FLAT[p*90 + i] = PST_TABLE[p][89 - i];只需定义红方 PST，黑方自动镜像即可。这是专业象棋引擎的常规做法。
四、Zobrist Hash：局面哈希
象棋 AI 需要频繁判断“局面是否重复”，用于：
- 三次重复和棋
- 长将判负
- 置换表加速搜索
你采用的是经典的 Zobrist hashing：
const ZOBRIST = new Uint32Array(23*90);
for(let i=0;i<ZOBRIST.length;i++)
ZOBRIST[i] = (Math.random()*0xFFFFFFFF)>>>0;基于 XOR 可进行 O(1) 的增量更新：
h ^= ZOBRIST[piece * 90 + pos];五、置换表（Transposition Table）
你的 TT 结构非常完整：
const TT_BUCKET_COUNT = 1<<20;
const tt_keys = new Uint32Array(TT_SIZE);
const tt_scores = new Int32Array(TT_SIZE);
const tt_depths = new Int8Array(TT_SIZE);
const tt_flags = new Int8Array(TT_SIZE);作用：
- 避免重复搜索
- 保存最佳走法
- 结合 AlphaBeta 能显著加速（甚至几十倍）
属于强力象棋 AI 的核心组件。
六、走法排序（Move Ordering）
走法排序越好，AlphaBeta 剪枝越充分。
你实现了两个关键机制：
1. Killer Moves
this.killer = Array.from({length:256}, ()=>[0,0]);当某个走法导致剪枝时，将其记录为 killer move，后续搜索优先尝试。
提升极大。
2. History Heuristic
this.history = new Int32Array(65536);记录“过去表现好的走法”，未来优先。
两者能让搜索迅速走向高价值分支。
七、AlphaBeta 搜索与剪枝
象棋 AI 的核心算法。
流程：
- 深度优先搜索
- 维护 alpha 与 beta
- 不可能更优的分支立即剪枝
搭配 PST、置换表、排序之后，棋力能跃升一个数量级。
八、迭代加深（Iterative Deepening）
专业引擎必备：
深度 1 → 深度 2 → ... → 深度 N上一层结果用于下一层的排序依据，提高稳定性与速度。
你的代码中 onProgress 用于记录每一层的搜索状态。
九、开局库（Opening Book）
你的 AI 还支持开局库：
import { getOpeningBookMove } from './openingbook';作用：
- 前 10–20 手不靠搜索
- 直接走专业布局
- 提高棋力并节省大量时间
是实战能力的重要提升。
十、走向 AlphaZero：MCTS + 神经网络
当传统 AlphaBeta 到达上限，我们就进入 AlphaZero 体系：
NN 输出：
- P：走法概率
- V：局面价值
MCTS 进行搜索，取代 AlphaBeta。
优点：
- NN 自动学习象棋规律
- 不需要人类手写评估函数
- 效果强于绝大多数传统引擎
缺点：
- 训练成本高
- 动作空间更复杂（中国象棋比国际象棋难编码）
中国象棋版 AlphaZero 的挑战
- 90 格输入更大
- 炮、马、象规则复杂
- 三次重复与长将判负更难处理
- 动作输出空间更大
但已有多个开源项目证明这条路线完全可行。
十一、如何让你的引擎升级到 AlphaZero 风格？
方向如下：
1. 用神经网络替代评估函数
输入：10×9×plane 编码 输出：
- 走法概率分布 P
- 局面价值 V
2. 构建 MCTS 结构
每个节点存储：
N(s,a)
W(s,a)
Q(s,a)
P(s,a)3. 使用 PUCT 选择公式
UCB = Q + c_puct * P * sqrt(sum(N)) / (1 + N)4. 自对弈训练
MCTS → 下棋 → 记录 (state, π, z) → 训练 → 更新模型循环即可让模型不断增强。
核心代码
import { getOpeningBookMove } from './openingbook';
export const R_KING = 8, R_ADV = 9, R_ELE = 10, R_HORSE = 11, R_ROOK = 12, R_CANNON = 13, R_PAWN = 14;
export const B_KING = 16, B_ADV = 17, B_ELE = 18, B_HORSE = 19, B_ROOK = 20, B_CANNON = 21, B_PAWN = 22;
export const COLOR_RED = 8;
export const COLOR_BLACK = 16;
// 基本子力
const VAL = new Int16Array(23);
VAL[R_KING]=10000; VAL[R_ADV]=120; VAL[R_ELE]=120; VAL[R_HORSE]=400; VAL[R_ROOK]=900; VAL[R_CANNON]=450; VAL[R_PAWN]=50;
VAL[B_KING]=10000; VAL[B_ADV]=120; VAL[B_ELE]=120; VAL[B_HORSE]=400; VAL[B_ROOK]=900; VAL[B_CANNON]=450; VAL[B_PAWN]=50;
// 增强版 PST (Piece-Square Tables) - 基于红方视角 (index 0-89)
// 红方大本营在 index 81-89 (Row 9), 进攻方向是 index 减小
// 黑方大本营在 index 0-8 (Row 0), 进攻方向是 index 增加
// 我们定义红方的 PST，黑方读取时取 (89 - index)
const PST_TABLE: Int16Array[] = new Array(23);
// 兵: 过河后价值提升，靠近九宫格价值提升
const PST_PAWN_RED = new Int16Array([
9, 9, 9, 11, 13, 11, 9, 9, 9, // Row 0 (Enemy Base)
19, 24, 34, 40, 40, 40, 34, 24, 19, // Row 1
7, 12, 16, 18, 18, 18, 16, 12, 7, // Row 2
7, 10, 13, 15, 15, 15, 13, 10, 7, // Row 3
5, 5, 5, 5, 5, 5, 5, 5, 5, // Row 4 (River)
0, 0, 0, 0, 0, 0, 0, 0, 0, // Row 5 (River)
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0 // Row 9 (Base)
]);
// 车: 抢占肋道(col 3,5)和巡河(row 4,5)
const PST_ROOK_RED = new Int16Array([
14, 14, 12, 18, 16, 18, 12, 14, 14,
16, 20, 18, 24, 26, 24, 18, 20, 16,
12, 12, 12, 18, 18, 18, 12, 12, 12,
12, 18, 16, 22, 22, 22, 16, 18, 12,
12, 14, 12, 18, 18, 18, 12, 14, 12,
12, 16, 14, 20, 20, 20, 14, 16, 12,
6, 10, 8, 14, 14, 14, 8, 10, 6,
4, 8, 6, 14, 12, 14, 6, 8, 4,
8, 4, 8, 16, 8, 16, 8, 4, 8,
-2, 10, 6, 14, 12, 14, 6, 10, -2
]);
// 马: 进攻时跳卧槽，防守时守中兵
const PST_HORSE_RED = new Int16Array([
4, 8, 16, 12, 4, 12, 16, 8, 4,
4, 10, 28, 16, 8, 16, 28, 10, 4,
12, 14, 16, 20, 18, 20, 16, 14, 12,
8, 24, 18, 24, 20, 24, 18, 24, 8,
6, 16, 14, 18, 16, 18, 14, 16, 6,
4, 12, 16, 14, 12, 14, 16, 12, 4,
2, 6, 8, 6, 10, 6, 8, 6, 2,
4, 2, 6, 4, 4, 4, 6, 2, 4,
0, 2, 4, 4, 4, 4, 4, 2, 0,
0, -4, 0, 0, 0, 0, 0, -4, 0
]);
// 炮: 炮归家，沉底炮
const PST_CANNON_RED = new Int16Array([
6, 4, 0, -10, -12, -10, 0, 4, 6,
2, 2, 0, -4, -14, -4, 0, 2, 2,
2, 2, 0, -10, -8, -10, 0, 2, 2,
0, 0, -2, 4, 10, 4, -2, 0, 0,
0, 0, 0, 2, 4, 2, 0, 0, 0,
-2, 0, 4, 2, 6, 2, 4, 0, -2,
0, 0, 0, 2, 4, 2, 0, 0, 0,
4, 0, 8, 6, 10, 6, 8, 0, 4,
0, 2, 4, 6, 6, 6, 4, 2, 0,
0, 0, 2, 6, 6, 6, 2, 0, 0
]);
// 士/相/帅: 主要是防守位置
const PST_ADVISOR = new Int16Array(90).fill(0);
const PST_ELEPHANT = new Int16Array(90).fill(0);
const PST_KING = new Int16Array(90).fill(0);
// 简单填充防守分
[76, 84, 86].forEach(i => PST_ADVISOR[i] = 20); // 仕在九宫
[47, 51, 63, 65, 67, 71, 83, 87].forEach(i => PST_ELEPHANT[i] = 20); // 相位
[84, 85, 86, 75, 76, 77].forEach(i => PST_KING[i] = 10); // 帅在九宫
// 注册到 PST_TABLE
PST_TABLE[R_PAWN] = PST_PAWN_RED;
PST_TABLE[R_ROOK] = PST_ROOK_RED;
PST_TABLE[R_HORSE] = PST_HORSE_RED;
PST_TABLE[R_CANNON] = PST_CANNON_RED;
PST_TABLE[R_ADV] = PST_ADVISOR;
PST_TABLE[R_ELE] = PST_ELEPHANT;
PST_TABLE[R_KING] = PST_KING;
// 黑方复用红方数组，但在 evaluate 时 index = 89 - i
// 为了方便 key 查找，映射一下
PST_TABLE[B_PAWN] = PST_PAWN_RED;
PST_TABLE[B_ROOK] = PST_ROOK_RED;
PST_TABLE[B_HORSE] = PST_HORSE_RED;
PST_TABLE[B_CANNON] = PST_CANNON_RED;
PST_TABLE[B_ADV] = PST_ADVISOR;
PST_TABLE[B_ELE] = PST_ELEPHANT;
PST_TABLE[B_KING] = PST_KING;
// 构建优化后的扁平 PST 表 (包含黑方翻转)
const PST_FLAT = new Int16Array(23 * 90);
for(let p=0; p<23; p++) {
if(!PST_TABLE[p]) continue;
for(let i=0; i<90; i++) {
// 如果是红棋 (8-14)，直接复制
if (p >= 8 && p <= 14) {
PST_FLAT[p*90 + i] = PST_TABLE[p][i];
}
// 如果是黑棋 (16-22)，翻转索引复制
else if (p >= 16 && p <= 22) {
PST_FLAT[p*90 + i] = PST_TABLE[p][89-i];
}
}
}
// Zobrist
const ZOBRIST = new Uint32Array(23*90);
let ZOBRIST_SIDE = (Math.random()*0xFFFFFFFF) >>> 0;
for(let i=0;i<ZOBRIST.length;i++) ZOBRIST[i] = (Math.random()*0xFFFFFFFF)>>>0;
// Transposition Table (数组实现)
// 4-way associative hashing
// Total entries = TT_BUCKET_COUNT * 4
const TT_BUCKET_COUNT = 1<<20; // 1M buckets
const TT_SIZE = TT_BUCKET_COUNT * 4; // 4M entries total
const tt_keys = new Uint32Array(TT_SIZE); // 存 hash
const tt_scores = new Int32Array(TT_SIZE);
const tt_depths = new Int8Array(TT_SIZE);
const tt_flags = new Int8Array(TT_SIZE);
const tt_moves = new Uint16Array(TT_SIZE); // 存储 MOVE
const TT_FLAG_EXACT=0, TT_FLAG_LOWER=1, TT_FLAG_UPPER=2;
// Move Generation Constants
const DIRS_ROOK_CANNON = [-1, 1, -9, 9];
const HORSE_STEPS = [
{d:-19,leg:-9},{d:-17,leg:-9},{d:17,leg:9},{d:19,leg:9},
{d:-11,leg:-1},{d:7,leg:-1},{d:-7,leg:1},{d:11,leg:1}
];
const ELEPHANT_OFFS = [
{d:-20,eye:-10,dr:-2,dc:-2},{d:-16,eye:-8,dr:-2,dc:2},
{d:16,eye:8,dr:2,dc:-2},{d:20,eye:10,dr:2,dc:2}
];
const ADVISOR_OFFS = [-10,-8,8,10];
const KING_OFFS = [-9,9,-1,1];
// 工具函数
export const SRC = (m: number)=> (m>>>8)&0xFF;
export const DST = (m: number)=> m & 0xFF;
export const MOVE = (s: number, d: number)=> (((s&0xFF)<<8)|(d&0xFF)) >>> 0;
export class Engine {
board: Int8Array;
color: number;
killer: number[][];
history: Int32Array;
moveBuffers: number[][]; // Pre-allocated buffers for move generation
nodes: number;
timeLimit: number;
startTime: number;
stop: boolean;
hashHistory: number[];
gameHistory: number[]; // 全局游戏历史 (用于检测长将/重复局面)
ply: number;
maxDepthReached: number;
// Incremental Hash
currentHash: number;
// Incremental Score
currentRedScore: number;
currentBlackScore: number;
// Cache King positions for performance
redKingPos: number;
blackKingPos: number;
onProgress: ((progress: { depth: number, score: number, move: number, nodes: number, time: number, pv?: number[] }) => void) | null = null;
constructor() {
this.board = new Int8Array(90);
this.color = COLOR_RED;
this.killer = Array.from({length:256}, ()=>[0,0]); // Increased size
this.history = new Int32Array(65536); // Fix: Increased size to cover all move encodings
this.moveBuffers = Array.from({length: 256}, () => []); // Buffer for moves at each ply
this.nodes = 0;
this.timeLimit = 1000;
this.startTime = 0;
this.stop=false;
this.hashHistory = [];
this.gameHistory = [];
this.ply=0;
this.maxDepthReached = 0;
this.currentHash = 0;
this.currentRedScore = 0;
this.currentBlackScore = 0;
this.redKingPos = -1;
this.blackKingPos = -1;
}
loadBoard(uiBoard: any[][], turnColor: string){
// console.log("Engine: loadBoard called");
this.board.fill(0);
this.redKingPos = -1;
this.blackKingPos = -1;
for(let r=0;r<10;r++) for(let c=0;c<9;c++){
const cell = uiBoard[r][c];
if(!cell) continue;
let p=0;
if(cell.color==='red'){
if(cell.type==='general') { p=R_KING; this.redKingPos = r*9+c; }
if(cell.type==='advisor') p=R_ADV;
if(cell.type==='elephant') p=R_ELE;
if(cell.type==='horse') p=R_HORSE;
if(cell.type==='chariot') p=R_ROOK;
if(cell.type==='cannon') p=R_CANNON;
if(cell.type==='soldier') p=R_PAWN;
} else {
if(cell.type==='general') { p=B_KING; this.blackKingPos = r*9+c; }
if(cell.type==='advisor') p=B_ADV;
if(cell.type==='elephant') p=B_ELE;
if(cell.type==='horse') p=B_HORSE;
if(cell.type==='chariot') p=B_ROOK;
if(cell.type==='cannon') p=B_CANNON;
if(cell.type==='soldier') p=B_PAWN;
}
this.board[r*9+c]=p;
}
this.color = turnColor==='red'?COLOR_RED:COLOR_BLACK;
// Fallback if not found (should not happen in valid board)
if (this.redKingPos === -1) this.redKingPos = this.findKing(COLOR_RED);
if (this.blackKingPos === -1) this.blackKingPos = this.findKing(COLOR_BLACK);
// Initialize Hash
this.currentHash = this.getHash();
// Initialize Score
this.currentRedScore = 0;
this.currentBlackScore = 0;
for(let i=0; i<90; i++) {
const p = this.board[i];
if(p) {
const val = VAL[p] + PST_FLAT[p*90 + i];
if(p & COLOR_RED) this.currentRedScore += val;
else this.currentBlackScore += val;
}
}
}
setGameHistory(history: number[]) {
this.gameHistory = [...history];
}
getBoardHash() {
return this.currentHash;
}
getHash(){
let h=0;
if(this.color===COLOR_BLACK) h ^= ZOBRIST_SIDE;
for(let i=0;i<90;i++){ const p=this.board[i]; if(p) h ^= ZOBRIST[p*90 + i]; }
return h>>>0;
}
// 找king位置 (Legacy method, now used for fallback or verification)
findKing(col: number){
for(let i=0;i<90;i++){ const p=this.board[i]; if(p && (p & col) && ((p===R_KING)||(p===B_KING))) return i; }
return -1;
}
getKingPos(col: number) {
return (col === COLOR_RED) ? this.redKingPos : this.blackKingPos;
}
// 判断某方是否被将
isAttacked(sq: number, byColor: number){
// 简单暴力：遍历敌方子力，按其类型判断是否能攻击 sq（不检查将帅对脸）
const enemy = byColor;
// 车/炮/马/兵/相/仕/将基础判断
// 方向数组
// 车/炮
for(let d of DIRS_ROOK_CANNON){
let dst = sq + d;
while(dst>=0 && dst<90){
// Check for wrap-around
if (Math.abs(d) === 1) {
// Horizontal move: must stay on same row
if ((dst / 9 | 0) !== ((dst - d) / 9 | 0)) break;
} else {
// Vertical move: must stay on same column (implicit by +/- 9 but good to be safe)
}
const p = this.board[dst];
if(!p) dst+=d; else {
if((p & enemy) && ((p===R_ROOK)||(p===B_ROOK))) return true;
// 炮需要跳一个子
let dst2 = dst + d; // 继续找炮架
while(dst2>=0 && dst2<90){
if (Math.abs(d) === 1) {
if ((dst2 / 9 | 0) !== ((dst2 - d) / 9 | 0)) break;
}
const p2 = this.board[dst2];
if(p2){ if((p2 & enemy) && ((p2===R_CANNON)||(p2===B_CANNON))) return true; break; }
dst2+=d;
}
break;
}
}
}
// 马 (Fixed: Check if enemy horse at 'src' can jump to 'sq')
for(let m of HORSE_STEPS){
const src = sq - m.d; // Potential enemy horse position
if(src>=0 && src<90){
const sr = src / 9 | 0;
const sc = src % 9;
const tr = sq / 9 | 0;
const tc = sq % 9;
// Strict geometry check
if ((Math.abs(sr - tr) === 1 && Math.abs(sc - tc) === 2) ||
(Math.abs(sr - tr) === 2 && Math.abs(sc - tc) === 1)) {
const p = this.board[src];
if(p && (p & enemy) && ((p===R_HORSE)||(p===B_HORSE))){
const leg = src + m.leg; // Leg position relative to src
if(this.board[leg]===0) return true;
}
}
}
}
// 兵的攻击 (修正版)
const r = (sq/9)|0;
const c = sq%9;
if (enemy === COLOR_RED) {
// 红兵攻击 sq: 兵在 sq+9 (身后), 或者 (如果 sq 在红方过河后 r<5) 兵在 sq-1, sq+1
if (sq+9 < 90 && this.board[sq+9] === R_PAWN) return true;
// 红兵过河后(Row 0-4)可以横吃
// 如果 sq 在 Row 0-4, 左右的红兵可能攻击它
if (r < 5) {
if (c > 0 && this.board[sq-1] === R_PAWN) return true;
if (c < 8 && this.board[sq+1] === R_PAWN) return true;
}
} else {
// 黑兵攻击 sq: 兵在 sq-9 (身后), 或者 (如果 sq 在黑方过河后 r>4) 兵在 sq-1, sq+1
if (sq-9 >= 0 && this.board[sq-9] === B_PAWN) return true;
// 黑兵过河后(Row 5-9)可以横吃
if (r > 4) {
if (c > 0 && this.board[sq-1] === B_PAWN) return true;
if (c < 8 && this.board[sq+1] === B_PAWN) return true;
}
}
return false;
}
// 将帅对脸
kingsFaceToFace(){
const k1 = this.redKingPos;
const k2 = this.blackKingPos;
if(k1<0||k2<0) return false;
if((k1%9)!==(k2%9)) return false;
// const col = k1%9;
const s = Math.min(k1,k2)+9;
for(let i=s;i<Math.max(k1,k2);i+=9){ if(this.board[i]) return false; }
return true; // face to face
}
// 生成伪合法走子（不过滤王被将）
generateMoves(onlyCaptures=false){
// Use pre-allocated buffer for the current ply to reduce GC
const moves = (this.ply < this.moveBuffers.length) ? this.moveBuffers[this.ply] : [];
moves.length = 0;
const self = this.color;
const enemy = (self===COLOR_RED)?COLOR_BLACK:COLOR_RED;
for(let src=0;src<90;src++){
const p=this.board[src]; if(!p || (p & self)===0) continue;
const r = (src/9)|0; const c = src%9;
// 车/炮
if(p===R_ROOK||p===B_ROOK||p===R_CANNON||p===B_CANNON){
for(let d of DIRS_ROOK_CANNON){
let dst=src+d;
let jump=false;
while(dst>=0 && dst<90) {
// Strict row/column check
if (Math.abs(d) === 1) {
// Horizontal: must be same row
if ((dst/9|0) !== (src/9|0)) break;
} else {
// Vertical: implicit check by +/- 9, but bounds checked by loop
}
const t=this.board[dst];
if(!t){
if(!jump && !onlyCaptures) moves.push(MOVE(src,dst));
dst+=d;
} else {
if(p===R_ROOK||p===B_ROOK){
if(t & enemy) moves.push(MOVE(src,dst));
break;
} else {
// Cannon
if(jump){
if(t & enemy) moves.push(MOVE(src,dst));
break;
}
jump=true;
dst+=d;
}
}
}
}
}
// 马
else if(p===R_HORSE||p===B_HORSE){
for(let m of HORSE_STEPS){
const leg = src + m.leg;
const to = src + m.d;
if(leg>=0 && leg<90 && to>=0 && to<90) {
// Strict geometry check for Horse move
const sr = r, sc = c;
const tr = (to/9)|0, tc = to%9;
if (!((Math.abs(sr-tr)===1 && Math.abs(sc-tc)===2) || (Math.abs(sr-tr)===2 && Math.abs(sc-tc)===1))) continue;
if(this.board[leg]===0) {
const tgt = this.board[to];
if(tgt===0){ if(!onlyCaptures) moves.push(MOVE(src,to)); }
else if(tgt & enemy) moves.push(MOVE(src,to));
}
}
}
}
// 象
else if(p===R_ELE||p===B_ELE){
for(let o of ELEPHANT_OFFS){
const tr = r + o.dr; const tc = c + o.dc;
if(tr>=0&&tr<10&&tc>=0&&tc<9){
if((p===R_ELE && tr<5) || (p===B_ELE && tr>4)) continue;
if(this.board[src+o.eye]===0) {
const dst = src+o.d;
const tgt = this.board[dst];
if(tgt===0){ if(!onlyCaptures) moves.push(MOVE(src,dst)); }
else if(tgt & enemy) moves.push(MOVE(src,dst));
}
}
}
}
// 仕
else if(p===R_ADV||p===B_ADV){
for(let o of ADVISOR_OFFS){
const to=src+o;
if(to>=0&&to<90){
const dr=(to/9)|0, dc=to%9;
if(dc<3||dc>5) continue;
if((p===R_ADV && dr<7) || (p===B_ADV && dr>2)) continue;
const tgt = this.board[to];
if(tgt===0){ if(!onlyCaptures) moves.push(MOVE(src,to)); }
else if(tgt & enemy) moves.push(MOVE(src,to));
}
}
}
// 将
else if(p===R_KING||p===B_KING){
for(let o of KING_OFFS){
const to=src+o;
if(to>=0&&to<90 && Math.abs((to%9)-c)<=1){
const dr=(to/9)|0, dc=to%9;
if(dc<3||dc>5) continue;
if((p===R_KING && dr<7) || (p===B_KING && dr>2)) continue;
const tgt = this.board[to];
if(tgt===0){ if(!onlyCaptures) moves.push(MOVE(src,to)); }
else if(tgt & enemy) moves.push(MOVE(src,to));
}
}
}
// 兵
else if(p===R_PAWN||p===B_PAWN){
const forward = (p & COLOR_RED)? -9:9;
const to=src+forward;
if(to>=0&&to<90) {
const tgt = this.board[to];
if(tgt===0){ if(!onlyCaptures) moves.push(MOVE(src,to)); }
else if(tgt & enemy) moves.push(MOVE(src,to));
}
const rDst = (src/9|0);
// Red crosses river at row 4 (moving to 4, 3, 2, 1, 0)
// Black crosses river at row 5 (moving to 5, 6, 7, 8, 9)
const crossed = (p & COLOR_RED)? (rDst<=4):(rDst>=5);
if(crossed){
if((src%9)>0) {
const dst = src-1;
const tgt = this.board[dst];
if(tgt===0){ if(!onlyCaptures) moves.push(MOVE(src,dst)); }
else if(tgt & enemy) moves.push(MOVE(src,dst));
}
if((src%9)<8) {
const dst = src+1;
const tgt = this.board[dst];
if(tgt===0){ if(!onlyCaptures) moves.push(MOVE(src,dst)); }
else if(tgt & enemy) moves.push(MOVE(src,dst));
}
}
}
}
return moves;
}
// make / undo（注意维护 hash & history）
makeMoveRaw(move: number){
const s=SRC(move), d=DST(move);
const cap=this.board[d];
const pc=this.board[s];
// Incremental Hash Update
this.currentHash ^= ZOBRIST[pc * 90 + s]; // Remove from src
if (cap) this.currentHash ^= ZOBRIST[cap * 90 + d]; // Remove captured
this.currentHash ^= ZOBRIST[pc * 90 + d]; // Add to dst
this.currentHash ^= ZOBRIST_SIDE; // Toggle side
// Incremental Score Update
// 1. Remove pc from s
const valSrc = VAL[pc] + PST_FLAT[pc*90 + s];
if (pc & COLOR_RED) this.currentRedScore -= valSrc;
else this.currentBlackScore -= valSrc;
// 2. Remove cap from d
if (cap) {
const valCap = VAL[cap] + PST_FLAT[cap*90 + d];
if (cap & COLOR_RED) this.currentRedScore -= valCap;
else this.currentBlackScore -= valCap;
}
// 3. Add pc to d
const valDst = VAL[pc] + PST_FLAT[pc*90 + d];
if (pc & COLOR_RED) this.currentRedScore += valDst;
else this.currentBlackScore += valDst;
this.board[d]=pc;
this.board[s]=0;
// Update King Position
if (pc === R_KING) this.redKingPos = d;
else if (pc === B_KING) this.blackKingPos = d;
this.color = this.color===COLOR_RED?COLOR_BLACK:COLOR_RED;
this.ply++;
return {s,d,cap,pc};
}
undoMoveRaw(undo: {s:number, d:number, cap:number, pc:number}){
const s = undo.s;
const d = undo.d;
const pc = undo.pc;
const cap = undo.cap;
// Incremental Hash Restore
// Operations are XOR, so order doesn't strictly matter, but let's mirror makeMove
this.currentHash ^= ZOBRIST_SIDE; // Toggle side back
this.currentHash ^= ZOBRIST[pc * 90 + d]; // Remove from dst
if (cap) this.currentHash ^= ZOBRIST[cap * 90 + d]; // Restore captured
this.currentHash ^= ZOBRIST[pc * 90 + s]; // Add back to src
// Incremental Score Restore
// 1. Remove pc from d
const valDst = VAL[pc] + PST_FLAT[pc*90 + d];
if (pc & COLOR_RED) this.currentRedScore -= valDst;
else this.currentBlackScore -= valDst;
// 2. Add cap to d
if (cap) {
const valCap = VAL[cap] + PST_FLAT[cap*90 + d];
if (cap & COLOR_RED) this.currentRedScore += valCap;
else this.currentBlackScore += valCap;
}
// 3. Add pc to s
const valSrc = VAL[pc] + PST_FLAT[pc*90 + s];
if (pc & COLOR_RED) this.currentRedScore += valSrc;
else this.currentBlackScore += valSrc;
this.board[s]=pc;
this.board[d]=cap;
// Restore King Position
if (pc === R_KING) this.redKingPos = s;
else if (pc === B_KING) this.blackKingPos = s;
this.color = this.color===COLOR_RED?COLOR_BLACK:COLOR_RED;
this.ply--;
}
// 更安全的 makeMove（并维护 hashHistory）
makeMove(move: number){
const before = this.currentHash;
const u=this.makeMoveRaw(move);
// after is now this.currentHash
this.hashHistory.push(before);
return u;
}
undoMove(u: {s:number, d:number, cap:number, pc:number}){ this.undoMoveRaw(u); this.hashHistory.pop(); }
// 判断走法是否合法（走完后自己的将不被吃 / 将帅对脸）
isLegalAfterMove(move: number){
const u=this.makeMoveRaw(move);
const kingsFace = this.kingsFaceToFace();
// Use cached king pos (which was updated in makeMoveRaw)
const myKingPos = (this.color===COLOR_RED) ? this.blackKingPos : this.redKingPos;
const inCheck = this.isAttacked(myKingPos, this.color);
this.undoMoveRaw(u);
if(kingsFace) return false;
return !inCheck;
}
// 评估函数：子力 + PST + 简单活动度 + 位置补偿
// light=true: 只计算材质和PST (用于剪枝)
// light=false: 包含机动性计算 (用于叶子节点)
evaluate(light = false){
// Simplified/cheaper evaluation: Material + PST + a few structural terms.
// Use incremental scores for base material + PST
let redScore = this.currentRedScore;
let blackScore = this.currentBlackScore;
let rAdv=0, rEle=0, bAdv=0, bEle=0;
let rAttackingUnits = 0;
let bAttackingUnits = 0;
for(let i=0;i<90;i++){
const p=this.board[i];
if(!p) continue;
// let v = VAL[p]; // Already in currentScore
const r = (i/9)|0;
const c = i%9;
if(p & COLOR_RED) {
// if(PST_TABLE[p]) v += PST_TABLE[p][i]; // Already in currentScore
if(p===R_ADV) rAdv++;
if(p===R_ELE) rEle++;
if (i < 45 && (p===R_ROOK || p===R_HORSE || p===R_CANNON)) rAttackingUnits++;
if (!light) {
// Mobility (Simplified)
if (p === R_ROOK) {
// Count empty squares / attacks in 4 directions
for(let d of DIRS_ROOK_CANNON) {
let dst = i + d;
let prevRow = (i / 9) | 0; // Track the row we came from
while(dst>=0 && dst<90) {
const curRow = (dst / 9) | 0;
// Horizontal move: must stay on same row as previous
if (Math.abs(d) === 1 && curRow !== prevRow) break;
redScore += 1; // +1 per square
if (this.board[dst]) break;
prevRow = curRow; // Update for next iteration
dst += d;
}
}
} else if (p === R_HORSE) {
for(let m of HORSE_STEPS) {
const leg = i + m.leg;
const to = i + m.d;
if(leg>=0 && leg<90 && to>=0 && to<90 && this.board[leg]===0) {
const tr = (to/9)|0, tc = to%9;
if ((Math.abs(r-tr)===1 && Math.abs(c-tc)===2) || (Math.abs(r-tr)===2 && Math.abs(c-tc)===1)) {
redScore += 12; // +12 per valid move
}
}
}
}
}
// Pawn structure (keep – cheap and important)
if (p === R_PAWN) {
if (c > 0 && this.board[i-1] === R_PAWN) redScore += 20;
if (c < 8 && this.board[i+1] === R_PAWN) redScore += 20;
if (i < 27 && c >= 3 && c <= 5) redScore += 30;
}
} else {
// const pstIdx = 89 - i;
// if(PST_TABLE[p]) v += PST_TABLE[p][pstIdx]; // Already in currentScore
if(p===B_ADV) bAdv++;
if(p===B_ELE) bEle++;
if (i > 44 && (p===B_ROOK || p===B_HORSE || p===B_CANNON)) bAttackingUnits++;
if (!light) {
// Mobility (Simplified)
if (p === B_ROOK) {
for(let d of DIRS_ROOK_CANNON) {
let dst = i + d;
let prevRow = (i / 9) | 0;
while(dst>=0 && dst<90) {
const curRow = (dst / 9) | 0;
if (Math.abs(d) === 1 && curRow !== prevRow) break;
blackScore += 1;
if (this.board[dst]) break;
prevRow = curRow;
dst += d;
}
}
} else if (p === B_HORSE) {
for(let m of HORSE_STEPS) {
const leg = i + m.leg;
const to = i + m.d;
if(leg>=0 && leg<90 && to>=0 && to<90 && this.board[leg]===0) {
const tr = (to/9)|0, tc = to%9;
if ((Math.abs(r-tr)===1 && Math.abs(c-tc)===2) || (Math.abs(r-tr)===2 && Math.abs(c-tc)===1)) {
blackScore += 12;
}
}
}
}
}
if (p === B_PAWN) {
if (c > 0 && this.board[i-1] === B_PAWN) blackScore += 20;
if (c < 8 && this.board[i+1] === B_PAWN) blackScore += 20;
if (i > 62 && c >= 3 && c <= 5) blackScore += 30;
}
}
// if(p & COLOR_RED) redScore += v; else blackScore += v; // Removed
}
// King safety with defenders (keep – very cheap)
redScore += (rAdv * 20 + rEle * 20);
blackScore += (bAdv * 20 + bEle * 20);
const rDeficit = (2-rAdv)*2 + (2-rEle);
const bDeficit = (2-bAdv)*2 + (2-bEle);
if (bAttackingUnits > 0) {
redScore -= rDeficit * 40;
}
if (rAttackingUnits > 0) {
blackScore -= bDeficit * 40;
}
const score = redScore - blackScore;
return (this.color===COLOR_RED)? score : -score;
}
// 检查是否初始局面 (用于开局库)
isInitialBoard() {
// 简单检查几个关键位置
// Red: Rooks at 81, 89; Horses at 82, 88; Cannons at 64, 70; Pawns at 54,56,58,60,62
// Black: Rooks at 0, 8; ...
if (this.board[81] !== R_ROOK || this.board[89] !== R_ROOK) return false;
if (this.board[64] !== R_CANNON || this.board[70] !== R_CANNON) return false;
if (this.board[0] !== B_ROOK || this.board[8] !== B_ROOK) return false;
// 检查是否还没动过 (简单判断中间没有兵)
if (this.board[45] !== 0 || this.board[44] !== 0) return false;
return true;
}
getOpeningMove() {
console.log(`Engine: getOpeningMove called, gameHistory.length=${this.gameHistory.length}, color=${this.color}`);
// 开局优先查 openingbook.ts
const mvFromBook = getOpeningBookMove(this.gameHistory, this.board, this.color);
if (mvFromBook) {
console.log(`Engine: openingbook returned move ${mvFromBook}`);
return mvFromBook;
}
console.log(`Engine: No book move, checking simple rules...`);
// 回退到原有的简易首步规则（只识别完全初始局面）
// Red First Move
if (this.gameHistory.length === 0 && this.color === COLOR_RED && this.isInitialBoard()) {
const moves = [
MOVE(70, 67), // 炮八平五
MOVE(64, 67), // 炮二平五
MOVE(82, 65), // 马二进三
MOVE(88, 69), // 马八进七
MOVE(83, 67), // 相三进五
MOVE(87, 67) // 相七进五
];
return moves[Math.floor(Math.random() * moves.length)];
}
// Black First Response (Simple Book)
if (this.gameHistory.length === 1 && this.color === COLOR_BLACK) {
// Check for Red Central Cannon (at 67)
if (this.board[67] === R_CANNON) {
const moves = [
MOVE(7, 24), // 马8进7 (Screen Horse)
MOVE(1, 20), // 马2进3 (Screen Horse)
MOVE(25, 22), // 炮8平5 (Same Direction Cannon)
MOVE(19, 22) // 炮2平5 (Same Direction Cannon)
];
return moves[Math.floor(Math.random() * moves.length)];
}
// Check for Red Horse (at 65 or 69)
if (this.board[65] === R_HORSE || this.board[69] === R_HORSE) {
const moves = [
MOVE(7, 24),
MOVE(1, 20),
MOVE(25, 22) // Central Cannon
];
return moves[Math.floor(Math.random() * moves.length)];
}
// Default fallback
const moves = [MOVE(7, 24), MOVE(1, 20)];
return moves[Math.floor(Math.random() * moves.length)];
}
return 0;
}
// 置换表 存取
ttProbe(hash: number, depth: number, alpha: number, beta: number){
const bucket = (hash & (TT_BUCKET_COUNT-1)) << 2; // * 4
// Check all 4 entries in the bucket
for(let i=0; i<4; i++) {
const idx = bucket + i;
if(tt_keys[idx] === hash){
const d = tt_depths[idx];
if(d >= depth){
const sc = tt_scores[idx];
const f = tt_flags[idx];
if(f===TT_FLAG_EXACT) return sc;
if(f===TT_FLAG_LOWER && sc <= alpha) return alpha;
if(f===TT_FLAG_UPPER && sc >= beta) return beta;
}
// Found the entry but depth is insufficient, return null to search
// But we could return the move for ordering?
// For now, just return null for value.
return null;
}
}
return null;
}
ttGetMove(hash: number) {
const bucket = (hash & (TT_BUCKET_COUNT-1)) << 2;
for(let i=0; i<4; i++) {
if(tt_keys[bucket+i] === hash) return tt_moves[bucket+i];
}
return 0;
}
ttStore(hash: number, depth: number, score: number, flag: number, move: number){
const bucket = (hash & (TT_BUCKET_COUNT-1)) << 2;
let replaceIdx = -1;
let minDepth = 1000;
// Strategy:
// 1. If key exists, update it.
// 2. If empty slot exists, use it.
// 3. Replace the entry with lowest depth (or age, but we don't have age).
for(let i=0; i<4; i++) {
const idx = bucket + i;
if (tt_keys[idx] === hash) {
// Found same position
if (depth >= tt_depths[idx]) {
tt_keys[idx]=hash;
tt_depths[idx]=depth;
tt_scores[idx]=score;
tt_flags[idx]=flag;
tt_moves[idx]=move;
}
return;
}
if (tt_keys[idx] === 0) {
// Found empty slot
replaceIdx = idx;
break; // Use the first empty slot
}
if (tt_depths[idx] < minDepth) {
minDepth = tt_depths[idx];
replaceIdx = idx;
}
}
// If we didn't find exact match or empty slot, replace the worst one
if (replaceIdx !== -1) {
tt_keys[replaceIdx]=hash;
tt_depths[replaceIdx]=depth;
tt_scores[replaceIdx]=score;
tt_flags[replaceIdx]=flag;
tt_moves[replaceIdx]=move;
}
}
// quiescence（只搜吃子）
quiescence(alpha: number, beta: number){
if (this.stop) return alpha;
this.nodes++;
if((this.nodes & 65535)===0){
if(Date.now()-this.startTime > this.timeLimit) this.stop=true;
console.log(`Engine Q: nodes ${this.nodes} alpha ${alpha} beta ${beta}`);
}
if (this.nodes > 5000000) this.stop = true;
if(this.stop) return alpha; // Return alpha (fail-low) or just return
const stand = this.evaluate(true); // Use light evaluation for speed
if(stand >= beta) return beta;
// Delta Pruning
// 如果当前局面评分加上一个大子(车)的价值还不够 alpha，那大概率没戏
// 除非有连杀，但在 QS 中我们只看单步吃子。
const R_VAL = 900;
if (stand < alpha - R_VAL) {
return alpha;
}
if(stand > alpha) alpha = stand;
const moves = this.generateMoves(true);
// sort by MVV-LVA simplified
moves.sort((a,b)=>{ const va = VAL[this.board[DST(a)]] - VAL[this.board[SRC(a)]]; const vb = VAL[this.board[DST(b)]] - VAL[this.board[SRC(b)]]; return vb - va; });
for(let mv of moves){ if(!this.isLegalAfterMove(mv)) continue; const u = this.makeMove(mv); const score = -this.quiescence(-beta, -alpha); this.undoMove(u); if(score >= beta) return beta; if(score > alpha) alpha = score; }
return alpha; }
// 主搜索（Negamax + PVS + Null move + LMR + TT + Check Extension + Razoring + Futility Pruning）
negamax(depth: number, alpha: number, beta: number, allowNull=true): number {
if (this.stop) return 0;
if (this.ply === 0) console.log(`Engine: negamax ENTRY depth=${depth} ply=${this.ply}`);
if (this.ply > 100) return this.evaluate(false);
if (this.ply === 0) console.log(`Engine: negamax after ply check`);
// Mate Distance Pruning
if (this.ply > 0) {
const mateVal = 20000 - this.ply;
if (alpha < -mateVal) alpha = -mateVal;
if (beta > mateVal) beta = mateVal;
if (alpha >= beta) return alpha;
}
if (this.ply === 0) console.log(`Engine: negamax after mate distance pruning`);
this.nodes++;
if((this.nodes & 65535)===0){
if(Date.now()-this.startTime > this.timeLimit) this.stop=true;
console.log(`Engine: nodes ${this.nodes} depth ${depth} ply ${this.ply}`);
}
if (this.nodes > 5000000) this.stop = true; // Safety valve: 5M nodes max
if(this.stop) return 0;
if (this.ply === 0) console.log(`Engine: negamax after node count, nodes=${this.nodes}`);
// 0. Quiescence Search at leaf
if(depth<=0) return this.quiescence(alpha, beta);
if (this.ply === 0) console.log(`Engine: negamax after quiescence check`);
// 1. TT Probe
const hash = this.currentHash;
const ttHit = this.ttProbe(hash, depth, alpha, beta);
if(ttHit !== null) return ttHit;
if (this.ply === 0) console.log(`Engine: negamax after TT probe, hash=${hash}`);
// 2. Repetition Check
if (this.ply === 0) console.log(`Engine: negamax checking repetition, hashHistory.length=${this.hashHistory.length}, gameHistory.length=${this.gameHistory.length}`);
if(this.hashHistory.includes(hash) || this.gameHistory.includes(hash)) return 0;
if (this.ply === 0) console.log(`Engine: negamax after repetition check`);
// 3. Check Extension (将军延伸)
if (this.ply === 0) console.log(`Engine: negamax getting king pos, color=${this.color}`);
const myKing = this.getKingPos(this.color);
if (this.ply === 0) console.log(`Engine: negamax got king pos=${myKing}`);
const inCheck = this.isAttacked(myKing, (this.color===COLOR_RED)?COLOR_BLACK:COLOR_RED);
if (this.ply === 0) console.log(`Engine: negamax checked isAttacked, inCheck=${inCheck}`);
let newDepth = depth;
if (inCheck) {
newDepth++; // 延伸
allowNull = false; // 被将军不能空着
}
// Static Eval (for pruning)
if (this.ply === 0) console.log(`Engine: negamax calling evaluate, inCheck=${inCheck}`);
let staticEval = -30000;
if (!inCheck) {
// Use full evaluation (with mobility) for pruning decisions in the search tree.
// This aligns with the strategy of using heavy eval in shallow layers (Negamax)
// and light eval in leaves (Quiescence).
staticEval = this.evaluate(false);
}
if (this.ply === 0) console.log(`Engine: negamax after evaluate, staticEval=${staticEval}`);
// 4. Razoring
// If static eval is way below alpha, drop into qsearch
if (!inCheck && newDepth <= 3 && staticEval + 400 * newDepth < alpha) {
const v = this.quiescence(alpha, beta);
if (v < alpha) return v;
}
// 5. Reverse Futility Pruning (Static Null Move Pruning)
// 如果当前局面已经很好（超过 beta），且剩余深度不大，可能不需要搜索就能截断
if (!inCheck && newDepth <= 4 && allowNull) {
const margin = 150 * newDepth;
if (staticEval - margin >= beta) {
return staticEval - margin; // Fail-soft return
}
}
// 6. Null-move pruning
if(allowNull && !inCheck && newDepth >= 3){
// 如果 staticEval 极低（比如被杀），不要空着
if (staticEval >= beta - 400) { // 只有局面还行才试空着
// Null Move: Toggle side in hash
this.currentHash ^= ZOBRIST_SIDE;
this.color = this.color===COLOR_RED?COLOR_BLACK:COLOR_RED; this.ply++;
// Adaptive Null Move Reduction
const R = 2 + (newDepth > 6 ? 1 : 0);
const score = -this.negamax(newDepth-1-R, -beta, -beta+1, false);
this.ply--; this.color = this.color===COLOR_RED?COLOR_BLACK:COLOR_RED;
this.currentHash ^= ZOBRIST_SIDE; // Restore hash
if(score >= beta) return beta;
}
}
// 7. Internal Iterative Deepening (IID)
// 如果是 PV 节点（alpha < beta - 1? 或者是主要搜索分支），且 TT 没有命中，
// 先搜一个浅层来填充 TT，以便 Move Ordering
let ttMove=0;
// Use new TT lookup
ttMove = this.ttGetMove(hash);
if (ttMove === 0 && newDepth >= 4) {
this.negamax(newDepth - 2, alpha, beta, allowNull);
ttMove = this.ttGetMove(hash);
}
// 8. Move Generation
if (this.ply === 0) console.log(`Engine: negamax generating moves at ply=${this.ply}`);
let moves = this.generateMoves(false);
if (this.ply === 0) console.log(`Engine: negamax generated ${moves.length} moves`);
// Optimize: Don't filter legal moves upfront. Sort pseudo-legal moves and check legality lazily.
// This saves 'isLegalAfterMove' calls for moves that are pruned.
if(moves.length===0){
// No pseudo-legal moves? (Rare, but possible if trapped)
// Check if it's actually mate or stalemate requires checking legality,
// but usually we have some moves. If 0 moves, it's definitely mate/stalemate.
if (this.ply === 0) console.log(`Engine: negamax NO MOVES, returning mate score`);
return -20000 + this.ply;
}
// 9. Move Ordering
if (this.ply === 0) console.log(`Engine: negamax sorting moves...`);
// Sort the pseudo-legal moves directly
moves.sort((a,b)=>{
if(a===ttMove) return -1; if(b===ttMove) return 1;
const ca = this.board[DST(a)]?1:0; const cb = this.board[DST(b)]?1:0; if(ca!==cb) return cb-ca;
if (ca && cb) {
const diffA = VAL[this.board[DST(a)]] - VAL[this.board[SRC(a)]];
const diffB = VAL[this.board[DST(b)]] - VAL[this.board[SRC(b)]];
return diffB - diffA;
}
const plyK = this.ply;
if (plyK < 256) {
const k1 = this.killer[plyK][0];
const k2 = this.killer[plyK][1];
if (a === k1) return -1;
if (b === k1) return 1;
if (a === k2) return -1;
if (b === k2) return 1;
}
return (this.history[a]||0) > (this.history[b]||0) ? -1 : 1;
});
// 10. PVS Loop
if (this.ply === 0) console.log(`Engine: negamax starting PVS loop...`);
let best=0; let value = -Infinity; let flag = TT_FLAG_UPPER;
let movesSearched = 0; // Counts LEGAL moves searched
let legalMoveCount = 0; // Total legal moves found
for(let i=0; i<moves.length; i++){
const mv = moves[i];
// Lazy Legality Check
if(!this.isLegalAfterMove(mv)) continue;
legalMoveCount++;
if (this.ply === 0 && legalMoveCount === 1) console.log(`Engine: negamax searching first legal move ${mv}...`);
const isCapture = this.board[DST(mv)]!==0;
// Futility Pruning (Move Loop)
if (!inCheck && !isCapture && newDepth <= 2 && staticEval + 200 * newDepth < alpha) {
// Skip quiet moves that are unlikely to raise alpha
// But ensure we search at least one move (if movesSearched==0, we shouldn't prune)
if (movesSearched > 0) continue;
}
// Late Move Pruning (LMP)
if (!inCheck && !isCapture && newDepth < 4) {
const lmpCount = 5 + newDepth * 3;
if (movesSearched > lmpCount) continue;
}
const u = this.makeMove(mv);
let score;
if (movesSearched === 0) {
score = -this.negamax(newDepth-1, -beta, -alpha, true);
} else {
// LMR
let reduction = 0;
if(movesSearched>=4 && newDepth>=2 && !isCapture && !inCheck){
reduction = 1;
if (movesSearched > 10 || newDepth > 4) reduction = 2;
if (movesSearched > 20) reduction = 3;
}
score = -this.negamax(newDepth-1-reduction, -alpha-1, -alpha, true);
if(score > alpha) {
if (reduction > 0) score = -this.negamax(newDepth-1, -alpha-1, -alpha, true);
if (score > alpha && score < beta) score = -this.negamax(newDepth-1, -beta, -alpha, true);
}
}
this.undoMove(u);
if(this.stop) return 0;
movesSearched++;
if(score >= beta){
if(!isCapture && this.ply < 256){
const plyK = this.ply;
this.killer[plyK][1]=this.killer[plyK][0];
this.killer[plyK][0]=mv;
this.history[mv] += newDepth*newDepth;
// Cap history to avoid overflow
if (this.history[mv] > 10000000) {
for(let h=0;h<this.history.length;h++) this.history[h] >>= 1;
}
}
this.ttStore(hash, depth, beta, TT_FLAG_LOWER, mv);
return beta;
}
if(score > value){ value = score; best=mv; }
if(score > alpha){ alpha = score; flag = TT_FLAG_EXACT; }
}
if(legalMoveCount===0){
// Chinese Chess: Stalemate is a loss, same as Checkmate
return -20000 + this.ply;
}
this.ttStore(hash, depth, value, flag, best);
return value;
}
// 迭代加深 + Aspiration window
search(maxDepth: number, timeLimit?: number){
console.log(`Engine: search called maxDepth=${maxDepth} timeLimit=${timeLimit}`);
this.stop=false;
this.startTime=Date.now();
if(timeLimit) this.timeLimit = timeLimit;
this.nodes=0;
this.hashHistory=[];
this.ply=0;
let bestMove=0;
let guess=0;
// Age history heuristic
for(let i=0;i<this.history.length;i++) this.history[i] >>= 1;
// 0. Opening Book Check
console.log(`Engine: Checking opening book...`);
const bookMove = this.getOpeningMove();
if (bookMove) {
console.log(`Engine: Opening book returned move ${bookMove}`);
return { move: bookMove, score: 0, pv: [bookMove] };
}
console.log(`Engine: No opening book move, starting iterative deepening...`);
for(let d=1; d<=maxDepth; d++){
console.log(`Engine: Starting depth ${d}`);
this.maxDepthReached = d;
let alpha = -30000, beta = 30000;
if(d>1){ alpha = guess - 50; beta = guess + 50; }
console.log(`Engine: Calling negamax depth=${d} alpha=${alpha} beta=${beta}`);
let score = this.negamax(d, alpha, beta, true);
console.log(`Engine: negamax returned score=${score}`);
if(this.stop) {
console.log(`Engine: stop flagged after negamax depth ${d}, score ${score}`);
break;
}
if(score <= alpha || score >= beta){ // failed aspiration
score = this.negamax(d, -30000, 30000, true);
}
if(this.stop) {
console.log(`Engine: stop flagged after re-search at depth ${d}, score ${score}`);
break;
}
const h = this.getHash();
const mv = this.ttGetMove(h);
if(mv) bestMove = mv;
guess = score;
// Extract PV
const pv = this.getPVLine(d);
if (this.onProgress) {
this.onProgress({
depth: d,
score: guess,
move: bestMove,
pv: pv,
nodes: this.nodes,
time: Date.now() - this.startTime
});
}
}
const finalPV = this.getPVLine(this.maxDepthReached);
return { move: bestMove, score: guess, pv: finalPV };
}
getPVLine(depth: number): number[] {
const pv: number[] = [];
const undos: any[] = [];
const seen = new Set<number>();
let d = 0;
while(d < depth) {
const hash = this.currentHash;
if (seen.has(hash)) break;
seen.add(hash);
const move = this.ttGetMove(hash);
if (!move) break;
// Verify source piece validity to avoid using stale/collided TT entries
const s = SRC(move);
const p = this.board[s];
if (!p || (p & this.color) === 0) break;
// Verify pseudo-legality (simple check)
// Ideally we should check isLegalAfterMove but that's expensive.
// We trust TT mostly, but check if destination is not own piece
const dst = DST(move);
const target = this.board[dst];
if (target && (target & this.color)) break;
pv.push(move);
undos.push(this.makeMove(move));
d++;
}
// Undo all moves in reverse order
for (let i = undos.length - 1; i >= 0; i--) {
this.undoMove(undos[i]);
}
return pv;
}
}开发小工具
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-11-21，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
