2つの合体ゲームに、1つの問い。どちらかを完璧にプレイすることはできるのか？ その答えは、盤面の隅、決して現れない対戦相手、そして17段の指数の高さを持つ数を通っていきます。
英語で執筆・編集されました。この日本語版は機械翻訳によって作成されたものです。正確さが重要な箇所については、英語の原文が正式なものです。 英語の原文を読む →
誰もが知っているゲームから始めましょう。4方向、4×4のグリッド、触れ合うと倍になるタイルからなる2048は、厳密に言えば未解決です。これを完璧にプレイするアルゴリズムを書いた人はいません。あるのは非常に強力な近似です。8手ほど先を見通し、空きマス、端に寄せた大きなタイル、なめらかさといった、手で調整した少数のヒューリスティックで各盤面を採点するexpectimax（期待値最大化）探索は、3分の1を超えるゲームで32768のタイルに到達し、1 公開されている最強のエンジンは、数パーセントの確率で65536のタイルに届きます。2 m×nの盤面に一般化すると、目標のタイルに到達できるかどうかを判定するだけでNP困難になります。3 強いことは、解けたことと同じではありません。
1つのタイルはどこまで高く昇れるのでしょうか。16マスの場合、その答えは小さく優雅な数え上げになります。盤面を下り階段のように並べてみましょう。65536、32768、16384と下っていき、最後はぽつんと1つの2です。各タイルは隣よりちょうど2の累乗1つ分だけ小さいので、21から216までの16個の異なる累乗が盤面をぴったり埋め、65536 = 216が頂上に座ります。1マスにつき指数1つです。これが、ゲームが2しか配らない場合の天井です。しかし2048は10回に1回の割合で4を出し、うまいタイミングの4が1枚あれば17番目の指数を密輸でき、本当の最大値は131072 = 217に引き上げられます。17枚分の累乗が16マスに詰め込まれるのです。4 これを作り上げた人間はいません。わずかなAIがかすめた程度です。
なぜこうした盤面では、最大のタイルを隅にしまい込むことが報われるのでしょうか。中央のタイルは4方向に押し出され得るので、結ばれたい相手のタイルから引き離され続けます。隅のタイルは2つの壁に接しています。すでに寄り添っている壁の方向へ押してもそのタイルは動かず、その壁から離れる方向に押さないようにしている限り、周りのすべてが整理されていくあいだ、じっと座っていられます。残りのタイルを単調な蛇のようにつなげ、最大のものを隅に置いて、降順に行ったり来たり折り返していけば、一度のスワイプで合体の連鎖を引き起こせます。1 これは人間の気軽なプレイを支配するヒューリスティックであり、AIに自分で重みを調整させると、ほぼこれを再発見します。
ランダムにタイルが出現する合体ゲームには、対戦相手はいません。あるのは天候だけです。それを「解く」とは、心を打ち負かすことではなく、平均してサイコロに勝つことなのです。
では、盤面を3次元へ傾けてみましょう。3927は2048の立方体版のいとこです。27マスの3×3×3の格子、4方向ではなく6方向のシフト、そして3つずつ融合するタイル。3が9に、9が27に、27が81になり、2048が2進法であるところを3進法で進みます。5 隅に積む戦略は、増えた次元を生き延びるでしょうか。立方体には8つの隅があり、隅のマスは2つではなく3つの面に接します。一度に3つの壁に押さえられるので、さらに安定するはずですが、6つの方向があるぶん、盤面にはあなたの構造を揺さぶってほどく手段も増えます。蛇は、3つの層すべてを縫うように折り畳まれた経路になります。私が調べた限り、このアナロジーが実際に成り立つかどうかを突き止めた人はいません。これは測定ではなく推論です。
では天井は？ 1マスにつき指数1つという規則からすれば、ゆるい上界として327 ≈ 7.6兆が示唆されます。しかし、このアナロジーはひどくほころびます。2048の余分な指数は幸運な4から来ていました。3927が出すのは常に最小のタイル、ただの3だけなので、ボーナスはありません。さらに悪いことに、3つの合体には一直線に並んだ3枚のタイルが必要で、3×3×3の立方体では行も列も柱もすべてちょうど3マスの長さなので、どの合体も1本のライン全体を消費します。この制約は平面のゲームのどんな制約よりもはるかに厳しく効き、本当の最大値を327よりかなり下まで引き下げるのはほぼ確実です。その本当の数がいくつなのか、計算されたものを私はどこにも見つけられていません。（はっきり推論と明記しておきます。上記の仕組みはゲームの設計文書から測ったものです。）
「完璧なプレイ」をつかみどころのないものにしている微妙な点があります。ランダムにタイルが出現する合体ゲームは1人用の確率ゲームであり、決闘ではなく、サイコロを相手にしたソリティアです。あなたを破滅させるために最悪の出現を選ぶものは何もありません。あるのは無関心な乱数生成器だけです。ですから、最適なプレイの正しい概念はexpectimaxです。出現の分布にわたって期待される結果を最大化するのです。それは断じてミニマックスではありません。ミニマックスは敵対者を前提としており、実際に敵対者にすべてのタイルを置かせると（「邪悪な2048」）、ゲームは負けを強制され得る、もっと残酷なものになります。サイコロは原理的にはどんな並びでも配り得るので、あるタイルへの到達を保証する戦略は、そもそも存在しないかもしれません。したがって「完璧な戦略はあるか？」への誠実な答えはこうなります。確率ゲームについて定義できるのはせいぜい平均的に最善の戦略であり、それを厳密に計算することは、2048では手の届かないところにあり、6 3927ではまったくの未解決です。