マルチスレッドアルファベータプルーニングの効果は何ですか？

Question

アルファベータプルーニングを使用したマルチスレッドの有効性は次の場合になります。

マルチスレッドは繰り返し使用されました。たとえば、1は最初の分岐になり、スレッド、2番目のスレッドが他の深さは、可能性があるため、私は、これが唯一の第1の深さ（次の一手製AI）で行うべきであると考えているなど、第二のスレッドを見てしまいます断つ。

1つのスレッドが生成されたハーフmovesetに検索生成された最初の「移動」であった、そして第二のスレッドが生成された最後の「移動」であったと後半movesetに検索します。ここで、私はそこに最後の移動が最善手と見なされる可能性があるため、高速化を増加させることができ、結果として、第二のスレッドが最初のスレッドができなかったカットオフを引き起こす可能性があると思います。

マルチスレッディングは、相手の時間を考えるために使用されました。たとえば、相手が考えて行動を起こすのに時間がかかったとします。 AIは、反復的に、私は必ずしも高速化を引き起こしますが、ミニマックス解析のために多くの時間を持っていない、想像、その検索を深め、相手が考えている間に結果を見つけることができます。

は、私が想像する、他の最適化があるかもしれませんが、これらは、心に入ってきたという少数でした。彼らが実際に何かを改善するかどうかはわかりません。

Answer 1

私があなたの考えを正しく理解していれば、ルートポジションでの動きを並行して検索することを計画しています。厳密にシーケンシャルなアルゴリズムと比較して、より良いはずですが、（複数のCPUを使って）うまくスケーリングできるとは思いません。比較のために

は、ここではチェスの既存の並列化戦略の概要です：

• http://chessprogramming.wikispaces.com/Parallel+Search

α-βは、シーケンシャルなアルゴリズムであるため、すべての並列化戦略は投機的です。したがって、検索ツリーの一部を検索するのに時間を費やすことは避けたいと考えています。検索ツリーの部分は、最終的に他の動作によって切り詰められます。無関係なサブツリーの検索を避けるための比較的簡単な方法の1つは、Young Brothers Wait Conceptと呼ばれています。

スケーラビリティが向上したアルゴリズムもありますが、理解して実装するのが難しくなります。たとえば、work-stealingをサポートするとスケーラビリティが向上するはずです。