15

速度の数パーセントを与える小さな最適化には興味がありません。私は、アルファベータ検索の最も重要なヒューリスティックに興味があります。そして、評価関数の最も重要なコンポーネント。

私は、(改善/コードサイズ) 比率が最大のアルゴリズムに特に興味があります。（ない（改善/複雑さ））。

ありがとう。

PS Killer ムーブ ヒューリスティックは完璧な例です。実装が簡単で強力です。ヒューリスティックのデータベースは複雑すぎます。

4

8 に答える 8

13

すでに認識しているかどうかはわかりませんが、Chess Programming Wikiをチェックしてください。これは、現代のチェス AI のほぼすべての側面をカバーする優れたリソースです。特に、あなたの質問に関連して、メイン ページの検索と評価のセクション (主要なトピックの下) を参照してください。また、ここにリストされているプログラムのいくつかで使用されている興味深いテクニックを発見できるかもしれません。あなたの質問がまだ答えられない場合は、Chess Programming Forumsで質問することを強くお勧めします. (ここで必ずしも良い答えが得られるとは限りません。トピック固有の専門家フォーラムで得られる可能性が高いというだけです)。

于 2009-02-07T12:54:14.100 に答える
4

MTD(f)またはMTD バリアントの 1 つは、標準の alpha-betaよりも大幅に改善されています。ただし、評価関数に非常に詳細な情報がなく、キラー ヒューリスティックを使用していると仮定した場合です。履歴ヒューリスティックも役立ちます。

最高評価のチェス プログラムRybkaは、明らかに MDT(f) を放棄し、非 PV ノードの吸引ウィンドウがゼロのPVSを採用しました。

通常の無益な剪定と深い剃刀の両方を組み込んだ拡張無益な剪定は、理論的には不健全ですが、実際には非常に効果的です。

反復深化は、もう 1 つの有用な手法です。そして、私は多くの優れたチェス プログラミング リンクをここにリストしました。

于 2009-02-07T19:41:44.807 に答える
2

ヒューリスティックに基づく多くの最適化 (実際に検索せずにツリーの深さを増やす方法を意味します) がチェス プログラミングの文献で議論されていますが、それらのほとんどはめったに使用されていないと思います。その理由は、理論上は優れたパフォーマンス ブースターですが、実際にはそうではないからです。

場合によっては、これらのヒューリスティックが悪い (最善ではない) 動きを返すこともあります。

私が話した人々は、他のヒューリスティックを追加しようとするのではなく、アルファベータ検索を最適化し、コードに反復的な深化を実装することを常に推奨しています.

主な理由は、コンピューターの処理能力が向上していることであり、研究[引用が必要] は、CPU 時間をフルに使ってアルファ ベータ ツリーを最大の深さまでブルート フォースするプログラムは、分割するプログラムよりも常に実行速度が速いことを示しています。特定のレベルのアルファベータとその後のヒューリスティックの間の時間。

いくつかのヒューリスティックを使用してツリーの深さを拡張すると、害が生じる可能性がありますが、アルファ ベータ検索アルゴリズムに追加できる多くのパフォーマンス ブースターがあります。

アルファベータが意図したとおりに正確に機能するためには、移動ソートメカニズム（反復深化）が必要であることを認識していると思います。反復的な深化により、パフォーマンスが約 10% 向上します。

アルファ ベータに主要なバリエーション検索手法を追加すると、さらに 10% のブーストが得られる場合があります。

MTD(f ) アルゴリズムも試してください。また、エンジンのパフォーマンスを向上させることもできます。

于 2009-02-07T16:09:42.553 に答える
1

言及されていないヒューリスティックの 1 つは、Null move pruningです。

また、Ed Schröder は、彼が Rebel エンジンで使用した多くのトリックと、それぞれが速度/パフォーマンスにどの程度の改善をもたらしたかを説明する素晴らしいページを持っています: Inside Rebel

于 2009-02-10T01:18:41.343 に答える
1

ゾブリスト ハッシュで転置テーブルを使用する

[移動または移動解除ごとに 1 つの XOR と、ゲーム ツリーで再帰する前の if ステートメント] を実装するのに必要なコードはごくわずかであり、特に反復的な深化を既に使用している場合は、かなり調整可能です (より大きなテーブル、より小さなテーブル、代替戦略など)

于 2009-02-10T01:29:54.750 に答える
0

ほとんどのボード ゲーム AI アルゴリズムは、 http://en.wikipedia.org/wiki/Minmax MinMaxに基づいています。目標は、オプションを最大化しながら、オプションを最小化することです。Chess の場合、これは非常に大きくコストのかかる実行時の問題です。これを減らすために、minmax を以前にプレイしたゲームのデータベースと組み合わせることができます。ボードの位置が似ていて、自分の色のレイアウトがどのように獲得されたかというパターンが確立されているゲームは、次にどこに移動するかを「分析」する限り使用できます。

改善/コードサイズの意味について少し混乱しています。あなたは本当に改善/ランタイム分析（大きなO（n）対o（n））を意味していますか？その場合は、IBM とビッグ ブルー、または Microsoft の Parallels チームに相談してください。PDC で、対戦相手 1 人あたり 8 コアを使用して麻雀を実演していた男 (名前も忘れてしまいました) と話をしました。

私は、常にチェスに勝って非常に速く勝つための「定型化された」アルゴリズムは存在しないと思います。あなたがそれをしなければならない方法は、非常に大規模な辞書ベースのデータベースで索引付けされたすべての可能な以前にプレイしたゲームを持ち、すべてのゲームの分析を事前にキャッシュすることです. それは非常に複雑なアルゴリズムであり、私の意見では、改善/複雑さの問題は非常に貧弱です。

于 2009-02-07T17:51:47.027 に答える
0

少し話が逸れるかもしれませんが、「最先端」のチェス プログラムでは、Deep Blue などの MPI を使用して大規模な並列処理能力を実現しています。

並列処理が現代のチェスで大きな役割を果たしていることを考えてみてください

于 2009-02-10T01:28:41.350 に答える
0

キラー ムーブは、コード サイズが小さく、ムーブ順序が大幅に改善された好例です。

于 2009-02-07T16:20:36.743 に答える