瞭解樹搜索中的PLINQ瓶頸

Question

我對PLINQ有一些奇怪的結果，我似乎無法解釋。我一直在嘗試對Alpha Beta樹進行並行化搜索以加速搜索過程，但是它正在有效地減緩搜索速度。我期望提高並行度，我會每秒線性地增加節點數......並且在修剪被推出之前處理額外的節點。當節點數量相匹配的期望，我的時間不：

非PLINQ，參觀 節點：61418， 運行時間：0：00.67

並行度：1，參觀 節點：61418， 運行時：0：01.48

平行度：2， 節點訪問：75504， 運行時：0：10.08

平行度：4， 節點訪問：95664， 運行時間：1：51.98

平行度：8， 節點訪問：108148， 運行時間：1：48.94

---

任何人都幫我識別可能的罪犯？

相關代碼：

public int AlphaBeta(IPosition position, AlphaBetaCutoff parent, int depthleft) 
    { 
     if (parent.Cutoff) 
      return parent.Beta; 

     if (depthleft == 0) 
      return Quiesce(position, parent); 

     var moves = position.Mover.GetMoves().ToList(); 

     if (!moves.Any(m => true)) 
      return position.Scorer.Score(); 

     //Young Brothers Wait Concept... 
     var first = ProcessScore(moves.First(), parent, depthleft); 
     if(first >= parent.Beta) 
     { 
      parent.Cutoff = true; 
      return parent.BestScore; 
     } 

     //Now parallelize the rest... 
     if (moves.Skip(1) 
      .AsParallel() 
      .WithDegreeOfParallelism(1) 
      .WithMergeOptions(ParallelMergeOptions.NotBuffered) 
      .Select(m => ProcessScore(m, parent, depthleft)) 
      .Any(score => parent.BestScore >= parent.Beta)) 
     { 
      parent.Cutoff = true; 
      return parent.BestScore; 
     } 
     return parent.BestScore; 
    } 

    private int ProcessScore(IMove move, AlphaBetaCutoff parent, int depthleft) 
    { 
     var child = ABFactory.Create(parent); 
     if (parent.Cutoff) 
     { 
      return parent.BestScore; 
     } 
     var score = -AlphaBeta(move.MakeMove(), child, depthleft - 1); 
     parent.Alpha = score; 
     parent.BestScore = score; 
     if (score >= parent.Beta) 
     { 
      parent.Cutoff = true; 
     } 
     return score; 
    } 

然後爲整個樹的各級分享α+β參數的數據結構...

public class AlphaBetaCutoff 
{ 
    public AlphaBetaCutoff Parent { get; set; } 

    private bool _cutoff; 
    public bool Cutoff 
    { 
     get 
     { 
      return _cutoff || (Parent != null && Parent.Cutoff); 
     } 
     set 
     { 
      _cutoff = value; 
     } 
    } 

    private readonly object _alphaLock = new object(); 
    private int _alpha = -10000; 
    public int Alpha 
    { 
     get 
     { 
      if (Parent == null) return _alpha; 
      return Math.Max(-Parent.Beta, _alpha); 
     } 
     set 
     { 
      lock (_alphaLock) 
      { 
       _alpha = Math.Max(_alpha, value); 
      } 
     } 
    } 

    private int _beta = 10000; 
    public int Beta 
    { 
     get 
     { 
      if (Parent == null) return _beta; 
      return -Parent.Alpha; 
     } 
     set 
     { 
      _beta = value; 
     } 
    } 

    private readonly object _bestScoreLock = new object(); 
    private int _bestScore = -10000; 
    public int BestScore 
    { 
     get 
     { 
      return _bestScore; 
     } 
     set 
     { 
      lock (_bestScoreLock) 
      { 
       _bestScore = Math.Max(_bestScore, value); 
      } 
     } 
    } 
} 

Answer 1

當你只有很少的工作，並抵銷新主題對於所有底層節點，您在線程上創建了巨大的開銷。由於Any，您可能正在處理更多的節點，通常情況下，處理會停止，但有些節點已經在Any（第一個匹配）找到之前開始處理。如果有一組已知的大型基礎工作負載，並行性將會更好地工作。如果只在頂級節點上執行並行操作，您可以嘗試執行什麼操作。