Новости

«Классические задачи Computer Science на языке Java» — это мастер-класс по программированию, содержащий 55 практических примеров, затрагивающих самые актуальные темы: базовые алгоритмы, ограничения, искусственный интеллект и многое другое.

В этой книге:

— Рекурсия, мемоизация и битовые манипуляции.
— Поисковые, графовые и генетические алгоритмы.
— Проблемы ограничений.
— Кластеризация методом k-среднего, нейронные сети и состязательный поиск.

Состязательный поиск

Идеальная информационная игра для двух игроков с нулевой суммой и точной информацией — это игра, в которой оба соперника имеют всю доступную им информацию о состоянии игры и все, что является преимуществом для одного, становится потерей преимущества для другого. К таким играм относятся крестики-нолики, Connect Four, шашки и шахматы. В этой главе вы узнаете, как создать сильного искусственного соперника, способного играть в такие игры. В сущности, обсуждаемые методы в сочетании с современными вычислительными возможностями позволяют создавать искусственных соперников, которые прекрасно играют в простые игры этого класса и способны играть в сложные игры, выходящие за пределы возможностей любого соперника-человека.

8.1. Основные компоненты настольной игры

Как и при рассмотрении большинства более сложных задач в предыдущих главах, постараемся сделать решение как можно более обобщенным. В случае состязательного поиска это означает, что наши алгоритмы поиска не должны зависеть от игры. Начнем с определения нескольких простых базовых классов, которые выявляют состояние, необходимое алгоритмам поиска. Затем создадим подклассы базовых классов для конкретных игр (крестики-нолики и Connect Four) и введем эти подклассы в алгоритмы поиска, чтобы они могли «играть» в эти игры. Вот базовые классы (листинг 8.1).

Листинг 8.1. Piece.java

Совет
Поскольку в крестиках-ноликах и игре Connect Four существует только один вид фигур, класс Piece в этой главе может использоваться как индикатор хода. В более сложных играх, таких как шахматы, где есть разные виды фигур, ходы могут обозначаться целым числом или логическим значением. В качестве альтернативы можно применять для обозначения хода атрибут color более сложного типа Piece.

Piece — это базовый класс для фигуры на доске в игре. Его другая роль — индикатор хода. Именно для этого необходимо свойство opposite. Нам нужно знать, чей ход следует за текущим ходом (листинг 8.2).

Листинг 8.2. Board.java

Класс Board является фактическим хранилищем состояния. Для любой конкретной игры, которую будут выполнять алгоритмы поиска, они должны уметь ответить на следующие вопросы.

• Чей сейчас ход?

• Какие ходы можно сделать из текущей позиции согласно правилам?

• Выиграна ли сейчас игра?

• Сыграна ли игра вничью?

Последний вопрос, касающийся ничьих, на самом деле комбинация двух предыдущих вопросов для многих игр. Если игра не выиграна, но возможных ходов нет, то это ничья. Вот почему в классе Board сразу можно создать конкретную реализацию метода isDraw(). Кроме того, есть еще несколько действий, которые необходимо реализовать.

• Сделать ход, чтобы перейти из текущей в новую позицию.

• Оценить позицию, чтобы увидеть, какой игрок имеет преимущество.

Каждый метод и свойство класса Board являются реализацией одного из предыдущих вопросов или действий. На языке игры класс Board можно было бы назвать Position, но мы используем это имя для чего-то более конкретного в каждом из подклассов.

Класс Board имеет общий тип Move. Тип Move представляет собой ход в игре. Это может быть просто целое число. В таких играх, как крестики-нолики и Connect Four, целое число представляет ход, указывая клетку или столбец, где должна быть размещена фигура. В более сложных играх для описания хода может потребоваться большее число, чем целое число. Move позволяет классу Board представлять более широкий спектр игр.

8.2. Крестики-нолики

Крестики-нолики — простая игра, но ее можно взять для иллюстрации того же минимаксного алгоритма, который применяется в сложных стратегических играх, таких как Connect Four, шашки и шахматы. Мы построим искусственный интеллект, который прекрасно играет в крестики-нолики с помощью минимаксного алгоритма.

Примечание
В этом разделе предполагается, что вы знакомы с игрой в крестики-нолики и ее стандартными правилами. Если нет, то, чуть-чуть поискав в интернете, вы найдете их.

8.2.1. Управление состоянием игры в крестики-нолики

Давайте разработаем несколько структур, позволяющих отслеживать состояние игры в крестики-нолики по мере ее развития.

Прежде всего нужен способ представления каждой клетки на игровом поле. Будем использовать перечисление TTTPiece — подкласс класса Piece. Клетка в игре в крестики-нолики может иметь значение X, 0 или быть пустой (в перечислении такие обозначаются E) (листинг 8.3).

Листинг 8.3. TTTPiece.java

В классе TTTPiece имеется свойство opposite, которое возвращает другой экземпляр TTTPiece. Это будет полезно для передачи хода от одного игрока к другому после того, как очередной ход игры завершен. Для представления ходов используем обычное целое число, соответствующее клетке на поле, где был поставлен крестик или нолик. Как вы помните, Move был определен в классе Board. Укажем, что Move при определении TTTPiece — целое число.

В игре в крестики-нолики существует девять позиций, образующих три ряда по три столбца. Для простоты эти девять позиций можно представить в виде одномерного списка. То, какие клетки получат какие номера (другими словами, индексы в массиве), не имеет значения, но мы будем придерживаться схемы, показанной на рис. 8.1.

Главным хранилищем состояния игры будет класс TTTBoard. Он отслеживает два элемента состояния: позицию, представленную вышеупомянутым одномерным списком, и игрока, который сейчас делает ход (листинг 8.4).

Листинг 8.4. TTTBoard.java

Исходное состояние поля — такое, при котором еще не сделано ни одного хода (пустое поле). Конструктор без параметров для TTTBoard инициализирует такую позицию, при которой первый игрок готовится поставить X (обычный первый ход в игре). getTurn() указывает, чья очередь находится в текущей позиции, X или O.

TTTBoard — это по соглашению неизменяемая структура данных: структуры TTTBoard не должны изменяться. Вместо этого каждый раз, когда необходимо сделать ход, будет генерироваться новая структура TTTBoard, позиция которой изменена с учетом хода. Впоследствии это пригодится в алгоритме поиска. При ветвлении поиска мы не сможем случайно изменить положение на поле, начиная с которого все еще анализируются потенциально возможные ходы (листинг 8.5).

Листинг 8.5. TTTBoard.java (продолжение)

Допустимым ходом в игре является любая пустая клетка. getLegalMoves() ищет любые пустые клетки на поле и возвращает их список (листинг 8.6).

Листинг 8.6. TTTBoard.java (продолжение)

Существует множество способов просмотреть строки, столбцы и диагонали на поле игры, чтобы проверить, завершилась ли она победой. В показанной далее реализации метода isWin()вместе с его вспомогательным методом checkPos() это сделано посредством жестко закодированной конструкции из &&, || и ==, которая кажется бесконечной (листинг 8.7). Это не самый красивый код, но он простой и выполняет свою работу.

Листинг 8.7. TTTBoard.java (продолжение)

Если все клетки строки, столбца или диагонали не пустые и содержат одинаковые элементы, то игра выиграна.

Игра закончена вничью, если она не выиграна и не осталось допустимых ходов (это свойство уже описано в методе isDraw() класса Board). Наконец, нам нужен способ оценки конкретной позиции и структурного вывода состояния поля (листинг 8.8).

Листинг 8.8. TTTBoard.java (продолжение)

В большинстве игр приходится вычислять позицию приблизительно, поскольку мы не можем пройти игру до самого конца, чтобы точно определить, кто выиграет или проиграет в зависимости от того, какие ходы будут сделаны. Но в крестиках-ноликах довольно малое пространство поиска, так что мы можем пройти его от любой позиции до конца игры. Следовательно, метод evaluate() может просто возвращать некое число, если игрок выиграл, меньшее число — в случае ничьей и совсем малое — в случае проигрыша.

С полным содержанием статьи можно ознакомиться на сайте "Хабрахабр":

https://habr.com/ru/company/piter/blog/581646/