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

8.5. РЕАЛЬНЫЕ ПРИЛОЖЕНИЯ
Минимакс.в.сочетании.с.дополнительными.расширениями,.такими.как.альфа-
бета-отсечение,.—.это.основа.большинства.современных.шахматных.движков..
Этот.алгоритм.успешно.применяется.в.разнообразных.стратегических.играх..
В.сущности,.большинство.искусственных.противников.в.компьютерных.играх.
основаны.на.той.или.иной.форме.минимакса.
Минимакс.(с.расширениями,.такими.как.альфа-бета-отсечение).оказался.на-
столько.эффективным.в.шахматах,.что.привел.к.громкому.поражению.чемпиона.
мира.по.шахматам.среди.людей.Гарри.Каспарова.в.1997.году.от.шахматного.ком-
пьютера.Deep.Blue,.созданного.компанией.IBM..Этот.долгожданный.матч.стал.
событием,.которое.в.корне.изменило.ситуацию..Прежде.шахматы.считались.самой.
высокоинтеллектуальной.игрой..Тот.факт,.что.компьютер.смог.превзойти.в.ней.
человека,.показал,.что.к.искусственному.интеллекту.следует.относиться.серьезно.
Спустя.два.десятилетия.подавляющее.большинство.шахматных.движков.по-
прежнему.основаны.на.той.или.иной.версии.минимакса..Сегодняшние.минимакс-
ные.шахматные.движки.намного.превосходят.возможности.лучших.шахматистов.
мира..Новые.методы.машинного.обучения.бросают.вызов.чисто.шахматным.
движкам,.построенным.на.основе.минимакса.(с.расширениями),.но.им.еще.пред-
стоит.доказать.свое.превосходство.в.шахматах.
Чем.выше.коэффициент.ветвления.в.игре,.тем.меньше.эффективность.минимакса..
Коэффициент.ветвления.—.это.среднее.количество.потенциальных.ходов.в.данной.
позиции.игры..Вот.почему.последние.достижения.в.компьютерной.реализации.
игры.го.потребовали.изучения.других.областей,.таких.как.машинное.обучение..

---

242
Глава 8.
Состязательный поиск
Недавно.искусственный.интеллект.для.го,.построенный.на.основе.машинного.
обучения,.победил.лучшего.игрока..Коэффициент.ветвления.(и,.следовательно,.
пространство.поиска).для.го.оказывается.просто.непосильным.для.алгоритмов,.
основанных.на.минимаксном.алгоритме,.которые.пытаются.генерировать.деревья,.
содержащие.будущие.позиции.игры..Но.го.—.это.скорее.исключение,.чем.правило..
Большинство.традиционных.настольных.игр.—.шашки,.шахматы,.Connect.Four,.
скрэбл.и.т..п..—.имеют.довольно.малое.пространство.поиска,.так.что.методы,.
основанные.на.минимаксных.алгоритмах,.в.них.хорошо.работают.
Если.вам.нужно.реализовать.нового.искусственного.противника.в.настольной.
игре.или.даже.построить.ИИ.для.пошаговой.компьютерной.игры,.то.минимакс,.
вероятно,.первый.алгоритм,.к.которому.следует.обратиться..Минимакс.можно.
использовать.для.экономических.и.политических.симуляций,.а.также.для.экс-
периментов.в.области.теории.игр..Альфа-бета-отсечение.должно.работать.для.
любой.формы.минимакса.
8.6. УПРАЖНЕНИЯ
1.. Напишите.модульные.тесты.для.игры.в.крестики-нолики,.чтобы.убедиться.
в.правильной.работе.свойств.
getLegalMoves()
,.
isWin()
.и.
isDraw()
.
2.. Напишите.модульные.тесты,.проверяющие.минимакс.в.Connect.Four.
3.. Код.в.файлах.
TicTacToe.java
.и.
ConnectFour.java
.практически.идентичен..