重點摘要

  • Misty 是以 Python 與 Rust 寫成的開源迷霧西洋棋引擎,採 GPL 授權:pip install misty-chess,或在 Mistboard 上直接用網頁瀏覽器對弈。
  • 它遵循 Obscuro(Zhang 與 Sandholm,ICLR 2026):保留與它所見相符的每個盤面,從中抽取固定數量的樣本,再對樣本執行反事實遺憾最小化。
  • 無論信念集合裡有四百個局面還是四千萬個,搜尋成本都維持不變;會增加的是樣本遺漏的部分,而更快的搜尋才能讓樣本變大。
  • 每一處偏離論文的地方都列出了原因,有量測過的也列出了成本;尚未解決的問題則以 GitHub issue 追蹤。

Misty 是開源的迷霧西洋棋引擎,以 GPL 授權釋出。pip install misty-chess,或不必安裝任何東西,直接在網頁瀏覽器裡對弈。

它實作了 Obscuro(Zhang 與 Sandholm,ICLR 2026)的架構,這是第一個在這個遊戲上超越人類的代理程式。論文沒有附上程式碼,arXiv 和 OpenReview 上都沒有。我所知道的另一個開源實作是 obscuro-chess,一個 2026 年 8 月開始的 JavaScript 移植版。Misty 是 Python 與 Rust 的版本,附有文件化的引擎協定,以及一個可以對弈的公開伺服器。它偏離論文的每一處都列在下文,附上原因,有量測過的也附上成本。

它在 Mistboard 上對弈,這是我為這類遊戲打造的網站。lichess 在 2015 年列出它可能加入的變體時,把黑暗西洋棋列為「大概屬於優先順序最低的一批。很難防止作弊(除非有辦法讓對局完全私密),而且完全缺乏觀賞性。需要一套複雜的裁判系統。」Mistboard 就是那個裁判。伺服器持有真實的棋盤。每位棋手、每個引擎、每位觀眾都只會收到該席位被允許看到的內容,所以任何人的網頁瀏覽器裡都沒有可以讀取的隱藏狀態,而對局結束後可以完整重播,任何人都能檢查。

最能推動它的有三種幫助:會下迷霧西洋棋的人和它下一組對局、手上有迷霧引擎的人讓自己的引擎和它對戰,以及任何願意接手一個未解決問題的人。文末會說明做法。

問題所在

在迷霧西洋棋裡,你只看得到自己棋子能走到的格子。對手的著法是看不見的。你觀察到的是它們的後果:你的一枚棋子消失了、你一直盯著的某個格子變了,然後你從那裡往回推。

. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . p . . .
p . . . . . . .
. . P P . N P .
P P . N P P B P
R . B Q . R K .
白方所見
r . b q k . . r
. p . . . p p p
. . p b . n . .
. . n p p . . .
p . . . . . . .
. . P P . N P .
P P . N P P B P
R . B Q . R K .
真實局面
r . b q k . . r
. p . . . p p p
. . p b . n . .
. . n p p . . .
p . . . . . . .
. . . P . . . .
. . . . . . . .
. . . . . . . .
黑方所見

本站一局真實的五分鐘對局中的第 9 回合,Misty 執黑。三個盤面是同一個局面,都以白方視角擺放。白方看不到黑方的 14 個棋子;黑方看不到白方的 15 個。雙方都從未看到中間那個盤面。

這拿掉了每個傳統引擎賴以建立的前提。Stockfish 搜尋的是一棵以單一局面為根的樹。在迷霧下沒有單一局面。只有與你觀察到的一切相符的所有盤面所構成的集合,而你需要一著在整個集合上都站得住腳的棋。

把這個集合叫做 P。一局棋中有兩次,它小到可以畫出來。

r n b q k b n r
p p p . p p p p
. . . . . . . .
. . . p . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
1.Nf3 d5 2.Ng5 之後黑方所見
r n b q k b n r
p p p . p p p p
. . . . . . . .
. . . p . . B .
. . . . . . . .
. . . P . . . .
P P P . P P P P
R N . Q K B N R
一個主教
r n b q k b n r
p p p . p p p p
. . . . . . . .
. . . p . . N .
. . . . . . . .
. . . . . . . .
P P P P P P P P
R N B Q K B . R
一個騎士

與之相符的兩個盤面

g5 是這一橫列上黑方唯一看不到的格子。

r . b q k b . r
. p . n p p p p
. . p . . n . .
p . . p . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
輪到黑方,第 6 回合
r . b q k b . r
. p . n p p p p
. . p . . n . .
p . . p . . . .
. . . . . P . P
P . N . . . . .
R P P P P . P .
. . B Q K B N R
r . b q k b . r
. p . n p p p p
. . p . . n . .
p . . p . . . .
. . . . . . . .
. . P P . . P .
P P . B P P B P
R N . Q K . N R
r . b q k b . r
. p . n p p p p
. . p . . n . .
p . . p . . . .
. . . . . . . P
. . P . . N . .
P P Q P P P P .
R N B K . B R .
r . b q k b . r
. p . n p p p p
. . p . . n . .
p . . p . . . .
. . . . . . . .
. . . P . N P .
P P P N P P B P
R . B Q . R K .
r . b q k b . r
. p . n p p p p
. . p . . n . .
p . . p . . . .
. . . . . . . N
. P . . P . . .
P B P P . P P P
R N Q . K B . R

236,480 個中的 5 個

一個真實的中局,出自下文嵌入的對局。其中四個從集合中均勻抽取;第五個是真實盤面。

黑方從自己視野中的一個缺口,推斷出一枚從未看見的棋子存在。這種推理在一般西洋棋裡沒有對應。推理之後仍然剩下兩個盤面,而黑方必須同時針對兩者走棋。

到了中局,已經沒有東西可以畫了。引擎無法針對它所在的局面選一著,因為它不知道那是哪一個局面。它選的是一著會在所有局面中同時被走出的棋。P 會變得多大,就是整個問題的核心。

到 2026 年 9 月為止,在與 Misty 對弈的 216 局中,決策所面對的相符盤面中位數是 74 個,每十次就有一次超過 7,000 個。與人類對弈時最大達到 8,200 萬個;在 Misty 自我對弈的一局中,則是 3.46 億個不同的盤面。論文指出這個遊戲中單一資訊集可高達 109。

101001K10K100K1M10M 10203040 對局數 最差 1% 最差 10% 中位數 Misty 的回合數 相符的局面數
與人類對手的 216 盤已完成對局中信念集合的大小,依 Misty 自己的回合數排列,對數刻度。色帶是中間一半的對局,虛線是最差的十分之一,點線是最差的百分之一。最差 1% 的曲線止於第 28 回合,之後剩下的對局不到 100 盤,第 99 百分位數就只是最大值。座標軸下方的條帶是仍在進行的對局數:第 1 回合 216 盤,到第 48 回合剩 11 盤。

第一次決策面對的永遠恰好是 20 個盤面,每個合法的開局著法對應一個。到第十二次決策時,中位數仍只有 84,而最糟的十分之一面對 19,427 個,最糟的百分之一峰值接近 250 萬。接著,雙方棋子的接觸會讓它縮小。每一次吃子、每一枚走進視野的棋子都是資訊;到第四十五次決策時,在撐得了那麼久的對局裡,中位數已降到 42。這是遊戲本身的性質,而不是一種策略:Misty 沒有任何獎勵獲取資訊的項,也不會刻意製造接觸,而這正是它可以學著去做的事情中比較有意思的一項。

對局

四盤對局:兩盤是 Misty 對看不見的東西進行推理,一盤是迷霧讓雙方都陷入混亂,還有一盤敗局,顯示出信念集合的大小所帶來的代價。每個棋盤上方都有白方、真實、黑方的切換開關:選一方,就只看得到那一方能看到的東西。

Misty 自我對弈,每著三十秒。一次吃子讓黑方得知白方的后只可能在某一格上。黑方把騎士走到白方看不見的格子去攻擊它,下一著就吃掉了后。看得見整個棋盤的 Stockfish 不會走這步騎士;在迷霧下,這步棋卻能取勝。這份研究收錄了全部十一盤自我對弈。

Misty 對一位匿名訪客,時間控制為十分鐘加五秒。11…b6 之後,a6 上的一枚黑方騎士無人保護,而 Misty 連續五著都沒去吃它:在它認為可能的大多數局面中,這個格子是有保護的,通常是被一枚主教保護,而那枚主教實際上在第 2 著就已經離開 c8,出了它的視野。等到第二個攻擊者就位時,它用主教去吃,冒險的是一枚主教而不是它的后。訪客也看不見白方位於 a3 的后,用后吃回,結果把后丟了。訪客在第 37 著認輸。

另一盤自我對弈顯示了當雙方都看不太到東西時,迷霧會造成什麼。黑方在白方看不見的地方做了后翼王車易位,而當一枚黑方騎士落到 c5 時,白方吃掉了它:它以為後面那一格 d8 上是黑方的后,並認為那裡是城堡的機率只有大約百分之一。這次吃子讓 d 線朝白方自己的后打開。從那之後,兩個后都在雙方都無法完全看見的棋子之間橫衝直撞,子力每隔幾著就擺盪一次,直到白方確定了它所需要的那唯一一個事實,對局才結束。它從未看見黑方的王,但它認為可能的每一個局面都把王放在 c8,而 27.Re8+ 找到了它。

還有一盤敗局,輸給一位朋友,顯示出信念集合的大小所帶來的代價。第 30 著時,Misty 吃了一個它認為大概有保護的城堡,而它安全檢查中的一個漏洞讓這次吃子通過了;它為這個城堡丟掉的后,促成了 1.6 版。接著,大幅領先的白方在 Misty 看不見的地方安靜地走棋。每一著看不見的棋都讓 Misty 必須保留的局面數倍增:吃子後是 4 個,五著後是 55,000 個,接著是 140 萬、360 萬和 650 萬。它的著法依序花了 9、11、16 秒,而預算只有五秒。下一次更新到 950 萬個局面時,超過了伺服器等待回覆的時限,伺服器判 Misty 棄權落敗,而它的棋鐘上還剩將近四分鐘。Misty 與人類對弈的研究還收錄了另外七盤。

Misty 如何選擇著法

六個步驟,遵循論文,採用 1.6 版出貨時的設定(v1.6-net-prune 設定檔,位於 misty-chess 0.1.3)。

信念:每一個相符的盤面

在對手走了看不見的一著之後,Misty 根據它觀察到的內容過濾 P,剔除所有被這次觀察排除的盤面。在自己走完一著之後,它會把每個盤面都往前推進。P 是精確持有的,每一個相符的局面都以 Rust 列舉出來,並在每個半回合重建:沒有粒子濾波器,沒有近似。正式環境把它的上限設為 1,600 萬個局面。

超過上限時,Misty 會保留一組均勻隨機樣本並繼續下;紀錄中最糟的一局這樣做時,峰值達到 7.7 GB。在 6 月唯一一盤越過上限的對局中,對手在視野外把兵升變的同時,信念集合成長到 8,200 萬個盤面,而真實局面從樣本中掉了出去。Misty 接下來的兩次決策,面對的都是一個不包含它實際所在盤面的集合。接著,那個新的后吃掉了它的王。每個半回合都只從上一個半回合建構,所以沒有任何東西能把真相找回來;用新的抽樣種子重播觀察歷史則可以做到(#10)。如果 P 變成空集合,引擎會拋出例外而不是去修補它,因為空集合代表觀察模型是錯的。

Rust 列舉器大約比 Python 版快 500 倍。Python 版被保留下來當作基準:測試套件會重播真實對局,並要求兩者在每個半回合都一致。這項檢查抓到的錯誤比它付出的成本還多,也是這個設計中最值得保留的部分。

抽樣:從 P 中取固定數量的世界

Misty 從 P 中隨機抽取固定數量的根世界:1.6 版是 32 個,這是設定檔中的一項設定,而論文用的是幾百個。把它固定下來,正是搜尋成本不會隨信念集合增長的原因:不論 P 裝了四百個局面還是四千萬個,搜尋看到的數量都一樣。為什麼不調高它,是一個關於時間的問題,答案在一著的成本一節。

每一個相符的盤面都得到相同的權重,雖然它們的可能性並不相等。一個對手花了三步棋來回挪動城堡的盤面,符合證據,實際上卻幾乎不可能發生。Misty 沒有對手模型可以區分它們。Obscuro 也沒有。obscuro-chess 有:一個用 246 盤 Chess.com 對局擬合出來的著法先驗分布。

搜尋:一棵以 Misty 所見為鍵的樹

被抽樣的世界共同長出一棵博弈樹。樹中的一個節點就是一段觀察歷史:輪到走棋的一方到目前為止看到的一切。對 Misty 來說看起來一模一樣的世界會落在同一個節點上,並共用同一個策略。這種分組就是資訊集的意思,也是搜尋最後只回傳一個答案的原因。

它排除了最直覺的做法,也就是把每個世界都交給 Stockfish,然後計票。投票讓你在無法分辨的局面中下不同的棋,但在棋盤前你做不到這件事。把 Stockfish 在各個世界的分數取平均也行不通,原因更隱微:每個分數都假設在這一著之後,你會知道自己身處哪個世界。

取兩個機率相等的世界,以及兩種著法。在等待之後,下一著是在兩個格子之間猜一個:猜對就贏,猜錯就輸。穩健則在兩個世界中都有些微優勢。

                 world 1   world 2   average   really
wait, then guess   +1        +1        +1        0
safe               +0.3      +0.3      +0.3     +0.3

一次只拿到一個世界時,Stockfish 永遠猜得對,因為在它的世界裡沒有什麼好猜的,所以等待平均下來是必勝。在棋盤前,Misty 無法分辨這兩個世界,只有一半的機率猜對,於是等待毫無價值。搜尋避開這個問題的方式,是把看起來一樣的世界放在同一個節點上,強迫兩者做出相同的猜測。

對手也有發言權。你看到什麼是由他們決定的,所以如果你對某個隱藏威脅總是用同一種方式回應,他們就會學起來,把局面引向你沒有防守的那個分支。Misty 尋找的是:面對一個知道它如何做決定的對手時,讓步最少的策略。有時候,那個策略是在兩著之間擲硬幣。

找出它的工具是反事實遺憾最小化,也就是解決了撲克的那一系列演算法。

每個節點都持有一個混合:每種著法各有一個機率,一開始平均分配。對樹的一次遍歷會由下而上做四件事:

leaf       v = tanh(centipawns / 500)
move       v(a) = average of a over the worlds
node       v(I) = Σ x(a) · v(a)
regret     R(a) ← max(0, R(a) + v(a) − v(I))
next mix   x(a) ∝ max(0, R(a) + Δ(a))

這裡 x 是節點目前的混合,Δ(a) 是 R(a) 剛剛得到的變化量。第一行把 Stockfish 的分數放到 −1 到 +1 的尺度上:多一個兵大約是 +0.2,多一個城堡大約是 +0.75,吃掉王則恰好是 +1。第二行和第三行是平均值。在輪到對手走棋的節點上,其值會以對手目前的混合加權,所以一著的價值,就是它在 Misty 無法分辨的所有世界中、面對對手此刻的下法所能得到的收益。

遺憾是每種著法比混合表現好多少的累計總和。假設某個節點以各一半的機率下兩種著法,而這一次遍歷它們的得分是 +0.12 與 +0.08。這個節點的價值是 +0.10,所以第一種著法累積了 0.02 的遺憾,第二種則降到零,因為遺憾永遠不會是負的。下一次遍歷時,混合就會偏向第一種著法。與此同時,每個對手節點也針對 Misty 的混合做了同樣的事,這會改變價值,而價值又會再次改變混合。當任何節點上都沒有一種著法勝過它自己的混合時,遍歷就不再改變任何東西。那就是均衡,而它需要幾千次遍歷而不是一次,因為雙方都在互相調整。

最小的版本可以放進一張表。你可以守住兩個格子中的一個,而對手攻擊其中一格,你看不到是哪一格。對 a 的攻擊若無人防守,你會損失一整分,對 b 則是半分。執行同樣的更新,雙方同時進行:

遍歷 你守 a 對方攻 a
1 100% 0%
2 11% 87%
3 83% 53%
10 72% 28%
20 67% 33%

起初雙方都對彼此反應過度,然後才穩定下來:每三次中有兩次守 a,任何一方都無法藉由改變策略做得更好。這個穩定下來的混合,就是搜尋要找的東西。

最後一行是相對於單純遺憾匹配的唯一改良。加上最近一次的變化量,等於預測下一次遍歷會和這一次相似。正是這一點讓 Misty 最後可以依照目前的混合來下,而不是依照它經過的所有混合的平均;這一系列方法稱為預測式 CFR+。

r . b . k b . r
p p p q p p p p
. . n . . n . .
. . . p . . . .
. . . . . . . .
N . . . P N P .
P P P P . P R P
R . B . K B . .
r . b . k b . r
p p p q p p p p
. . n . . n . .
. . . p . . . .
P . . . . . . .
N . . . P N P .
. P P P . P . P
R . B . K B R .
r . b . k b . r
p p p q p p p p
. . n . . n . .
. . . p . . . .
. . . . . . . P
. . . . P . P .
P P P P . P N .
R N B . K B . R
r . b . k b . r
p p p q p p p p
. . n . . n . .
. . . p . . . .
. . . . . . . .
. . . . P P P .
P P P P N . K P
R N B . . B . R

從 12,567 個中抽取的 32 個世界裡的四個。著色的是這四個世界有分歧的 13 個格子,而黑方一個也看不到,所以對搜尋來說這四個是同一個局面。

e50.389Qf50.388a50.155h50.06701.0

黑方 30 個合法著法上的一個策略。另有 5 個著法合計不到 0.001。

由於每個抽樣世界呈現給黑方的觀察歷史都相同,它們共用搜尋樹中的同一個節點,這步五秒棋的 20,768 次迭代都在那裡一起累積遺憾。輸出是單一的機率分布。之後還必須把它落成一著,在這裡就是在 0.0017 的差距上把 e5 和 Qf5 分開。

那是一次五秒的真實決策,也是實戰中出現的擲硬幣:兩種著法的差距在 0.002 以內。每一次迭代是對所有節點做一次遍歷,然後新增一個葉節點。到了 2,000 個葉節點時,樹停止成長,遍歷則在固定的樹上繼續進行,直到時間用完,因此一著中大部分的迭代都在精修混合,而不是擴展樹。時間是唯一的停止條件;沒有任何機制會檢查混合是否已經穩定(#8)。

範圍:要往外解多遠

在迷霧下,固定深度是錯誤的停止點。重要的是一個局面離某個可能被人混淆的局面有多遠。只要任一方無法分辨兩個節點,Misty 就把它們連起來,並且只擴展在幾步這樣的距離之內的葉節點,這也是它開始推理對手對它有哪些不知道之處的地方。

評估值:葉節點上的 Stockfish

新的葉節點由深度一的 Stockfish 18 評分。它以單一執行緒、16 MB 的雜湊表執行,並從固定在某個 commit 的原始碼編譯,好讓每一次部署都執行同一個二進位檔。在固定版本之前,正式環境執行的是 Linux 發行版附帶的版本,也就是 14;在唯一比較過兩者的那組實驗中,它們的差異在雜訊範圍內。版本沒有再進一步比較,因為葉節點評估只佔一著的 11%。Stockfish 從來看不到迷霧。它只回答「這個具體的盤面有多好」,這是它最擅長回答的問題,而迷霧推理則留在上面那一層。這有一個上層無法彌補的代價:兵的對峙對傳統引擎來說是中性的,在迷霧下卻是決定性的,因為先吃子的一方會獲得視野。論文估計評估器的價值約為 262 Elo。

落子:從機率分布中選出一著

搜尋結束時,每種著法都有一個機率,而 Misty 下機率最高的那一著。Obscuro 可以安全地在著法之間混合,因為它會拿從上一著延續下來的策略來檢查候選著法。Misty 在兩著之間會丟掉它的樹,所以沒有東西可以拿來檢查混合;強制混合的結果是 0 勝、7 負、1 和。

防護機制最後執行,否決那些在信念集合中足夠多的部分裡會白送大子、或讓王走進被吃位置的著法。它們不在論文裡,也不是罕見的最後防線:在上面那十一盤對局中,它們在 17% 的著法上取代了搜尋的選擇。它們能抓住那些讓引擎在人類眼中顯得愚蠢的錯誤,但自己也會造成一些錯誤。在上面那盤自我對弈中,雙方最糟的著法裡有三著是防護機制選的,而不是搜尋選的:它們只往前看一著,而兵的雙重攻擊需要兩著。一個能自己看出這些危險、讓防護機制得以拿掉的搜尋,是大多數其他問題底下的那個未解決問題。

設定

設定項目 出貨值 調高的效果
信念上限 16,000,000 個局面 精確性維持得更久,代價是數 GB 的記憶體
抽樣的根世界數 32 看到更多的信念集合,但每個世界的迭代次數較少
擴展預算 每著 2,000 個葉節點 樹更寬,遍歷它也更慢
範圍階數 2 子賽局更大,每著重新求解的部分更多
葉節點評估深度 1 葉節點分數更好,但數量大幅減少
每著時間預算 5 秒 以上所有項目,按比例增加

根世界數、擴展次數與範圍都寫在設定檔 v1.6-net-prune 中;信念上限與每著時間預算由呼叫端提供;葉節點深度則固定在評估器裡。階數為 2 時,三個混淆步以內的葉節點都有資格擴展,而一到兩步之間的區段會在搜尋中重新求解。

一著的成本

正式環境中的每一著都會記錄它的時間花在哪裡。以 913 著取平均:

步驟 平均 佔比
均衡遍歷 3.91 秒 69%
新葉節點上的 Stockfish 0.61 秒 11%
擴展的其餘部分 0.18 秒 3%
葉節點選擇 0.16 秒 3%
範圍 0.06 秒 1%
搜尋之外:信念更新、防護機制、落子、傳輸 0.68 秒 12%
總計 5.68 秒  

均衡遍歷是每次迭代對樹中每個節點的更新,這就是它佔大宗的原因。信念更新這個大家都預期會很昂貴的步驟,平均只要 6 毫秒。防護機制在搜尋計時停止後才執行,這就是為什麼一著五秒的棋要花 5.7 秒;在一次於本機剖析的決策中,它們花了 1.2 秒。

一著的上限是實際耗時:time_budget_seconds,正式環境為 5,棋鐘可以把它調低。設定檔也帶有一個迭代上限,設為一千萬,好讓時間總是先觸及上限。如果不給時間預算也不給棋鐘,迭代上限就會成為停止條件。一次 5,000 次迭代的執行,在三個獨立的行程中選了同一著、建出同一棵樹,並給出相同的前四名機率。任何你想重現的東西都該用這個模式,因為計時的著法取決於機器當下跑得多快。

成本也是那個顯而易見的問題的答案:論文用幾百個世界,為什麼只抽 32 個?每一次遍歷都會走過每個世界,所以一次遍歷的成本與世界數成正比。同一個局面、同樣的時間:

根世界數 5 秒內的迭代次數 樹節點數
32,出貨值 45,068 6,322
128 10,645 25,291
200 5,958 43,070
256,論文範圍的上限 4,958 52,557

世界數變成八倍,換來的是遍歷次數少了九倍。2,000 個葉節點的預算也由所有世界共用,所以在 256 個世界時,每個世界只分到大約八個葉節點,而不是六十個,而且在一著 40% 的時間裡樹都還在成長。在 32 個世界時,樹很早就完成,大約 43,000 次遍歷在上面精修混合。更多世界能看到更多的信念集合,但每一個都解得更差。在固定五秒的對戰中,64、128 和 200 個世界除了一格以外,每一格都輸給 32 個世界。

所以要調高它,得先提升吞吐量,而吞吐量就在均衡遍歷裡。把它限制在擴展已經遵守的範圍內(#6),或是把它分散到多個核心上,才是倍數提升的來源。照抄論文一個求解器、兩個擴展器的分工則不是:那是把擴展平行化,而擴展只佔時間的 14%。計時的數字取決於機器,所以這裡的筆電數字只能彼此比較,不能和正式環境比較。

與論文對照

Misty 以 Obscuro 為指引,而不是忠實重現它。逐列與論文對照:

論文中 本專案 原因
搜尋樹與均衡在著法之間延續 每一著都丟棄並重新抽樣 1.1 版建置,1.2 版移除;見下文
觸及贈與,依每個資訊集設定 單一純量邊際,設為零 未建置
安全裝置所用的藍圖策略 在 P 小時覆蓋率約 38%,大規模時約為 0 第一列的結果
Resolve 與 Maxmargin 兩種模式,彼此切換 只有 Resolve 切換功能藏在一個環境變數後面,從未出貨
由幾百個世界組成的根集合 32 吞吐量;見「一著的成本」
帶部分剪枝的 CFR,一次迭代的耗時通常隨樹的規模次線性增長 每次迭代都走遍整棵樹 未建置;樹停在 2,000 個葉節點就是因為它(#6)
一個求解執行緒,加上兩個擴展共用樹的執行緒 單一執行緒 未建置,而且它平行化的會是時間上本來就分配不足的那一部分

第一列造成了第二列和第三列。藍圖就是上一著的搜尋,所以在重新抽樣根世界的情況下,它在 P 小時只覆蓋約 38% 的世界,大規模時則完全覆蓋不到。少了它,Misty 的安全裝置會過度防守,所以只在開局時啟用。

延續的樹在 1.1 版建置、1.2 版移除:在開局,它在真實盤面上的代價約為 125 厘兵,迭代次數也少了 21%。中局才是 P 很大、藍圖也才重要的地方,它應該在那裡回本。

接下來

這些工作以 issue 的形式追蹤在 strength(棋力)標籤底下,每一個都附有證據、建議的修正方式,以及能證明它奏效的量測方法。依照各自預期的收益排序:

  1. 吞吐量(#6)。均衡遍歷在每次迭代都會走過整棵樹,雖然範圍已經限制了哪些葉節點可以成長。用同樣的方式限制遍歷,應該能帶來倍數而非百分比的提升,而世界數也在等它:在目前速度下由 32 個世界勝出的那組對戰,會在新速度下重新跑一次。
  2. 中局裡延續的樹(#11)。在信念集合很小的開局,於著法之間延續搜尋大約付出了 125 厘兵的代價。論文說中局才是它回本的地方,而著法之間的混合以及一個能運作的安全裝置都仰賴它。
  3. 不需要防護機制的搜尋。它們在 17% 的著法上取代了搜尋的選擇,也造成了一些最糟的著法。像兵的雙重攻擊這種兩著之後才出現的危險,必須由搜尋本身看出來;檢驗方式是一場關掉防護機制的對抗賽。
  4. 解法已知的修正:動用累積的時間(#7)、在混合穩定時停止而不是等時間用完(#8)、對光桿王把贏的殘局下完(#9),以及在超過信念上限後找回真實盤面(#10)。

本文描述的是 2026 年 9 月的 1.6 版。issue 反映的才是目前狀態。

來下棋、來測試、在它之上打造

來下棋。Misty 在 Mistboard 上,不需要帳號也不用安裝。那裡的機器人執行的是與儲存庫出貨版本相同的引擎和設定檔。與人類的對局是 Misty 最稀缺的資料,它們能顯示自我對弈顯示不出來的東西。

與我聯絡。如果你會下迷霧西洋棋並想和它下一組、研究不完全資訊賽局、想在研究或專案中使用 Misty,或是在這篇文章裡發現了錯誤,請寫信到 contact@brianhliou.com。

在它之上打造。pip install misty-chess 就能取得引擎;README 說明了 Rust 擴充模組,以及純 Python 備援版本的代價。引擎透過 stdio 使用 JSON 協定溝通,文件在儲存庫中。伺服器只會傳送經過遮蔽的觀察,所以執行中的引擎無從得知真相。

帶你的引擎來。Misty 幾乎沒有可以拿來衡量自己的對象。一個使用這套協定的迷霧西洋棋引擎可以在同一個伺服器上和它對弈,而且不論結果如何都會公開。