graph - AIスネークBFSの問題

Question

私はスネークボクシング自体の問題の解決に取り組んでいます。幅優先探索（BFS）を使用して移動すると、ボックスに入れられるリスクを大幅に減らすことができると思います。私の質問は、この動きが自分自身をボクシングにしないことを確認するために、いくつの可能な空のスペース（接続されている）を探す必要があるかです。

Answer 1

ゲームツリーを検索するために必要な深い動きの数は、ヘビが自分自身を取り囲むときに含めることができる正方形の領域に関連していると思います。たとえば、長さ12のヘビ：

----
|00|
|00|
91--

ヘビが（北に）上がる場合、それはまだ生きることができますが、それが東に行く場合に限ります。それが再び北に行くならば、それは死にます。

ヘビが収容できる最大面積は:(長さ/4-1）^2です。これが小数の場合は、おそらく切り上げたいと思うでしょう。

Answer 2

あなたが箱に入れられているかどうかを見なければならない距離は、常にヘビのサイズ/位置に依存します。100％確実にする唯一の方法は、すべての動きを事前に検索し、ヘビが箱に入れられるような動きを避けることです。とはいえ、幅優先探索よりも深さ優先探索の方が運が良いかもしれません。行き止まりをすばやく見つけます（存在する場合）。次に、それらの動きを避けます。2番目の例では、深さ優先探索により、「上」への移動が行き止まりであることがすぐにわかります。