Снижение размерности. Гипергаммон.
Одним из способов изучения особенностей игры является снижение размерности. Так, существует разновидность игры нарды – гипергаммон. Гипергаммон – вариант нард в котором каждый игрок имеет по три фишки и игра ведется на обычной доске. Дальнейшее упрощение – рассмотрение только одной стороны, в котором рассматривается процесс вывода фишек без взятий.
Разделение игрового процесса на фазы.
Игровой процесс в большинстве игр можно достаточно формально разделить на фазы. Для нард можно выделить следующие фазы: позиции близкие к начальной, фаза контакта (характеризуется большим числом взятий) и фаза разрыва контакта (когда единственная цель - как можно быстрее вывести свои фишки). Для каждой фазы характерна определенна стратегия, и соответственно для общего повышения качества оценки позиции, можно предварительно классифицировать оцениваемую позицию и применять разные оценочные функции.
Наиболее простой и наглядной для анализа представляется фаза разрыва контакта для которой верно следующее утверждение: перед любой из своих фишек нет фишек противника. Этот случай хорош тем, что можно рассматривать процесс вывода фишек только одним из игроков - для другого полученные результаты можно применять автоматически. Частным случаем этой фазы является стадия непосредственного вывода фишек с последних шести полей.
Для исследования этой фазы игры удобно построить полную таблицу позиций для небольшого числа фишек (пять – шесть фишек) и посчитать математическое ожидание числа ходов, необходимых для вывода всех фишек из этой позиции в случае игры наилучшим образом. В работе была построена такая таблица методом динамического программирования. Полученные результаты хорошо обобщаются и на большее число фишек.
|
|
|
Такая таблица занимает значительные объемы памяти (мегабайты) поэтому ее хранение для оценивания позиций неэффективно. Также невозможно использование таких данных для оценивания других позиций (контакта). Для этого нужно аппроксимировать эти данные некоторой функцией. В работе использовалось несколько видов функций: сумма расстояний до выхода плюс сумма квадратов расстояний, формула с частным от деления тех же самых параметров, нейронная сеть. Для настройки параметров этих функций использовался метод наименьших квадратов
Для сравнения была построена точно такая же таблица на основе эвристического алгоритма, двигающего дальнюю фишку (подробное описание этого алгоритма). После сверки каждой позиции, выяснилось, что максимально различие в числе ходов составляет не более 3%. Таким образом можно говорить, что такой алгоритм может быть применен для оценки позиции для фазы разрыва контакта практически без ущерба для качества игры по сравнению с оптимальным вариантом. Такой вариант также хорош своей простотой, легкостью реализации и нетребовательностью к аппаратным ресурсам.
|
|
|
Построение оценочных функций на основе нейронных сетей.
Теория нейронных сетей.
Искусственные нейронные сети появились в середине пятидесятых годов в качестве математической модели нервной деятельности, в том числе и деятельности головного мозга человека. Нейробиологические исследования с использованием искусственных нейронных сетей интенсивно ведутся и сегодня.
Одним из важных направлений использования нейронных сетей является аппроксимация функций. Показано, что нейронные сети с соответствующей топологией и числом узлов образуют класс универсальных аппроксиматоров, т.е. позволяет сколь угодно хорошо аппроксимировать функции.
Под искусственной нейронной сетью обычно понимают ориентированный граф - сеть состоящий из вершин - нейронов соединенных ребрами - связями. Каждый нейрон может принимать несколько, или бесконечно много, состояний, характеризующихся потенциалом нейрона - некоторым действительным числом. К нейрону подходят входные связи, по которым ему передается возбуждение от других нейронов, и выходные связи при помощи которых нейрон передает возбуждение другим нейронам. Состояние нейрона pi определяется как некоторая нелинейная функция f от суммарного возбуждения переданного ему другими нейронами: 
, где pj - потенциал возбуждающего нейрона, а cij - вес соответствующей связи.
|
|
|
Первоначально в нейронной сети входные нейроны возбуждаются подаваемым сигналом. Далее нейроны переходят в некоторые состояния в соответствии с описанным правилом. После перехода всех нейронов сети в финальное состояние с выходных нейронов снимаются потенциалы, по которым определяется результат работы сети.
В процессе тренировки нейронной сети происходит подбор весов связей, обеспечивающих наименьшую ошибку аппроксимации функции. В настоящее время известно много алгоритмов тренировки нейронных сетей, но в данном случае были употреблены генетические алгоритмы.
Типы нейронных сетей (многослойный перцептрон (MLP), сети построенные по адаптивной резонансной теории (ART), двунаправленная ассоциативная память (BAM), самоорганизующиеся карты (SOM)) различаются топологией и методом обучения. Под топологией сети понимается количеством входных и выходных нейронов, число скрытых уровней и способ связи нейронов. Считается, что в задачах аппроксимации функций наилучшие результаты достигаются при использовании многослойного перцептрона (MLP).
|
|
|
|
Дата добавления: 2018-05-02; просмотров: 357; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!