Подход к программированию недетерминированных игр (Часть II: Специальные эвристики и примеры)

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