3

我对 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);
            }
        }
    }
}
4

1 回答 1

0

当您只做很少的工作并为所有底层节点启动新线程时，您会在线程上产生巨大的开销。由于 Any，您可能正在处理更多节点，通常处理应该停止，但是在找到 Any（第一个匹配项）之前，一些节点已经开始处理。当您拥有一组已知的大型基础工作负载时，并行性将更好地工作。如果您只在顶级节点上进行并行处理，您可以尝试会发生什么。

于 2013-03-20T09:31:47.447 回答