8

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

2013-05-11 18:22:06,835 [9] INFO  CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 1
2013-05-11 18:22:06,835 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 28
2013-05-11 18:22:06,835 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 28
2013-05-11 18:22:06,835 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: A4->A6 
2013-05-11 18:22:06,835 [9] INFO  CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 2
2013-05-11 18:22:06,897 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 90
2013-05-11 18:22:06,897 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 118
2013-05-11 18:22:06,897 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: A2->A3 B7->B6 
2013-05-11 18:22:06,897 [9] INFO  CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 3
2013-05-11 18:22:08,005 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 6027
2013-05-11 18:22:08,005 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 6414
2013-05-11 18:22:08,005 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: A2->A3 A6->B8 A4->A7 
2013-05-11 18:22:08,005 [9] INFO  CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 4
2013-05-11 18:22:10,485 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 5629
2013-05-11 18:22:10,485 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 6880
2013-05-11 18:22:10,485 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: D2->D4 A6->B8 C4->C5 A7->A6 
2013-05-11 18:22:10,485 [9] INFO  CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 5
2013-05-11 18:22:34,353 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 120758
2013-05-11 18:22:34,353 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 129538
2013-05-11 18:22:34,353 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: D2->D4 A6->B8 C4->C5 A7->A6 A4->A6 

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

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

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

4

2 に答える 2

39

私も C# でチェス エンジンを開発しましたが、分岐係数は約 2.5 です。エンジンを桁違いに改善することは間違いなく可能です。現在の一般的な戦略は、適切な移動順序に基づいて非常に積極的な移動プルーニングを使用することです。いくつかの深い戦術的な線を見ることができるようにするために、いくつかの正確さを犠牲にします.

以下は、私が最も効果的であるとわかったテクニックの概要です。一部のコンポーネントは補完的であり、他のコンポーネントは代替品であることに注意してください。したがって、ここで示す結果は一般的なガイドラインです。強力な基盤がなければ、リストの最後にある大きな利益は得られません。

  1. alpha-beta pruningでちょうどnegamax : 3 秒以内に深さ 4。

  2. 反復深化ヌル移動ヒューリスティックを追加します: 深さ 5. 反復深化はこの時点ではあまり役に立ちませんが、実装は簡単です。ヌル ムーブは、ターンをスキップして、浅い検索でまだベータ カットオフを取得できるかどうかを確認することで構成されます。可能であれば、ほとんどの場合移動する方が有利であるため、木を剪定しても安全です。

  3. キラー ヒューリスティック: 深度 6。これには、ベータ カットオフを引き起こす動きを保存し、次に同じ深度にいるときに合法である場合に最初に試すことが含まれます。あなたはすでに似たようなことをしているようです。

  4. MVV/LVA の順序付け: 深さ 8. 基本的に、多くの潜在的なマテリアル ネット ゲインを持つキャプチャをムーブ リストの一番上に配置します。したがって、ポーンがクイーンを捕まえた場合、明らかに最初にそれを検索する必要があります。

  5. ビットボード表現: 深さ 10. これは分岐係数を改善しませんが、これは私がこの時点に到達したときに行ったことです。配列をUInt64捨てて、代わりに s を使用し、copy-make の代わりに make/unmake を使用します。難しい場合は、マジック ビットボードを使用する必要はありません。まだ非常に高速な、より単純な方法があります。ビットボードはパフォーマンスを大幅に向上させ、評価コンポーネントの作成を容易にします。私は perft(6) 数分から 3 秒かかりました。(ちなみに、perft 関数を記述することは、移動生成の正確性を確保するための優れた方法です)

  6. 移調表: 深さ 13。これは大きな利益をもたらしますが、正しく設定するのも非常に困難です。テーブルを実装する前に、位置ハッシュが正しいことを絶対に確認してください。利点のほとんどは、テーブルが提供する驚くべき順序付けから得られます。常に最良の動きをテーブルに保存し、一致する位置を取得したら、最初に試してください。

  7. レイト ムーブ リダクション: 深度 16。これにより探索深度が大幅に増加しますが、強度の増加は他のテクニックよりも人工的です。基本的に、移動順序は非常に優れているため、ノード内の最初の数移動のみを完全に検索する必要があり、浅い検索で他の移動を確認するだけで済みます。

  8. 無益な剪定: 深さ 17. リーフ ノードは、潜在的なマテリアル ゲインを調べるときに、ノードの値を改善する可能性が低い移動をスキップすることによってトリミングされます。移動の正味の潜在的ゲイン + 位置の静的評価が現在の位置の値を下回っている場合、移動の評価をスキップします。

他にも役立つさまざまなコンポーネントがありますが、ほとんどはマイナーであり、独自のものもあります。:D ただし、検索深度が高く、分岐係数が低いことがすべてではありません。静止検索のようなものは検索の深さを悪化させますが、どのエンジンにもほとんど必要です。これがないと、エンジンは大きな戦術的エラーに悩まされます。また、チェック拡張機能シングル リプライ拡張機能を検討することもできます。また、少なくとも正方形のテーブルを導入することをお勧めしますあなたの評価関数に。これは、プログラムの位置に関する知識を大幅に向上させる非常に簡単な方法です。おそらく、エンジンがより一般的な開口部を再生するのを見るでしょう。チェスのプログラミングは楽しい趣味であり、情報量の多さに落胆しないことを願っています!

于 2013-05-20T04:50:54.763 に答える