問題タブ [iterative-deepening]

私は通常の二分木を持っており、 c を使用して反復的な深さの最初の検索を適用しようとしています:

ノードをツリーに挿入する関数を使用していますが、検索関数を次のように実装する必要があります。つまり、 function search(root,goal,maxLevel) 深さ優先検索を使用して検索しますが、特定の最大レベルまで検索してから停止します。これは私の最初の試みでした。作業:

助けてください、ありがとう...

単純なチェス エンジンを開発しようとしていますが、そのパフォーマンスに苦労しています。アルファ ベータ プルーニングと反復的な深化 (追加のヒューリスティックなし) を使用して Negamax を実装しましたが、3 ～ 4 層を超える妥当な検索時間を得ることができません。以下は、ゲーム開始時のプログラム ログからの抜粋です。

分岐係数が約 10 であることを示しています。適切な移動順序で約 6 になるはずであると読んだので、順序が間違っているのではないかと思います。現在、次のように動作します。

1. ゲーム ツリー ノードには、その子のリンク リストがあります。最初は、キャプチャとプロモーションが静かな動きの前に配置されます
2. 検索中、アルファを増加させるか、カットオフを引き起こす子はリストの先頭に配置されます
3. 深化の次の反復では、PV を最初に検索する必要があります

移動を注文するのは適切な方法で、私が得る分岐係数は予想されますか? 現在、位置の重要な違いのみを考慮した単純な静的評価関数を使用しています - カットオフ率が低い理由になるでしょうか (フィギュアの可動性も考慮すれば、同様の結果が得られます)。ヌル ムーブ リダクションやキラー ヒューリスティックなどの手法は、大幅に (10 ～ 15% ではなく、桁違いに) 役立ちますか? エンジンが強いとは思っていませんが、分岐係数を 6 程度にしたいと考えています。

反復的な深化 (増分ツリー構築) を実装したい。これは、私が尋ねる私のコードの一部です:

時間制限のある invokeAny() について読んだことから、期限に達するとすぐに Callable オブジェクトの実行を終了する必要があります。関数 iterativeDeepening(depthLimit, board) の代わりにロングスリープを設定すると機能します。私の機能でそれを機能させるにはどうすればよいですか？以下に、この関数にコードを貼り付けます。

それを行うためのより良い方法を知っているか、関数の実行を正常に停止する方法を知っている場合は、お知らせください。このトピックで言及されているRunnable Interfaceも試しました： Javaで特定の時間後に実行を停止する方法は? しかし、それは同じように機能しました。

^{私は、一般に O(b m} ) で動作するツリー トラバーサル アルゴリズムを持っています。ここで、b は分岐係数、m は最大深度です。

反復深化を使用して、このアルゴリズムは深さを増やしながら m 回繰り返し実行されます。

O(b ^m ) = b⁰ + b¹ + b² + ... + b ^m

時間の複雑さに関する私の限られた理解に基づいて、最大の要素を採用します。これは、時間の経過とともに最も重要な要素であるためです。その要素は b ^mになります。ここで、m は到達した最大深度です。

^{したがって、その知識があれば、反復深化アルゴリズムも O(b m} )で実行されると結論付けます。

ただし、論理的な観点から、アルゴリズムが深さmで1回実行されるか、深さmまでm回実行されるかにかかわらず、ツリートラバーサルがまったく同じ時間の複雑さを持つ方法を理解するのに苦労しています。

b ^mは本質的に Σ _k=0,..,m b ^kより小さくなります。したがって、反復深化の時間計算量は高くするべきではありませんか?

それとも、私が理解できない何かがありますか？

私は、コンピューター チェス プログラムのアルファ ベータ検索の主要なバリエーションを使用した反復的な深化の実装に取り​​組んでおり、検索の時間制限を含めることを望んでいました。たとえば、深さ 5 の検索の途中で制限時間に達した場合の結果について疑問に思っていました。この不完全な検索で新しい主要なバリエーションが見つかった場合、少なくとも深さ 4 での完全な検索によって見つかった主な変化は? そうでなければ、深さ 5 の不完全な検索で見つかったものをすべて破棄する必要があるようです。

Prolog でゴール検索エージェントを作成しています。という名前の述語が 2 つありsearchます。問題のある場所Type == exploreと他の場所にありType == climbます。
使用される深さは定数 = 10 であることに注意してください。プログラムはすべてのテスト ケースに対して正しいパスを提供していましたが、最短ではなかったので、ここからを使用するというアイデアを得ましたlength(Actions,_)。
最初のsearch述語にはうまく機能しますが、後者の検索述語を満たすために同様のものを追加しようとするとType == climb、無限ループに陥り、時間がかかりすぎます。これは私がそのために持っていたものです：

なぜこうなった？

完全なコードは次のとおりです。

編集:
わかりました、指定されている「深さ」に関連していることがわかりました。MaxDepthから制約を削除しましたdepthfirstが、現在は機能しています。ただし、元の深さ優先は指定された深さで解決策を見つけていましたが、なぜ反復深化を使用してそれを行うことができないのですか?私が指定した方法で行ったのですか?

DFS 検索があり、この DFS で反復的な深化検索を実装しようとしていますが、何をすべきか本当にわかりません。私は多くの方法を試しましたが、最終的にそれが間違っていることがわかりました! どのような変更を行うべきかについて何か提案はありますか?