単純なチェス エンジンを開発しようとしていますが、そのパフォーマンスに苦労しています。アルファ ベータ プルーニングと反復的な深化 (追加のヒューリスティックなし) を使用して 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 になるはずであると読んだので、順序が間違っているのではないかと思います。現在、次のように動作します。
- ゲーム ツリー ノードには、その子のリンク リストがあります。最初は、キャプチャとプロモーションが静かな動きの前に配置されます
- 検索中、アルファを増加させるか、カットオフを引き起こす子はリストの先頭に配置されます
- 深化の次の反復では、PV を最初に検索する必要があります
移動を注文するのは適切な方法で、私が得る分岐係数は予想されますか? 現在、位置の重要な違いのみを考慮した単純な静的評価関数を使用しています - カットオフ率が低い理由になるでしょうか (フィギュアの可動性も考慮すれば、同様の結果が得られます)。ヌル ムーブ リダクションやキラー ヒューリスティックなどの手法は、大幅に (10 ~ 15% ではなく、桁違いに) 役立ちますか? エンジンが強いとは思っていませんが、分岐係数を 6 程度にしたいと考えています。