koobas.hobune.stream
Minimax implementation problem ?
I'm trying to make a board game similar to chess, but I can't figure out a correct way to implement the minimax search algorithm for the AI movement. Two days in, this is what I came up with:
public void MoveAI()
{
if (Preserve.againstAI) //Verify if playing against AI
{
Tuple<BasePiece, Cell, int> minimaxTuple = MiniMax(3, int.MinValue, int.MaxValue, false);
real = true; //Basically saying that the next move is going to be physically applied to the board (pieces change position);
minimaxTuple.Item1.targetCell = minimaxTuple.Item2;
minimaxTuple.Item1.Move(); //Applying the best move given by minimax
SwitchSides(Color.black); // Whites turn
}
}
public Tuple<BasePiece, Cell, int> MiniMax(int depth, int alpha, int beta, bool maximizingPlayer)
{
real = false; //Pieces movement doesn't appear physically in the board, but they change cells
if (depth == 0 || CheckMat() || CheckNull()) // CheckNull checks if a draw occurs
{
return new Tuple<BasePiece, Cell, int>(null, null, BasePiece.numberOfWhitePieces - BasePiece.numberOfBlackPieces);
}
if (maximizingPlayer)
{
bool found = false;
int maxEval = int.MinValue;
for (int j = 0; j < allWhites.Count; j++) //Checks all white pieces
{
allWhites[j].CheckPathing(); //Checks every possible move for this piece and adds it to the higlightedCells list
for (int i = 0; i < allWhites[j].highlightedCells.Count; i++)
{
allWhites[j].targetCell = allWhites[j].highlightedCell[i];
allWhites[j].Move();
int eval = MiniMax(depth - 1, alpha, beta, false).Item3;
UIElement.Undo(); // Pieces go back to the previous board state before previous Move() call
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
{
bool found = false;
int minEval = int.MaxValue;
for (int j = 0; j < allBlacks.Count; j++)
{
allBlacks[j].CheckPathing();
for (int i = 0; i < allBlacks[j].highlightedCells.Count; i++)
{
allBlacks[j].targetCell = allWhites[j].highlightedCell[i];
allBlacks[j].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 messy and I end up with a bunch of pieces moving and duplicating (?) even after using a boolean (real) to keep the pieces from physically moving in the board within the minimax call.
