棋譜從哪裡來
它們來自 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。這個走子器演示其中一種。兩種都能贏,於是沒有東西可以用來對照解題者的答案,這個候選就被丟掉了。
許諾的殺棋沒有兌現是範圍最窄的一類,它並不是一條針對非殺棋題目的規則。它只在引擎返回殺棋分值時觸發,也就是說這條線路許諾了一個殺棋,而在七個半回合的上限內把它重演一遍卻沒有走到。這個許諾無法驗證,於是候選被丟棄。評分只是普通勝勢的局面根本不會進入這個分支,它們會作為上面那種勝勢題目發布出去。
一道題目到頭來是什麼
大多數勝勢局面都有好幾步能贏的棋,而這正是它們被淘汰的原因:找到的全部候選裡有三分之一只栽在這一點上。一道題目是這樣一個局面:它只有一個答案,深到需要下功夫才找得到,穩到一小時後一個更強的引擎仍然同意。
這比一個錯誤要窄得多。十個錯誤裡有九個不夠格。
有一點我寧可說出來而不是藏著:這套判定關卡從來沒有拿真人檢驗過。它的四個閾值來自翻看被拒絕的局面,而不是來自衡量它放行的題目到底好不好,而這些閾值所依據的勝率曲線是從國際象棋繼承來的。每道題目的解出率和看答案率都有記錄,所以用來給它打分的數據是存在的。