數(shù)學(xué)大神攻克猜字游戲Wordle，求解算法成績(jī)逼近理論極限，連信息論都用上了

夢(mèng)晨 發(fā)自 凹非寺
量子位 | 公眾號(hào) QbitAI

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

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

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

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

這個(gè)游戲自然也成了程序員們的新競(jìng)技場(chǎng)，他們寫(xiě)出各種算法來(lái)比拼誰(shuí)用的步數(shù)最少。

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

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

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

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

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

為了游戲點(diǎn)進(jìn)來(lái)，為了精彩的信息論知識(shí)留下，太酷了！

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

從每一次猜測(cè)中獲得最多信息

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

玩家可以隨意提交一個(gè)英語(yǔ)單詞，但必須是字典里有的，不能胡亂拼寫(xiě)。

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

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

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

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

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

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

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

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

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

下面需要一種新的計(jì)算方法。

如何計(jì)算信息量？

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

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

因?yàn)橛螒蚴怯肑avascript寫(xiě)的，數(shù)據(jù)都在客戶端，這些數(shù)據(jù)直接可以從源碼里找到。

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

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

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

這樣對(duì)同一個(gè)猜測(cè)，從5個(gè)字母全沒(méi)出現(xiàn)到5個(gè)字母全對(duì)的各種反饋的概率都可以計(jì)算出來(lái)。

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

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

理解起來(lái)也不難，可以用扔硬幣來(lái)解釋。

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

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

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

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

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

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

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

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

以猜測(cè)weary為例，計(jì)算出獲得的信息量為4.9比特。

代表這則信息消除的不確定性比扔5個(gè)硬幣的不確定性少一點(diǎn)。

算法思路有了，接下來(lái)就可以交給程序，計(jì)算出所有12972個(gè)單詞的能消除的信息熵。

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

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

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

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

3Blue1Brown覺(jué)得這個(gè)成績(jī)還不夠好，至少?zèng)]有超過(guò)普通人類玩家水平，還需要繼續(xù)優(yōu)化。

最終成績(jī)逼近理論極限

成績(jī)不夠好的一個(gè)問(wèn)題出在每個(gè)單詞作為答案的可能性其實(shí)并不相同。

像aahed aalii aargh這種偏門(mén)單詞雖然在允許猜測(cè)的總單詞列表里，但并不在答案列表的2315個(gè)單詞里。

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

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

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

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

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

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

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

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

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

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

此外還可以讓程序知道具體哪2315個(gè)單詞真的是在答案列表里的，用上所有這些技巧后，成績(jī)?cè)俅翁嵘?strong>3.438。

實(shí)際上這個(gè)成績(jī)的理論極限就不可能低于3。

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

也就是說(shuō)第三步的難度比二選一還要難一點(diǎn)，沒(méi)有算法能保證每次都正確。

不過(guò)3Blue1Brown還是找到了新辦法進(jìn)一步提升成績(jī)。

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

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

也有很多人對(duì)到底哪個(gè)單詞才是最佳開(kāi)局展開(kāi)了討論。

雖然兩步搜索的結(jié)果是crane，不過(guò)3Blue1Brown也不確定對(duì)于人類玩家來(lái)說(shuō)是不是最佳開(kāi)局單詞。

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

對(duì)于人類來(lái)說(shuō)，soare和tares都是很好的開(kāi)局。

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

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

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

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

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

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

如果你看到這里也想挑戰(zhàn)這個(gè)變態(tài)版試試，可以復(fù)制下方鏈接或點(diǎn)擊閱讀原文～

視頻傳送門(mén)：
https://www.youtube.com/c/3blue1brown/videos

原版游戲地址：
https://www.powerlanguage.co.uk/wordle

變態(tài)版游戲地址：
https://qntm.org/files/absurdle/absurdle.html