帖子
勛章
關(guān)注
任務(wù)
Wolfram：25個最好的猜單詞游戲  一個六歲孩子關(guān)于猜單詞的簡單問題變成了另一種分析的癡迷，使我最近玩了1500萬場猜單詞游戲。 早在 2007 年，我在從牛津到倫敦的火車上為一個人類猜測者寫了一個猜單詞游戲。我在倫敦地鐵上花時間思考玩這個游戲的最佳策略，并在回程時為做猜詞的計算機寫了這個版本。它成功地猜出了我的測試詞，我很滿意，所以我把這兩個版本提交給了 Wolfram 演示項目。三年后的今天，我的女兒已經(jīng)長大了，可以玩了，但演示讓她很惱火，因為它總是能猜到她的詞。她問了一個顯而易見的問題，當時我從來沒有想過。"我能選擇最難的詞是什么，這樣我就可以打敗它？"  如果您不知道，猜單詞的想法是，一個玩家想到一個詞，并告訴另一個玩家它有多少個字母。第二位玩家反復(fù)猜測字母。如果猜中的字母在單詞中，選詞者必須說出該字母在單詞中每一次出現(xiàn)的位置。如果不能，那么選詞者就會很高興地畫出一個絞架的組件，上面掛著一個人。如果在單詞被完全猜中之前，絞架和人就已經(jīng)完成了，那么第二個玩家就輸了。絞架和人的設(shè)計有很多種；我在上面這個有 13 個元素的絞架上學過，但我見過 10 到 13 之間的很多可能性，可能還有其他的。我把這些稱為10局和13局。我的設(shè)計，即13局，對猜測者來說比較容易，因為他或她在輸之前可以犯更多的錯誤。 為什么是劊子手？我不知道。據(jù)稱，這個游戲可以追溯到維多利亞時代的英國，當時絞刑可能是對拼寫不良的一種可接受的懲罰! 以下是我是如何創(chuàng)建這些游戲的。首先，讓我描述一下我們正在攻擊的算法。我的猜單詞算法使用所有可用的信息來產(chǎn)生一個候選詞的列表。起初，可用的信息只是單詞的長度，但后來我們會知道一些字母和它們的位置，還有一些不在單詞中的字母。所有這三點信息都可以很快地減少字典。接下來，游戲會對所有候選詞中的字母進行頻率分析（有多少候選詞中至少包含一個 "a"，至少包含一個 "b"，以此類推）。我們避免猜錯的最好機會（如果我們假設(shè)這個詞是從字典中隨機選擇的）是選擇一個經(jīng)常出現(xiàn)的字母。 在這一點上，值得介紹一下博弈論中的納什均衡（Nash equilibrium）。這是指當發(fā)現(xiàn)對立的策略時，即使對手的策略是已知的，任何一方都不能單方面改善他或她的結(jié)果。部分考慮到這一點，該算法并不選擇最受歡迎的字母，而是根據(jù)頻率加權(quán)選擇任何一個可能的字母（例如，如果 1000 個候選詞包含 "e"，13個包含 "x"，那么 "e "將以 1000：13 的比例被選中，而不是 "x"）。這是走向納什均衡點的第一次迭代；沒有它，我們的算法就完全是決定性的，因此，任何擊敗它的詞都會每次都擊敗它。對手會通過每次都選擇那個詞來優(yōu)化他或她的策略。該算法還使游戲更加有趣。我女兒的問題可以被認為是朝著納什均衡的下一次迭代。知道了猜測者的算法，我們被要求優(yōu)化如何從字典中選擇單詞的權(quán)重，而不是我所假設(shè)的同等權(quán)重。 (說點題外話：幾年前在倫敦舉行的第五屆國際數(shù)學研討會上，我有幸聆聽了 John Nash- 納什均衡的發(fā)明者，諾貝爾獎獲得者，以及電影《美麗心靈》的主角，講述了他對 Mathematica 的使用。每年的諾貝爾獎名單中通常至少有一位 Mathematica 用戶，盡管遺憾的是，諾貝爾獎得主很少出現(xiàn)在好萊塢電影中)。 從概念上講，回答我女兒的問題最簡單的方法是對每一個可能的詞進行粗暴的蒙特卡洛分析。我所做的第一件事是重構(gòu)演示中的代碼，使其更快。在我的演示中，篩選 90,000 個單詞的字典并進行頻率分析大約需要 0.2 秒--在互動游戲中是瞬時的。但是模擬整個游戲可能需要多達 26 個這樣的選擇，由于我想模擬 1500 萬個游戲，我花了幾分鐘時間使用 Wolfram Workbench 中的 Profiler 來了解時間的去向，結(jié)果得到了一個快 10 倍的版本。如果要重復(fù)或改進我的分析,此實施位于帖子的底部。 然后我用 gridMathematica 并行運行了它。如果我能夠使用 Wolfram-Alpha 的硬件，我將在幾分鐘內(nèi)完成，但我只有幾臺閑置的辦公電腦，所以我讓它在周末運行。 我為字典中的每個詞做了 50 個游戲的初始運行。足夠收斂到真實結(jié)果的10% 以內(nèi)，也足夠做一個粗略的排序。然后我對更有希望的詞進行了進一步的試驗，在 1000 個最佳詞的名單上共進行了 3000 場游戲。這足以讓我對它們的排序有相當?shù)陌盐铡?span style="display:none"> ixT:)|'i 為了使其他人不必消耗 CPU 周期，我在這里包括了 50MB 的生成數(shù)據(jù)。 現(xiàn)在我們有了這些數(shù)據(jù)，我們就可以開始分析了：  以下是我對 "困難 "一詞得到的結(jié)果：  數(shù)據(jù)顯示了 50 場比賽中每場的猜錯次數(shù)。我們可以看到，"difficult"這個詞并不難，平均需要 3.3 次錯誤的猜測--這還不足以讓我的設(shè)計中開始畫人。在50場比賽中，該算法從未在10場比賽中失敗過，甚至在 13 場比賽中接近失敗。盡管如果它下的是 8 局棋，它就會輸一次。  |
