我已经为一个运行良好的国际象棋游戏编写了一个单线程的最小-最大算法。现在我正在尝试重写它以使用所有可用的 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);
}
}
}
}
}
因为它的算法将返回带走敌人碎片但根本不保护自己的动作。我相信棋盘、移动、棋盘值等中的代码是正确的。问题必须在多线程/传播值代码中。我已经为此撕裂了一个多星期的头发，非常感谢任何帮助。
谢谢