Эта статья будет немного отличаться от предыдущих, которые основаны на некоторых новых технологиях для использования в ваших проектах.
Интересно? Я опишу алгоритм Minimax с точки зрения теории игр. Просто сообщаю вам, чего вам следует ожидать:
1. Так что же такое алгоритм Minimax?
2. План и код
3. Описание алгоритма
4. Оптимизация
4.1. Оптимизация глубины
4.2. Оптимизация альфа-бета
5. Совет
6. Заключение
Для кодирования мы будем использовать язык Objective-C.Не волнуйтесь, это будет больше теории, чем просто код.
Направление задано, поехали.
Так что же такое алгоритм Minimax? Minimax - это правило принятия решений, используемое в теории принятия решений, теории игр, статистике и философии для минимизации возможных потерь для наихудшего (максимального) сценария. Первоначально сформулированная для теории игр двух игроков с нулевой суммой, охватывающая как случаи, когда игроки делают поочередные ходы, так и те, когда они делают одновременные ходы, она также была распространена на более сложные игры и на принятие общих решений в присутствии неопределенности.
Coooooooooool!
Теперь, когда у нас есть определение, какая логика в нем заложена? Предположим, вы играете в игру против своего друга. И затем на каждом шагу, который вы делаете, вы хотите максимизировать свой выигрыш, а ваш друг также хочет минимизировать свои проигрыши. В конце концов, это одно и то же определение для вас обоих. Следующим вашим решением должно быть максимальное увеличение вашей текущей выигрышной позиции, зная, что ваш друг на следующем шаге минимизирует свою проигрышную позицию, и зная, что на следующем шаге вы также максимизируете свою выигрышную позицию ...
Уловили этот запах рекурсии? Таким образом, основная идея этого алгоритма - принять лучшее решение, зная, что ваш оппонент сделает то же самое.
План и код
Мы построим этот алгоритм, используя представление в виде дерева. С каждым новым поколением детей возможен следующий шаг другого игрока. Например, первое поколение - это ваши возможные шаги, каждый шаг приведет к некоторому списку возможных шагов оппонента. В этой ситуации ваш шаг - это «родительская вершина», а возможные следующие шаги вашего оппонента - это «дочерние вершины».
Вот окончательный код алгоритма со всеми оптимизациями.
#pragma mark - Public
- (NSUInteger)startAlgorithmWithAITurn:(BOOL)aiTurn; {
return [self alphabetaAlgorithm:_searchingDeapth alpha:NSIntegerMin beta:NSIntegerMax maximizing:aiTurn];
}
#pragma mark - Private
- (NSInteger)alphabetaAlgorithm:(NSInteger)depth alpha:(NSInteger)alpha beta:(NSInteger)beta maximizing:(BOOL)maximizing {
self.currentCheckingDepth = _searchingDeapth - depth;
if (self.datasource == nil || self.delegate == nil) {
return 0;
}
if (depth == 0 || [self.datasource checkStopConditionForAlgorithm:self onAITurn:maximizing]) {
return [self.datasource evaluateForAlgorithm:self onAITurn:maximizing];
}
NSArray *nextStates = [self.datasource possibleNextStatesForAlgorithm:self onAITurn:maximizing];
for (id state in nextStates) {
[self.delegate performActionForAlgorithm:self andState:state onAITurn:maximizing];
if (maximizing) {
alpha = MAX(alpha, [self alphabetaAlgorithm:depth - 1 alpha:alpha beta:beta maximizing:NO]);
} else {
beta = MIN(beta, [self alphabetaAlgorithm:depth - 1 alpha:alpha beta:beta maximizing:YES]);
}
[self.delegate undoActionForAlgorithm:self andState:state onAITurn:maximizing];
if (beta <= alpha) {
break;
}
}
return (maximizing ? alpha : beta);
}
Описание алгоритма
Давайте закроем глаза на оптимизацию и начнем с того, что нам нужно. Прежде всего, нам нужен алгоритм, который будет выдавать список возможных следующих шагов на основе сделанного шага. Мы используем это для создания других дочерних вершин, как описано ранее.
Во-вторых, нам нужен алгоритм, который будет вычислять оценку результата игры в конце игры. Каждой вершине (сделанному шагу) будет присвоено значение с оцененным результатом с использованием этого алгоритма. Как он будет назначен, будет рассказано позже.
Итак, как это работает с использованием дерева и этих алгоритмов? Логически алгоритм делится на две части:
1. Наш ход
2. Ход противников.
На «нашей очереди» в качестве следующей вершины мы выбираем одного из наших дочерних элементов, у которого есть лучшая оценка. Затем, поскольку следующий выбранный шаг генерирует возможные шаги оппонента с его оценкой, он выберет худшее значение оценки (худшее для нас означает лучшее для него).
Это просто означает, что мы сделаем максимально оцененный шаг из возможных шагов оппонента, а противник сделает минимальный оцененный шаг из наших возможных следующих шагов.
Следующий вопрос - когда мы будем оценивать шаг? Первое, что приходит в голову - когда он создан. Но подождите минутку, как мы можем рассчитать это сразу, если это зависит от следующего поколения или, другими словами, от шага другого игрока? Это означает, что наше значение шага будет максимальным из значения шага следующего поколения, которое является шагом оппонента. С другой стороны, значение шага оппонента будет минимальным из значений шага следующего поколения, которое принадлежит мне.
Следуя этому правилу, мы можем сказать, что оценка будет производиться по окончании игры, так как это последнее поколение ступеней. После этого он будет раскручиваться в обратном направлении, отмечая все вершины с ранее описанным вычисленным значением, пока не дойдет до корня.
Рекурсивная генерация заканчивается, если:
Мы выигрываем
Невозможно сделать следующий ход, мы получаем ничью
Оценка состояния игры может быть рассчитана следующим образом:
Если мы выиграем, то оцененное значение должно быть больше некоторого положительного значения
Если проиграем, то оно должно быть меньше некоторого отрицательного значения
Если у нас есть ничья, то она должна быть между этими значениями.
Это означает, что чем лучше у нас позиция, тем больше она должна быть.
Эта оценка может зависеть от разных вещей. Возьмем, к примеру, что для оценки мы даем ситуацию, когда мы победители.
Затем он может оцениваться в зависимости от следующих значений:
1. Сколько шагов я сделал, чтобы получить победу
2. Насколько близок был ваш противник к победе
и т. д.
Эта функция - одна из самых важных частей алгоритма. Чем лучше он организован, тем лучше результаты. Функция, зависящая только от одной характеристики, не будет такой точной, как функция, зависящая от десяти. Кроме того, характеристики, которые вы выбираете для оценки, должны иметь логическое значение. Если вы считаете, что значение оценки больше, потому что игрок - женщина, а не мужчина, это имеет смысл для сексистов, но не для алгоритма. В результате вы получите неверные результаты. И все потому, что вы сексист.
Отлично !, теперь мы в целом разбираемся в алгоритме и в том, какая идея в нем заложена. Звучит круто, но все же не так хорошо, когда дело касается времени выполнения. Почему?
Оптимизация
Для использования, например, выберем игру «четыре в ряд». Если вы не знаете, что это такое, вот краткое описание:
«Цель игры - соединить четыре ваших жетона в линию. Разрешены все направления (вертикальное, горизонтальное, диагональное). Игроки по очереди кладут один из своих жетонов в один из семи слотов. Жетон падает как можно глубже в слот. Игрок с красными жетонами начинает. Игра заканчивается немедленно, когда первый игрок соединяет четыре камня ».
Давайте подумаем, как в этом случае будет работать наш алгоритм. Поле имеет 7 * 6 = 42 шага. Вначале каждый пользователь может сделать 7 разных шагов. Что нам дают эти данные? Эти ценности самые ужасные. Чтобы сделать их более реалистичными, скажем, например, игра завершается за 30 шагов, и в среднем у пользователя будет возможность выбрать 5 строк. Используя наш алгоритм, мы получим следующие приблизительные данные. Первый пользователь может произвести 5 шагов; на каждом шаге будет 5 собственных шагов. Теперь у нас 5 + 25. Эти 25 шагов, каждый может дать 5 новых шагов, что равно 125. Это означает, что на третьем шаге вычислений у нас будет около 155 шагов. С каждым следующим шагом будет появляться все больше и больше возможных шагов, которым нужно следовать. Вы можете подсчитать их, используя следующую функцию:
5¹ + 5² + 5³ +… + 5³⁰. Это огромное значение, и компьютеру потребуется много времени, чтобы рассчитать такое количество шагов.
К счастью, есть готовые оптимизации для алгоритма Minimax, которые снизят это значение. Мы скоро поговорим о них двоих.
Оптимизация глубины
Однажды один очень мудрый человек сказал: «Зачем нам считать до конца? Можем ли мы принять решение где-то посередине? ». Да мы можем. Конечно, в конечном итоге точность будет намного лучше, чем где-то посередине, но с хорошим алгоритмом оценки мы можем уменьшить эту проблему. Итак, что нам делать, просто добавить еще одно правило для остановок алгоритма. Это правило - останавливаться, если текущая глубина шага находится на критическом значении. Это значение вы можете выбрать самостоятельно после некоторого тестирования. Я думаю, что с помощью кучи тестов вы найдете те, которые подходят для вашей особой ситуации. Когда мы начинаем оценивать по этому правилу, мы рассматриваем это как ничью.
Это правило было не таким сложным, и оно действительно может оптимизировать наши алгоритмы. Тем не менее, это снижает нашу точность, и, чтобы заставить его работать, мы просто не можем использовать сверхнизкую глубину, иначе это даст нам неправильные и неточные значения. Скажу дальше, мы выбрали, что глубина 8 нам подходит. Хотя на то, чтобы получить окончательный результат, требовалось много времени. Следующая оптимизация не влияет на точность и действительно сокращает время алгоритма. Его имя - Alpha Beta, и это то, что ломает мне голову.
Оптимизация альфа-бета
Смысл прост. Идея следующая - не нужно считать следующие ветки, если мы знаем, что уже созданная ветка будет иметь лучший результат. Это просто пустая трата ресурсов. Идея простая, а как насчет реализации?
Чтобы посчитать это, нам нужно передать рекурсивному алгоритму две другие переменные.
1. Альфа - представляет оценочное значение в увеличивающейся части.
2. Бета - представляет оценочное значение в минимальной части.
Из предыдущих частей мы поняли, что нужно пройти до конца нашего дерева и только после этого мы сможем оценить наши результаты. Таким образом, первая оценка будет производиться на последней вершине, если мы всегда будем выбирать левую вершину. После этого процесс оценки начнется для ее непосредственной вершины и будет продолжаться для всех левых вершин, пока не закончится одна из возможных, и так далее и так далее.
Зачем я тебе это говорю? Все потому, что мы понимаем, насколько важна оценка вершин для этой оптимизации.
Чтобы нам было легче представить, давайте предположим, что мы находимся на максимальном повороте. Для нас это означает, что мы считаем значение Alpha. Это значение считается максимальным из всех оценочных значений его потомков. В то же время, когда мы считаем Alpha (мы находимся в процессе максимизации), у нас есть значение Beta. Здесь он представляет текущее бета-значение его родителя. Отлично !, теперь мы знаем, что означают альфа и бета в определенное время. Во избежание недоразумений, альфа - это наше текущее оценочное значение, а бета - текущее дальнейшее оценочное значение.
Последнее, что нужно сделать - это проверка оптимизации. Если бета меньше или равна альфа, мы прекращаем оценку для всех следующих детей.
Последнее, что нужно сделать - это проверка оптимизации. Если бета ниже или равна альфа, мы прекращаем оценку для всех следующих потомков.
Почему это работает? Поскольку Beta уже меньше, чем Alpha - значение его потомка, в то же время Alpha считается как максимум возможных значений потомка. Это означает, что теперь оценочное значение для нашего шага не может быть ниже текущего значения. С другой точки зрения, бета-версия, которая у нас сейчас есть, является текущим оценочным значением нашего родителя. Из идеи, которую в настоящее время мы максимизируем, мы можем понять, что наш Родитель минимизирует, что означает, что он выберет минимум из своего текущего значения и расчетного значения его потомков.
Собирая все это вместе - поскольку мы знаем, что наше вычисленное значение выше родительского значения, мы принимаем решение, что он не будет выбирать нас в качестве следующего возможного шага (у него есть лучшее потомство, и это дает ему более низкое значение, если оно выбирает их). С этой точки зрения делать следующие вычисления нелепо, потому что они не изменят конечный результат. Итак, мы, как родитель-потомок, останавливаем все вычисления и возвращаем текущее значение. Используя это, наш родитель будет сравнивать нас и лучший на данный момент вариант. По ранее описанной логике он выберет свое текущее значение.
Используя эту оптимизацию, мы можем вырезать огромные ветви и сэкономить много работы, которая ничего не повлияет на конечный результат.
Совет
Отлично !, теперь, когда мы знаем две оптимизации, которые заставят наш алгоритм работать быстрее, я хотел бы дать вам один совет. Обычно, когда машина делает выбор, реальному пользователю нужно время, чтобы решить, что делать дальше. Мы можем использовать это время, чтобы подготовиться к следующему решению.
Итак, когда мы сделаем свой выбор, давайте продолжим работать над всеми возможными вариантами выбора пользователя. Что это нам дает?
1. Многие из них уже рассчитаны на основе предыдущей пользовательской итерации.
2. К тому времени, когда пользователь сделает свой выбор, мы продвинемся далеко вперед в наших расчетах. Это увеличит глубину нашего дерева, другими словами - точность.
В конце концов, когда пользователь делает выбор, мы можем просто отрезать все остальные ветви, которые не были выбраны, и продолжить только с выбранной.
Это здорово, но давайте сделаем общий вывод о том, что, как я полагаю, - не запускайте алгоритм каждый раз, когда наступает ваша очередь. Заставьте его запускаться один раз во время игры, и когда пользователь выберет какой-то шаг, получите для него расчетные данные и продолжите наши вычисления до конца.
Кто-то скажет, что у него тяжелая проблема с памятью. Да, это так, но это всего лишь совет, вы можете объединить два решения, чтобы найти то, что лучше всего подходит для вашего времени, памяти и точности для вашей конкретной ситуации.
Кроме того, я бы рекомендовал выполнять вычисления для каждого возможного шага в новом потоке, но это совсем другая история.
Заключение
Где использовать эту информацию? Везде, где вам нужно принять или сделать решение, основанное на действиях пользователя. Чаще всего это могут быть игры, но затем вы можете использовать свою фантазию, чтобы интегрировать ее в место, где вам придется размышлять над любым выполненным действием. Единственное, что вам нужно понять, это алгоритм двух частей, которые «играют» друг против друга.
Конец!
