さて、私はしばらくの間チェス プログラムに取り組んできましたが、壁にぶつかり始めています。私はすべての標準的な最適化 (ネガスカウト、反復的深化、キラー ムーブ、ヒストリー ヒューリスティック、静止検索、ポーン位置評価、いくつかの検索拡張) を実行しましたが、アイデアがすべて尽きました!
私はすぐにそれをマルチスレッド化することを検討しており、それによってパフォーマンスが大幅に向上するはずですが、それ以外に、皆さんが見つけた気の利いたトリックはありますか? MDF(f) への切り替えを検討しましたが、面倒で割に合わないと聞きました。
私が最も興味を持っているのは、ある種の学習アルゴリズムですが、チェスプログラムで効果的にそれを行った人がまだいるかどうかはわかりません。
また、ビットボードへの切り替えは重要ですか？私は現在0x88を使用しています。
私のチェスエンジン（www.chessbin.com）の開発の最後の年の間、より良くそしてより速い動きの検索を可能にするために私のコードを最適化することに多くの時間が費やされました。その間、私はあなたと共有したいいくつかのトリックを学びました。
性能測定
基本的に、次の2つの方法でパフォーマンスを向上させることができます。
コード最適化の最初の問題は測定です。あなたが本当に違いを生んだことをどうやって知っていますか？この問題を解決するには、移動検索中にいくつかの統計を記録できることを確認する必要があります。チェスエンジンでキャプチャするものは次のとおりです。
これにより、変更のベンチマークとテストが可能になります。テストに取り組む最良の方法は、オープニングポジション、ミドルゲーム、エンドゲームからいくつかのセーブゲームを作成することです。黒と白を検索したノードの時間と数を記録します。変更を加えた後、私は通常、上記のセーブゲームに対してテストを実行して、上記の2つのマトリックス（検索されたノードの数または速度）が改善されたかどうかを確認します。
さらに複雑なことに、コードを変更した後、エンジンを3回実行し、毎回3つの異なる結果を得ることができます。あなたのチェスエンジンが9、10、11秒で最高の動きを見つけたとしましょう。それは約20％の広がりです。それで、エンジンを10％〜20％改善しましたか、それともPCの負荷を変化させただけでしたか。どうして知っていますか？これと戦うために、エンジンがそれ自体と対戦できるようにするメソッドを追加しました。これにより、白と黒の両方が動きます。このようにして、1回の移動での時間の変動だけでなく、ゲームの過程で50回もの一連の移動をテストできます。前回のゲームに10分かかり、現在は9分かかる場合は、エンジンが10％向上した可能性があります。テストを再度実行すると、これを確認できます。
パフォーマンスの向上を見つける
パフォーマンスの向上を測定する方法がわかったので、潜在的なパフォーマンスの向上を特定する方法について説明します。
.NET環境を使用している場合は、.NETプロファイラーが友だちになります。Visual Studio for Developersエディションをお持ちの場合は、無料で組み込まれていますが、他にも使用できるサードパーティツールがあります。このツールを使用すると、エンジンがほとんどの時間を費やしている場所がわかり、問題のある場所に集中できるため、作業時間を節約できます。プロファイラーツールがない場合は、エンジンがさまざまな手順を実行するときに、何らかの方法でタイムスタンプをログに記録する必要があります。私はこれを提案しません。この場合、優れたプロファイラーは金でその重量に見合う価値があります。Red Gate ANTS Profilerは高価ですが、私が今まで試した中で最高のものです。余裕がない場合は、少なくとも14日間のトライアルに使用してください。
あなたのプロファイラーはあなたのために物事を確実に識別します、しかしここに私がC＃で働くことを学んだいくつかの小さな教訓があります：
さらなるパフォーマンスの向上：
ムーブの生成と順序付けは非常に重要だと思います。しかし、私が見ているように、ここに問題があります。アルファベータを並べ替えて実行する前に各移動のスコアを評価すると、移動の順序を最適化して、非常に迅速なアルファベータカットオフを取得できます。これは、ほとんどの場合、最初に最善の動きを試すことができるためです。ただし、各移動の評価に費やした時間は無駄になります。たとえば、20の手でスコアを評価し、最初の2つの手で並べ替えて、手番号2のカットオフを受け取ったとします。理論的には、他の18の手で費やした時間は無駄になります。
一方、キャプチャだけと言って、より軽くてはるかに高速な評価を行う場合、ソートはそれほど良くなく、より多くのノードを検索する必要があります（最大60％多く）。一方、あなたはすべての可能な動きについて重い評価をすることはありません。全体として、このアプローチは通常より高速です。
適切な並べ替えに十分な情報を用意することと、使用しない移動で余分な作業を行わないことのこの完璧なバランスを見つけることで、検索アルゴリズムに大きなメリットを見つけることができます。さらに、より貧弱なソートアプローチを選択した場合は、最初に浅い検索、たとえば3を重ねて、より深い検索に入る前に移動をソートする必要があります（これは反復深化と呼ばれることがよくあります）。これにより、並べ替えが大幅に改善され、検索する動きがはるかに少なくなります。
古い質問に答えます。
作業用の転置テーブルが既にあると仮定します。
レイトムーブの削減。これにより、私のプログラムは約 100 の elo ポイントを獲得でき、実装は非常に簡単です。
私の経験では、実装が非常に非効率的でない限り、実際のボード表現 (0x88、ビットボードなど) はそれほど重要ではありません。
パフォーマンスの悪いチェス エンジンを無効にすることはできますが、電光石火の速さのジェネレーター自体がプログラムを優れたものにすることはありません。
使用される検索トリックと評価関数は、全体の強さを決定する圧倒的な要素です。
そして、評価の最も重要な部分は、マテリアル、パスされたポーン、キングの安全性、およびポーンの構造です。
検索の最も重要な部分は、Null Move Pruning、Check Extension、Late Move 削減です。
これらの単純なテクニックだけで、あなたのプログラムは長い道のりを歩むことができます!
古い質問ですが、5 年前と同じ手法が適用されます。私たちは皆、独自のチェス エンジンを作成しているわけではありません。私は「Norwegian Gambit」と呼ばれる独自のエンジンを持っており、最終的には CCRL で他の Java エンジンと競合することを期待しています。Stockfish は非常にうまく書かれており、オープンであるため、私と同じように多くの人がアイデアを得るために Stockfish を使用しています。彼らのテスト フレームワークである Fishtest とそのコミュニティからも、多くの適切なアドバイスが得られます。評価方法はおそらくチェス プログラミングの最大の未知数であり、Stockfish は都市伝説となった多くの伝統的な eval (ダブル ビショップ ボーナスなど) から離れているため、自分の評価スコアを Stockfish が取得するものと比較する価値があります。ただし、最大の違いは、あなたが言及したのと同じテクニック、ネガスカウト、TT、LMR、
忘れがちなことの 1 つは、適切な移動順序です。アルファ ベータ カットオフが効率的であるためには、最初に最良の動きを得ることが不可欠です。一方で、時間がかかる場合もあるため、必要な場合にのみ行うことが不可欠です。
並べ替えは必要に応じて実行する必要があります。通常は、キャプチャを並べ替えるだけで十分です。その後は、必要な場合にのみ、よりコストのかかるチェックの並べ替えと PSQT を実行できます。
Java のプログラミング手法は、C# を使用した Adam Berent による優れた回答と同じです。彼のリストに加えて、プリミティブの多くの配列を使用するのではなく、オブジェクト配列を回避することについて言及しますが、バイトを使用するという彼の提案に反して、64ビットのJavaでは、64ビットの長さの代わりにバイトとintを使用して保存するものはほとんどないことがわかりました。また、C/C++/Assembly に書き直す道をたどりましたが、パフォーマンスはまったく向上していません。LZCNT や POPCNT などのビットスキャン命令にはアセンブリ コードを使用しましたが、Java 8 も Long オブジェクトのメソッドの代わりにそれらを使用していることが後でわかりました。驚いたことに、Java の方が高速です。Java 8 仮想マシンは、C コンパイラよりも優れた最適化を行っているようです。
仕上げの巨大なデータベースを持っている大学の AI コースで話された 1 つの改善点を知っています。そのため、少数の数字しか残っていないゲーム用の事前計算されたデータベースがあります。そのため、検索でニアエンドのポジショニングにヒットした場合は、検索を停止し、事前に計算された値を取得して、計算時間をあまり費やさずに重要/批評の動きに対して実行できる追加の深化などの検索結果を改善します。ゲーム後半の状態でのヒューリスティックスの変化も伴うと思いますが、私はチェスプレイヤーではないので、ゲーム終了のダイナミクスはわかりません.
かなり古い質問です。チェスに関する質問を検索していたところ、この質問には回答がありませんでした。今は何の役にも立たないかもしれませんが、他のユーザーには役立つかもしれません。
null 移動プルーニング、転置テーブルは見ませんでした..それらを使用していますか? 彼らはあなたに大きな後押しをするでしょう...
私に大きな後押しをしたことの 1 つは、条件分岐を最小限に抑えることでした...多くのことを事前に計算できます。そのような機会を探してください。
最近のほとんどの PC には複数のコアが搭載されているため、マルチスレッド化することをお勧めします。そのために必ずしもMDF（f）に行く必要はありません。
コードをビットボードに移動することはお勧めしません。単純に仕事が多すぎる。ビットボードは 64 ビット マシンを強化することができますが。
最後に、そして最も重要なことは、チェスの文献が、使用する可能性のある最適化を支配することです。最適化は大変な作業です。オープン ソースのチェス エンジン、特に狡猾でフルーツ/トーガに注目してください。Fruit は当初、オープンソースでした。
スレッド化された環境でゲーム検索を正しく行うことは、王様の苦痛になる可能性があることに注意してください (私はそれを試しました)。それは可能ですが、私がしばらく前に行ったいくつかの文献検索から、それから速度を向上させることは非常に困難です.
ヒントとしては、eval 関数の前に移動生成ルーチンを最適化することで大きな効果が得られることを私は知っています。その関数を可能な限りタイトにすることで、ノード/秒を 10% 以上改善できます。
ビットボードに移行する場合は、rec.games.chess.computer アーカイブを掘り下げて、ロバート ハイアット博士の Crafty に関する古い投稿を探してください (彼はもう投稿していないはずです)。または、彼の FTPから最新のコピーを入手して、調査を開始します。でも、それはあなたにとって大きな変化になると確信しています。
プロファイルとベンチマーク。理論上の最適化は優れていますが、変更を加えるたびにパフォーマンスへの影響を測定していない限り、作業によって最終的なコードの速度が向上しているのか低下しているのかを知ることはできません。
さまざまなアルゴリズムを試すことによるペナルティを自分自身に制限するようにしてください。アルゴリズムのさまざまな実装を相互に簡単にテストできるようにします。つまり、コードの PVS バージョンと NegaScout バージョンを簡単にビルドできるようにします。
ホット スポットを見つけます。リファクタリング。必要に応じてアセンブリで書き換えます。繰り返す。
「ヒストリー ヒューリスティック」が過去の動きのある種のデータベースを含むと仮定すると、学習アルゴリズムは、同じプレイヤーに対して多くのゲームをプレイしない限り、それ以上のものを提供することはありません。プレーヤーを分類し、履歴データベースからの動きの選択を微調整することで、おそらくさらに多くのことを達成できます。