一個六歲孩子關于猜單詞的簡單問題變成了另一種分析的癡迷，使我最近玩了1500萬場猜單詞游戲。

早在 2007 年，我在從牛津到倫敦的火車上為一個人類猜測者寫了一個猜單詞游戲。我在倫敦地鐵上花時間思考玩這個游戲的最佳策略，并在回程時為做猜詞的計算機寫了這個版本。它成功地猜出了我的測試詞，我很滿意，所以我把這兩個版本提交給了 Wolfram 演示項目。三年后的今天，我的女兒已經長大了，可以玩了，但演示讓她很惱火，因為它總是能猜到她的詞。她問了一個顯而易見的問題，當時我從來沒有想過。"我能選擇最難的詞是什么，這樣我就可以打敗它？"

如果您不知道，猜單詞的想法是，一個玩家想到一個詞，并告訴另一個玩家它有多少個字母。第二位玩家反復猜測字母。如果猜中的字母在單詞中，選詞者必須說出該字母在單詞中每一次出現的位置。如果不能，那么選詞者就會很高興地畫出一個絞架的組件，上面掛著一個人。如果在單詞被完全猜中之前，絞架和人就已經完成了，那么第二個玩家就輸了。絞架和人的設計有很多種；我在上面這個有 13 個元素的絞架上學過，但我見過 10 到 13 之間的很多可能性，可能還有其他的。我把這些稱為10局和13局。我的設計，即13局，對猜測者來說比較容易，因為他或她在輸之前可以犯更多的錯誤。

為什么是劊子手？我不知道。據稱，這個游戲可以追溯到維多利亞時代的英國，當時絞刑可能是對拼寫不良的一種可接受的懲罰!

以下是我是如何創建這些游戲的。首先，讓我描述一下我們正在攻擊的算法。我的猜單詞算法使用所有可用的信息來產生一個候選詞的列表。起初，可用的信息只是單詞的長度，但后來我們會知道一些字母和它們的位置，還有一些不在單詞中的字母。所有這三點信息都可以很快地減少字典。接下來，游戲會對所有候選詞中的字母進行頻率分析（有多少候選詞中至少包含一個 "a"，至少包含一個 "b"，以此類推）。我們避免猜錯的最好機會（如果我們假設這個詞是從字典中隨機選擇的）是選擇一個經常出現的字母。

在這一點上，值得介紹一下博弈論中的納什均衡（Nash equilibrium）。這是指當發現對立的策略時，即使對手的策略是已知的，任何一方都不能單方面改善他或她的結果。部分考慮到這一點，該算法并不選擇最受歡迎的字母，而是根據頻率加權選擇任何一個可能的字母（例如，如果 1000 個候選詞包含 "e"，13個包含 "x"，那么 "e "將以 1000：13 的比例被選中，而不是 "x"）。這是走向納什均衡點的第一次迭代；沒有它，我們的算法就完全是決定性的，因此，任何擊敗它的詞都會每次都擊敗它。對手會通過每次都選擇那個詞來優化他或她的策略。該算法還使游戲更加有趣。我女兒的問題可以被認為是朝著納什均衡的下一次迭代。知道了猜測者的算法，我們被要求優化如何從字典中選擇單詞的權重，而不是我所假設的同等權重。

(說點題外話：幾年前在倫敦舉行的第五屆國際數學研討會上，我有幸聆聽了 John Nash- 納什均衡的發明者，諾貝爾獎獲得者，以及電影《美麗心靈》的主角，講述了他對 Mathematica 的使用。每年的諾貝爾獎名單中通常至少有一位 Mathematica 用戶，盡管遺憾的是，諾貝爾獎得主很少出現在好萊塢電影中)。

從概念上講，回答我女兒的問題最簡單的方法是對每一個可能的詞進行粗暴的蒙特卡洛分析。我所做的第一件事是重構演示中的代碼，使其更快。在我的演示中，篩選 90,000 個單詞的字典并進行頻率分析大約需要 0.2 秒--在互動游戲中是瞬時的。但是模擬整個游戲可能需要多達 26 個這樣的選擇，由于我想模擬 1500 萬個游戲，我花了幾分鐘時間使用 Wolfram Workbench 中的 Profiler 來了解時間的去向，結果得到了一個快 10 倍的版本。如果要重復或改進我的分析,此實施位于帖子的底部。

然后我用 gridMathematica 并行運行了它。如果我能夠使用 Wolfram-Alpha 的硬件，我將在幾分鐘內完成，但我只有幾臺閑置的辦公電腦，所以我讓它在周末運行。

我為字典中的每個詞做了 50 個游戲的初始運行。足夠收斂到真實結果的10% 以內，也足夠做一個粗略的排序。然后我對更有希望的詞進行了進一步的試驗，在 1000 個最佳詞的名單上共進行了 3000 場游戲。這足以讓我對它們的排序有相當的把握。

為了使其他人不必消耗 CPU 周期，我在這里包括了 50MB 的生成數據。

現在我們有了這些數據，我們就可以開始分析了：

以下是我對 "困難 "一詞得到的結果：

數據顯示了 50 場比賽中每場的猜錯次數。我們可以看到，"difficult"這個詞并不難，平均需要 3.3 次錯誤的猜測--這還不足以讓我的設計中開始畫人。在50場比賽中，該算法從未在10場比賽中失敗過，甚至在 13 場比賽中接近失敗。盡管如果它下的是 8 局棋，它就會輸一次。

讓我們來看看算法在從字典中隨機選擇的一個詞上的整體表現（最初的假設）。我們不能看平均失誤率，因為一個猜錯13個的游戲和一個猜錯 20 個 的游戲同樣是一個失敗者。我們關心的是勝率，而這些勝率取決于游戲的大小。

事實證明，對于 13 場比賽來說，我們只有 1% 的時間會擊敗隨機選擇的單詞的算法。我明白為什么我的女兒會感到沮喪了。

10 局比賽上升到 5%：

如果算法根本沒有使用頻率分析，那么13局的勝率將是 10%，10 局的勝率將是 25%（在實驗的第一次運行中，一個粗心的編碼錯誤告訴了我）。

下面是游戲結果的分布。有一半的時間它的猜測是 4 個或更少的錯誤。

長單詞和短單詞哪個更好？當我和女兒玩的時候，我用的是短詞，因為我以為短詞更容易（對她來說當然更容易拼寫），但我驚訝地發現，短詞的平均錯誤率最高。原因似乎很簡單，字母的變化越大，人就越不可能錯過它們。在極端情況下，一個有 14 個不同字母的單詞不可能在13局中獲勝。只有 12個錯誤的字母。

因此，如果我們只記住一條規則，那就是使用 3 個字母的詞。而絞架 (gallows) 的設計作品越多，情況就越是如此。

但我們感興趣的是非常好的詞，所以這里是每個詞長中最好的詞的得分：

通過仔細的選擇，每個詞的長度中最好的詞都是比較平均的。

而且有趣的是，如果我們按勝率對這些詞進行分類，最好的詞比排名靠后幾位的詞有明顯的優勢。這里的每一行都是不同的游戲大小，從 9 到 13。排名靠后的單詞的粗糙度是由于模擬數據不足，而不是算法中的真實現象。

好了，關于趨勢就不多說了，下面是最好的詞：

如您所料，像 "x "和 "z "這樣的低頻字母是一個很大的因素，但字母重復也是有用的，因為它們使較長的單詞具有與較短的單詞相似的不同字母數量。

因此，我們有了它。在所有游戲規模中，"jazz"贏得最多。盡管我們可以看到游戲大小的奇特差異。隨著游戲大小的增加，"Jazzed "的表現逐漸變差，但 "faffed "的表現逐漸變好。了解這一點是另一個項目!

我們現在可以改進我們的選詞算法。我們不應該隨機選擇一個詞，而應該將我們的選擇權重放在具有高勝率的詞上。

當然，這只是朝著納什均衡點又走了一步。如果猜測者更新算法以考慮到該策略，我們將不得不重復這整個實驗，以獲得一個更好的策略。最終，這兩種算法很可能會收斂在一個點上，即每個詞都有相同的勝率，而我們將知道最佳的游戲結果。

我懷疑這 13 局游戲基本上是可以解決的。有足夠多的詞是很容易猜到的，在這些詞上冒更大的風險，去測試更難的詞，會使猜測算法從 99% 的成功率提高到 100%。在這一點上，我們處于平衡狀態--用 WOPR 的話說，"一個奇怪的游戲。唯一的勝利之舉就是不玩。《戰爭游戲》的提法特別相關，因為納什均衡被用作冷戰時期相互確保破壞的核戰略的理論基礎，而影片的高潮基本上是這種模擬--增加了計算機的自我意識）。

對于 10 局，我只學到了足夠的知識，看到最終的算法可能相當復雜，而且在這個簡單的游戲中，有比我預期更豐富的內容。

如果您更想獲得樂趣，那就從長詞中挑選最好的。這里有一個表格，列出了10局中每個長度的最佳單詞。它們的表現不如 3-5 個字母的單詞好，但在娛樂方面，您無法擊敗 "powwowing"、"bowwowing "和 "huzzahing"!

這都是基于 Mathematica 內置的 90,000 詞英語詞典。對于更大的字典或其他語言，結果可能會有很大不同。