猜拳遊戲在實踐中並未被破解

大家好，在此分享我對中階猜拳（剪刀石頭布）策略的 Inkhaven 說明，同時也想探討一種評估猜拳機器人的替代方式。這篇文章比大多數 Inkhaven 的貼文更精煉，但仍請留意，這內容大部分是在約 2 天內完成的。

在實踐中，猜拳問題尚未被完全解決。

當我在 2016 年剛開始學習程式設計時，我斷斷續續花了幾年時間，試圖製作出優秀的猜拳機器人。我總共大約投入了 20 個小時。我最好的程式在面對所有對手時，勝率約為 60-65%；而頂尖機器人的勝率則接近 80%。我從未登上排行榜頂端，但在過程中學到了一些有趣的事情：猜拳是對抗性推理（adversarial reasoning）的一個近乎完美的縮影。你有兩個處於恆定緊張狀態的目標：預測並利用對手的招式，同時確保自己不被利用。本質上，每種策略都是對如何平衡這兩個目標的不同回答。

來源：https://commons.wikimedia.org/w/index.php?curid=27958688

簡單策略

永遠出石頭 (Always Rock)

最簡單的策略就是一直出石頭。這是 35% 的一般人類玩家，以及 50% 的男性玩家會選擇的開場招式。

石頭會輸給它的宿敵——布。如果你確信對手會出石頭，你就應該出布。因此，「永遠出石頭」是一種極易被其天敵反制的策略。

另一方面，如果你確信對手會出布，你就應該出剪刀。

這在我第一次了解猜拳統計數據時真的發生過。我看到了上面圖表的早期版本，向一位朋友挑戰，而他也看過同樣的圖表，他識破我是個「看圖表的人」，於是出了剪刀作為回應。哎呀。

當然，剪刀可以被原始策略（石頭）擊敗。

這是否意味著這種無限倒退（infinite regress）永無止境？並非如此。有一種簡單的策略，無論你的對手多麼擅長讀透你，基本上都無法被利用。

純隨機 (Pure Random)

對抗強大對手的最佳策略就是進行純隨機出拳。

隨機出拳（1/3 石頭、1/3 布、1/3 剪刀）在證明上是不可被利用的。無論你的對手多麼厲害，只要他們無法破解你的隨機來源（在電腦猜拳中這是一個可靠的假設），你的勝負機率預期應該是相等的。

側欄：執行方式（針對人類）

隨機性（或近乎完美的偽隨機性）對機器人來說很容易。對人類來說則難得多！

大多數人類無法僅憑直覺「隨機出拳」。相反，他們需要一些外部的隨機來源。就我個人而言，我使用圓周率（pi）的位數，我背了很多位（我知道，很宅）。然後我將圓周率的位數對 3 取模（modulo 3）來決定我的招式。例如：0 -> 石頭，1 -> 布，2 -> 剪刀。

如果你想比我更認真地對待猜拳，背誦一串更長（且不同）的隨機數字/招式序列對你可能更有利。

為什麼純隨機不是完美的？

為什麼純隨機不直接被視為最佳策略？畢竟，它完全無法被利用！這符合博弈論中「納許均衡」（Nash Equilibrium）的技術定義：如果每個玩家都採取純隨機策略，沒有人能透過改變策略來獲益。

純隨機是一種不可被利用的策略，對抗最強策略時有 50-50 的勝率。不幸的是，它對抗最爛的策略時也同樣只有 50-50 的勝率。

而有些人會寫出像「永遠出石頭」這種爛機器人！而你會想要利用這些策略。

考慮「純隨機 + 布反制」（Pure Random + Paper Counter），它包含兩個部分：

1. 預設進行隨機出拳。
2. 如果你確信對手「永遠出石頭」，就出布。否則，回到步驟 1。

這個策略絕對優於「永遠出石頭」和「純隨機」。當然，如果你能合理地預測對手，你可以做得比僅僅利用單一策略好得多。

字串搜尋器 (String Finder)，又稱 Aaronson 先知

你該如何預測其他人可能擁有的許多不同特異模式和策略？人類和機器人都經常重複某些模式，所以你只需要尋找模式並反制它們。

你如何找到這些模式？一個簡單的方法是在對手的出拳歷史中尋找過去的模式。例如，如果過去 5 次對手出 SS（剪刀、剪刀）時，有 4 次隨後會出 R（石頭），那麼你可以合理推測，如果她剛出了 SS，接下來很可能出 R（所以你應該出 P 作為反制）。

Scott Aaronson 製作了一個非常簡單的字串搜尋器，可以擊敗幾乎所有天真的人類策略。可以在此查看 Github，或在此親自與它對戰（使用 Collisteru 的版本）。

來源：https://www.cs.utexas.edu/people/faculty-researchers/scott-aaronson

側欄：單向字串搜尋器 vs 雙向字串搜尋器

對於你的字串搜尋器，你可以選擇只記錄（並使用）對手過去的出拳歷史，或者記錄成對的招式（包括對手的招式和你自己的招式）。

這兩種策略各有千秋。僅針對對手的招式進行記錄和模式匹配較為簡單，且減少了組合空間。相比之下，記錄成對招式在理論上更完整，且更能代表遊戲的全貌（你的對手也在試圖預測你！）。

在實踐中，大多數中階和高階機器人會同時使用單向和雙向字串搜尋器。

為什麼字串搜尋器不是完美的？

字串搜尋器極易被利用。如果你的對手知道你正在使用字串搜尋策略，他們只需要反轉他們的歷史記錄。當他們在某種情況下歷史上出 R 時，他們會預期你出 P，進而改出 S。

預測你字串搜尋策略的人可以輕易地擊潰你。

是否可能在對抗更聰明的策略時，在極限情況下基本上不可被利用，同時又能利用對手策略中的偏差？令人驚訝的是，答案是肯定的。

「Henny」策略：頻率加權隨機

Henny 策略很簡單：

1. 前幾手以隨機出拳或其他策略開始。
2. 記錄對手過去所有的招式。
3. 然後，從對手的整個歷史記錄中隨機抽取一個招式並進行反制。

如果對手在過去 100 手中出了 30 次石頭、45 次布和 25 次剪刀，你就從該分佈中抽樣並反制：你會在 30% 的時間出布，45% 的時間出剪刀，25% 的時間出石頭作為回應。

只要你的對手在出拳中有任何偏差（例如，出布的次數略多於剪刀），你就能在多次對戰中穩定勝過他們。

此外，Henny 不容易被利用。首先，由於其高度的隨機性，對手很難識別你在做什麼。其次，在對抗無偏差對手的極限情況下，這種策略會趨近於純隨機，即納許均衡。

Henny 策略在極限情況下基本上不可被利用，同時也能穩定地利用許多弱小的對手。

Henny 的主要限制

Henny 策略終究是一種高度防禦性的策略。它很難被更複雜的策略利用，但相應地，它利用其他策略的能力也有限。

首先，當它對抗較弱的策略時，通常只能取得微小的優勢，而無法完全利用對方的弱點。這對於機器人競賽來說不是問題，因為你是在（例如）1000 場獨立對局中贏得比賽，比賽結束時的具體得分並不重要。然而，在現實生活中人類的三戰兩勝或七戰四勝制中，這可能會成為問題，因為你微小的統計優勢可能太小，無法穩定保證勝利。

更大的問題是，它只能利用一小部分可預測的策略。考慮一個只會無限循環出 {RPSRPS...} 的人。這在理論和實踐上都是極其容易被利用的（早先提到的字串搜尋器可以徹底摧毀它），但從天真的 Henny 策略角度來看，這與隨機出拳無異！

因此，天真的 Henny 策略雖然在難以預測和難以被利用方面表現出色，但因為無法利用任何非「招式頻率偏差」的策略，而錯失了許多獲勝機會。

我們能做得更好嗎？

顯而易見的做法是融合上述方法。你可以對招式序列（而非單一招式）進行頻率加權，或者根據比賽進展在不同策略之間切換。但這引出了一個新問題：如何選擇使用哪種策略，以及何時使用？

這就是「元策略」（Meta-Strategy）發揮作用的地方。

元策略：Iocaine Powder

「兩邊都有毒。」——蒙面俠

電腦猜拳界最著名的元策略是 Iocaine Powder（以此命名自《公主新娘》中經典的智力對決場景）。其核心見解是，任何對對手策略的成功預測（P）都可以在多個「元層級」（meta-levels）上運行。

例如，假設你的預測器（Predictor）說對手將出石頭：

• 層級 0 (P0)：預測對手會出什麼，然後反制它。出布。
• 層級 2 (P1)：反制對手的第二次猜測。假設對手預期你使用層級 0 策略。他們會出剪刀來反制你的布。所以你應該出石頭來反制。
• 層級 4 (P2)：反制對手的第四次猜測。你的對手預期你出石頭，於是出布。所以你應該出剪刀來反制。

...

此時，你可能會預期會出現無限倒退。並非如此！猜拳的循環特性意味著層級 6 (P3) 建議你出布，就像層級 0 一樣。因此，同一個預測器的所有元層級（旋轉）最終會簡化為 3 種策略。

但如果你的對手也對你使用預測器 P，並試圖預測你的策略呢？我們從同一個預測器中又得到了 3 種策略：

• 層級 -1 (S0)：直接執行你的策略。希望對手沒看穿。
• 層級 1 (S1)：假設對手成功預測/反制了你的基礎策略。比他們高出 1 個層級（比你的基礎策略高出 2 個層級）。

L...