# Minimax implementation problem

it's my first time posting so apologies in advance if the format is weird. I'm developing a board game that's very similar to checkers/chess and I've faced some problems implementing the minimax/negamax algorithms with alpha-beta pruning for my AI. This is how far I've got:

public IEnumerator MoveAI()
{
if (Preserve.againstAI)
{
if (!CheckMat() && !CheckNull())
{
yield return new WaitUntil(() => BasePiece.mandatoryCheckFinished);
minimaxChecking = true; //Changing the movement of pieces so it doesn't appear physically in the board
Tuple<BasePiece, Cell, int> minimaxTuple = MiniMax(originalDepth, -10000, 10000, false);
minimaxChecking = false;
minimaxTuple.Item1.targetCell = minimaxTuple.Item2;
minimaxTuple.Item1.Move(); //Applying the move found by MiniMax
StartCoroutine(minimaxTuple.Item1.MandatoryCheck());
SwitchSides(Color.black);
}
}
}

public Tuple<BasePiece, Cell, int> MiniMax(int depth, int alpha, int beta, bool maximizingPlayer)
{
if (depth == 0)
{
return new Tuple<BasePiece, Cell, int>(null, null, BasePiece.numberOfWhitePieces - BasePiece.numberOfBlackPieces);
}
if (maximizingPlayer)
{
BasePiece actualPiece = null;
Cell actualCell = null;
bool found = false;
int maxEval = -10000;
for (int j = 0; j < allWhites.Count; j++) //Going through all possible whites movement
{
actualPiece = allWhites[j];
actualPiece.CheckPathing();
if (actualPiece.highlightedCells.Count > 0)
{
for (int i = 0; i < actualPiece.highlightedCells.Count; i++)
{
actualCell = actualPiece.highlightedCells[i];
actualPiece.targetCell = actualCell;
actualPiece.Move();
int eval = MiniMax(depth - 1, alpha, beta, false).Item3;
UIElement.Undo(); //Undoing the previous move
maxEval = eval > maxEval ? eval : maxEval;
alpha = eval > alpha ? eval : alpha;
if (beta <= alpha)
{
found = true;
break;
}
}
if (found)
{
break;
}
}
}
return new Tuple<BasePiece, Cell, int>(actualPiece, actualCell, maxEval);
}
else
{
BasePiece actualPiece = null;
Cell actualCell = null;
bool found = false;
int minEval = 10000;
for (int j = 0; j < allBlacks.Count; j++)
{
actualPiece = allBlacks[j];
actualPiece.CheckPathing();
if (actualPiece.highlightedCells.Count > 0)
{
for (int i = 0; i < actualPiece.highlightedCells.Count; i++)
{
actualCell = actualPiece.highlightedCells[i];
actualPiece.targetCell = actualCell;
actualPiece.Move();
int eval = MiniMax(depth - 1, alpha, beta, true).Item3;
UIElement.Undo();
minEval = eval < minEval ? eval : minEval;
beta = eval < beta ? eval : beta;
if (beta <= alpha)
{
found = true;
break;
}
}
if (found)
{
break;
}
}
}
return new Tuple<BasePiece, Cell, int>(actualPiece, actualCell, minEval);
}
}


The result is quite weird for any initial depth. For an originalDepth = 1, The player's first move gets undone, plus the move that I get is not a valid one. (the negamax gives a similar result although with a different move)

The problem could very well be in my undo function (Which I doubt as the undo method works very well in a human vs human mode) and I can edit it's code in if there is no actual error within the algorithm.

I'm also wondering if it's necessary to make a deep copy of the board state before the MiniMax call (right now I'm exploring the moves without physically moving the pieces in the board but rather changing their cells and then I undo each move, all in the original board).

Any help or suggestions would be greatly appreciated as I have been stuck with this for quite a few days now.

EDIT: I'm aware of the lack of a proper evaluation function but I don't think it explains why I'm getting an invalid move. (I could be wrong)

• Answering this requires a lot of guess work. Undo could have a bug only present when minimaxChecking is true. Also, if you hide highlightedCells when the player clicks away (say, to click Undo), and fix it when they click back… Then a human player won't notice if Undo does not undo highlightedCells correctly. Another thing a human player won't notice is the pieces getting reordered when a move captures a piece and Undo adds it in a different place on the collection. I suggest to decouple the state form the UI and to work with copies. In fact, Undo could simply a stack of copies. – Theraot Nov 12 '20 at 7:11
• I know I'm writing 8 months late. Did you solve the problem? – Theraot Nov 12 '20 at 7:12