Искусственный интеллект / [Из песочницы] Искуственный интеллект с нечеткой логикой в аркадной игре

Введение или как я писал свой первый ИИ

Доброго времени суток. Я написал свой первый искуственный интеллект много лет назад, когда учился в колледже. Тогда это был ИИ для змейки в необычной для змеек игре — Serpent's Madness (ссылка ведет на мой сайт игры), в которой последние могут двигаться в любом направлении. Скриншот ниже демонстрирует это:
Тогда это был детерминированный алгоритм, т.е. алгоритм с четкой последовательностью действий, когда на каждом шаге можно точно сказать, что будет на следующем. Выглядел он приблизительно так (псевдокод):
rwarn = 0 //опасность, грозящая змейке справа
lwarn = 0 //опасность, грозящая змейке слева
для всех оппонентов op {
Если точка - центр кости оппонента op лежит в пределах полуокружности змейки, то {
Если точка лежит справа от змейки, то
rwarn++;
Если точка лежит слева от змейки, то
lwarn++;
}
Если движемся параллельно одной из стен на расстоянии не более заданного с максимальным отклонением вектора движения по одной из координат (x или y) не более заданного, то {
Если стена - справа от змейки, то
rwarn+=100;
Если стена - слева от змейки, то
lwarn+=100;
}
Если rwarn!=0 и lwarn != 0, то {
Если rwarn>lwarn, то поворачиваем влево. Иначе - вправо.
}
} //для всех оппонентов op

Т.е. этот ИИ по заданным расположениям змеек всегда делает одно и то же: поворачивает в сторону, где меньше змеек и/или стен. Да-да, я указал магическое число «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 близко, 2 средне, 3 далеко, 4 нет;
впереди 1 близко, 2 средне, 3 далеко, 4 нет;
справа 1 далеко, 2 нет, 3 далеко, 4 нет
Результатом должно быть решение повернуть вправо.
мин(макс(1, 0.75, 0, 0), макс(1, 0.75, 0, 0), макс(0,0,0,0) = мин(1,1,0) = 0 = повернуть вправо
Пример №3
слева 1 близко, 2 средне, 3 далеко, 4 нет
впереди 1 близко, 2 средне, 3 далеко, 4 нет
справа 1 далеко, 2 нет, 3 близко, 4 нет
Результат сложно принять — везде есть опасность неминуемой гибели.
Что решит змейка:
мин(макс(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 на андроид, к сожалению, нельзя увидеть как он работает, в ней используется алгоритм почти такой же, что я приводил во введении. Нечеткий ИИ есть только в полной версии приложения (ссылка — в конце поста).
/**
*
*/
package com.iz.serpents.tools;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

import android.graphics.RectF;

import com.iz.serpents.model.Movement;
import com.iz.serpents.model.Serpent;
import com.iz.serpents.model.SerpentCollidable;

/**
* @author iz
* There are three sectors, which in sum gives us one half of circle,
* these sectors corresponds to aim, specified in constructor.
* Each sector (LEFT, RIGHT, FORWARD) is 60 degrees.
* So, sector is 1/6 of circle square.
*
*/
public class CircleSector implements ICircleSectorReadable {
/*
* Checks if circle sector has the given point.
* Algorithm is:
* 1) check distance < radius
* 2) check point is to the left of the first line
* 3) check point is to the right of the second line
*/
public boolean hasPoint(Vector pt) {
return (pt.qdist(O) < rad &&
pt.isOnLine(O, A)0);
}

/*
* Checks, if this sector has intersection with specified rectange. It is thought,
* that sector's center is allways inside this rectangle. Return of the method will be
* intersection points from 0 to 4.
*/
public List intersectionPoints(RectF rect) {
List res = new LinkedList();
return res;
}

/*
* Creates sector
* @param movementType - one of Movement.*, used in sector creation, different
* movementTypes means different sectors
* Note, that FORWARD sector will have radius greater, than specified in circleRadius.
*/
public CircleSector(float circleRadius, int movementType,
Vector aim, Vector circleCenter) {
if(movementType == Movement.FORWARD)
rad = circleRadius * 1.1f;
else
rad = circleRadius;
O = circleCenter;
type = movementType;
_ptBones = new LinkedList();
_ptWalls = new LinkedList();
Vector ortAim = (Vector) aim.clone();
ortAim.normalize();
Vector vC = ortAim.mul(rad);
Vector vAC = null, vCB = null;
if(type == Movement.LEFT || type == Movement.FORWARD) {
vAC = (Vector) vC.clone(); vAC.qrotate(30, Movement.LEFT);
}
if(type == Movement.FORWARD || type == Movement.RIGHT) {
vCB = (Vector) vC.clone(); vCB.qrotate(30, Movement.RIGHT);
}
switch(type) {
case Movement.LEFT:
Vector lo = (Vector) ortAim.clone(); lo.leftOrtogonalRotate();
A = O.add( lo.mul(rad) );
B = O.add(vAC);
break;
case Movement.FORWARD:
A = O.add(vAC);
B = O.add(vCB);
break;
case Movement.RIGHT:
Vector ro = (Vector) ortAim.clone(); ro.rightOrtogonalRotate();
A = O.add(vCB);
B = O.add( ro.mul(rad) );
break;
}
possibleBonesInside = (int) ((rad*rad)/
(6f*Serpent.boneRad()*Serpent.boneRad()));
}

/*
* Fills sector with content
*/
public void addBones(List serpents, int indAI) {
_indAI = indAI;
for(int j = 0;j<serpents.size();j++) {
Serpent s = serpents.get(j);
int start = 0;
if(j==indAI)
start = SerpentCollidable.afterNeckInd;
for(int i=start;i<s.numBones();i++) {
if(hasPoint(s.bone(i)))
_ptBones.add(s.bone(i));
}
}
}

/*
* Gets number of bones in sector
*/
public int getNumBones() {
return _ptBones.size();
}

/*
* Fills sector with content
*/
public void addWalls(RectF walls) {
List walls_points = new LinkedList();
walls_points.add(Vector.create(walls.left, walls.top));
walls_points.add(Vector.create(walls.right, walls.top));
walls_points.add(Vector.create(walls.right, walls.bottom));
walls_points.add(Vector.create(walls.left, walls.bottom));
walls_points.add(Vector.create(walls.left, walls.top));
for(int i=0;i<walls_points.size()-1;i++) {
Vector common;
//left
common = Vector.intersect(walls_points.get(i),
walls_points.get(i+1),
O, A);
if(common!=null)
_ptWalls.add(common);
//right
common = Vector.intersect(walls_points.get(i),
walls_points.get(i+1),
O, B);
if(common!=null)
_ptWalls.add(common);
//forward
common = Vector.intersect(walls_points.get(i),
walls_points.get(i+1),
A, B);
if(common!=null)
_ptWalls.add(common);
//corner
if(_ptWalls.size()==1)
_ptWalls.add(walls_points.get(i+1));
}
}

/*
* Gets number of wall's ends in sector:
* 0 - no walls
* 2 - one wall
* 3 - two walls (corner)
* 4 - two walls
* wall is a line with two (!) ends
*/
public int getNumWallEnds() {
return _ptWalls.size();
}

/*
* Gets distance to closest serpent in range [0;rad]
* Attention! Distance = rad, when there actually
* no serpents!
*/
public float distToClosestSerpent() {
float res = rad;
for(int i=0;i<_ptBones.size();i++) {
float dist = _ptBones.get(i).qdist(O);
if(dist < res)
res = dist;
}
return res;
}

/*
* Gets distance to closest wall in range [0;rad]
* Attention! Distance = rad, when there actually
* no walls!
*/
public float distToClosestWall() {
float res = rad;
for(int i=0;i<_ptWalls.size();i++) {
float dist = _ptWalls.get(i).qdist(O);
if(dist < res)
res = dist;
}
return res;
}

//RELATION FUNCTIONS//
//all relation functions returns value in ragne [0;1],
//where 1 - is "the worst" or "the biggest" threat
//and 0 - means no threat at all

public float rel_distToClosestSerpent() {
return 1 - distToClosestSerpent()/rad;
}

public float rel_serpentsStrength() {
return ((float)getNumBones())/possibleBonesInside;
}

public float rel_distToClosestWall() {
return 1 - distToClosestWall()/rad;
}

public float rel_inCorner() {
float res = 0;
if(getNumWallEnds()==4)
res = 0.5f;
if(getNumWallEnds()==3)
res = 1f;
return res;
}

public float rel_max_threat() {
return Math.max(
Math.max(rel_distToClosestSerpent(), rel_serpentsStrength()),
Math.max(rel_distToClosestWall(), rel_inCorner()));
}

/*
* Finds minimal threat and returns index of the element.
* Keep in mind, that if all threats are equal, than the first
* sector will be returned.
*/
public static int findMinThreatReturnIndex(ICircleSectorReadable sector[]) {
float min = sector[0].rel_max_threat();
int result = 0;
for(int i=1;icur) {
result = i;
min = cur;
}
}
return result;
}

//RELATION FUNCTIONS END//

//sector geometry
private Vector O;
private Vector A;
private Vector B;
private final float rad;
private final int type;
private final int possibleBonesInside;
//sector is presented as two lines: (O,A) - left line, (0,B) - right line,
//O - is center of circle, which sector it is
//rad - radius of circle, which sector it is
//type is one of Movement.*, used in sector creation, different
//movementTypes means different sectors
//when working with walls there used triangular instead of circle center - for
//performance reasons

//initialed if necessary:
//sector content
private List _ptBones = null;
private List _ptWalls = null;
//sector owner
private int _indAI;

//interface readable
@Override
public Vector getO() {
return (Vector) O.clone();
}

@Override
public Vector getA() {
return (Vector) A.clone();
}

@Override
public Vector getB() {
return (Vector) B.clone();
}

@Override
public float getRad() {
// TODO Auto-generated method stub
return rad;
}

/*
* Get's movement type of this sector
*/
@Override
public int getMoveType() {
// TODO Auto-generated method stub
return type;
}

@Override
public List getBonesInside() {
return Collections.unmodifiableList(_ptBones);
}

@Override
public List getWallEndsInside() {
return Collections.unmodifiableList(_ptWalls);
}

/*
* Get sector owner. Warning: it is initialized only
* after addBones() call! When created, sector does not
* belong to anyone.
* @see com.iz.serpents.tools.ICircleSectorReadable#indAI()
*/
@Override
public int getOwnerInd() {
return _indAI;
}
}

Результаты

Ниже представлены скриншоты из Serpent's Madness на андроид в режиме отладки ИИ.
Белым обозначены границы секторов – треугольники (для стенок, для костей – несложно представить).
Желтым выделены кости в секторе.
А красным – стены в секторе.
Иногда они все же сталкиваются. Как я писал выше, это устраняется увеличением секторов. Но в рамках игры не нужен был непобедимый ИИ.
Но в целом, ИИ отличный:
Это моя первая разработка для платформы Андроид и первый ИИ с нечеткой логикой, если есть предложения и замечания — всегда готов выслушать. Спасибо за внимание. Если Вас заинтересовала игра, Вы можете скачать ДЕМО с Андроид Маркета.