Игра в стратегии с алгоритмом Minimax

Грант Бартель

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

В моем предыдущем посте «Как выиграть судоку» мы узнали, как научить компьютеры решать головоломки судоку. Если вы ее не читали, то вперед и бегло прочитайте. Но на самом деле это был просто способ намочить ноги, прежде чем погрузиться в более изощренные методы игровых агентов. Особенно те методы, которые могут сделать стратегические ходы против противника!

Не застрять

Isolation (или Isola) — это настольная пошаговая стратегическая игра, в которой два игрока пытаются удержать своего противника на доске, похожей на шашки 7×7. В конце концов, они больше не могут сделать ход (тем самым изолируя их).

У каждого игрока есть одна фигура, которую он может двигать как ферзя в шахматах — вверх-вниз, влево-вправо и по диагонали. Есть три условия, при которых фигуры могут двигаться:

1. Они не могут поставить свою фишку на уже посещенную клетку.
2. Они не могут пересекать уже посещенные квадраты (можно протискиваться через них по диагонали).
3. Они не могут пересекать кусок друг друга.

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

Сейчас это может показаться простой игрой — и, честно говоря, так оно и есть. Это не похоже на то, что мы играем в покер или Starcraft. Тем не менее, существует огромное количество возможных ходов, которые любой игрок может сделать в любой момент игры.

В таких головоломках, как судоку, есть «ответ», который мы хотим найти. Но нет ответа, когда дело доходит до стратегических игр.

Мы играем против другого противника — человека, компьютера или кота-детектива. Это требует стратегии и некоторого размышления о том, как может сложиться игра по ходу ее развития.

Такие игры могут развиваться и приводить к абсурдному количеству возможных результатов. Поэтому нам нужно подумать о том, как мы можем выбрать наилучший возможный ход, не тратя столько времени, сколько потребовалось кошкам, чтобы заселить Землю.

Хорошо, больше никаких кошек!

Могучий минимакс и друзья

Теперь, когда вы знаете, как играть в «Изоляцию», давайте посмотрим, как мы можем использовать минимакс алгоритм; основной продукт в сообществе ИИ. Мы также рассмотрим эвристические оценки, итеративное углубление, а также альфа-бета обрезка. Вместе с этим мы можем создать конкурентоспособного агента ИИ.

Минимакс

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

Теперь, как это выглядит?

Ну, подобно тому, как агент ИИ будет играть в игру вроде судоку, мы можем смоделировать следующие возможные ходы, которые любой игрок может сделать с помощью дерево поиска. Однако нам нужно будет использовать дерево поиска с переменной шириной — или, другими словами, шириной уровня дерева. Причина в том, что каждый игрок может сделать разное количество ходов в любой момент игры.

Дерево, показанное выше, представляет следующие ходы, доступные во время игры в изоляцию. Он имеет сетку 2×3, при этом нижний правый квадрат недоступен. Как видите, два игрока — это синий круг и красный крест.

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

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

Теперь вам может быть интересно, что это за треугольники под каждым ходом?

Нисходящий треугольник представляет место в дереве, где минимакс будет свести к минимуму преимущество соперника. Принимая во внимание, что восходящие треугольники — это места, где минимакс максимизирует преимущество агента.

Но минимакс может знать преимущество любого из игроков только в том случае, если ему известны пути в дереве, ведущие к победе любого из игроков. Это означает, что минимакс должен пройти к самому низу дерева для каждой возможной серии ходов. Затем он должен присвоить некоторый балл (например, +1 за победу и -1 за поражение) и распространить эти числа вверх по дереву. Таким образом, в каждом игровом состоянии или узле дерева есть информация о том, какой из игроков может получить наибольшую выгоду от любого потенциального хода.

По этой картинке мы можем сделать пару наблюдений. Первый минимакс присваивает номер окончательным исходам игры на листовые узлы. Затем он распространяет их вверх по дереву, выполняя по пути минимизацию и максимизацию. Как только минимакс заканчивает заполнять дерево, всякий раз, когда наступает очередь агента ИИ, он будет знать, какие ходы, скорее всего, приведут к победе или проигрышу.

Второй уровень после корневого узла показывает следующие возможные ходы для синего игрока (нашего агента ИИ). Наш агент хочет максимизировать доступные очки во время своего хода. Таким образом, он выберет ход, представленный в крайнем правом узле, следующем за корневым узлом. Очень круто!

Но имеет ли смысл просто присваивать +1 или -1 результатам игры? Разве этот счет не должен учитывать, как игра выиграна или проиграна?

Спойлер: ответ — да!

Эвристические оценки

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

Вероятно, мы можем придумать неограниченное количество эвристических оценок. Но здесь мы рассмотрим лишь некоторые из них, кроме наивная оценка (NS) +1 и -1.

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

Другая идея может состоять в том, чтобы использовать значение, полученное из OMS, и вычесть количество следующих возможных ходов, которые есть у противника. Причина в том, что каждый игрок хочет увеличить количество своих ходов, одновременно уменьшая количество ходов своего противника. Мы назовем это улучшенный балл (IS).

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

Интересно, что первые два почти точно такие же, как улучшенный балл. Мы позвоним им агрессивный улучшенный показатель (AIS) а также суперагрессивная улучшенная оценка (SAIS). Но есть небольшая разница между этими партитурами и оригиналом. К двум лучшим результатам применяется коэффициент два и три к значению, которое вы вычитаете (количество ходов, доступных противнику) при подсчете улучшенного счета.

Вы можете найти оптимальный «фактор агрессии» для применения при подсчете этого балла!

Еще один спойлер — существуют лучшие значения.

Но что, если мы придумаем эвристический показатель, который требует много времени для вычисления? А если дерево большое? Будет ли у нашего агента ИИ достаточно времени, чтобы найти свои следующие лучшие ходы, и при этом он будет достаточно отзывчивым во время игры?

Итеративное углубление

Теперь мы знаем, что наш агент ИИ может моделировать все возможные ходы, используя дерево поиска и соответствующую эвристическую оценку его узлов. Но, к сожалению, при игре в Изоляцию наше дерево будет огромным. Поиск по дереву и вычисление этих значений занял бы больше времени, чем лет после Большого взрыва!

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

Но как работает итеративное углубление?

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

Теперь это дает некоторое представление о том, насколько это может быть сложно. Создание агента ИИ, достаточно умного и отзывчивого для стратегических игр, может быть довольно сложной задачей даже для волшебников ИИ. Особенно, если такие игры таят в себе целый мир возможностей.

К сожалению, количество ходов, которые агент ИИ может «вообразить», ограничено.Так что вполне возможно, что он может принять решение, которое приведет к его гибели. Это известное явление, называемое эффект горизонта. Но нам все еще нужно взглянуть на, пожалуй, самый эффективный алгоритм сокращения времени, используемый при поиске деревьев.

Альфа-бета обрезка

Ладно, это изюм, а не чернослив, но все же — откуда они вообще были? Я имею в виду, серьезно, блюзовую группу?

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

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

Если мы сможем это сделать, это может значительно сократить время отклика нашего агента ИИ и повысить производительность.

Как работает альфа-бета обрезка?

Минимаксный алгоритм перемещается по дереву, используя поиск в глубину. Это означает, что он проходит через дерево слева направо и всегда идет максимально глубоко. Затем он обнаруживает значения, которые должны быть присвоены узлам непосредственно над ним, даже не глядя на другие ветви дерева.

Сокращение альфа-бета позволяет минимаксу принимать такие же правильные решения, как и минимакс в одиночку, но с более высоким уровнем производительности.

Рассмотрим следующее изображение, на котором у нас есть дерево с различными оценками, присвоенными каждому узлу. Некоторые узлы заштрихованы красным, что указывает на то, что их не нужно просматривать.

В левом нижнем углу дерева минимакс смотрит на значения 5 и 6 на нижнем максимальном уровне. Он определяет, что 5 должно быть присвоено минимальному уровню прямо над ним. Имеет смысл.

Но, посмотрев на 7 и 4 правой ветки максимального уровня, он понимает, что указанному выше узлу минимального уровня должно быть присвоено максимальное значение 4.Поскольку второй максимальный уровень прямо над первым минимальным уровнем будет принимать максимум от 5 до максимум 4, ясно, что он выберет 5. После этого он продолжит обход дерева, чтобы выполнить тот же точный набор операций внутри другие ветки дерева.

Ниже приведено алгоритмическое представление минимакса с сокращением альфа-бета.

Использование этого метода обеспечивает простой способ сократить пространство поиска нашего агента ИИ. Таким образом, сокращение альфа-бета позволяет минимаксам принимать правильные решения, которые минимакс мог бы принимать в одиночку, но с более высоким уровнем производительности.

Изола-тер

Мы рассмотрели, как создать собственного ИИ-агента, способного играть в игру «Изоляция» на довольно конкурентном уровне. Используя алгоритм minmax, мы увидели, как агент ИИ может моделировать игру и принимать решения на основе эвристической оценки. Мы также узнали, как определить четко определенную эвристику для нашей задачи (изоляция).

Но мы также обнаружили, что это было бы слишком интенсивно с точки зрения вычислений, чтобы позволить минимаксу разгуляться. Поэтому нам пришлось использовать такие методы, как итеративное углубление и сокращение альфа-бета. Это заставит нашего агента ИИ придумать следующий ход в разумные сроки. Но что, если мы хотим, чтобы у нашего ИИ-агента был более высокий процент побед, но, по крайней мере, он был таким же отзывчивым, как человек?

Что ж, есть и другие методы, которые мы могли бы изучить, чтобы увеличить процент побед нашего агента, а также время отклика. Мы коснулись идеи настройки параметров нашей эвристической оценки (помните «агрессивный фактор»?). Мы могли бы даже придумать эвристический счет, лучше приспособленный для игры в «Изоляцию».

Есть также отражающие свойства, связанные с возможными ходами на доске изоляции. Это становится очевидным, когда мы анализируем полностью заполненное дерево поиска, что потенциально позволяет нам сократить множество ветвей из дерева поиска. Кроме того, если бы мы обновили наше оборудование, наш агент ИИ стал бы быстрее и, таким образом, смог бы исследовать больше возможностей.

Если вы хотите вникнуть в мельчайшие детали того, как реализовать это самостоятельно, взгляните на код, который я написал для решения этой проблемы для моей Наностепени искусственного интеллекта Udacity. Вы можете найти его в моем репозитории GitHub.