Введение или как я писал свой первый ИИ
Доброго времени суток. Я написал свой первый искуственный интеллект много лет назад, когда учился в колледже. Тогда это был ИИ для змейки в необычной для змеек игре — Serpent's Madness (ссылка ведет на мой сайт игры), в которой последние могут двигаться в любом направлении. Скриншот ниже демонстрирует это:
Тогда это был детерминированный алгоритм, т.е. алгоритм с четкой последовательностью действий, когда на каждом шаге можно точно сказать, что будет на следующем. Выглядел он приблизительно так (псевдокод):
Т.е. этот ИИ по заданным расположениям змеек всегда делает одно и то же: поворачивает в сторону, где меньше змеек и/или стен. Да-да, я указал магическое число «100», на которое увеличивается опасность, если есть стена. Магические числа — плохой стиль программирования, но в то время это было простительно. Сделал я это, чтобы змейки чаще врезались в других змеек чем стены, хотя условие это достаточно относительное: если в пределах полуокружности змейки справа или слева будет более 100 костей (=частей) других змеек, то алгоритм выберет врезаться в стену. Несмотря на это, алгоритм работал достаточно хорошо: ИИ объезжал змеек под разными углами, объезжал стены (никогда сам в них не врезался, если другие змейки не вынуждали), а также балансировал между стеной и змейкой когда приходилось это делать. Однако, у него были 2 недостатка: 1) Когда змейка ехала рядом со стеной, а ИИ оказывался между стеной и змейкой, то даже, если было куда ехать периодически возникало следующее: ИИ путался, дергался — чуть влево, чуть вправо, чуть влево,… и погибал. 2) На том самом заданном расстоянии от змейки ИИ всегда начинал поворот. Если получилось так, что змейка находилась на большем расстоянии от ИИ, а чуть погодя — на значительно меньшем (резко повернула в сторону ИИ), то ИИ врезался. При условии, что он мог повернуть заранее или по крайней мере начать поворачивать. Я думал о том, чтобы ввести еще одну полуокружность с большим радиусом — для которой нужно повернуть «немного». Потом я сказал себе стоп, т.к. алгоритм становился, как мне кажется, чересчур сложным. Уж если усложнять, то непременно вводить waypoint'ы — думал я. Эти два недостатка можно описать одним словом — змейка была в ряде случаев «дерганая» и из-за этого эпизодически погибала. Сейчас, когда через 5 лет, я портировал Serpent's Madness на андроид, я решил, что с этим недостатком надо бороться. И в этом мне помогла «нечеткая логика». Я понимаю нечеткую логику как инструмент внесения наших «нечетких» рассуждений в алгоритм. Итак, взглянем на задачу с новой точки зрения.
Принцип
Змейка в разрабатываемой мной игре Serpent's Madness может двигаться влево, вправо или вперед. Не двигаться вообще она не может. Таким образом, у ИИ будут следующие выходы: 1) повернуть влево 2) повернуть вправо 3) ехать вперед В соответствии с этим представим таблицу c лингвистическими переменными — переменными, которые могут принимать значения фраз из естественного или искусственного языка. Дистанция до змеек Плотность змеек Дистанция до стен Попадание в угол Слева Справа Впереди
В ячейках будут термы. Под термом я понимаю то самое значение фразы для переменных (лингвистических). далеко, как раз, близко — когда речь идет о расстоянии (столбцы 1 и 3) нет, мало, средне, много — когда речь идет о плотности змеек (столбец 2) нет, возможно, точно — когда речь идет о попадании в угол (столбец 4)
Для каждого терма определяются функции принадлежности. По смыслу здесь это будут «функции опасности» от 0 до 1, чем больше значение, тем больше опасность ехать в заданном направлении. Для каждой строки i вычисляем максимум значений в ячейках m(i). Так скажем, максимальную опасность по параметрам в заданном направлении. Затем из всех таких m(i) находим минимум. Минимум это и будет ответ на вопрос — что делать, свернуть влево/вправо или ехать прямо.
Ниже идут несколько примеров. Обращаю внимание на то, что числовая интерперетация приведена лишь для примера. Реально, в разработанной cистеме, могут быть другие значения.
Пример №1 Дистанция до змеек Плотность змеек Дистанция до стен Попадание в угол Слева как раз мало нет нет Справа далеко нет как раз точно Впереди близко много далеко нет Результатом должно быть решение повернуть влево. Что получается из вычислений: мин( макс(0.5, 0.33, 0, 0), макс(0, 0, 0.5, 1), макс(1, 1, 0, 0)) = мин(0.5, 1, 1) = 0.5 = поворот влево
Пример №2 Дистанция до змеек Плотность змеек Дистанция до стен Попадание в угол Слева близко средне далеко нет Справа далеко нет далеко нет Впереди близко средне далеко нет Результатом должно быть решение повернуть вправо. мин(макс(1, 0.75, 0, 0), макс(1, 0.75, 0, 0), макс(0,0,0,0) = мин(1,1,0) = 0 = повернуть вправо
Пример №3 Дистанция до змеек Плотность змеек Дистанция до стен Попадание в угол Слева близко средне далеко нет Справа далеко нет близко нет Впереди близко средне далеко нет Результирующее решение сложно принять — везде есть опасность неминуемой гибели. Что решит змейка: мин(макс(1, 0.75, 0,0), макс(1, 0.75, 0, 0), (0,0, 1, 0)) = мин(1,1,1) = 1 = поворот влево
Я хочу в логику добавить в перспективе следующее: один и тот же терм (скажем близко) для змеек имеет меньшую степень принадлежности, чем для стен. Это даст при неминуемой гибели, скажем по всем направлениям столкновение со змейкой, а не стеной — это для того, чтобы игрокам можно было быстрее набирать очки.
Правила вычислений
При разработке обращу внимание на следующие моменты. Они экономят процессорное время. 1) если терм для функции макс вычислен и равен 1, то нет смысла вычислять остальные, максимум даст 1. 2) если терм для функции мин вычислен и равен 0, то нет смысла вычислять остальные, мин даст 0.
Графическая интерпретация
Слева, впереди, справа — 1,2,3 соответственно. Вертикальная черта — условное обозначение змейки. Это области анализа. Нам нет смысла анализировать, что находится позади, поэтому области 1 и 2 ограничены снизу горизонтальной чертой. Стоит заметить, что при «заполнении» сектора стенами используется не сектор окружности (как в случае с костями змеек), а вписанный в него треугольник. Реализация функций принадлежности для термов Получается, у нас 3 области: слева, справа и впереди. Все эти области в сумме дают половину окружности, а по одиночке — сектора по 1/3 каждый. Сектор может содержать: 1) кости всех змеек (в том числе и самой змейки — свой хвост надо объезжать), т. е. их координаты и количество 2) стены (максимум две, когда угол они имеют общую точку) Такой сектор подается на вход функции «дистанция до змеек», «плотность змеек», «дистанция до стен» и «попадание в угол». Далее возвращаются степени принадлежности и с ними мы уже знаем что делать. Сами функции тоже не сложные. Самый сложный момент — сформировать такие сектора.
Поля и обязанности сектора
Класс «сектор окружности» CircleSector Поведение: 1) проверить принадлежность точки сектору 2) найти пересечение с прямоугольником (от 0 до 4 точек), имея в виду, что сектор находится своим центром всегда внутри прямоугольника 3) Инициализироваться в соответствии с костями змеек и стенками (используя методы выше) 4) узнать мин. Дистанцию до змеек (лингв. Переменная 1) 5) узнать плотность змеек (лингв. Пер. 2) 6) узнать мин. Дистанцию до стен (линг. Пер. 3) 7) узнать степень попадания в угол 8) узнать степень максимальной опасности С 4 по 7 — реализация функций принадлежности. 8 — ищет максимум из 4-7. Поля: точки — координаты (центры) костей змеек точки — координаты отрезков стенок (0, 2, 3 (угол), 4)
Внесение изменений
Реализовав первый вариант нечеткого ИИ я запускаю Serpent's Madness и вижу ряд недостатков. Выявлено, что змейка крутится и крутится, когда нет опасностей. Функция минмакс при одинаковых значениях угроз в секторах возвращает первый сектор. А первый — правый. Сделал первым — передний сектор. Теперь змейка по умолчанию едет вперед, как и требовалось. Заметил, что змейка, когда едет перпендикулярно стене — врезается в нее. При этом анализ проходит как обычно (все инициализировано корректно). Похоже, при движении перпендикулярно все сектора одинаково содержат одну стену, а передний сектор оказывается «самым близким» к ней, соответственно в нем угроза — минимальна. Исправлю это, пусть передний сектор будет несколько длиннее остальных. Тогда функция принадлежности будет возвращать большую угрозу при движении перпендикулярно стене. Уже увеличение радиуса сектора в 1.1 раза по сравнению с остальными секторами избавляет нас от указанного бага. Иногда змейки врезаются головами вдвоем или даже вчетвером. Экспериментально установлено, что при увеличении всех секторов в два раза столкновения становятся реже. Но тогда змейки становятся чересчур осторожными — на большом расстоянии от минимальной опасности поворачивают и играть становится не так интересно. И тем не менее змейки все равно иногда сталкиваются «лбами» вдвоем. Это, на мой взгляд, проблема такого рода интеллекта: анализ только близлежащей области в текущий момент без анализа возможных действий противника в следующие моменты времени.
Листинги Java & Android SDK (v2.1)
А теперь я приведу рабочий код, что почему-то нечасто делают в большинстве статей (что я видел) по искусственному интеллекту с нечеткой логикой. Наглядно увидеть как работает этот ИИ можно, поиграв в уровни с длинными змейками Serpent's Madness. На момент редактирования статьи, это 4-ый уровень.
Результаты
Ниже представлены скриншоты из Serpent's Madness в режиме отладки ИИ. Белым обозначены границы секторов – треугольники (для стенок, для костей – несложно представить).
Желтым выделены кости в секторе.
А красным – стены в секторе.
Иногда они все же сталкиваются. Как я писал выше, это устраняется увеличением секторов. Но в рамках игры не нужен был непобедимый ИИ.
Но в целом, ИИ отличный:
Это моя первая разработка для платформы Андроид и первый ИИ с нечеткой логикой, если есть предложения и замечания — всегда готов выслушать. Спасибо за внимание. Если Вас заинтересовала игра, Вы можете скачать ее с Андроид Маркета: Serpent's Madness