Blitz AI RBS-системы

[IGR]

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

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


ТЕОРИЯ

Rule-Based Systems – системы основанные на правилах !! Как видно из названия, в основе такой системы ИИ лежат правила, на основе которых система выполняет действия !! Такие системы состоят из трех компонентов:
- рабочая память
- база правил
- интерпретатор



В рабочая памяти хранятся символы, это все доступные системе ИИ факты и утверждения о правилах !!
База правил состоит из множества правил, проще говоря, это набор операторов IF … THEN … , где IF-чать это заглавие правила, а THEN-часть это тело правила !! От того в каком виде (т.е. какой структурой данных) представленные правила, зависит быстродействие системы !! Самой простой и легкой в реализации будет база правил основанная на массиве, но если правил очень много, то поиск, выборка нужных правил будет тормозить все систему, по этому более сложные системы можно строить, например на бинарных деревьях или других !!
Интерпретатор – это компонент RBS-системы, который управляет ее работой, взаимодействуя с ее базой правил и рабочей памятью !! Именно интерпретатор выбирает нужные правила и выполняет операции которые соответствуют этим правилам !! Существует несколько вариантов выборки правил из базы:
- выборка с прямым логическим выводом
- выборка с обратным логическим выводом
- гибридный метод выборки

Детально каждый метод я описывать не стану, а рассмотрим работу интерпретатора на основе наиболее популярного метода - выборка с прямым логическим выводом !!

Работа интерпретатора состоит из трех фаз:

- ПРОВЕРКА УСЛОВИЙ
Проверяется IF-часть правила, если в этой части несколько условий то все они должны совпадать !! Очень часто интерпретатор находит несколько правил у которых подходящие условие !! По этому нужно выбрать одно правило, которое будет выполнено, а за это отвечает вторая фаза интерпретатора.

- РАЗРЕШЕНИЕ ПРОТИВОРЕЧИЙ
Существуют такие основные варианты разрешения противоречий:
- выбрать первое попавшееся правило
- случайно выбрать правило из тех, которые подходят
- задать каждому правилу приоритет, и выбирать правило, у которого прирежет выше

- ВЫПОЛНЕНИЕ ПРАВИЛА
В этой фазе выполняется THEN-часть правила !! Это, в большинстве случаев приводит к изменению символов в рабочей памяти, или же запускает необходимую функцию !!

Эти три фазы повторяются до тех пор пока не будет найдено не единого правила которое можно выполнить !! За то после этого система будет иметь всю необходимую информацию для достаточно интересного поведения.

Выборка с обратным логическим выводом

Суть этого метода в том что вместо проверки IF-части правила, мы берем его THEN-часть и исходя из этого находим правила которые привели символ рабочей памяти в это состояние !! Вообще на практике, это более сложный метод в реализации который не имеет больших преимуществ над методом с прямым логическим выводом !! По этому, сам по себе этот метод используется редко !! Чаще используется гибридный метод, который включает в себя как прямой так обратный !!
Вот, пожалуй, со структурой системы разобрались !! Еще одним важным моментом остается принцип предоставления знаний для системы, т.е. каким образом будет строится база правил !! Здесь есть два основных направления:
- создавать базу правил в коде программы..
- загружать базу из внешних файлов

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

Все !! С теорией разобрались, а теперь перейдем к практике !! Для закрепления теоретических знаний создадим какой-то один маленький элемент игры, с использованием RBS-системы !!

[IGR]

ПРАКТИКА


ПРОГНОЗИРОВАНИЕ УДАРОВ В БОЕВОЙ СИСТЕМЕ (Fight Prediction)

Я для примера взял именно эту тему, поскольку она очень явно раскрывает принципы работы RBS-системы !! К тому же я постараюсь объяснить каждую строчку, что бы все м было все понятно !! Если же возникнут какие-то вопросы, то вы без проблем можете задавать !!

Основная идея в том что игрок, при ведении боя зачастую использует некие комбинации ударов, которые приносят максимальный урон противнику !! В данном примере мы попытаемся сделать так, что бы бот мог предсказать какой следующий удар выполнит игрок, на основании предыдущих ударов !! Если бот удачно предугадает следующий удар, он сможет эффективно поставить блок, выполнить встречный удар или уклонится !! Это добавит в игру некий степень реализма, что в свою очередь сделает игру более интересной и сложной для игрока.

Для этого, мы разработаем RBS-систему с возможностью своеобразного обучения !! Для достижения имитации обучения мы введем приоритет каждому правилу и по ходу игры будим манипулировать этими приоритетами для достижения более эффективного поведения в бою.

Так, допустим у нас есть три типа ударов: удар слева, удар п центру и удар справа !! Но даже с этими тремя типами ударов нам потребуется 27 правил что бы охватить все возможные действия и предоставить системе полную информацию !! Прежде чем переходить к правилам, сначала рассмотрим типы данных, которые мы будем использовать !!

;	Структура рабочей памяти RBS-системы
Type RBS_Memory
	Field kick_next%	; следующи удар
	Field kick_prev1%	; предшествующий предыдущему удару
	Field kick_prev2%	; предыдущий удар
End Type

;	Структура правила RBS-системы
Type RBS_Rule
	Field kick1%		; первый элементы IF-части правила
	Field kick2%		; второй элементы IF-части правила
	Field prediction%	; элемент THEN-части правила (предугаданный удар)
	Field match%		; флаг отвечающий за то, подходит ли нам это правило
	Field priority%	; приоритет правила
End Type

Так, в рабочей памяти у нас будет хранится всего три символа !! Два предыдущих удара и предположительно следующий удар !!

Структура правила тоже очень проста !! Первые два элемента – это компоненты заглавия правила, которые содержат типы ударов !! Если эти два элемента соответственно равны двум предыдущим ударам из рабочей памяти, то это одно из тех правил, что нам нужно выполнить !!
Элемент типа prediction это элемент THEN-части правила, т.е. здесь у нас будет содержатся предугаданный тип удара !!
Элемент типа match это флаг, который отвечает за то что kick1и kick2 совпадают со значениями в рабочей памяти !! Иными словами если:

rulebase(i)\kick1 = memory\kick_prev1 And rulebase(i)\kick2 = memory\kick_prev2 Then

Член класса priority это значение приоритета правила !! Оно используется для разрешения противоречий, а так же своеобразного обучения системы !! Когда у нас отмечены несколько правил, мы выбираем, то у которого больший приоритет !! Далее выполняем THEN-часть правила !! Если мы смогли предугадать удар, то мы увеличиваем приоритет данного правила, если же наоборот – мы выбрали неправильное правило, по этому мы уменьшаем его приоритет !!


Указатель на рабочую память мы будим хранить глобально !! Так же для работы памяти нужно ее первоначально инициализировать !! Для этого напишем простую функцию:

;	Функция для инициализации рабочей памяти RBS-системы
Function Init_RBS_Memory.RBS_Memory()

	m.RBS_Memory = New RBS_Memory
		m\kick_next = KICK_UNKNOWN
		m\kick_prev1 = KICK_UNKNOWN
		m\kick_prev2 = KICK_UNKNOWN
	Return m

End Function

Все глобальные переменные:

;	Глобальная переменная описывающая рабочюю память RBS-системы
Global memory.RBS_Memory
memory = Init_RBS_Memory.RBS_Memory()

Global	SysLastPredication% = KICK_UNKNOWN		; предыдущий удар прогнозированный системой (для примера)

Global	PreviousRuleFired% = 0				; правило, что выполнено в предыдущем цикле 
Global	SystemPrediction% = KICK_UNKNOWN	; прогнозируемый удар
Global	N% = 0								; количество сделанных прогнозов
Global	NSystemSuccess% = 0					; количество успешных прогнозов сделанных системой

Как мы уже говорили, у нас три типа ударов и соответственно 27 правил:

;	Типы ударов
Const	KICK_UNKNOWN% = 1001	; неизвестно
Const	KICK_CENTER% = 1002	; удар по центру
Const	KICK_LEFT% = 1003		; удар слева
Const	KICK_RIGHT% = 1004		; удар справа

;	Количество правил системы
Const	MAX_RULES% = 27

Для создания правил нам потребуется небольшая функция:

;	Функция для создания правила
Function Create_Rule.RBS_Rule (p_head1%, p_head2%, p_body%)

	r.RBS_Rule = New RBS_Rule
		r\kick1 = p_head1
		r\kick2 = p_head2
		r\prediction = p_body
		r\match = 1
		r\priority = 0
	Return r

End Function

Базу правил для простоты будим хранить в массиве !! После объявления массива правил, нужно инициализировать базу правил !! Для этого существует специальная функция !! Она очень проста в реализации, но достаточно объемная, по этому ее код я отдельно давать не буду, вы его сможете посмотреть в полном листинге к статье !!

;	Массив, который содержит базу правил RBS-системы
Dim rulebase.RBS_Rule(MAX_RULES+1)
Init_RuleBase()

Такс… инициализация системы закончена !! Далее нужно организовать работу, т.е. интерпретатор – главный функциональный элемент системы !! Он у нас будет представлен тоже одной функцией, в которой будут выполнятся все три фазы интерпретатора !!

Сначала работы программы, когда в рабочей памяти еще пока ничего нету, то первые два удара заносятся в соответствующие символы:

	; если первый символ рабочей памяти неизвестен, то им будет текущий символ
If memory\kick_prev1 = KICK_UNKNOWN Then
	memory\kick_prev1 = p_move
	; пока предсказание удара не доступно
	Return KICK_UNKNOWN
EndIf

	; если второй символ рабочей памяти неизвестен, то им будет текущий символ
If memory\kick_prev2 = KICK_UNKNOWN Then
	memory\kick_prev2 = p_move
	; пока предсказание удара не доступно
	Return KICK_UNKNOWN
EndIf

Потом, когда необходимые символы уже заполнены система совершает попытку предсказать удар !! Нам, естественно нужно проверить, удалось ли правильно предсказать удар !! Если удалось, то мы увеличиваем приоритет выполненного правила, если нет – то наоборот уменьшаем !! Также в этом случае, нужно увеличить приоритет того правила, которое мы отбросили в прошлый раз, но оно оказалось правильным !!

	; если текущий удар совпадает с предсказаным системой
If p_move = SystemPrediction Then

	; увеличиваем счетчик удачных попыток системы
	NSystemSuccess = NSystemSuccess + 1
	; увеличиваем приоритет выполненного правила в прошлый раз
	If PreviousRuleFired <> 0 Then rulebase(PreviousRuleFired)\priority = rulebase(PreviousRuleFired)\priority + 1

	; если текущий удар предсказать не удалось
Else
	; уменьшаем приоритет выполненного правила в прошлый раз
	If PreviousRuleFired <> 0 Then rulebase(PreviousRuleFired)\priority = rulebase(PreviousRuleFired)\priority - 1

	; теперь рассматриваем все правила, которые мы отбросили в прошлый раз
	For i = 1 To MAX_RULES
		; находим среди них, верное для данного удара
		If rulebase(i)\match = 1 And rulebase(i)\prediction = p_move Then
				; увеличиваем его приоритет
			rulebase(i)\priority = rulebase(i)\priority + 1
			Exit
		EndIf
	Next

EndIf

Дальше идут три фазы интерпретатора !! В первой мы отмеяаем подходящие правила:

	; теперь нужно отметить правила, которые соответствуют текущему состоянию символов рабочей памяти
For i = 1 To MAX_RULES
	; если заголовок правила соответствует символам памяти
	If rulebase(i)\kick1 = memory\kick_prev1 And rulebase(i)\kick2 = memory\kick_prev2 Then
		; отмечаем правило как подходящее
		rulebase(i)\match = 1
	Else
		; снимаем пометку
		rulebase(i)\match = 0
	EndIf
Next

Во второй – выбираем лучшее по приоритету правило:

	; теперь нужно выбрать одно правило с наибольшим приоритетом
For i = 1 To MAX_RULES
	; если правило отмеченное
	If rulebase(i)\match = 1 Then
		; если пока еще ничего не выбрали
		If RuleToExecute = 0 Then
			; то выбираем текущее правило
			RuleToExecute = i
		Else
			; сравниваем приоритеты выбраного и текущего правил
			; и выбираем то правило у которого приоритет больше
			If rulebase(i)\priority > rulebase(RuleToExecute)\priority Then RuleToExecute = i
		EndIf
	EndIf
Next

И в третей – выполняем выбранное правило, если такое существует !! В противном случае прогноза следующего удара не будет:

	; если правило найденно
If RuleToExecute <> 0 Then

	; устанавливаем прогноз удара, т.е. выполняем правило
	memory\kick_next = rulebase(RuleToExecute)\prediction
	; сохраняем номер текущего выполненного правила
	PreviousRuleFired = RuleToExecute

	; если правило не найденно
Else
	; то прогноза удара нет
	memory\kick_next = KICK_UNKNOWN
	; нет выполненного правила
	PreviousRuleFired = 0
EndIf

Вот и все!! Остальное вы можете просмотреть в полном листинге !!

Это был простой пример !! Чем дальше в лес – тем крупнее малина!! Хе-хе !! Как только появится свободное время, постараюсь рассказать о чем-то более !! Возможно это будут деревья решений, возможно планирование поведения, возможно что-то еще !!


Fight Prediction 3.zip

[tormoz]

Осталось сделать парсер текста, который бы удалял знаки "!!" и подарить аффтару.