Computer Science на языке Java 2022 Дэвид Копец Классические задачи Computer Science на языке Java 2022 ббк

Листинг 8.9. 
Minimax.java
package 
chapter8;
public class 
Minimax {
// Находим наилучший из возможных результатов для первого игрока
public static 
 
double 
minimax(Board board,
Boolean 
maximizing, Piece originalPlayer, 
int 
maxDepth) {
// Базовый случай — достигнута финальная 
// позиция или максимальная глубина поиска
if 
(board.isWin() || board.isDraw() || maxDepth == 0) {
return 
board.evaluate(originalPlayer);
}

---

224
Глава 8.
Состязательный поиск
// Рекурсивный случай — максимизируйте свою выгоду или 
// минимизируйте выгоду противника
if 
(maximizing) {
double 
bestEval = Double.
NEGATIVE_INFINITY
; // результат выше
for 
(Move move : board.getLegalMoves()) {
double 
result = 
minimax
(board.move(move), 
false
,
originalPlayer, maxDepth — 1);
bestEval = Math.
max
(result, bestEval);
}
return 
bestEval;
} 
else 
{ // минимизация
double 
worstEval = Double.
POSITIVE_INFINITY
; // результат ниже
for 
(Move move : board.getLegalMoves()) {
double 
result = 
minimax
(board.move(move), 
true
,
originalPlayer, maxDepth — 1);
worstEval = Math.
min
(result, worstEval);
}
return 
worstEval;
}
}
Õîä 0:
ìàêñèìèçèðóþùèé
õîä èãðîêà O
Îöåíêà = 1
Îöåíêà = 1
Max (1, 0)
Îöåíêà = 0
Îöåíêà = 0
X
O
X
O
X
X
O
Õîä 1:
ìèíèìèçèðóþùèé
õîä èãðîêà Õ
X
O
X
O
X
X
O
O
X
O
X
O
O
X
X
O
Õîä 2:
ìàêñèìèçèðóþùèé
õîä èãðîêà O
X
O
X
O
O
X
X
X
O
Рис. 8.2.
Минимаксное дерево решений для игры в крестики-нолики, в которой 
осталось сделать два хода. Чтобы максимизировать вероятность выигрыша, 
первоначальный игрок, 0, должен поставить 0 по центру в нижнем ряду.
Стрелки указывают позиции, с которых принимается решение

---

8.2. Крестики-нолики
225
При.каждом.рекурсивном.вызове.нужно.отслеживать.позицию.на.поле.независимо.
от.того,.максимизируем.мы.ее.или.минимизируем.и.для.кого.пытаемся.оценить.
позицию.(
originalPlayer
)..
Первые.несколько.строк.функции.
minimax()
.касаются.базового.случая.—.заключи-
тельной.позиции.(выигрыш,.проигрыш.или.ничья).или.максимально.достижимой.
глубины..Остальная.часть.функции.обрабатывает.рекурсивные.случаи.
Один.из.рекурсивных.случаев.—.это.максимизация..В.этой.ситуации.мы.ищем.ход,.
который.даст.максимально.возможную.оценку..Второй.рекурсивный.случай.—.
минимизация:.ищем.ход,.который.приведет.к.наименьшей.возможной.оценке..Как.
бы.то.ни.было,.эти.два.случая.чередуются,.пока.не.будет.достигнута.финальная.
позиция.или.максимальная.глубина.поиска.(базовый.случай).
К.сожалению,.мы.не.можем.использовать.нашу.реализацию.
minimax()
,.чтобы.
найти.наилучший.ход.для.данной.позиции,.так.как.функция.возвращает.оцен-
ку.—.значение.с.плавающей.запятой..Оно.не.сообщает,.какой.лучший.первый.ход.
привел.к.данной.оценке.
Вместо.этого.создадим.вспомогательную.функцию.
findBestMove()
,.которая.
перебирает.вызовы.
minimax()
.для.каждого.допустимого.хода.из.данной.по-
зиции.и.позволяет.найти.ход,.который.имел.бы.максимальную.оценку..Функ-
цию.
findBestMove()
.можно.представить.как.первый.максимизирующий.вызов.
minimax()
,.но.с.отслеживанием.начальных.ходов.(листинг.8.10).
Листинг 8.10. 
Minimax.java (продолжение)
// Найти наилучший возможный ход из текущей 
// позиции, просматривая maxDepth ходов вперед