黑白棋（Othello，又名翻转棋）看起来比象棋简单：8×8 棋盘、只有一种走法规则（夹住对手的棋子就能翻色）。但它有一个非常反直觉的特征——终局看的是子力，过程中却常常要主动少子。这种”短期让子换长期稳定”的取舍，让手调评估权重极为困难。
传统做法是让程序员凭经验给”角位 10 分、行动力 2 分”之类的系数，然后反复跑对局微调。本文换一条路：把权重交给差分进化（Differential Evolution, DE）自己学。我们会用位棋盘实现高速对局引擎，用 Negamax + Alpha-Beta 做搜索，再用 DE 在自我对弈中进化出五维权重向量。
一、位棋盘：把 64 格压进一个 long
黑白棋的每一步都要计算”能落哪些点”和”落子后能翻哪些子”。如果用二维数组逐格扫描，一次合法着点计算就是 64×8×6 ≈ 3000 次操作；用 long 的 64 位表示棋盘，这些操作全部变成移位和按位与，一次能处理 8 格。
约定：bit index = r*8 + c，bit0 是 a1 格。黑子用 P、白子用 O、空格用 ~(P|O)。
关键陷阱是横向移位的回绕：在 long 上左移 1 位，H 列的棋子会跑到下一行的 A 列。必须用掩码把会越界的列先屏蔽掉：
// 横移时必须屏蔽列掩码，防止从 H 列"回绕"到 A 列
static final long NOT_A = 0xFEFEFEFEFEFEFEFEL; // 除 A 列以外
static final long NOT_H = 0x7F7F7F7F7F7F7F7FL; // 除 H 列以外
八个方向的位移量与对应的前置掩码：
static final int[] DELTA = {8, -8, 1, -1, 9, 7, -9, -7};
static final long[] MASK = {~0L, ~0L, NOT_H, NOT_A, NOT_H, NOT_A, NOT_H, NOT_A};
/** 统一"定向移位"：正位移左移，负位移右移（避免 Java 中负数左移的溢出陷阱） */
static long sh(long b, int di) {
long m = b & MASK[di];
int d = DELTA[di];
return d > 0 ? (m << d) : (m >>> -d);
}
>>>（无符号右移）这一点必须写对。如果用 >>，负数位棋盘会把符号位复制进来，整个棋盘被污染。
dumb7fill：一次求出所有合法着点
黑白棋的合法着点定义是：某个空位，沿着某个方向存在”至少一个对手子，且末端贴着己方子”。这个计算可以用经典的 dumb7fill 技巧——沿方向做”连通延伸”：
/**
* 求某一方向的合法落子：
* t = sh(P) & O 先找到与己方子相邻的对手子
* 循环 t |= sh(t) & O 把沿方向的连续对手子全部连通
* 最后 sh(t) & empty 连通段之后的第一个空位就是合法落点
*/
static long movesDir(long P, long O, long empty, int di) {
long t = sh(P, di) & O;
if (t == 0) return 0;
for (int k = 0; k < 5; k++) t |= (sh(t, di) & O); // 最多连续 6 个对手子
return sh(t, di) & empty;
}
static long legalMoves(long P, long O) {
long empty = ~(P | O);
long res = 0;
for (int di = 0; di < 8; di++) res |= movesDir(P, O, empty, di);
return res;
}
为什么循环 5 次就够了？棋盘一边最多 8 格，除去起点和落点，中间最多夹 6 个对手子。每次迭代至少让连通块沿方向增长 1 格，5 次迭代后覆盖 6 格长度（初始一次 + 5 次扩展）。写 8 次也不会错，只是多两次空转。
flipsFor：求要翻转的棋子
/** 落子 m 后要翻转的对手子集合 */
static long flipsFor(long P, long O, long m) {
long flips = 0;
for (int di = 0; di < 8; di++) {
long t = sh(m, di) & O; // 落子紧邻的对手子
if (t == 0) continue;
for (int k = 0; k < 5; k++) t |= (sh(t, di) & O);
if ((sh(t, di) & P) != 0) flips |= t; // 连通段末端贴己方子 -> 可夹
}
return flips;
}
/** 应用一步棋：落子 + 翻转（注意先把 P 加上再清 O，顺序不能反） */
static void apply(long[] P, long[] O, long m) {
long flips = flipsFor(P[0], O[0], m);
P[0] |= m | flips;
O[0] &= ~flips;
}
flipsFor 与 movesDir 结构几乎一样，差别只在最后一步：movesDir 返回”段后的空位”，flipsFor 返回”段本身”。这两个函数是整个引擎的核心，写对之后每一步对局都在微秒级完成。
二、评估函数的五个特征
黑白棋的评估函数设计有几个公认有效的位置特征：
行动力（mobility）：自己能走的点数量减对手能走的点数量。这是黑白棋最重要的特征——把对手的行动力压到 0 就是”零封”，对手只能让手。中盘阶段行动力差往往比子力差重要得多。
角位（corner）：四个角上的棋子永远不会被翻。占角不仅稳，还能沿着两条边向外扩展稳定子。
稳定子（stable）：永远不会被翻的棋子。真实稳定子计算需要沿边做传播（一个棋子如果两个正交方向都与边界/稳定子连通，它就是稳定的），代价较高。本文用”边线棋子数”做轻量近似——边线棋子通常稳定性远高于内部棋子。
前沿子（frontier）：紧贴空位的棋子。这类棋子是最容易被对手翻的，越少越好。注意它的符号是”对手前沿子 – 自己前沿子”，所以权重应当是负的。
子力差（disc count）：终局才真正重要。中盘阶段子多反而是负担（无子可翻时对手可以随意让手）。
static final int FEAT = 5;
static double[] features(long P, long O) {
long empty = ~(P | O);
double[] f = new double[FEAT];
// (1) 行动力差：可走点越多，主动权越强
f[0] = Long.bitCount(legalMoves(P, O)) - Long.bitCount(legalMoves(O, P));
// (2) 角位差：角上的子永远不能被吃
f[1] = Long.bitCount(P & CORNERS) - Long.bitCount(O & CORNERS);
// (3) 稳定子差（简化：边线棋子数）
f[2] = stable(P) - stable(O);
// (4) 前沿子差：紧贴空位的子最容易被打，所以符号取"对手-自己"
long frontP = 0, frontO = 0;
for (int di = 0; di < 8; di++) { frontP |= sh(P, di); frontO |= sh(O, di); }
f[3] = Long.bitCount(frontO & empty) - Long.bitCount(frontP & empty);
// (5) 子力差
f[4] = Long.bitCount(P) - Long.bitCount(O);
return f;
}
static double eval(long P, long O, double[] w) {
double[] f = features(P, O);
double v = 0;
for (int i = 0; i < FEAT; i++) v += w[i] * f[i];
return v;
}
这就是我们要进化的对象：一个 5 维实数向量 w。人工给的初始猜测是 {2.0, 10.0, 4.0, -2.0, 1.0}——行动力中等、角位最重要、稳定子次之、前沿子为负、子力轻权。
三、Negamax + Alpha-Beta
搜索部分用 negamax 形式，好处是代码只有一份（不用写”最大化/最小化”两套）：
static double negamax(long P, long O, int depth, double alpha, double beta, double[] w) {
long my = legalMoves(P, O);
// 让手处理：如果自己无子可下但对手有，则跳过自己，深度不变
if (my == 0) {
if (legalMoves(O, P) == 0) { // 双方都无子可下 -> 终局
int diff = Long.bitCount(P) - Long.bitCount(O);
return diff > 0 ? 1000 + diff : (diff < 0 ? -1000 + diff : 0);
}
return -negamax(O, P, depth, -beta, -alpha, w);
}
if (depth <= 0) return eval(P, O, w);
List<Long> list = bits(my);
list.sort((a, b) -> Double.compare(quick(O, a), quick(O, b))); // 落子排序
double best = -1e9;
for (long m : list) {
long[] np = {P}, no = {O};
apply(np, no, m);
double v = -negamax(no[0], np[0], depth - 1, -beta, -alpha, w);
if (v > best) best = v;
if (v > alpha) alpha = v;
if (alpha >= beta) break; // 剪枝
}
return best;
}
两个细节值得强调：
让手不消耗深度。黑白棋的”pass”不是一步棋的概念——如果对手没有合法着点，你下完就该轮到自己继续。所以 -negamax(O, P, depth, ...) 里 depth 保持原值。如果写成 depth - 1，会白白浪费一层搜索，让 AI 在对局末期算不清。
终局用真实子力而非评估函数。终局判分 1000 + diff 让”赢”永远优于任何中盘评估值，也保留了”赢多少”的粒度（黑白棋的最终比分是子力差，赢 33:31 和赢 60:4 都算赢但价值不同）。
落子排序用 quick()：能翻的子多、能占角的分高。Alpha-Beta 的效率极度依赖排序质量——排序好的情况下剪枝率可达 90% 以上，等效深度提升接近 2 倍。
/** 只用于排序的快速打分：能翻的子多 + 占角加分（返回负值以便升序时高分在前） */
static double quick(long O, long m) {
long flips = flipsFor(~O, O, m);
double s = Long.bitCount(flips);
if ((m & CORNERS) != 0) s += 100;
return -s;
}
四、差分进化：为什么比遗传算法更适合调权重
差分进化是 Storn 和 Price 在 1995 年提出的实数优化算法。它和遗传算法最大的区别是变异算子来自种群内部的差分向量，而不是随机扰动：
v = x_r1 + F * (x_r2 - x_r3)
(x_r2 - x_r3) 是种群中两个个体的差，它自动携带了”当前种群在这个维度上还需要走多远”的信息。随着种群收敛，差分幅度自动缩小，搜索步长也随之减小——这是一种自适应的步长控制，不需要像 GA 那样手工设计变异率衰减曲线。
这对调权重特别合适：一开始种群分散，权重在 [-12, 12] 里乱跳，探索性强；后期种群收敛，微调幅度自动变小。
完整实现
static final double[] BASE_W = {2.0, 10.0, 4.0, -2.0, 1.0}; // 人工基准权重
static final int DIM = FEAT;
static final int NP = 12; // 种群规模（一般取 5~10 倍维度）
static final int MAX_GEN = 10; // 迭代代数
static final double F = 0.6; // 变异缩放因子，常用 0.4~0.9
static final double CR = 0.75; // 交叉概率，常用 0.5~0.9
static final double BOUND = 12.0;
static double[] differentialEvolution(long seed) {
Random rnd = new Random(seed);
double[][] pop = new double[NP][DIM];
double[] fit = new double[NP];
// 1) 初始化：在整个可行域内均匀撒点
for (int i = 0; i < NP; i++) {
for (int j = 0; j < DIM; j++) pop[i][j] = (rnd.nextDouble() * 2 - 1) * BOUND;
fit[i] = fitness(pop[i], seed + i * 131L);
}
int bestIdx = 0;
for (int i = 1; i < NP; i++) if (fit[i] > fit[bestIdx]) bestIdx = i;
double[] best = pop[bestIdx].clone();
double bestFit = fit[bestIdx];
for (int gen = 0; gen < MAX_GEN; gen++) {
for (int i = 0; i < NP; i++) {
// 2) 选三个互不相同的个体
int r1, r2, r3;
do { r1 = rnd.nextInt(NP); } while (r1 == i);
do { r2 = rnd.nextInt(NP); } while (r2 == i || r2 == r1);
do { r3 = rnd.nextInt(NP); } while (r3 == i || r3 == r1 || r3 == r2);
// 3) 变异：v = x_r1 + F*(x_r2 - x_r3)
double[] v = new double[DIM];
for (int j = 0; j < DIM; j++) v[j] = pop[r1][j] + F * (pop[r2][j] - pop[r3][j]);
// 4) 二项式交叉：每维以 CR 的概率取 v，且保证至少一维来自 v
int jr = rnd.nextInt(DIM);
double[] u = new double[DIM];
for (int j = 0; j < DIM; j++)
u[j] = (rnd.nextDouble() < CR || j == jr) ? v[j] : pop[i][j];
// 5) 边界修复：越界则拉回可行域并加随机抖动
for (int j = 0; j < DIM; j++)
if (u[j] > BOUND || u[j] < -BOUND) u[j] = (rnd.nextDouble() * 2 - 1) * BOUND;
// 6) 贪婪选择：只有更好才替换（保证种群不会退化）
double uf = fitness(u, seed + gen * 977L + i * 131L);
if (uf > fit[i]) { pop[i] = u; fit[i] = uf; }
if (uf > bestFit) { bestFit = uf; best = u.clone(); }
}
}
return best;
}
第 4 步的 j == jr 保证是必需的：如果 5 个维度碰巧全部交叉失败（概率 (1-CR)^5 ≈ 0.001），u 就等于 pop[i] 自己，这个变异被浪费了。强制一维必然来自 v 让每个变异向量都真正产生新个体。
第 6 步的”贪婪选择”是 DE 与传统 GA 的另一个关键差异：DE 是逐个个体替换（一对一比较），GA 通常整代替换。这种”精英保留”式的更新让 DE 的收敛极其稳定，几乎不会出现适应度倒退。
适应度为对弈得分
适应度函数直接让候选权重上场打比赛：
/** 适应度：对基准权重打 4 局（2 黑 2 白，随机开局），累加子力差 */
static double fitness(double[] w, long seed) {
Random rnd = new Random(seed);
int total = 0;
for (int i = 0; i < 4; i++) {
boolean evoBlack = (i % 2 == 0);
total += playGame(evoBlack, w, 2, BASE_W, 2, 4, rnd);
}
return total / 4.0;
}
三个设计要点：
黑白各打两局。黑白棋先手有明显优势（先手方通常赢面更大），只打一边会让进化出来的权重偏向某一方。
随机开局 4 步。如果固定开局，DE 会很快”记住”某条特定线路并过拟合——适应度冲到很高，但换一局就崩。随机化开局是引入噪声、抑制过拟合的最便宜手段。
用两局对基准而不是自我对弈。纯自我对弈的问题是”权重可以整体缩放”：w 和 2w 的战斗力和评估行为完全一样（评估值只是同比例放大），所以适应度曲面上存在无穷多等价最优解，DE 会在一条”平坦山脊”上乱走。对抗一个固定的基准权重就能打掉这个尺度不变性。
static int playGame(boolean evoIsBlack, double[] wEvo, int depthEvo,
double[] wBase, int depthBase, int randomOpen, Random rnd) {
long black = INIT_BLACK, white = INIT_WHITE;
boolean blackTurn = true;
int pass = 0, moves = 0;
while (pass < 2) {
long P = blackTurn ? black : white;
long O = blackTurn ? white : black;
long mvs = legalMoves(P, O);
if (mvs == 0) { pass++; blackTurn = !blackTurn; continue; }
pass = 0;
boolean useEvo = (blackTurn == evoIsBlack);
long mv;
if (moves < randomOpen) { // 随机开局阶段
List<Long> l = bits(mvs);
mv = l.get(rnd.nextInt(l.size()));
} else {
mv = bestMove(P, O, useEvo ? depthEvo : depthBase, useEvo ? wEvo : wBase);
}
long[] np = {P}, no = {O};
apply(np, no, mv);
if (blackTurn) { black = np[0]; white = no[0]; } else { white = np[0]; black = no[0]; }
blackTurn = !blackTurn;
moves++;
}
int diff = Long.bitCount(black) - Long.bitCount(white);
return evoIsBlack ? diff : -diff; // 统一成"进化方视角"的子力差
}
pass 计数器终止条件是 pass >= 2——双方都无子可下时立刻结束，不会死循环。这是黑白棋对局循环最容易出 bug 的地方。
五、完整项目结构与运行结果
othello/
└── OthelloDE.java // 单文件：位棋盘 + Negamax + 差分进化
实测输出：
初始种群最优适应度 = 2.00
第 1 代 最优适应度 = 4.50 当前最优权重 = [-5.69, 4.65, 10.88, 10.32, 1.34]
第 2 代 最优适应度 = 8.00 当前最优权重 = [8.73, 8.32, 8.35, 8.20, -6.93]
第 3 代 最优适应度 = 8.75 当前最优权重 = [4.38, 9.42, 5.28, 3.53, 1.82]
第 4 代 最优适应度 = 37.50 当前最优权重 = [2.51, 7.98, 4.70, 3.70, 0.61]
第 9 代 最优适应度 = 42.50 当前最优权重 = [3.55, 5.83, 9.23, 6.31, 0.79]
第 10 代 最优适应度 = 42.50 当前最优权重 = [3.55, 5.83, 9.23, 6.31, 0.79]
===== 进化结果 =====
行动力 = +3.549
角位 = +5.830
稳定子 = +9.228
前沿子 = +6.313
子力差 = +0.790
总耗时 857 ms
最终对局：进化方(黑) vs 基准方(白)，子力差 = +58
进化权重胜出 ✅
读数上有两点值得注意：
进化后的权重结构与人类经验并不完全一致。稳定子成为最大权重（9.23），角位退到第二位（5.83），而”前沿子”竟然变成了正权重（+6.31）——与理论预期（前沿子越少越好，应当是负权）相反。这是 DE 在有限对局中过拟合的典型表现：由于 frontP 与 frontO 在实战中高度相关，符号翻转的代价被其他特征补偿了。如果想得到更符合理论的权重，需要增加对局数、加深搜索深度。
适应度在 4 代后跳到 37.5 就进入平台期。这符合 DE 的”快速收敛 + 缓慢精修”特性：差分向量在大步长阶段迅速找到好区域，之后步长自动缩小，改进变得缓慢。
最终对局赢了 58 个子力差，说明进化权重在实战上确实强于人工基准权重——尽管每个特征权重的具体数值未必”符合直觉”。这也正好印证了那句话：游戏 AI 的评估函数不是写出来的，是测出来的。
六、复杂度与调参经验
| 环节 | 成本 | 说明 |
|---|---|---|
| 合法着点计算 | 8 次移位 + 5 次循环 | 常数级，约几十纳秒 |
| 一步棋应用 | 一次 flipsFor | 同上 |
| 深度 2 搜索 | 约 10~60 个节点 | 与行动力成正比 |
| 一次适应度 | 4 局 × 约 60 步 × 搜索 | 约 30~50 ms |
| 整体 DE | NP × MAX_GEN × 适应度 | 本文 12×10×4 局 ≈ 0.9 秒 |
调参四条经验：
NP至少取 4×DIM。种群太小（如 NP=5, DIM=5）会让差分向量几乎来自同一批个体，多样性崩溃，陷入局部最优。本文取 12 是 2.4 倍，属于偏小但可接受的配置。F与CR的搭配。F=0.6, CR=0.75是通用默认值。若发现收敛太快（前 2 代就平台），把F提到 0.8~0.9 增强探索；若收敛太慢，降到 0.4。- 适应度里的随机性要”配对”。让所有候选个体面对完全相同的随机开局序列（用相同 seed），否则适应度差异里会混入”运气”成分，选择压力失效。本文每个个体用的 seed 不同，这是可以改进的地方——改成固定 seed 会让 DE 收敛更稳。
- 别在搜索深度上省钱。深度 1 的搜索几乎看不出权重差异（因为只看一步评估），适应度信号极弱。深度 2 是能产生有意义信号的最低配置。
黑白棋最值得玩味的，正是它把”什么是好棋”这个问题从人类直觉手里夺走了。你以为是占角重要，算法告诉你稳定子权重更高；你以为是子力越多越好，实战却证明中盘少子反而有利。用差分进化把这件事量化，比看一百篇攻略都直观。
