1
Я пытаюсь реализовать минимаксный алгоритм для небольшой шахматной игры. Возможно, мое предположение ошибочно, и это не то, что нужно пытаться. Это?Облицовочные проблемы производительности, реализующие минимакс для шахматной игры
Программа работает, но есть большая проблема с производительностью:
- Depth = 0, 1 или 2 результат немедленно.
- Глубина = 3 Результат занимает 15 секунд.
- Глубина = 4 - пока нет результатов.
Вот моя реализация:
private Move findBestMove(Chessboard chessboard, int depth,
boolean maximizingPlayer) {
if (depth == 0) {
return new Move(chessboard.calculateHeuristicValue());
} else {
Move bestMove;
if (maximizingPlayer) {
bestMove = new Move(Integer.MIN_VALUE);
for (Move possibleMove : findAllPossibleMoves(chessboard,
!(maximizingPlayer^whiteTurn))) {
Move move = findBestMove(
possibleMove.getResultChessboard(), depth - 1,
!maximizingPlayer);
if (move.getValue() > bestMove.getValue()) {
possibleMove.setValue(move.getValue());
bestMove = possibleMove;
}
}
} else {
bestMove = new Move(Integer.MAX_VALUE);
for (Move possibleMove : findAllPossibleMoves(chessboard,
!(maximizingPlayer^whiteTurn))) {
Move move = findBestMove(
possibleMove.getResultChessboard(), depth - 1,
!maximizingPlayer);
if (move.getValue() < bestMove.getValue()) {
possibleMove.setValue(move.getValue());
bestMove = possibleMove;
}
}
}
return bestMove;
}
}
Может быть, есть ошибка в реализации алгоритма или при проектировании объектов или при их использовании. Я не могу на нее наложить. Поэтому я хочу быть уверенным, что нет основной проблемы, которую я пропущу, прежде чем пытаться оптимизировать код или настроить конфигурацию памяти в программе.
Примечание: нет опыта с профилированием памяти.
минимакс экспоненциальный. чтобы уменьшить количество изученных ветвей, вы можете использовать обрезку алфавита – njzk2