問題タブ [alpha-beta-pruning]

反復的な深化を伴うアルファベータ検索を実装し、以前の深さ検索から得られた最初の最良の動きを検索することでアルゴリズムをさらに最適化するためのいくつかの手法を読みました。

私が理解している限り、以前の深さ検索からの主要なバリエーションを動的長さリストに保存できますか? たとえば、深さ 4 まで PV で検索したとします: [1, 0, 2, 3] は、深さ 1 で移動番号 1 を選択し、深さ 2 で移動番号 0 を選択し、深さ 3 で移動番号 2 を選択するなどを意味します。 ...そして、深さ 5 の検索では、アルゴリズムは最初にその前の深さ PV からノードの子を検索します。

それはあなたが反論テーブルと呼んでいるものですか？

このリンクからの反論テーブルの説明: 反復ごとに、検索により、ルートからリーフ ノードへの各移動のパスが生成され、その結果、正しいミニマックス スコアまたはその値の上限が得られます。d - 1 ply 検索からのこのパスは、d ply への検索の基礎として使用できます。多くの場合、現在の反復で調べられた最初のパスとして、前の反復のパスまたは動きの反論を検索すると、1 層深い動きを反駁するのに十分であることが証明されます。

それが同じでない場合、反駁表が実際に何であるかを説明できますか（私には両方が等しいように見えますが、よくわかりません）、最初に述べた方法の代わりに反駁表を使用する利点は何ですか?

ミニマックスとアルファベータ枝刈りの基本を理解しています。すべての文献で、最良のケースの時間計算量は O(b^(d/2)) であると述べています。ここで、b = 分岐係数、d = ツリーの深さであり、基本ケースはすべての優先ノードが最初に展開。

私の「最良のケース」の例では、4 レベルのバイナリ ツリーがあるため、16 のターミナル ノードのうち、最大で 7 つのノードを展開する必要があります。これは O(b^(d/2)) とどのように関係していますか?

どのようにして O(b^(d/2)) になるのかわかりません。

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

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

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

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

マンカラ ボード ゲームを実装し、そのための AI も実装する必要があるプロジェクトを実行する必要があります。

ゲームではプレーヤーが連続して複数のターンを持つ可能性があるため、mancala を使用できるようにするには、ミニマックス ツリーを修正または変更する必要があるとの指示を受けました。

ゲーム ロジックと GUI は既に実装していますが、AI を始める前に、AI の背後にある理論について少し考えてみたいと思います。ネットで非ターン ベースのミニ マックス ツリーを検索しましたが、何も見つからないようです。しかし、mancala に minimax を使用することについて多くの人が話しているのを見てきました。

これで、通常のミニマックス ツリーと、各レベルが最小ノードと最大ノードの間でどのように切り替わるかを理解できました。私が今必要としているツリーで、 min > max > max > min > max次のように言えますか?

また、Minimax ツリーの特定の層の深さを指定できる必要があります。アルファ ベータの枝刈りも必要ですが、それは実際に木ができてからの話です。

これは以前に尋ねられたことは知っていますが、これを理解することができませんでした。

コネクト 4 っぽいゲーム用に 7x7 のボードを持っています。

Minimax の Alpha Beta プルーニングを実装するために、このメソッドを定義しました。

それは私にヒューリスティックを返し、最善の動きを設定する必要があります。しかし、ボード上で利用可能な最後の手として、私は常に最善の手を得ています....

私が見逃しているかもしれない何かがここにありますか？

ありがとうございました！

Duchess http://www.cse.unsw.edu.au/~blair/duchess/rules.htmlと呼ばれるゲームのアルゴリズム/メソッドを探していました。

アルファ ベータのプルーニングを検討していますが、2 人以上のゲームに適用できるかどうかはわかりません。

キラーヒューリスティックの背後にある考え方と、それが役立つ理由を理解しています。私が苦労しているのは、アルファベータ検索ルーチンでそれを実装する方法です。特に、兄弟ノードのキラー ムーブのみが最初に試行されるようにするにはどうすればよいでしょうか? 擬似コードは非常に役立ちます。

私はチェスプログラムを開発しようとしています。ツリーの通常のブルートフォース検索になりますが、異なるのは評価だけです。最初は、Claude Shannon によって設計された標準のエバリュエーターを使用して、ベースで正常に機能するかどうかを簡単にテストできるようにします。リストの生成とその周りの他のすべてのインフラストラクチャを移動すると、正常に動作します。

検索については、 wikipediaのアルファ/ベータ プルーニング コード例を使用したいと思います。これがちょっとした問題です。1 つの点があいまいです。評価は誰の視点から行うべきか？私は何日も（文字通り）グーグルで検索してきましたが、これを明示的に示している例はありません。だから：評価は

• その深さの「現在のムーバー」の視点から
• その深さでの「現在の動きの相手」の視点から
• ツリーのルートにいるムーバーの視点から、たとえば、このツリー検索が行われている人 (AI プレーヤー)
• 木の根元にいるムーバーの相手の視点から

?

rootSide、side、rootOpponent、基本的にすべてのオプションを実験的に試してから、それらを互いに対戦させました。その結果、「その深さの現在のムーバー」が使用される (最も頻繁に勝利した) ことになりましたが、そのバージョンを他のエンジンに対してテストすると、100% の損失が発生しました。

もちろん、ウィキペディアはそれについてより明確になるように更新されます! （ウィキペディアの歴史の側面にあるメモは無視してください：それは私からのもので、間違っている可能性があるので削除しました）