Играем в игры с ИИ
Допустим, вы играете в игру с другом. А показатель «насколько хорошо вы выступаете в этой игре» измеряется числовым баллом, который увеличивается, когда вы приближаетесь к «победе в игре», чем ваш друг, и уменьшается, когда ваш друг приближается к «победе в игре», чем вы. В этой обстановке вы можете думать о себе как о пытающемся максимизировать счет, а о своем друге как о пытающемся минимизировать его.
Мы можем придумать алгоритм, способный принимать правильные решения и выигрывать в такой игре, моделируя описанную выше ситуацию следующим образом: у нас будет 2 объекта (функции), которые вызывают друг друга; один пытается максимизировать балл, другой - минимизировать его. По сути, эти 2 функции будут имитировать двух игроков.
Этот алгоритм также является хорошим примером искусственного интеллекта, а не машинного обучения. Некоторые люди путают это и думают, что AI = ML; на самом деле ML - это подмножество AI. Некоторые методы искусственного интеллекта не связаны с машинным обучением. Минимаксный алгоритм - это такой алгоритм, который заставляет компьютеры вести себя разумно, но они ничему не учатся. И, несмотря на это, он неплохо работает во многих играх.
Минимаксный алгоритм
Если мы думаем об игре с точки зрения этих двух игроков, Макс и Мин, меняющих ходы друг с другом, то мы можем представить игру в виде дерева решений. Давайте посмотрим на довольно простой пример:
Каждый узел в этом дереве (за исключением конечных узлов) представляет решение, которое должно быть принято в данный момент в игре. Мы решаем, какой шаг предпринять. В этом примере нам нужно выбрать только из 2 движений, но в целом у нас может быть любое количество движений, и это количество может варьироваться от узла к узлу, в зависимости от состояния игры.
Верхний узел (тот, что на глубине 0) - это текущее состояние игры. Здесь мы должны выбрать следующее движение в игре. Здесь мы начинаем с Макса, поскольку именно игрок хочет того, что мы делаем: максимизировать счет. Вместо того чтобы принимать решение, основываясь только на следующих возможных состояниях игры, которых Макс может достичь с этого момента, он думает: «После того, как я сделаю один из этих ходов, что сделает мой противник Мин?»
Итак, он звонит Мин и говорит: «Эй, какой ход ты сделаешь, если я выберу левую?», А затем: «Какой ход ты сделаешь, если я выберу правильный?».
После того, как Макс узнает, что сделает Мин, он выберет ту ветку, которая принесет ему максимальное количество очков.
Но ждать. Как Мин решит, что делать, чтобы минимизировать счет? Он будет применять ту же стратегию, что и Макс. Мин, в свою очередь, позвонит Максу, чтобы спросить его, что он будет делать для каждого возможного выбора Мин. Но после этого, вместо того чтобы делать выбор, который максимизирует счет, Мин сделает обратное: сделает выбор, который минимизирует счет.
И так далее ... Каждый будет вызывать другого, рекурсивно строя большое дерево, пока не достигнет конечного состояния.
Конечным состоянием предпочтительно должно быть состояние, в котором игра завершена. Но обычно это слишком дорого с точки зрения вычислений; позволяя алгоритму исследовать все возможные ходы до конца игры, может потребоваться очень много времени. Итак, мы установили максимальную глубину. Состояние игры будет считаться конечным, когда либо игра закончена, либо достигнута максимальная глубина.
В приведенном выше примере состояния терминала находятся внизу (глубина 2).
Что будет на оконечных узлах?
Любой игрок, который достигнет конечных состояний, будь то Макс или Мин, не сможет применить ту же стратегию, которая использовалась до сих пор; стратегия обращения за помощью к другому игроку.
Теперь в оконечных узлах нам нужно подсчитать счет игры в каждом из этих оконечных состояний.
В некоторых играх это может быть не так очевидно, но нам нужно, по крайней мере, оценить счет на основе этого состояния игры.
В нашем примере выше оценки конечных состояний - это числа внизу: 1, 2, 3 и 4.
Единственное, что игрок Max будет делать на этом последнем уровне, это вернуть эти очки вызывающему Min на предыдущем уровне.
После этого наше дерево будет выглядеть так:
Варианты, которые сделает Мин, отмечены стрелкой. Баллы распространяются с уровня 2 на уровень 1 (минимальный уровень).
Теперь, когда мы знаем, что произойдет на глубине 1, мы позволяем Максу делать свой ход на уровне 0:
Это означает, что оптимальным ходом в текущем состоянии игры является ход, представленный правым краем этого верхнего узла, и мы получим не менее 3 очков.
Я говорю «по крайней мере», потому что этот алгоритм работает так, как будто и Макс, и Мин всегда выбирают лучший ход. Но если на самом деле наш враг хуже Мин, мы можем получить лучший результат.
Итак, как мы можем четко выразить этот алгоритм в коде? Вышеупомянутое дерево было просто для интуитивного описания. Компьютеру не нужно явно строить такое дерево. Все, что нам нужно, это 2 функции: максимизировать и минимизировать, которые будут вызывать друг друга.
Вот набросок описанного выше алгоритма:
Функция maximize() возвращает кортеж, который содержит в своей первой позиции дочернее состояние игры, которое максимизирует счет, а во второй позиции - оценку оценки, которая будет достигнута при отслеживании этого состояния. Аналоговая величина возвращается функцией minimize().
Приведенная ниже функция decision() принимает в качестве входных данных текущее состояние игры и возвращает состояние, которому следует следовать, если мы хотим максимизировать наш счет.
eval() - это функция, которая оценивает оценку своего входного состояния игры.
Минимакс с обрезкой α - β
Чем больше глубина, тем лучше будет наш плеер. Но этот алгоритм может занять некоторое время, если мы установим для него большую глубину. Итак, мы должны выбрать максимально возможную глубину, которая все еще соответствует нашим требованиям времени. Можем ли мы сделать этот алгоритм немного быстрее, чтобы мы могли использовать большее значение глубины, при этом соблюдая временные ограничения?
Давайте посмотрим на следующий пример:
Чтобы определить перемещение верхнего узла, нужно ли нам оценивать все узлы в дереве?
Отсечение α - β - это стратегия, которую мы можем использовать для улучшения алгоритма Minimax, игнорируя некоторые ветви дерева, о которых мы заранее знаем, что они не помогут нам в принятии оптимального решения. Название «обрезка α - β» происходит от двух параметров, используемых в этом алгоритме: α и β.
Теперь, как этот метод работает?
Каждый раз, когда мы устанавливаем оценку узла, мы также распространяем его вверх по дереву на его родительский узел и используем его, чтобы установить нижнюю или верхнюю границу результата родительского узла.
Например, в нашем дереве, если мы начнем оценивать узлы слева направо после того, как установим оценку крайнего левого конечного узла (который равен 4), мы знаем, что результат для родительского узла не может быть больше 4. Это потому, что parent - это узел Min, и если у нас уже есть 4, родительский узел не может выбрать что-то большее, чем это.
Но на данный момент эта информация не слишком помогает. Давайте продолжим и посмотрим, что будет. Мы оцениваем следующий конечный узел и обнаруживаем, что значение родительского узла равно 3, а верхний узел не может быть меньше 3. И эта информация нам поможет.
Если мы продолжим оценивать узлы, мы обнаружим терминал с оценкой 2, а это означает, что его родительский элемент должен быть ≤ 2.
Теперь нужно ли нам также оценить последний узел? Нет. Мы уже знаем, что верхний узел может получить как минимум 3, если он следует за левой ветвью. И мы знаем, что из правой ветви мы не можем получить больше 2. Итак, с этого момента мы можем просто игнорировать правую ветвь.
В этом небольшом примере это может показаться не большим улучшением, поскольку мы пропустили только один конечный узел. Но в большем дереве один такой узел может содержать довольно большое поддерево. И обратите внимание, что здесь мы пропустили только один родственный узел, потому что он был единственным оставшимся в этой ветке. Если бы оставалось больше узлов, мы бы пропустили их все. Например, если правая ветвь имела 2, 1 и 0 в качестве конечных узлов, то после того, как мы оценим 2, мы сможем пропустить как 1, так и 0.
Кроме того, количество пропущенных узлов будет зависеть от порядка конечных узлов. Вы, наверное, заметили, что в этом примере я поменял местами оценки с 1, 2, 3, 4 на 4, 3, 2, 1. Это было не случайно. Когда оценки расположены в порядке возрастания, это наихудший сценарий, при котором обрезка не происходит. Но вероятность того, что такое неправильное упорядочение возникнет на практике, невелика. В среднем, обрезка α - β позволяет минимаксному алгоритму пройти почти вдвое глубже за то же время по сравнению с отсутствием обрезки.
Ниже представлен псевдокод описанного выше алгоритма.
Альфа - это самая большая нижняя граница среди (прямых или косвенных) родительских узлов Max, а Beta - наименьшая верхняя граница среди (прямых или косвенных) родительских узлов Min. В режиме максимизации при итерации по дочерним узлам мы обновляем альфа-значение, чтобы оно было максимальной оценкой, найденной на данный момент, и если эта максимальная оценка больше, чем бета-версия, мы знаем, что есть родительский узел Min, который не будет выбирать нашу текущую ветвь, поэтому мы прекратить исследовать оставшиеся дочерние узлы. Аналоговая штука бывает свести к минимуму.
Бесконечность - / + в функции принятия решения (первый вызов максимизации) означает, что мы начинаем алгоритм без каких-либо ограничений на то, какой может быть результирующий результат.
Итак, минимаксный алгоритм - это относительно простой алгоритм, который хорошо работает в простых играх (низкий коэффициент ветвления). Это также хороший пример искусственного интеллекта, который не является машинным обучением.
В следующих нескольких статьях я покажу, как использовать этот алгоритм (вместе с Selenium WebDriver) для создания ИИ, способного играть в игру 2048 в прямом эфире на наших экранах.
Надеюсь, эта информация была для вас полезной, и спасибо за внимание!
Эта статья также размещена на моем собственном сайте здесь. Не стесняйтесь смотреть!
