Apple Gameは最適に解けるのか？
※ この記事は英語の原文をAIで翻訳したものです。
tl;dr - 一般的なケースでは、おそらく効率的には解けない。
一つの長方形の合計が10かどうかを確認するのは簡単だ。提案された手順を検証するのも簡単だ。難しいのは最適な手順を見つけることだ。すべての手が将来の合法手の集合を変えるからだ。これにより分解が弱い大きな探索木が生じ、厳密な探索はスケールしにくい。小さな盤面では、DFSとBranch and Boundのような厳密な手法が機能する。現実的な盤面サイズでは、Heuristic探索がより実用的なアプローチとなる。
問題設定
m x nの盤面があり、各セルには1から9の値が入っている。合法手は、セルの合計がちょうど10になる軸平行な長方形を選択し、それらのセルを盤面から除去することだ。
目的は、除去したセルの総数を最大化することである。
つまり問題はこうだ：与えられた初期盤面に対して、最高スコアを達成する合法手順を見つけよ。
簡単な部分
問題の一部は簡単だ。
一つの候補長方形は素早く確認できる。2D Prefix Sumを使えば、O(mn)の前処理後、O(1)時間でセルの合計を計算できる。合法性の判定に長方形内のすべてのセルがまだ存在していることも必要なら、生存セルに対する二つ目のPrefix Sumで十分だ。
現在の盤面上のすべての候補長方形を列挙するのも管理可能だ。軸平行な長方形はO(m^2 n^2)個あり、それぞれ素早くテストできる。
検証も管理可能だ。誰かが完全な手順を示し、少なくともK個のセルを除去したと主張すれば、その手順を再現して多項式時間で確認できる。
ボトルネックは局所的な確認ではない。全域的な探索だ。
厳密な探索が難しくなる理由
難しさは手の依存性から来る。
ある手が将来の機会を潰すことがある。また、残りの配置を変えることで、より良い将来の機会を生み出すこともある。したがって、手の価値は即座の利得だけでは決まらない。残される盤面状態に依存する。
そのため手の順序が核心となる。同じ盤面から始めた二つの異なる手順が、まったく異なるスコアで終わることがある。
平均分岐因子がBで、ゲームがD手続くとすると、単純な探索木のサイズはおおよそB^Dとなる。17 x 10の盤面では、BとDの両方が探索空間を急速に爆発させるのに十分な大きさになる。
これはDynamic Programmingも制限する。強い分解構造を持つ問題では、状態をほぼ独立した部分問題に分割できるためDPが機能する。Apple Gameは一般に、そのようには振る舞わない。ある領域での除去が別の領域での将来の実行可能性を変えうる。特に大きな長方形が許される場合にそうなる。
NP的な探索との関係
複雑性の問題をより整理して述べると、決定問題になる：盤面と整数Kが与えられたとき、少なくともK個のセルを除去する合法手順は存在するか？
この形式は典型的なNP的構造を持つ。提案された解は多項式時間で検証できるが、解を見つけるには大きな探索空間を探索する必要があるかもしれない。
これはNP-hardの証明ではない。本当の証明には既知のNP-hard問題からの還元が必要だ。しかし構造的に、この問題は単純な多項式時間の厳密アルゴリズムが存在する問題よりも、難しい組合せ探索にはるかに近い。
厳密な手法
小さな盤面では、厳密な探索が可能だ。
標準的なベースラインはDFSとBranch and Boundだ。深さ優先で探索しつつ、上界が現在の最良解を上回れないことを示す枝を刈る。
異なる手順が同じ盤面状態に到達する場合、Memoizationが助けになる。固定された初期盤面では、各セルは存在か除去かの二状態のみを取る。したがって到達可能な状態の上界は10^(mn)ではなく2^(mn)となる。17 x 10の盤面ではこれでもなお完全な状態キャッシュには大きすぎるが、小さなインスタンスでは効果がある。
制約プログラミングやILP的な定式化も、小さなインスタンスでは可能だ。主な問題は、逐次的な実行可能性のためにエンコーディングが急速に大きくなることだ。
狭い特殊ケースでは、Dynamic Programmingがまだ可能かもしれない。1 x nの変形や他の制約された幾何学では、コンパクトな状態表現が可能かもしれない。一般的な2Dケースではそうはならない。
実用的な結論
小さなインスタンスでは、厳密な最適化は実行可能だ。
現実的な盤面サイズでは、厳密な探索は急速にコストが高くなる。最も有望な厳密アプローチは通常、DFSとBranch and Boundに良い手の順序付け、Transposition Table、そして残存する生存セル数のような安価な許容可能上界を組み合わせたものだ。
保証された最適性よりも強いパフォーマンスが目標なら、Heuristicが実用的な選択だ。
Heuristic探索
Beam search visualization. CC BY-SA 4.0, Wikimedia Commons.
Greedy Solverは局所ルールに従って最も良く見える手を選ぶ。高速で実装も容易だが、短期的に弱い手がはるかに良い継続につながる手順を見逃すことがある。
Beam Searchは一つのパスだけを追う代わりに、各深さで上位k個の部分解を保持する。これはまだ近似だが、純粋なGreedy手法よりも探索空間の広い部分を探索する。
Heuristicはプロキシ目的関数も使える。即座の利得だけを最大化する代わりに、将来の選択肢をより多く保持する手や、難しいセルを孤立させない手を好むことができる。
これらの手法は最適解を保証しないが、フルサイズの盤面ではるかに実用的だ。
投稿一覧