[解決済み] ゲーム「2048」の最適なアルゴリズムとは？

質問

最近、このゲームに出会いました。 2048 . 似たようなタイルを4方向に動かして合体させ、より大きなタイルを作るゲームです。各移動後、新しいタイルは、いずれかの値でランダムな空の位置に表示されます。 2 または 4 . ゲームは、すべてのボックスが埋まり、タイルを結合できる手がなくなると終了します。 2048 .

1つは、目標に到達するためには、きちんとした戦略を立てる必要があることです。そこで、そのためのプログラムを書こうと考えたのです。

現在の私のアルゴリズム

while (!game_over) {
    for each possible move:
        count_no_of_merges_for_2-tiles and 4-tiles
    choose the move with a large number of merges
}

私がやっていることは、どの時点でも、値を持つタイルをマージしようとすることです。 2 と 4 を持つようにしている、つまり 2 と 4 のタイルを、できるだけ少なくする。この方法で試してみると、他のタイルはすべて自動的にマージされるようになり、戦略はうまくいったようです。

でも、実際にこのアルゴリズムを使ってみると、ゲームが終了するまでに4000点くらいしか取れないんです。最大点数（AFAIK）は2万点強で、現在の私のスコアよりはるかに大きいです。これ以上のアルゴリズムはないのでしょうか？

どのように解決するのですか？

を使って、2048のAIを開発しました。 expectimax のアルゴリズムで使われているミニマックス探索の代わりに、@ovolve の最適化を使っている。このAIは単純に、すべての可能な手に対して最大化を行い、次にすべての可能なタイルスポーンに対して期待値（タイルの確率で重み付け、つまり4なら10％、2なら90％）を設定するものです。私の知る限り、期待値最適化を刈り込むことは不可能であり（極めて低い確率の枝を削除する以外）、したがって使用されるアルゴリズムは慎重に最適化されたブルートフォースサーチとなります。

パフォーマンス

デフォルト設定（最大探索深度8）のAIは、盤面の複雑さにもよりますが、一手を実行するのに10msから200msの時間がかかります。テストでは、AIはゲーム全体を通して1秒間に5～10手の平均移動速度を達成しました。探索深度が6手に制限されている場合、AIは1秒間に20手以上を簡単に実行することができます。 見ていて面白い .

AIのスコア性能を評価するために、AIを100回走らせてみました（ブラウザゲームにリモコンで接続）。各タイルについて、そのタイルが少なくとも一度は達成されたゲームの割合を示します。

2048: 100%
4096: 100%
8192: 100%
16384: 94%
32768: 36%

すべてのランの最小スコアは124024、最大スコアは794076であった。中央値は387222点。AIは2048のタイルを獲得できなかったことはなく（つまり100ゲーム中一度も負けたことはない）、実際、このゲームでは 8192 少なくとも1回ずつは

ベストランのスクリーンショットはこちらです。

このゲームは96分間で27830手、つまり1秒間に平均4.8手かかっています。

実装

私のアプローチでは、ボード全体（16エントリ）を単一の64ビット整数（ここでタイルはナイブル、すなわち4ビットチャンク）としてエンコードします。64ビットマシンでは、これはボード全体が単一のマシンレジスタで渡されることを可能にします。

ビットシフト演算は、個々の行と列を抽出するために使用されます。1つの行や列は16ビットの量なので、65536サイズのテーブルで1つの行や列を操作する変換を符号化することができる。例えば、移動は、各移動が1つの行または列にどのように影響するかを記述した、事前に計算された「移動効果テーブル」（例えば、「右に移動」テーブルには、「1122 -> 0023」という項目があり、右に移動すると行 [2,2,4,4] が行 [0,0,4,8] になるという記述があります）への4回の参照として実装されています。

また、採点はテーブル・ルックアップで行われる。テーブルには、すべての可能な行/列で計算されたヒューリスティックスコアが含まれており、ボードの結果としてのスコアは、各行と列のテーブル値の合計にすぎません。

この盤面表現と、移動と得点のテーブル・ルックアップ・アプローチにより、AIは膨大な数のゲーム状態を短時間で探索することができます（私の2011年半ばのノートパソコンの1コアで、1秒間に1000万以上のゲーム状態を探索します）。

expectimax探索自体は再帰的探索としてコード化されており、quot;expectation"ステップ（すべての可能なタイルスポーン位置と値をテストし、それぞれの可能性の確率によって最適化されたスコアに重み付けする）とquot;maximization"ステップ（すべての可能な手をテストし、最高のスコアで1を選択）を交互に実行するようになっています。木探索は、以前に見たことのある位置が見えたら終了する( 転置表 ) 、あらかじめ定義された深さの制限に達したとき、または可能性が極めて低い盤面状態に達したとき (例えば、開始位置から6枚の "4" のタイルを連続で取得することで到達した) に、このような状態になります。典型的な探索深度は4-8手です。

ヒューリスティック

最適化アルゴリズムを有利な位置へ導くために、いくつかのヒューリスティックが使用されます。ヒューリスティックの正確な選択は、アルゴリズムの性能に大きな影響を与えます。様々なヒューリスティックは重み付けされ、ポジション・スコアにまとめられ、与えられたボードのポジションがどれだけ良いかを決定します。最適化検索は、すべての可能なボードポジションの平均スコアを最大化することを目指します。実際のスコアは、ゲームによって示されるように ではない それは（遅延マージが大きな利益を生む可能性がある場合）タイルの合併に有利にあまりにも大きく重み付けされているので、ボードのスコアを計算するために使用されます。

当初、私は2つの非常に単純なヒューリスティックを使いました。開いているマスにボーナスを与えることと、端に大きな値を持つことにボーナスを与えることです。これらのヒューリスティックは非常によく機能し、16384を頻繁に達成しましたが、32768に到達することはありませんでした。

Petr Morávek (@xificurk) は私のAIに2つの新しいヒューリスティックを追加しました。最初のヒューリスティックは、単調でない行と列を持つことに対するペナルティで、ランクが上がるにつれて増加します。これにより、小さな数の単調でない行はスコアに強く影響しませんが、大きな数の単調でない行はスコアに大きく影響するようになりました。2つ目のヒューリスティックは、オープンスペースに加えて、マージ（隣接する同じ値）の可能性の数をカウントした。これらの2つのヒューリスティックは、アルゴリズムを単調な碁盤（マージしやすい）へ、そしてマージの多い碁盤の位置（より大きな効果を得るために可能な限りマージを揃えることを奨励）へと押しやる役割を果たしました。

さらにPetrは、quot;meta-optimization"戦略を用いてヒューリスティック重みの最適化も行いました（quot;meta-optimizationと呼ばれるアルゴリズムを用いています）。 CMA-ES そこで、できるだけ高い平均点が得られるように重みそのものを調整したのです。

この変更の効果は極めて大きい。アルゴリズムは16384タイルを達成するのが13%程度だったのが90%以上になり、32768タイルを達成するのが1/3以上になりました（古いヒューリスティックでは一度も32768タイルを生成しませんでした）。

ヒューリスティックには、まだまだ改善の余地があると思います。このアルゴリズムはまだ最適とは言えませんが、かなり近づいてきていると感じています。

AIが3分の1以上のゲームで32768タイルを達成したことは大きなマイルストーンですが、公式戦で32768を達成した人間がいたら驚きです（つまり、savestatesやundoなどのツールを使わずに）。65536のタイルは手の届くところにあると思います。

AIは自分で試すことができます。コードは以下のサイトで公開されています。 https://github.com/nneonneo/2048-ai .