2048年ゲームの最適アルゴリズムは?

algorithm logic artificial-intelligence 2048


私は最近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 とマージしようとすることです。つまり、 24 のタイルを最小限にしようとします。この方法で試してみると、他のすべてのタイルが自動的にマージされており、戦略は良いようです。

しかし、実際にこのアルゴリズムを使ってみると、ゲームが終了するまでに4000点くらいしか取れません。AFAIKの最大ポイントは、現在の私のスコアよりもはるかに大きい20,000ポイントをわずかに超えています。上記のアルゴリズムよりも良いアルゴリズムはありますか?




Answer 1 nneonneo


@ovolveのアルゴリズムで使用されるミニマックス検索の代わりに、expectimax最適化を使用して2048 AIを開発しました。 AIは、可能なすべての動きに対して最大化を実行し、次にすべての可能なタイルスポーンに対する期待値を実行します(タイルの確率で重み付けされます。つまり、4の場合は10%、2の場合は90%)。私が知る限り、expectimaxの最適化を排除することは(非常にありそうもないブランチを削除する場合を除いて)不可能なので、使用されるアルゴリズムは慎重に最適化されたブルートフォース検索です。

Performance

デフォルトの構成(最大検索深度8)のAIは、ボード位置の複雑さに応じて、移動を実行するのに10ミリ秒から200ミリ秒かかります。テストでは、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回でもゲームが失われることはありません)。実際、すべての実行で少なくとも8192タイルを達成しました!

ベストランのスクリーンショットです。

32768 tile, score 794076

この対局は96分27830手、1秒間に平均4.8手をかけて行われました。

Implementation

私のアプローチでは、ボード全体(16エントリ)を単一の64ビット整数(タイルはナイブル、つまり4ビットのチャンク)としてエンコードします。64ビットマシンでは、これによりボード全体を1つのマシンレジスタに渡すことができます。

ビットシフト操作は、個々の行と列を抽出するために使用されます。単一の行または列は16ビットの数量であるため、サイズが65536のテーブルは、単一の行または列を操作する変換をエンコードできます。たとえば、移動は、各移動が単一の行または列にどのように影響するかを説明する事前計算された「移動効果テーブル」への4つのルックアップとして実装されます(たとえば、「右移動」テーブルには、「1122-> 0023」というエントリが含まれています。行[2,2,4,4]は、右に移動すると行[0,0,4,8]になります)。

スコアリングはテーブルルックアップを用いても行われる.テーブルには、可能なすべての行列に対して計算されたヒューリスティックなスコアが含まれており、結果として得られるボードのスコアは、各行と列のテーブル値の合計です。

このボード表現は、移動とスコアリングのためのテーブルルックアップアプローチと一緒に、AIが短時間で膨大な数のゲームステートを検索することを可能にします(私の2011年半ばのラップトップの1つのコアで1秒間に1,000,000,000以上のゲームステートを検索します)。

expectimax検索自体は、「期待」ステップ(すべての可能なタイルスポーンの場所と値をテストし、最適化されたスコアに各可能性の確率で重み付け)と「最大化」ステップ(すべての可能な動きをテスト)を交互に繰り返す再帰的検索としてコード化されます。そして、最高のスコアを持つものを選択します)。ツリー検索は、以前に表示された位置(転置テーブルを使用)を検出したとき、事前定義された深さ制限に達したとき、または可能性が非常に低いボード状態に到達したときに終了します(たとえば、6 "4"タイルを取得して到達した場合)開始位置から続けて)。典型的な探索の深さは4-8手です。

Heuristics

最適化アルゴリズムを有利な位置に向けるために、いくつかのヒューリスティックが使用されます。ヒューリスティックの正確な選択は、アルゴリズムのパフォーマンスに大きな影響を与えます。さまざまなヒューリスティックが重み付けされ、位置スコアに結合されます。これにより、特定のボードポジションの「良さ」が決まります。次に、最適化検索は、すべての可能なボード位置の平均スコアを最大化することを目指します。ゲームによって示される実際のスコアはボードスコアの計算には使用されません。これは、タイルをマージするために重み付けが高すぎるためです(マージの遅延により大きなメリットがもたらされる可能性がある場合)。

最初は 2 つの非常にシンプルなヒューリスティックを使いました。これらのヒューリスティックは非常にうまく機能しており、頻繁に16384を達成することができたが、32768に到達することはなかった。

PetrMorávek(@xificurk)が私のAIを採用し、2つの新しいヒューリスティックを追加しました。最初のヒューリスティックは、ランクが増加するにつれて増加する非単調な行と列を持つペナルティであり、小さい数の非単調な行がスコアに強く影響しないことを保証しますが、大きい数の非単調な行はスコアに大きな影響を与えます。 2番目のヒューリスティックは、オープンスペースに加えて、潜在的なマージ(隣接する等しい値)の数をカウントしました。これらの2つのヒューリスティックは、アルゴリズムを単調なボード(マージしやすい)に向けて、および多数のマージがあるボードポジションに向けて(効果を高めるために可能な限りマージを揃えるように促す)のに役立ちました。

さらに、Petrは、「メタ最適化」戦略(CMA-ESと呼ばれるアルゴリズムを使用)を使用してヒューリスティックな重みも最適化しました。この場合、重み自体が調整され、可能な限り高い平均スコアが取得されました。

これらの変更の効果は非常に大きい。アルゴリズムは時間の約13%の16384タイルを達成することから、時間の90%以上のそれを達成するようになり、アルゴリズムは時間の13以上の32768を達成し始めました(古いヒューリスティックスは一度も32768タイルを生成したことがないのに対し)。

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


AIが3分の1以上のゲームで32768を達成したというのは大きな節目である。65536牌は手の届くところにあると思いますよ。

自分でAIを試すことができます。コードはhttps://github.com/nneonneo/2048-aiで入手できます。




Answer 2 ovolve


私は、他の人がこのスレッドで言及したAIプログラムの作成者です。動作中のAIを表示したり、ソースを読んだりできます。

現在、このプログラムは、私のラップトップ上のブラウザでjavascriptを使って実行した場合、約90%の勝率を達成しています(1回の動きにつき約100ミリ秒の思考時間を与えられます)。

ゲームは離散状態空間、完全な情報、チェスやチェッカーなどのターンベースのゲームなので、私はそれらのゲームで機能することが証明されているのと同じ方法、つまりアルファベータ剪定によるミニマックス検索を使用しました。そのアルゴリズムについてはすでに多くの情報があるので、静的評価関数で使用する2つの主なヒューリスティックについて説明します。これは、他の人々がここで表現した直観の多くを形式化しています。

Monotonicity

このヒューリスティックは、タイルの値が右下がりと右下がりの両方の方向に沿って増加または減少していることを確認しようとします。このヒューリスティックな方法だけで、他の多くの人が言及しているように、より価値の高い牌は隅に集まるべきだという直感を捉えています。これは、一般的に、より小さな価値のある牌が孤児になるのを防ぎ、より小さな牌が連鎖して大きな牌の中に埋まっていくことで、盤面を非常に整理した状態に保つことができます。

これは完全に単調なグリッドのスクリーンショットです。他のヒューリスティックを無視して、単調性のみを考慮するようにeval関数を設定してアルゴリズムを実行することで、このような結果が得られました。

A perfectly monotonic 2048 board

Smoothness

上記のヒューリスティックだけでは、隣接するタイルの値が減少している構造を作る傾向がありますが、もちろんマージするためには、隣接するタイルは同じ値である必要があります。したがって、平滑性ヒューリスティックは、隣接するタイル間の値の差を測定するだけで、このカウントを最小化しようとします。

Hacker Newsのコメンターは、グラフ理論の観点からこのアイデアを興味深い形式化しました。

これは、この優れたパロディフォークのおかげで、完全に滑らかなグリッドのスクリーンショットです。

A perfectly smooth 2048 board

無料のタイル

そして最後に、ゲームボードがあまりにも窮屈になるとオプションがすぐになくなることができるので、あまりにも少ない無料のタイルを持っているためのペナルティがあります。

そして、それだけです! これらの基準を最適化しながら対局空間を探索すると、非常に良いパフォーマンスが得られます。明示的にコード化された手筋ではなく、このような一般化されたアプローチを使用することの利点の一つは、アルゴリズムが興味深く予想外の解決策を見つけることができることです。アルゴリズムが実行されているのを見ていると、壁や角に向かって構築している壁や角を突然切り替えるような、驚くような、しかし効果的な動きをすることがよくあります。

Edit:

このアプローチの威力を実証してみましょう。タイルの値をアンキャップして(そうすれば2048に達した後も続けられる)、8回の試行の後の最良の結果がこれです。

4096

そう、2048と並んで4096です。)つまり、同じ盤面で3回も2048を達成したということだ。




Answer 3 Ronenz


ハードコードされたインテリジェンス(つまり、ヒューリスティックス、スコアリング関数など)を含まないこのゲームのAIのアイデアに興味を持ちました。 AIはゲームルールのみを「認識」し、ゲームプレイを「把握」する必要があります。これは、ほとんどのAI(このスレッドのAIと同様)とは対照的です。この場合、ゲームプレイは、本質的に、ゲームに対する人間の理解を表すスコアリング関数によって力ずくで操作されます。

AIアルゴリズム

シンプルでありながら驚くほど優れたプレーアルゴリズムを見つけました。特定のボードの次の動きを判別するために、AI はゲームが終わるまでランダムな動きを使用してメモリ内でゲームをプレイします。これは、ゲーム終了時のスコアを追跡しながら数回行われます。次に、開始移動ごとの平均終了スコアが計算されます。最も高い平均エンドスコアを持つ最初の手が次の手として選択されます。

1手あたり100回(メモリーゲームの場合)の実行で、AIは80%の2048タイルと50%の4096タイルを達成します。10000回の実行で2048タイルが100%、4096タイルが70%、8192タイルが約1%となります。

アクションで見る

ここでは、最高の達成スコアを表示しています。

best score

このアルゴリズムについての興味深い事実は、ランダムプレイのゲームは当然のことながら非常に悪いのですが、最高の(または最低の)手を選択すると非常に良いゲームプレイになるということです。典型的なAIゲームは70000ポイントに達し、最後の3000手に達することができますが、任意の位置からのインメモリランダムプレイゲームは、死ぬ前に約40手の余分な手で平均340ポイントの追加ポイントをもたらします。(これは、AIを実行してデバッグコンソールを開くことで確認することができます)。

このグラフは、この点を示しています。青い線は、各移動後のボードのスコアを示しています。赤い線は、その位置からのアルゴリズムの最高のランダムラン終了ゲームのスコアを示しています。本質的に、赤の値は青の値を上向きに「引き」、アルゴリズムの最良の推測であるためです。赤い線が各点で青い線のほんの少し上にあるのは興味深いことですが、青い線はますます増え続けています。

scoring graph

アルゴリズムが、それを生み出す手を選択するために、実際に良いゲームプレイを予見する必要がないというのは、非常に驚くべきことだと思います。

後で検索すると、このアルゴリズムが純粋なモンテカルロツリー検索アルゴリズムに分類される可能性があることがわかりました。

実装とリンク

まず、ここで実際に動作するJavaScriptバージョンを作成しました。このバージョンでは、何百回もの実行を適切な時間で実行できます。追加情報については、コンソールを開いてください。(ソース

その後、さらにいくつかを試すために、@ nneonneoの高度に最適化されたインフラストラクチャを使用し、自分のバージョンをC ++に実装しました。このバージョンでは、1回の移動で最大100000回実行でき、忍耐力がある場合は1000000回まで実行できます。提供される構築手順。コンソールで実行され、Webバージョンを再生するためのリモコンも備えています。(ソース

Results

驚いたことに、実行回数を増やしても、ゲームプレイは大幅には改善されません。この戦略には、4096タイルとすべての小さいタイルで約80000ポイントの制限があり、8192タイルの達成に非常に近いようです。100から100000までのランの数を増やすと増加オッズ(5%から40%)、このスコアの限界になってそれを突破しないのです。

重要な位置の近くで1000000への一時的な増加との10000の操業を実行することは129892および8192タイルの最大スコアを達成する回の1%以下この障壁を壊すことをどうにかして。

Improvements

このアルゴリズムを実装した後、私は最小または最大スコア、または最小、最大、および平均の組み合わせの使用を含む多くの改善を試みました。私はまた、深度を使用してみました:移動ごとにKランを試行する代わりに、指定された長さ(「上、上、左」など)の移動リストごとにK移動を試行し、最高スコアの移動リストの最初の移動を選択しました。

その後、私は、与えられた手のリストの後に手を打つことができる条件付き確率を考慮したスコアリングツリーを実装しました。

しかし、これらのアイデアはどれも単純な最初のアイデアに比べて、実際には何のメリットもありませんでした。私は、これらのアイデアのためのコードをC++のコードでコメントアウトしたままにしておきました。

私は「ディープサーチ」のメカニズムを追加しました。これにより、時間の短縮につながりました。

他にもAIのドメイン非依存性を維持する改善案があれば教えて欲しいですね。

2048のバリアントとクローン

面白くするために、AIをブックマークレットとして実装し、ゲームのコントロールにフックしました。これにより、AIは元のゲームとその多くのバリアントで動作することができます。

これは、AIのドメイン非依存性に起因する可能性がある。変種の中には、ヘキサゴナルクローンのようにかなり特徴的なものもあります。




Answer 4 Daren


編集:これは単純なアルゴリズムであり、人間の意識的な思考プロセスをモデル化しており、AIと比較して非常に弱い結果を取得します。回答のタイムラインの早い段階で提出されました。

私はアルゴリズムを洗練させ、ゲームを倒しました それは終わりに近い単純な不運のために失敗する可能性があります(あなたは決してすべきではない下に移動することを余儀なくされ、あなたの最高位があるはずの場所にタイルが表示されます。ただ、左に移動してもパターンを壊さないように、上の行を埋めるようにしてください)が、基本的には固定部分と遊ぶためのモバイル部分を持っていることになってしまいます。これはあなたの目的です。

Ready to finish

デフォルトで選んだモデルです。

1024 512 256 128
  8   16  32  64
  4   2   x   x
  x   x   x   x

選ばれた角は任意で、基本的に1キー(禁手)は絶対に押さないし、押されたらまた逆を押して修正しようとする。将来の牌については、モデルは常に次のランダムな牌が2であることを期待し、現在のモデルとは反対側に現れる(1列目が不完全な間は右下の角に、1列目が不完全な間は左下の角に、1列目が不完全な間は左下の角に、1列目が不完全な間は右下の角に、1列目が不完全な間は左下の角に)。

アルゴリズムはこうだ。80%前後の勝率(もっと「プロ」のAI技術を使えば必ず勝てそうな気がしますが、これはよくわかりません。)

initiateModel();

while(!game_over)
{    
    checkCornerChosen(); // Unimplemented, but it might be an improvement to change the reference point

    for each 3 possible move:
        evaluateResult()
    execute move with best score
    if no move is available, execute forbidden move and undo, recalculateModel()
 }

 evaluateResult() {
     calculatesBestCurrentModel()
     calculates distance to chosen model
     stores result
 }

 calculateBestCurrentModel() {
      (according to the current highest tile acheived and their distribution)
  }

不足しているステップについてのいくつかの指摘。これをmodel change

想定していたモデルに近づくという運の良さでモデルが変わった。AIが実現しようとしているモデルは

 512 256 128  x
  X   X   x   x
  X   X   x   x
  x   x   x   x

そして、そこにたどり着くまでの連鎖が

 512 256  64  O
  8   16  32  O
  4   x   x   x
  x   x   x   x

O は、禁じられた空間を表現し...

だから、それは右を押して、もう一度右を押して、その後(4が作成した場所に応じて右またはトップ)、それが取得するまでチェーンを完了するために進みます。

Chain completed

これでモデルとチェーンは元に戻りましたね。

 512 256 128  64
  4   8  16   32
  X   X   x   x
  x   x   x   x

2番目のポインター、それは運が悪く、本命スポットを取られてしまいました。失敗する可能性が高いですが、達成することができます。

Enter image description here

ここにモデルとチェーンがあります。

  O 1024 512 256
  O   O   O  128
  8  16   32  64
  4   x   x   x

それが128に達することを管理するとき、それは全体の行が再び得られます。

  O 1024 512 256
  x   x  128 128
  x   x   x   x
  x   x   x   x



Answer 5 Nicola Pezzotti


ブログの投稿内容をここにコピーします


私が提案するソリューションは非常にシンプルで簡単に実装できます。しかし、それは131040のスコアに達している。アルゴリズムの性能のいくつかのベンチマークが提示されています。

Score

Algorithm

ヒューリスティックスコアリングアルゴリズム

私のアルゴリズムがベースとしている前提は単純です:より高いスコアを達成したければ、ボードは可能な限り整頓されていなければなりません。特に、最適な設定は、タイルの値が線形で単調に減少する順序によって与えられます。この直感は、タイルの値の上限も与えてくれます。sここで、nは盤面上のタイルの数である。

(必要に応じて2牌ではなく4牌をランダムに発生させれば131072牌に到達する可能性がある)

ボードの整理方法として考えられるのは、以下の画像のような2つです。

enter image description here

タイルの順序を単調に減少させるために、スコアsiは、ボード上の線形化された値の合計に、共通の比率r <1の幾何学的シーケンスの値を掛けたものとして計算されます。

s

s

複数の線形パスを一度に評価することができ、最終的なスコアは任意のパスの最大スコアとなります。

決定ルール

実装されている決定ルールはかなりスマートではありませんが、Pythonでのコードを紹介します。

@staticmethod
def nextMove(board,recursion_depth=3):
    m,s = AI.nextMoveRecur(board,recursion_depth,recursion_depth)
    return m

@staticmethod
def nextMoveRecur(board,depth,maxDepth,base=0.9):
    bestScore = -1.
    bestMove = 0
    for m in range(1,5):
        if(board.validMove(m)):
            newBoard = copy.deepcopy(board)
            newBoard.move(m,add_tile=True)

            score = AI.evaluate(newBoard)
            if depth != 0:
                my_m,my_s = AI.nextMoveRecur(newBoard,depth-1,maxDepth)
                score += my_s*pow(base,maxDepth-depth+1)

            if(score > bestScore):
                bestMove = m
                bestScore = score
    return (bestMove,bestScore);

minmaxまたはExpectiminimaxの実装は確かにアルゴリズムを改善するでしょう。明らかに、より洗練された決定規則はアルゴリズムを遅くし、それが実装されるのに時間がかかるでしょう。(期待しています)

Benchmark

  • T1-121のテスト-8つの異なるパス-r=0.125
  • T2-122のテスト-8つの異なるパス-r=0.25
  • T3-132回の試験-8つの異なるパス-r=0.5
  • T4-211のテスト-2つの異なるパス-r=0.125
  • T5-274回の試験-2つの異なるパス-r=0.25
  • T6-211回の検定-2つの異なるパス-r=0.5

enter image description here enter image description here enter image description here enter image description here

T2の場合、10回に4回のテストで平均スコアが4096の牌が生成されます。s42000

Code

コードは次のリンクのGiHubにあります:https : //github.com/Nicola17/term2048-AI これはterm2048に基づいており、Pythonで書かれています。より効率的なバージョンをC ++にできるだけ早く実装します。