スネークゲームの経路探索アルゴリズム

スネークゲーム、ある領域内に蛇と餌があって、蛇は上下左右に移動でき、餌を食べると長さが1ずつ長くなっていく。蛇が壁にぶつかったり、自分自身にぶつかったら終了。
餌はここでは、蛇が餌を食べる度に、空いた空間のどこかに等確率で出現するとする。

このゲームを自動で行うようなアルゴリズムを考えていたのだが、意外に難しい。

まず前提として、最終的に詰まるまでの長さを最大化することを目的とし、餌の位置は、出現するまでは全くわからないものとする。

一番初めはbkzenさんのこれ。

これはよくわからないアルゴリズムを使っているが、割合はやく詰まってしまう。それも非常に哀れな詰み方で・・

これを改良して自分がつくったのがこれ。

A*を用いている。これで寿命は少し延びたが、餌を食べた時点で蛇の頭がある空間と次の餌のある空間が連結でない場合、経路を作れず詰む。これを防ぐために、できるだけ壁伝いに行くとか実装してみたが、それほど効果はなかった。

餌がどこに現れるのかわからないので、どこに餌が出てもそこに行く経路を作れれば良いが、それをそれ以前の餌を取りに行く状態で考えるのは非常に困難である。
とりあえず問題を緩和して、餌を食べた瞬間、空いている空間がすべて連結であればよいとする。この条件だけではまだ計算量があるので、さらに緩和して、途中でも空いている空間がすべて連結という条件をくわえる。これで各セルに経路が1個だけ対応するので、A*が使える。

この条件下でつくったものがこれ。デバッグ出力があるが気にしない。

これだとだいぶ寿命が延びている。直線的に進むよりも、ギザギザに進んだ方が空間を分断しにくい。

だが、なんとこれでも不十分なのである。これで詰まった状態を見ればわかると思うが、次の餌までの経路を探す途中で必ず連結性が崩れてしまう場合、詰まってしまう。これの解決方法は現在模索中・・