| 小火龍果 |
2023-07-07 11:27 |
Wolfram：25個(gè)最好的猜單詞游戲
[attachment=118762]
sG
F aL
V=o
t-1,j7
一個(gè)六歲孩子關(guān)于猜單詞的簡(jiǎn)單問題變成了另一種分析的癡迷，使我最近玩了1500萬(wàn)場(chǎng)猜單詞游戲。 a6uJYhS~
a ?)NC
早在 2007 年，我在從牛津到倫敦的火車上為一個(gè)人類猜測(cè)者寫了一個(gè)猜單詞游戲。我在倫敦地鐵上花時(shí)間思考玩這個(gè)游戲的最佳策略，并在回程時(shí)為做猜詞的計(jì)算機(jī)寫了這個(gè)版本。它成功地猜出了我的測(cè)試詞，我很滿意，所以我把這兩個(gè)版本提交給了 Wolfram 演示項(xiàng)目。三年后的今天，我的女兒已經(jīng)長(zhǎng)大了，可以玩了，但演示讓她很惱火，因?yàn)樗偸悄懿碌剿脑~。她問了一個(gè)顯而易見的問題，當(dāng)時(shí)我從來沒有想過。"我能選擇最難的詞是什么，這樣我就可以打敗它？"[attachment=118763] ?`PvL!'
++`0rY%
如果您不知道，猜單詞的想法是，一個(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ò)誤。 De'_S D|=
7 t0e r'VC
為什么是劊子手？我不知道。據(jù)稱，這個(gè)游戲可以追溯到維多利亞時(shí)代的英國(guó)，當(dāng)時(shí)絞刑可能是對(duì)拼寫不良的一種可接受的懲罰! @X#F3;
以下是我是如何創(chuàng)建這些游戲的。首先，讓我描述一下我們正在攻擊的算法。我的猜單詞算法使用所有可用的信息來產(chǎn)生一個(gè)候選詞的列表。起初，可用的信息只是單詞的長(zhǎng)度，但后來我們會(huì)知道一些字母和它們的位置，還有一些不在單詞中的字母。所有這三點(diǎn)信息都可以很快地減少字典。接下來，游戲會(huì)對(duì)所有候選詞中的字母進(jìn)行頻率分析（有多少候選詞中至少包含一個(gè) "a"，至少包含一個(gè) "b"，以此類推）。我們避免猜錯(cuò)的最好機(jī)會(huì)（如果我們假設(shè)這個(gè)詞是從字典中隨機(jī)選擇的）是選擇一個(gè)經(jīng)常出現(xiàn)的字母。 iMDM1}b
在這一點(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)重。 NgP&.39U
(說點(diǎn)題外話：幾年前在倫敦舉行的第五屆國(guó)際數(shù)學(xué)研討會(huì)上，我有幸聆聽了 John Nash- 納什均衡的發(fā)明者，諾貝爾獎(jiǎng)獲得者，以及電影《美麗心靈》的主角，講述了他對(duì) Mathematica 的使用。每年的諾貝爾獎(jiǎng)名單中通常至少有一位 Mathematica 用戶，盡管遺憾的是，諾貝爾獎(jiǎng)得主很少出現(xiàn)在好萊塢電影中)。 KV0]m ^@x
從概念上講，回答我女兒的問題最簡(jiǎn)單的方法是對(duì)每一個(gè)可能的詞進(jìn)行粗暴的蒙特卡洛分析。我所做的第一件事是重構(gòu)演示中的代碼，使其更快。在我的演示中，篩選 90,000 個(gè)單詞的字典并進(jìn)行頻率分析大約需要 0.2 秒--在互動(dòng)游戲中是瞬時(shí)的。但是模擬整個(gè)游戲可能需要多達(dá) 26 個(gè)這樣的選擇，由于我想模擬 1500 萬(wàn)個(gè)游戲，我花了幾分鐘時(shí)間使用 Wolfram Workbench 中的 Profiler 來了解時(shí)間的去向，結(jié)果得到了一個(gè)快 10 倍的版本。如果要重復(fù)或改進(jìn)我的分析,此實(shí)施位于帖子的底部。 woK&q
| |