現在のループコースパズルのソルバーはそこそこの定石ルールや大域定理を突っ込んでいるが、実は早期閉路に関しての検出が弱い。解けずにLookahead(先読み)ロジックに頼っている部分はたいがいループ検出ができていないからだ。
分析モードではLookaheadが動くから難しい問題も解けるが、問題生成時には動いていない(遅いから無効にしている)ので、生成する問題はそういう意味でソルバーの能力限界よりも簡単な問題となっている。それでも相当難しいのだが。LUTとGF2のせいで。
この問題についてGeminiさんに相談してみると、コリドー(Corridor)法と軽量Lookaheadを提案された。ここ数日、Geminiさんの提案はハズレが続いていたのだが、今回はよさげだなと実装してみた。
まずはコリドー法だが、これはゲーム他いろんな分野で使われるグラフ理論のアルゴリズムで、平たく言えば障害物を避けて行動できる範囲を先に計算しておく、みたいなやつだ。ループコースパズルで適用する場合、先に計算もなにもないので、エッジを一つ確定させたときに、その先のドットの周囲にxが2つあったら、そのまま先に進むことができる、という感じで、一本道を検出して線を引いて行って、エッジにぶつかったらループを調べる、みたいに使う。
これは実際、そこそこの効果があった。現状のLookaheadやGF2を削減するほどの効果は無いが、いままで検出できないループを検出することは確かにできた。ただ、ロジックの組み方に問題があったようで、非常に遅かった。
次にもう一つの軽量Lookaheadだが、これは現状の汎用Lookaheadがとても遅いことを嘆いた結果で、汎用LookaheadはGF2以外のルールを全て適用しながらバックトラックをするのが原因で時間がかかる。盤面の確定状態をコピーして保存して、戻す必要があるのも問題だ。
しかしLookahead時にGF2のような重い処理を使って確定させる必要が無かった(GF2を無効にしても効果が変わらなかった)というのは重要な情報で、つまり、先読みで矛盾を探す際には、難しいことを考える必要が無いことを意味する。
これを押し進めると、Lookahead時に大域定理は必要ない、となるが、これは昨日やってめっちゃ遅かったので却下済である。今日の軽量Lookaheadは極限まで押し進めた形となり、コリドー法を拡張したようなものになる。
既存のエッジから1手確定して進めるが、この時、マスの充足およびドットの制約に基づいて、線とxを確定させる(ここがコリドー法より進歩したところ)。これをスタックに積んでおいて、再帰で処理する。ダメだったら元に戻すが、この処理はスタックから戻すことにより、盤面のコピーを発生させない。また、線やxを確定させるときに矛盾を検出できるから、ループ検出だけではない。難しい定石ルールは一切無視、基本中の基本ルールのみを適用する。
これを実装した結果、いつもの職人パズルの分析結果は以下のようになった。いつもお世話になっています。本当にありがとうございます。
難易度9はGF2だけじゃなく、軽量Lookaheadもここに含まれている。従来の汎用Lookaheadが難易度10で、ほとんど発生しなくなった。簡単なルールを見るだけで先読みは大概が成り立つのである。逆に言えば、先読みが必要な職人パズルは先読み中に難しい定石を必要としないように設計されている。例えば先読み中にGF2のような理論を要求されれば現実的には先読み中の先読み、多段先読み化してしまう。それは無理ゲーだ。
またこの軽量Lookaheadは強烈に軽い。汎用Lookaheadと比べるまでもなく、コリドー法よりもはるかに軽く、他の大域定理よりも軽い。ループ検出関連、例えば仮想パスなども重い処理だが、これも場合によっては消してもいいかもしれない。ぐらいには速いし強い。
問題生成時に使うことを考えると、基本的に先読みなのでこれがあると難易度は跳ね上がる。ただ、先読み中の使用定石は基本ルールのみなので汎用Lookaheadを発動するよりも簡単だろうと言うことが想像できる。まあ職人パズルレベルだが。
難易度の調整は問題になるかもしれない。Masterだけにとどめておくべきか？まあ、最後にビルドしようとしたらGeminiさんがクォーターに達してしまったのでリリースはお預けなのだが。
AIが無いとビルドすらできない軟弱なエンジニアになってしまった。いや環境とかオプションとかがややこしくてな…
