1. Обзор
В этой статье мы обсудим алгоритм Минимакс и его применение в ИИ. Поскольку это алгоритм теории игр, мы реализуем простую игру, используя его.
Мы также обсудим преимущества использования алгоритма и посмотрим, как его можно улучшить.
2. Введение
Минимакс — это алгоритм принятия решений, обычно используемый в пошаговых играх для двух игроков . Цель алгоритма — найти оптимальный следующий ход.
В алгоритме один игрок называется максимизатором, а другой игрок — минимизатором. Если мы присвоим игровому полю оценочный балл, то один игрок попытается выбрать состояние игры с максимальным количеством очков, а другой — состояние с минимальным счетом.
Другими словами, максимизатор работает, чтобы получить наибольшее количество очков, в то время как минимизатор пытается получить наименьшее количество очков, пытаясь противодействовать ходам .
Он основан на концепции игры с нулевой суммой . В игре с нулевой суммой общая оценка полезности делится между игроками. Увеличение счета одного игрока приводит к уменьшению счета другого игрока. Таким образом, общий балл всегда равен нулю. Чтобы один игрок выиграл, другой должен проиграть. Примерами таких игр являются шахматы, покер, шашки, крестики-нолики.
Интересный факт – в 1997 году шахматный компьютер Deep Blue от IBM (созданный на базе Minimax) победил Гарри Каспарова (чемпиона мира по шахматам).
3. Минимаксный алгоритм
Наша цель — найти лучший ход для игрока. Для этого мы можем просто выбрать узел с наилучшей оценочной оценкой. Чтобы сделать процесс более умным, мы также можем смотреть вперед и оценивать ходы потенциального противника.
Для каждого хода мы можем заглянуть вперед на столько ходов, сколько позволяют наши вычислительные мощности. Алгоритм предполагает, что противник играет оптимально.
Технически мы начинаем с корневого узла и выбираем наилучший возможный узел. Мы оцениваем узлы на основе их оценочных баллов. В нашем случае функция оценки может присваивать баллы только узлам результата (листьям). Таким образом, мы рекурсивно достигаем листьев с оценками и распространяем оценки обратно.
Рассмотрим приведенное ниже игровое дерево:
Максимайзер начинает с корневого узла и выбирает ход с максимальным счетом. К сожалению, только листья имеют оценки с ними, и, следовательно, алгоритм должен рекурсивно достигать листовых узлов. В данном игровом дереве в настоящее время очередь минимизатора выбирать ход из листовых узлов , поэтому будут выбраны узлы с минимальными очками (здесь узлы 3 и 4). Таким же образом он продолжает выбирать лучшие узлы, пока не достигнет корневого узла.
Теперь формально определим шаги алгоритма:
- Построить полное игровое дерево
- Оцените баллы для листьев, используя функцию оценки
- Резервное копирование очков от листьев к корню с учетом типа игрока:
- Для максимального игрока выберите ребенка с максимальным количеством очков.
- Для минимального игрока выберите ребенка с минимальным счетом
- В корневом узле выберите узел с максимальным значением и выполните соответствующий ход.
4. Реализация
Теперь давайте реализуем игру.
В игре у нас есть куча с n количеством костей . Оба игрока должны поднять 1, 2 или 3 кости в свой ход. Игрок, который не может взять кости, проигрывает. Каждый игрок играет оптимально. Учитывая значение n , давайте напишем ИИ.
Чтобы определить правила игры, мы реализуем класс GameOfBones :
class GameOfBones {
static List<Integer> getPossibleStates(int noOfBonesInHeap) {
return IntStream.rangeClosed(1, 3).boxed()
.map(i -> noOfBonesInHeap - i)
.filter(newHeapCount -> newHeapCount >= 0)
.collect(Collectors.toList());
}
}
Кроме того, нам также нужна реализация для классов Node и Tree :
public class Node {
int noOfBones;
boolean isMaxPlayer;
int score;
List<Node> children;
// setters and getters
}
public class Tree {
Node root;
// setters and getters
}
Теперь реализуем алгоритм. Требуется игровое дерево, чтобы заглянуть вперед и найти лучший ход. Давайте реализуем это:
public class MiniMax {
Tree tree;
public void constructTree(int noOfBones) {
tree = new Tree();
Node root = new Node(noOfBones, true);
tree.setRoot(root);
constructTree(root);
}
private void constructTree(Node parentNode) {
List<Integer> listofPossibleHeaps
= GameOfBones.getPossibleStates(parentNode.getNoOfBones());
boolean isChildMaxPlayer = !parentNode.isMaxPlayer();
listofPossibleHeaps.forEach(n -> {
Node newNode = new Node(n, isChildMaxPlayer);
parentNode.addChild(newNode);
if (newNode.getNoOfBones() > 0) {
constructTree(newNode);
}
});
}
}
Теперь мы реализуем метод checkWin , который будет имитировать розыгрыш, выбирая оптимальные ходы для обоих игроков. Он устанавливает оценку:
- +1, если выигрывает максимизатор
- -1, если минимизатор выигрывает
CheckWin вернет true, если выиграет первый игрок (в нашем случае — максимизатор) :
public boolean checkWin() {
Node root = tree.getRoot();
checkWin(root);
return root.getScore() == 1;
}
private void checkWin(Node node) {
List<Node> children = node.getChildren();
boolean isMaxPlayer = node.isMaxPlayer();
children.forEach(child -> {
if (child.getNoOfBones() == 0) {
child.setScore(isMaxPlayer ? 1 : -1);
} else {
checkWin(child);
}
});
Node bestChild = findBestChild(isMaxPlayer, children);
node.setScore(bestChild.getScore());
}
Здесь метод findBestChild находит узел с максимальным количеством очков, если игрок является максимизатором. В противном случае он возвращает дочерний элемент с минимальным баллом:
private Node findBestChild(boolean isMaxPlayer, List<Node> children) {
Comparator<Node> byScoreComparator = Comparator.comparing(Node::getScore);
return children.stream()
.max(isMaxPlayer ? byScoreComparator : byScoreComparator.reversed())
.orElseThrow(NoSuchElementException::new);
}
Наконец, давайте реализуем тестовый пример с некоторыми значениями n (количество костей в куче):
@Test
public void givenMiniMax_whenCheckWin_thenComputeOptimal() {
miniMax.constructTree(6);
boolean result = miniMax.checkWin();
assertTrue(result);
miniMax.constructTree(8);
result = miniMax.checkWin();
assertFalse(result);
}
5. Улучшение
Для большинства задач невозможно построить все игровое дерево. На практике мы можем разработать частичное дерево (построить дерево только до заранее определенного количества уровней) .
Затем нам нужно будет реализовать функцию оценки, которая должна решить, насколько хорошее текущее состояние для игрока.
Даже если мы не строим полные игровые деревья, вычисление ходов для игр с высоким коэффициентом ветвления может занять много времени.
К счастью, есть возможность найти оптимальный ход, не исследуя каждый узел дерева игры. Мы можем пропустить некоторые ветки, следуя некоторым правилам, и это не повлияет на конечный результат. Этот процесс называется обрезкой . Альфа-бета-обрезка является распространенным вариантом минимаксного алгоритма.
6. Заключение
Алгоритм минимакс — один из самых популярных алгоритмов для компьютерных настольных игр. Широко применяется в пошаговых играх. Это может быть хорошим выбором, когда у игроков есть полная информация об игре.
Это может быть не лучший выбор для игр с исключительно высоким коэффициентом ветвления (например, игра GO). Тем не менее, при правильной реализации это может быть довольно умный ИИ.
Как всегда, полный код алгоритма можно найти на GitHub .