ホームページへ戻る恐怖の1000面パズル「XOR」を解く岸和田高校物理部プロジェクトチームが、ASCII誌(1987年7月号)上に発表したという恐怖の1000面パズルゲーム「XOR」のソルバープログラムを作ってみました。現在、このゲームは開発チームのひとりである安岡孝一さんのホームページにおいて、JavaScript版のXORが公開されており、ネット上から直接遊ぶことが可能です。このゲームがどのようなものなのか、是非２・３面解いてみてからこのページを読まれることをお勧めします。
ネット検索で調べてみると「XOR」というこのゲームは「エクサー」と呼ぶらしいです。 ルールの説明がちょっと不充分で「画面上のΩの周りをクリックしてΩを上下左右に動かし、道を制限歩数以内で塗りつぶして下さい。」としか書かれてなくて最初は戸惑いましたが、XORがエクスクルーシブ・オア、つまり「排他的論理和」を意味していると理解すると、このゲームのルールがよく見えてきます。 「空きマスに進入するとその地点が塗りつぶされ、塗りつぶされた地点に進入すると空きマスに戻ってしまう、という法則の元に総てのマスを塗りつぶして下さい。」ということになります。しかし、一見して一筆書きのようなゲームですが「排他的論理和」のルールが加わっただけで難易度は一気に高くなります。第１面から既に難しいと感じた人も多いと思います。
ソルバープログラムを作ろうと思えば、最初に思い付くのは幅優先探索か反復深化を使い最適解(最短歩数解)を求めたいと考えるのが一般的でしよう。しかし実際にやってみるとこのゲームの探索空間は想像以上に大きなものでした。 幅優先探索では直ぐにメモリーがパンクし、反復深化では何時間待っても答えが返ってきません。やり方が悪かったのではと言われるとそれまでですが、私は最適解を得ることを断念し、ヒューリスティックスな手法を用いることにしました。 何題か自力で解いてみるとこのゲームは、「本線(最も重要なルート)を見つける問題」と「本線が取りこぼした空きマスの穴埋め問題」に分割して考えることが出来る事に気付きます。
本線とは、一筆書きのルールに近く私は本線というものをこのように定義しました。
次に本線が取りこぼした空きマスの穴埋めですが、ひと繋がりの空きマスを「島」と呼ぶことにし、島の穴埋めを行う方法は大きく分けて２つの技法があるように思います。
方法１は２つの島の間を往復するのですから「２つの島の距離×２」ステップ消費することは明らかです。 しかし、方法２は少し複雑で２マスを埋めるのに消費するステップ数は２か４か６の場合があります。 空きマスには「一度も本線が通過していない空きマス」と「本線が偶数回通過して空きマスになった」ものがあります。２マス連続した空きマスを埋める場合、本線が一度も通過していないなら６ステップ必要ですが、２マスの内どちらかでも本線が通過したことのある場合は２ステップの消費で済みます。 そしてこの方法で連続した２マスを埋めていくと、島の形状に交差点を含む場合は島が分断されることがあり、その場合は方法１に習って２マス埋めるのに４ステップ消費する場合も生じます。
本線探索と穴埋めを別に扱っている関係で解の表示は下図の例のようにしています。本線はＳからＥまで進み、穴埋めの方は数字を丸で囲んであるものが方法１によるもので、数字は「ペア関係を識別する番号」になっています。「口」は方法２によるものですが本線が通過したことのある空きマスは「田」と表しています。
本線の終着点についてまだ触れていませんでしたが、これまでの話から本線の終着点と成り得るための条件が少し見えてきます。先ず、本線が最終的に取りこぼす空きマスの数は偶数でなければなりません。何故なら、穴埋めは常に２マス単位で行われるからです。 次に終着点は塗りつぶされた状態であるべきです。それは、本線が通過したことのある連続した２つの空きマスは２ステップで埋めることが出来るので、終着点が塗りつぶされていない状態は、その２ステップ前の状態と同値と言えるので無駄なのです。(間違いではありませんが)
ここから先の話は明確な理論というよりも、おそらくそんなもんだろうという話になるのですが、ドーナツ状のループした島がまだ残っている場合は本線を終了させるには早すぎます。２マス消すのに６ステップも消費するような穴埋めをするよりも、ドーナツ状の島は本線を通過させて埋めていった方がずっと得策だと思われるからです。
穴埋め時に２マスを２ステップで埋めることが可能な場合があるので、枝刈りとしては、
本線探索には最良優先探索を使用しましたが、本線は交差しない方が評価が高いという程度のものです。 それから、方法１による穴埋めはバックトラッキングを使い、方法２よる穴埋めは演繹的な方法(制約伝播)を使いました。 XORの作者(特にランキング登録によるHPを開設している安岡さん)に迷惑がかかるので、私の書いたプログラムを公開することは出来ませんが、全1000面を解くことに成功しています。 ヒューリスティックスな手法なので最適解の保証はありませんが、解けなくなるまで制限歩数を４ステップずつ小さくして探索を繰り返すと最適解に限りなく近い解を求めることも可能になります。(下の追記を参照)
尚、このページでの説明は主要な部分だけを書きました。実際にはかなり細かい部分にまで様々なアイデアを投入しないと全問制覇は困難かと思われます。そういった部分に関してはここでは触れませんし質問されてもお答えできません。
私のソルバープログラムに「buzzstyle」という名前を付けて、問題面の収集とソルバープログラム開発を目的として全1000面を解かせてみた結果を下に置きました。 それから、解けなくなるまで制限歩数を小さくして行く方法で解かせたソルバー「RingMyBell」を実行させた結果も置いておきます。★印のあるものは制限歩数を下回って解けてしまったもので、合計で63面の制限歩数を更新しましたが、制限歩数を更新すると安岡さんのHPでの制限歩数が自動で更新記録に書き換えられる仕組みになっているようです。従って、RingMyBellが通過してしまった今の状態からの制限歩数の更新は、かなり困難かも知れません。(不可能という意味ではありません)
このページの公開にあたって、安岡孝一さんの承諾を頂くことが出来ました。心より感謝申し上げます。 それにしても全1000問とは、まさに恐怖をいう形容詞が見事に当てはまります。面の作者が約２０名いたようですが、量だけの問題ではなく内容的にも関心させられる問題が多数あり、とても楽しませて頂きました。ありがとうございます。 尚、今回の私のプログラムには理論的に曖昧な部分が幾つかあり、それが心残りです。機会があれば「完全最適解」を目指して再チャレンジしてみたいと思っています。
最適解に近い解を求める時、制限歩数を「４ステップずつ小さくしてよい」という報告が、としひでさんからありました。ありがとうございます。
ところがその後、安岡孝一さんを通して、本家のＸＯＲ開発チームがゲーム制作中の1985年頃に、この事は既に発見していて、より明快なその証明方法と、さらにもう１つの規則性があることを教えて頂きました。ここをご覧下さい。
ホームページへ戻る |