一個(gè)六歲孩子關(guān)于猜單詞的簡單問題變成了另一種分析的癡迷，使我最近玩了1500萬場(chǎng)猜單詞游戲。

早在 2007 年，我在從牛津到倫敦的火車上為一個(gè)人類猜測(cè)者寫了一個(gè)猜單詞游戲。我在倫敦地鐵上花時(shí)間思考玩這個(gè)游戲的最佳策略，并在回程時(shí)為做猜詞的計(jì)算機(jī)寫了這個(gè)版本。它成功地猜出了我的測(cè)試詞，我很滿意，所以我把這兩個(gè)版本提交給了 Wolfram 演示項(xiàng)目。三年后的今天，我的女兒已經(jīng)長大了，可以玩了，但演示讓她很惱火，因?yàn)樗偸悄懿碌剿脑~。她問了一個(gè)顯而易見的問題，當(dāng)時(shí)我從來沒有想過。"我能選擇最難的詞是什么，這樣我就可以打敗它？"

如果您不知道，猜單詞的想法是，一個(gè)玩家想到一個(gè)詞，并告訴另一個(gè)玩家它有多少個(gè)字母。第二位玩家反復(fù)猜測(cè)字母。如果猜中的字母在單詞中，選詞者必須說出該字母在單詞中每一次出現(xiàn)的位置。如果不能，那么選詞者就會(huì)很高興地畫出一個(gè)絞架的組件，上面掛著一個(gè)人。如果在單詞被完全猜中之前，絞架和人就已經(jīng)完成了，那么第二個(gè)玩家就輸了。絞架和人的設(shè)計(jì)有很多種；我在上面這個(gè)有 13 個(gè)元素的絞架上學(xué)過，但我見過 10 到 13 之間的很多可能性，可能還有其他的。我把這些稱為10局和13局。我的設(shè)計(jì)，即13局，對(duì)猜測(cè)者來說比較容易，因?yàn)樗蛩谳斨翱梢苑父嗟腻e(cuò)誤。

為什么是劊子手？我不知道。據(jù)稱，這個(gè)游戲可以追溯到維多利亞時(shí)代的英國，當(dāng)時(shí)絞刑可能是對(duì)拼寫不良的一種可接受的懲罰!

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

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

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

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

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

我為字典中的每個(gè)詞做了 50 個(gè)游戲的初始運(yùn)行。足夠收斂到真實(shí)結(jié)果的10% 以內(nèi)，也足夠做一個(gè)粗略的排序。然后我對(duì)更有希望的詞進(jìn)行了進(jìn)一步的試驗(yàn)，在 1000 個(gè)最佳詞的名單上共進(jìn)行了 3000 場(chǎng)游戲。這足以讓我對(duì)它們的排序有相當(dāng)?shù)陌盐铡?/p>

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

現(xiàn)在我們有了這些數(shù)據(jù)，我們就可以開始分析了：

以下是我對(duì) "困難 "一詞得到的結(jié)果：

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

讓我們來看看算法在從字典中隨機(jī)選擇的一個(gè)詞上的整體表現(xiàn)（最初的假設(shè)）。我們不能看平均失誤率，因?yàn)橐粋€(gè)猜錯(cuò)13個(gè)的游戲和一個(gè)猜錯(cuò) 20 個(gè) 的游戲同樣是一個(gè)失敗者。我們關(guān)心的是勝率，而這些勝率取決于游戲的大小。

例如，如果我們?cè)?13 場(chǎng)比賽中選擇 "貓"，那么我們將有 23% 的時(shí)間擊敗算法。

在 10 場(chǎng)比賽中，我們有 50% 的時(shí)間會(huì)擊敗它。

事實(shí)證明，對(duì)于 13 場(chǎng)比賽來說，我們只有 1% 的時(shí)間會(huì)擊敗隨機(jī)選擇的單詞的算法。我明白為什么我的女兒會(huì)感到沮喪了。

10 局比賽上升到 5%：

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

下面是游戲結(jié)果的分布。有一半的時(shí)間它的猜測(cè)是 4 個(gè)或更少的錯(cuò)誤。

長單詞和短單詞哪個(gè)更好？當(dāng)我和女兒玩的時(shí)候，我用的是短詞，因?yàn)槲乙詾槎淘~更容易（對(duì)她來說當(dāng)然更容易拼寫），但我驚訝地發(fā)現(xiàn)，短詞的平均錯(cuò)誤率最高。原因似乎很簡單，字母的變化越大，人就越不可能錯(cuò)過它們。在極端情況下，一個(gè)有 14 個(gè)不同字母的單詞不可能在13局中獲勝。只有 12個(gè)錯(cuò)誤的字母。

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

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

通過仔細(xì)的選擇，每個(gè)詞的長度中最好的詞都是比較平均的。

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

好了，關(guān)于趨勢(shì)就不多說了，下面是最好的詞：

如您所料，像 "x "和 "z "這樣的低頻字母是一個(gè)很大的因素，但字母重復(fù)也是有用的，因?yàn)樗鼈兪馆^長的單詞具有與較短的單詞相似的不同字母數(shù)量。

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

我們現(xiàn)在可以改進(jìn)我們的選詞算法。我們不應(yīng)該隨機(jī)選擇一個(gè)詞，而應(yīng)該將我們的選擇權(quán)重放在具有高勝率的詞上。

當(dāng)然，這只是朝著納什均衡點(diǎn)又走了一步。如果猜測(cè)者更新算法以考慮到該策略，我們將不得不重復(fù)這整個(gè)實(shí)驗(yàn)，以獲得一個(gè)更好的策略。最終，這兩種算法很可能會(huì)收斂在一個(gè)點(diǎn)上，即每個(gè)詞都有相同的勝率，而我們將知道最佳的游戲結(jié)果。

我懷疑這 13 局游戲基本上是可以解決的。有足夠多的詞是很容易猜到的，在這些詞上冒更大的風(fēng)險(xiǎn)，去測(cè)試更難的詞，會(huì)使猜測(cè)算法從 99% 的成功率提高到 100%。在這一點(diǎn)上，我們處于平衡狀態(tài)--用 WOPR 的話說，"一個(gè)奇怪的游戲。唯一的勝利之舉就是不玩?！稇?zhàn)爭(zhēng)游戲》的提法特別相關(guān)，因?yàn)榧{什均衡被用作冷戰(zhàn)時(shí)期相互確保破壞的核戰(zhàn)略的理論基礎(chǔ)，而影片的高潮基本上是這種模擬--增加了計(jì)算機(jī)的自我意識(shí)）。

對(duì)于 10 局，我只學(xué)到了足夠的知識(shí)，看到最終的算法可能相當(dāng)復(fù)雜，而且在這個(gè)簡單的游戲中，有比我預(yù)期更豐富的內(nèi)容。

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

這都是基于 Mathematica 內(nèi)置的 90,000 詞英語詞典。對(duì)于更大的字典或其他語言，結(jié)果可能會(huì)有很大不同。

購買軟件/免費(fèi)試用

【13.2.1中英文 Wolfram 軟件】請(qǐng)點(diǎn)擊"評(píng)論區(qū)留言或私信申請(qǐng)