先日の記事でWordleに表示された条件を入力したら候補の単語を表示してくれるソフトを作りました。この応用で、「次に入力すべき単語」を提案してくれるソフトを作っていきたいと思います。
メタ的なアプローチ
いきなりですがメタ的なアプローチをします。メタ的というのは、「こういう単語が出そう」という予想から始めるという意味です。
Wordleに入力できる（＝答えとしてあり得る） 単語はこちらのページに出ています。
Wordle 単語リスト
しかし、中には固有名詞だったり普通の英和辞典では出てこなかったりと、かなりニッチな単語もあります。そのような単語が答えになることはまずなく、メジャーな単語が答えになる「だろう」という解き方です。
邪道と思う人も多いかもしれませんが、現実としてWordleを少ない手数で解こうと思うとかなり有効と考えられます。
メジャーな単語
さて、そうするとここで重要になってくるのが「メジャーな単語」です。何をもってメジャーと言うかですが、こういうのは意外と世の中研究されているようです。今回は2種類持ってきました。
Moby Word Lists by Grady Ward
BNC database and word frequency lists
前者には様々な単語のリストがありますが、今回は「common」を選びました。これは2つ以上の辞書に載っているような一般的な単語が入っているようです。後者は「Lemmatised list（見出し語リスト）」から選びました。おそらく記事の見出しなどで使われる言葉なんだと思います。
前者は約75,000語、後者は約6,300語ありますが、Wordle単語リストに含まれていないものを除外するとそれぞれ4,056語、777語となりました。便宜上、前者を「common」、後者を「frequent」と呼ぶこととします。
common.txt
frequent.txt
評価
本日（2022年3月21日）時点でWordleは275まで来ています。どうもスタートは0だったらしく、合計276語が今までに出題されていたようです。この単語がcommonやfrequentにどれくらい含まれているかを調べてみました。
| Common | Frequent | |
| 答えが含まれている割合 | 96.74% | 42.03% |
| 全体に対する単語数の割合 | 31.27% | 5.99% |
Wordleの全単語のうち6%に42%の答えが集中し、1/3弱に96%以上の答えが集中していることになります。これを愚直に全単語から1つの単語を取り出すためのアルゴリズムを考え続けるのはかなりもったいないです。ですので、メタ的な解法ではありますが、基本戦略としてこれら2つの単語リストをできるだけ生かしていくことにします。
文字の出現頻度
さて、続いて正統派（？）なアプローチをしていきます。Wordleはできるだけ少ない手数で上がるゲームですので、絞り込みが進めば進むほど、すなわち単語を入力したときに次の候補の数が少なければ少ないほど良い手と言えます。
ですので、極端に言えば、総当たりですべての入力可能な単語を入れて、そして答えがすべてのパターンだった時を想定して、候補数が最小になるものを選べば良いという話になります。ただ、基本的に入力可能な単語の数も答えの候補の数もオーダーは同じですので、すべての組み合わせを試すには$O(n^2)$の計算量が必要です。全単語は13,000語弱ありますから、良いアプローチとは言えません。
そこで、文字の出現頻度を使った方法を考えていきます。Wordleは⬜よりも🟨や🟩が出た時のほうがゲームが大きく進むことを利用し、最も使われる文字から入れていって早く🟨や🟩を出してしまおうという作戦です。
それぞれの文字の出現頻度は以下の通りです。
前述の通り、Wordleに入れられるすべての文字のほか、commonやfrequentという単語セットを用意しましたので、それぞれについて求めています。一部eやsなどのように偏りがあるものもありますが、概ね同様の傾向と言えるでしょう。あまりどの母集団を使うかは気にしなくてよさそうです。
ソルバーの実装/評価
まずは、出現頻度評価が簡単にできるようにこんな基底クラスを実装してみました。
public abstract class SolverBase : ISolver
{
public abstract string Suggest(IEnumerable<IWordHint> hints);
protected Dictionary<char, int> GetCharCount(IEnumerable<string> words)
{
return GetCharCount(words.SelectMany(p => p));
}
protected Dictionary<char, int> GetCharCount(IEnumerable<char> chars)
{
var result = new Dictionary<char, int>();
for(var c = 'a'; c <= 'z'; c++)
result[c] = 0;
foreach(var c in chars)
result[c]++;
return result;
}
protected IEnumerable<(string word, int point)> GetWordRanking(IEnumerable<string> words, IReadOnlyDictionary<char, int> charcount)
{
return words.Select(p => (word: p, point: p.Distinct().Sum(p => charcount[p]))).OrderByDescending(p => p.point);
}
}
GetCharCount()は各文字が何回ずつ使われているかを数えるメソッドです。
GetWordRanking()は単語リストを与えると、各文字に割り当てられた点数をもとにスコアを計算し、上位から順に返すメソッドです。同じ文字が2回以上使われる単語で点数を重複して加算するのは不適切なので、そのような場合は2回目以降ゼロ点になるようにしています。
実際は、GetCharCount()で得た文字の出現回数をそのまま点数としてGetWordRankingに渡すことを想定しています。
頻出文字法
さて、具体的に実装と評価を行っていきます。まずはシンプルに、「頻出文字を多く含む単語から順に入れていく」作戦をします。
public class FrequentCharSolver : SolverBase
{
IReadOnlySet<string>[] universe;
public FrequentCharSolver(IReadOnlySet<string>[] universe)
{
this.universe = universe;
}
public override string Suggest(IEnumerable<IWordHint> hints)
{
IReadOnlySet<string>? candidates = null;
foreach(var list in universe) {
candidates = Candidate.Nominate(hints, list);
if(candidates.Count > 0)
break;
}
if(candidates == null || candidates.Count <= 0)
throw new InvalidOperationException();
return GetWordRanking(candidates, GetCharCount(candidates)).First().word;
}
}
コンストラクタで受け取るuniverseは調べる単語の母集団、すなわちfrequent / common / allです。1つ目の母集団のつもりで検索をかけ、もしも無かったら次の母集団に行くという流れになります。回答を確実に含む母集団が必ずなければなりませんので、allを最後に含める必要があります。
これらについて、お題の単語を過去問 / frequent / common / allの4つパターンを与え、計12パターンの評価をしてみました。
| お題 | 検索母集団 | 最小手数 | 平均手数 | 最大手数 |
| 過去問 | frequent→common→all | 2 | 3.7572 | 8 |
| 過去問 | common→all | 2 | 4.0326 | 8 |
| 過去問 | all | 2 | 4.5000 | 11 |
| frequent | frequent→common→all | 1 | 3.1609 | 6 |
| frequent | common→all | 2 | 4.0193 | 10 |
| frequent | all | 2 | 4.5328 | 13 |
| common | frequent→common→all | 1 | 3.9768 | 10 |
| common | common→all | 1 | 3.9539 | 10 |
| common | all | 2 | 4.5155 | 14 |
| all | frequent→common→all | 1 | 4.8251 | 17 |
| all | common→all | 1 | 4.9184 | 16 |
| all | all | 1 | 4.8366 | 16 |
上3行を見ても明らかですが、前述の「メタ解法」がめちゃめちゃ有効であることがわかります。ほかはあまり言えることはなさそうですが、まあ一般として検索母集団が最初から大きければ大きいほど手数がかかること、検索母集団とお題の母集団が一致しているときは比較的手数が少なくて済む（逆転現象すら起こりうる）というところでしょうか。
過去問の母集団がfrequentとcommonのどちらが近いかと言われるとなかなか難しいので、ひとまず今後の評価ではこれら12通りをやっていくことにします。
セルフハードモード解除
さて、上のアルゴリズムには1つ大きな問題があります。それはセルフハードモードだということです。
Wordleにはハードモードというものがあり、緑や黄色の文字が出てきたら、それをしかるべき場所に使わなくてはならないというモードです。一方で、ハードモードでなければ、すでに緑や黄色の文字が出ていても2手目くらいなら候補を絞るためにあえて全く関係のない語を入れるという戦略も考えられます。しかし、前項のアルゴリズムはシンプルに「候補の中から次の候補を選ぶ」という操作をしているため、いわばセルフハードモード状態になっています。これを解消していきましょう。
public class NotHardModeSolver: MultipleUniverseBase
{
public NotHardModeSolver(IReadOnlySet<string>[] universe) : base(universe) { }
public override string Suggest(IEnumerable<IWordHint> hints, IReadOnlySet<string> candidates)
{
if(candidates.Count >= 9) {
var score = GetCharCount(candidates);
// 緑や灰の文字はできるだけ使わないようにする
foreach(var c in hints.SelectMany(p => p.Characters).Where(p => p.Hint != HintState.ExactPosition || p.Hint != HintState.NotContained).Select(p => p.Character))
score[c] = -1;
var yellow = hints.SelectMany(p => p.Characters.Select((c, i) => (c, i))).Where(p => p.c.Hint == HintState.NotInPosition).ToArray();
return GetWordRanking(WordList.All, score)
.Select(p => (p.word, p.point, ypt: yellow.Select(p1 => p.word[p1.i] == p1.c.Character).Count(p => p))) // ypt: 黄色の文字がその場所で使われている個数
.OrderBy(p => p.ypt) // 黄色の文字がその場所で使われている個数が少ない順で
.ThenByDescending(p => p.point) // pointが高い順
.First().word;
}
return GetWordRanking(candidates, GetCharCount(candidates)).First().word;
}
}
public abstract class MultipleUniverseBase : SolverBase
{
IReadOnlySet<string>[] universe;
public MultipleUniverseBase(IReadOnlySet<string>[] universe)
{
this.universe = universe;
}
public sealed override string Suggest(IEnumerable<IWordHint> hints)
{
IReadOnlySet<string>? candidates = null;
foreach(var univ in universe) {
candidates = Candidate.Nominate(hints, univ);
if(candidates.Count > 0)
break;
}
if(candidates == null || candidates.Count <= 0)
throw new InvalidOperationException();
return Suggest(hints, candidates);
}
public abstract string Suggest(IEnumerable<IWordHint> hints, IReadOnlySet<string> candidates);
}
先ほどのFrequentCharSolverから複数の母集団を指定する機能を分離しました。そのうえで、今回のセルフハードモード解除を実装しています。
その実装にあたっては、候補が9個以上あった場合にこのアルゴリズムが発動するようにしました。9の根拠は希薄ですが、8や10を入れた時より過去問のfrequent→common→allの平均手数が少なくなったからです。
| お題 | 検索母集団 | 最小手数 | 平均手数 | 最大手数 |
| 過去問 | frequent→common→all | 2 | 3.6920 | 7 |
| 過去問 | common→all | 2 | 3.9601 | 7 |
| 過去問 | all | 2 | 4.3587 | 9 |
| frequent | frequent→common→all | 1 | 3.1918 | 6 |
| frequent | common→all | 2 | 3.9408 | 10 |
| frequent | all | 2 | 4.2664 | 10 |
| common | frequent→common→all | 1 | 3.9001 | 10 |
| common | common→all | 2 | 3.8715 | 10 |
| common | all | 2 | 4.2710 | 10 |
| all | frequent→common→all | 1 | 4.6425 | 13 |
| all | common→all | 1 | 4.6295 | 12 |
| all | all | 1 | 4.4554 | 12 |
過去問でも平均0.1手程度下がっており、候補数の多いall-allなどでは特に顕著に下がっています。まあ、all-allは本命ではないですが、十分良い結果と言えるでしょう。
1文字違い対策
さて、Wordleを長くやっていると一度はぶち当たる問題、それは1文字違いです。例えば答えが"hatch"の場合、上のアルゴリズムに沿って解くとaleart→chinsと入力することになり、その時点での候補が以下の通りになります。
batch
match
patch
watch
（この段階ではfrequentリストで検索しているためhatchが含まれていません。）
嫌らしいですねぇ。最初の1文字だけが違い、あとは全部-atchと続きます。このとき順に候補を入れていった場合、答えにたどりつくまでにかかる手数の期待値は2.5となります。一方で、次の一手でbmpwをできるだけ含む単語を1つ入れてやれば、その次の1手で答えにたどり着ける可能性が高まります。
しかしこれには注意しなければいけない要素があります。例えば、catchなど未確定部が確定部の文字を含む場合、cを含む語を用意したところでcatchのcなのかcatchのcなのかを判別することは（緑にならない限り）できません。このような語は除外して消去法で考えるべきでしょう。
類題も見ていきましょう。答えがwhelpの場合、alert→whidsと入力されることになります。この時点での候補は
wheel
whelk
whelm
whelp
となります。1字違いではないですが、この時点ではkmpを含む語を入れたくなりますね。
ここでのポイントは、「候補のすべてに共通する文字を除いた残りの文字をたくさん使う語を選ぶ」にほかなりません。これを実装していきましょう。
public class NotCommonCharSolver : NotHardModeSolver
{
public NotCommonCharSolver(IReadOnlySet<string>[] universe) : base(universe) { }
public override string Suggest(IEnumerable<IWordHint> hints, IReadOnlySet<string> candidates)
{
const int commoncharcnt = 4;
if(candidates.Count >= 4) {
var intersect = candidates.First().ToArray();
foreach(var candidate in candidates.Skip(1)) {
intersect = intersect.Intersect(candidate).ToArray();
if(intersect.Length < commoncharcnt)
break;
}
if(intersect.Length >= commoncharcnt) {
var hintwords = hints.Select(p => p.Word).ToArray();
var excepted = candidates.SelectMany(p => p).Except(intersect).ToArray();
if(excepted.Length > 0) // アナグラムになっていたらこのアルゴリズムは使わない
return GetWordRanking(WordList.All, GetCharCount(excepted)).First().word;
}
}
return base.Suggest(hints, candidates);
}
}
こんな感じでどうでしょう。候補が4つ以上で共通の文字が4個以上あったらこのアルゴリズムが発動し、その共通の文字以外の文字が多く使われている語を探し出してきます。
| お題 | 検索母集団 | 最小手数 | 平均手数 | 最大手数 |
| 過去問 | frequent→common→all | 2 | 3.6703 | 6 |
| 過去問 | common→all | 2 | 3.9094 | 7 |
| 過去問 | all | 2 | 4.3261 | 9 |
| frequent | frequent→common→all | 1 | 3.1905 | 6 |
| frequent | common→all | 2 | 3.9331 | 7 |
| frequent | all | 2 | 4.2664 | 8 |
| common | frequent→common→all | 1 | 3.8935 | 10 |
| common | common→all | 2 | 3.8676 | 8 |
| common | all | 2 | 4.2668 | 9 |
| all | frequent→common→all | 1 | 4.5880 | 13 |
| all | common→all | 1 | 4.5692 |
12 |
| all | all | 1 | 4.4411 |
12 |
平均手数は本当に微減ですが、最大手数が小さくなっているものが多いです。特に今までのアルゴリズムだと1字違いは総当たりになっていたため、単語によってはめちゃめちゃ回数を使っていました。それを底上げすることができたので、最大手数削減という結果につながったのですね。
さらに、なんと過去問の最大手数が6手になりました。すなわち、過去問は全クリできるということになります。素晴らしい。
最強の1手目を求めて
さて、今までは1手目にはあまりこだわらずにソフトを組んできました。今までのアルゴリズムによって自動的に求められる1手目が入力されています。具体的には、検索母集団がfrequentのときはalert、commonのときはarose、allのときはaerosが入っていました。
しかしこれが本当に最良なの？という疑問も同時にあるわけです。特に、1手目は完全にノーヒントで、今までの結果には何も左右されません。「最善」を探すうえでは条件は比較的緩いでしょう。
ということで調べてみましょう。…と言っても時間がかかるので、頻出単語を上から順に適当に漁ってみた際の良さげな単語をすでに拾ってきております。その名もずばりalert、sonde、trailです。
alert
| お題 | 検索母集団 | 最小手数 | 平均手数 | 最大手数 |
| 過去問 | frequent→common→all | 2 | 3.6703 | 6 |
| 過去問 | common→all | 2 | 3.8587 | 7 |
| 過去問 | all | 2 | 4.2138 | 9 |
| frequent | frequent→common→all | 1 | 3.1905 | 6 |
| frequent | common→all | 2 | 3.8069 | 7 |
| frequent | all | 2 | 4.2008 | 8 |
| common | frequent→common→all | 1 | 3.8935 | 10 |
| common | common→all | 1 | 3.8331 | 9 |
| common | all | 1 | 4.2586 |
9 |
| all | frequent→common→all | 1 | 4.5880 | 13 |
| all | common→all | 1 | 4.5538 |
13 |
| all | all | 1 | 4.4369 |
11 |
frequentスタートはもともとalertだったので変わりませんが、それ以外は全体的に手数が少なくなっています。
snode
| お題 | 検索母集団 | 最小手数 | 平均手数 | 最大手数 |
| 過去問 | frequent→common→all | 2 | 3.6630 | 8 |
| 過去問 | common→all | 2 | 3.8587 | 7 |
| 過去問 | all | 2 | 4.2283 | 8 |
| frequent | frequent→common→all | 1 | 3.2561 | 6 |
| frequent | common→all | 2 | 3.8456 | 8 |
| frequent | all | 2 | 4.2291 | 8 |
| common | frequent→common→all | 2 | 3.9068 | 9 |
| common | common→all | 2 | 3.8333 | 7 |
| common | all | 2 | 4.2756 |
9 |
| all | frequent→common→all | 2 | 4.6222 | 11 |
| all | common→all | 2 | 4.5203 |
13 |
| all | all | 2 |
4.4367 |
11 |
過去問のfrequentスタートは平均手数が微減していますが（というかそれで選んできました）最大手数が8手になってしまい、過去問全クリならずです。他のアルゴリズムは全体的に平均手数も最大手数も悪化する傾向にあり、alertと比較してあまり良い手と言えないかもしれません。
trail
| お題 | 検索母集団 | 最小手数 | 平均手数 | 最大手数 |
| 過去問 | frequent→common→all | 2 | 3.6232 | 7 |
| 過去問 | common→all | 2 | 3.8297 | 7 |
| 過去問 | all | 2 | 4.2210 | 9 |
| frequent | frequent→common→all | 1 | 3.1879 | 5 |
| frequent | common→all | 1 | 3.7902 | 7 |
| frequent | all | 1 | 4.1532 | 7 |
| common | frequent→common→all | 1 | 3.8950 | 9 |
| common | common→all | 1 | 3.8351 | 8 |
| common | all | 1 | 4.2522 |
9 |
| all | frequent→common→all | 1 | 4.6203 | 11 |
| all | common→all | 1 | 4.5272 |
12 |
| all | all | 1 |
4.4371 |
12 |
過去問のfrequentスタートは最も平均手数が少ないですが、最大手数は7でやはりはみ出ています。平均手数は全体的にはalertより若干下くらいで、最大手数が増えたことを踏まえるとどっこいどっこいでしょうか。
0 件のコメント:
コメントを投稿