追加のアルファ ベータ プルーニング実装を備えた従来のミニマックス問題ソルバーがあります。
次の方法でアルゴリズムを並列化しました。
- 使用可能なスレッドよりも多くのノードが得られるまで、反復的な深化を行います
- N スレッドのバッチで、スレッドごとに 1 つのミニマックスを実行します。したがって、シリアル検索から深さ 2 で 9 つの可能な移動を取得した場合、最初に 4 つのスレッドを開始し、次に別の 4 つ、最後に 1 つを開始します。それぞれが独自のパラメーターを使用して深さ 2 から開始します。
4 スレッドのスピードアップ S=T(シリアル)/T(パラレル) は 4.77 であることが判明したため、基本的にここでアムダールの法則を破っています。
実装が何らかの形で壊れていないと言うなら、ここでアルファベータの剪定が魔法のように働いているのではないでしょうか? いくつかの検索を並行して開始するため、より多くの剪定が行われ、より早く? それは私の理論ですが、誰かがこれをより詳細に確認できれば幸いです。
明確にするために：
アルファベータ実装のない Minimax は、基本的にツリー全体の深さ優先検索を最大深さまで実行します。alpha-beta でも同じことを行っていますが、いずれにせよ悪い結果につながるいくつかの枝を剪定します。
編集: コードをさらに調べた後、コードの 1 行にバグがあり、プログラムが「チート」していくつかの動きに従わなくなりました。実際のスピードアップ係数は現在 3.6 です。皆さんの時間を無駄にして申し訳ありません.. 今日のコンピューティングにはブレークスルーがありません。:/