問題
alpha-beta-pruningを使用したnegamaxアルゴリズムを使用して、パーフェクト情報ゼロサム ゲーム (チックタックトーやチェスなど) を解決しようとしています。目標は、1 人のプレイヤーが勝利または引き分けを強制できるかどうかを証明することです。これは、深さ制限がないことを意味しますが、アルゴリズムは常に勝利/引き分けになるまでゲームツリーを評価します。
特定のゲームに合わせてコードを最適化するのに数週間を費やし、数日間のランタイムにまで落とし込みました。しかし、問題があります:
alpha-beta-pruning のため、minimax-algorithm の実行時間は非常に予測不可能です。実際にシミュレートするまで、次の 5 分で完了するか、さらに 5 週間実行されるかはわかりません。残りのランタイムを予測でき、桁違いにずれないようにしたいと考えています。
これまでに試したこと
すべてのサブブランチとサブサブブランチの結果を最大5* サブブランチまで記録し、マシンがそれらをシミュレートするのにかかった時間を記録しています。次に、同じレベルのポジションは評価に同じ時間がかかり、それを1日と呼ぶと仮定します. これらの予測は、10 倍以上ずれることがあります。
また、記録されたデータを調べて、私の仮定が成り立つかどうかを確認しました。5* サブブランチを評価するのに必要な時間は、 から0.01sまでさまざま180sでした。だからこそ、私の予測は外れています。誰がゲスしたでしょう。
私の質問
私が想像しているように、これはミニマックスのすべての実装に適用されます:
アルファベータプルーニングを使用してミニマックスアルゴリズムの残りのランタイムを正確に予測するための、より洗練されたアルゴリズムはありますか? それとも、ミニマックスは設計上予測不可能なのでしょうか?
もしそうなら、それらはどのように機能しますか？