3

PLINQ を使用すると、説明できないような奇妙な結果が得られます。検索プロセスを高速化するために Alpha Beta ツリー検索を並列化しようとしてきましたが、実際には速度が低下しています。並列度を上げると、1 秒あたりのノード数が直線的に増加すると予想されます...そして、プルーニングが後で延期されるため、処理される追加のノードでヒットします。ノード数は予想と一致しますが、私の時間は一致しません:

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

1 に答える 1

0

作業をほとんど行わず、基盤となるすべてのノードに対して新しいスレッドを開始すると、スレッド化に大きなオーバーヘッドが発生します。Anyが原因で、おそらくより多くのノードを処理しています。通常、処理は停止しますが、一部のノードは、Any（最初の一致）が見つかる前に処理を開始しました。並列処理は、基礎となる大きなワークロードの既知のセットがある場合に、より適切に機能します。トップレベルのノードでのみ並列処理を行うとどうなるかを試すことができます。

于 2013-03-20T09:31:47.447 に答える