ゲーム2048に最適なアルゴリズムは何ですか？
はじめに
2048は、ますます大きなタイル値を目指して、それらを結合するためにタイルを移動するエキサイティングなタイルシフトゲームです。
このチュートリアルでは、2048を再生するアルゴリズム、最高のスコアを取得するために、各ステップで作るために最高の動きを決定するのに役立ちます
2048の遊び方
2048のゲームは4×4のボードでプレイされます。, ボード上の各位置は空であってもよいし、タイルが含まれていてもよく、各タイルは、その上に番号を持っています。
開始すると、ボードはランダムな場所に二つのタイルを持ち、それぞれに”2″または”4″があります–それぞれが10％の確率で”4″であるか、そうでなければ”2″で
移動は、すべてのタイルを上、下、左、または右の端に向かってシフトすることによって実行されます。, これを行うと、互いに隣接しており、一緒に移動している同じ値を持つタイルはマージされ、以前の二つの合計に等しい新しいタイルになります。
移動した後、新しいタイルがボード上に配置されます。 これはランダムな場所に配置され、最初のタイルと同じように”2″または”4″になります–”2″時間の90％と”4″時間の10％。
ゲームはその後、可能な動きがなくなるまで続きます。
一般的に、ゲームの目標は、”2048″の値を持つ単一のタイルに到達することです。, しかし、ゲームはここで止まらず、可能な限り最大のタイルを目指して、可能な限りプレイを続けることができます。 理論的には、これは値”131,072″のタイルです。
問題の説明
このゲームを解くことは、ランダムなコンポーネントを持っているので興味深い問題です。 それぞれの新しいタイルが配置される場所だけでなく、それが”2″か”4″かどうかを正しく予測することは不可能です。
そのため、毎回正しくパズルを解くアルゴリズムを持つことは不可能です。, 私たちができる最善のことは、各段階で最高の動きになる可能性があるものを決定し、確率ゲームをプレイすることです。
どの時点でも、可能な動きは四つしかありません。 時には、これらの動きのいくつかは、ボードに影響を与えないので、作る価値がない–例えば、上記のボードでは、すべてのタイルが下端に既にあるので、”ダウン”の動きは影響を与えません。
課題は、これら四つの動きのどれが最良の長期的な結果を持つものになるかを決定することです。,
このアルゴリズムはExpectimaxアルゴリズムに基づいており、それ自体はMinimaxアルゴリズムのバリエーションですが、ツリーを通る可能なルートはそれらが起こる確率で重み付けされています。
基本的には、ゲームをツープレイヤーゲームとして扱います。
- プレイヤーワン-人間のプレイヤー–ボードを四つの方向にシフトすることができます。
- プレイヤーワン–コンピュータプレイヤー–ボード上の空の場所にタイルを置くことができます。
これに基づいて、各移動が起こる確率によって重み付けされた各移動からの結果のツリーを生成することができます。, これにより、どの人間の動きが最良の結果をもたらす可能性があるかを判断するために必要な詳細が得られます。
3.1. ゲームプレイのフローチャート
ゲームプレイの仕組みの一般的な流れ：
“ランダムタイルを追加”プロセスでゲームのランダムな側面をすぐに見ることができます–タイルを追加するためのランダムな正方形を見つけているという事実と、タイルのランダムな値を選択しているという事実の両方です。
私たちの課題は、”次の動きを決定する”ステップで何をすべきかを決定することです。 これがゲームをプレイするアルゴリズムです。,
これの一般的なオーバーフローは一見単純なようです：
私たちがする必要があるのは、可能な動きのそれぞれをシミュレートし、どれが最良の結果を与えるかを決定し、それを使用することだけです。
しておりますので、今の削減のためのアルゴリズムにシミュレー意の移動の発生も得点に結果となります。
これは二部プロセスです。 最初のパスは、移動が可能かどうかを確認することであり、そうでない場合は、”0″のスコアで早期に中止します。, 移動が可能な場合は、実際のアルゴリズムに移動して、これがどれほど良い移動であるかを判断します。
3.2。 次の動きを決定する
これまでのアルゴリズムの重要な部分は、動きをシミュレートすることであり、その重要な部分は、可能な動きごとにスコア これがExpectimaxアルゴリズムの出番です。
を毎がこの辺りですと最高の立地ですから、両手で数段、見る者に与える結果を得ることができました。 人間のプレイヤーにとって、これは”上”、”下”、”左”、”右”の動きのそれぞれを意味します。,
コンピュータプレーヤーの場合、これは可能なすべての空の場所に”2″または”4″のタイルの両方を配置することを意味します：
このアルゴリズムは再帰的であり、各再帰ステップは実際のゲームでの実際の動きから一定の深さである場合にのみ停止します。,現在シミュレートされているボードレイアウトのスコアをシミュレートする
- すべての可能な人間の動きをシミュレートする
- これらのそれぞれについて
- アルゴリズムに戻る
- この人間の移動から計算されたスコアを返す
これが終わったら、計算されたすべてのスコアを合計し、これが現在のゲームボードから作りたいムーブの最終スコアです。, 現在のゲームボードからの可能な移動ごとに四回行うので、私たちは四つのスコアで終わり、それらの最高は作るための動きです。
3.3. ボードポジションのスコアリング
この時点で、残っているのはボードのスコアを計算することだけです。 これはゲームが使用するのと同じ得点ではありませんが、これがプレーを続けるためのポジションがどれほど良いかを考慮する必要があります。
適切な重み付けとともにいくつかの要因を追加することによって、これを達成することができる多くの方法があります。, 例えば、
- 空の場所の数
- 可能なマージの数–すなわち、同じ数が二つの隣接する場所にある回数
- 任意の場所の最大値
- すべての場所の合計
- ボードの単調性–これは、位置の値が単一の方向に増加するように、ボードがどれだけうまく構成されているかです。
擬似コード
アルゴリズムがどのように機能するかがわかったので、これはどのように見えますか？ アルゴリズムをより詳細に記述する擬似コードを調べてみましょう。,
私たちはゲームの実際のプレイには興味がありません、動きを決定するためのアルゴリズムだけですので、そこから始めましょう：
前と同じように、これにより、スタートボードからの可能な動きのそれぞれをシミュレートし、最高のスコアを返すポイントに到達します。 これにより、新しくシミュレートされたボードのスコアを生成する必要が
しばらくすると処理を停止できるように、深さ制限を追加しました。, 再帰アルゴリズムで作業しているので、それを停止する方法が必要です。
これは再帰を与え、特定の数のステップで可能なすべての人間とコンピュータの動きをシミュレートし、どの人間の動きが可能な限り最良の結果を与えるかを決定します。
残っている唯一のものは、任意のボードの位置のための最終的なスコアを動作するようにすることです。 これには完璧なアルゴリズムはなく、異なる要因によって異なる結果が得られます。,
パフォーマンスの最適化
これまでのところ、ゲームを解決しようとするアルゴリズムがありますが、できるだけ効率的ではありません。 ゲームのランダムな性質のために、完全に最適化されたソルバーを持つことは不可能です–プロセスの性質のために、常にあるレベルの繰り返しがあり
私たちは少なくとも私たちがする必要のない作業を減らすために最善を尽くすことができます。,
上記のアルゴリズムでは、ゲームに影響を与えない動きを処理しないことにより、すでに少しの最適化を行っています。 しかし、移動の累積確率を追跡したり、それが低すぎると停止したりするなど、作業を減らすことができる他の方法があります。 これには完璧な解決策を取り除くリスクがありますが、確率がそれほど低い場合、それはほぼ確実に起こりませんとにかく。
作業する深さの制限を動的に決定することもできます。, 上記の擬似コードの上限は3ですが、計算の開始時にボードの形状に基づいて動的に計算できます。 これは、拡張の範囲が少ないボードからの移動が少なくなることを意味します。
さらに、同じボードの位置を複数回再訪することが可能であるため、毎回再計算するのではなく、これらを覚えて、それらの位置のスコアをキャッシュすることができます。, 潜在的に我々は事前にすべての可能なボード位置を生成することができますが、これらの膨大な数があります–281,474,976,710,656 2048までのタイルを使用して異なる可能なボード位置–したがって、これはおそらく実現可能ではありません。
しかし、私たちができる最も重要な最適化は、ボードスコアを生成するためのアルゴリズムを調整することです。 これは、ボードがプレーし続けるためのものであり、我々はこれのために使用する要因と重み付けが直接私たちのアルゴリズムが出て果たしているどれだ,
結論
2048は、解決しようとする非常に面白いゲームです。 それを解決する完璧な方法はありませんが、ゲームを通して可能な限り最良のルートを検索するヒューリスティックを書くことができます。
同じ一般的な原則は、他のプレイヤーがどの程度の確実性で何をするかを予測することができない、チェスなどのツープレイヤーゲームでも機能します。
なぜこれの実装を書いてみて、それがどれだけうまく動作するかを見てみませんか？