1

正常に動作するチェスゲーム用のシングルスレッドのmin-maxアルゴリズムを作成しました。現在、使用可能なすべてのCPUコアを使用するように書き直そうとしていますが、正しく機能させることができません。

私の考えは、システム上のコア（私の場合は4）と同じ数のスレッドを生成し、スレッドが作業項目をキューに追加したり、キューから削除したりできるようにすることです。これらの各作業項目は「CalculateState」であり、ボード上でx回移動した後に可能なチェス盤に関する情報を保持します。

ワークアイテムがmaxDepthでスポーンされると、チェス盤を評価し、その値を「返し」ます。戻りは、（再帰をシミュレートするために）調べられた動きのツリーでその値を上向きに伝播することによって行われます。

アルゴリズムの開始：

private readonly ConcurrentPriorityQueue<int, CalculateState> _calculateStates = new ConcurrentPriorityQueue<int, CalculateState>(); 
private Thread[] _threads = new Thread[Environment.ProcessorCount];
private const int MaxDepth = 3;
private PlayerColor _maxPlayer;

public Move CalculateMoveMultithreaded(ChessBoard board)
    {
        _maxPlayer = board.TurnToMove;
        var parentState = new CalculateState(null, null, 0, null, int.MaxValue, int.MinValue, board.TurnToMove);

        foreach (var move in board.GetPossibleMoves())
        {
            move.MakeMove(board);
            var newState = ChessStateTransforms.TransformChessBoardToState(board);
            move.UnMakeMove(board);

            _calculateStates.Enqueue(MaxDepth, new CalculateState(move, newState, 1, parentState, int.MaxValue, int.MinValue, Player.OppositeColor(board.TurnToMove)));
        }

        for (var i = 0; i < _threads.Length; i++)
        {
            var calculationThread = new Thread(DoWork);
            _threads[i] = calculationThread;
            calculationThread.Start();
        }

        foreach (var thread in _threads)
        {
            thread.Join();
        }

        return parentState.MoveToMake;
    }

スレッドの実行：

private void DoWork()
    {
        while (true)
        {
            KeyValuePair<int, CalculateState> queueItem;
            if (!_calculateStates.TryDequeue(out queueItem))
                break;

            var calculateState = queueItem.Value;
            var board = ChessStateTransforms.TransformChessStateIntoChessBoard(calculateState.ChessState);

            if (calculateState.Depth == MaxDepth)
            {
                var boardValue = board.ValueOfBoard(_maxPlayer);
                calculateState.PropergateValue(boardValue);
                continue;
            }

            foreach (var move in board.GetPossibleMoves())
            {
                move.MakeMove(board);
                var newState = ChessStateTransforms.TransformChessBoardToState(board);
                move.UnMakeMove(board);

                _calculateStates.Enqueue(MaxDepth - calculateState.Depth, new CalculateState(calculateState.MoveToMake, newState, calculateState.Depth + 1, calculateState, calculateState.MinValue, calculateState.MaxValue, Player.OppositeColor(board.TurnToMove)));
            }

        }
    }

作業項目のコンテキスト。

 private class CalculateState
    {
        public readonly PlayerColor Turn;
        public int MaxValue;
        public int MinValue;

        public readonly int Depth;
        public readonly ChessState ChessState;
        public Move MoveToMake;

        private readonly CalculateState _parentState;        

        public CalculateState(Move moveToMake, ChessState chessState, int depth, CalculateState parentState, int minValue, int maxValue, PlayerColor turn)
        {
            Depth = depth;
            _parentState = parentState;
            MoveToMake = moveToMake;
            ChessState = chessState;
            MaxValue = maxValue;
            Turn = turn;
            MinValue = minValue;
        }

        public void PropergateValue(int value, Move firstMove = null)
        {
            lock (this)
            {
                if (Turn == _maxPlayer)
                {
                    if (value > MaxValue)
                    {
                        MaxValue = value;

                        if (Depth == 0)
                        {
                            MoveToMake = firstMove;
                            return;
                        }

                        _parentState.PropergateValue(MaxValue, MoveToMake);
                    }
                }
                else
                {
                    if (value < MinValue)
                    {
                        MinValue = value;

                        if (Depth == 0)
                        {
                            MoveToMake = firstMove;
                            return;
                        }

                        _parentState.PropergateValue(MinValue, MoveToMake);
                    }


                }
            }
        }
}

アルゴリズムは敵の駒を奪う動きを返しますが、それ自体をまったく保護しません。チェス盤、移動、valueofboardなどのコードは正しいと確信しています。問題は、マルチスレッド/propegate値コードのようになっている必要があります。私はこれで一週間以上髪を引き裂いてきました、そして本当に助けていただければ幸いです。

ありがとう

4

1 に答える 1

1

あなたが尋ねたことについて正確な答えを与えていないことをお詫びします（実際にはあなたの問題は明確ではなく、あなたが与えたものに基づいてそれを調査することは非常に難しいです）、しかし私はあなたの分でアルファベータプルーニングをよりよく実装することをお勧めします-最大 それはあなたに何百ものCPUコアをはるかに超えるのを助けるかもしれません。それについて読みたい場合は、http：//www.cs.utah.edu/~hal/courses/2009S_AI/Walkthrough/AlphaBeta/およびhttp://cs.ucla.edu/~rosen/161/notes/を参照してください。アルファベットa.html

PS：あなたの質問に関しては、再帰マルチスレッドを実装するのは難しいでしょう（効果的にすべてのスレッドを使用し、トップレベルでのみ移動ツリーを分割しない）。あなたはそこでバグを犯したとほぼ確信しています。計算（拡張）に必要な追加の状態キューを使用することをお勧めします。すべてのスレッドはキューからアイテムを取得し、それを計算して、ツリーにclildノードを追加する必要があります。したがって、アルゴリズムはもはやDFSではなく、BFS（幅優先探索）に変換されます。これは、このような移動計算タスクではるかに効果的です。

于 2012-07-31T08:55:10.233 に答える