Главная
База знаний "Allbest"
Программирование, компьютеры и кибернетика
Аспекты задачи сокращения перебора при анализе сложных позиционных игр
Аспекты задачи сокращения перебора при анализе сложных позиционных игр
Проблема сокращения перебора при анализе сложных позиционных игр, древовидная структура выбора стратегий, в которых дерево игры в силу своего гигантского размера не может быть построено на практике полностью. Короткие нарды как конкретный пример игры.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | дипломная работа |
| Язык | русский |
| Дата добавления | 27.10.2013 |
| Размер файла | 1,6 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
pips = 1 pips = - 1
pips = 5 pips = - 5
Рис. 4. Поверхности количества побед линейной модели над эталонным игроком от величины параметров.
Из графиков видно, что все три параметра в значительной мере влияют на качество оценки позиций. Так параметр pips можно проассоциировать с близостью победы, соответственно, следует максимизировать вес этого параметра. Количество удерживаемых клеток (две и более фишек на одном поле) также значительно влияет на количество побед так как его фишки сложнее побить и соответственно, игрок, обращающий на это внимание выигрывает чаще. Количество blots игрок должен стремиться минимизировать, так как это "откатывает” его назад. Наилучшие результаты дало сочетание весов pips = 1, blots = - 8, hold = - 8.
В процессе проведения расчетов было отмечено, что чем ближе игроки по силе (близость к 0 разницы количества побед игроков) тем дольше идет партия. Также в ряде статей (например в [11]) отмечается увеличение длины партий с ростом класса игрока. Данный эффект также был отмечен и в игре в нарды.
2.5 Таблицы вероятностей
Для усиления игры программы были опробованы таблицы вероятностей. Для игры нарды можно построить два типа таких таблиц: двусторонние и односторонние. Двусторонние таблицы содержат предварительно просчитанные вероятности победы. Например для шести и менее фишек, находящихся в доме есть 924 возможных позиции, всего 924*924 = 853,776 возможных позиций для каждой из которых нужно хранить вероятность победы. Наибольшая проблема таких таблиц - экспоненциальный рост размера с увеличением числа фишек и полей. Так, для упомянутой таблицы объем занимаемой памяти можно оценить шестью мегабайтами, что выходит за рамки ограничений мобильных устройств.
Значительная экономия может быть достигнута при использовании односторонних таблиц в которых хранятся вероятности вывода всех фишек в данной позиции за n ходов - . Предположим, что для игроков A и B в текущей позиции нам известны распределения и , тогда вероятность того что игрок A выведет все свои фишки первым будет рассчитываться по формуле: . Число позиций состоящих из 15 фишек на 6 полях равно 54,264 и такая таблица будет занимать в памяти примерно 1.4 мегабайта, что гораздо ближе к ограничениям для существующих мобильных устройств.
Как оказалось, прирост качества игры от использования такой таблицы оказался незначительным, что может быть объяснено ее небольшим размером и тем, что только порядка 1-2% позиций в игре оценивается по ней.
Но можно применить похожие принципы для генерации выборки для обучения нейронной сети. Так, чтобы получить оценку вероятности выигрыша из данной позиции можно сформировать некоторый набор позиций. И для каждой из этих позиций провести по N партий, между двумя равными сильными игроками. Причем, под числом побед белых над черными можно понимать оценку данной позиции. На сгенерированной таким образом выборке можно обучить нейронную сеть и получить оценочную функцию высокого класса. Можно повторять этот процесс итеративно для улучшения качества оценки.
2.6 Снижение размерности. Гипергаммон
Одним из способов изучения особенностей игры является снижение размерности. Так, существует разновидность игры нарды - гипергаммон. Гипергаммон - вариант нард в котором каждый игрок имеет по три фишки и игра ведется на обычной доске. Дальнейшее упрощение - рассмотрение только одной стороны, в котором рассматривается процесс вывода фишек без взятий.
2.7 Разделение игрового процесса на фазы
Игровой процесс в большинстве игр можно достаточно формально разделить на фазы. Для нард можно выделить следующие фазы: позиции близкие к начальной, фаза контакта (характеризуется большим числом взятий) и фаза разрыва контакта (когда единственная цель - как можно быстрее вывести свои фишки). Для каждой фазы характерна определенна стратегия, и соответственно для общего повышения качества оценки позиции, можно предварительно классифицировать оцениваемую позицию и применять разные оценочные функции.
Наиболее простой и наглядной для анализа представляется фаза разрыва контакта для которой верно следующее утверждение: перед любой из своих фишек нет фишек противника. Этот случай хорош тем, что можно рассматривать процесс вывода фишек только одним из игроков - для другого полученные результаты можно применять автоматически. Частным случаем этой фазы является стадия непосредственного вывода фишек с последних шести полей.
Для исследования этой фазы игры удобно построить полную таблицу позиций для небольшого числа фишек (пять - шесть фишек) и посчитать математическое ожидание числа ходов, необходимых для вывода всех фишек из этой позиции в случае игры наилучшим образом. В работе была построена такая таблица методом динамического программирования. Полученные результаты хорошо обобщаются и на большее число фишек.
Такая таблица занимает значительные объемы памяти (мегабайты) поэтому ее хранение для оценивания позиций неэффективно. Также невозможно использование таких данных для оценивания других позиций (контакта). Для этого нужно аппроксимировать эти данные некоторой функцией. В работе использовалось несколько видов функций: сумма расстояний до выхода плюс сумма квадратов расстояний, формула с частным от деления тех же самых параметров, нейронная сеть. Для настройки параметров этих функций использовался метод наименьших квадратов
Для сравнения была построена точно такая же таблица на основе эвристического алгоритма, двигающего дальнюю фишку (подробное описание этого алгоритма). После сверки каждой позиции, выяснилось, что максимально различие в числе ходов составляет не более 3%. Таким образом можно говорить, что такой алгоритм может быть применен для оценки позиции для фазы разрыва контакта практически без ущерба для качества игры по сравнению с оптимальным вариантом. Такой вариант также хорош своей простотой, легкостью реализации и нетребовательностью к аппаратным ресурсам.
3. Построение оценочных функций на основе нейронных сетей
3.1 Теория нейронных сетей
Искусственные нейронные сети появились в середине пятидесятых годов в качестве математической модели нервной деятельности, в том числе и деятельности головного мозга человека. Нейробиологические исследования с использованием искусственных нейронных сетей интенсивно ведутся и сегодня.
Одним из важных направлений использования нейронных сетей является аппроксимация функций. Показано, что нейронные сети с соответствующей топологией и числом узлов образуют класс универсальных аппроксиматоров, т.е. позволяет сколь угодно хорошо аппроксимировать функции.
Под искусственной нейронной сетью обычно понимают ориентированный граф - сеть состоящий из вершин - нейронов соединенных ребрами - связями. Каждый нейрон может принимать несколько, или бесконечно много, состояний, характеризующихся потенциалом нейрона - некоторым действительным числом. К нейрону подходят входные связи, по которым ему передается возбуждение от других нейронов, и выходные связи при помощи которых нейрон передает возбуждение другим нейронам. Состояние нейрона pi определяется как некоторая нелинейная функция f от суммарного возбуждения переданного ему другими нейронами:
,
где pj - потенциал возбуждающего нейрона, а cij - вес соответствующей связи.
Первоначально в нейронной сети входные нейроны возбуждаются подаваемым сигналом. Далее нейроны переходят в некоторые состояния в соответствии с описанным правилом. После перехода всех нейронов сети в финальное состояние с выходных нейронов снимаются потенциалы, по которым определяется результат работы сети.
В процессе тренировки нейронной сети происходит подбор весов связей, обеспечивающих наименьшую ошибку аппроксимации функции. В настоящее время известно много алгоритмов тренировки нейронных сетей, но в данном случае были употреблены генетические алгоритмы.
Типы нейронных сетей (многослойный перцептрон (MLP), сети построенные по адаптивной резонансной теории (ART), двунаправленная ассоциативная память (BAM), самоорганизующиеся карты (SOM)) различаются топологией и методом обучения. Под топологией сети понимается количеством входных и выходных нейронов, число скрытых уровней и способ связи нейронов. Считается, что в задачах аппроксимации функций наилучшие результаты достигаются при использовании многослойного перцептрона (MLP).
Нейронные сети на основе многослойного перцептрона (MLP) состоят из нескольких слоев нейронов (рис.4), причем на вход нейронов каждого слоя подаются возбуждения со всех выходов нейронов предыдущего слоя. Самый младший слой (номер 0) возбуждается непосредственно вектором входного воздействия х, а с последнего слоя снимают результат - вектор у, который, в зависимости от постановки задачи, интерпретируется как результат классификации, либо как вектор оцениваемых параметров. Промежуточные слои, между первым и последним, обычно называют скрытыми.
Рис 5. Схема топологии многослойного перцептрона.
При работе многослойного перцептрона, первоначально нейроны 0ого возбуждаются входным вектором х, после чего последовательно вычисляются состояния нейронов 1ого,2 ого и наконец последнего Nого - выходного уровня.
При обучении сети необходимо определить число уровней, количество нейронов на уровнях и веса связей cij, обеспечивающие наилучшее представление зависимости выхода у от входа х.
Для правильного обучения сети важно выбрать нужное количество нейронов (определить топологию сети). В ряде работ предлагается для этого обучить несколько сетей с различной топологией и выбрать ту, где получился наилучший результат.
Генетические алгоритмы.
Генетический алгоритм (Genetic algorithm) представляет собой технику оптимизации, которая моделирует феномен естественной эволюции (впервые открытый Чарльзом Дарвином). При естественной эволюции выживают и дают самое многочисленное потомство особи, наиболее адаптированные к сложным условиям окружающей среды. Степень адаптации, в свою очередь, зависит от набора хромосом конкретной особи, полученным от родителей. Это основа выживания сильнейшего - не только процесс выживания, но и участие в формировании следующего поколения.
Решение задачи кодируются в хромосому. Отдельные гены хромосомы представляют собой уникальные переменные для изучаемой проблемы. При отборе "здоровых” хромосом из популяции и использовании генетических операторов (таких как рекомбинирование и мутация) в популяции остаются только те хромосомы, которые лучше всех приспособлены к окружающей среде, то есть наиболее полно отвечают задаче.
При рекомбинировании (Recombination) части хромосом перемещаются, может быть, даже изменяются, а получившиеся новые хромосомы возвращаются обратно в популяцию для формирования следующего поколения. Первая группа хромосом обычно называется родителями, а вторая детьми. С одинаковой вероятностью могут применяться один или несколько генетических операторов. Доступные операторы включают мутацию и перекрестное скрещивание, которые являются аналогами одноименных генетических процессов.
Оператор перекрестного скрещивания (Crossover) берет две хромосомы, разделяет их в произвольной точке (для каждой хромосомы), а затем меняет местами получившиеся "хвосты”. При этом образуется две новые хромосомы. Разделение хромосомы в одной точке (получившее название перекрестного скрещивания в одной точке) является не не единственной возможностью. Также возможно использовать разделение в нескольких точках.
Оператор мутации (Mutation) вносит произвольное изменение в гены хромосомы (иногда даже несколько изменений в зависимости от частоты применения). Он позволяет создавать в популяции новый материал.
3.2 Использование нейронных сетей в качестве оценочной функции
Для применения нейронных сетей в качестве оценочной функции нужно определить ее топологию, сформировать обучающую выборку и обучить.
Большинство авторов склоняется к использованию трехслойной нейронной сети (MLP) как наиболее удобной в данном случае, такие сети были использованы и в этой работе. Существует несколько подходов к определению числа нейронов в каждом слое. Например, входные нейроны можно понимать как позицию на доске, представленную в некотором виде (26 входов по числу полей на доске), либо уже посчитанные параметры от эвристической оценочной функции, либо совмещение этих вариантов.
В качестве данных для обучения могут быть применены: база партий признанных игроков, выборка с позициями, оцененными эвристической оценочной функцией, выборка с оценкой по числу выигранных партий одним из игроков. Каждый из этих вариантов обладает своими преимуществами и недостатками. Так, база партий признанных игроков может позволить получить хорошие оценки качества позиций, но такие базы отсутствуют в свободном доступе, либо имеют очень ограниченный объем или неопределенное происхождение. Нейронная сеть, обученная по выборке с позициями, оцененными эвристической оценочной функцией (ОФ), не может играть лучше чем исходная ОФ, но может вычисляться быстрее. Наилучших результатов можно добиться используя выборки с оценкой по числу выигранных партий одним из игроков. Для построения такой выборки проводится N партий для некоторого набора позиций (размер выборки), между двумя равными сильными игроками. Причем под числом побед белых над черными можно понимать оценку данной позиции.
3.3 Использование MatLab для обучения нейронных сетей
Для обучения нейронной сети использовался инструмент nntool программного комплекса МаtLab 7.0. Использование MatLab для обучения нейронной сети может быть объяснено повышенным удобством построения нейронных сетей с помощью инструмента nntool, возможностью визуализации построенной нейронной сети, возможностями значительных вариаций методов обучения нейронных сетей, несколькими способами инициализации весов, наглядным представлением и отсутствием необходимости разрабатывать и отлаживать код обучения НС, и тем самым сокращение сроков разработки готовой программы.
Рис. 6. Графическое представление одной из использовавшихся нейронных сетей и график ошибки обучения сети в инструменте nntool.
В рамках этого подхода была написана программа-экспортер позиций и их оценок из внутреннего представления программы в формат MatLab. Для получения данных (весов нейронной сети) обратно была написана программа-импортер, которая переводит веса обученной нейронной сети из MatLab во внутренний формат программы.
Также была реализована функциональность нейронных сетей в качестве оценочной функции (замена эвристической оценочной функции нейронной сетью производится простой заменой классов в программе).
Для настройки весов нейронных сетей использовался алгоритм обратного распространения ошибки. Суть метода состоит в измерении ошибки между вектором выходных значений нейронов и желаемым выходом, с возвращением получившейся ошибки к входному уровню с целью выбрать веса в связях минимизирующие ошибки на выходном уровне, при помощи алгоритма дельта обучения. В комбинации с этим методом также использовался стахостический метод, основанный на внесении псевдослучайных изменений в величины весов, сохраняя те изменения, которые ведут к улучшениям. Этот метод позволяет обойти такие проблемы как: локальные минимумы и паралич сети. Брать наиболее сильные эвристические функции, для получения правдоподобных оценок вероятности победы позиций, для работы с большими, генерируется некоторое число позиций (в работе использовались выборки размером 10 тыс.
3.4 Экспериментальные данные
Позиции для обучающей выборки брались из партий двух сильных эвристических алгоритмов. Это позволяет получить репрезентативную выборку, в отличие от метода случайной генерации позиций.
В качестве входов нейронной сети использовались количество фишек на каждом поле (28 параметров) или параметры эвристической оценочной функции (8-10 параметров). Из общих тенденций следует отметить, что время обучения сети с более формализованными параметрами меньше, а качество игры выше, что достигается предварительным просчетом параметров. Подход, использующий параметры эвристической оценочной функции, позволяет достичь лучших результатов, но требует больших вычислительных ресурсов, что не всегда оправданно, особенно для портативных устройств.
Было опробовано несколько методик обучения нейронных сетей (например, уже настроенная эвристическая функция для прямой оценки позиций в выборке) и несколько топологий (число нейронов в каждом слое, наличие нейронных смещений).
Наилучшие же результаты показал метод формирования обучающей выборки, основанный на вычислении оценки по числу выигранных партий одним из игроков. Так, для получения обучающей выборки генерируется некоторое число позиций (в работе использовались выборки размером не более 10 тыс. позиций, для работы с большими выборками инструменту nntool не хватает оперативной памяти). Для оценки каждой из этих позиций проводится турнир из N партий между двумя равными игроками, причем текущая позиция берется начальной для каждой партии. Причем, под числом побед белых над черными можно понимать оценку данной позиции. Число N в работе бралось не больше 10 тыс. партий (из-за большой вычислительной сложности задачи). В качестве игроков следует брать наиболее сильные эвристические функции, для получения правдоподобных оценок вероятности победы из данной партии. Далее на полученной выборке обучается трехслойная нейронная сеть и используется в программе в качестве оценочной функции.
В качестве сети использовалась трехслойная нейронная сеть с 28 нейронами во входном слое. В скрытом слое использовалось различное число нейронов (1, 2, 5, 10, 20), но наилучший результат дала сеть с двумя нейронами, что объясняется недостаточным объемом выборки и недостаточной точностью оценок. Построенная нейронная сеть выигрывает около 55% партий у наилучшей эвристической оценочной функции.
Для дальнейшего увеличения качества игры с применением нейронных сетей, планируется увеличить объем обучающей выборки и точность оценок, играя больше партий и используя более сложные ОФ. Увеличение выборок повлечет за собой отказ от инструмента nntool и написание собственной функции обучения сети, менее универсальной и менее требовательной к ресурсам. Также предполагается построить несколько сетей, отвечающие за разные стадии игры (отсутствие контакта фишек, вывод с доски). Также предполагается построение итеративного процесса, в котором обученная сеть используется для формирования следующей выборки, что должно позволить повысить качество игры.
4. Реализация версии для мобильных устройств
4.1 Особенности программирования портативных устройств
В настоящее время все большую популярность приобретают различного вида мобильные и портативные устройства, включая сотовые телефоны и коммуникаторы, карманные персональные компьютеры (КПК) и системы навигации. Хотя все они содержат в себе в том или ином виде универсальное вычислительное устройство, архитектура их может существенно отличаться от архитектуры персональных компьютеров (ПК).
Рассмотрим основные особенности программирования, оборудования и пользовательского интерфейса портативных устройств.
4.1.1 Размер экрана
Для портативных устройств существенной характеристикой являются физические размеры и разрешение экрана. Из соображений эргономики физические размеры экрана ограничены диагональю 3,5-4 дюйма, а типичное разрешение составляет 160х160, 320х240 или 320х320 пикселей. Для сотовых телефонов эти величины еще меньше и составляют порядка 1-2 дюймов и 128х128, 176х220 соответственно.
Такие ограничения естественным образом сказываются на проектировании пользовательского интерфейса, который приобретает другие свойства и приоритеты. Необходимо обеспечивать баланс между информационной насыщенностью и уровнем заполнения экрана, но при этом в большинстве случаев разрешение экрана может зависеть от конкретной модели и не известно заранее.
4.1.2 Быстрый отклик
На ПК пользователи, как правило, работают с приложением достаточно длительный период времени и время отклика, составляющее несколько секунд, является приемлемым. На мобильных устройствах, таких как сотовые телефоны, приложение может использоваться 15-20 раз по несколько минут в течение дня. Таким образом, скорость приложений становится критическим приоритетом при разработке.
При этом существенное влияние на общую эффективность оказывает не только скорость выполнения кода, но и удобство взаимодействия пользователя с интерфейсом приложения.
Для увеличения производительности следует минимизировать количество перемещений между окнами, обрабатываемых диалогов и т.п. Раскладка экрана приложения должна быть настолько простой, чтобы пользователь выполнил свою задачу за минимальное время. Очень полезно разработать пользовательский интерфейс в соответствии с интерфейсом других приложений.
4.1.3 Ввод данных
Портативные устройства в силу своих габаритов не могут обеспечить пользователя полноразмерными устройствами ввода - клавиатурой и мышью. Как правило устройство оснащается упрощенной или виртуальной клавиатурой и/или сенсорным экраном.
Учитывая, что эти средства не обеспечивают достаточного удобства, следует минимизировать объем вводимой пользователем информации.
4.1.4 Питание
Портативные устройства обеспечиваются, как правило, источником энергии существенно ограниченной емкости. Соответственно, ресурсоемкие задачи, требующие большого объема вычислений, следует по возможности выносить для решения сопутствующим ПО на стационарных ПК.
4.1.5 Память
Портативные устройства являются ограниченными по объему доступной памяти, как для времени исполнения, так и для хранения данных. Типичное значение доступной памяти для мобильных телефонов составляет от 128 Кб до 2 Мб. Некоторые устройства поддерживают дополнительные карты памяти объемом 32-512 Мб, но только для хранения приложений и данных.
По этой причине существенной является оптимизация применяемых алгоритмов и программ по следующим приоритетным направлениям (в порядке убывания важности):
объем памяти, используемой при работе
скорость
объем кода
4.1.6 Файловая система
По причине ограниченного объема памяти для хранения данных портативные устройства редко используют традиционные файловые системы.
Типичные свойства, обеспечиваемые ОС - доступ и установка атрибутов отдельных записей, на не всех файлов для обеспечения частичной синхронизации и работы с записями по месту, без предварительной загрузки и последующей записи.
4.2 Выбор средств разработки
Программа написана на языке Java с использованием технологии Java Micro Edition. Язык Java - это объектно-ориентированный язык программирования и программа разбита на части, называемые классами (или объектами). Каждый класс описан в отдельном файле и компилируется также в отдельный файл. Возможности объектно-ориентированного программирования максимально использовались для того, чтобы отделить код интерфейса от кода алгоритма, между которыми в сущности мало общего. Это позволяет с легкостью модифицировать как интерфейс, так и алгоритм не затрагивая другие части программы.
Рассмотрим вкратце архитектуру платформы Java 2 Platform, Micro Edition (J2ME), которая использовалась при написании программы.
Для того, чтобы поддержать гибкость и настраиваемость размещения, требуемые семейством ограниченных по ресурсам устройств, таких как сотовые телефоны, архитектура J2ME спроектирована модульной и масштабируемой. Эта модульность и масштабируемость определяется технологией J2ME в завершенной прикладной модели времени исполнения, имеющей четыре программных уровня, строящихся над операционной системой устройства.
На рисунке ниже показана схема архитектуры J2ME.
Уровень Java Virtual Machine (JVM). Этот уровень представляет собой реализацию виртуальной машины Java, которая адаптирована под операционную систему конкретного устройства и поддерживает конкретную конфигурацию J2ME.
Уровень конфигурации. Уровень конфигурации определяет минимальный набор функций JVM и библиотек классов Java, доступных для определенной категории устройств. В некоторой степени конфигурация определяет общие свойства и особенности платформы Java и библиотек, которые в предположении разработчиков должны быть доступны для всех устройств, принадлежащих конкретной категории. Этот уровень менее видим для пользователей, но является очень важным для разработчиков профилей.
Уровень профиля. Уровень профиля определяет минимальный набор API (интерфейс программирования приложений), доступный для конкретного семейства устройств. Профили создаются для конкретной конфигурации. Приложения создаются для конкретного профиля и являются, таким образом, переносимыми на любое устройство, поддерживающее этот профиль. Устройство может поддерживать несколько профилей. Этот уровень является наиболее видимым для пользователей и поставщиков приложений.
Уровень MIDP. Уровень Mobile Information Device Profile (MIDP) представляет собой набор Java API, предназначенный для решения таких вопросов как пользовательский интерфейс, постоянное хранение и сетевые функции.
Разработка игры нарды для мобильных телефонов проводилась с применением Java 2 Micro Edition Wireless Toolkit 2.2 (J2ME WTK 2.2).
Фазы разработки приложений с помощью Wireless Toolkit можно представить в виде диаграмм:
Схема 1 Фазы разработки приложений с помощью Wireless Toolkit
Достоинства и недостатки JAVA:
1. Независимость от архитектуры ЭВМ
Самое большое преимущество Java - его "нейтральность" по отношению к любой архитектуре. Программа, полностью написанная на Java, будет исполняться везде, где есть Виртуальная Java-машина, JVM (Java Virtual Machine).
2. Безопасность
В популярной литературе наших дней, особенно если речь заходит об Internet, стало модной темой обсуждение вопросов безопасности. Один из ключевых принципов разработки языка Java заключался в обеспечении защиты от несанкционированного доступа.
3. Надежность
Java ограничивает вас в нескольких ключевых областях и таким образом способствует обнаружению ошибок на ранних стадиях разработки программы. В то же время в ней отсутствуют многие источники ошибок, свойственных другим языкам программирования (строгая типизация, например). Большинство используемых сегодня программ "отказывают” в одной из двух ситуаций: при выделении памяти, либо при возникновении исключительных ситуаций.
4. Объектная ориентированность
Поскольку при разработке языка отсутствовала тяжелая наследственность, для реализации объектов был избран удобный прагматичный подход. Объектная модель в Java проста и легко расширяется, в то же время, ради повышения производительности, числа и другие простые типы данных Java не являются объектами.
5. Простота и мощь
После освоения основных понятий объектно-ориентированного программирования вы быстро научитесь программировать на Java. В наши дни существует много систем программирования, гордящихся тем, что в них одной и той же цели можно достичь десятком различных способов.
6. Богатая объектная среда
Среда Java - это нечто гораздо большее, чем просто язык программирования. В нее встроен набор ключевых классов, содержащих основные абстракции реального мира, с которым придется иметь дело вашим программам. Основой популярности Java являются встроенные классы-абстракции, сделавшие его языком, действительно независимым от платформы.
7. Производительность и предсказуемость
Язык Java довольно медленный - в 40 раз медленнее C++. Java - язык медленный, потому что это интерпретатор, потому что он является объектно-ориентированным и потому что это язык с повышенным обеспечением безопасности. Его производительность предсказать трудно, поскольку в нём используется чистка памяти ("сборка мусора”).
8. Размер кода
В целом Java-система очень велика. Создаваемый код довольно велик - Windows-станции для хорошей работы должны иметь хотя бы 20 Мб памяти. Размер программы можно уменьшить, используя динамическую компоновку и подключение классов только в необходимый момент.
9. Требования к памяти
Требования к памяти очень тесно связаны с процессом "сборки мусора”. Java нужно очень много дополнительной памяти, чтобы чистка памяти не происходила в неподходящий момент.
4.3 Реализация игры
Итогом работы стала игровая программа нарды для мобильных устройств с поддержкой технологии Java. Игра обладает богатой графикой и набором особенностей, позволяющих выделить именно эту реализацию среди подобных игр конкурентов. К этим особенностям можно отнести возможности игры с историческими личностями, имеющими собственные стили игры, игры в турнирах, ведение рейтингов. Скриншоты из игры представлены на рисунке 3.
Для управления игрой используются переменные: private byte gameState, private int currentColor, private int moveNumber.
moveNumber - это номер хода. currentColor - цвет игрока, выполняющего ход (чёрный или белый). gameState может принимать значения:
byte GAMEOVER=1; // игра кончена
byte INPLAYERMOVE=3; // приложение ожидает выполнения хода игрока
byte INCOMPUTERMOVE=4; // приложение ожидает выполнения хода компьютера
byte MOVECOMPLETED=5; // ход выполнен
Переменная gameState используется для управления событиями и определения, какие процессы имеют место в данный момент. К примеру, если пользователь хочет поставить фишку, он может это сделать только если сейчас его очередь.
Теперь представляю вашему вниманию структурную схему игры:
Схема 2. Структурная схема игры.
Функция StartTurn () вызывается в начале игры и после выполненного хода любым из игроков. Она отвечает за определение игровой ситуации и подготовку следующего хода.
Прежде всего она проверяет, имеет ли текущий игрок хоть одну клетку для хода. Если нет, она переключает ход на другого игрока и проверяет, имеет ли другой игрок клетки для хода. Когда ни один игрок не может делать ход, значит, игра окончена.
В противном случае, функция организует выполнение хода для текущего игрока. Если текущий игрок - пользователь, всё очень просто далее вызывается MakePlayerMove (), которая выполняет некоторые служебные оерации и вызывает MakeMove () для выполнения хода.
Если текущий игрок - компьютер, вызывается функция CalculateComputerMove () для вычисления лучшего хода. Затем вызывается MakeComputerMove () и MakeMove (). MakeMove () обновляет класс Board и помещает новую фишку в нужную клетку.
Далее вызывается функция EndMove (), которая переключает текущего игрока и вновь вызывает StartTurn ().
Функция CalculateComputerMove () содержит 6 вспомогательных функций:
Первая функция генерирует все возможные ходы (с текущим положением кубиков) и осуществляет выборку наиболее вероятных ходов.
Вторая функция осуществляет подсчёт пипсов. Количество пипсов - это число, которое нужно выбросить на игральных костях, чтобы вывести все свои фишки. По этому параметру определяют лидерство и близость победы.
Третья функция максимизации числа полей с двумя и более фишками. Число полей с двумя и более фишками является противоположностью предыдущему параметру, его стремятся максимизировать. Чем больше таких полей, тем устойчивее позиция и тем сложнее через нее пройти.
Четвертая функция рассчитывает возможность блокад - несколько смежных полей, занятых двойными или более фишками. С этим параметром можно связать изменение стратегии - нужно проводить свои фишки вперед, если их запирают.
Пятая функция анализирует число прямых возможностей взятий - это число одинарных фишек на расстоянии 6 или меньше полей. Есть схожий с этим параметр - число одинарных фишек на расстоянии меньшем 12. Схожим параметром является вероятность взятия одинарной фишки, которая в большинстве случаев рассчитывается по предварительно посчитанной таблице.
Шестая анализирует выгодную позицию. Анализируя сыгранные партии можно заметить, что занятие определенных позиций на доске способствует победе. Такими позициями является 4-я и 5-я клетки и соответственно 20-я и 21-я симметричные клетки. Таким образом, в простейшем случае можно ввести факт занятия этих клеток в оценочную функцию. В более общем случае, вводят весовые коэффициенты для всех полей доски.
Рис. 6. Скриншоты игры.
Таблица 1. Используемые классы.
|
Наименование класса |
Назначение класса |
|
|
App |
Унаследован от класса Midlet. В нём создаются экземпляры имеющихся классов, а также находится точка входа в программу. Класс отвечает за запуск приложения и выход из него, а так же на всевозможные внешние реакции, например звонок. |
|
|
Board |
Данный класс представляет доску. Класс использует двумерный массив, который отвечает за содержимое каждой клетки доски. Также этот класс содержит количество фишек каждого игрока. |
|
|
MyCanvas |
Унаследован от класса Canvas. В нем находится код, отвечающий за управление процессом создания интерфейса пользователя, объявления набора данных необходимых для работы всего приложения. В этом классе содержатся объекты и методы, отвечающие за интерфейс, такие как меню, функция прорисовки доски, реакция на нажатия клавиш. В классе содержится оценочная функция, а так же алгоритм нахождения лучшего хода |
Разработанная версия игры в короткие нарды основана на линейной модели. Выбор в пользу линейной модели а не НС был сделан в виду незначительного превосходства в качестве оценки позиций последней, но значительно возросшем количестве вычислений, что критично для мобильных устройств.
Заключение
В процессе работы были реализованы короткие нарды. Поскольку в нардах присутствует элемент случайности (бросаются кости, которые определяют количество ходов), алгоритмы, основанные на рекурсивном переборе позиций, не позволяют добиться хороших результатов, необходимо было разработать хорошую функцию оценки. Для решения этой задачи были построены линейные модели и использовались нейронные сети с использованием игры с собой.
Для построения оценочной функции с использованием нейронных сетей, использовалось несколько подходов. Так, в одном из самых перспективных подходов для получения оценки вероятности выигрыша из данной позиции формировался некоторый набор позиций. И для каждой из этих позиций проводилось по N партий, между двумя равными сильными игроками. Причем, под числом побед белых над черными можно понимать оценку данной позиции. На сгенерированной таким образом выборке обучалась нейронная сеть и полученная сеть использовалась как оценочная функция. Можно повторять этот процесс итеративно для улучшения качества оценки.
К настоящему моменту был реализован прототип программы, обладающий значительной частью функциональности и реализующий алгоритм игры.
Список литературы
1. Ф. Уоссермен, Нейрокомпьютерная техника: Теория и практика 1992г
2. Джонс М.Т. Программирование искусственного интеллекта в приложениях /М. Тим Джонс; Пер. с англ. - М.: ДМК Пресс 2004. - 312 с.: ил.
3. Эккель Б. Философия Java: Библиотека программиста Питер, 2001г
4. G.I. Belchansky, N. V. Korobkov, "Neural network application for analysis of satellite remote sensing data”, Research of the Earth form Space, 1998, N4, pp 111-120
5. Imran Ghory, Reinforcement learning in board games. 2004.
6. J. B. Pollack, A. D. Blair, Co-Evolution in the successful learning of backgammon strategy.
7. W. Duch, R. Adamczak, Statistical methods for construction of neural networks.
8. D. Stoutamire, Machine learning, game play, and Go.
9. W. S. Sarle, Neural networks and statistical models, 1994.
10. A. Shapiro, G. Fuchs, R. Levinson, Learning a game strategy using pattern-weights and self-play.
11. J. Baxter, A. Tridgell, L. Weaver, KnightCap: a chess program that learns by combining TD with game-tree search.
12. A. Junghanns, J. Shaeffer, Search versus knowledge in game-playing programs revisted.
13. G. Tesauro. TD-Gammon, a self-teaching backgammon program. Neural Computaion, 6: 215-219, 1994.
14. J. Pollack & A. Blair "Co-Evolution in the successful learning of backgammon strategy.
15. M. Buro "Efficient approximation of backgammon race equities”.
16. Информационные ресурсы сети Интернет (http://www.bkgm.com, http://www.gnubg.org).
Размещено на Allbest.ru
Подобные документы
Разработка на основе игры "Точки" подхода к программированию "искусственного интеллекта" в позиционных играх и возможность применения данного подхода для решения задач в области экономики, управления и других областях науки. Модель игровой ситуации.
дипломная работа [1,5 M], добавлен 21.07.2013Исследование асимптотической временной сложности решения шахматной задачи; разработка наиболее эффективных алгоритмов и структуры данных; аналитическая и экспериментальная оценка методов сокращения перебора в комбинаторных задачах; программная реализация.
курсовая работа [36,6 K], добавлен 25.06.2013Концептуальная модель операции. Математическая постановка задачи. Описание метода ветвей и границ, прямого перебора. Проектирование сценария диалога. Описание структур данных. Ручная реализация решения задачи с помощью алгоритма Литла и перебора.
курсовая работа [202,6 K], добавлен 14.12.2013Выбор программных средств для реализации игры "Угадай число". Разработка функционально-структурной схемы для написания текста программы. Изучение сути вариации алгоритма полного перебора с определённой эвристикой. Варианты компьютерной реализации игры.
контрольная работа [337,3 K], добавлен 19.06.2012Исследование основ математической теории игр. Изучение особенностей бесконечных, антагонистических, позиционных и кооперативных игр. Обоснование программных средств реализации логической игры. Описание интерфейса программы и результатов тестирования.
курсовая работа [341,5 K], добавлен 06.01.2015Исследование систем методами случайного поиска. Изучение сущности метода половинного деления. Сравнительный анализ прямого перебора и половинного деления. Ручной счет. Шаги исследования. Описание окна работающей программы. Блок-схема и код программы.
курсовая работа [257,5 K], добавлен 06.05.2014Реализация программы для решения матричных игр. Задание матрицы игры вручную и случайным образом, нахождение оптимальных стратегий игроков итерационным и методом чистых стратегий. Проектирование и листинг программного кода, сохранение матрицы игры.
контрольная работа [716,7 K], добавлен 11.06.2011Разработка компьютерной игры "Эволюция" с помощью игрового движка Unit. Сравнение критериев игры-аналога и разрабатываемой игры. Разработка графического интерфейса пользователя. Настройки камеры в редакторе Unity. Структура файла сохранения игры.
дипломная работа [3,6 M], добавлен 11.02.2017Многоблочный метод решения сложных задач. Программирование параллельных ЭВМ. Алгоритм сокращения критического пути (CPR). Упаковка в контейнеры. Алгоритмы EVAH. Общая архитектура разработанного средства. Первоначальные предложения по отображению.
дипломная работа [611,5 K], добавлен 15.10.2010Редакторы для растровой графики. Программы для работы с векторной графикой. Возможности фракталов в художественной графике, при описании свойств сложных природных объектов (турбулентных потоков), финансовом анализе и в других прикладных дисциплинах.
лекция [785,4 K], добавлен 28.08.2013
