より良いバックトラッキングシステムをお探しの場合

Question

私はこれを簡単な言葉で説明しようとしています。私は正しい「移動命令」を選んでゲームを完了させなければならない再帰的な解決策の一部を作りました。そして、それが難局に陥った場合は、それを取り戻す必要があります。私の現在のシステムは、新しいパス/移動命令が見つかるまで、逆戻り中に再び使用することができないように動作していない移動に対して識別子を設定することによって動作します。

しかし、私は問題に遭遇しました。ゲームは2つの移動しか残っておらず、いずれもゲームを解決しない状態に到達することができる。私の現在のシステムは、基本的に、この2つの動きが連続的にスワップするようにします。なぜなら、解決策は動きを再生しようとし、動きませんと見て、次の動きを試みるからです。私の問題は、移動を行うたびに、移動を使用しないようにソリューションに指示する識別子をリセットしたことですが、それ以外の方法を設定するのはわかりません。

詳細情報が必要な場合や洞察力がある場合はお知らせください。ありがとう！

Answer 1

あなたが説明しているゲームの性質についてはわかりませんが、いくつかの情報があなたに従うためのより良い方法を決めるのに役立つかもしれません。新しい動きが見つかった後にこのインデックスがリセットされると言っているトピックであなたのコメントを見ました。これはとても良いとは言えません。私はあなたがこの問題を修正しなければならないと信じているのは、あなたの例から見たように、失敗するケースがあり、条件付きでしか動作しないアルゴリズムを持つことができないからです。

あなたの問題はゲームツリーのように聞こえるでしょうか？正しい？もしそうなら、問題の説明をゲームツリーに変更し、ゲームが敵対的であると仮定して、Alpha-Beta Pruningのような証明されたゲームツリー検索アルゴリズムの1つを利用しないのはなぜですか？