10

編集:この質問は、2048 年のゲームに最適なアルゴリズムは何ですか?の複製ではありません。

  • その質問は、「ゲームに勝つための最良の方法は何ですか?」と尋ねます。
  • この質問は、「どうすればゲームの複雑さを解決できるでしょうか?」と尋ねます。

それらはまったく異なる質問です。「勝利」状態に移行するために必要なステップには興味がありません。可能なステップの総数を計算できるかどうかを調べることに興味があります。

ゲームをうまくプレイするアルゴリズムを作成するための戦略について説明しているゲーム2048に関するこの質問を読んでいます。

受け入れられた回答には、次のことが記載されています。

ゲームは離散状態空間、完全な情報、チェスのようなターンベースのゲーム

その複雑さについて考えさせられました。チェスのような決定論的なゲームでは、(理論的には) 勝利状態につながる可能性のあるすべての動きを計算し、逆方向に作業して、その結果につながり続ける最良の動きを選択することができます。私はこれが多数の可能性のある動きにつながることを知っています（宇宙の原子数の範囲内の何か）..しかし、2048年は多かれ少なかれ複雑ですか？

擬似コード:

for the current arrangement of tiles
    - work out the possible moves
    - work out what the board will look like if the program adds a 2 to the board
    - work out what the board will look like if the program adds a 4 to the board
    - move on to working out the possible moves for the new state

この時点で、これが実行されるのを待っている間、ここにいると思います...

そこで私の質問は、このアルゴリズムをどのように書き始めるかということです。ゲームの複雑さを計算するのに最適な戦略は何ですか?

2048 とチェスの大きな違いは、プログラムが新しい牌を追加するときに 2 から 4 の間でランダムに選択できることです。

最終的には、ゲーム内で可能な順列の数を示す 1 つの図をプログラムに出力してもらいたいと考えています。これは可能ですか？

4

1 に答える 1

8

考えられるボード構成がいくつあるかを判断してみましょう。

各タイルは空にすることも、2、4、8、...、512、または 1024 タイルを含めることもできます。

つまり、タイルごとに 12 の可能性があります。16 個のタイルがあるので、16 12 = 2 48 の可能なボードの状態が得られます。これには、いくつかの到達不能な状態が含まれている可能性があります。

これらすべてをメモリに保存できると仮定すると、次の手で 2048 タイルを生成するすべてのボードの状態から逆方向に作業し、到達可能なボードの状態を相互にリンクするために一定量の作業を行うことができます。各州の最善の動き。

すべてのビットをメモリに格納するには、タイルごとに 4 ビット、つまり 64 ビット = ボード状態ごとに 8 バイトが必要だとします。

2 48ボードの状態では、8*2 48 = 2251799813685248 バイト = 2048 TB が必要になります (最適なボードを追跡するための追加のオーバーヘッドは言うまでもありません)。これは、最近のデスクトップ コンピュータの能力を少し超えていますが、たとえば 3 TB のハード ドライブやRAMでも。

参考までに、チェスには2,155の可能な位置の上限があります。

最初からすべての可能な動きを (幅優先探索のような方法で) 実際に計算すると、膨大な数が得られます。

これは正確な数値ではなく、上限の概算です。

いくつかの仮定を立ててみましょう: (常に正しいとは限りませんが、簡単にするために)

  • 開いているマスは常に 15 個あります

  • あなたは常に4つの動きを持っています（左、右、上、下）

  • ボード上のすべてのタイルの合計が 2048 に達すると、1 つの 2048 を取得するための組み合わせの最小数が必要になります (したがって、2 を配置すると合計が 2048 になる場合、組み合わせは 2 -> 4 -> 8 になります。 > 16 -> ... -> 2048、つまり 10 回の移動)

  • 2 は常に配置され、4 は配置されません。アルゴリズムはこれを想定しませんが、上限を計算するために想定します。

  • このプロセス中に重複したボードが生成される可能性があるという事実は考慮されません。

2048 に到達するには、2048 / 2 = 1024 個のタイルを配置する必要があります。

ランダムに配置された 2 つのタイルから始めて、移動を繰り返し、別のタイルが配置されるので、合計が 2048 になるまで、約 1022 の「ターン」(移動とタイルの配置からなるターン) があります。 2048 タイルを得るためにさらに 10 ターン。

各ターンには 4 つの移動があり、15 の位置 (30 の可能性) のいずれかに配置された 2 つのタイルのうちの 1 つが存在する可能性があるため、4*30 = 120 の可能性があります。

これにより、合計で 120 1032の可能な状態が得られます。

代わりに、常に 4 が配置されると仮定すると、120 519の状態が得られます。

正確な数を計算するには、これらすべての状態を処理する必要があり、実際には実行可能ではありません.

于 2014-03-19T15:21:32.630 に答える