Настольная игра Искусственный интеллект: алгоритм минимакса: 8 шагов

2024 Автор: John Day | [email protected]. Последнее изменение: 2024-01-30 11:51

Вы когда-нибудь задумывались, как сделаны компьютеры, с которыми вы играете в шахматы или шашки? Не ищите ничего, кроме этого руководства, поскольку оно покажет вам, как создать простой, но эффективный искусственный интеллект (ИИ) с использованием алгоритма Minimax! Используя алгоритм Minimax, ИИ делает хорошо спланированные и продуманные действия (или, по крайней мере, имитирует мыслительный процесс). Я мог бы просто дать вам код для искусственного интеллекта, который я создал, но это было бы неинтересно. Я объясню логику выбора компьютера.

В этом руководстве я расскажу вам, как создать ИИ для Отелло (AKA Reversi) на Python. Вы должны иметь промежуточное представление о том, как писать код на Python, прежде чем взяться за этот проект. Вот несколько хороших веб-сайтов, на которые стоит обратить внимание, чтобы подготовить вас к этому руководству: w3schools или learnpython. В конце этой инструкции у вас должен быть ИИ, который будет делать просчитанные ходы и сможет победить большинство людей.

Поскольку этот Instructable будет в первую очередь иметь дело с тем, как создать ИИ, я не буду объяснять, как создавать игру на Python. Вместо этого я дам код игры, в которой человек может играть против другого человека, и модифицирую его, чтобы вы могли играть в игру, в которой человек играет против ИИ.

Я научился создавать этот ИИ на летней программе в Columbia SHAPE. Я хорошо провел там время, так что загляните на их веб-сайт, чтобы узнать, будет ли вам интересно.

Теперь, когда мы разобрались с логистикой, приступим к программированию!

(Я поместил пару примечаний к изображениям, поэтому обязательно посмотрите на них)

Запасы

Это легко:

1) Компьютер со средой Python, такой как Spyder или IDLE.

2) Загрузите файлы для игры Othello с моего GitHub

3) Ваш мозг с терпением установлен

Шаг 1. Загрузите необходимые файлы

Когда вы заходите в мой GitHub, вы должны увидеть 5 файлов. Загрузите все 5 и поместите их все в одну папку. Перед запуском игры откройте все файлы в среде spyder.

Вот что делают файлы:

1) othello_gui.py этот файл создает игровую доску, на которой игроки могут играть (будь то человек или компьютер)

2) othello_game.py этот файл играет два компьютера друг против друга без игрового поля и показывает только счет и позиции перемещения

3) ai_template.py, здесь вы будете размещать весь свой код для создания своего ИИ.

4) randy_ai.py - это готовый ИИ, который выбирает свои ходы случайным образом

5) othello_shared.py - набор готовых функций, которые вы можете использовать для создания своего ИИ, например, для проверки доступных ходов, счета или состояния доски.

6) Три других файла: Puma.py, erika_5.py и nathan.py, созданные мной, Эрикой и Натаном соответственно из программы SHAPE, это три разных ИИ с уникальными кодами.

Шаг 2: Как открыть Python Othello и поиграть в него

Когда все файлы открыты, в правом нижнем углу экрана введите «run othello_gui.py» и нажмите Enter в консоли IPython. Или в терминале Mac введите «python othello_gui.py» (конечно, после того, как вы окажетесь в нужной папке). Затем на вашем экране должна появиться доска. Это режим человека против человека. Свет идет вторым, а темный - первым. Посмотрите мое видео, если вы запутались. iВверху отображается оценка каждой цветной плитки. Чтобы играть, щелкните допустимое пространство для перемещения, чтобы поместить туда плитку, а затем отдайте компьютер своему противнику, который сделает то же самое и повторит.

Если вы не знаете, как играть в Отелло, прочтите эти правила на сайте Ultra Board:

Черные всегда ходят первыми. Ход делается путем помещения диска цвета игрока на доску в положение, которое «выходит за пределы» одного или нескольких дисков соперника. Диск или ряд дисков находится в обходе, когда он окружен на концах дисками противоположного цвета. Диск может заходить за любое количество дисков в одном или нескольких рядах в любом направлении (горизонтальном, вертикальном, диагональном)…. (дочитайте на их сайте)

Разница между исходной игрой и этой игрой на питоне заключается в том, что когда не остается действительных ходов для одного игрока, игра заканчивается

Теперь, когда вы можете играть в игру с другом, давайте создадим ИИ, с которым вы сможете играть.

Шаг 3. Минимаксный алгоритм: создание сценариев

Прежде чем говорить о том, как написать это в коде, давайте рассмотрим логику, лежащую в основе этого. Минимаксный алгоритм представляет собой алгоритм принятия решений с обратным отслеживанием и обычно используется в пошаговых играх для двух игроков. Цель этого ИИ - найти следующий лучший ход и следующие лучшие ходы, пока он не выиграет игру.

Теперь, как алгоритм определит, какой ход является лучшим? Остановитесь и подумайте, как бы вы выбрали следующий ход. Большинство людей выберут ход, который принесет им наибольшее количество очков, верно? Или, если бы они думали о будущем, они бы выбрали ход, который создал бы ситуацию, в которой они могли бы набрать еще больше очков. Последний способ мышления - это способ мышления минимаксного алгоритма. Он смотрит вперед на все будущие настройки доски и делает ход, который принесет наибольшее количество очков.

Я назвал это алгоритмом отслеживания с возвратом, потому что он начинается с создания и оценки всех будущих состояний платы с соответствующими значениями. Это означает, что алгоритм будет играть в игру столько, сколько ему нужно (делая ходы за себя и оппонента), пока не будут разыграны все сценарии игры. Чтобы отслеживать все состояния доски (сценарии), мы можем нарисовать дерево (смотрите на рисунках). Дерево на картинке выше - простой пример игры Connect 4. Каждая конфигурация доски называется состоянием доски, а ее место в дереве называется узлом. Все узлы внизу дерева - это окончательные состояния доски после выполнения всех ходов. Очевидно, что некоторые состояния доски лучше для одного игрока, чем для другого. Итак, теперь мы должны заставить ИИ выбрать, в какое состояние платы он хочет попасть.

Шаг 4: Minimax: оценка конфигураций платы

Чтобы дать значения состояниям на доске, мы должны изучить стратегии игры, в которую мы играем: в данном случае стратегии Отелло. Поскольку эта игра представляет собой битву за переворачивание дисков соперника и ваших дисков, лучшими положениями дисков являются те, которые стабильны и не могут быть перевернуты. Например, угол - это место, куда ставится диск, его нельзя изменить на другой цвет. Таким образом, это место было бы чрезвычайно ценным. Другие хорошие позиции включают стороны доски, которые позволят вам взять много камней. На этом сайте есть больше стратегий.

Теперь мы можем присвоить значения позициям для каждой платы состояния платы. Когда позиция занята фигурой ИИ, вы даете определенное количество очков в зависимости от позиции. Например, состояние доски, в котором фигура ИИ находится в углу, вы можете дать бонус в 50 очков, но если она была в неблагоприятном месте, фигура может иметь значение 0. После учета всех значений позиции, вы присваиваете статусу платы значение. Например, если у ИИ есть фигура в углу, состояние доски может иметь оценку 50, в то время как другое состояние доски с фигурой ИИ посередине имеет оценку 10.

Есть много способов сделать это, и у меня есть три различных эвристики для оценки элементов доски. Я рекомендую вам создать свой собственный тип эвристики. Я загрузил на свой github три разных ИИ от трех разных производителей с тремя разными эвристиками: Puma.py, erika5.py, nathanh.py.

Шаг 5: минимаксный алгоритм: выбор лучшего хода

Теперь было бы хорошо, если бы ИИ мог просто выбирать все ходы, чтобы перейти в состояние доски с наибольшим количеством очков. Но помните, что ИИ также выбирал ходы для противника, когда он генерировал все состояния доски, и если противник умен, он не позволит ИИ набрать наивысшее количество очков. Вместо этого умный противник сделает ход, чтобы заставить ИИ перейти в самое низкое состояние доски. В алгоритме мы называем двух игроков максимизирующим игроком и минимизирующим игроком. ИИ будет максимальным игроком, так как он хочет получить как можно больше очков для себя. Противник будет минимизирующим игроком, поскольку противник пытается сделать ход, при котором ИИ получает наименьшее количество очков.

После того, как все состояния платы сгенерированы и им присвоены значения, алгоритм начинает сравнивать состояния платы. На рисунках я создал дерево, чтобы показать, как алгоритм будет выбирать свои ходы. Каждое разделение на ветви - это отдельный ход, который может сделать ИИ или противник. Слева от строк узлов я написал, собирается ли игрок максимизировать или минимизировать. Нижняя строка - это все состояния платы с их значениями. Внутри каждого из этих узлов есть число, и это баллы, которые мы присваиваем каждой из плат: чем они выше, тем лучше для ИИ.

Определения: родительский узел - узел, который образует или создает узлы под ним; происхождение дочерних узлов - узлы, которые происходят от одного и того же родительского узла

Пустые узлы показывают, какое движение ИИ сделает, чтобы перейти в наилучшее состояние доски. Он начинается со сравнения дочерних элементов самого левого узла: 10, -3, 5. Поскольку максимизирующий игрок сделает ход, он выберет ход, который принесет ему наибольшее количество очков: 10. Затем мы выбираем и сохраняем это переместите счет доски и запишите его в родительский узел. Теперь, когда 10 находится в родительском узле, наступает очередь минимизирующих игроков. Однако узел, с которым мы сравниваем 10, пуст, поэтому мы должны сначала оценить этот узел, прежде чем минимизирующий игрок сможет сделать выбор. Итак, мы возвращаемся к ходу максимизирующего игрока и сравниваем потомков соседнего узла: 8, -2. Максимизация выберет 8, и мы запишем это в пустой родительский узел. Теперь, когда алгоритм завершил заполнение пустых пространств для дочерних элементов узла над ним, минимизирующий игрок может сравнить эти дочерние элементы - 10 и 8 и выбрать 8. Затем алгоритм повторяет этот процесс до тех пор, пока не будет заполнено все дерево. В конце этого примера у нас есть счет 8. Это наивысшее состояние доски, которое ИИ может играть, если предположить, что противник играет оптимально. Таким образом, ИИ выберет первый ход, который приведет к состоянию доски 8, и, если противник играет оптимально, ИИ должен сыграть все ходы, чтобы перейти к состоянию доски 8. (Следуйте примечаниям на моих рисунках)

Я знаю, что это было много. Если вы один из тех, кому нужно, чтобы кто-то поговорил с вами, чтобы что-то понять, вот несколько видео, которые я посмотрел, чтобы помочь мне понять идею, лежащую в основе этого: 1, 2, 3.

Шаг 6: минимаксный алгоритм: псевдокод

После того, как вы поймете логику минимаксного алгоритма, взгляните на этот псевдокод (функции, универсальные для всех кодов) из википедии:

функция minimax (node, depth, maximizingPlayer) равна

если глубина = 0 или узел является конечным узлом, тогда

вернуть эвристическое значение узла

если maximizingPlayer, то

значение: = −∞

для каждого потомка узла сделать

значение: = макс (значение, минимакс (дочерний элемент, глубина - 1, ЛОЖЬ))

возвращаемое значение

else (* сворачивание игрока *)

значение: = + ∞

для каждого потомка узла сделать

значение: = min (значение, минимакс (дочерний элемент, глубина - 1, ИСТИНА))

возвращаемое значение

Это рекурсивная функция, то есть она вызывает себя снова и снова, пока не достигнет точки остановки. Во-первых, функция принимает три значения: узел, глубину и чью очередь. Значение узла - это место, где вы хотите, чтобы программа начала поиск. Глубина - это то, насколько далеко вы хотите, чтобы программа выполняла поиск. Например, в моем примере с деревом он имеет глубину 3, потому что он просматривал все состояния доски после 3 ходов. Конечно, мы хотели бы, чтобы ИИ проверял каждое состояние платы и выбирал наиболее выигрышный вариант, но в большинстве игр, где существуют тысячи, если не миллионы конфигураций плат, ваш домашний ноутбук не сможет обработать все эти конфигурации. Итак, мы ограничиваем глубину поиска ИИ и переводим его в наилучшее состояние доски.

Этот псевдокод воспроизводит процесс, который я объяснил в предыдущих двух шагах. Теперь давайте сделаем еще один шаг и исправим это в коде Python.

Шаг 7. Создайте свой ИИ с помощью Ai_template.py

Прежде чем взглянуть на мой код Minimax AI, попытайтесь создать свой собственный AI с файлом ai_template.py и псевдокодом, о котором мы говорили на последнем шаге. В шаблоне AI есть две функции: def minimax_min_node (доска, цвет) и def minimax_max_node (доска, цвет). Вместо того, чтобы рекурсивно вызывать саму функцию минимакса, у нас есть две разные функции, которые вызывают друг друга. Чтобы создать эвристику для оценки состояний доски, вам нужно будет создать свою собственную функцию. В файле othello_shared.py есть готовые функции, которые вы можете использовать для создания своего ИИ.

Когда у вас есть ИИ, попробуйте запустить его против randy_ai.py. Чтобы запустить два ais друг против друга, введите "python othello_gui.py (вставьте имя файла ai).py (вставьте имя файла).py" в терминале Mac или введите "run othello_gui.py (вставьте имя файла ai).py" (вставьте имя файла).py "и убедитесь, что вы находитесь в правильном каталоге. Также посмотрите мое видео, чтобы узнать о точных шагах.

Шаг 8: Время заставить ИИ сражаться

Теперь соберите кучу своих компьютерных друзей и заставьте их разработать собственный ИИ! Затем вы можете устроить соревнование, и ваш ИИ победит. Надеюсь, даже если вы не смогли создать свой собственный ИИ, вы смогли понять, как работает алгоритм минимакса. Если у вас есть какие-либо вопросы, не стесняйтесь оставлять их в комментариях ниже.