Я должен был создать искусственный интеллект kalaha, который использует альфа-бета-обрезку с итеративным углублением и ограничением по времени 5 секунд .... функция альфа-бета-отсечения работает отлично и все время побеждает, но альфа-бета-отсечение с итеративным углублениемне работает нормально ... когда он собирается закончить, deepCount идет очень глубоко, но не должен (например, 15000) .... Я добавил изображение в конце, чтобы показать эту проблему
Можетsonmeone помочь мне с этим?
public int minimaxIDAlphaBeta(GameState currentBoard, int maxPlayer, boolean isMax, boolean isMin, int alpha, int beta) {
int bestMove = 0;
int depthCount = 1;
int value = 0;
Integer maxValue = Integer.MIN_VALUE;
start_time = 0;
time_exceeded = false;
elapsed_time = 0;
if (!currentBoard.gameEnded()) {
start_time = System.currentTimeMillis();
while (!time_exceeded) {
elapsed_time = System.currentTimeMillis() - start_time;
// GameState newBoard = currentBoard.clone();
if (elapsed_time > timeLimit) {
//System.out.println("time out: " + elapsedTime / 1000F + ", and depth count: " + depthCount);
time_exceeded = true;
break;
} else {
// if (newBoard.gameEnded()) {
// return bestMove;
// }
for (int i = 2; i <= 25 ; i++) //for (int i = 1; elapsed_time < timeLimit ; i++)
{
value = MinimaxIterativeDeepeningAlphaBeta(currentBoard, 1, maxPlayer, isMax, isMin, i, alpha, beta, start_time, time_exceeded);
if (value > maxValue) {
bestMove = value;
}
if (elapsed_time >= timeLimit) {
System.out.println("depth count: " + i);
System.out.println("best move: " + bestMove + ", elapsed time: " + elapsed_time / 1000F);
break;
}
}
}
}
}
return bestMove;
}
[![enter image description here][1]][1]
public int MinimaxIterativeDeepeningAlphaBeta(GameState currentBoard, int currentDepth, int maxPlayer, boolean isMax, boolean isMin, int maxDepth, int alpha, int beta,long start_time,boolean exceeded_time) {
int depth = maxDepth;
int value = 0;
Integer maxValue = Integer.MIN_VALUE;
Integer minValue = Integer.MAX_VALUE;
int bestMove = 0;
//get elapsed time in milliseconds
elapsed_time = System.currentTimeMillis() - start_time;
//if elapsed time is larger than maximum time limit, then stop searching
if (elapsed_time > timeLimit) {
time_exceeded = true;
}
//if time is not exceeded 5 sec
if (!time_exceeded) {
//if the game is ended or we hit a terminal node, return the maxPlayer score
if (currentBoard.gameEnded() || currentDepth == depth || time_exceeded == true) {
if (maxPlayer == 1) {
return currentBoard.getScore(1) - currentBoard.getScore(2);
} else {
return currentBoard.getScore(2) - currentBoard.getScore(1);
}
}
//check to see if it's max turn
if (isMax) {
for (int i = 1; i < 7; i++) {
//check to see if move is possible or not
if (currentBoard.moveIsPossible(i)) {
//copy the current board in each iteration
GameState newBoard = currentBoard.clone();
newBoard.makeMove(i);
//check to see if the next player is max again or not...if it's next turn is max again set isMax true and isMin false...
if (newBoard.getNextPlayer() == maxPlayer) {
isMax = true;
isMin = false;
} else {
isMax = false;
isMin = true;
}
if (isMax) {
//if it's max turn it will excute this recursive function
value = MinimaxIterativeDeepeningAlphaBeta(newBoard, currentDepth + 1, maxPlayer, isMax, isMin, maxDepth, alpha, beta,start_time,exceeded_time);
} else {
//if it's min turn it will excute this recursive function
value = MinimaxIterativeDeepeningAlphaBeta(newBoard, currentDepth + 1, maxPlayer, isMax, isMin, maxDepth, alpha, beta,start_time,exceeded_time);
}
//if the value is greater than the max value, it will store the value in max value and the i as the best move
if (value > maxValue) {
maxValue = value;
bestMove = i;
}
//if maximum value is larger than alpha value, then store maximum value as alpha value
if (maxValue > alpha) {
alpha = maxValue;
}
//if the alpha value is larger than beta value, then stop the iteration
if (beta <= alpha) {
break;
}
}
}
//as long as the depth is greater than 1 we want to calculate the best value and return, but when the current depth is 1 we want to return the best move instead of best value
if (currentDepth != 1) {
bestMove = maxValue;
}
} else { //if it is min turn it will go through the else
for (int i = 1; i < 7; i++) {
if (currentBoard.moveIsPossible(i)) {
//copy the current board in each iteration
GameState newBoard = currentBoard.clone();
newBoard.makeMove(i);
//check to see if the next player is min again or not...if it's next turn is min again set isMin true and isMax false...
if (newBoard.getNextPlayer() != maxPlayer) {
isMax = false;
isMin = true;
} else {
isMax = true;
isMin = false;
}
if (isMin) {
//if it's min turn it will excute this recursive function
value = MinimaxIterativeDeepeningAlphaBeta(newBoard, currentDepth + 1, maxPlayer, isMax, isMin, maxDepth, alpha, beta,start_time,exceeded_time);
} else {
//if it's max turn it will excute this recursive function
value = MinimaxIterativeDeepeningAlphaBeta(newBoard, currentDepth + 1, maxPlayer, isMax, isMin, maxDepth, alpha, beta,start_time,exceeded_time);
}
//if the value is less than the min value, it will store the value in min value and the i as the best move
if (value < minValue) {
minValue = value;
bestMove = i;
}
//if minimum value is smaller than beta value, then store minimum value as beta value
if (minValue < beta) {
beta = minValue;
}
//if the beta value is smaller than alpha value, then stop the iteration
if (beta <= alpha) {
break;
}
}
}
//as long as the depth is greater than 1 we want to calculate the best value and return, but when the current depth is 1 we want to return the best move instead of best value
if (currentDepth != 1) {
bestMove = minValue;
}
}
}
//when the current depth equals to 1 it will return the best move
return bestMove;
}
