2048ソルバーのしくみ

盤面の下にあるヒントと自動プレイのボタンは、決まりきった助言を返しているわけではありません。今の盤面そのものに対して、ブラウザの中で本物の探索を行い、最も評価の高い手を返しています。ヒントは盤面の上に矢印を表示し、自動プレイはゲームが終わるまでその手を打ち続けます。サーバーには何も送信されません。

まっさらな盤面からこの探索だけに任せると、91.4%のゲームで2048のタイルに到達します。ここでは、どうやってそこまでたどり着くのかを説明します。

チェスのアルゴリズムではなく、エクスペクティマックスを使う理由

ゲーム木を扱う定番の道具はミニマックスです。相手が最悪の応手を選ぶと仮定して、それに備えて計画します。しかし2048には相手がいません。あるのはランダムに現れるタイルで、この違いはとても大きな意味を持ちます。

ミニマックスで考えるプレイヤーは、新しいタイルを悪意のあるものとみなし、4が必ず最悪のマスに現れると仮定します。その結果、30回に1回起きるかどうかの盤面への備えに計算をすべて費やし、疑り深く守りに偏ったプレイになります。エクスペクティマックスは代わりに、実際に起こりうるすべての出現を、それぞれの起こりやすさで重みづけして平均を取ります。悪夢ではなく確率に従って打つわけで、ランダムさに悪意がない以上、これが正しいモデルです。

そのため探索は2種類のノードを交互にたどります。プレイヤーノードでは4方向すべてを試し、いちばんよい結果を残します。確率ノードでは、空いているすべてのマスに重み0.9で2を、重み0.1で4を置き、それぞれを評価して平均します。これはゲーム自体がタイルを出すときと同じ90対10の割合です。

ソルバーが考える「よい盤面」

ゲームの終わりまで木を探索することはできないので、探索のいちばん下でソルバーは盤面を4つの指標で採点し、次の重みで足し合わせます。

4つのうち3つは、人がよく口にするアドバイスを計算式にしただけのものです。マスを空けておく、並びを整える、大きなタイルを角に置く。そのアドバイスを判断に変えるのが重みです。探索は、空きマスが十分に増えるなら角の位置が多少悪くなることを喜んで受け入れます。そしてこの取引を、人はたいてい逆向きに間違えます。

どの項目も、タイルの数字そのものではなく、その2を底とする対数を使います。そのため2から4への差は、1024から2048への差と同じだけ数えられます。そうしなければ、盤面でいちばん大きなタイルがほかのすべてをかき消してしまいます。

計算の手間を、必要な場面に回す

確率ノードは、空きマスひとつごとに、しかも2通りずつ枝分かれします。空きマスが10ある広い盤面ではどの段にも20本の枝があり、空きマスが3つしかない詰まった盤面なら6本です。両方を同じ深さまで探索するのはあべこべです。広い盤面は生き残るのはたやすいのに探索には手間がかかり、詰まった盤面はその逆だからです。

そこで、深さは盤面に合わせて変わります。

広い盤面はさっと眺め、窮屈になったらぐっと慎重になる。強いプレイヤーと同じ感覚を、正確に当てはめたものです。これによって、ゲームのどの段階でも、クリックしてから矢印が出るまでの待ち時間を快適な範囲に収めています。

実際の強さ

500局の完全なゲームで、2048に到達したのは91.4%、スコアの中央値は37,004、ゲームの長さの中央値は1,943手でした。比較対象つきの全結果で、これらの数字を文脈の中で確かめられます。

これが最先端の2048ボットではないことは、はっきりさせておく価値があります。公開されているソルバーは、ビットボード表現、事前計算した移動表、置換表のキャッシュを使ってずっと深く探索し、32768に到達します。このソルバーはブラウザのメインスレッド上で普通の配列を使って動き、手と手のあいだにキャッシュを持たず、ページがもたつかないよう4手先までに制限されています。記録を出すためではなく、「ここで何をすべきか？」に一瞬で感じられる速さで答えるために作られています。

ゲームを台なしにしない使い方

ヒントのいちばん役に立つ使い方は、それに従うことではありません。まず自分の手を決め、そのあとでヒントを押しましょう。矢印が一致したなら、新しく学ぶことはありません。でも食い違ったなら、自分が読み違えている盤面を見つけたことになり、上達の種はまさにそこにあります。

自動プレイは、救済策としてよりもお手本として使うほうが役に立ちます。自分が難しいと感じた局面から動かして、どの方向を守り、どの合体をあえて取らないかを観察しましょう。矢印キーを押せば、いつでもすぐに操作を取り戻せます。

ソルバーは依存関係のないJavaScriptでおよそ250行、/js/ai.jsにただのファイルとして置かれています。ここに書いたことを確かめたければ、ブラウザのソース表示でそのまま読めます。