ここで初めてゲーム2048がHabrahabr で紹介されました 。 5日も経たないうちに、彼らはその通過のための単純な戦略の秘密を明らかにしました。 それは本当に簡単です-あなたはタイルからヘビを構築する必要があります（写真のように）。
ただし、理解できる目標は必ずしも容易に達成できるとは限りません。 Mrrlと私は連続して成功を共有しました。彼らは8、16、32 、および65,000のブロックを盲目にしました。ポイント。
これにより、ゲーム2048についての以前の考えを投稿としてまとめて整理することになりました。これは、パスの戦略と戦術ではなく、次のような問題に関するものです。
-2 17は本当に可能な最大ブロックですか？
-ゲームの必然的な終了までの途中で、原則として何ポイント獲得できますか？
-パズルはいくつの動きをしますか？
それを理解するには少し数学が必要です...
最大可能タイル
ブロック2 17の作成につながる蛇の絵を見ると、この特定の戦略を使用してより大きなタイルを組み立てることができないことは明らかです。 しかし、131,072が実際に最大であるという結論は本当ですか？ 直観は答えがイエスであると言っていますが、もっと説得力のある議論が欲しいです。 そして、研究のこの部分は私にとって最も難しいことが判明しました。 いくつかのアプローチが行き詰まり、ついに次の設計にたどり着きました。
主なアイデアは、競技場でタイルがどのように配置されているかを無視し、その値のみに焦点を当てることです。 この観点から、ゲームの状態は、現在画面に表示されている16個の数字の昇順で説明できます（ゼロは空のセルに対応します）。
この図の場合、状態はセット（4、4、8、16、...、65536）になります。 そして、ゲームの最初の段階では、例えばベクトル（0、0、...、0、2、2）になります。 それぞれの動き（人間と機械の両方）は新しい状態につながりますが、それはarbitrary意的ではありません。 したがって、ゲームのルールでは、（0、...、0、2、2、8）から（0、...、0、4、16）に一度にジャンプすることはできません。
ある状態から別の状態へのすべての可能な遷移について説明します。
-人の過程で-何も変わらないか、同じ数の1つ以上のペアがペアの要素の合計に置き換えられ、必要な数のゼロが追加され、ベクトルが順序付けられます。
-車の進行中-1デュースまたは1フォー4がセットに追加され（順序を乱さないように）、1ゼロが削除されるか、（状態にゼロがない場合）プレイヤーが負けます。
初期状態（つまり、パズルの開始時の状態）は、（0、...、0、2、2）、（0、...、0、2、4）または（0、...、0、4、4）です。 男と車が順番に行き、プレーヤーが最初にスタートします。
これらのルールは、構築した2048ゲームモデルの公理と見なすことができますが、予想どおり、モデリングオブジェクトよりも単純ですが、重要なプロパティがあります。
-元のパズルで、たとえば2 17のタイルを作成できる場合、新しいものでも同じです。
-逆もまた同様です。単純化されたゲームで2 18の状態になることが不可能な場合、そのようなブロックの元の作成は不可能です。
したがって、「131 072は可能な限り最大のタイルですか？」という質問に答えるために、モデル内で番号2 18の状態に切り替えることは決して不可能であることを証明する必要があります。
証明：反対のことを想定し、最初の状態から2 18番が最初に現れたときまでの状態の連鎖を考えてください。 モデルの公理に基づいて、最後のベクトルは、人がフォーム（...、2 17、2 17 ）の状況で移動した後にのみ表示されます。
チェーンで最初に遭遇したこのような状態を考えてみましょう。 （...、2 16、2 16、2 17 ）、または（...、2 16、2 16、2 16、2 16 ）のいずれかに先行し（受け入れられた公理によると）、コースの順番はその人のためです。
これは、プレイヤーが以前は（...、2 15、2 15、2 16、2 17 ）、（...、2 15、2 15、2 15、2 15、2 17のいずれかの状況にあった必要があることを意味します）、（...、2 15、2 15、2 16、2 16、2 16 ）、（...、2 15、2 15、2 15、2 15、2 16、2 16 ）、（...、2 15、2 15、2 15、2 15、2 15、2 15、2 16 ）または（...、2 15、2 15、2 15、2 15、2 15、2 15、2 15、2 15 ）。
注：一部の状態と遷移は、検討中のモデルでのみ可能です。ゲーム2048には類似物がなく、証明の過程に影響しません。
そのような推論の各後続の段階は、チェーンに存在する必要があるベクトルの厳密に指定されたコンポーネントの数の少なくとも単位の増加につながります。 この場合、固定値の最小値が半分になります。
その結果、わずか15ステップで、16個のコンポーネントすべてが明示的に定義されます。 次に、チェーンにフォーム（2 k 、...）の状態がなければならないという結論に達します。ここで、k≥3で、人が歩いています。
しかし、マシンのアクション後、ベクトルで表される数字の最小値は0、2、または4にしかならないため、プレーヤーはそのような状況に陥ることはありませんでした。
その結果、2 17は 2048ゲームで実際に可能な最大のタイルです。 また、パズルを渡すことは、限られた数のポイントで、一定の数の動きを超えて実行できないことを意味します。 いくつのポイントとアクションが自由に使えるのだろうか？
最大ポイント
スコアリングは私にとってずっと簡単でした。 まず、2048年にプレイヤーが目指すことができる最善のものを概説します。チャンピオンの大切な目標（および移動数も）は、ベクトル（2、8、16、32、...、131 072）または（ 4、8、16、32、...、131 072）。 この場合、ゲームは終了しますが、他の状態は指定された状態によって「支配」されます。つまり、追加のポイントを獲得することで（追加のアクションを完了することで）間違いなく改善できます。
また、目的のエンディングまでの途中で、マシンは多かれ少なかれ4を生成できることに注意してください。 プレーヤーがこのような「ギフト」を受け取る頻度が高いほど、スコアは悪化します。 したがって、すべての場合（以下に指定されている場合を除く）のマシンがデュースを与えると仮定しましょう。 最後までたどり着くには、15個の4だけを取得する必要があります。ブロック131 072、その隣にあるタイル65 536などを収集して、8になります。
したがって、行われた仮定を覚えて、関数f （ n ）を考慮してください。その値は、タイル2 nが最初にフィールドに表示されるまでに獲得できるポイントの最小数として定義されます。 なぜ最も小さいのですか？ 実際には、たとえばブロック4で初めて収集したことにより、このために獲得した4ポイントの存在を保証できますが、さらに多くのポイントがある可能性があります（突然複数のタイルを4で集めた場合）。
f （2）= 4になります。次に：
f （3）= 16（2つの必要なブロック4ごとに4ポイントを取得し、8つの組み合わせでさらに8ポイントを取得します）、
f （4）= 48（= 16 + 16 + 16）、
f （5）= 128（= 48 + 48 + 32）など
再帰関係は次のとおりです。すべての正の整数nについて 、 f （ n ）= 2 f （ n-1 ）+ 2 n 、3≤n≤16。それを解決する1つの方法は、等式f （ n ）= 2（2 f （ n- 2 ）+ 2 n-1 ）+ 2 n = 4 f （ n-2 ）+ 2 * 2 n 、 f （ n ）= 4（2 f （ n-3 ）+ 2 n-2 ）+ 2 * 2 n = 2 3 f （ n-3 ）+ 3 * 2 n 、...、 f （ n ）= 2 n -2 f （ 2 ）+（ n -2）* 2 n 。 f （2）= 4の場合、 f （ n ）= 2 n （ n -1）を取得します。これは、3≤n≤16の場合、真です。
タイル2 17を収集すると、推測された式よりも4ポイント少なくなります。これは、マシンから提示された4つのうちの1つを使用せざるを得ないためです。 つまり、 f （17）= 2 17 * 16-4または2097 148。
最大ブロックを作成した後、再度2 16タイルを「収集」する必要があり、 f （16）-このために4ポイント（罰金は無料の4つを使用するために再びあります）を取得し、2 15にアテンダントf （15 ）-4ポイント、2 3およびf （3）まで-貯金箱で4ポイント。
合計f （17）+ f （16）-4 + f （15）-4 + ... + f （3）-4を計算すると、3 932 100が得られます。これは、ゲーム2048で可能な最大ポイント数です 。
小さな注釈：定義上、 f （ n ）は、タイル2 nがフィールドに最初に表示されるまでに獲得できるポイントの最小数です。 ただし、最終的なゲームでは、獲得したポイントの数は、 nが3から17（罰金を差し引いた）の関数の値の合計に正確に等しくなります。 余剰はありません。これは、小さなブロックに対応する用語で考慮されるためです。
プレーヤーの最大移動可能数
移動回数のタスクは、最初は最も難しいように思えました。 しかし、推論は非常に簡単です。関数g （ n ）を導入します。これはfにいくらか似ています。 その値は、ブロック2 nを収集するために必要なタイル2の最小数として定義されます。 移動回数を最大化するために、マシンが毎回（15の特別なケースを除いて）デュースを与えるという仮定に基づいて行動します。
したがって、 g （2）= 2（4を収集するには2デュースをマージする必要があります）、 g （3）= 4（8を収集するには2フォースをマージする必要があり、それぞれに2デュースが必要です）、 g （4）= 8（ = 4 + 4）など。 単純な回帰関係g （ n ）= 2 g （ n -1）は、3≤n≤16に対して式g （ n ）= 2 n -1を与えます。
ブロック2 17を作成する場合、上記の式が示すより2タイル少ない2タイルが必要です。1タイルがすぐに1タイルになるため、収集する必要はありません。 したがって、 g （17）= 2 16-2 = 65534。ポイントの場合と同じ方法で、2つの最終状態の1つへの途中に含まれる2の総数を計算するには、 nの関数g （ n ）の値を追加します。罰金を含む3〜17。 g （17）+ g （16）-2 + ... + g （3）-2、131 038になります。完全な注文の場合、最終状態（2、8、16、 ...、131 072）。
さて、タスクに戻ります。 最初から2つのタイル2が与えられます。 残りの131,036（ファイナルの1つで最後を数えない）を取得するには、適切な数のアクションを実行する必要があります（結局、マシンがターンするたびに正確に1つ2つが与えられます）。 さらに、さらに15の4が必要です（ファイナルの1つで最後を数えません）。 そして最後に、別のアクションが最後の2つまたは4つの外観につながります。
合計、PERFORCE、131,036 + 15 + 1 = 131,052のキーストローク（またはタッチスクリーンでのタッチ）を行う必要があります-これは、ゲーム2048でのユーザーの最大移動回数です 。
ゲーム2048での私の現在の成果の分析
結論として、ゲーム2048での最近の成功を分析するために上記の結果とアプローチを適用することができます。写真に反映された状況を達成するために必要な動きの正確な数を決定できることがわかったのは驚くべきことでした。 もちろん、これは私が実行したアクションを考慮せず、最後の保存から個々のエピソードを繰り返し再生します（セーブはゲームでタブを複製することで行うことができます）。 そして、これがなければ、可能な限り最大のブロックを組み立てることは非常にまれです。
したがって、以前にテストした推論に従って、2と1 4だけがゲーム全体に落ちた場合、 g （16）+ g （15）+ ... + g （2）+ 1-2 = 65,533の動きの結果、ダイヤルする必要がありましたポイントf （16）+ f （15）+ f （14）+ ... + f （2）= 1 835 012ポイント。 しかし、ご覧のように、獲得したのは1,811,320だけで、23,692の不足があります、つまり、車は5,923の4を与え、ポイントを獲得できなくなりましたが、対応する移動数は節約されました。
結論：
-これまでに、私はゲーム2048で完全な勝利に向かう途中で約6万の正しいアクションを行いました。
-避けられない2つのファイナルのうちの1つまで、約7万1千回のキーストロークがあります（理想的なゲームと運で）。
-私が受け取ったポイントの合計数（最大タイルとその隣の4分の1ブロックを収集した後）は2,117,800、つまり可能な最大の54％です。 半分以上！ 乱数ジェネレーターによるほぼ24,000ポイントの回復不能な損失も考慮に入れています。
いきなりおもちゃを最後まで仕上げたら-この投稿に写真を掲載します。 みんなに良い気分！
UPD：
スクリーンショットの直後に表示される「ゲームオーバー」というフレーズは、この場合は完全に適切ではないように思われます。 実際、2つの可能な最終状態のうちの1つに向かう途中で、勝利ブロック2048を127回収集する必要がありました。 合計119 322の正しい動きが行われました。 マシンは、フィールド上に11 730のフォースを投げ（左上隅の最後をカウントしません）、勝利を加速しましたが、46 920ポイントを失いました。