Подход к программированию недетерминированных игр (Часть I. Описание общих эвристик)

Актуальность и цели. Рассмотрены некоторые подходы, используемые авторами при программировании интеллектуальных недетерминированных игр - те подходы, которые не были описаны в наших предыдущих публикациях. Методы алгоритмизации, разработанные и реализованные авторами, работают со специально модифицированным для недетерминированных игр деревом поиска и представляют собой дополнение (а иногда - альтернативу) нейросетевым методам. Важно отметить, что разработанные нами алгоритмы находят свое применение не только непосредственно в недетерминированных играх, но и в других задачах дискретной оптимизации. Материалы и методы. После реализации алгоритмов статической оценки позиции (выполняемых либо стандартными подходами программирования интеллектуальных игр, либо нейросетевыми методами) окончательная (динамическая) оценка позиции вычисляется по всем детерминированным оценкам, полученным для всех возможных реализаций случайного события. Эти оценки специальным образом усредняются - и результат этого усреднения рассматривается как динамическая оценка. С физической точки зрения применяемое усреднение дает положение центра тяжести одномерной системы тел, масса которых задается специальной функцией - так называемой функцией риска. Координаты тел соответствуют детерминированным оценкам, зависящим, как и в обычном методе минимакса, только от детерминированных факторов игры. Для определения последовательности обработки вершин недетерминированного дерева перебора мы строим специальные эвристические функции (функции предпочтения), на основе которых применяется сортировка в каждом из двух таких множеств вершин. Эти функции предпочтения зависят от следующих параметров: глубины текущей вершины в дереве игры; предшествующей оценки позиции; значения уже достигнутой глубины перебора. Одновременно с построением оценочной функции с помощью эксперта авторами были рассмотрены некоторые вопросы, касающиеся алгоритмов автоматизированного построения таких функций. В качестве аппроксимации статической оценки позиции использовалась трехслойная нейросеть с обратным распространением ошибки. Результаты. Результатами данной работы являются не только разработанные программы для интеллектуальных недетерминированных игр, но и описание применения рассмотренных нами «игровых» подходов в различных задачах дискретной оптимизации. Выводы. Практические результаты программ, созданных на основе рассмотренных нами алгоритмов, показывают преимущества нашего подхода к порядку обработки вершин недетерминированного дерева перебора - по сравнению с подходами, близкими к полному перебору.