棋谱从哪里来
它们来自 ElephantChess,该网站以 GPL-3.0 协议按月发布自己站内对局的匿名数据集。业余对局,这一点很重要:高手漏着的频率不足以支撑一个题库。
每一轮挖掘在花掉任何引擎时间之前,都会先把棋谱清单冻结,并按等级分、时限、结果和长度采样,以免全是快棋。一轮开始之后就不再往里加棋。
算法
两遍扫描:一遍便宜的,跑遍每一局的每一个局面;一遍昂贵的,只跑通过了前一遍的少数局面。
便宜的那一遍把棋谱重演一次,在第 8 个半回合之后的每个局面停下,用 60,000 个节点向 Pikafish 要它认为最好的两步棋。这大约相当于 10 到 14 层深度,浅是故意的,因为这一遍要跑遍所有局面。
当实际走出的那一步比引擎的最佳着法差至少 250 厘兵,并且它留下的局面对另一方而言至少领先 250 厘兵时,这个局面就成为候选。一个只把棋下成均势的漏着不是题目,那里没有东西可找。
厘兵是一个兵的百分之一,引擎用来衡量子力的单位。象棋里没有国际象棋那种兵,所以这个名字连同它的标度都是从国际象棋借来的。本站采用的子力价值把马或炮记作 450,车记作 900,因此 250 厘兵的落差大约是半个马。
另有两个过滤器让这一遍保持诚实。已经以 800 厘兵分出胜负的局面会被跳过,因为把一盘已经赢定的棋赢得更多不算战术。而且每一局最多只交出三个候选,这样一次崩盘就不会用同一个局面的各种变化淹没题库。
昂贵的那一遍把每个候选送回引擎,用 20 层深度和 600,000 个节点,是前一遍预算的十倍,而且只交给它一个不带走子历史的 FEN。同一个局面,没有上下文,引擎无法依赖它刚才做过的搜索。
然后解答线路一步一步地搭起来,每一步都必须自己单独是唯一最佳。这才是一道题目和一串看起来合理的着法之间的区别。主变只是引擎在一次搜索里喜欢的一条线路,它没有说第三步是不是被迫的;一个找到了另一种第三步却被判为错误的解题者,是被骗了。
唯一性不是厘兵差。相差 50 厘兵的两步棋都不错,硬要挑出一步只会因为解题者选对了而惩罚他。让一步棋成为那个答案的,是其余每一种选择都是错的:要么把胜势让掉,要么赢得的子力明显更少。这个判定是一串手工调出来的阈值,谈不上有什么原理,而且它是分不开就拒绝,所以凡是它分不开的都会被丢掉。
代码
便宜的那一遍,精简版。有一个细节把它的开销减半:判断一步棋需要知道局面在这一步之前和之后的分值,而只要扫描保持顺序,这两个值就都已经在手上了,因为走出的这一步的价值就是下一个局面分值的相反数。每个局面搜索一次,而不是两次。
// packages/game/src/puzzles-xiangqi-mining.ts (condensed)
// scans[i] is the engine's best score at the position BEFORE move i, from the
// point of view of whoever is to move there. That one array is enough to
// judge every move in the game: the value of the move played from
// position i is -scans[i + 1], because position i + 1 is the same position
// scored by the opponent. One search per position, not two.
for (let ply = minPly; ply < moveCount; ply += 1) {
const pre = scans[ply]; // the best that was available
const post = scans[ply + 1]; // what they left behind, opponent's view
if (pre === null || post === null) continue;
if (Math.abs(pre) >= decidedCp) continue; // already decided: no tactic
if (post < winCp) continue; // solver must end up winning
const playedCp = -post; // the move, in their own terms
const swing = pre - playedCp;
if (swing < swingCp) continue; // a mistake, but a small one
candidates.push({ ply, swingCp: swing, preBestCp: pre, postBestCp: post });
}还有判定关卡。这里每一个返回 false 的分支,都是一个真实的漏着未能成为题目的方式。
// packages/game/src/puzzles-xiangqi-mining.ts (condensed)
const winRate = (cp) => 1 / (1 + 10 ** (-cp / 400));
// Is this solver move THE answer, or merely a good one? Every branch that
// returns unique:false is a reason a real blunder failed to become a puzzle.
function classifySolverMove(best, second) {
if (!best) return { unique: false, reason: 'missing-best' };
// Mate saturates both centipawns and win%, so mates get their own rule:
// unique only when this is the strictly fastest forced mate.
if (mates(best)) {
if (!second || !mates(second))
return { unique: true, reason: 'fastest-mate' };
return best.mate < second.mate
? { unique: true, reason: 'fastest-mate' }
: { unique: false, reason: 'mate-not-unique' };
}
if (winRate(best.scoreCp) < 0.8)
return { unique: false, reason: 'best-not-winning' };
if (!second) return { unique: true, reason: 'only-move' };
if (mates(second)) return { unique: false, reason: 'runner-up-mates' };
const gapCp = best.scoreCp - second.scoreCp;
if (gapCp < 200) return { unique: false, reason: 'near-tie' };
// The runner-up is wrong if it gives the win away outright...
if (winRate(second.scoreCp) <= 0.6)
return { unique: true, reason: 'runner-up-loses-win' };
// ...or if it still wins, but wins a whole piece less.
if (gapCp >= 250) return { unique: true, reason: 'material-gap' };
return { unique: false, reason: 'alternative-still-good' };
}它留下什么
三分之二的题目以一步不吃子的棋开始。 如果你像我们大多数人那样,先扫一遍能吃子的着法去找战术,那你多数时候看的是棋盘上错误的那三分之一。把这一题走一遍看看:车从棋盘的一端走到另一端,一路上什么都没吃。
只有大约十分之一涉及弃子。 弃子是人们记得住的那种战术,所以我原本以为它的比例会更大。在真实棋手之间的真实对局里,取胜的那一步通常就只是一步棋。这是十分之一里的一个,而且落后的正是解题的一方:开始时少一马一炮。
并不是每道题目都以将死收尾。 大约 40% 是以解题方单纯取得胜势结束的,而这些正是一心找杀棋的直觉会漏掉的。这一题以一步不吃子的棋开始,交还一个兵,换回一个士和两个马。
还有一题连着四个半回合什么都不吃。红方在这里落后 150 厘兵,而引擎认为局面是均势。
它丢掉什么
被丢掉的那些比留下的更能说清一道题目是什么,因为每一个都是一个真实的漏着,而且恰好因为一个原因失败。
| 结果 | 占候选的比例 |
|---|---|
| 拒绝:几乎并列 | 35% |
| 拒绝:太短 | 32% |
| 拒绝:许诺的杀棋没有兑现 | 12% |
| 拒绝:不唯一,或者并非胜势 | 9% |
| 进入复核 | 12% |
几乎并列是最大的一类,约占三分之一。 走棋的一方有一步能赢的棋,而另外还有一步也能赢。两步都成立,于是没有可以用来对照的答案,也就没有题目,尽管那个漏着是真实的,局面也确实是胜势。
太短是另外三分之一,它给出了整个题库里最能说明这个挖掘器是干什么的例子。下面是一个被拒绝的局面。轮黑方走,引擎把它判为必然的杀棋,次优线路是 +1407,而黑方二十步合法着法里恰好只有一步能做到。
另一种失败方式是答案太多而不是太少。下面轮红方走,e8 的马有两种不同的将死方法,c9 或者 g9。这个走子器演示其中一种。两种都能赢,于是没有东西可以用来对照解题者的答案,这个候选就被丢掉了。
许诺的杀棋没有兑现是范围最窄的一类,它并不是一条针对非杀棋题目的规则。它只在引擎返回杀棋分值时触发,也就是说这条线路许诺了一个杀棋,而在七个半回合的上限内把它重演一遍却没有走到。这个许诺无法验证,于是候选被丢弃。评分只是普通胜势的局面根本不会进入这个分支,它们会作为上面那种胜势题目发布出去。
一道题目到头来是什么
大多数胜势局面都有好几步能赢的棋,而这正是它们被淘汰的原因:找到的全部候选里有三分之一只栽在这一点上。一道题目是这样一个局面:它只有一个答案,深到需要下功夫才找得到,稳到一小时后一个更强的引擎仍然同意。
这比一个错误要窄得多。十个错误里有九个不够格。
有一点我宁可说出来而不是藏着:这套判定关卡从来没有拿真人检验过。它的四个阈值来自翻看被拒绝的局面,而不是来自衡量它放行的题目到底好不好,而这些阈值所依据的胜率曲线是从国际象棋继承来的。每道题目的解出率和看答案率都有记录,所以用来给它打分的数据是存在的。