私は最近このゲームに出会った2048類似のタイルを 4 つの方向のいずれかに移動して結合し、「より大きな」タイルを作成します。移動するたびに、 または の値を持つ新しいタイルがランダムに空き位置に表示されます。すべてのボックスが埋まり、タイルを結合できる移動がなくなる2か4、 の値を持つタイルを作成すると、ゲームは終了します2048。
まず、目標を達成するには、明確に定義された戦略に従う必要があります。そこで、そのためのプログラムを書こうと考えました。
私の現在のアルゴリズム:
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 ポイントしか獲得できません。私の知る限り、最大ポイントは 20,000 ポイントをわずかに超える程度で、現在のスコアよりはるかに大きいです。上記よりも優れたアルゴリズムはありますか?
ベストアンサー1
私は、@ovolve のアルゴリズムで使用されるミニマックス検索ではなく、期待値最大化最適化を使用して 2048 AI を開発しました。AI は、すべての可能な動きに対して単純に最大化を実行し、次にすべての可能なタイルの発生に対して期待値を実行します (タイルの確率によって重み付けされます。つまり、4 の場合は 10%、2 の場合は 90%)。私の知る限り、期待値最大化最適化を刈り込むことは不可能です (非常に可能性が低い分岐を削除する場合を除く)。そのため、使用されるアルゴリズムは慎重に最適化されたブルート フォース検索です。
パフォーマンス
AIのデフォルト設定（最大探索深度8）では、盤面の複雑さに応じて、10msから200msの間で移動を実行します。テストでは、AIはゲーム全体を通して1秒あたり5〜10手の平均移動速度を達成しました。探索深度を6手に制限すると、AIは1秒あたり20手以上を簡単に実行できるため、面白い。
AI のスコア パフォーマンスを評価するために、AI を 100 回実行しました (リモート コントロール経由でブラウザ ゲームに接続)。各タイルについて、そのタイルが少なくとも 1 回達成されたゲームの割合は次のとおりです。
2048: 100%
4096: 100%
8192: 100%
16384: 94%
32768: 36%
すべての実行での最小スコアは 124024 で、達成された最大スコアは 794076 でした。中央値は 387222 です。AI は 2048 タイルの取得に失敗したことはありません (したがって、100 ゲーム中 1 回もゲームに負けたことはありません)。実際、すべての実行で少なくとも 1 回は8192タイルを取得しました。
最高のランのスクリーンショットは次のとおりです。
このゲームは 96 分間で 27,830 手、つまり 1 秒あたり平均 4.8 手を要しました。
実装
私のアプローチでは、ボード全体 (16 エントリ) を 1 つの 64 ビット整数 (タイルはニブル、つまり 4 ビットのチャンク) としてエンコードします。これにより、64 ビット マシンでは、ボード全体を 1 つのマシン レジスタで渡すことができます。
ビット シフト操作は、個々の行と列を抽出するために使用されます。1 つの行または列は 16 ビットの量であるため、サイズが 65536 のテーブルは、1 つの行または列で動作する変換をエンコードできます。たとえば、移動は、各移動が 1 つの行または列にどのように影響するかを説明する、事前に計算された「移動効果テーブル」への 4 つの参照として実装されます (たとえば、「右に移動」テーブルには、行 [2,2,4,4] が右に移動すると行 [0,0,4,8] になる方法を説明するエントリ「1122 -> 0023」が含まれます)。
スコアリングもテーブル ルックアップを使用して行われます。テーブルには、すべての可能な行/列で計算されたヒューリスティック スコアが含まれており、ボードの結果スコアは、各行と各列のテーブル値の合計になります。
このボード表現と、移動とスコアリングのためのテーブル検索アプローチにより、AI は短時間で膨大な数のゲーム状態を検索できます (2011 年半ばのラップトップの 1 つのコアで 1 秒あたり 10,000,000 を超えるゲーム状態を検索できます)。
期待最大探索自体は、再帰探索としてコード化されており、「期待」ステップ（すべての可能なタイルの出現場所と値をテストし、それぞれの可能性の確率によって最適化されたスコアに重み付けする）と「最大化」ステップ（すべての可能な動きをテストし、最高のスコアを持つものを選択する）を交互に実行する。ツリー探索は、以前に見た位置（転置表）、事前に定義された深さの制限に達したとき、または非常にありそうもないボード状態に達したとき（開始位置から 6 つの「4」タイルを連続して取得することによって到達したなど）に、検索が終了します。一般的な検索深さは 4 ～ 8 手です。
経験則
最適化アルゴリズムを有利な位置に導くために、いくつかのヒューリスティックが使用されます。ヒューリスティックの正確な選択は、アルゴリズムのパフォーマンスに大きく影響します。さまざまなヒューリスティックが重み付けされ、位置スコアに結合され、特定のボード位置がどれだけ「優れている」かが決定されます。最適化検索は、すべての可能なボード位置の平均スコアを最大化することを目指します。ゲームによって表示される実際のスコアは、ボードスコアの計算には使用されません。これは、タイルのマージに過度に重み付けされているためです (マージを遅らせると大きな利益が得られる場合があります)。
最初は、開いた四角形と端に大きな値がある場合に「ボーナス」を与えるという、非常に単純な 2 つのヒューリスティックを使用しました。これらのヒューリスティックは非常にうまく機能し、16384 を頻繁に達成しましたが、32768 に到達することはありませんでした。
Petr Morávek (@xificurk) は私の AI を採用し、2 つの新しいヒューリスティックを追加しました。最初のヒューリスティックは、ランクが上がるにつれて増加する非単調な行と列に対するペナルティで、小さな数字の非単調な行はスコアに大きく影響しませんが、大きな数字の非単調な行はスコアを大幅に下げます。2 番目のヒューリスティックは、空きスペースに加えて、潜在的なマージ (隣接する同じ値) の数をカウントします。これら 2 つのヒューリスティックは、アルゴリズムを単調なボード (マージが簡単) と、マージの多いボードの位置 (より大きな効果を得るために、可能な限りマージを揃えるように促す) に向ける役割を果たしました。
さらに、ペトルは「メタ最適化」戦略（と呼ばれるアルゴリズムを使用）を使用してヒューリスティックな重みを最適化しました。CMA-ES）、ここでは、可能な限り最高の平均スコアが得られるように重み自体が調整されました。
これらの変更の効果は極めて重要です。アルゴリズムは、16384 タイルを約 13% の時間で達成することから、90% を超える時間で達成することになり、アルゴリズムは 32768 タイルを 1/3 の時間で達成するようになりました (一方、古いヒューリスティックでは 32768 タイルは一度も生成されませんでした)。
ヒューリスティックにはまだ改善の余地があると思います。このアルゴリズムはまだ「最適」ではありませんが、かなり近づいているように感じます。
AI がゲームの 3 分の 1 以上で 32768 タイルを達成するというのは、大きなマイルストーンです。公式ゲームで (つまり、セーブステートや元に戻すなどのツールを使用せずに) 32768 を達成した人間のプレイヤーがいると聞いたら驚きます。65536 タイルは手の届くところにあると思います。
AIを自分で試すことができます。コードは次の場所にあります。https://github.com/nneonneo/2048-ai。