Wordle ソルバーを作ろう

いま流行りのワードゲーム Wordle のソルバーを作ります。

クエリワードと集合分割

クエリワードによる試行 (guess) は、 解答候補を部分集合に分割すること と見なせます。

いま解答候補が mount, mound, found, sound, round に絞り込めているとします。

クエリワード mount による集合分割

解答候補 mount, mound, found, sound, round に対して mount を試行した結果は、次のように分割されます。

• mount (🟩🟩🟩🟩🟩)
• mound (🟩🟩🟩🟩🟨)
• found, sound, round (⬜🟩🟩🟩🟩)

最良の場合 1 手で正解 (mount) できますが、最悪の場合は候補が 3 つ (found, sound, round) 残ってしまいます。
正解までの平均手数は 2.4 手です。

クエリワード first による集合分割

同じ解答候補に対して first を試行した結果は、次のように分割されます。

• mount (⬜⬜⬜⬜🟩)
• mound (⬜⬜⬜⬜⬜)
• found (🟩⬜⬜⬜⬜)
• sound (🟨⬜⬜⬜⬜)
• round (⬜⬜🟨⬜⬜)

全ての集合分割が要素数 1 となり、正解までの平均手数は 2 手 (最良・最悪手数も 2 手) になります。

最良クエリワードとスコア関数

最良のクエリワードとは何でしょうか。
今回は、解答候補に対して 正解までの平均手数を最小化 するクエリワードを最良と定義します。
先程の例ではクエリワード mount の平均手数が 2.4 手だったのに対して、first の平均手数は 2 手でした。
これは全クエリワードの中で最小であり、この解答候補に対しては first が最良のクエリワードです。

言い換えると、今回のソルバーの目的は 与えられた解答候補 S に対して、平均手数を最小化するクエリワードを求める ことです。

function solve(S: string[]): { word: string; score: number } {
  // bestWord:  平均手数を最小化するクエリワード
  // bestScore: 平均手数
  return { word: bestWord, score: bestScore };
}

// solve(['mount', 'mound', 'found', 'sound', 'round'])
//     => { word: 'first', score: 2.0 }

ゲーム木の探索

Wordle のゲーム木を次のように定義します。

各ノードは解答候補を表します。
子ノードは、クエリワードで遷移する集合分割です。
便宜上、正解したノードは要素数ゼロの空集合φで表しています。

ノード S のスコア(平均手数)は、子ノード s のスコアから再帰的に計算できます。

\mathrm{score}(S) =
\begin{cases}
1 + \min_{w}\sum_{s \in \mathrm{split}(S, w)} \dfrac{\left|s\right|}{\left|S\right|} \mathrm{score}(s) & (|S| > 0) \\
0 & (|S| = 0)
\end{cases}

場合分け上部 (|S| > 0) の min_w の内側は「S からクエリワード w で遷移できる子ノード集合のスコア期待値 (平均手数)」の最小値を表しています。

下記はシンプルな深さ優先探索による再帰的なスコア計算の実装です。

const QueryWordSet = ["aback", "abase", "abate", ...];

function solve(S: string[]): { word: string; score: number } {
  if (S.length === 0) {
    return { word: "", score: 0 };
  }

  let bestScore = Infinity;
  let bestWord = "";
  for (const word of QueryWordSet) {
    let avgMoves = 1;
    for (const subset of split(word, S)) {
      avgMoves += (subset.length / S.length) * solve(subset).score;
    }
    if (avgMoves < bestScore) {
      bestScore = avgMoves;
      bestWord = word;
    }
  }
  return { word: bestWord, score: bestScore };
}

計算量を抑える

上記のコードは全ノード探索 (しらみつぶし法) するもので、ルートノード (全ての解答候補ワードを含む) に対して実行するのは計算量的に困難です。
ゲーム木探索において計算量を減らすいくつかのアプローチがあります。

枝刈りと深さ制限探索

枝刈りとは、探索する必要が無いノードを切り捨てて、有効と見込まれるノードのみに探索を絞る手法です。枝刈りによって主にゲーム木の横幅を減らすことができます。

深さ制限探索は、あらかじめ決めた深さに到達した場合に、そのノードから子ノードへの遷移を打ち切る手法です。主にゲーム木の深さを減らすことができます。

Wordle ではクエリワードの有効性が簡単に判別できる (後述) ため、特に枝刈りが有効です。また、深さは高々 6 程度なので、深さ制限は行わずとも枝刈りパラメータの調整のみでゲーム木を探索しきれます。

枝刈りを実装する

クエリワードの中には明らかに効率の悪いもの、解答候補をほとんど分割できないものが多く存在します。
例えば解答候補 mount, mound, found, sound, round に対してクエリワード apple を試行しても、全ての候補で ⬜⬜⬜⬜⬜ が返ってきます。
そのようなクエリワードに対しては探索を省きたいです。

与えられた解答候補に対して、有効なクエリワードをはじめに 20 ワード程度選び出し、それらについてのみ子ノードの探索を行うことを考えます。

ここで仮にゲーム木を完全 N 分木とすると、解答候補 S を持つノードのスコア (平均手数) は、

\log_{N}{\left|S\right|} + 1

で表せます。
そこで、解答候補 S のスコアを下記で近似します。(Mは適当な定数)

\mathrm{score}(S) \sim M\log{\left|S\right|} + 1

この近似スコアは集合分割の要素数 (|S|) のみに依存しており、子ノードの再帰的な探索をすることなく決定できます。各ノードの計算時に、まず全てのクエリワードに対して子ノードを展開して近似スコアを計算し、上位のみに絞ることで、不要なノードへの遷移を枝刈りできます。

const QueryWordSet = ["aback", "abase", "abate", ...];
const BeamSize = 20;

function approxScore(S: string[], word: string): number {
  let avgMoves = 1;
  for (const subset of split(word, S)) {
    if (subset.length <= 0) continue;
    avgMoves += (subset.length / S.length) * (0.43 * Math.log(subset.length) + 1);
  }
  return avgMoves;
}

function solve(S: string[]): { word: string; score: number } {
  if (S.length === 0) {
    return { word: "", score: 0 };
  }

  const topQueryWords = QueryWordSet.map((word) => ({
    word,
    score: approxScore(S, word),
  }))
    .sort((a, b) => a.score - b.score)
    .slice(0, BeamSize)
    .map((e) => e.word);

  let bestScore = Infinity;
  let bestWord = "";
  for (const word of topQueryWords) {
    let avgMoves = 1;
    for (const subset of split(word, S)) {
      avgMoves += (subset.length / S.length) * solve(subset).score;
    }
    if (avgMoves < bestScore) {
      bestScore = avgMoves;
      bestWord = word;
    }
  }
  return { word: bestWord, score: bestScore };
}

動かしてみる

コード全体はこちら (https://github.com/na-o-ys/wordle-solver/blob/main/src/main.ts) です。
ワードリストはこちら (https://gist.github.com/cfreshman/a03ef2cba789d8cf00c08f767e0fad7b) の 2315 語を用いました。

221 (whack)

blush の時点で平均手数 3.17 と、ほぼ全ての部分集合を確定 1 要素に分割できています。

220 (sugar)

219 (knoll)

初手真っ黒は最も解答候補が絞れない (246 ワード) ですが、3 手で当てられました。

218 (crimp)

初手

初手は trace が最も平均手数が小さく、3.445 のようです。

• trace: 3.445
• slate: 3.445
• crate: 3.446
• crane: 3.449
• least: 3.454
• roast: 3.465
• stare: 3.466

と続きます。3 文字目の a や 5 文字目の e など、多くの共通点が見て取れます。

(おまけ) hard モード

hard モードではクエリワード集合がノードの解答候補と一致します。ノーマルモードよりもゲーム木のサイズは大幅に減少するため、計算が容易になります。
hard モードの初手はノーマルと同じく trace が推薦されます。平均手数は 3.519 と、ほぼノーマルと遜色ない手数で当てられるようです。