c# - 了解树搜索中的 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;
    }

然后是用于跨层级树共享 Alpha Beta 参数的数据结构......

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(第一个匹配项)之前已经开始处理。当您拥有一组已知的大型底层工作负载时，并行性将更好地发挥作用。您可以尝试仅在顶层节点执行并行性时会发生什么情况。