ゲーム2048の最適なアルゴリズムは何ですか？

1. 序章

2048はエキサイティングなタイルシフトゲームで、タイルを動かして組み合わせ、タイルの値をますます大きくすることを目指しています。

このチュートリアルでは、 2048を再生するアルゴリズムを調査します。これは、最高のスコアを取得するために各ステップで行う最適な動きを決定するのに役立ちます。

2. 2048の遊び方

2048のゲームは4×4のボードでプレイされます。ボードの各位置は空であるかタイルを含む可能性があり、各タイルには番号が付いています。

開始すると、ボードにはランダムな場所に2つのタイルがあり、それぞれに「2」または「4」があります。それぞれに「4」であるという独立した10% cの可能性があります。は「2」です。

移動は、すべてのタイルを1つのエッジに向かってシフトすることによって実行されます –上、下、左、または右。これを行うと、互いに隣接し、一緒に移動している同じ値のタイルがマージされ、前の2つの合計に等しい新しいタイルになります。

移動後、新しいタイルがボードに配置されます。これはランダムな場所に配置され、と同じように「2」または「4」になります。初期タイル–「2」90 % o fの時間、「4」10% of時間。

その後、ゲームはそれ以上の動きがなくなるまで続きます。

一般に、ゲームの目標は、値が「2048」の単一のタイルに到達することです。ただし、ゲームはここで止まらず、可能な限り最大のタイルを目指して、可能な限りプレイを続けることができます。理論的には、これは値が「131,072」のタイルです。

3. 問題の説明

このゲームを解くのはランダムな要素があるので興味深い問題です。新しいタイルが配置される場所だけでなく、それが「2」か「4」かを正確に予測することは不可能です。

そのため、毎回パズルを正しく解くアルゴリズムを持つことは不可能です。私たちができる最善のことは、各段階で何が最良の動きである可能性が高いかを判断し、確率ゲームをプレイすることです。

いつでも、私たちが行うことができる可能な動きは4つだけです。場合によっては、これらの動きの一部はボードに影響を与えないため、作成する価値がありません。たとえば、上記のボードでは、すべてのタイルがすでに下端にあるため、「下」の動きは影響を与えません。

次に、これら4つの動きのどれが、長期的に最良の結果をもたらすかを判断することが課題になります。

私たちのアルゴリズムは、 Expectimax アルゴリズムに基づいています。これは、それ自体が Minimax アルゴリズムのバリエーションですが、ツリーを通る可能なルートは、それらが発生する確率によって重み付けされます。

基本的に、このゲームは2人用ゲームとして扱います。

プレイヤー1–人間のプレイヤー–はボードを4つの方向のいずれかにシフトできます
プレーヤー2–コンピュータープレーヤー–は、ボード上の空の場所にタイルを置くことができます

これに基づいて、各移動が発生する確率で重み付けされた、各移動からの結果のツリーを生成できます。これにより、どの人間の動きが最良の結果をもたらす可能性が高いかを判断するために必要な詳細を得ることができます。

3.1. ゲームプレイのフローチャート

ゲームプレイがどのように機能するかの一般的な流れ：

「ランダムタイルの追加」プロセスで、ゲームのランダムな側面をすぐに確認できます。タイルを追加するランダムな正方形を見つけ、タイルにランダムな値を選択しているという事実の両方です。

次に、「次の動きを決定する」ステップで何をするかを決定することが私たちの課題です。これはゲームをプレイするためのアルゴリズムです。

これの一般的なオーバーフローは一見単純に見えます：

私たちがする必要があるのは、可能な動きのそれぞれをシミュレートし、どれが最良の結果をもたらすかを決定し、それを使用することです。

そのため、アルゴリズムを縮小して、特定の動きをシミュレートし、結果のスコアを生成しました。

これは2つの部分からなるプロセスです。最初のパスは、移動が可能かどうかを確認することです。不可能な場合は、スコア「0」で早期に中止します。移動が可能な場合は、実際のアルゴリズムに進み、移動がどれだけ優れているかを判断します。

3.2. 次の動きを決定する

これまでのアルゴリズムの重要な部分は、動きをシミュレートすることであり、その重要な部分は、可能な動きごとにスコアを生成する方法です。これが、Expectimaxアルゴリズムの出番です。

両方のプレイヤーからの可能なすべての動きをいくつかのステップでシミュレートし、どちらが最良の結果をもたらすかを確認します。人間のプレイヤーにとって、これは「上」、「下」、「左」のそれぞれを意味します、」と「右」が移動します。

コンピュータプレーヤーの場合、これは「2」または「4」の両方のタイルをすべての可能な空の場所に配置することを意味します。

このアルゴリズムはrecursiveであり、各再帰ステップは、実際のゲームでの実際の動きから特定の深さである場合にのみ停止します。これにより、フローチャート自体がループバックするため、フローチャートを理解するのが難しくなりますが、基本的には次のようになります。

深度制限に達したら停止し、現在シミュレートされているボードレイアウトのスコアを計算します
考えられるすべてのコンピューターの移動をシミュレートする
これらのそれぞれについて
- 考えられるすべての人間の動きをシミュレートする
- これらのそれぞれについて
  - アルゴリズムに戻る
  - この人間の動きから計算されたスコアを返します
- このコンピューターの移動から計算されたスコアを追加し、この移動が発生する確率で重み付けします

これが終了したら、計算されたすべてのスコアを合計します。これが、現在のゲームボードから作成する移動の最終スコアです。これを4回（現在のゲームボードからの可能な移動ごとに1回）行うため、最終的に4つのスコアが得られ、そのうちの最も高いものが移動です。

3.3. ボードポジションのスコアリング

この時点で、あとはボードのスコアを計算するだけです。これはゲームが使用するスコアと同じではありませんが、これがプレイを継続するためにどれだけ良いポジションであるかを考慮する必要があります。

適切な重み付けとともにいくつかの要素を追加することにより、これを実現する方法は多数あります。例えば：

空の場所の数
可能なマージの数–つまり、同じ数が2つの隣接する場所にある回数
任意の場所で最大の値
すべての場所の合計
ボードの単調性–これは、位置の値が一方向に増加するように、ボードがどの程度適切に構成されているかを示します。

4. 擬似コード

アルゴリズムがどのように機能するかがわかったので、これはどのようになりますか？ アルゴリズムをより詳細に説明するいくつかの擬似コードを調べてみましょう。

ゲームの実際のプレイには関心がなく、動きを決定するためのアルゴリズムだけに関心があるので、そこから始めましょう。

以前と同様に、これにより、開始ボードから可能な各移動をシミュレートし、最高のスコアを返すようになります。これにより、新しくシミュレートされたボードのスコアを生成する必要があります。。

しばらくして処理を停止できるように、深度制限を追加しました。再帰的アルゴリズムを使用しているため、それを停止する方法が必要です。そうしないと、永久に実行される可能性があります。

これにより、再帰が得られ、特定のステップ数で可能なすべての人間とコンピューターの動きをシミュレートし、どの人間の動きが可能な限り最良の結果をもたらすかを決定します。

残っているのは、特定のボード位置の最終スコアを算出することだけです。 これに最適なアルゴリズムはなく、さまざまな要因によってさまざまな結果が得られます。

5. パフォーマンスの最適化

これまでのところ、ゲームを解決しようとするアルゴリズムがありますが、それは可能な限り効率的ではありません。 ゲームの性質がランダムであるため、完全に最適化されたソルバーを使用することは不可能です –プロセスの性質のために、常にある程度の繰り返しが発生します。

少なくとも、必要のない作業を減らすために最善を尽くすことができます。

ゲームに影響を与えない動きを処理しないことにより、上記のアルゴリズムですでに少し最適化を行っています。ただし、移動の累積確率を追跡し、それが低くなりすぎたときに停止するなど、実行する作業を減らすことができる他の方法があります。これには完全な解決策を削除するリスクがありますが、確率がそれほど低い場合は、とにかくそれはほぼ確実に起こりません。

使用する深度制限を動的に決定することもできます。 上記の擬似コードのハードコード制限は3ですが、計算の開始時のボードの形状に基づいて動的に計算できます。たとえば、空の正方形の数に設定したり、ボード上の個別のタイルの数。これは、拡張の余地が少ないボードからの移動が少ないことを意味します。

さらに、同じボード位置を何度も再訪できるため、毎回再計算するのではなく、これらを記憶してそれらの位置のスコアをキャッシュできます。可能なすべてのボード位置を前方に生成できる可能性があります時間の経過はありますが、これらは膨大な数になります– 2048までのタイルを使用した281,474,976,710,656の異なる可能なボード位置–したがって、これはおそらく実現可能ではありません。

ただし、実行できる最も重要な最適化は、ボードスコアを生成するためのアルゴリズムを調整することです。これは、プレイを継続するためにボードがどれだけ優れているかを判断するために機能し、これに使用する要素と重みは、アルゴリズムがどれだけうまく機能するかに直接関連しています。