← 投稿一覧

りんごゲームの難易度ベースラインとしてのGreedy Solver

※ この記事は英語の原文をAIで翻訳したものです。

Apple Gameのボードがどれくらい難しいかを推定したいとする。最も直接的な方法は、多くの人間プレイヤーにそのボードをプレイしてもらい、スコアを平均することだ。しかし、これはコストが高く時間もかかる。反対側の極端として、全探索を行い理論上の最大スコアを計算する方法がある。しかし実際には、1つのボードだけでも可能な手順の数が急激に増加するため、これも現実的ではない。

そこで、この2つの極端の間にあるものが必要だった。高速で一貫性があり、任意のボードに対して難易度に関するスコアを1つ割り当てられる近似手法だ。

目標は完璧なソルバーを作ることではなかった。人間の思考過程を詳細に再現することでもなかった。実行コストが低く、説明しやすく、多くのボードにわたって安定する単純なベースラインが欲しかった。ボードごとにスコアが変化するなら、その変化が複雑な評価手法ではなく、ボード構造そのものに起因してほしかった。

こうした理由から、Greedy Solverを選択した。

アルゴリズム設計において、貪欲法とは将来の状態を深く探索せず、各ステップで最も良さそうに見える局所的な行動を選ぶ手法だ。我々のソルバーは現在のボードを見て、有効な手をすべて見つけ、固定のルールで1つを選び、該当セルを除去し、有効な手がなくなるまでこのプロセスを繰り返す。バックトラッキングも、探索木も、確率的サンプリングもない。

手の選択ルールも単純だ。各ステップで、ソルバーはセルの合計が10になるすべての長方形を列挙する。これらが有効な手である。その中から、最も大きい単一セル値を含む手を優先的に選ぶ。大きい値は柔軟に組み合わせにくいため、早めに除去するとボードがより使いやすい状態に残ることが多いという直感に基づく。同点の場合は、セル数が少ない長方形を優先する。小さい長方形の方が後の手のためにより多くのセルを温存できるからだ。

一見すると、この貪欲な振る舞いは弱点に見えるかもしれない。しかし我々の目的においては、むしろ有用だ。ある意味で、貪欲であることが人間のプレイにより近い性質を持たせている。

Apple Gameには2分の制限時間がある。この条件下で、20手先まで計画してボードを解こうとする人はほぼいない。せいぜい1～2手先を見る程度だ。我々が測定したいのは数学的最適性ではなく体感難易度であるため、貪欲なアプローチは合理的な近似となる。

一般的なプレイヤーの視点では、主な難しさは長期戦略ではなく、残っている有効な手を認識すること自体にある。多くのプレイヤーは、現在のボード上の有効な長方形をすべて把握するだけでもすでに苦労する。実際のプレイでは、大抵貪欲に進行する。最初に目についた領域から始め、そこで手を打ち、次に近くの領域へ移る。毎ターン、ボード全体をグローバルに最適化することはしない。

このため、我々のソルバーはApple Gameを何度かプレイしたことがあり、比較的高いスコアを出すことに慣れたプレイヤーとある程度似た挙動をする。上級者ではないが、ランダムでもない。計算は完璧でボード全体を漏れなく見ることができるが、意思決定ルール自体は近視眼的だ。この組み合わせが、機械的なベースラインとして有用であることがわかった。

function SolveBoard(board): integer;
var
  validMoves: list of Move;
  bestMove: Move;
  totalScore: integer;
begin
  totalScore := 0;
while HasValidMove(board) do
begin
validMoves := FindAllRectanglesSummingTo10(board);
bestMove := SelectBestMove(validMoves);
RemoveRectangle(board, bestMove);
totalScore := totalScore + ScoreOf(bestMove);
end;
SolveBoard := totalScore;
end;
function SelectBestMove(validMoves): Move;
begin
SelectBestMove := move in validMoves
with maximum LargestCellValue(move),
and if tied, minimum CellCount(move);
end;

これがソルバーの全体像だ。決定論的なので、同じボードは常に同じ結果を生む。

このソルバーの主な利点は速度と一貫性だ。多くのボードを素早く評価し、それぞれに再現可能なスコアを割り当てることができる。この限定的なソルバーでも高スコアが出るボードなら、そのボードは実際に簡単である可能性が高い。ソルバーの成績が悪いボードは、散在する小さい値、非効率な配置、目に見える機会の少なさなど、人間プレイヤーにとっても難しくなる構造的特性を持っていることが多い。

もちろん、このソルバーには明確な限界がある。最適ではない。先読みをしないため、今は弱く見える手が後にはるかに良い手順を生み出すケースを見逃すことがある。非直感的な犠牲が報われるボードが存在するが、Greedy Solverはそのような手を意図的に選ぶことはない。そのため、ソルバースコアは実用的な下限推定値として解釈すべきであり、達成可能な真の最大スコアとして解釈すべきではない。

ヒューリスティックが不安定になるエッジケースもある。候補手が似通っている場合、タイブレーキングルールが軌跡全体に影響を与えることがある。特定のセルを後のために残すことが成否を分けるボードでは、貪欲な選択が早すぎる段階で行き止まりに入る可能性がある。これらの限界は実在しており、貪欲スコアは難易度の代理指標に過ぎず、絶対的な測定値ではないことを意味する。

それでも、当初の目的に照らせば、このトレードオフは許容範囲だ。完璧なプレイヤーが必要だったわけではない。ボード間の比較のための単純で再現可能なレンズが必要だった。Greedy Solverはこの役割を十分に果たす。透明で、決定論的で、実行コストが低い。時に、粗くても明確に定義されたツールの方が、高価すぎたり解釈が難しすぎる洗練された手法よりも有用なことがある。