Wordle最強AIをつくってあそぼ

やること

みなさんはWordleというゲームをご存知でしょうか。

最近流行りの言語ゲームで、お題となっている5文字の英単語を6回以内に当てるというものです。英単語を入力する(guessする)たびに、お題の単語と同じ場所にある文字は緑色に、場所は違うがお題の単語に含まれている文字は黄色に表示されます。数字当てゲーム「ヌメロン」の単語版といえばわかりやすいでしょうか。

さて、自分は以前、「ヌメロン」で最も効率良い質問をするにはどうすれば良いかについてこの記事で考察したことがあります。ほとんど同じ流れで、Wordle最強（広義）AIを作成していきます。今日始めたばかりのゲームに対する最も効率的な取り組み方を、いきなり機械に教えてもらおうだなんて野暮にもほどがありますが、そうせずにはいられないのが理系の悪いところなのかもしれません。

理論

このゲームにおいて「最強」たるためには、今まで得られた情報を元にして最も「いいguess」をする必要があります。「いいguess」とは大雑把に言うと、返ってくる応答が満遍なく、そしてたくさんありえるようなものです。この散らばり具合は、エントロピー（平均情報量）という量として計算します。n通りの応答がありえて、それぞれの確率をp1~pnとすると、エントロピーHは以下の式によって計算されます。

H = -\sum_{i=1}^np_i\log{p_i}

エントロピーを最大化するguessは、(おおよそ)答えを当てるまでのguess回数の期待値を最小化するようなguessなので、これを指針とすれば数学的に「最強」と言って差し支えないWordle AIが出来上がることとなります。

数学的な詳細は前述のこの記事に任せるとして、早速Pythonで実装していきます。なおここでは、より一般的に、d文字の単語に対するwordleを考えます。

実装

「ヌメロン」からの書き換え箇所は少なく、数十分ほどでそれらしいものが出来ました。

緑(場所の一致)を2、黄(場所は一致しないが含む)を1、白(含まない)を0と符号化し、「2 1 0 1 0」のように返ってきた色たちを入力することでAIのguessを促します。また、使用した辞書に存在する言葉がWordleでは存在しないと判定される可能性もあるため、その場合は「-1」と入力することでスキップし、次善の単語を聞き直すことができます。（答えとなる単語が使用した辞書にない場合は正解に辿り着けませんが、それほどマイナーな単語が答えになることはないと思われます）

さらに、1回目のguessに要する時間があまりに長いので、一度計算して求めたエントロピー最大の単語 "tares" は記憶し、初手は必ずこれを問うことにします。

guessする単語に確信を持った場合（つまり一つまで候補を絞り込んだとき）、AIはguessの前に「I am confident that the answer is : 」と前置きします。

コードはこの記事の最後に載せています。

結果

実際に、Wordleの過去問を使って、挙動を見てみましょう。

※ここからWordleのネタバレ注意

対2022/1/01

対2022/1/02

対2022/1/03

対2022/1/04

ちゃんと作れたようです。10回ほど試しましたが、毎回4回以内のguessで正解にたどり着く事ができています。

考察

AIは耳馴染みのない単語まで駆使して、気配を殺して獲物に迫るハイエナのように、気がついたら答えの目の前に辿り着いています。辞書を参照しているのだから強いのは当たり前だという考え方もできますが、決してそれだけではありません。探索のアルゴリズムが「最強」だから強いのです。

例えば、この対戦

にはAIの特徴がよく出ています。人間なら灰色の多さから探索に失敗してしまったように感じられますが、AIは巧みに重複なく文字を問い続けることで、答えをしれっと一つに絞り込んでいたのです。

さらに、AIが終盤で敢えて全て灰色のguessをするパターンも散見されましたが、これは次に確実に単語を当てるための布石にほかなりません。この戦法は、確定した文字からそれに当てはまる単語を探そうとしてしまう人間には極めて再現が難しいものです。

ただし、人間も捨てたものではありません。勝負強さの面では一日の長があります。人間には一か八かで答えを当てに行くという作戦が取れますが、あくまで期待値の最小化を行動原理とするAIは、「思い切って当てに行く」ことが一切ありません。例えば候補を4つに絞っていても、目を瞑ってどれか一つをguessすることはなく、次の次に確実に当てるために、候補にない単語を平気でguessすることだってあるでしょう。その帰結として、「運よく2回目に当てた」というようなミラクルは、起こしづらくなるのです。

感想と今後の展望

4桁の数字なら全て答えとguessとしてありえた「ヌメロン」と比較すると、答えが単語という制約のあるWordleは、返ってくる応答がeatとbiteよりも細かいことも相まって、一度のguessで得られる情報量が想像以上に多いと言えそうです。機械にやらせて何が楽しいのかという意見ももっともですが、人間の思いもよらない正確さと選択で答えに迫っていく様を眺めるのは、将棋AI同士の神がかった対局を観戦するのにも似て、大変愉快で痛快です。はっきり言って、AIを使ってWordleを遊ぶのは楽しいです。ぜひ体験してください。

最後に、改良のためのメモを残しておきます。

今回は、「辞書に載っている全ての単語が同様に確からしく答えとなる」という仮定のもとでエントロピーを計算しています。どんなマイナーな単語であっても、辞書に載っていれば、立派な解答候補の一つとして平等に扱っているわけです。ところが、実際には平易な単語ほど答えとなる可能性が高いと考えられ、そこに（思いつきやすい単語をguessする確率が高いという点で）人間のアドバンテージがあります。実際普通の人でも四回以内に答えを当てるのは（確実にというのは難しくても）そこまでも大変ではなく、膨大な計算をするAIと人間の差がそこまで生まれていない原因はここにあります。しかしこの問題は、答えとなる単語に対する事前分布を仮定することで解決します。例えばgoogleでのヒット件数などから単語のメジャーさを定量化し、それに比例するような重みを単語に与えて平均情報量の計算に取り入れることで、さらに実戦的なAIができると考えられます。よりシンプルには、guessすることのできる単語の辞書とは別に、比較的平易な単語のみを集めた、答え候補の辞書を用意しておくという方法も取れるでしょうか。

また、勝負強さに関する話題ですが、Wordleでは「6回以内に単語を当てなければ負け」というある種不連続的なルールがあるので、5回目のguessを終えて一つに絞れていなくても、残った候補からどれか一つを選んでguessをする、というのが勝利のためには最適になります。本実装では大抵4回以内に当ててしまうことを踏まえてその場合分けを省略しましたが、「ゲームのルールによって、期待値の最小化が最適戦略ではなくなることがある」ということには留意しておくべきでしょう。

さらに細かい点ですが、このAIには一切ランダム要素が組み込まれていません。最善手を選び続けているわけなので妥当な仕様には違いないのですが、確定的なAIには常に弱点を突かれる恐れがあります。例えば対戦相手がこのAIのことを知っていて、意地悪なお題を選んでくる場合（どんな状況？）、全ての単語が同様に確からしいという想定が崩れるので、性能が落ちるのは不可避です("tares"に強い単語を選ばれる、など)。これは、guessにおいてある程度のランダム性を持たせることで対策できます。具体的には、エントロピーの大きい10個の単語からランダムに一つを選んでguessする、などの修正が考えられます。

単語を一つ思い浮かべ、AIの追及からどれだけ逃げ果せるかを競う「逆Wordle」なんていうゲームも面白いかもしれません。

さて、ここまでお読みいただきありがとうございました。
この記事がみなさんのWordleライフの糧になってくれれば幸いです。

おまけ

3文字で対戦してみた（"dog"を思い浮かべている）

3文字の方がかなり大変みたい。5文字というゲーム設計の絶妙さがわかる。

コード

辞書のテキストファイルを"words.txt"としてダウンロードし、下のコード全体をコピーすればすぐに遊べます。
使用した辞書(再掲)

wordle.py

import math
from collections import defaultdict
import numpy as np
class Wordle:
    def __init__(self,d):
        #単語の長さの設定
        self.digit = d  
        #辞書ファイルの読み込み
        with open("words.txt") as f:
            wordlist = [s.strip() for s in f.readlines()]
        f.close()
        #guessの候補
        self.candidate = [w for w in wordlist if len(w) == d]
        #答えの候補
        self.left = [w for w in wordlist if len(w) == d]
        self.phase = 1
        self.flag = True
    #緑(一致)を2,黄(含む)を1,白(含まない)を0
    def check(self,guess,target):
        rtn = []
        for i in range(self.digit):
            xi = guess[i]
            if xi in target:
                if target[i] == xi:
                    rtn.append(2)
                else:
                    rtn.append(1)
            else:
                rtn.append(0)
        return tuple(rtn)
    #エントロピーの計算
    def entropy(self,guess):
        d = defaultdict(int)
        for target in self.left:
            rtn = self.check(guess,target)
            d[rtn] += 1
        return np.sum(np.vectorize(lambda x:x*math.log2(x))(list(d.values())))
    #エントロピー最大のguessを求める
    def bestentropy(self):
        if self.phase == 1 and self.digit == 5:
            return [("tares",0)]
        if len(self.left) == 1:
            print("I am confident that the answer is : ")
            return [(self.left[0],0)]
        choice = sorted([(word,self.entropy(word)) for word in self.candidate],key=lambda x:x[1])
        return choice[:100]   
    #ありうる候補の絞り込み
    def narrow(self,guess,result):
        self.left = [w for w in self.left if self.check(guess,w) == result]
        return
    def aisturn(self):         
        j = 0
        guesses = self.bestentropy()
        while True:
            print(guesses[j][0])
            result = tuple(map(int,input().split()))
            if result[0] == -1:
                j += 1
            else:
                guess = guesses[j][0]
                break
        if result == tuple([2 for _ in range(self.digit)]):
            print("I identified the answer in "+str(self.phase)+" tries!")
            self.flag = False
            return
        self.narrow(guess,result)
        self.phase += 1
        return
    def playgame(self):
        while self.flag:
            self.aisturn()
            
Wordle(5).playgame()