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;
}
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;
}
- 2 Pls post a minimal reproducible example of your code or explain the current code better. There’s a lot going on in the code you’ve posted – Dinux Commented Mar 27 at 16:42
- 1 Does your eval function have any positional weighting terms in it? If not then MiniMax might well play the first legal move generated even if it is working correctly. The only way to tell if minimax is working is to test on a few very constrained blocked endgame positions with few legal moves for either side and mate in two. Print out the search tree and eval at each node and check that minimax does what it claims to do. I'm assuming that it is chess - you don't say what the game is and othello is another possibility. It is all too easy to have sign convention errors. – Martin Brown Commented Mar 27 at 16:48
- It's checkers. Yes it has positional weighting terms in it. It checks for the piece difference and weight pawns as 10 and kings 20. Also the pieces in the center of the board are weighted 2 each . Piece with more available moves are weighted 5 each and pieces that are under threat of capture are weighted -5. – Franklyn Oreben Commented Mar 27 at 17:16
- 1 OK so set up a nice simple position and check that minimax really does what it should with a branching factor of at most 3 and no more than 3 ply to a win for the side on the move. Then check the same for side not on the move to make sure it resists properly. – Martin Brown Commented Mar 27 at 17:31
- 1 As an aside, your list of esoteric strings would be greatly improved, not just performance-wise but also in a reader's ability to understand whats going on, by being a list of objects with the state represented by an enum. In fact, I see no reason why each object needs to store its position when you can just use the list index as the position, so all you really need to store is the enum state. This would also help to prevent bugs like what presumably happened by there being two pieces in the list you shared having two different states with the index "53". – Abion47 Commented Mar 27 at 19:37
1 Answer
Reset to default 0I 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;
}
}