Последнее время, на форуме, демки появляются все более высокого уровня !! Радует глаз графика, приятна реалистичная физика и для этого, слава Богу, есть все необходимое, я имею ввиду сторонние библиотеки !! Но игра это не только графика и физика, еще нужен интересный сюжет и, что немаловажно, достойные противники !! Вот собственно о последних и пойдет речь !!
На форуме сравнительно мало материалов по программированию ИИ !! По этому, последнее время увлекшись немного этой темой, я решил поделится интересной информацией !! Я думаю, она будет особо полезна новичкам, хотя более опытные программисты тоже, возможно возьмут что-то для себя !!
В современных играх ИИ тоже не стоит на месте !! Постоянно появляются новые технологии, улучшаются алгоритмы… но первую статью я все-таки хотел бы посвятить чему-то более простому и несложному в понимании. Речь пойдет о RBS-системах. Сначала я сделаю небольшое теоретическое вступление, а потом поэтапно мы создадим небольшой практический пример !!
ТЕОРИЯ
Rule-Based Systems – системы основанные на правилах !! Как видно из названия, в основе такой системы ИИ лежат правила, на основе которых система выполняет действия !! Такие системы состоят из трех компонентов:
- рабочая память
- база правил
- интерпретатор
В рабочая памяти хранятся символы, это все доступные системе ИИ факты и утверждения о правилах !!
База правил состоит из множества правил, проще говоря, это набор операторов IF … THEN … , где IF-чать это заглавие правила, а THEN-часть это тело правила !! От того в каком виде (т.е. какой структурой данных) представленные правила, зависит быстродействие системы !! Самой простой и легкой в реализации будет база правил основанная на массиве, но если правил очень много, то поиск, выборка нужных правил будет тормозить все систему, по этому более сложные системы можно строить, например на бинарных деревьях или других !!
Интерпретатор – это компонент RBS-системы, который управляет ее работой, взаимодействуя с ее базой правил и рабочей памятью !! Именно интерпретатор выбирает нужные правила и выполняет операции которые соответствуют этим правилам !! Существует несколько вариантов выборки правил из базы:
- выборка с прямым логическим выводом
- выборка с обратным логическим выводом
- гибридный метод выборки
Детально каждый метод я описывать не стану, а рассмотрим работу интерпретатора на основе наиболее популярного метода - выборка с прямым логическим выводом !!
Работа интерпретатора состоит из трех фаз:
- ПРОВЕРКА УСЛОВИЙ
Проверяется IF-часть правила, если в этой части несколько условий то все они должны совпадать !! Очень часто интерпретатор находит несколько правил у которых подходящие условие !! По этому нужно выбрать одно правило, которое будет выполнено, а за это отвечает вторая фаза интерпретатора.
- РАЗРЕШЕНИЕ ПРОТИВОРЕЧИЙ
Существуют такие основные варианты разрешения противоречий:
- выбрать первое попавшееся правило
- случайно выбрать правило из тех, которые подходят
- задать каждому правилу приоритет, и выбирать правило, у которого прирежет выше
- ВЫПОЛНЕНИЕ ПРАВИЛА
В этой фазе выполняется THEN-часть правила !! Это, в большинстве случаев приводит к изменению символов в рабочей памяти, или же запускает необходимую функцию !!
Эти три фазы повторяются до тех пор пока не будет найдено не единого правила которое можно выполнить !! За то после этого система будет иметь всю необходимую информацию для достаточно интересного поведения.
Выборка с обратным логическим выводом
Суть этого метода в том что вместо проверки IF-части правила, мы берем его THEN-часть и исходя из этого находим правила которые привели символ рабочей памяти в это состояние !! Вообще на практике, это более сложный метод в реализации который не имеет больших преимуществ над методом с прямым логическим выводом !! По этому, сам по себе этот метод используется редко !! Чаще используется гибридный метод, который включает в себя как прямой так обратный !!
Вот, пожалуй, со структурой системы разобрались !! Еще одним важным моментом остается принцип предоставления знаний для системы, т.е. каким образом будет строится база правил !! Здесь есть два основных направления:
- создавать базу правил в коде программы..
- загружать базу из внешних файлов
Первый метод проще в реализации, так как не требует дополнительно создавать интерфейс между программой (игрой) и файлами в которых хранятся знания для системы, к тому же не нужно придумывать каким образом хранить эти знания (двоичный файл, картинка, строковые значения и т.д.) !!
Второй метод, хоть и сложнее но более гибкий !! Так как в этом случае организацию знаний для системы ИИ можно поручить другому программисту или вообще лучше человеку, который более продвинут в этом деле !! Например, если мы пишем базу правил для поведения животных, то зоолог или сторож зоопарка знает больше о поведении животных чем программист который пишет программу, по этому база созданная зоологом будет намного лучше, но для этого нужно написать очень удобный метод заполнения базы знаний, например XML-файл или написать простую программку где нужно будет просто заполнить необходимые поля !!
Все !! С теорией разобрались, а теперь перейдем к практике !! Для закрепления теоретических знаний создадим какой-то один маленький элемент игры, с использованием RBS-системы !!