LoginSignup
1
0

More than 1 year has passed since last update.

@hatori_hoku(羽鳥 北)

データサイエンスでWordleに立ち向かう

Last updated at Posted at 2022-02-14

本記事の目的

インターネット上ではWordleというゲームを攻略するための様々な知見が既に見出されていますが、今回はデータサイエンスを駆使してWordleに立ち向かってみました。
記事にするとそれなりに長い解析をしているので、結論のみを知りたい方は後半 (まとめ) までスキップをお願いします。

What's Wordle?

aaa

  • Webで遊べる日替わりの英単語当てゲームです。
  • ルール
    • システムが独自の辞書から選択したアルファベット5文字の英単語を、プレイヤー (あなた) は最大6回の試行で推測します。
    • 各試行ではプレイヤーが入力した5文字のアルファベットからなる英単語を受けて、真の単語にたどり着くためのヒントが表示されます。
      • 真の単語と同じ位置にそのアルファベットが入力されているならば緑色のハイライト表示
      • 真の単語に含まれているが位置が違うアルファベットが入力されていれば黄色のハイライト表示
      • かすりもしないアルファベットが入力された場合はグレーのハイライト表示
    • めちゃくちゃなアルファベットの羅列、あるいはWordleの内部辞書に登録されていない英単語をプレイヤーが入力することはできません。
  • 詳細はWikipediaの記事を参照ください。

本検討の指針

下記の指針を簡単なPythonコードにより実装します。
柔軟にEDAを行うために、Jupyter Notebookを使用します。

  • 英語コーパスから5文字の英単語リストを作成 1
  • リストに現れる英単語の素性をEDA (exploratory data analysis)
  • EDAの結果をもとにWordleの独自の解法を練る

英単語リストの作成

まずは本検討で必要となるライブラリを一通りimportします。
ポイントとしては、英語コーパスに関するハンドリングのためにnltkを、EDAにおけるネットワーク可視化のためにnetworkxを使います。nltkは自然言語処理ではお馴染みですね。残りはごく一般的なライブラリです。

import copy
import collections
import itertools

import matplotlib.pyplot as plt
import networkx as nx
import nltk
from nltk.corpus import brown
import numpy as np
import pandas as pd

%matplotlib inline
pd.set_option('display.max_columns', 50)

nltkを使って、英語コーパスを入手します。
英語リスト作成に用いるコーパスとしては一般的なものであれば何でも良いですが、有名なBrownコーパスを使うことにします。

# Brown corpusをダウンロード
nltk.download('brown')
# True (ダウンロードが完了すると表示される)

Brownコーパスの全英単語を要素とするlistを作成します。

words = nltk.corpus.brown.words()
# 小文字化しておく
words_lower = [word.lower() for word in words]

コーパスには多数の英文として、様々な英単語やその活用形が収録されています。
一方、Wordleには動詞の過去形、過去分詞形、現在進行形、(いわゆる) 三人称単数現在形が出現しないと海外サイトで噂されているので2、英語リストからこれらを除外します。
そのために、リストに含まれる英単語に対して品詞解析を行います。nltkライブラリでは追加機能をダウンロードすることで、品詞解析も実行することができます。

# pos_tagメソッドをダウンロード
nltk.download('averaged_perceptron_tagger')
# True (ダウンロードが完了すると表示される)

準備が整ったので品詞解析を実行します。

tagged_words = nltk.pos_tag(words_lower)

for i, (word, tag) in enumerate(tagged_words):
    if i == 20: break
    print(i, word, tag)

品詞解析の実行結果です。品詞タグの見方はこちらのQiita記事を参照ください。

0 the DT
1 fulton NN
2 county NN
3 grand JJ
4 jury NN
5 said VBD
6 friday PDT
7 an DT
8 investigation NN
9 of IN
10 atlanta's JJ
11 recent JJ
12 primary JJ
13 election NN
14 produced VBD
15 `` ``
16 no DT
17 evidence NN
18 '' ''
19 that IN

無事、英単語リストに品詞タグを付与することができたので、ここからWordleの対象となる5文字の英単語を小文字化して重複なく抽出します。この際に、動詞の過去形 (VBD)、過去分詞形 (VBN)、三人称単数現在形 (VBZ) を除外します。3

words_5_let = sorted(set(word.lower() for word, tag in tagged_words if len(word) == 5 and word.isalpha() and tag != 'VBD' and tag != 'VBN' and tag != 'VBZ'))
print(len(words_5_let))
print(words_5_let[:10])
print(words_5_let[-10:])
# 3896
# ['aaron', 'aback', 'abbas', 'abbey', 'abbot', 'abell', 'abide', 'abler', 'abner', 'abode']
# ['zabel', 'zadel', 'zebek', 'zebra', 'zeiss', 'zendo', 'zeros', 'ziggy', 'zones', 'zooey']

isalpha()メソッドを使うことにより、記号などを含まない、純粋なアルファベットのみで構成される英単語に制限しています。
結果、5文字の英単語 3896語が抽出されました。リストの冒頭・末尾に含まれる英単語を10語ずつprintしてみましたが、きちんと抽出できていそうですね。

次の処理は若干邪道ですが、Wordle辞書に含まれない数個の英単語をリストから手動で削除します。
実は本解析からWordleの解法を導いたとき、入力すると有望な英単語が複数パターン得られるのですが、上位解法パターンに含まれる英単語のいくつかが、Wordleに入力できませんでした (= Wordleの内部辞書に登録されていませんでした)。そこで、本解析を実施し、導かれた有望な英単語がWordleに入力可能かどうかを実際に試行し、Wordleに入力不可だった場合は解析用英単語リストから削除する処理を3回繰り返しました。

# Wordle辞書に含まれない単語リスト
words_forbidden = ['digby', 'elman', 'bucky', 'danes', 'gorky', 'floyd']
# Wordle辞書に含まれない単語群を削除
words_5_let = [w for w in words_5_let if w not in words_forbidden]
print(len(words_5_let))
# 3890

最終的に6単語を削除したので、5文字の英単語 3890語が残りました。

EDA

ここまでで英語コーパスからWordle向けの英単語データセットを作成できたので、続いていくつかの解析を行います。

各アルファベットが英単語の5文字の枠にどのように使われているのか可視化

先に作成したデータセットに収録されている英単語において、1文字目から5文字目には、それぞれいずれのアルファベットが出現しやすいのか、集計して可視化します。

方針としては、まずデータセット中の全英単語の1文字目のアルファベットを取り出したリストを作成します。この作業をループで2から5文字目のアルファベットにも適用します。

list_lett_n = []
for i in range(5):
    list_lett_n.append([l[i] for l in words_5_let])
    print(list_lett_n[i][:10])
# ['a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a']
# ['a', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b']
# ['r', 'a', 'b', 'b', 'b', 'e', 'i', 'l', 'n', 'o']
# ['o', 'c', 'a', 'e', 'o', 'l', 'd', 'e', 'e', 'd']
# ['n', 'k', 's', 'y', 't', 'l', 'e', 'r', 'r', 'e']

collections.Counterを使って、リストの各要素の出現回数をカウントします。この際、most_common()メソッドを用いると、出現回数順にソートされた結果が返ってきます。もしアルファベット順にソートしたい場合には、temp = dict(sorted(collections.Counter(list_lett_n[i]).items())) のように書きます。

list_cnt_n = []
for i in range(5):
    temp = dict(collections.Counter(list_lett_n[i]).most_common())
    list_cnt_n.append(temp)
    print({k:list_cnt_n[i][k] for k in list(list_cnt_n[i])[:10]})
# {'s': 484, 'b': 316, 'c': 314, 't': 238, 'a': 233, 'p': 230, 'm': 219, 'f': 207, 'd': 198, 'l': 197}
# {'a': 681, 'o': 585, 'e': 487, 'i': 395, 'r': 364, 'u': 305, 'l': 267, 'h': 184, 'n': 103, 't': 98}
# {'a': 447, 'i': 371, 'r': 364, 'o': 318, 'n': 292, 'l': 282, 'e': 276, 'u': 204, 't': 184, 's': 163}
# {'e': 649, 't': 297, 'n': 288, 'l': 273, 'a': 267, 'i': 262, 'r': 229, 'o': 216, 's': 199, 'c': 186}
# {'s': 887, 'e': 596, 'y': 406, 't': 265, 'n': 252, 'r': 243, 'a': 176, 'l': 169, 'h': 158, 'd': 153}

以上の処理を踏まえ、1文字目から5文字目における各アルファベットの出現回数を棒グラフとしてプロットします。4 出現回数をデータセットに占める単語総数 3890 で割ることにより、百分率に換算して表示します。

list_cnt_n_rate = []
for i in range(5):
    temp = np.array(list(list_cnt_n[i].values())) / sum(list_cnt_n[i].values()) * 100.0
    list_cnt_n_rate.append(dict(zip(list(list_cnt_n[i].keys()), temp)))
    plt.bar(list(list_cnt_n_rate[i].keys()), list(list_cnt_n_rate[i].values()))
    # Convert a natural number to an ordinal
    ordinal = (lambda n: '%d%s' % (n, 'tsnrhtdd'[(n / 10 % 10 != 1) * (n % 10 < 4) * n % 10::4]))(i + 1)
    plt.title(f'Frequency of the alphabet at the {ordinal} letter')
    plt.ylabel('Frequency [%]')
    plt.show()

結果は以下の通りです。

freq_let_1.png
freq_let_2.png
freq_let_3.png

freq_let_4.png
freq_let_5.png

1文字目にsが来る確率 (12.4%)、4文字目にeが来る確率 (16.7%)、5文字目にsが来る確率 (22.8%) は、それぞれ同じ文字位置における他のアルファベットと比較して高いことがわかります。すなわち、5文字の英単語の中では、sで始まる単語が最も多いことがわかります。5 5文字目にsが来る確率は全ての文字位置の中でも、絶対的に高くなっています。これは語尾がsで終わる複数形の英単語によって底上げされていることが予想されます。4文字目にeが来る確率が高いことは、5文字目にsが来る確率に共起されている可能性があると仮説を立てています。英語の発音上、eの長音に続き、sで終わる単語はよく見られますが (e.g. boxes)、この構造を反映しているのかもしれません。

2文字目の上位として、母音が現れていることも直感に反していないと考えられます。すなわち、1文字目の子音に続き、2文字目には子音ではなく母音が来ることで、英語の発音がしやすくなります。興味深いことは、1, 3, 4, 5文字目の出現確率のグラフは下位までテールを引いているのに対して、2文字目のグラフはバーの高さがより早く減衰していることです。この事実も、2文字目には子音よりも母音が来やすいという英語の発音上の特性が反映されていることが示唆されます。

もう一つ興味深いこととして、各文字位置に現れるアルファベットの出現回数は以下のようになります。

for i in range(5):
    print(i + 1, len(list_cnt_n[i]))
# 1 26
# 2 26
# 3 26
# 4 26
# 5 24

1文字目から4文字目までは26アルファベット全てが使用されていますが、5文字目のみ24アルファベットしか使われていません。5文字目に出現するアルファベットを確認してみましょう。

print(sorted(list_cnt_n[4]))
# ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'k', 'l', 'm', 'n', 'o', 'p', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

すなわち、jとqで終わるアルファベットは (今回のデータセットの範疇では) 存在しないことになります。これはWordleの戦略に関わる大きな事実です。

各アルファベットが英単語にどのくらい使われているのか可視化

続いて、文字位置に関係なく、いずれのアルファベットが英単語に使用されやすいのか、集計して可視化します。

方針としては、先に作成した英単語の1文字目から5文字目までのアルファベットの出現回数をカウントしたリストを統合し、全英単語中の各アルファベットの出現回数を調べます。

def add_two_dicts(dict_a, dict_b):
    dict_new = {}
    for key in sorted(dict_a.keys() | dict_b.keys()):
        val_a = dict_a.get(key) or 0
        val_b = dict_b.get(key) or 0
        val = val_a + val_b
        dict_new[key] = val
    return dict_new

list_cnt_all = add_two_dicts(list_cnt_n[0], list_cnt_n[1])
list_cnt_all = add_two_dicts(list_cnt_all, list_cnt_n[2])
list_cnt_all = add_two_dicts(list_cnt_all, list_cnt_n[3])
list_cnt_all = add_two_dicts(list_cnt_all, list_cnt_n[4])
list_cnt_all = dict(sorted(list_cnt_all.items(), key=lambda x:x[1], reverse=True))

こちらも百分率に換算してプロットします。

temp = np.array(list(list_cnt_all.values())) / sum(list_cnt_all.values()) * 100.0
list_cnt_all_rate = dict(zip(list(list_cnt_all.keys()), temp))
list_cnt_all_rate
plt.bar(list(list_cnt_all_rate.keys()), list(list_cnt_all_rate.values()))
plt.title(f'Frequency of the alphabet')
plt.ylabel('Frequency [%]')
plt.show()

freq_all.png

上図より、eの出現確率が最も高く、10.83%となりました。すなわち、今回の解析からは、英単語中でeが最も多く使われるアルファベットであることが示唆されました。

この事実は、シャーロック・ホームズシリーズの短編小説『踊る人形 (The Adventure of the Dancing Men)』における、次の有名なセリフと相違ありません。6

As you are aware, E is the most common letter in the English alphabet, and it predominates to so marked an extent that even in a short sentence one would expect to find it most often. Out of fifteen symbols in the first message four were the same, so it was reasonable to set this down as E.

同作品では、「英語で最も多く使われる文字はEである」という手掛かりをもとに、「踊る人形」と称される暗号を解き、推理が進んでいきます。

話は解析に戻り、eに続いて出現しやすいaおよびsでも、出現確率がそれぞれ9.27%および9.11%と高い値を取ることがわかりました。つまり、e/a/sの3文字だけで約30%の実効的なアルファベット空間を占めることができます。

この解析からは様々な戦法が導出できそうなので、最後に全アルファベットの出現確率を降順にソートし、累積確率とともに示します。

df_let_all = pd.DataFrame(list(list_cnt_all_rate.values()), index=list(list_cnt_all_rate.keys()), columns=['rate'])
df_let_all['accumulate'] = list(itertools.accumulate(list(list_cnt_all_rate.values())))
df_let_all
alphabet rate accumulate
e 10.832905 10.832905
a 9.269923 20.102828
s 9.110540 29.213368
r 7.028278 36.241645
o 6.704370 42.946015
l 6.102828 49.048843
i 5.866324 54.915167
t 5.562982 60.478149
n 5.275064 65.753213
c 3.588689 69.341902
d 3.434447 72.776350
u 3.434447 76.210797
h 3.012853 79.223650
m 2.910026 82.133676
y 2.832905 84.966581
p 2.632391 87.598972
b 2.580977 90.179949
g 2.313625 92.493573
k 1.845758 94.339332
f 1.717224 96.056555
w 1.444730 97.501285
v 1.192802 98.694087
z 0.416452 99.110540
j 0.401028 99.511568
x 0.339332 99.850900
q 0.149100 100.000000

共起ネットワークの解析

続いて、一つの英単語の中で、あるアルファベットとあるアルファベットが一緒に出現しやすいかどうか (共起しやすいかどうか) をネットワーク図として可視化します。ここでは、以下の例で示すルールに則って、各単語に出現するアルファベットのペアを抽出します。

  • _e_s_
    • (e, s)は抽出される
    • (s, e)は抽出されない
  • _s_e_
    • (s, e)は抽出される
    • (e, s)は抽出されない
  • _e_sE (二つのイーを大文字・小文字を用いて区別する)
    • (e, s), (e, E), (s, E)は抽出される
    • (s, e), (E, e), (E, s)は抽出されない

すなわち、前から後ろへの文字の流れを考慮し、異なる文字位置にある同アルファベットは別物として扱い、アルファベットのペアを取得します。ペアの取得にはitertools.combinations()を用います。

combi_let = [list(itertools.combinations(word, 2)) for word in words_5_let]
combi_let = list(itertools.chain.from_iterable(combi_let))
list_cnt_combi_let = dict(collections.Counter(combi_let).most_common())
for i, (k, v) in enumerate(zip(list_cnt_combi_let.keys(), list_cnt_combi_let.values())):
    if i == 10: break
    print(i, k, v)
# 0 ('e', 's') 478
# 1 ('a', 's') 471
# 2 ('a', 'e') 446
# 3 ('r', 'e') 396
# 4 ('l', 'e') 378
# 5 ('e', 'r') 372
# 6 ('o', 's') 369
# 7 ('s', 'e') 359
# 8 ('a', 'n') 357
# 9 ('a', 'r') 346

取得したペアをネットワーク図として可視化します。networkx を用いてグラフを作成します。ノードには各アルファベット、エッジには各ノードペアを割り当てます。先ほどの例で云う (e, s)と (s, e) を区別し、有向グラフ DiGraph() としてプロットします。また、ノード・エッジの大きさ・太さ・色により、各アルファベットの出現数、各アルファベットペアの出現数を表現します。

G = nx.DiGraph()
G.add_nodes_from(list(list_cnt_all.keys()))
G.add_edges_from(list(list_cnt_combi_let.keys()))
nx.set_edge_attributes(G, name='weight', values=0)
for u, v in list_cnt_combi_let.keys():
    G.edges[u, v]['weight'] = list_cnt_combi_let[u, v]

# Visualize
pos = nx.circular_layout(G)
nx.draw_networkx(G, pos=pos, node_color="c", node_size=np.array(list(list_cnt_all.values()))/10, width=[G.edges[u, v]['weight']/500 for u, v in G.edges], edge_color=[G.edges[u, v]['weight']/500 for u, v in G.edges], connectionstyle='arc3, rad=0.2')

network_all.png

やはり、出現頻度の高いアルファベットから集中してエッジが生えていますが、この図だけだと複雑で知見を得にくいです。そこで、もう少し単純化し、連続したアルファベットの共起関係のみを可視化します。つまり、scare という単語からは (s, c), (c, a), (a, r), (r, e) という4個のペアを抽出します。

def extract_consecutive_let(word):
    list_new = []
    for i in range(len(word) - 1):
        temp = word[i], word[i + 1]
        list_new.append(temp)
    return list_new

combi_let_consecutive = [extract_consecutive_let(word) for word in words_5_let]
combi_let_consecutive = list(itertools.chain.from_iterable(combi_let_consecutive))
list_cnt_combi_let_consecutive = dict(collections.Counter(combi_let_consecutive).most_common())
for i, (k, v) in enumerate(zip(list_cnt_combi_let_consecutive.keys(), list_cnt_combi_let_consecutive.values())):
    if i == 10: break
    print(i, k, v)
# 0 ('e', 'r') 260
# 1 ('e', 's') 234
# 2 ('a', 'r') 212
# 3 ('a', 'n') 208
# 4 ('i', 'n') 208
# 5 ('l', 'e') 194
# 6 ('r', 'a') 189
# 7 ('a', 'l') 174
# 8 ('r', 'e') 172
# 9 ('s', 't') 163

同じく、各アルファベットおよびアルファベットペアの出現個数をネットワーク図に可視化します。

G2 = nx.DiGraph()
G2.add_nodes_from(list(list_cnt_all.keys()))
G2.add_edges_from(list(list_cnt_combi_let_consecutive.keys()))
nx.set_edge_attributes(G2, name='weight', values=0)
for u, v in list_cnt_combi_let_consecutive.keys():
    G2.edges[u, v]['weight'] = list_cnt_combi_let_consecutive[u, v]

# Visualize
pos = nx.circular_layout(G2)
nx.draw_networkx(G2, pos=pos, node_color="c", node_size=np.array(list(list_cnt_all.values()))/10, width=[G2.edges[u, v]['weight']/500 for u, v in G2.edges], edge_color=[G2.edges[u, v]['weight']/500 for u, v in G2.edges], connectionstyle='arc3, rad=0.2')

network_neighbor.png

依然として複雑ではありますが、先ほどのネットワーク図よりも大分シンプルになりました。ここでも出現頻度の高いノードから生えているエッジが多いこと、母音から生えているエッジが多いことは当然ですが、いくつか子音間でも太いエッジがあることがわかります。この図から得られる知見は、Wordleで穴抜きのアルファベットを推測するのに役立つかもしれません。

Wordleの戦略立案

さて、ここまでの知見を利用して、データサイエンス的にWordleの効率的な戦略を考えてみたいと思います。
目的関数 (評価関数・報酬関数) は色々考えられるので、それに応じて戦略も様々なパターンが考えられます。

まず、複数回の試行で同じアルファベットを入力することは冗長なので、同じアルファベットを使わない単語をリストから抽出します。単語内に包含される文字をset化することで、ユニークな文字のみが生き残ります。生き残った文字数が5文字であるかにより、冗長性のないアルファベットかどうかを判定します。

word_5_let_no_redun = [word for word in words_5_let if len(set(word)) == 5]
print(word_5_let_no_redun[:10])
print(len(word_5_let_no_redun))
# ['abide', 'abler', 'abner', 'abode', 'about', 'above', 'abuse', 'aches', 'acids', 'acres']
# 2554

同じアルファベットを含まない英単語は、今回2554語見つかりました。この単語群を用いて、以下のいくつかの戦略を考えます。

出現確率の高いアルファベットをなるべく先に消化する作戦

先ほど、各アルファベットの出現確率の序列を調べました。e, a, s, r, o, l, i, t, n, c, d, u, h, m, y, p, b, ... という序列です。このランキング上位に現れるアルファベットからできるだけ順に使って、Wordleの試行として入力する英単語を定めます。

let_desc_order.png

まずは、最上位のe, a, s, r, oを使った英単語をリストから探します。

[w for w in word_5_let_no_redun if 'e' in w and 'a' in w and 'r' in w and 'o' in w and 's' in w]
# ['arose']

arose の1語のみ発見されました。

続いて、l, i, t, n, c を使った英単語をリストから探します。

[w for w in word_5_let_no_redun if 'l' in w and 'i' in w and 't' in w and 'n' in w and 'c' in w]
# ['clint']

clint (岩棚) の1語のみ発見されました。

次の5文字 d, u, h, m y を使った英単語をリストから探します。

[w for w in word_5_let_no_redun if 'u' in w and 'd' in w and 'y' in w and 'h' in w and 'm' in w]
# []

流石にそう都合良くは見つかりませんでした。

そこで、既出の e, a, s, r, o, l, i, t, n, c を含まない英単語をリストから探します。

[w for w in word_5_let_no_redun if 'e' not in w and 'a' not in w and 'r' not in w and 'o' not in w and 's' not in w and 'l' not in w and 'i' not in w and 't' not in w and 'n' not in w and 'c' not in w]
# ['jumpy']

jumpy (ガタガタする・ビクビクする) の1語のみ発見されました。

この単語群に含まれるアルファベットの出現確率から、全体に対する寄与を算出します。

contri_arose = list_cnt_all_rate['a'] + list_cnt_all_rate['r'] + list_cnt_all_rate['o'] + list_cnt_all_rate['s'] + list_cnt_all_rate['e']
contri_arose
# 42.94525828835775

aroseの寄与は42.9%でした。

contri_clint = list_cnt_all_rate['c'] + list_cnt_all_rate['l'] + list_cnt_all_rate['i'] + list_cnt_all_rate['n'] + list_cnt_all_rate['t']
contri_clint
# 26.3993831919815

clintの寄与は26.4%でした。

contri_jumpy = list_cnt_all_rate['j'] + list_cnt_all_rate['u'] + list_cnt_all_rate['m'] + list_cnt_all_rate['p'] + list_cnt_all_rate['y']
contri_jumpy
# 12.212798766383962

jumpyの寄与は12.2%でした。

contri_arose + contri_clint
# 69.34464148033925

すなわち、最初2回の試行でaroseとclintを入力すると、空間の69.3%を網羅できます。

contri_arose + contri_clint + contri_jumpy
# 81.55744024672322

さらに、最初の3回の試行でaroseとclintとjumpyを入力すると、空間の81.6%を網羅できます。

let_desc_aroseclintjumpy.png

【作戦1】 "arose", "clint", "jumpy" をこの順番で入力することは、3回の試行で81.6%の空間を網羅し得る最も効率的な戦略の一つである。

効率的な単語の組み合わせをbrute-forceに探索

アルファベットの出現確率の序列のうち、末尾の j, z, x, q は特に出現確率が低く、いずれも1%未満でした。また、そのすぐ上位に位置する w, v の出現確率も1.5%未満です。そこで、w, v, j, z, x, q の6文字 (総確率 3.9%) を除き、残り20文字のアルファベット (総確率 96.1%) で構成できる英単語の組み合わせをbrute-force (総当たり) で探索します。

let_desc_cutoff.png

まず、特定のアルファベットを含む英単語を親リストから削除する関数を実装しておきます。

# Remove words containing specific letters from the list
def remove_specific_let(words, letters, verbose=False):
    words_new = copy.deepcopy(words)
    for let in letters:
        words_new = [word for word in words_new if let not in word]
        if verbose: print(f'{let} has been removed; #words = {len(words_new)}')
    return words_new

# Remove words containing five specific letters from the list
# (faster than the one above)
def remove_specific_5_let(words, letters, verbose=False):
    words_new = [w for w in words if letters[0] not in w and letters[1] not in w and letters[2] not in w and letters[3] not in w and letters[4] not in w]
    if verbose: print(f'{letters} has been removed; #words = {len(words_new)}')
    return words_new

上の関数を用いて、探索空間から w, v, j, z, x, q を除外します。

word_5_let_no_redun_constrain = remove_specific_let(word_5_let_no_redun, 'wvzjxq', verbose=True)
# w has been removed; #words = 2342
# v has been removed; #words = 2185
# z has been removed; #words = 2146
# j has been removed; #words = 2097
# x has been removed; #words = 2051
# q has been removed; #words = 2030

最終的に探索空間は2030語まで削減されました。

ここから除外されなかったアルファベット20語を重複なく含む、4語の英単語の組み合わせをbrute-force探索します。ここではstraightforwardに4重ループを書いて探索します。4重ループにすると計算コストが気になるので、実行時間を計測しておきます。今回はJupyter Notebookでコーディングしているので、%%timeコマンドを付けるだけでこのセルのCPU timeとwall timeを簡単に調べることができます。

%%time
words_efficient = []
for w1 in word_5_let_no_redun_constrain:
    rest_words_1 = remove_specific_5_let(word_5_let_no_redun_constrain, w1)
    for w2 in rest_words_1:
        rest_words_2 = remove_specific_5_let(rest_words_1, w2)
        for w3 in rest_words_2:
            rest_words_3 = remove_specific_5_let(rest_words_2, w3)
            for w4 in rest_words_3:
                rest_words_4 = remove_specific_5_let(rest_words_3, w4)
                words_efficient.append([w1, w2, w3, w4])
# CPU times: user 32.4 s, sys: 0 ns, total: 32.4 s
# Wall time: 32.5 s

探索は32.5秒のwall timeで完了しました。4重ループによるbrute-force探索でしたが、比較的短時間で探索することができました。組み合わせパターンが限定的であるためと推測されます。

発見された単語のパターンをデータフレームとして出力してみます。

df_words_efficient = pd.DataFrame(words_efficient, columns=['w1', 'w2', 'w3', 'w4'])
df_words_efficient

table_efficient_words.png

全部で86544のパターンの単語群が抽出されました。画面出力されている組み合わせを見ると、20個のアルファベットが重複なく4単語に散らばっていることが確認できます。ここで注意すべきは、たとえばデータフレームの0行目と1行目を比べると、これらのパターンでは用いている4単語の組み合わせは同一ですが、3単語目と4単語目の順番のみが異なります。Wordleでは同じ単語の組み合わせを入力する場合でも、どの単語をより早く入力するかに依存して、その戦略の有効性が変わってくるため、本検討ではこのような出力の形式を取っています。

並び順を無視した、ユニークな組み合わせパターンの個数をカウントしてみましょう。

words_efficient = df_words_efficient.values.tolist()
temp = [tuple(sorted(words)) for words in words_efficient]
words_efficient_no_redun = sorted(set(temp))
print(words_efficient_no_redun[:3])
print(len(words_efficient_no_redun))
# [('abide', 'frock', 'lymph', 'stung'), ('abner', 'docks', 'fight', 'lumpy'), ('abner', 'dutch', 'folks', 'gimpy')]
# 3606

ユニークな組み合わせは3606パターン存在することが確認できました。

さて、ここでは単語の入力順も考慮した全86544パターンの単語群それぞれに対して、いくつかの妥当なスコアリングを行い、Wordleにおける有効な戦術を導いていきましょう。

まずは、最も標準的なやり方として、先に調べた「単語リストにおける各アルファベットの出現確率」(文字位置に関係なく、いずれのアルファベットが英単語に使用されやすいのかという指標) によって、各単語のスコアリングをします。本検討ではこの評価指標をsスコアと称することにします。

scores_whole = []
for i in range(len(words_efficient)):
    scores_whole_temp = []
    for j in range(4):
        word = words_efficient[i][j]
        score = 0.0
        for k in range(len(word)):
            score += list_cnt_all_rate[word[k]]
        scores_whole_temp.append(score)
    scores_whole.append(scores_whole_temp)
df_scores_whole = pd.DataFrame(scores_whole, columns=[f's{i+1}' for i in range(4)])
df_scores_whole.describe()

summary_sscore.png

各パターンに現れる4単語のsスコアが算出されました。さらに、「sスコアの高い単語ほど先に入力すべきである」と考えられることから、4単語のsスコアに対して重み係数を導入し、先に入力する単語ほど重みが大きくなるように調整します。この指標をrスコアと呼ぶことにします。ここでは単純に4単語のsスコアに対して、前から順に0.4, 0.3, 0.2, 0.1という重み係数を掛けたものをrスコアとします。最終的にrスコアの総和 r_sum が、各単語パターンの良し悪しを判断する指標の一つとなります。

# Weights
c1, c2, c3, c4 = 0.4, 0.3, 0.2, 0.1

df_scores_whole['r1'] = df_scores_whole['s1'] * c1
df_scores_whole['r2'] = df_scores_whole['s2'] * c2
df_scores_whole['r3'] = df_scores_whole['s3'] * c3
df_scores_whole['r4'] = df_scores_whole['s4'] * c4
df_scores_whole['r_sum'] = df_scores_whole['r1'] + df_scores_whole['r2'] + df_scores_whole['r3'] + df_scores_whole['r4']
df_scores_whole

summary_rscore.png

最後に、pスコアという指標を導入します。こちらも先に算出した確率的指標で、「単語リストの各文字位置における各アルファベットの出現確率」(英単語の5文字の枠それぞれにおいて、いずれのアルファベットが使用されやすいのかという指標) によって、各単語のスコアリングをします。

scores_partial = []
for i in range(len(words_efficient)):
    scores_partial_temp = []
    for j in range(4):
        word = words_efficient[i][j]
        score = 0.0
        for k in range(len(word)):
            score += list_cnt_n_rate[k][word[k]]
        scores_partial_temp.append(score)
    scores_partial.append(scores_partial_temp)
df_scores_partial = pd.DataFrame(scores_partial, columns=[f'p{i+1}' for i in range(4)])
df_scores_partial

summary_pscore.png

Wordleを遊ぶ上では、入力したアルファベットの文字位置が正しいかどうかも知りたい情報ですが、そもそも入力したアルファベットが単語の中に含まれるかどうかということの方が、多くの場合においてより重要な情報です。そこでpスコアは、先のrスコアおよびsスコアと組み合わせることで、補助的に用いることを考えます。ここでは、rスコアとpスコアの積をrpスコア、sスコアとpスコアの積をspスコアと呼称します。rpスコアおよびspスコアの総和もそれぞれ、各英単語パターンの評価指標の一つとなります。探索された英単語パターンとそれらのスコアをconcatして、最終的なデータフレームを作成しましょう。

df_words_efficient_with_scores = pd.concat([df_words_efficient, df_scores_whole, df_scores_partial], axis=1)
df_words_efficient_with_scores['rp_sum'] = df_words_efficient_with_scores['r1'] * df_words_efficient_with_scores['p1'] + df_words_efficient_with_scores['r2'] * df_words_efficient_with_scores['p2'] + df_words_efficient_with_scores['r3'] * df_words_efficient_with_scores['p3'] + df_words_efficient_with_scores['r4'] * df_words_efficient_with_scores['p4'] 
df_words_efficient_with_scores['sp_sum'] = df_words_efficient_with_scores['s1'] * df_words_efficient_with_scores['p1'] + df_words_efficient_with_scores['s2'] * df_words_efficient_with_scores['p2'] + df_words_efficient_with_scores['s3'] * df_words_efficient_with_scores['p3'] + df_words_efficient_with_scores['s4'] * df_words_efficient_with_scores['p4'] 
df_words_efficient_with_scores.loc[:,['w1', 'w2', 'w3', 'w4', 'r_sum', 'rp_sum', 'sp_sum']]

summary_scores.png

戦略策定に向けて、統計情報も表示しておきましょう。

df_words_efficient_with_scores.loc[:,['w1', 'w2', 'w3', 'w4', 'r_sum', 'rp_sum', 'sp_sum']].describe()

scores_desc.png

さて、各指標に従って、複数の有効な戦略を導出してみましょう。以下では、それぞれの指標を最大化するような単語パターンを抽出します。

【rスコア】

df_words_efficient_with_scores[df_scores_whole['r_sum'] == df_scores_whole['r_sum'].max()].loc[:,['w1', 'w2', 'w3', 'w4', 'r_sum', 'rp_sum', 'sp_sum']]

best_r.png

rスコアが最大となるパターンは2組見つかりました。
(gears, doubt, flick, nymph あるいは rages, doubt, flick, nymph)

【rpスコア】

df_words_efficient_with_scores[df_words_efficient_with_scores['rp_sum'] == df_words_efficient_with_scores['rp_sum'].max()].loc[:,['w1', 'w2', 'w3', 'w4', 'r_sum', 'rp_sum', 'sp_sum']]

best_rp.png

rpスコアが最大となるパターンは1組見つかりました。
(bales, dingy, frock, thump)

【spスコア】

df_words_efficient_with_scores[df_words_efficient_with_scores['sp_sum'] == df_words_efficient_with_scores['sp_sum'].max()].loc[:,['w1', 'w2', 'w3', 'w4', 'r_sum', 'rp_sum', 'sp_sum']]

best_sp.png

20パターンの単語群が得られました。
(bundy, frock, might, pales の並び替え)

目的関数 (評価関数・報酬関数) の定め方が一意ではないので、ここでは3種類の戦略が見出されました。このうち、敢えて一つの戦略のみを選出するならば、rpスコアの総和を最大化するパターン (bales, dingy, frock, thump7) が良いかもしれません。 なぜならば、rpスコアは「各アルファベットの出現確率」、「各文字位置における各アルファベットの出現確率」、および「sスコアの高い単語ほど先に入力すべきである」という最も多くの要素を同時に考慮している指標となっているからです。さらに、この英単語のパターンはrpスコアの総和を最大化するだけでなく、rスコアの総和およびspスコアの総和も、比較的高い値をとっていることがわかります。

この戦略における評価関数の定め方に関しては議論が尽きないところですが、本セクションの仮定より、いずれの英単語の組み合わせも出現しやすいアルファベット上位20種類のアナグラムで構成されていることから、どのようなミクロな戦略を取ったとしても、全空間の96.1%の可能性を網羅可能であることは確かです。

【作戦2】 "bales", "dingy", "frock", "thump" を入力することは、4回の試行で96.1%の空間を網羅し得る最も効率的な戦略の一つである。

まとめ

  • Brownコーパスという英語コーパスから、5文字の英単語リストを作成しました。
  • 作成した英単語リストに対する統計解析より、各アルファベットの出現確率を複数の観点から調べました。
  • 解析結果に基づき、Wordleにおける複数の有効な戦略を見出しました。特に有効な二つの戦略 (入力パターン) は以下の通りです。
    • arose → clint → jumpy (3試行): 81.6%の空間を網羅可能
    • bales → dingy → frock → thump (4試行): 96.1%の空間を網羅可能

  1. インターネット上ではWordleに搭載されている英語辞書が特定されているようですが、本検討ではそちらを参照せず、あくまで一般的な知識に基づいて挑みます。単語空間が完全に特定されているならば、最強の作戦を立案することができそうですよね。 ↩

  2. 参考ページ ↩

  3. 本当はWordleで対象外らしい固有名詞 (品詞タグ: NNP) も除外したかったのですが、nltkによる固有名詞の判定精度が今ひとつに感じたので、今回は省略しました。具体的には、大文字始まりの一般名詞まで固有名詞と判定されることが多いように見受けられました。 ↩

  4. ここではグラフタイトルに序数を含めるために、こちらのページの方法を参考にさせていただきました。 ↩

  5. この理由を考えてみましたが、あまり思いつきませんでした。単純に偶々と割り切るのが良いでしょうか…。情報をご存知の方、仮説を思いつかれた方はご教示いただけますと幸いです。 ↩

  6. The Adventure of the Dancing Men (PDF) ↩

  7. それぞれの英単語の意味は次の通りです。bales = bale (俵) の複数形、dingy = 薄汚れた、frock = 仕事着/僧服、thump = ゴツンと叩く。 ↩

1
0
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0