Дипломная работа на тему: Подходы к реализации АI в логических играх

Введение

В настоящее время мобильная связь имеет широкое распространение в мире. При этом и без того немалое число пользователей мобильных телефонов продолжает расти. Сами же мобильные телефоны больше не являются просто средством связи. Благодаря поддержке сторонних приложений они получают новые возможности. Соответственно возрастает спрос на софт для мобильных телефонов. В том числе и на игры. Многие пользователи воспринимают телефон как мобильный центр развлечений, поэтому игровые возможности устройства являются для них наиболее приоритетными после его коммуникативных возможностей.

Еще несколько лет назад игровые возможности телефона полностью определялись набором игр, "вшитых" в него производителем: не существовало никакой возможности добавить новые игры. В настоящее же время большинство телефонов работающих как под управлением операционных систем (смартфоны), так и под управлением встроенного ПО (прошивки), поддерживают технологию Java. Благодаря этой технологии, совместимой с любыми приложениями созданными при помощи Java Micro Edition, появилась возможность написания любых программ для мобильных устройств, в том числе и игр.

Человеческий мозг и вычислительная техника - различные механизмы, каждый со своими собственными сильными и слабыми сторонами. Люди способны к изучению, рассуждению по аналогии, обработке изображения. Вычислительные машины же наоборот способны к большим числовым вычислениям и запоминанию больших объемов информации. Выходит, что возможности человека и компьютера дополняют друг друга: способность человека обрабатывать информацию - слабая сторона деятельности компьютера, а преимущества компьютера являются человеческими недостатками. Учитывая сложившуюся обстановку, правильным решением будет использовать преимущества машины, а не ее слабости.

Исследования в области искусственного интеллекта внесли один из самых глубоких вкладов 20-ого столетия в знания человечества. Изучений привело к пониманию, что интеллект присущий только человеку, можно воссоздать, используя вычислительную технику. Другими словами, появилась возможность построения иллюзии человеческого разума, используя компьютерную интеллектуальную систему. Эта возможность была ярко проиллюстрирована в истории компьютерных игр. Применение искусственного интеллекта в логических играх дало возможность решения трудных задач в реальном времени и с высокой эффективностью.

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

Мобильная игра - игровая программа для мобильных устройств <http://ru.wikipedia.org/w/index.php?title=%D0%9С%D0%ВЕ%D0%В1%D0%В8%D0%ВВ%D1%8С%D0%ВD%D0%ВЕ%D0%B5_%D1%83%D1%81%D1%82%D1%80%D0%ВЕ%D0%В9%D1%81%D1%82%D0%В2%D0%ВЕ&action=edit&redlink=1>, например сотовых телефонов <http://ru.wikipedia.org/wiki/%D0%А1%D0%ВЕ%D1%82%D0%ВЕ%D0%В2%D1%8В%D0%B9_%D1%82%D0%В5%D0%ВВ%D0%В5%D1%84%D0%ВЕ%D0%ВD>, смартфонов <http://ru.wikipedia.org/wiki/%D0%А1%D0%ВС%D0%В0%D1%80%D1%82%D1%84%D0%ВЕ%D0%ВD>, коммуникаторов <http://ru.wikipedia.org/wiki/%D0%9А%D0%ВЕ%D0%ВС%D0%ВС%D1%83%D0%ВD%D0%В8%D0%ВА%D0%В0%D1%82%D0%ВЕ%D1%80>, КПК <http://ru.wikipedia.org/wiki/%D0%9А%D0%В0%D1%80%D0%ВС%D0%В0%D0%ВD%D0%ВD%D1%8В%D0%B9_%D0%ВF%D0%В5%D1%80%D1%81%D0%ВЕ%D0%ВD%D0%В0%D0%ВВ%D1%8С%D0%ВD%D1%8В%D0%B9_%D0%ВА%D0%ВЕ%D0%ВС%D0%ВF%D1%8С%D1%8Е%D1%82%D0%В5%D1%80> и прочих (за исключением ноутбуков <http://ru.wikipedia.org/wiki/%D0%9D%D0%ВЕ%D1%83%D1%82%D0%В1%D1%83%D0%ВА>).

На данный момент особенно распространены мобильные игры для платформы Java Micro Edition <http://ru.wikipedia.org/wiki/Java_2_Micro_Edition>. Эту платформу поддерживают большинство современных мобильных устройств, в том числе большинство сотовых телефонов стандарта GSM, используемого в России.

Решения на машинном коде изначально ориентированы на определённую платформу <http://ru.wikipedia.org/wiki/%D0%9А%D0%ВЕ%D0%ВС%D0%ВF%D1%8С%D1%8Е%D1%82%D0%В5%D1%80%D0%ВD%D0%В0%D1%8F_%D0%ВF%D0%ВВ%D0%В0%D1%82%D1%84%D0%ВЕ%D1%80%D0%ВС%D0%В0>. Поэтому такие игры показывают самый высокий уровень производительности и используют все мультимедийные <http://ru.wikipedia.org/wiki/%D0%9С%D1%83%D0%ВВ%D1%8С%D1%82%D0%В8%D0%ВС%D0%В5%D0%В4%D0%В8%D0%В0> возможности аппарата, но недоступны для других платформ.

Исторически первая, простейшая технология написания мобильных игр - на машинном коде <http://ru.wikipedia.org/wiki/%D0%9С%D0%В0%D1%88%D0%В8%D0%ВD%D0%ВD%D1%8В%D0%B9_%D0%ВА%D0%ВЕ%D0%В4> в составе прошивки <http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%ВЕ%D1%88%D0%В8%D0%В2%D0%ВА%D0%В0> устройства. Такие игры существуют даже для дешёвых телефонов; впрочем, такие игры без исходных кодов <http://ru.wikipedia.org/wiki/%D0%98%D1%81%D1%85%D0%ВЕ%D0%В4%D0%ВD%D1%8В%D0%B9_%D0%ВА%D0%ВЕ%D0%В4> прошивки практически невозможно заменить или удалить.

В смартфонах <http://ru.wikipedia.org/wiki/%D0%А1%D0%ВС%D0%В0%D1%80%D1%82%D1%84%D0%ВЕ%D0%ВD> и карманных компьютерах применяются устанавливаемые игры на машинном коде <http://ru.wikipedia.org/wiki/%D0%9С%D0%В0%D1%88%D0%В8%D0%ВD%D0%ВD%D1%8В%D0%B9_%D0%ВА%D0%ВЕ%D0%В4> (как на обычных компьютерах), например, игры для N-Gage <http://ru.wikipedia.org/wiki/N-Gage>. Как и любая другая программа, такая игра может содержать деструктивный код <http://ru.wikipedia.org/wiki/%D0%92%D1%80%D0%В5%D0%В4%D0%ВЕ%D0%ВD%D0%ВЕ%D1%81%D0%ВD%D0%В0%D1%8F_%D0%ВF%D1%80%D0%ВЕ%D0%В3%D1%80%D0%В0%D0%ВС%D0%ВС%D0%В0>. С этим борются с помощью сертификации <http://ru.wikipedia.org/wiki/%D0%А1%D0%В5%D1%80%D1%82%D0%В8%D1%84%D0%В8%D0%ВА%D0%В0%D1%86%D0%В8%D1%8F> игр, однако не все производители или издатели могут позволить себе это, а иногда расходы на сертификацию могут стать причиной более высокой цены на игру.<http://ru.wikipedia.org/wiki/Sun_Microsystems> J2ME <http://ru.wikipedia.org/wiki/J2ME> (Java 2 Micro Edition, в просторечии Java <http://ru.wikipedia.org/wiki/Java>) - одно из самых распространённых средств для разработки игр для мобильных телефонов. Лёгкость портирования <http://ru.wikipedia.org/wiki/%D0%9F%D0%ВЕ%D1%80%D1%82%D0%В8%D1%80%D0%ВЕ%D0%В2%D0%В0%D0%ВD%D0%В8%D0%В5> позволяет выпускать одну и ту же игру на большое число различных устройств. Использование виртуальной машины <http://ru.wikipedia.org/wiki/%D0%92%D0%В8%D1%80%D1%82%D1%83%D0%В0%D0%ВВ%D1%8С%D0%ВD%D0%В0%D1%8F_%D0%ВС%D0%В0%D1%88%D0%В8%D0%ВD%D0%В0> для выполнения промежуточных кодов позволяет ограничить доступ приложения к данным телефона для повышения безопасности, однако это же зачастую приводит к снижению функциональности.

Несмотря на то, что промежуточный код предназначен для выполнения на большом количестве устройств, на разных телефонах реализации виртуальной машины и аппаратные спецификации могут отличаться. Это может привести к проблемам с совместимостью игры с различными устройствами, особенно при использовании разработчиками дополнительных библиотек. Например, различные устройства могут справляться по-разному с воспроизведением MMAPI <http://ru.wikipedia.org/wiki/MMAPI> при высоких нагрузках, а некоторые могут не работать и вовсе. Другой распространённой проблемой является различное количество доступной распределённой памяти <http://ru.wikipedia.org/wiki/%D0%94%D0%В8%D0%ВD%D0%В0%D0%ВС%D0%В8%D1%87%D0%В5%D1%81%D0%ВА%D0%B8_%D1%80%D0%В0%D1%81%D0%ВF%D1%80%D0%В5%D0%В4%D0%В5%D0%ВВ%D1%8F%D0%В5%D0%ВС%D0%В0%D1%8F_%D0%ВF%D0%В0%D0%ВС%D1%8F%D1%82%D1%8С> устройства.

Большинство логических игр построено на основе перебора игровых позиций и последующей их оценки некоторой оценочной функцией. При небольшом среднем числе доступных ходов из текущего (коэффициент ветвления игрового дерева) выгодно перебирать на большую глубину и иметь простую и быстро вычисляемую оценочную функцию. Нарды имеют большой коэффициент ветвления, что связано с необходимостью бросать игральные кости во время игры, следовательно, применение данного подхода к этой игре ограничено. Поэтому необходима качественная оценочная функция, дающая правдоподобную оценку вероятности победы игрока в данной позиции.

В данной работе рассмотрены аспекты задачи сокращения перебора при анализе сложных позиционных игр, то есть таких игр, структура выбора стратегий в которых древовидна, и дерево игры в силу своего гигантского размера не может быть построено на практике полностью. Еще более узким объектом исследований были выбраны недетерминированные игры, а в качестве конкретного примера такой игры - короткие нарды. Анализ игр со стохастическим фактором требует специальных подходов и актуален из-за возможности его применения в экономике.

Оглавление

- Введение

- Подходы к реализации АI в логических играх

- Понятие поиска

- Позиционная игра

- Подходы к решению задач выбора хода в позиционных играх

- Особенности игры нарды

- Правила игры в нарды

- Оценочная функция

- Самообучение

- Нетранзитивность игр

- Обзор литературы и существующих программ

- Игровые деревья

- Дерево игры в нарды

- Построение эвристических оценочных функций

- Выделение параметров

- Определение более сильного игрока из двух

- Настройка весовых коэффициентов

- Линейная модель из 3-х параметров. Вид поверхности

- Таблицы вероятностей

- Снижение размерности. Гипергаммон

- Разделение игрового процесса на фазы

- Построение оценочных функций на основе нейронных сетей

- Теория нейронных сетей

- Использование нейронных сетей в качестве оценочной функции

- Использование MatLab для обучения нейронных сетей

- Экспериментальные данные

- Реализация версии для мобильных устройств

- Особенности программирования портативных устройств

- Размер экрана

- Быстрый отклик

- Ввод данных

- Питание

- Память

- Файловая система

- Выбор средств разработки

- Реализация игры Заключение

- Список литературы

Заключение

В процессе работы были реализованы короткие нарды. Поскольку в нардах присутствует элемент случайности (бросаются кости, которые определяют количество ходов), алгоритмы, основанные на рекурсивном переборе позиций, не позволяют добиться хороших результатов, необходимо было разработать хорошую функцию оценки. Для решения этой задачи были построены линейные модели и использовались нейронные сети с использованием игры с собой.

Список литературы

1. Ф. Уоссермен, Нейрокомпьютерная техника: Теория и практика 1992г

2. Джонс М.Т. Программирование искусственного интеллекта в приложениях /М. Тим Джонс; Пер. с англ. - М.: ДМК Пресс 2004. - 312 с.: ил.

. Эккель Б. Философия Java: Библиотека программиста Питер, 2001г

4. G.I. Belchansky, N. V. Korobkov, "Neural network application for analysis оf satellite remote sensing data", Research оf the Earth form Space, 1998, N4, рр 111-120

. J. В. Pollack, А. D. Blair, Со-Evolution in the successful learning оf backgammon strategy.

. J. Baxter, А. Tridgell, L. Weaver, KnightCap: а chess program that learns by combining ТD with game-tree search.

. G. Tesauro. ТD-Gammon, а self-teaching backgammon program. Neural Computaion, 6: 215-219, 1994.

. J. Pollack & А. Blair "Со-Evolution in the successful learning оf backgammon strategy.

. М. Buro "Efficient approximation оf backgammon race equities".

16. Информационные ресурсы сети Интернет (http://www.bkgm.com, http://www.gnubg.org).