免費猜字小游戲Wordle正在席卷全球，火到以數(shù)百萬美元的價格被收購，全球玩家數(shù)量也突破了200萬。

如果你在微博、微信等地方看到這些神神秘秘的方塊，那就是Wordle玩家在分享自己當日的戰(zhàn)績了。

根據(jù)統(tǒng)計，大多數(shù)人類玩家需要猜測4次或以上才能取得勝利。

比如，2月5日的題目在當天30多萬份曬出戰(zhàn)績的玩家中，只有27%能在三次以內(nèi)猜中。

這個游戲自然也成了程序員們的新競技場，他們寫出各種算法來比拼誰用的步數(shù)最少。

這其中，百萬粉數(shù)學科普大神3Blue1Brown的玩法更為硬核——

他不光寫出了求解算法，還用數(shù)學知識一步步優(yōu)化至逼近理論極限，最終成績平均3.138次猜測就能獲勝。

并且他用統(tǒng)計辦法找出了與人類常見策略不同的最佳開局單詞crane。

他像往常一樣把這個過程整理成視頻分享出來，不僅展示了算法，還把其中涉及的信息論、統(tǒng)計學知識講得明明白白。

視頻發(fā)布一天之內(nèi)就有上百萬播放，圍觀的網(wǎng)友也紛紛在評論區(qū)表達了贊嘆。

為了游戲點進來，為了精彩的信息論知識留下，太酷了！

他用了什么樣的算法，理論極限又是怎么算出來的？下面一起來看看。

從每一次猜測中獲得最多信息

Wordle的游戲規(guī)則很簡單，玩家需要猜出程序每天指定的一個5位英語單詞謎底。

玩家可以隨意提交一個英語單詞，但必須是字典里有的，不能胡亂拼寫。

如果字母在謎底中出現(xiàn)且位置對了就顯示綠色，字母出現(xiàn)了但位置不對就顯示黃色，字母在答案的單詞中沒出現(xiàn)就顯示灰色。

根據(jù)反饋信息再進行下一輪猜測，在6次嘗試之內(nèi)猜出就算贏。

如何讓步數(shù)盡量少？

3Blue1Brown的總體思路是盡量從每一次猜測中獲得最多的信息。

他先是找來了26個字母在英語文本中出現(xiàn)頻率的統(tǒng)計數(shù)據(jù)，嘗試在前兩次嘗試中覆蓋最多高頻字母。

比如other+nails的組合，就可以覆蓋出現(xiàn)頻率最高的11個字母中的10個，如果運氣好就能確定下來一些字母。

即使這些字母都沒出現(xiàn)依然是一種信息量很大的反饋，10個常用字母都沒出現(xiàn)的單詞數(shù)量就大大減少了，讓下一步猜測更簡單。

不過在嘗試過程中，又出現(xiàn)了新的問題。

同樣用nails這幾個字母，也可以拼成snail，這兩種拼寫順序之間的差異，僅依據(jù)字母頻率數(shù)據(jù)是無法衡量的。

下面需要一種新的計算方法。

如何計算信息量？

原版Wordle游戲里有一個數(shù)量12972的總單詞列表，都能作為猜測詞使用。

另外有一個2315個單詞的列表，只有這些單詞會出現(xiàn)在答案里(據(jù)說是游戲作者的女朋友挑選的)。

因為游戲是用Javascript寫的，數(shù)據(jù)都在客戶端，這些數(shù)據(jù)直接可以從源碼里找到。

不過3Blue1Brown覺得讓程序利用答案列表的話有點像作弊了，他果斷給自己加大難度，只考慮總單詞列表。

游戲中，每一次猜測都能從12972個單詞中排除一些結(jié)果。

比如猜測weary，如果W位置正確同時A出現(xiàn)了，那么剩下的可選單詞只剩58個。

這樣對同一個猜測，從5個字母全沒出現(xiàn)到5個字母全對的各種反饋的概率都可以計算出來。

這樣，問題就變成了如何評估各種反饋情況包含的信息量。

3Blue1Brown選擇的辦法，就是利用信息論祖師爺香農(nóng)提出的信息熵概念。

信息熵描述的是事件的不確定性，單位就是大家知道的比特。

理解起來也不難，可以用扔硬幣來解釋。

扔1枚硬幣只會出現(xiàn)正、反兩種結(jié)果，而且概率相等。

扔2枚硬幣就有正正、正反、反正、反反這4種結(jié)果，扔3枚有8種情況等等，也就是扔n次有2的n次方種結(jié)果。

當一個事件有兩種結(jié)果且概率都是1/2，其不確定性相當于扔1枚硬幣，此時信息熵定義為1比特。

如果一個事件有8種結(jié)果且概率都是1/8，就相當于扔3枚硬幣，此時信息熵就是3比特。

信息量和信息熵的數(shù)量相等、意義相反，相當于衡量一則信息能消除多少不確定性。

設(shè)每種結(jié)果的概率為p，信息量為I，有如下等式。

稍作變換，可以得到信息量的計算公式。

回到Wordle游戲上，一次猜測獲得的信息量可以用每種可能情況的概率與對應(yīng)信息量相乘、再把結(jié)果相加來計算，也就是求數(shù)學期望。

以猜測weary為例，計算出獲得的信息量為4.9比特。

代表這則信息消除的不確定性比扔5個硬幣的不確定性少一點。

算法思路有了，接下來就可以交給程序，計算出所有12972個單詞的能消除的信息熵。

用同樣的方法，可以再計算第二步、第三步猜測能消除的信息熵。

根據(jù)這些計算結(jié)果，程序就可以在每一次猜測時，選擇所有可能單詞里能消除信息熵最多的那個。

比如第一次猜slate獲得一次反饋，此時還剩下578個單詞可選，其中選ramin能消除最多的信息熵，這樣一步一步猜直到猜出正確答案。

接下來，拿這個程序在所有2135種可能的答案上跑一遍，平均用了4.124步猜出正確答案。

3Blue1Brown覺得這個成績還不夠好，至少沒有超過普通人類玩家水平，還需要繼續(xù)優(yōu)化。

最終成績逼近理論極限

成績不夠好的一個問題出在每個單詞作為答案的可能性其實并不相同。

像aahed aalii aargh這種偏門單詞雖然在允許猜測的總單詞列表里，但并不在答案列表的2315個單詞里。

找一個典型的例子，當遇到abbas（人名，阿巴斯）和abyss（深淵）二選一時，如果程序能知道abyss是常用詞，就可以省下一步。

下一步改進方向就是引入詞頻統(tǒng)計數(shù)據(jù)，這樣的數(shù)據(jù)集可以從Wolfram上找到。

這里還遇到一個問題，比如which和braid的出現(xiàn)頻率相差1000倍，但都可以算是常見單詞，出現(xiàn)在答案列表里的可能性相差不大。

解決辦法就是用Sigmoid函數(shù)做處理，讓更多數(shù)據(jù)靠近0或1。

將處理后的詞頻數(shù)據(jù)與前面的信息量計算結(jié)果相結(jié)合，得到優(yōu)化后的信息量計算方法。

在實際游戲中，也把信息量與詞頻結(jié)合考慮，就能讓程序更傾向于選擇常見單詞。

比如在下面的情況中，words和dorms的信息量并不是最高的，但因為詞頻較高所以優(yōu)先考慮。

優(yōu)化后的成績到了3.601，平均節(jié)省了半步。

如果加大計算量，每次根據(jù)兩步搜索的結(jié)果選擇單詞可以進一步提高成績。

而且根據(jù)兩步搜索的計算結(jié)果，3Blue1Brown認為能獲得最大信息量的開局單詞是crane。

此外還可以讓程序知道具體哪2315個單詞真的是在答案列表里的，用上所有這些技巧后，成績再次提升到3.438。

實際上這個成績的理論極限就不可能低于3。

2315種答案意味著有11.17比特的不確定性，而暴力搜索后，前兩步能獲得的最大信息量在10.01比特，還剩下1.16。

也就是說第三步的難度比二選一還要難一點，沒有算法能保證每次都正確。

不過3Blue1Brown還是找到了新辦法進一步提升成績。

讓程序記住每個正確答案，并在下一局中把猜過的單詞排除出去，最終成績到達3.138，逼近了理論極限。

看完整個視頻后，有網(wǎng)友表示學到的信息論知識比上課學到的還多。

也有很多人對到底哪個單詞才是最佳開局展開了討論。

雖然兩步搜索的結(jié)果是crane，不過3Blue1Brown也不確定對于人類玩家來說是不是最佳開局單詞。

畢竟實際游戲中人類很難像程序一樣算出第二步的情況。

對于人類來說，soare和tares都是很好的開局。

還能挑戰(zhàn)變態(tài)模式

程序?qū)懞煤螅?Blue1Brown還做了更多嘗試，比如原版Wordle的困難難度，成績是3.562，

還有一個Wordle變態(tài)版Absurdle，這個版本不再限制嘗試次數(shù)，但變態(tài)之處在于游戲AI會與玩家對抗。

玩家猜測一次后正確答案就會變化，在所有反饋可能性中挑選信息熵最大的那個，就像是在躲避玩家的猜測。

Absurdle的作者之前還開發(fā)過一個變態(tài)版俄羅斯方塊，每次都給你最不需要的方塊。

對于這個變態(tài)版Wordle，結(jié)果3Blue1Brown的程序也挑戰(zhàn)成功。

如果你看到這里也想挑戰(zhàn)這個變態(tài)版試試，可以點下方鏈接。

原版游戲地址：

變態(tài)版游戲地址：

總結(jié)

以上是生活随笔為你收集整理的数学大神攻克猜字游戏Wordle：求解算法成绩逼近理论极限 连信息论都用上了的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。