パズルの自動生成の仕組みと、検証が大切な理由

2011年、Julian Togelius、Georgios Yannakakis、Kenneth Stanley、Cameron Browneは、急成長していた分野を整理し、「探索ベースの手続き型コンテンツ生成」という名前をつけました。彼らのサーベイは生成器を、何をつくるか、そのコンテンツがプログラムの中でどう表現されるか、そして何より、その質がどう評価されるかで分類しています。探索ベースのアプローチは、レベルデザインを最適化問題として扱います。候補を生成し、評価関数でそれぞれに点をつけ、最良のものを残して変化を加え、それをくり返します。生物学から借りてきた進化的アルゴリズムがよく使われます。

デザインが宿るのは評価関数です。レベルを直接測ることもできますし（ピースの数、空きスペースの量）、シミュレーションで測ることも（人工のプレイヤーに挑戦させて結果を見る）、インタラクティブに測ることも（実際のプレイヤーに聞く）できます。どれにもコストがあります。直接の測定は安上がりですが浅く、シミュレーションはより正確ですが、実際にゲームを遊べるプログラムが必要です。人に聞くのがいちばん正確で、とびきり時間がかかります。

スライドパズルなら、イメージしやすいでしょう。候補は、ブロックが置かれたグリッドです。変化とは、ブロックを動かしたり、加えたり、取り除いたりすることです。直接の測定なら、ステージがどれだけ混み合っているかを数えるかもしれません。シミュレーションによる測定なら、ステージをソルバーに渡し、クリアできるかどうかと、見つかったルートの長さを記録します。点数の高いステージを残し、また変化を加える。何千回もくり返すうちに、生成器は評価関数が報いるものへと流れていきます。それが強みであり、危うさでもあります。数字は満たすけれどプレイヤーを退屈させるステージも含めて、求めたものをそのとおりに見つけてくるのです。

出典1出典1Togelius, J., Yannakakis, G. N., Stanley, K. O., & Browne, C. (2011). Search-based procedural content generation: A taxonomy and survey. IEEE Transactions on Computational Intelligence and AI in Games, 3(3), 172–186.

反対側から出発する流派もあります。ステージを進化させて良いものが現れるのを期待するかわりに、Adam SmithとMichael Mateasは、許容できるデザインの範囲を論理的な制約の集まりとして明示的に記述し、汎用のソルバーにそれを満たすステージを探させる方法を提案しました。解集合プログラミングという手法を使えば、デザイナーは「出口に到達できなければならない」「このピースは少なくとも2回動かなければならない」といったルールを書き、それに従うステージだけを受け取ることができます。

パズルデザインにとっての魅力は明らかです。ステージをおもしろくしているものの多くは制約だからです。このブロックはあのブロックにふさがれていなければならない、このカギは必要でなければならない。それを書き出すことで、デザイナーは自分が本当に求めているものを言葉にせざるをえなくなります。これは機械にとってと同じくらい、人間にとっても役に立つ訓練です。

出典2出典2Smith, A. M., & Mateas, M. (2011). Answer set programming for procedural content generation: A design space approach. IEEE Transactions on Computational Intelligence and AI in Games, 3(3), 187–200.

どんな生成器であれ、パズルはまず解けなければなりません。そして、それを証明するのがいちばん難しい段階であることも少なくありません。Noor Shaker、Mohammad Shaker、Julian Togeliusは、時間も空間も連続している物理パズル、Cut the Ropeでこの問題に向き合いました。そこでは総当たりの探索は望みがありません。彼らの答えは、各状態で理にかなった手だけを提案する推論エージェントでした。これで探索の範囲が十分に絞られ、素直な深さ優先探索でも解を見つけられるようになり、生成したレベルが遊べることを確かめられました。

Bilal Kartal、Nick Sohre、Stephen Guyは、箱を押す古典パズル、倉庫番（Sokoban）で別の道をとりました。彼らの生成器は、モンテカルロ木探索を使ったシミュレーション上のプレイを通してパズルを組み立てるので、生み出すパズルはすべて、つくり方からして解けることが保証されています。スライドパズルも難しいケースです。スライドパズルの歴史で説明しているとおり、一般化した問題はPSPACE完全なので、どんなステージでも素早く解ける近道は知られていません。

出典3出典3Shaker, N., Shaker, M., & Togelius, J. (2013). Evolving playable content for Cut the Rope through a simulation-based approach. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 9(1), 72–78.4出典4Kartal, B., Sohre, N., & Guy, S. (2016). Data driven Sokoban puzzle generation with Monte Carlo tree search. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 12(1), 58–64.

ステージは解けても退屈なことがありますし、人間には見つけられないルートでしか解けないこともあります。Kartalらは、この問題に正面から取り組みました。ユーザー調査を行って、計算が安く、しかも人がパズルをどれだけ難しいと感じるかと相関するステージの特徴を見つけ、それらを組み合わせて採点関数をつくりました。そして2つ目の調査で、点数の高いパズルほど難しいと感じられることを確かめました。つまり難しさは、前提とするのではなく、人から学ぶ必要があったのです。

YannakakisとTogeliusは、体験駆動型の手続き型コンテンツ生成の枠組みで、この点を一般化しています。行動、自己報告、生理反応のいずれかからプレイヤーの体験をモデル化し、その体験を形づくるようにコンテンツを生成する、というものです。野心的な目標ですが、正直に言えば、楽しさやイライラのモデルは今もまだ大まかです。パズルの場合、エレガントさ、満足のいく「ひらめき」、公平さといった性質は、計算するより見分けるほうが今も簡単です。プレイヤーにとって公平さが何を意味するかは、公平なパズルとは何かで考えています。

出典4出典4Kartal, B., Sohre, N., & Guy, S. (2016). Data driven Sokoban puzzle generation with Monte Carlo tree search. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 12(1), 58–64.5出典5Yannakakis, G. N., & Togelius, J. (2011). Experience-driven procedural content generation. IEEE Transactions on Affective Computing, 2(3), 147–161.

プレイヤーにとっては、ここからひとつの便利な目安が導けます。「無限のレベル」という言葉からわかるのは、生成器があるということだけで、そのレベルがどうテストされているかはわかりません。ステージをどう確認しているかを説明しているゲームを探しましょう。そして難しさがでたらめに上下するときは注意してください。多くの場合、難しさを何もモデル化していないしるしです。

生成されたものかどうかにかかわらず、よくできたパズルのセットにはほかにもいくつかのしるしがあります。パズルのペース配分の研究がすすめるとおり、新しいアイデアがひとつずつ紹介されること。ピースをひとつ動かしただけのほぼコピーではなく、ステージごとに違いが感じられること。そして行き詰まったときに、解はあると信じられること。最後のひとつはごまかすのがいちばん難しく、生成器がもっとも長く勝ち取ろうとしてきたものです。

OutBrickの2,000ステージは、あなたのデバイス上で次々と生成されるものではなく、固定された、つくり込まれたセットです。そのすべてについて、リリース前にクリアのルートをゲーム自体のルールで再生して確かめています。ソルバーが計算の予算を使い切ったときに、それが「不可能」ではなく「不明」を意味する理由も含めて、そのプロセスは2,000のスライドパズルのステージをどう検証したかで説明しています。ソルバーが証明するのはルートが存在することであって、ステージが楽しいことではありません。だからペース配分は別に判断しています。その結果は今日のボードで確かめられます。