c# Multithreaded min-max algorithm
===

I have written a single-threaded min-max algorithm for a chess game that works fine. Now I am trying to rewrite it to use all avaliable cpu-cores, but I can not get it to work correctly. 

My idea is to spawn as many threads as there are cores on the system (in my case 4) and to let the threads add and remove work items from a queue. Each of these work items is a "CalculateState" that holds information about a possible chessboard after x number of moves on the board.

When a workitem is spawned at maxDepth it will evaluate the chessboard and "return" its value. The return is done by propegating its value upwards in the tree of examined moves (to simulate recursion).

Algorithm start:

    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;
        }

Thread execution:

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

            }
        }

Work item context.

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

                        
                    }
                }
            }
    }
As it is the algorithm will return moves that takes the enemies pieces, but does not protect its own at all.
I am confident that the code in chessboard, move, valueofboard etc is correct. The problem must like in the multithreading/propegate value code. I have torn my hair over this for over a week and would really appreciate any help.

Thanks