max算法

Question

我已经写了一个单线程的最小-最大算法，为国际象棋游戏，工作良好。现在我正在尝试重写它以使用所有的可维护的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);
                    }


                }
            }
        }
}

因为它的算法将返回的移动，采取了敌人的碎片，但不保护自己的一点。我相信棋盘，移动，价值板等代码是正确的。这个问题必须类似于多线程/propegate值代码。我已经为这件事扯了一个多星期的头发了，我真的很感激你的帮助。

谢谢

Answer 1

很抱歉，没有给出确切的答案，你已经问了什么(实际上，你的问题还不清楚，并调查，根据你的付出是非常困难的)，但我建议更好地实现α-β修剪在您的最小。它可能对你的帮助远远超过数百个CPU核心。您喜欢阅读这方面的内容，请参阅AI/Walkthrough/AlphaBeta/和http://cs.ucla.edu/~rosen/161/notes/alphabeta.html

PS:关于您的问题，很难实现递归多线程(有效地使用所有线程，而不是只在顶层拆分移动树)。我几乎肯定你在那里做过窃听器。我建议您使用计算(展开)所需的额外状态队列。每个线程都应该从队列中获取项并计算它，将clild节点添加到树中。因此，您的算法将不再是DFS，而是将转换为BFS (广度优先搜索)，这在此类移动计算任务中更为有效。