The Minimax algorithm only selects the first available move as the best move when none of its pieces are threatened. On an 8x8 board, when it is the bot's turn to play and the Minimax algorithm is called to determine the best move, the bot chooses the first available move, provided that no piece is under threat. This behavior has become predictable because I can now anticipate what the bot will play.
I have also tried increasing the search depth, and I believe this could be contributing to the issue. When increasing the depth from 2 to 4, I noticed that the maxEval is always 9999. Additionally, at depth 3, I observed that the bot attempts to play the minimizing player's piece as the best move.
I need help resolving this behavior.
This is the Min Max method
int minMax(List<String> piecesPos, int depth, bool isMaximizing, int alpha, int beta) {
// Base case: if depth is 0 or the game is over, return the evaluation
if (depth == 0 || isGameOver(piecesPos)) {
return evaluateBoard(piecesPos);
}
if (isMaximizing) {
int maxEval = -9999; // Initialize to a very low value
for (int i = 0; i < piecesPos.length; i++) {
if (piecesPos[i][0] == "B" || piecesPos[i][0] == "O") {
List<int> possibleMoves = getPossibleMoves(piecesPos, i);
for (int move in possibleMoves) {
// Save the current state
List<String> saveState = List.from(piecesPos);
// Make the move
makeMove(piecesPos, i, move);
// Recursive call
int eval = minMax(piecesPos, depth - 1, false, alpha, beta);
// Restore the state
piecesPos = List.from(saveState);
// Update maxEval
maxEval = max(maxEval, eval);
alpha = max(alpha, eval);
// Alpha-Beta Pruning
if (beta <= alpha) {
break;
}
}
}
}
return maxEval;
} else {
int minEval = 9999; // Initialize to a very high value
for (int i = 0; i < piecesPos.length; i++) {
if (piecesPos[i][0] == "W" || piecesPos[i][0] == "Q") {
List<int> possibleMoves = getPossibleMoves(piecesPos, i);
for (int move in possibleMoves) {
// Save the current state
List<String> saveState = List.from(piecesPos);
// Make the move
makeMove(piecesPos, i, move);
// Recursive call
int eval = minMax(piecesPos, depth - 1, true, alpha, beta);
// Restore the state
piecesPos = List.from(saveState);
// Update minEval
minEval = min(minEval, eval);
beta = min(beta, eval);
// Alpha-Beta Pruning
if (beta <= alpha) {
break;
}
}
}
}
return minEval;
}
}
This is how I call and play the best move
void playBestMove(List<String> piecesPosCopy, int depth) {
int bestEval = -9999;
int bestMovePrev = -1;
int bestMoveIndex = -1;
// Save the current state before call
List<String> defaultState = List.from(piecesPos);
for (int i = 0; i < piecesPos.length; i++) {
if (piecesPos[i][0] == "B" || piecesPos[i][0] == "O") {
List<int> possibleMoves = getPossibleMoves(piecesPos, i);
for (int move in possibleMoves) {
// Save the current state
List<String> saveState = List.from(piecesPos);
// Make the move
makeMove(piecesPos, i, move);
// Evaluate the move
int eval = minMax(piecesPos, depth - 1, false, -9999, 9999);
// Restore the state
piecesPos = List.from(saveState);
// Update best move
if (eval > bestEval) {
bestEval = eval;
bestMovePrev = i;
bestMoveIndex = move;
}
}
}
}
print("BBB The best max is $bestEval prev is $bestMovePrev and index is $bestMoveIndex");
//Restored state to original State before making best move
piecesPos = List.from(defaultState);
// Play the best move
if (bestMovePrev != -1 && bestMoveIndex != -1) {
//makeMove(piecesPos, bestMovePrev, bestMoveIndex);
recentlyCrowned = false;
if(animatePieceMovement){performMultitakeAnim = true;}
if(!vsComputer){
undoMove = List.from(piecesPos);
saveMovesState.add(undoMove);
}
//Allow to check for Win, loose and draw.
checkForWinLooseDraw = true;
//MakeMove
makeBotMove(bestMovePrev, bestMoveIndex);
}
}
This is the code for the evaluateBoard method
int evaluateBoard(List<String> piecesPos) {
// Implement the evaluation function
// This function should return a score based on the current state of the board
// For example, the difference in the number of pieces between the two players
int totalMyPiece = 0;
int totalOppPiece = 0;
//Piece Weight
for (int i = 0; i < piecesPos.length; i++) {
if (piecesPos[i][0] == "W"){
totalOppPiece = totalOppPiece + 10;
}else
if(piecesPos[i][0] == "Q"){
totalOppPiece = totalOppPiece + 20;
}else
if (piecesPos[i][0] == "B"){
totalMyPiece = totalMyPiece + 10;
}else
if(piecesPos[i][0] == "O"){
totalMyPiece = totalMyPiece + 20;
}
}
// center control
for(int b = 0; b < centerControlArea.length; b++){
if (piecesPos[centerControlArea[b]][0] == "W" || piecesPos[centerControlArea[b]][0] == "Q"){
totalOppPiece = totalOppPiece + 3;
}
}
// Threats (pieces under attack)
totalOppPiece = totalOppPiece - squaresWithTakes_OPP.length * 5;
// center control
for(int b = 0; b < centerControlArea.length; b++){
if (piecesPos[centerControlArea[b]][0] == "B" || piecesPos[centerControlArea[b]][0] == "O"){
totalMyPiece = totalMyPiece + 3;
}
}
// Threats (pieces under attack)
totalMyPiece = totalMyPiece - squaresWithTakes.length * 5;
print("VVV $totalMyPiece");
print("VVV $totalOppPiece");
return totalMyPiece - totalOppPiece;
}
I had to save the board state for each move made when Minimax was called and analyze them individually. This allowed me to track the moves and notice that the board state was not being updated correctly. I’ve now resolved the issue. The problem was related to how I was passing my board state (piecesPos). I was retrieving and passing the wrong board state, which caused Minimax to make incorrect or suboptimal moves. Thank you all for your contributions; it is greatly appreciated.
Renaming to piecesPosCopy and using piecesPos
This was getting the actual board state to use when min max is called.
int minMax(List<String> piecesPosCopy, int depth, bool isMaximizing, int alpha, int beta) {
// Base case: if depth is 0 or the game is over, return the evaluation
if (depth == 0 || isGameOver(piecesPos)) {
return evaluateBoard(piecesPos);
}
if (isMaximizing) {
int maxEval = -9999; // Initialize to a very low value
for (int i = 0; i < piecesPos.length; i++) {
if (piecesPos[i][0] == "B" || piecesPos[i][0] == "O") {
List<int> possibleMoves = getPossibleMoves(piecesPos, i);
for (int move in possibleMoves) {
// Save the current state
List<String> saveState = List.from(piecesPos);
// Make the move
performMultitakeAnim = false;
makeMove(piecesPos, i, move);
// Recursive call
int eval = minMax(piecesPos, depth - 1, false, alpha, beta);
// Restore the state
piecesPos = List.from(saveState);
// Update maxEval
maxEval = max(maxEval, eval);
alpha = max(alpha, eval);
// Alpha-Beta Pruning
if (beta <= alpha) {
break;
}
}
}
}
return maxEval;
} else {
int minEval = 9999; // Initialize to a very high value
for (int i = 0; i < piecesPos.length; i++) {
if (piecesPos[i][0] == "W" || piecesPos[i][0] == "Q") {
List<int> possibleMoves = getPossibleMoves(piecesPos, i);
for (int move in possibleMoves) {
// Save the current state
List<String> saveState = List.from(piecesPos);
// Make the move
performMultitakeAnim = false;
makeMove(piecesPos, i, move);
// Recursive call
int eval = minMax(piecesPos, depth - 1, true, alpha, beta);
// Restore the state
piecesPos = List.from(saveState);
// Update minEval
minEval = min(minEval, eval);
beta = min(beta, eval);
// Alpha-Beta Pruning
if (beta <= alpha) {
break;
}
}
}
}
return minEval;
}
}