Что такое алгоритм в компьютерной игре
Обновлено: 02.07.2024
В статье рассмотрены способы создания универсальной компьютерной программы, играющей в логические игры («Крестики-нолики», «Реверси» и т.п.). Также проведен анализ некоторых универсальных алгоритмов выбора оптимального хода.
Программа должна состоять из двух частей: алгоритма выбора оптимального хода для игрока-компьютера и набора функций, определяющих правила игры (рассматриваться будут только антагонистические игры).
Антагонистическая игра (или игра с нулевой суммой) - некооперативная игра, в которой участвуют два игрока, выигрыши которых противоположны.
Рассмотрим каждую часть отдельно.
1. Алгоритм выбора оптимального хода
Алгоритм должен быть универсальным (не зависеть от правил игры) и обеспечивать хороший уровень игры. Первый рассматриваемый алгоритм, удовлетворяющий этим условиям – алгоритм минимаксного дерева.
Игрок в текущей позиции пытается сделать все возможные ходы и максимизировать свой выигрыш, а также минимизировать выигрыш другого игрока. Перебор позиций проводится при помощи поиска в глубину (depth-first search, DFS) до достижения некоторой заданной глубины \(d\) или конца игры.
- \(p\) – текущая позиция;
- \(p_i\) – все позиции, доступные из позиции \(p\);
- \(F(p)\) – выигрыш игрока в позиции \(p\).
Если позиция p является терминальной, то для нее определена функция \(f(p)\), определяющая выигрыш игрока, которому принадлежит ход в этой позиции.
Позиция называется терминальной, если из нее нет разрешенных ходов (достигнуты конец игры или необходимая глубина перебора).
Выигрыш игрока будет равен:
если позиция \(p\) – терминальная, иначе
- Простая реализация.
- Гарантированно будут рассмотрены все ходы.
Недостаток: требуется проверять все возможные ходы и при увеличении глубины перебора количество рассматриваемых позиций растет экспоненциально.
Количество перебираемых вариантов можно уменьшить, если прекращать поиск точной оценки хода, когда стало известно, что этот ход не может стать лучше, чем один из ходов, рассмотренных ранее[1].
Алгоритм альфа-бета отсечений при вычислении оценки позиции иcпользует верхнюю и нижнюю допустимые границы.
- alpha – верхняя граница;
- beta – нижняя граница;
- \(F_(p,alpha,beta)\) – функция, вычисляющая оценку позиции \(p\) методом альфа-бета отсечений.
Функция Fab должна удовлетворять условиям:
- \(F_(p,alpha,beta) \le alpha\), если \(F(p) \le alpha\)
- \(F_(p,alpha,beta) = F(p)\), если \(alpha < F(p) < beta\)
- \(F_(p,alpha,beta) \ge beta\), если \(F(p) \ge beta\)
- В большинстве случаев значительно уменьшается количество рассматриваемых позиций при переборе.
- Реализация легко получается из реализации алгоритма мини-максного дерева.
- Результат не хуже, чем при полном переборе позиций.
Недостаток: сложность алгоритма остается такой же, как и при полном переборе позиций (экспоненциальной). Существуют случаи, когда выигрыш от оптимизации незначителен или отсутствует.
Сравнение количества перебранных позиций для первых 10 ходов в игре «Реверси» на поле 8х8 при использовании алгоритмов минимаксного дерева и альфа-бета отсечений (глубина перебора 6 позиций, программа играет против человека, человек делает ход первым)
| Номер хода | Минимаксное дерево поиска (полный перебор) | Перебор с использованием альфа-бета отсечений |
|---|---|---|
| 1 | 16 251 | 1 015 |
| 2 | 61 730 | 1 712 |
| 3 | 568 484 | 10 948 |
| 4 | 1 083 976 | 14 325 |
| 5 | 1 624 623 | 13 598 |
| 6 | 2 412 356 | 18 287 |
| 7 | 1 847 605 | 15 328 |
| 8 | 5 389 480 | 30 807 |
| 9 | 4 870 334 | 22 508 |
| 10 | 3 390 729 | 21 994 |
Альтернативой алгоритму минимаксного дерева является использование метода Монте-Карло.
Метод Монте-Карло - общее название группы численных методов, основанных на получении большого числа реализаций случайного процесса, вероятностные характеристики которого совпадают с аналогичными величинами решаемой задачи.
В нашей задаче (поиск оптимального хода): для текущей позиции \(p\) выбираются все возможные позиции \(p_i\) и с каждой из этих позиций разыгрывается большое количество случайных партий. Позиция, для которой соотношение побед и поражений будет наилучшим, выбирается для следующего хода.
- Высокий уровень игры при большом количестве разыгрываемых случайных партий.
- Хорошо поддается распараллеливанию.
- Линейная сложность.
- Хорошие ходы могут не попасть в случайную выборку.
- Для сильной игры требуется производительный компьютер.
Например, одна из сильнейших программ для игры в го, «MoGo», использующая этот метод, запускалась на компьютере производительностью 15 Терафлопс[3] (для сравнения, производительность процессора Intel Core i7-975 0.06 Терафлопс[2], а производительность суперкомпьютера СКИФ МГУ 47,17 Терафлопс[4]).
График зависимости количества выигранных партий в игру «Реверси» на поле 8х8 для программы, использующей метод Монте-Карло с разным числом разыгрываемых случайных партий, играющей против программы, использующей алгоритм альфа-бета отсечений с глубиной перебора 6 позиций.
2. Способы описания правил.
В программе алгоритм получает сведения о правилах игры через вызов специальных функций. Пример набора функций, достаточного для большинства логических игр:
- Задание начальных условий.
- Проверка возможности хода.
- Выполнение хода и оценка позиции.
- Проверка условия конца игры.
Для обеспечения универсальности, функции должны поддерживать выбор правил для разных игр. Правила могут быть представлены разными способами.
1. Набор функций для каждой игры описывается вместе с остальными функциями (алгоритмом выбора хода и т.п.) и компилируется в один исполняемый файл.
- Простая реализация.
- Высокая скорость работы игровых функций.
- Для добавления правил игры необходимы весь исходный код программы и компилятор.
- Необходимо знание языка программирования, на котором написана программа.
2. Подключение набора функций в виде внешнего модуля (например, DLL).
Большинство шахматных программ подключается к шахматным оболочкам в виде внешних модулей (для взаимодействия обычно используется специальный протокол UCI - Universal Chess Interface).
- Возможность создания любого количества игр, не изменяя исход-ный код программы.
- Высокая скорость работы функций, реализованных в модулях.
- Необходимость знания языка программирования, программу на котором можно скомпилировать в модуль.
- Нужен интерфейс для взаимодействия с модулями.
3. Реализация программы как интерпретатора языка программирования. Каждая функция описываются в виде программы, которую можно интерпретировать и которая может получать доступ к игровым переменным. При вызове функции программа интерпретируется с заданными параметрами (номер игрока, координаты хода и т.п.) и, если требуется, возвращает не-которое значение (выигрыш игрока, возможность хода и т.п.).
- Количество возможных игр не ограничено.
- Не требует средств разработки и каких-либо компиляторов.
- Язык должен быть очень простым и обучение программированию на нем не должно занимать много времени. (В язык могут быть встроены функции, облегчающие какие-либо часто встречающиеся операции (например, функции, подсчитывающие количество идущих подряд клеток определенного цвета).
- Требуется изучение специального языка.
- Язык может уступать по функциональности распространенным языкам высокого уровня.
- Скорость работы значительно ниже, чем при использовании скомпилированного кода, т.к. тратится дополнительное время на интерпретацию.
Пример программы на интерпретируемом языке, описывающей правила игры “Крестики-нолики” на поле 3х3:
4. Правила создаются при помощи визуального редактора. Наборы действий для каждой функции могут собираться из большого числа стандартных блоков, которые могут отображаться в удобном для пользователя виде.
Такой подход использует среда разработки Scratch, разработанная в MIT.
Схема из блоков может быть автоматически преобразована в программный код, который может интерпретироваться, либо компилироваться в программный модуль.
- Не требуется специального обучения программированию.
- Функции, составленные из блоков, удобно редактировать.
Недостаток: высокая сложность реализации подхода.
Это был краткий обзор универсальных алгоритмов выбора оптимального хода и способов определения правил для логических антагонистических игр.
Данная статья была опубликована в сборнике “Энергия и талант молодёжи - залог развития наукоёмких производств. Сборник научных трудов XII Областной научно-практической конференции молодых учёных. - Т. 1 - Псков: Издательство ППИ, 2010.
Поиск в ширину - равномерное исследование во всех направлениях.
реклама
Используют этот алгоритм при решении задач теории графов, при поиске пути, процедурной генерации миров, при проектировке печатных плат и многие другие, но сегодня нам понадобится именно поиск кратчайшего пути в графе.
Создавая режим для еще не вышедшей игры S&Box (Преемник Garry`s mod) мы процедурно генерируем карту из комнат, каждая из комнат получает индекс в формате [x, y, z]. Где x,y могут иметь значения от -32 768 до 32 767, а z изменяется от 0 до 2, поскольку сейчас мы подразумеваем, что этажей будет всего 3.
Наш режим должен будет стать кооперативным побегом причем игроки не всегда находятся в 1 месте. Следовательно противники - ИИ. Они ищут ближайшего игрока и двигаются к нему. Чтобы найти действительно ближайшего игрока нельзя сравнивать их координаты. Поскольку комнаты могут быть расположены вот так:
Скажу сразу, картинка немного не точная. Расстояния между комнатами всегда одинаковое, а комнаты ровные.
Координатно красная точка в 0:0 ближе к фиолетовой внутри -1:0, но идти до нее намного дольше чем до фиолетовой точки 1:1. Именно тут, мы можем применить поиск в ширину.
В красной точке вызывается метод поиска ближайшего игрока который принимает индекс текущей комнаты - [0,0,z] Помечает эту комнату как посещенную. Далее он обращается к словарю в котором хранятся комнаты (Они же vertexes в теории графов) с этими индексами и узнает у комнаты какие есть проходы (Они же edges в теории графов), Далее проверяет какие индексы из них уже посещены и если не посещенных вертексов более 1, он добавляет эту комнату в очередь (Branch - разветвление) с указанием количества не посещенных сторон. Поскольку 1 поток может выполнять только 1 операцию за раз, мы не можем сразу двигаться из 0:1 в 1:1 и -1:1 поэтому двигаемся сначала в ту сторону, у которой угол между текущей позицией и следующей наименьший согласно тригонометрическому кругу. Когда мы находим игрока, мы отправляем список с индексами комнат, у нас он будет: ([0,0,z]; [0,1,z]; [1:1,z])
Скорость этого алгоритма = O(Vertexes + Edges)
Алгоритм Дейкстры
Алгоритм Дейкстры - он же алгоритм поиска с равномерной стоимостью. Используется для поиска оптимальных маршрутов
Бывает так, что проход между комнатами разный. Например, чтобы попасть в комнату, у которой нет двери стоимость прохода 1 очко, а где есть дверь, 1.2 очка, поскольку нужно потратить время на ее открытие. Соответственно мы можем выбирать путь из наиболее дешевого пути. Мы этот алгоритм использовать не стали, поскольку у нас проходы между комнатами всегда равны, а скорость движения внутри комнаты не зависит от чего-либо. Более того, этот алгоритм подразумевает нахождение наиболее "дешевых" путей для всех узлов. Реализация алгоритма Дейкстры похожа на поиск в ширину, но появляется список стоимости перехода между клетками и его учет при выборе пути.
Скорость этого алгоритма = O(N 2 ) - при линейном поиске
Скорость этого алгоритма = O(M Log N) - при бинарном поиске
Привет детишки, сегодня я хочу рассказать вам сказку про генетические алгоритмы и их применение в игрострое. Простыми словами мы рассмотрим теорию и практику, а в качестве примера напишем небольшую утилиту для балансировки игры.
Уровень подготовки:
Если за плечами уже есть змейка и тетрис - читаем смело. Если нет, ничего страшного, расширяем кругозор.
Также желательны базовые знание LUA для понимания кода.
Теоретическая часть.
Наверняка многие уже не раз слышали про генетические алгоритмы и с чем их едят.
Что далеко ходить, у нас даже есть небольшая статья в разделе термины Генетический алгоритм.
Но сегодня разговор не о теоретической, а практической стороне вопроса, как все это безобразие можно пустить в дело.
Для начала попробую простыми словами рассказать, что же из себя представляет этот хитрый алгоритм.
Если максимально упрощенно генетический алгоритм - ничто иное, как подбор коэффициентов для решения уравнения.
Вся соль кроется в способе подбора этих параметров, тут то мы и вспоминаем про название алгоритма.
Представим искомые коэффициенты как гены и вспомним, как работает эволюция.
Еще в далекие времена Дарвин говорил про естественный отбор, что всегда выживает самый приспособленный. Вот так же и у нас.
алгоритм до неприличия прост:
1-создаем новое поколение популяции
2-отбираем самых приспособленных, остальных удаляем
3-из оставшихся выводим(селекционируем) новое поколение и снова пункт 2
И все это происходит до тех пор, поке не будет найдено решение задачи.
Простой пример: уравнение X + Y = 100, здесь X и Y можно представить как гены.
Создаем 4 особи со случайным набором ген:
( X = 2, Y = 2 )
( X = 20, Y = 2 )
( X = 30, Y = 50 )
( X = 22, Y = 44 )
Проверяем приспособленность, для этого считаем насколько переменные приближают нас к решению уравнения:
| 2 + 2 | / 100 = 0.04
| 20 + 2 | / 100 = 0.22
| 30 + 50 | / 100 = 0.8
| 22 + 44 | / 100 = 0.66
На основе лучшей пары создаем следующее поколение, также добавляем в него и лучших особей из предыдущего.
У нас крайне простой случай, у каждой особи всего по 2 гена.
Скрещиваем ( X1, Y1 ) и ( X2, Y2 ) и получаем в итоге ( X1, Y2 ) и ( X2, Y1 )
новое поколение:
( X = 30, Y = 50 ) родитель 1
( X = 22, Y = 44 ) родитель 2
( X = 30, Y = 44) потомок 1
( X = 22, Y = 50) потомок 2
И казалось бы, вот уже мы скачем верхом на эволюционном процессе и все задачи нам по плечу, но не все так просто.
На данном примере видно, что уже через 1 итерацию - новых генов взять неоткуда, а из старых уже найдена лучшая комбинация.
Решения достигнуто не было, и система работает без изменений.
Тут то нам на помощь приходят мутации, они не такие красивые как скажем в сталкере, но зато очень даже эффективные.
Суть мутации проста: добавить новых генов при формировании следующей популяции.
Будь это совершенно новая особь или изменение случайных генов потомка, уже детали реализации.
Но, как говорится и это еще не все! При большом количестве генов система порой приходит к равновесию, так и не найдя решения.
И даже мутации из за малого удельного веса не спасают ситуацию.
В качестве аналогии можно привести новичка, пришедшего в большую компанию.
У него горят глаза, полно энергии, идей, инновационные технологии.
Он кричит: “Я знаю как правильно, как нам улучшить компанию, достигнуть успеха, даже есть опыт”
А с другой стороны - бывалые дяди, которые всю жизнь тут трудятся и знают, как делать дела.
У них связи, авторитет, они сидят на откатах и не хотят ничего менять.
И они ему говорят: “Ты кто такой ваще, ты нам мать что ли, че учить то нас вздумал, уйди,
не мешай работать” А дальше система либо его ломает, либо он уходит.
И чтобы эволюция не буксовала на месте - нужны встряски. Как с динозаврами например.
Как только происходит застой ( появился стабильный генотип ), всей системе нужна встряска.
Удаление большей части популяции или даже полностью всей и создание недостающих особей со случайным набором генов.
Опять же аналогия с компанией.
Большие компании поделили рынок поровну и всем достается понемногу, рынок не развивается.
И тут приходят стартапы, состоящие из тех самых молодчиков с горящими глазами.
Конечно только один из ста в итоге останется на плаву, а остальные потонут, но тот кто сможет - сорвет куш.
Итак ребятишки, давайте подведем итог, что же сегодня мы узнали.
Для работы генетического алгоритма нужны следующие вещи:
-описать решение задачи набором параметров( генов ) назовем это описание особью.
-определить критерии успешности особи( мера правильности решения задачи )
-провести эволюционный отбор при помощи 3х методов: скрещивание, мутация и встряска.
Практическая часть.
Формулы и циферки эт конечно хорошо, но как говорится ближе к телу.
Есть задача, с которой часто встречаются, как разработчики, так и игроки, а именно расчет билда.
Для простоты примем, что игра пошаговая.
Есть монстр, у него нет хп и мы будем измерять максимально урон, который герой может нанести пока не погибнет.
Каждые 3 хода монстр атакует игрока, с 20% шансом крита.
Есть игрок со следующими параметрами: шкалы здоровья и силы, реген здоровья и силы, атака и защита.
Также у игрока есть экипировка, которая влияет на параметры.
В качестве генов здесь будет выступать экипировка, что и в каком слоте находится у героя.
руки:
меч1( атака 5, требует силы 5 )
меч2( атака 4, требует силы 3 )
меч3( атака 8, требует силы 10 )
щит1( защита 3, требует силы 2 )
щит2( защита 5, требует силы 3 )
туловище:
доспех1( защита 5, атака -2 )
доспех2( защита 3, атака 0 )
доспех3( защита 1, реген здоровья 1 )
голова:
шлем( защита 2 )
шапка силы( реген силы 1 )
шапка здоровья( реген здоровья 1 )
макс здоровье 500
макс сила 100
реген здоровья 0
реген силы 5
атака 1
защита 1
Монстр атакует за раз на 25 единиц, во время крита на 45, шанс крита 20%.
Игрок атакует каждый ход, когда хватает силы.
Кодить все это дело будем на луа. Почему, да это быстро и весело :)
Для начала пропишем параметры персонажа, монстра и экипировки.
Теперь когда с входными данными закончено - идем дальше.
Первым делом нам нужно сгенерировать особь( то есть создать случайный билд )
Для этого напишем небольшую функцию:
Копируем параметры заданные по умолчанию в новый билд)
Дальше устанавливаем в слоты экипировку.
Здесь вместо готовой таблицы устанавливаем ссылку на исходную таблицу и генерируем в ее пределах случайный индекс.
Это нам понадобится для селекции.
Перед тем как вернуть созданный билд, добавляем параметры из экипировки в параметры самого билда.
Это делается небольшой функцией:
Теперь нужен способ скрещивания особей, так как гены у нас, это просто индексы массива,
то скрещивание будет представлять из себя случайный выбор гена у одной из особей родителей.
Ну и чтоб ускорить эволюцию немного, одна из особей( доминантная ) будет иметь больший шанс( 6 из 10 ) передать свои гены.
Также во избежание вырождения популяции добавим шанс мутации ( 2 из 10 )
В нашем случае мутация - случайное изменение одного из генов( слота экипировки )
Добавляем параметры экипировки к билду и готово!
Еще нам понадобится функция оценки жизнеспособности билда, пишем:
Оценивать будем по максимальному нанесенному урону, также не лишним будет знать - сколько на это потребовалось шагов.
На каждом шаге мы делаем следующие вещи:
-Если достаточно энергии - атакуем.
-Если ход кратный трем, получаем урон от монстра( с 20% шансом крита ).
-Проводим регенерацию здоровья и энергии.
-Проверяем, вдруг билд получился круче монстра, ограничивая все это дело 10000 итераций.
В итоге возвращаем нанесенный урон и продолжительность битвы.
Итак все приготовления сделаны и пришло время окунуться в увлекательный мир генетических алгоритмов. Вы готовы дети!?
А вот и сам генетический алгоритм, подгреб к нашему празднику невежества и знаний:
Создаем таблицу и заполняем случайными билдами. Размер популяции был выбран в 16 особей.
Далее вся популяция проходит проверку боем и сортируется по нанесенному урону.
Переходим к селекции. Гены лучшей половины популяции переходят в следующее поколение.
После чего начинаем скрещивать успешную половину с теми, кто отбор так и не прошел, в этот же момент может происходить мутация.
В итоге мы получаем количество особей, что было в начале. И опять бой, селекция, бой…
Казалось бы все этом может длиться вечно, но на небольшом количестве генов лучшая комбинация находится довольно быстро,
поэтому у нас стоит ограничение в 50 циклов. После чего можно подводить итоги.
Для запуска всего этого мракобесия осталось только взвести рандомизатор по текущему времени и запустить симуляцию.
Сохраняем , запускаем, затаив дыхание ждем результата.
И вуаля! Видим, что самый хороший билд это: два вторых меча, доспех номер 3 и шапка жизни :)
Запустив симуляцию еще несколько раз подряд - видно что, этот билд является стабильным, но все же иногда есть небольшие отклонения.
Это получается за счет небольшого количества поколений и рандома связанного с критическими атаками монстра.
При увеличении количества поколений до 500 - билд получается всегда один и тот же.
Поэтому для балансировки важно правильно подобрать количество итераций.
Вот сводный график 3х запусков моделирования. Зависимость нанесенного урона от поколения особей.
Высокий старт всех случаев обусловлен тем, что это результаты лучшей особи первого поколения.
Основная часть эволюции происходит в течении первых 20 циклов, после уже видна стабилизация.
Снизив количество поколений до 10, можно увидеть и другие жизнеспособные варианты.
Что интересно, в них ни разу не было щитов, а значит они нуждаются в ребалансе.
Та же при помощи этого алгоритма можно определить среднее время жизни монстра,
а если немного переделать, то появится возможность сталкивать билды друг с другом.
Правда в примере не был использован механизм встряски, из за малого количества генов, его эффект был бы просто незаметен.
Надеюсь еще расскажу вам об этом, но это уже будет совсем другая история.
Если вы думаете, что изучение программирования подходит только для старшеклассников, то вы ошибаетесь! При помощи современных образовательных игр можно научить составлять алгоритмы даже четырехлеток и тем более - младших школьников. Игровая среда не пугает детей. Через увлекательные программы, разработанные в формате игр, можно познакомиться с основами кодинга и привить интерес к программированию в целом.
Это отдельный ресурс с различными курсами по программированию. Начиная с 4-6 лет тут можно обучить ребенка основам информатики, даже если он не умеет читать. Для освоивших данный курс есть продолжение.
Занятия проходят в игровой форме.
Lightbot
Minecraft
Это игра, которой одержимы дети всего мира уже на протяжении нескольких лет. Сама по себе она развивает пространственное и логическое мышление, математические способности. Существует образовательная версия этой увлекательной игры, где для решения различных задач необходимо построить правильные алгоритмы. Дети с младшего школьного возраста смогут освоить основы программирования.
Для тех, кто хочет выжать максимум из игры и сделать ее личным стартом в мир программирования: Minecraft Creator
Scratch
Скретч – это визуальный язык программирования, совместимый с различными платформами, в том числе с конструктором LEGO WeDo и контроллером Ардуино. При помощи ярких и красочных программных блоков, можно составить алгоритмы и привести в движение собранную модель. Дети сразу видят результат и воодушевляются на дальнейшее изучение кодинга.
Программирование Scratch также доступно в нашем центре: Scratch
ПиктоМир
Это отечественная разработка, ориентированная на обучение программированию младших школьников и даже дошкольников, которые не умеют еще читать и писать. Дети учатся составлять алгоритмы, задавая правильное направление роботам, работающим на космодроме. В игре шесть уровней сложности, рассчитанных на разный уровень подготовки.
Познакомиться с этой интересной разработкой можно у нас в центре: ПиктоМир
Colobot
Многие образовательные игры сейчас создаются для малышей и младших школьников. Но ребят постарше тоже не обходят вниманием. Колобот – игра для тех, кому уже есть 10 лет и старше. Тут нужно правильно программировать роботов, чтобы подготовить планету для заселения и добычи полезных ископаемых. Язык программирования тут более серьезный, чем блочный. Он очень похож на языки C ++ и Java, но с небольшими ограничениями.
Java Rush
Обучение программированию проходит в формате видеоигры. Как видно из названия, учащиеся пользуются языком Java. Дети осваивают планеты солнечной системы, перемещаясь на космическом корабле.
Code Combat
Это полноценная компьютерная игра, ориентированная на детей от восьми лет. Играть могут даже дети с нулевыми познаниями в программировании, совершенствуя свои навыки с каждым уровнем. Написание алгоритмов может быть на нескольких языках – JavaScript, Lua, Python, CoffeScriot и другие. Игроки становятся волшебниками, которые с помощью программного кода меняют окружающий мир.
Примечание: Как программировать научит информатика для школьников в молодежном образовательном развивающем центре POLYCENT. Проводим занятия как продвинутого уровня, так и преподаем начальное программирование для детей возрастом от 5 до 15 лет.
Читайте также: