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

222
Глава 8.
Состязательный поиск
Листинг 8.8. 
TTTBoard.java (продолжение)
@Override
public double 
evaluate(Piece player) {
if 
(isWin() && turn == player) {
return 
-1;
} 
else if 
(isWin() && turn != player) {
return 
1;
} 
else 
{
return 
0.0;
}
}
@Override
public 
String toString() {
StringBuilder sb = 
new 
StringBuilder();
for 
(
int 
row = 0; row < 3; row++) {
for 
(
int 
col = 0; col < 3; col++) {
sb.append(position[row * 3 + col].toString());
if 
(col != 2) {
sb.append("|");
}
}
sb.append(System.
lineSeparator
());
if 
(row != 2) {
sb.append("-----");
sb.append(System.
lineSeparator
());
}
}
return 
sb.toString();
}
}
В.большинстве.игр.приходится.вычислять.позицию.приблизительно,.поскольку.
мы.не.можем.пройти.игру.до.самого.конца,.чтобы.точно.определить,.кто.выиграет.
или.проиграет.в.зависимости.от.того,.какие.ходы.будут.сделаны..Но.в.крестиках-
ноликах.довольно.малое.пространство.поиска,.так.что.мы.можем.пройти.его.от.
любой.позиции.до.конца.игры..Следовательно,.метод.
evaluate()
.может.просто.
возвращать.некое.число,.если.игрок.выиграл,.меньшее.число.—.в.случае.ничьей.
и.совсем.малое.—.в.случае.проигрыша.
8.2.2. Минимакс
Минимакс.—.это.классический.алгоритм.для.поиска.наилучшего.хода.в.играх.
с.двумя.игроками,.нулевой.суммой.и.отличной.информацией,.таких.как.крестики-
нолики,.шашки.или.шахматы..Этот.алгоритм.был.расширен.и.модифицирован.
для.других.типов.игр..Минимакс.обычно.реализуется.с.использованием.рекур-
сивной.функции,.в.которой.каждый.игрок.обозначается.как.максимизирующий.
или.минимизирующий.

---

8.2. Крестики-нолики
223
Максимизирующий.игрок.стремится.найти.ход,.который.приведет.к.максималь-
ному.выигрышу..Однако.он.должен.учитывать.ходы.минимизирующего.игрока..
После.каждой.попытки.максимизирующего.игрока.максимизировать.выигрыш.
рекурсивно.вызывается.минимакс,.чтобы.найти.ответ.противника,.который.
минимизирует.максимизирующий.выигрыш.игрока..Это.продолжается.в.обоих.
направлениях.(максимизация,.минимизация,.максимизация.и.т..д.),.пока.не.будет.
достигнут.базовый.случай.рекурсивной.функции..Базовый.случай.—.это.конечная.
позиция.(выигрыш.или.ничья).либо.достижение.максимальной.глубины.поиска.
Минимакс.вычисляет.стартовую.позицию.для.максимизирующего.игрока..Для.
метода.
evaluate()
.класса.
TTTBoard
,.если.наилучшая.возможная.игра.обеих.сторон.
приведет.к.выигрышу.максимизирующего.игрока,.возвращается.1.балл..Если.
наилучшая.возможная.игра.приведет.к.проигрышу,.то.возвращается.–1..Наконец,.
если.наилучшая.игра.—.это.ничья,.то.возвращается.0.
Эти.числа.возвращаются.при.достижении.базового.случая..Затем.они.передают-
ся.через.все.рекурсивные.вызовы,.которые.привели.к.базовому.случаю..Чтобы.
максимизировать.каждый.рекурсивный.вызов,.вверх.по.рекурсии.передаются.
наилучшие.вычисленные.ходы..Чтобы.минимизировать.каждый.рекурсивный.
вызов,.передаются.худшие.вычисленные.ходы..Таким.образом.строится.дерево.
решений..На.рис..8.2.показано.такое.дерево,.которое.упрощает.передачу.данных.
вверх.по.рекурсивным.вызовам.для.игры,.в.которой.осталось.сделать.два.хода.
В.играх,.имеющих.слишком.глубокое.пространство.поиска,.таких.как.шашки.
и.шахматы,.чтобы.достичь.конечной.позиции,.минимакс.останавливается.после.
достижения.определенной.глубины.(выполнения.заданного.количества.ходов.по-
иска,.иногда.называемого.
ply
)..Затем.включается.функция.оценки,.использующая.
эвристику.для.оценки.состояния.игры..Чем.лучше.выглядит.игра.для.первого.
игрока,.тем.выше.присуждаемая.ей.оценка..Мы.вернемся.к.этой.концепции,.когда.
будем.обсуждать.игру.Connect.Four,.которая.имеет.гораздо.большее.пространство.
поиска,.чем.крестики-нолики.
В.листинге.8.9.представлена.полная.реализация.функции.
minimax()
.