Сможете ли вы превзойти то, что только что создали?

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

Минимаксный алгоритм

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

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

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

  1. Найдите все возможные ходы на текущем этапе игры.
  2. Для каждого возможного хода возвращайтесь вниз по иерархии, пока не найдете лист.
  3. Если текущий узел является листом, сделайте следующее:

3а. Если игрок - Макс, вернуть максимальное количество очков текущего листового узла и его братьев и сестер.

3b. Иначе вернуть минимум

4. После того, как рекурсия завершится и алгоритм вернется к месту первоначального вызова, решите, основываясь на вычисленном счете и текущем игроке (минимальном или максимальном), какой путь выбрать.

Алгоритм обратного отслеживания.

Сколько времени это занимает

Скажем, время, необходимое для раскрытия узла, оказывается постоянным и имеет значение c, и у нас есть дерево с коэффициентом ветвления 3, т.е. каждый раз, когда любой узел раскрывается, он расширяется еще на 3 узла (обычно коэффициент ветвления уменьшается с глубиной, как в крестики-нолики, как вы увидите позже в этом эпизоде) . Обратите внимание: изначально есть один узел, корень, узлы на уровне 0 равны 3⁰ (= 1), он расширяется до 3 узлов, поскольку коэффициент ветвления равен 3, поэтому на уровне 1 имеется 3¹ узлов, на следующем На уровне каждый из 3 узлов расширяется на еще 3 узла, поэтому на уровне 2 имеется 3x3 = 9 = 3² узла. Заметили закономерность? На уровне d есть 3 ^ d узлов. Если коэффициент ветвления равен b, то на уровне d имеется b ^ d узлов.

Теперь общие усилия, необходимые для расширения всех узлов, представляют собой сумму узлов, развернутых на каждом уровне. Как и на уровне 0, его c.3⁰ = c, на уровне 1 его c.3¹ = 3c и так далее. Суммарное усилие для коэффициента ветвления b и глубины d составляет,

общее усилие = c.b⁰ + c.b² + c.b³ +… + c.b ^ d

Учитывая самый большой член и опуская постоянную часть, временная сложность становится O (b ^ d).

Для таких игр, как шахматы, среднее количество возможных ходов в каждом конкретном случае составляет 35, а средняя глубина составляет около 100, что означает, что для имитации шахматной игры из любой заданной точки потребуется примерно 35¹⁰⁰ или 2,55x10¹⁵⁴ узлов, и это только средний, а не худший случай!

Можем ли мы сделать лучше?

Minimax - большой шаг вперед для ИИ, конкурирующего с людьми, но слишком наивен для большинства стратегических игр. Тот факт, что он расширяет каждый узел до листьев, заставляет его спотыкаться о землю. ИИ можно научить обрезать некоторые ветви, если они не кажутся достаточно многообещающими. Это называется обрезкой α-β. Это не алгоритм сам по себе, скорее, как Minimax 2.0.

Основная идея состоит в том, чтобы поддерживать две переменные, называемые альфа и бета, которые отслеживают, насколько полезно расширять следующий узел. Альфа максимизируется, а бета минимизируется. Алгоритмический псевдокод для крестиков-ноликов с обрезкой α-β приведен в следующем разделе.

Алгоритм

Алгоритм почти легко можно воспроизвести в работающей реализации Python с некоторыми синтаксическими изменениями.

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

  • +/- inf обозначают положительную и отрицательную бесконечности. win () - это служебная функция, которая проверяет конфигурацию доски, чтобы определить, выигрывает ли игрок. findEmptySlots () просматривает каждую ячейку, чтобы найти пустую. Логика здесь состоит в том, чтобы вернуть -10 при проигрыше, +10 при выигрыше и 0 при ничьей - с точки зрения Мин (ИИ-игрок) с добавленной компенсацией, следовательно, вычитая глубину.

Моделирование

Давайте на самом деле применим алгоритм в реальной игре с крестиками-ноликами на ближнем конце и посмотрим, как он работает. Рассмотрим следующий этап игры: O для AI, X для человека.

У него 3 пустых слота. С этого момента 11 новых узлов могут быть расширены следующим образом, очевидно, что на данном этапе нет единого хода, который может привести к победе ИИ,

Вот соглашение,

  • кортеж внутри каждого уникален как минимум по одному значению
  • первое значение обозначает номер узла в соответствии с порядком обхода, например, узел (3, 1, 2) - это третий узел, который нужно посетить
  • второе значение обозначает глубину, а третье обозначает количество пустых слотов на этом этапе.
  • числа по краю также обозначают глубину, красные числа под каждым листом обозначают окончательную оценку, +/- (10-глубина)
  • наконец, узлы, обведенные красным, - это те, которые были обрезаны

Попробуйте сами, алгоритм должен отсечь 4 узла.

Насколько лучше альфа-бета-обрезка по сравнению с Minimax, это в основном зависит от порядка узлов, если самый левый узел содержит лучший путь, алгоритм обрезает другие ветви, если нет - требуется то же время как Minimax, если не хуже, для обработки переменных альфа и бета. Среднюю сложность можно суммировать до O (sqrt (b ^ d)).