Я помню, как играл в Pokemon, когда был еще ребенком. В этом было что-то такое, что заставило меня захотеть больше играть. Когда я победил лидеров спортзала и элитную четверку, став таким образом чемпионом мира по покемонам, спустя годы я понял, насколько ужасен процессор по сравнению с другими детскими играми. Фактически, глядя на каждое поколение, большая часть ЦП ужасна и не имеет интеллектуальной основы или даже варианта сложности. Есть ли причина, по которой эти игры про покемонов не сложнее? Я задал этот вопрос в старших классах колледжа и решил найти проверенный ответ!
Чтобы проверить эту теорию, мне нужно было доказать, что ИИ может выбирать оптимальные ходы. Я взял несколько классов программирования и несколько классов математики, поэтому я решил написать свой собственный симулятор битвы покемонов! Мне нужно было бы создать свою собственную программную среду для запуска игры, и мне нужно было бы использовать математический алгоритм, чтобы найти лучший набор ходов. Я использовал Python для этого симулятора, если кому-то было интересно.
Программирование
Короче говоря, сделать это было намного труднее, чем я мог когда-либо мечтать! Игры выглядели настолько простыми, однако, происходило так много всего, что никто не видел. С точки зрения программирования это то, что я должен был иметь в виду и в конце концов сделал. Я попытаюсь объяснить свой код из 4000 строк упрощенно:
Создайте хеш-карту всех 151 покемона. Ой, подождите, разве у покемонов нет таких типов, как огонь и вода? Я должен указать их типы. Кроме того, у большинства ходов также есть тип и связь и т. Д. «Это суперэффективно». Например, водная атака наносит больший урон огненному покемону, движется эффект различных типов покемонов. Я также должен указать на это. Но ждать! У каждого покемона также есть характеристики Атаки, Защиты, Скорости, Здоровья и Специальности.
Создайте функцию для каждого хода, как это было в старых играх, и сохраните эти функции в другой хэш-карте. да, вы можете ссылаться на созданные функции внутри вашего объекта. Покемон может только 4 хода в своем арсенале ходов. Программа должна быстро проверить все 100 ходов в игре, чтобы увидеть, какая функция сочетается с каким ходом. Такие как:
Moves = {«летать»: летать (состояние_игры), «копать»: копать (состояние_игры), ……}
Другие мелкие детали, случайные детали в Pokemon, о которых вы никогда не задумывались. Назначьте значения EV и IV, которые делают Pokemon в игре gameboy случайным образом сильным или слабым. Я просто использовал «обычное» значение для простоты. Движения, похожие на копание, делают противника неуязвимым на ход. Движется, как магазин байд, атакует в течение 2–3 ходов, а затем высвобождает полезную нагрузку. Такие движения, как быстрая атака, должны иметь приоритет, чтобы двигаться первыми. И там оооочень многое другое, но я не буду вдаваться в подробности. Не заводите меня на замену;)
Создайте функцию «прогнозирования». Нам нужны данные, чтобы сделать некоторые математические вычисления для нашей стратегии. У меня нет лучшего подхода для этого, но он работал и имел смысл в то время. У каждого покемона есть 4 хода, которые точно копируются из стадиона покемонов, плюс возможность переключаться на другого покемона, поскольку каждая сторона начинается с 6 покемонов. Другими словами, их ходы никогда не изменятся, и мы можем предположить, что компьютерный ИИ их узнает. Мы также предполагаем, что ИИ знает, какой у вас покемон, но не знает, какой ход вы сделаете. Нам нужно разыграть любую возможность, заглядывая вперед на «Х», я просто смотрел на три хода вперед и позже объясню, почему я это сделал. Таким образом, мы можем оценить каждую возможность ходов и увидеть, какие пары ходов являются хорошими и плохими для ИИ. Очевидно, что такой ход, как «всплеск», является ужасной идеей и снижает оценку порядка ходов.
Математика
Я не собираюсь лгать, математику здесь очень сложно понять с небольшим математическим образованием. Так что я изо всех сил стараюсь объяснить, что я сделал. Я буду использовать много диаграмм :)
Встречайте Gradient Decent
Gradient Decent - это в основном алгоритм, который оптимизирует функцию, максимизируя или минимизируя. Посмотрите короткое видео ниже:
У нас есть отправная точка или «предположение» о том, какова точка минимизации. После нескольких итераций «скачки точек» становятся меньше и, кажется, сходятся к какой-то точке. Итак, что на самом деле делает этот алгоритм. Вкратце, вот полный алгоритм:
i: на какой итерации мы сейчас, сколько у нас «точек». r (o), например, выше, говорит, что это абсолютный в своем роде определенный, действует как массив, который содержит функции и каждый раз подталкивает функцию.
r: в основном отрицательное значение основной функции «f», являющейся оценкой.
α: забудьте о том, как его нашли. Просто помните, что это найденное значение говорит о том, насколько большой шаг мы делаем, чтобы добраться до следующей точки. Думайте об этом как о количестве пороха, которое вы используете для пушки. Сколько нужно, чтобы поразить цель, не регулируя прицел?
Чтобы лучше понять, что происходит визуально, посмотрите ниже:
Представьте, что наша первая точка предположения находится на самом верху трехмерного графика. Видите эту вертикальную плоскость, пересекающую нашу основную функцию? Это пересечение - это все возможные места, в которых может находиться наша «следующая точка», в зависимости от того, что мы выбираем для альфы. Мы не знаем наверняка, но интуиция градиентного спуска говорит: «Мы должны выбирать самую низкую точку в нашем направлении на каждой итерации, в конечном итоге мы найдем абсолютный минимум, если он существует». Переосмыслив проблему и сделав вертикальную плоскость теперь параллельной нам, наш вид теперь становится двухмерным, и теперь мы смотрим на второй график выше. Это быстро превратилось для нас в задачу Calculus 1. Найдите значение для α, которое возвращает минимальное значение нашего направленного «f». Окончательный вывод этого показан в третьем синем квадрате маркированного списка выше.
Получение читаемых данных
Если до сих пор это имело смысл, то поздравляю! Однако у этого алгоритма есть ограничения, которые я не буду вдаваться в подробности, а просто выберу «лучший» метод градиентного спуска. Кроме того, вместо того, чтобы найти самую низкую точку, я вместо этого собираюсь найти оптимальный полином, который подходит для данного графика случайных данных.
Если вы знакомы с методом «наименьших квадратов», то вы знаете, что минимизируется. Если вы этого не сделаете, то представьте, что у вас есть металлический столб и вы хотите уловить как можно больше магнитного песка и как можно быстрее. Расположение шеста и форма шеста имеют значение. Посмотрите видео ниже и вы увидите, как можно изменить положение и форму «шеста» для оптимальной близости. Это итеративная сходимость нелинейного сопряженного градиентного спуска в действии!
Почему это важно? Хорошо представьте, если бы каждая синяя точка была на самом деле оценкой определенного набора движений покемона. Давайте разберемся с этим лучше.
Нечетные ходы представляют индекс AI в его массиве ходов, а четные - человека-противника. (здесь мы хотим максимизировать ИИ). «Указатель» справа переводит его в указатель, который можно изобразить в виде графика. Каждый индекс соответствует определенному набору ходов, который выводит значение в нашей функции «прогнозирования». Также обратите внимание на бинарное поведение, ясно показанное при переходе от индекса 4 к 5. Положительные числа хороши для ИИ, а отрицательные - плохи.
Алгоритм MiniMax
Этот алгоритм начинается с древовидной структуры. Он возвращается в исходное положение между нахождением максимального или минимального значения, прикрепленного к нему, в зависимости от глубины. Посмотрите, сможете ли вы следовать приведенной ниже логике.
Синие числа - это максимальное количество под ним. Тем не мение…
… Красные числа представляют собой минимальные числа, которые подключаются прямо под узлом.
Идея этого алгоритма состоит в том, что обе стороны не допускают глупых ошибок. Таким образом, компьютер максимизирует свою собственную стратегию, в то же время минимизируя человеческую. В современных шахматных приложениях используются гораздо более модифицированные версии этого алгоритма.
Результат моей работы
Подробнее об авторе и скачивании игры
В настоящее время я только начал изучать веб-разработку на онлайн-семинаре Firehose Project. Вы можете проверить игру, щелкнув ссылку ниже:
Если у вас есть какие-либо вопросы или вакансии в веб-разработке, напишите мне ниже :)
Почта: [email protected]
