Сможете ли вы превзойти то, что только что создали?
Интересно, почему обычному человеку практически невозможно обыграть компьютер в стратегических настольных играх, таких как шахматы, го или крестики-нолики? Это потому, что компьютеры могут буквально заглядывать в будущее (или, если быть точным, фьючерсы) игры и принимать соответствующие решения о предстоящих действиях. Класс алгоритмов, используемых в этом контексте, известен как состязательный поиск. Основной мотив таких алгоритмов - играть в обороне и не дать сопернику победить любой ценой. Так что, пока вы не сядете с листом бумаги и не попытаетесь смоделировать результат до определенной глубины, прежде чем завершить какие-либо ходы, шансы, что вы проиграете, довольно высоки.
Минимаксный алгоритм
Как указывалось ранее, ИИ, которые используют состязательный поиск, действуют в оборонительной манере, стремясь не к победе, а к минимизации потерь настолько, насколько позволяет ситуация. Это известно как неприятие потерь. Обратите внимание, что в случае таких решающих игр, упомянутых выше, вся игра может быть представлена деревом решений, где каждое начальное решение приводит к определенному уникальному листу.
В алгоритме Minimax каждому терминальному узлу (называемому листьями) присваивается значение (подробнее об этом присвоении значения позже). Играют два игрока, которых зовут Мини (традиционно ИИ-игрок) и Макс (противник-человек). Первоначальный ход всегда делает Макс. Подстрекательство каждого игрока состоит в том, чтобы максимизировать полезность в свой ход и свести к минимуму в свой ход оппонента. Вот типичное дерево игры,
Обратите внимание, что первый ход делает Макс, и игра продолжается с чередующимися игроками. Алгоритм, написанный простым английским языком, выглядит так:
- Найдите все возможные ходы на текущем этапе игры.
- Для каждого возможного хода возвращайтесь вниз по иерархии, пока не найдете лист.
- Если текущий узел является листом, сделайте следующее:
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)).