АНАЛИЗ АЛГОРИТМОВ «MINIMAX» И «ALPHA BETA»

АННОТАЦИЯ

В данной статье проанализирована работа двух широко известных алгоритмов «Minimax» и «Alpha Beta» в контексте разработки приложения для игры «крестики-нолики». Приводится пример реализации на языке программирования C#, позволяющий пользователю играть против компьютерного оппонента, принимающего оптимальные решения с использованием этих алгоритмов.

Ключевые слова: алгоритм; minimax; alpha beta отсечение; искусственный интеллект.

Алгоритм «Minimax» ‑ это рекурсивный алгоритм, широко применяемый в теории игр и искусственном интеллекте. Используется для определения оптимального хода при различных входных данных в игре с нулевой суммой, то есть победа одного игрока равноценна проигрышу другого [1].

Рассмотрим подробнее работу данного алгоритма. Введём определение победных случаев для игрока, играющего крестиками. Игровое поле будет составлять 3х3 клетки, а для победы игроку необходимо собрать линию, состоящую только из его символов, расположенную непрерывно по горизонтали, вертикали или диагонали. В основе идеи алгоритма «Minimax» присутствуют две сущности: максимизирующий игрок и минимизирующий игрок. Максимизирующий игрок всегда стремится принимать только те решения, которые ему принесут победу, либо большее количество очков. Минимизирующий игрок, напротив, выбирает только те ходы, которые будут не выгодны для максимизирующего игрока.

Пусть игрок «Х» будет максимизирующим, а игрок «О» – минимизирующим. Рассмотрим ситуацию, представленную на рисунке 1, демонстрирующую все возможные исходы в зависимости от хода игрока.

Рисунок 1. Дерево возможных исходов игры

Корнем дерева является текущее состояние игрового поля, а следующий ход должен сделать игрок «Х». Игроку доступны только три позиции, но необходимо выбрать лучшую. Рассмотрим все возможные события, начиная с листьев дерева. В ситуации под номером 9 игрок «X» успешно выигрывает, поэтому вернём в ситуацию 6 оценку +1. Перейдём к ситуации 5, в которой ходит игрок «O» и успешно выигрывает, следовательно, вернётся оценка -1. Данный игрок будет стараться ходить таким образом, чтобы помешать игроку «X» победить, поэтому игрок «O» должен выбрать меньшую оценку среди всех полученных из ситуаций 5 и 9, то есть в ситуацию 3 вернётся оценка -1. В ситуацию 4 попадёт оценка -1, так как ситуации 7, 8, 10 аналогичны. Ситуация 2 вернёт +1, так как игрок «X» выигрывает. Поскольку мы достигли корня дерева игроку «X» необходимо проанализировать полученные данные для лучшего хода. Игрок «Х» является максимизирующим, следовательно, ему необходимо выбрать наибольшую оценку из возможных ситуаций. Среди оценок +1, -1, -1 игрок выберет оценку +1, полученную из ситуации 2 и совершит ход.

Теперь, когда теоретическая часть алгоритма понятна, необходимо использовать его на практике. При реализации приложения был использован язык программирования C# и фреймворк Windows Presentation Foundation (WPF).

На рисунке 2 представлены дополнительные функции, необходимые для реализации алгоритма «Minimax».

Рисунок 2. Дополнительные функции

Основная функция «MinimaxAlgo» представлена на рисунке 3. В функции происходит рекурсивное интегрирование по всем ходам. Таким образом, можно оценить все возможные исходы хода, а также выбрать среди них лучший.

Рисунок 3. Реализация функции «Minimax»

Рисунок 4. Тестирование приложения

Функция возвращает объект класса «ResultAlgo», который хранит оценку и позицию клетки в поле.

Заключительным этапом реализуем графический интерфейс для общения с человеком и протестируем работоспособность программы. Результат представлен на рисунке 4.

Алгоритм «Minimax» имеет ряд недостатков, одним из которых является обработка неэффективных ходов. Из-за этого для вычисления всевозможных ходов с игровым полем 5x5 тратится большое количество времени.

Решить данную проблему можно несколькими способами: ввести глубину поиска, использовать алгоритм «Alpha beta». Первый подразумевает использование некоторой переменной, показывающей как глубоко рекурсивно мы сможем исследовать все возможные развития игры [2]. Использование данного подхода уменьшает время на вычисление следующего хода, но не гарантирует, что выбранный ход был лучшим. Используя алгоритм «Alpha beta», мы можем пропускать некоторые проверки ветвей дерева игры, ускоряя поиск лучшего хода [3]. Происходит это путём добавления двух переменных. Первая переменная «alpha» представляет текущую оценку для максимизирующего игрока, по умолчанию должна иметь отрицательную бесконечность. Переменная «beta» представляет оценку для минимизирующего игрока, по умолчанию устанавливается значение положительная бесконечность.

Рисунок 5. Оптимизация алгоритма

При рекурсивном прохождении по дереву игры, значения переменных «alpha» и «beta» будут меняться и, если значение переменной «alpha» будет больше либо равно значению переменной «beta», дальнейшее рассмотрение этой ветви не целесообразно.

Применение алгоритма «Alpha beta» для оптимизации поиска лучшего хода представлено на рисунке 5.

После внесённых изменений в программу необходимо провести несколько измерений, чтобы быть уверенным в их целесообразности. Тестирование времени вычисления оптимального хода двух алгоритмов приведено в таблице 1.

Таблица 1.

Тестирование «Minimax» и «Alpha beta»

Полученные результаты демонстрируют, что применение алгоритма «Alpha beta» для игрового поля 4х4 сокращает время вычисления оптимального хода в несколько раз. В случае, когда количество свободных ячеек может достигать 18 и более, использование алгоритма «Alpha beta» необходимо.

Список литературы:

1. «The Minimax Algorithm». [электронный ресурс] – URL: https://medium.com/@aidenrtracy/the-minimax-algorithm-f6e8e0a1eadb (дата обращения 05.07.2023).
2. Джордж Хейнеман, Гэри Поллис, Стэнли Селков. Алгоритмы справочник с примерами на С, С++, Java и Python. М.: Диалектика, 2017. – С. 211-231.
3. «Alpha Beta Pruning in AI». [электронный ресурс] – URL: https://www.mygreatlearning.com/blog/alpha-beta-pruning-in-ai/ (дата обращения 05.07.2023).