AIが一手を指す前に、15万語という干し草の山の中から自分の手を見つけ出し、そして探すのをやめなければなりません。
英語で執筆・編集されました。この日本語版は機械翻訳によって作成されたものです。正確さが重要な箇所については、英語の原文が正式なものです。 英語の原文を読む →
人にWordChessのタイルをひとそろい渡して「良い単語を置いて」と言えば、その人は自分でも気づかないうちに問題を絞り込みます。コンピューターにはそのような直感がありません。25×25の盤面で、100枚そろった自分専用のタイルセットを持つコンピューターは、148,941語の辞書語のほぼどれでも試すことができ、しかもそれぞれの単語を何千通りもの合法な座標と向きに置けます。さらに厄介なことに、ある配置が合法になるのは、新たに置くすべての文字が、盤上にすでにある文字と交差する箇所でも実在の単語を完成させる場合に限られます。単語の数に配置の数を掛け、さらにその交差の制約を掛け合わせれば、人間であれシリコンであれ、どんなプレイヤーにも全部を列挙して順位づけすることはできない探索空間ができあがります。
だからこそ、本格的な単語ゲームのエンジンは、オープンソースの標準的な実装であるQuackleも含めて、決して辞書を総当たりしません。4 Steven Gordonが1994年に考案したGADDAG構造、そしてそれ以前のDAWGは、プログラムが盤上にすでにあるタイルから外側へ単語を伸ばしながら交差をその都度確認できるようにし、不合法な枝は採点されてから捨てられるのではなく、早い段階で刈り取られます。1 課題は「すべての単語を列挙すること」ではありません。「合法になりうる手だけを生成し、それを高速に行うこと」なのです。
無駄のない生成器であっても、深く評価しきれないほど多くの候補手を返すので、2つ目の問題は時間です。トップクラスの人間を初めて打ち負かしたプログラムであるBrian SheppardのMavenは、まさにこの問題に直面し、2段階で答えを出しました。まず高速なヒューリスティックが生の手をおおよその質の順に並べ、最も有望な少数の候補だけを、ゲームを何度も先までシミュレートして、どの候補が実際に最も良い結果を出すかを確かめることで入念に検討するのです。2 ほかのゲームでは同じ発想が別の名前で知られています。バックギャモンのロールアウト、囲碁プログラムのプレイアウトです。Mavenではそれをシミュレーションと呼んでいます。
WordChessも同じ精神で、ただしより厳しい制約のもとで動きます。1手あたりの探索時間の予算が固定されているのです。予算が尽きると、AIはその時点までに見つけた最良の単語に決めます。これは技術者たちが悔やんでいる妥協ではなく、設計そのものです。いつまでも考え続けるプレイヤーは、より強い相手ではなく、より遅い相手にすぎません。時計は、人間が本能的にしていること、つまり証明可能な最善手ではなく明らかに良い手で手を打つことを、機械にも強いるのです。
辞書を知っているのは簡単な部分です。難しいのは、いつ辞書の探索をやめるかを知ることです。
ゲームAIを易しくする安易な方法は、ランダムに愚かにすること、つまり明らかに見えていた手をしくじらせることです。プレイヤーはそれに気づき、腹を立てます。デザイナーのSid Meierは、コンピューターがプレイヤーとほぼ同じくらい巧みに悪用できたため、Civilizationから同盟の機能を削ったことでよく引き合いに出されます。AI対戦相手の設計に関するある解説が引用するMeier自身の言葉によれば、その効果は「コンピューターがズルをしているから勝てないのだという感覚をゲーマーに残してしまう」というものでした。3 不正のように感じられる難易度はゲームを台無しにします。だからこそ、動的難易度調整に関する研究文献は、AIに何を見ることを許すかではなく、AIが何をできるかを調整することに取り組んでいるのです。5
WordChessは4つの段階を、人間にも理解できる軸に沿って調整しており、AIに隠された情報を与えることは決してありません。段階ごとに異なるのは、どれだけ長く探索できるか、語彙が珍しい辞書のどこまで深く届くか、そしてどの語長帯を好むかです。易しい相手は、もっともらしく弱い単語、つまり実在し、筋が通っていて、短い単語を置き、でたらめなものは置きません。グランドマスターは難解な語彙のすべてをHard(難しい)の段階と共有しており、それを掘り起こす時間は最も多く持っています。プレイヤーが負ける相手は、より豊かな語彙とより鋭い読みを持っているように見える何かであり、それはまさにその通りのものなのです。
| 段階 | 語彙の範囲 | 探索予算 | 語長の傾向 |
|---|---|---|---|
| Easy(易しい) | 一般語のみ | 最短 | 短い |
| Normal(普通) | 一般語+中程度+珍しい語の半分 | 短い | 混合 |
| Hard(難しい) | 全部 | 長い | やや長い |
| Grandmaster(グランドマスター) | 全部 | 最長 | 制限なし |
計算機は毎回同じ答えを返しますが、対戦相手はあなたを驚かせます。WordChessは手の選択に、意図的にランダム化した段階を加えています。そのため、ほぼ同等の手がいつも同じように決着するわけではなく、AIが毎回同じ単語を繰り返し置くこともありません。段階ごとの語彙の上限と組み合わさることで、その効果は多様性となります。盤の向こうに誰かが座って選択をしていて、そのうちのいくつかはあなた自身も選んだかもしれない、という感覚です。
それこそが、このささやかな技の妙です。信じられる対戦相手には、強さと同じくらい抑制が必要です。単に良いだけの単語を置く気構え、点数を取り残す気構え、そして勝ち取ったと感じられるかたちで負けてくれる気構えです。この機械にとって技術的に最も難しい問題は、干し草の山を探すことでした。最も繊細な問題は、いつ探すのをやめるか、何を知っておくか、そしてどれだけ手加減するかを学ぶことだったのです。