問題タブ [negamax]

問題

alpha-beta-pruningを使用したnegamaxアルゴリズムを使用して、パーフェクト情報ゼロサム ゲーム (チックタックトーやチェスなど) を解決しようとしています。目標は、1 人のプレイヤーが勝利または引き分けを強制できるかどうかを証明することです。これは、深さ制限がないことを意味しますが、アルゴリズムは常に勝利/引き分けになるまでゲームツリーを評価します。

特定のゲームに合わせてコードを最適化するのに数週間を費やし、数日間のランタイムにまで落とし込みました。しかし、問題があります:

alpha-beta-pruning のため、minimax-algorithm の実行時間は非常に予測不可能です。実際にシミュレートするまで、次の 5 分で完了するか、さらに 5 週間実行されるかはわかりません。残りのランタイムを予測でき、桁違いにずれないようにしたいと考えています。

これまでに試したこと

すべてのサブブランチとサブサブブランチの結果を最大5* サブブランチまで記録し、マシンがそれらをシミュレートするのにかかった時間を記録しています。次に、同じレベルのポジションは評価に同じ時間がかかり、それを1日と呼ぶと仮定します. これらの予測は、10 倍以上ずれることがあります。

また、記録されたデータを調べて、私の仮定が成り立つかどうかを確認しました。5* サブブランチを評価するのに必要な時間は、 から0.01sまでさまざま180sでした。だからこそ、私の予測は外れています。誰がゲスしたでしょう。

私の質問

私が想像しているように、これはミニマックスのすべての実装に適用されます:

1. アルファベータプルーニングを使用してミニマックスアルゴリズムの残りのランタイムを正確に予測するための、より洗練されたアルゴリズムはありますか? それとも、ミニマックスは設計上予測不可能なのでしょうか?

2. もしそうなら、それらはどのように機能しますか？

これは私の最後の投稿のフォローアップです。コードはエラーなしで機能し、次善の策を計算できます。転置テーブルを組み込み、ネガマックス関数に順序を移動して、より高速かつ正確に実行する方法を検討してきましたが、私のような初心者にとってはやや難しく高度なようです。

私のコードはこちらにあります。

チェス プログラミング wiki を調べているときに、転置テーブルのサンプル コードを見つけました。

コードに統合するためにいくつかの変更を加えようとしましたが、結果は得られませんでした。位置の Zobrist キーを使用してハッシュ キーを保存することについても見たことがありますが、それがどのように機能するのかよくわからなかったので、アイデアを取り下げました。現在、これらの問題にいくらか行き詰まっており、次のステップが何であるかわかりません。