Является ли этот язык достаточно общим / мощным, чтобы его можно было использовать для общего игрового ИИ?

Question

Я хочу разработать генетическую программу, которая может решать общие проблемы, такие как выживание в компьютерной игре. Так как это для развлечения / обучения, я не хочу использовать существующие библиотеки.

Мне пришла в голову следующая идея:

Входные данные представляют собой массив из N целых чисел. Генетическая программа состоит из N NST, каждая из которых получает входные данные от некоторых элементов массива и записывает свои выходные данные в один конкретный элемент массива.

AST могут быть произвольно сложными и состоять только из четырех арифметических операторов (+, -, *, /) и могут работать с константами и фиксированными элементами данного массива (без произвольного доступа).

Итак, для [N = 3] у нас есть 3 AST, например:

a[0] = {a[0] + 1}
a[1] = {a[0] + a[1]}
a[2] = {a[0] * 123 + a[1]}

N AST выполняются один за другим, и это повторяется бесконечно.

Теперь мой вопрос, достаточно ли эта система "мощная" (тьюринг завершен?) Или она не сможет решить некоторые проблемы, типичные для игрового ИИ?

Answer 1

Абстрактное синтаксическое дерево (AST) равно программному потоку, который сформулирован на предметно-ориентированном языке. Если язык состоит из возможных команд: вверх, влево, вниз, вправо, возможный AST будет: вверх, вверх, вверх, влево. Генетическое программирование пытается развить AST, то есть выяснить множество различных программных потоков для решения игры. Вместо того, чтобы только развивать AST, гораздо лучшая идея состоит в том, чтобы развивать грамматику. Это означает, что необходимо изменить язык, специфичный для предметной области, на котором сформулирован AST. Например, добавив дополнительную команду, например «gocenter». Новый язык содержит теперь 5 возможных действий: gocenter, вверх, влево, вниз, вправо, и есть возможность опробовать новые виды населения. Для систематического развития грамматики необходимо изучать грамматику путем взаимодействия. Это означает, что мы начинаем с пустой грамматики и тщательно добавляем новые возможные команды действий. В литературе это описывается как «индукция грамматики» и означает получение входного потока от человеческого взаимодействия и создание нового языка с нуля. С помощью этой грамматики возможно развитие возможных AST.

цитата: «Грамматическая эволюция (ГЭ) - это основанная на грамматике форма генетического программирование, которое определяет синтаксис возможных решений через контекстно-свободная грамматика »источник: Perez, Diego, et al. «Развивающееся поведение деревья для соревнования Mario Ai с использованием грамматической эволюции ". Европейская конференция по приложениям эволюционных вычислений. Springer, Berlin, Heidelberg, 2011.

Answer 2

С моей точки зрения, полнота по Тьюрингу не является здесь главной проблемой. При использовании генетического алгоритма для разработки какой-то стратегии, применяемой к некоторой игровой среде, одна из особенностей алгоритма, которая была бы полезна, заключается в том, что - я считаю, - что небольшое изменение в «геноме» решения приводит к достаточно небольшое изменение в поведении. Если это не так, то каждая мутация или пересечение может привести к образованию объекта, который ведет себя совершенно по-разному, и в этом виде ландшафта для генетического алгоритма может быть проблематично прийти к некоторому оптимуму - так как ландшафт функции пригодности не является достаточно непрерывным ,

Сказав, что для меня имеет смысл попытаться как-то закодировать форму дерева решений в геноме и развить это. Однако, исходя из моего опыта, генетические алгоритмы в ИИ для игр работают лучше всего, когда используются для «вычисления» оптимальных значений некоторых параметров определенного поведения, а затем для «развития» самого поведения.