Я реализовал алгоритм MiniMax (с отсечкой альфа-бета), однако он ведет себя интересно. Мой игрок создаст огромное преимущество, но когда придет время сделать последний, выигрышный ход, он не займет этот ход и просто затянет игру.
Вот моя минимаксная функция:
// Game states are represented by Node objects (holds the move and the board in that state)
//ValueStep is just a pair holding the minimax value and a game move (step)
private ValueStep minimax(Node gameState,int depth,int alpha,int beta) {
//Node.MAXDEPTH is a constant
if(depth == Node.MAXDEPTH || gameOver(gameState.board)) {
return new ValueStep(gameState.heuristicValue(),gameState.step);
}
//this method definately works. child nodes are created with a move and an
//updated board and MAX value
//which determines if they are the maximizing or minimizing players game states.
gameState.children = gameState.findPossibleStates();
if(state.MAX) { //maximizing player
ValueStep best = null;
for(Node child: gameState.children) {
ValueStep vs = new ValueStep(minimax(child,depth+1,alpha,beta).value,child.move);
//values updated here if needed
if(best==null || vs.value > best.value) best = vs;
if(vs.value > alpha) alpha = vs.value;
if(alpha >= beta) break;
}
return best;
} else { //minimizing player
ValueStep best = null;
for(Node child: gameState.children) {
ValueStep vs = new ValueStep(minimax(child,depth+1,alfa,beta).value,child.move);
if(best==null || vs.value < best.value) best = vs;
if(vs.value < beta) beta = vs.value;
if(alpha >= beta) break;
}
return best;
}
}
Сначала я подумал, что проблема в моей функции оценки, но если это так, я не смог ее найти. В этой игре у обоих игроков есть оценка, и моя функция просто вычисляет эвристическое значение из разницы очков.
Вот оно:
public int heuristicValue() {
//I calculate the score difference here in this state and save it in
//the variable scoreDiff. scoreDiff will be positive if I am winning
//here, negative if im loosing.
//"this" is a Node object here. If the game is over here, special
//heuristic values are returned, depending on who wins (or if its a
//draw)
if(gameOver(this.board)) {
if(scoreDiff>0) {
return Integer.MAX_VALUE;
} else if(scoreDiff==0) {
return 0;
} else {
return Integer.MIN_VALUE;
}
}
int value = 0;
value += 100*scoreDiff; //caluclate the heuristic value using the score differerence. If its high, the value will be high as well
return value;
}
Я "перевел" мой код на английский, поэтому возможны опечатки. Я уверен, что проблема где-то здесь, но если вам нужен какой-то другой код, я обновлю вопрос. Опять же, мой игрок может создать преимущество, но по какой-то причине он не сделает последний ход.
Я ценю вашу помощь!