引擎本来会做的事

这点值得单独说,因为它决定了后面的一切。引擎对胜利条件的理解是完整的:进入兽穴被算作将死,在候选着法里排在最前,并且在静态搜索中被搜索。它缺的是预见能力,不是理解力。

它照样能赢,因为斗兽棋由子力主导,而评估函数对子力的读取是精确的。在进入兽穴的那一刻,胜方的中位子力领先 20 分,大约一只猫。只有 4.7% 的对局是由持平或落后的一方赢下的。引擎是怎么搭建的,以及它与其他引擎对比的测量结果,见斗兽棋引擎一文。

没有这个概念时它会怎么走

研究中的第 10 局取决于四着棋,它比下面任何表格都更好地解答了这个问题。

斗兽棋的中路是三行水面,d 路夹在两条河之间,只有一格宽。在这些对局进行时 Mistboard 采用的规则下,虎只能纵向跳水,绝不能横向跳,所以站在那条通道里的虎几乎无处可去。自 9 月 21 日起,虎也像狮一样可以横向跳,遵循中国的规则体系;这条通道对它不再是陷阱,下面这条着法线是旧规则下的产物。

第 20 回合,蓝方行棋。红方的虎刚在 d6 吃掉一只狼,现在站在通道里,在蓝方象下方一格,而象的等级高于它。

第 20 回合时红方在 d5 的虎只有两个合法着法,向前或向后,都还在通道里。它选择向前吃掉了狼,这让蓝方损失 40 分,同时把虎停在了蓝方象的旁边。

蓝方的象等级高于虎,所以这看起来像是送礼。蓝方没有立刻吃,这正是那个问题单 要我们解释的一着。引擎的理由是那只虎逃不掉:象在 d7 时,虎唯一的着法是 d5,而从 d5 出发唯一的着法是 d4,被一个能吃掉它的棋子沿着单车道通道一路赶下去。去吃它等于花一个先手收取已经到手的东西。蓝方走了一着白得的改善着法,两回合之后在 d5 而不是 d6 吃掉了虎。两条线路达到的子力完全相同。

决定这局胜负的四着,按着序编号:

41  Red   tiger     d6 -> d5    its only move, back down the corridor
42  Blue  elephant  d7 -> d6    steps into the corridor after the tiger
43  Red   lion      c3 -> c7    jumps into the square the elephant just left
44  Blue  elephant  d6 -> d5    takes the tiger, up a piece
    Red's lion is now three moves from a den Blue cannot defend

那只虎是诱饵。不是弃子:它反正几乎已被困死,而吃掉狼得 +10,几乎所有其他选择都是 +6,差距是四分而非一个计划。它在离开棋盘的路上所做的,是把唯一等级高于狮的棋子拉下 d 路。第 20 回合时狮的跳跃评估值是 −195,因为 c7 紧邻 d7 上蓝方的象。两回合之后同样的跳跃就能取胜,因为象走开了。

这段着法结束时蓝方领先 13 分,然后输掉了。

把这个计划复述一遍,听起来像是引擎理解了冲兽穴竞速。它并没有。那份评估函数里从头到尾都没有冲兽穴竞速项,在这个项目之前和之后都没有。它搜索了五百万个节点,这条线路就出来了。这就是全部结果:那个问题单 想装进去的行为本来就在,是由深度而不是知识产生的。

基础发生率:4.7% 的对局,在全力对弈强度下测量

172 局自我对弈,采用生产环境的每着五百万节点预算。

终局方式占比
重复和棋52.9%
进入兽穴26.2%
其中真正的竞速4.7%
无进展判和20.9%
真正的竞速,指胜方在终局前十着时持平或落后的对局。

同一套测试框架在 200k 节点下报出 22% 的竞速比例。棋力更弱会把这个数字大约放大五倍。便宜的测量方式是现成的,而它会朝着「值得多做工作」的方向错上 5 倍。

上限空间:搜索加深 12 倍只换来约一着

对 8 场竞速中的每一场,我们在败方的对局中二分查找每个预算最早能识别出必败的那一着,然后取差值。

60M 节点提前看出竞速局数
0 着4
2 着3
4 着1
每着六千万节点对五百万节点,共 8 场真正的竞速。

六千万节点对五百万节点,更深的搜索看到败势的时间中位数只提前一着:最多四着,而在一半的竞速里根本没有提前。在那个视野之前,两者走势非常接近,只在最后一两着才分开。

这个数字本该让项目就此终结。如果十二倍的搜索只挽回大约一着,那这个信息并不是摆在那里、等着一个更聪明的评估函数去发掘。

路线 A:搜索延伸,免费版与付费版

没有真的实现就先探了一下。测试框架里的一条策略规定:只要有棋子处在对方兽穴 R 格之内,就给该方更大的节点预算,这是任何真实延伸的严格上界。

在算 Elo 之前的第一个发现:触发条件并不稀疏。

半径触发的着数占比
223%
343%
472%

斗兽棋棋盘很小,兽穴就在底线上。在 R=4,也就是及早看到竞速所需的半径下,这个延伸就等于「到处都多搜十二倍」,所以「精准手术」这种设想从一开始就是错的。

在 R=2,每组 300 对交换先后手的对局:

实验组Elo相对对照组的节点数
兽穴附近 12 倍深度,免费给予+453.3×
预算中性:基础 3.7M,兽穴附近 10M−151.04×
预算中性:基础 1.1M,兽穴附近 20M−120.98×

同一个想法,同一份代码,符号相反。引擎那五百万节点是由玩家愿意等多久固定下来的,所以真实的延伸没法凭空造出深度:它只能从搜索的其他部分抢。免费那一组测的是额外算力,跟兽穴毫无关系。

我们之所以跑了预算中性那一组,是因为 +45 看起来好得不真实。就此停手,就会为一个价值略低于零的功能花掉一周工作。

两组各只花了一个下午,因为都不需要动引擎。那个延伸只是测试框架里一条根据棋盘条件改变节点预算的策略。对于任何形式为「让它在 X 上更聪明」的提案,先免费给它完美的 X,是判断 X 到底重不重要的最便宜的办法。

路线 B:评估项本身

我们还是把它做了出来,因为延伸失败的原因并不适用于一个评估项。延伸消耗节点;而评估项在每个叶子节点上几乎不花成本。

这是当时的评估函数。在棋盘上做一次循环,每个棋子独立贡献:

for idx in 0..N {
    let v = VAL[role_of(code) as usize];
    let friendly = color_of(code) == me;
    s += if friendly { 2 * v } else { -2 * v };

    // Advancement toward the relevant den: the enemy's for our pieces, ours for theirs.
    let target = if friendly { enemy_den } else { own_den };
    let dist = manhattan(idx as u8, target);
    let advance = if dist <= 1 { 400 } else { (16 - dist) * 3 };
    s += if friendly { advance } else { -advance };
}

那个推进项正是评估函数对竞速视而不见的原因,而根源是对称性。我们的奔跑者距你的兽穴三格得 +39。你的奔跑者距我们的兽穴三格得 −39。双方同时冲刺得到的数字接近零,于是恰恰在胜负最为确定的那一刻,局面读起来风平浪静。

所以这个项不能再是一个逐子奖励。它必须是每方一个判定,只计算一次,把两个奔跑者互相比较:

for side in [me, 1 - me] {
    // Nearest enemy runner to this side's den, and this side's nearest defender
    // to its own trap ring.
    let (mut att, mut def) = (99, 99);
    for idx in 0..N { /* ...scan once... */ }

    if att > RACE_RADIUS { continue; }   // no race here: contribute nothing

    // The side to move gets one free step in the race for its own den.
    let margin = att - def + i32::from(side == me);
    let pen = if margin <= 0 { RACE_LOST }
              else if margin == 1 { RACE_TIGHT }
              else { 0 };
    score += if side == me { -pen } else { pen };
}

防守方是按到陷阱环的距离来度量的,而不是到兽穴。这才是正确的拦截区,因为兽穴的三个相邻格就是它的三个陷阱,而站在陷阱上的棋子不论等级都能被任何防守方吃掉。走进你兽穴的象必须穿过一个你的鼠能吃掉它的格子。

在它专门针对的那些局面里,它改变了 17% 的选着,并且在节点数相同时实际耗时增加约 17%。每个权重跑 300 对交换先后手的对局,在还没把这项成本算进去之前:

权重Elo
10−3
25+9

无效,而且这还是在对它有利的条件下得出的结果。

我们会保留下来的东西

把预算固定住,否则你测的就是预算。实验的免费版本是建起来最方便的那个,而它会递给你一个自信的正数。不管这个改动本该从哪里挪用资源,就从那里挪,然后看结果还站不站得住。

这个陷阱在一天里坑了我们两次。同一个下午做的蔑视值扫描显示,分出胜负的对局从 32% 升到 50%,而这本来就是提高蔑视值必然产生的结果,因为自我对弈扫描中双方都用了同一个设置。只有让两个取值互相对抗,才能看出它是否付出了代价。它没有,所以那一项上线了。

评估函数的这个短板是真实的,诊断也没错。只是它背后什么都没有。在同一批对局里找到的两个常数,一个是过早结束对局的无吃子和棋限制,一个是接近零的和棋蔑视值,把斗兽棋自我对弈从四分之一的对局分出胜负提升到了大约一半,而这两者都没教引擎任何东西。那个问题单 要求的是理解。理解从来就不是瓶颈。

这些对局是公开的,上面那个局面也是。分析棋盘运行的是同一个引擎,采用的是如今虎可以横向跳出通道的规则,所以如果你觉得蓝方当时该吃掉那只虎,你可以让它把一条线路走完。

浏览这 52 局打开该局面