Автор оригинала: Mina Krivokuća.
Вступление
Еще в конце 1920-х годов Джон Фон Нейман установил главную проблему теории игр, которая остается актуальной и по сей день:
Игроки ы 1 , с 2 , …, s n играют в заданную игру G. Какие ходы должны играть игроки m , чтобы достичь наилучшего возможного результата?
Вскоре после этого проблемы такого рода переросли в вызов, имеющий огромное значение для развития одной из самых популярных на сегодняшний день областей информатики – искусственного интеллекта. Некоторые из величайших достижений в области искусственного интеллекта достигнуты в области стратегических игр – чемпионы мира в различных стратегических играх уже были побеждены компьютерами, например, в шахматах, шашках, нардах, а совсем недавно (2016 год) даже в Го.
Хотя эти программы очень успешны, их способ принятия решений сильно отличается от человеческого. Большинство этих программ основаны на эффективных алгоритмах поиска , а с недавнего времени и на машинном обучении.
Минимаксный алгоритм-это относительно простой алгоритм, используемый для принятия оптимальных решений в теории игр и искусственном интеллекте. Опять же, поскольку эти алгоритмы в значительной степени зависят от эффективности, производительность ванильного алгоритма может быть значительно улучшена с помощью альфа-бета – обрезки-мы рассмотрим и то, и другое в этой статье.
Хотя мы не будем анализировать каждую игру в отдельности, мы кратко объясним некоторые общие понятия, которые актуальны для двух игроков некооперативных | с нулевой суммой симметричных игр с совершенной информацией – Шахматы, Го, Крестики-нолики, Нарды, Реверси, Шашки, Манкала, 4 в ряд и т. Д…
Как вы, наверное, заметили, ни одна из этих игр не является такой, где, например, игрок не знает, какие карты есть у противника, или где игроку нужно угадать определенную информацию.
Определение Терминов
Правила многих из этих игр определяются правовыми позициями (или правовыми состояниями ) и правовыми ходами для каждой правовой позиции. Для каждой правовой позиции можно эффективно определить все правовые ходы. Некоторые из юридических позиций являются начальными позициями , а некоторые – конечными позициями .
Лучший способ описать эти термины-использовать древовидный граф, узлы которого являются законными позициями, а ребра-законными ходами. График ориентирован, так как это не обязательно означает, что мы сможем вернуться точно туда, откуда мы пришли в предыдущем шаге, например, в шахматах пешка может идти только вперед. Этот граф называется игровым деревом . Перемещение вниз по игровому дереву означает, что один из игроков делает ход, а состояние игры меняется с одной законной позиции на другую.
Вот иллюстрация игрового дерева для игры в крестики-нолики:
Сетки, окрашенные в синий цвет, – это повороты игрока X, а сетки, окрашенные в красный цвет, – повороты игрока O. Конечная позиция (лист дерева) – это любая сетка, где один из игроков выиграл или доска заполнена, а победителя нет.
полное игровое дерево – это игровое дерево, корень которого является начальной позицией, а все листья-конечными позициями. Каждое полное игровое дерево имеет столько узлов, сколько игра имеет возможных исходов для каждого законного сделанного хода. Нетрудно заметить, что даже для таких маленьких игр, как крестики-нолики, полное игровое дерево огромно. По этой причине не рекомендуется явно создавать целое игровое дерево как структуру при написании программы, которая должна предсказывать лучший ход в любой момент. Тем не менее, узлы должны быть созданы неявно в процессе посещения.
Мы определим сложность пространства состояний игры как количество легальных игровых позиций, достижимых из начальной позиции игры, и коэффициент ветвления как количество детей в каждом узле (если это число не является постоянным, то обычно используется среднее значение).
Для крестиков-ноликов верхняя граница размера пространства состояний равна 3 9 =19683. Представьте себе это число для таких игр, как шахматы! Следовательно, поиск по всему дереву, чтобы узнать, какой ваш лучший ход, когда мы делаем поворот, будет очень неэффективным и медленным.
Вот почему Минимакс имеет такое большое значение в теории игр.
Теория Минимакса
Минимаксный алгоритм опирается на систематический поиск, или точнее сказать – на грубую силу и простую функцию оценки. Предположим, что каждый раз, решая следующий ход, мы ищем все дерево, вплоть до листьев. Фактически мы рассматривали бы все возможные исходы и каждый раз могли бы определить наилучший возможный ход.
Однако для нетривиальных игр эта практика неприменима. Даже поиск на определенную глубину иногда занимает неприемлемое количество времени. Поэтому Minimax применяет поиск к довольно низкой глубине дерева с помощью соответствующей эвристики и хорошо разработанной, но простой оценочной функции .
При таком подходе мы теряем уверенность в поиске наилучшего возможного хода, но в большинстве случаев решение, которое принимает минимакс, намного лучше, чем у любого человека.
Теперь давайте подробнее рассмотрим функцию оценки, о которой мы уже упоминали. Чтобы определить хороший (не обязательно лучший) ход для определенного игрока, мы должны каким-то образом оценить узлы (позиции), чтобы иметь возможность сравнивать один с другим по качеству.
Функция оценки-это статическое число, которое в соответствии с характеристиками самой игры присваивается каждому узлу (позиции).
Важно отметить, что функция оценки не должна полагаться ни на поиск предыдущих узлов, ни на поиск следующих. Он должен просто анализировать состояние игры и обстоятельства, в которых находятся оба игрока.
Необходимо, чтобы оценочная функция содержала как можно больше релевантной информации, но с другой стороны – поскольку она вычисляется много раз – она должна быть простой.
Обычно он отображает множество всех возможных позиций в симметричный сегмент:
$$ \mathcal{F}: \mathcal{P} \rightarrow [-M, M] $$
Значение M присваивается только листьям, где победителем является первый игрок, а значение -M листьям, где победителем является второй игрок.
В играх с нулевой суммой значение оценочной функции имеет противоположное значение-что лучше для первого игрока, то хуже для второго, и наоборот. Следовательно, значение для симметричных позиций (если игроки меняются ролями) должно отличаться только по знаку.
Общепринятой практикой является изменение оценок листьев путем вычитания глубины этого точного листа, чтобы из всех ходов, ведущих к победе, алгоритм мог выбрать тот, который делает это за наименьшее число шагов (или выбирает ход, который откладывает проигрыш, если он неизбежен).
Вот простая иллюстрация шагов Минимакса. В данном случае мы ищем минимальное значение.
Зеленый слой вызывает метод Max() на узлах в дочерних узлах, а красный слой вызывает метод Main() на дочерних узлах.
- Оценка листьев:
- Выбор наилучшего хода для зеленого игрока с использованием глубины 3:
Идея состоит в том, чтобы найти наилучший возможный ход для данного узла, глубины и функции оценки.
В этом примере мы предположили, что зеленый игрок ищет положительные значения, в то время как розовый игрок ищет отрицательные. Алгоритм в первую очередь оценивает только узлы на заданной глубине, а остальная часть процедуры является рекурсивной . Значения остальных узлов являются максимальными значениями их соответствующих дочерних элементов, если это ход зеленого игрока, или, аналогично, минимальным значением, если это ход розового игрока. Значение в каждом узле представляет следующий наилучший ход с учетом данной информации.
При поиске в игровом дереве мы рассматриваем только узлы на фиксированной (заданной) глубине, а не те, что были до или после. Это явление часто называют эффектом горизонта .
Открытие книг и Крестики-нолики
В стратегических играх вместо того, чтобы позволить программе начать процесс поиска в самом начале игры, обычно используют открывающие книги – список известных и продуктивных ходов, которые часто встречаются и, как известно, являются продуктивными, в то время как у нас все еще нет большой информации о состоянии самой игры, если мы смотрим на доску.
В начале игры слишком рано, и количество потенциальных позиций слишком велико, чтобы автоматически решить, какой ход, безусловно, приведет к лучшему состоянию игры (или победе).
Однако алгоритм пересматривает следующие потенциальные ходы каждый ход, всегда выбирая то, что в данный момент кажется самым быстрым путем к победе. Поэтому он не будет выполнять действия, которые требуют более одного хода, и из-за этого не может выполнять некоторые хорошо известные “трюки”. Если ИИ играет против человека, то очень вероятно, что человек сразу же сможет предотвратить это.
С другой стороны, если мы посмотрим на шахматы, мы быстро поймем непрактичность решения шахмат путем грубой силы через целое игровое дерево. Чтобы продемонстрировать это, Клод Шеннон вычислил нижнюю границу сложности игрового дерева шахмат, в результате чего около 10 120 возможные игры .
Насколько велико это число? Для справки, если мы сравним массу электрона (10 -30 кг) к массе всей известной вселенной (10 50 -10 60 кг), то соотношение будет иметь порядок 10 80 -10 90 .
Это ~0,0000000000000000000000000000000001% от числа Шеннона.
Представьте себе, что вы просите алгоритм пройти каждую из этих комбинаций только для того, чтобы принять единственное решение. Это практически невозможно сделать.
Даже после 10 ходов количество возможных партий невероятно велико:
| 1 | 20 |
| 2 | 40 |
| 3 | 8902 |
| 4 | 197281 |
| 5 | 4865609 |
| 6 | 119060324 |
| 7 | 3195901860 |
| 8 | 84998978956 |
| 9 | 2439530234167 |
| 10 | 69352859712417 |
Давайте возьмем этот пример для игры в крестики-нолики. Как вы, наверное, уже знаете, самая известная стратегия игрока X заключается в том, чтобы начать в любом из углов, что дает игроку O больше всего возможностей ошибиться. Если игрок О играет что – то помимо центра, а X продолжает свою первоначальную стратегию, это гарантированный выигрыш для X. Открывающие книги именно таковы-некоторые хорошие способы обмануть противника в самом начале, чтобы получить преимущество или, в лучшем случае, победу.
Чтобы упростить код и добраться до сути алгоритма, в примере из следующей главы мы не будем утруждать себя открытием книг или какими-либо умственными трюками. Мы позволим минимаксному поиску с самого начала, поэтому не удивляйтесь, что алгоритм никогда не рекомендует угловую стратегию.
Минимаксная реализация в Python
В приведенном ниже коде мы будем использовать функцию оценки, которая довольно проста и распространена для всех игр, в которых можно искать все дерево, вплоть до листьев.
Он имеет 3 возможных значения:
- -1, если игрок, который стремится к минимальному выигрышу
- 0 если это ничья
- 1 если игрок который стремится к максимальному выигрышу
Поскольку мы будем реализовывать это через игру в крестики-нолики, давайте пройдемся по строительным блокам. Во-первых, давайте сделаем конструктор и нарисуем доску:
# We'll use the time module to measure the time of evaluating
# game tree in every move. It's a nice way to show the
# distinction between the basic Minimax and Minimax with
# alpha-beta pruning :)
import time
class Game:
def __init__(self):
self.initialize_game()
def initialize_game(self):
self.current_state = [['.','.','.'],
['.','.','.'],
['.','.','.']]
# Player X always plays first
self.player_turn = 'X'
def draw_board(self):
for i in range(0, 3):
for j in range(0, 3):
print('{}|'.format(self.current_state[i][j]), end=" ")
print()
print()
Мы говорили о юридических ходах в первых разделах статьи. Чтобы убедиться, что мы соблюдаем правила, нам нужен способ проверить, является ли переезд законным:
# Determines if the made move is a legal move
def is_valid(self, px, py):
if px < 0 or px > 2 or py < 0 or py > 2:
return False
elif self.current_state[px][py] != '.':
return False
else:
return True
Затем нам нужен простой способ проверить, закончилась ли игра. В крестики-нолики игрок может выиграть, соединив три последовательных символа в горизонтальной, диагональной или вертикальной линии:
# Checks if the game has ended and returns the winner in each case
def is_end(self):
# Vertical win
for i in range(0, 3):
if (self.current_state[0][i] != '.' and
self.current_state[0][i] == self.current_state[1][i] and
self.current_state[1][i] == self.current_state[2][i]):
return self.current_state[0][i]
# Horizontal win
for i in range(0, 3):
if (self.current_state[i] == ['X', 'X', 'X']):
return 'X'
elif (self.current_state[i] == ['O', 'O', 'O']):
return 'O'
# Main diagonal win
if (self.current_state[0][0] != '.' and
self.current_state[0][0] == self.current_state[1][1] and
self.current_state[0][0] == self.current_state[2][2]):
return self.current_state[0][0]
# Second diagonal win
if (self.current_state[0][2] != '.' and
self.current_state[0][2] == self.current_state[1][1] and
self.current_state[0][2] == self.current_state[2][0]):
return self.current_state[0][2]
# Is whole board full?
for i in range(0, 3):
for j in range(0, 3):
# There's an empty field, we continue the game
if (self.current_state[i][j] == '.'):
return None
# It's a tie!
return '.'
ИИ, с которым мы играем, стремится к двум вещам – максимизировать свой собственный счет и минимизировать наш. Для этого у нас будет метод max () , который ИИ использует для принятия оптимальных решений.
# Player 'O' is max, in this case AI
def max(self):
# Possible values for maxv are:
# -1 - loss
# 0 - a tie
# 1 - win
# We're initially setting it to -2 as worse than the worst case:
maxv = -2
px = None
py = None
result = self.is_end()
# If the game came to an end, the function needs to return
# the evaluation function of the end. That can be:
# -1 - loss
# 0 - a tie
# 1 - win
if result == 'X':
return (-1, 0, 0)
elif result == 'O':
return (1, 0, 0)
elif result == '.':
return (0, 0, 0)
for i in range(0, 3):
for j in range(0, 3):
if self.current_state[i][j] == '.':
# On the empty field player 'O' makes a move and calls Min
# That's one branch of the game tree.
self.current_state[i][j] = 'O'
(m, min_i, min_j) = self.min()
# Fixing the maxv value if needed
if m > maxv:
maxv = m
px = i
py = j
# Setting back the field to empty
self.current_state[i][j] = '.'
return (maxv, px, py)
Однако мы также включим метод main () , который будет служить нам помощником для минимизации оценки ИИ:
# Player 'X' is min, in this case human
def min(self):
# Possible values for minv are:
# -1 - win
# 0 - a tie
# 1 - loss
# We're initially setting it to 2 as worse than the worst case:
minv = 2
qx = None
qy = None
result = self.is_end()
if result == 'X':
return (-1, 0, 0)
elif result == 'O':
return (1, 0, 0)
elif result == '.':
return (0, 0, 0)
for i in range(0, 3):
for j in range(0, 3):
if self.current_state[i][j] == '.':
self.current_state[i][j] = 'X'
(m, max_i, max_j) = self.max()
if m < minv:
minv = m
qx = i
qy = j
self.current_state[i][j] = '.'
return (minv, qx, qy)
И в конечном счете, давайте сделаем игровой цикл, который позволит нам играть против ИИ:
def play(self):
while True:
self.draw_board()
self.result = self.is_end()
# Printing the appropriate message if the game has ended
if self.result != None:
if self.result == 'X':
print('The winner is X!')
elif self.result == 'O':
print('The winner is O!')
elif self.result == '.':
print("It's a tie!")
self.initialize_game()
return
# If it's player's turn
if self.player_turn == 'X':
while True:
start = time.time()
(m, qx, qy) = self.min()
end = time.time()
print('Evaluation time: {}s'.format(round(end - start, 7)))
print('Recommended move: X = {}, Y = {}'.format(qx, qy))
px = int(input('Insert the X coordinate: '))
py = int(input('Insert the Y coordinate: '))
(qx, qy) = (px, py)
if self.is_valid(px, py):
self.current_state[px][py] = 'X'
self.player_turn = 'O'
break
else:
print('The move is not valid! Try again.')
# If it's AI's turn
else:
(m, px, py) = self.max()
self.current_state[px][py] = 'O'
self.player_turn = 'X'
Давайте начнем игру!
def main():
g = Game()
g.play()
if __name__ == "__main__":
main()
Теперь посмотрим, что происходит, когда мы следуем рекомендуемой последовательности ходов – то есть играем оптимально:
.| .| .| .| .| .| .| .| .| Evaluation time: 5.0726919s Recommended move: X = 0, Y = 0 Insert the X coordinate: 0 Insert the Y coordinate: 0 X| .| .| .| .| .| .| .| .| X| .| .| .| O| .| .| .| .| Evaluation time: 0.06496s Recommended move: X = 0, Y = 1 Insert the X coordinate: 0 Insert the Y coordinate: 1 X| X| .| .| O| .| .| .| .| X| X| O| .| O| .| .| .| .| Evaluation time: 0.0020001s Recommended move: X = 2, Y = 0 Insert the X coordinate: 2 Insert the Y coordinate: 0 X| X| O| .| O| .| X| .| .| X| X| O| O| O| .| X| .| .| Evaluation time: 0.0s Recommended move: X = 1, Y = 2 Insert the X coordinate: 1 Insert the Y coordinate: 2 X| X| O| O| O| X| X| .| .| X| X| O| O| O| X| X| O| .| Evaluation time: 0.0s Recommended move: X = 2, Y = 2 Insert the X coordinate: 2 Insert the Y coordinate: 2 X| X| O| O| O| X| X| O| X| It's a tie!
Как вы уже заметили, победить такого рода ИИ невозможно. Если предположить, что и игрок, и ИИ играют оптимально, то игра всегда будет ничейной. Поскольку ИИ всегда играет оптимально, если мы ошибемся, то проиграем.
Внимательно посмотрите на время оценки, так как мы сравним его со следующей, улучшенной версией алгоритма в следующем примере.
Альфа-Бета-Обрезка
Альфа–бета (𝛼−𝛽) алгоритм был открыт независимо несколькими исследованиями в середине 1900-х годов. Альфа–бета на самом деле является улучшенным минимаксом с использованием эвристики. Он перестает оценивать ход, когда убеждается, что он хуже, чем ранее рассмотренный ход. Такие шаги не нуждаются в дальнейшей оценке.
При добавлении к простому минимаксному алгоритму он дает тот же результат, но отсекает определенные ветви, которые не могут повлиять на окончательное решение – резко повышая производительность.
Основная концепция состоит в том, чтобы поддерживать два значения в течение всего поиска:
- Alpha : Лучший уже изученный вариант для игрока Max
- Beta : Лучший уже изученный вариант для игрока Min
Изначально альфа-это отрицательная бесконечность, а бета-положительная бесконечность, то есть в нашем коде мы будем использовать наихудшие возможные оценки для обоих игроков.
Давайте посмотрим, как будет выглядеть предыдущее дерево, если мы применим метод альфа-бета:
Когда поиск дойдет до первой серой области (8), он проверит текущий лучший (с минимальным значением) уже исследованный вариант вдоль пути для минимизатора, который в данный момент равен 7. Поскольку 8 больше 7, мы можем отрезать все дальнейшие дочерние элементы узла, в котором мы находимся (в данном случае их нет), поскольку, если мы сыграем этот ход, противник сыграет ход со значением 8, что для нас хуже, чем любой возможный ход, который мог бы сделать противник, если бы мы сделали еще один ход.
Лучший пример может быть, когда дело доходит до следующего серого. Обратите внимание на узлы со значением -9. В этот момент лучшим (с максимальным значением) исследованным вариантом вдоль пути для максимизатора является -4. Поскольку -9 меньше, чем -4, мы можем отрезать все остальные дочерние элементы узла, в котором мы находимся.
Этот метод позволяет нам игнорировать многие ветви, которые ведут к значениям, которые не помогут нашему решению и никак на него не повлияют.
Имея это в виду, давайте изменим методы min() и max() из предыдущих:
def max_alpha_beta(self, alpha, beta):
maxv = -2
px = None
py = None
result = self.is_end()
if result == 'X':
return (-1, 0, 0)
elif result == 'O':
return (1, 0, 0)
elif result == '.':
return (0, 0, 0)
for i in range(0, 3):
for j in range(0, 3):
if self.current_state[i][j] == '.':
self.current_state[i][j] = 'O'
(m, min_i, in_j) = self.min_alpha_beta(alpha, beta)
if m > maxv:
maxv = m
px = i
py = j
self.current_state[i][j] = '.'
# Next two ifs in Max and Min are the only difference between regular algorithm and minimax
if maxv >= beta:
return (maxv, px, py)
if maxv > alpha:
alpha = maxv
return (maxv, px, py)
def min_alpha_beta(self, alpha, beta):
minv = 2
qx = None
qy = None
result = self.is_end()
if result == 'X':
return (-1, 0, 0)
elif result == 'O':
return (1, 0, 0)
elif result == '.':
return (0, 0, 0)
for i in range(0, 3):
for j in range(0, 3):
if self.current_state[i][j] == '.':
self.current_state[i][j] = 'X'
(m, max_i, max_j) = self.max_alpha_beta(alpha, beta)
if m < minv:
minv = m
qx = i
qy = j
self.current_state[i][j] = '.'
if minv <= alpha:
return (minv, qx, qy)
if minv < beta:
beta = minv
return (minv, qx, qy)
А теперь игровой цикл:
def play_alpha_beta(self):
while True:
self.draw_board()
self.result = self.is_end()
if self.result != None:
if self.result == 'X':
print('The winner is X!')
elif self.result == 'O':
print('The winner is O!')
elif self.result == '.':
print("It's a tie!")
self.initialize_game()
return
if self.player_turn == 'X':
while True:
start = time.time()
(m, qx, qy) = self.min_alpha_beta(-2, 2)
end = time.time()
print('Evaluation time: {}s'.format(round(end - start, 7)))
print('Recommended move: X = {}, Y = {}'.format(qx, qy))
px = int(input('Insert the X coordinate: '))
py = int(input('Insert the Y coordinate: '))
qx = px
qy = py
if self.is_valid(px, py):
self.current_state[px][py] = 'X'
self.player_turn = 'O'
break
else:
print('The move is not valid! Try again.')
else:
(m, px, py) = self.max_alpha_beta(-2, 2)
self.current_state[px][py] = 'O'
self.player_turn = 'X'
Игра в эту игру такая же, как и раньше, хотя если мы посмотрим на время, необходимое ИИ для поиска оптимальных решений, то увидим большую разницу:
.| .| .| .| .| .| .| .| .| Evaluation time: 0.1688969s Recommended move: X = 0, Y = 0 Evaluation time: 0.0069957s Recommended move: X = 0, Y = 1 Evaluation time: 0.0009975s Recommended move: X = 2, Y = 0 Evaluation time: 0.0s Recommended move: X = 1, Y = 2 Evaluation time: 0.0s Recommended move: X = 2, Y = 2 It's a tie!
После тестирования и запуска программы с нуля в течение нескольких раз результаты для сравнения приведены в таблице ниже:
| Минимакс | Альфа-бета-обрезка | Альфа-бета-обрезка |
| Альфа-бета-обрезка | Альфа-бета-обрезка | Альфа-бета-обрезка |
Вывод
Альфа-бета-обрезка имеет большое значение при оценке больших и сложных игровых деревьев. Несмотря на то, что крестики-нолики-сама по себе простая игра, мы все же можем заметить, что без альфа-бета-эвристики алгоритм занимает значительно больше времени, чтобы рекомендовать ход в первый ход.