Аспекты задачи сокращения перебора при анализе сложных позиционных игр - Дипломная работа

Еще несколько лет назад игровые возможности телефона полностью определялись набором игр, "вшитых" в него производителем: не существовало никакой возможности добавить новые игры. Благодаря этой технологии, совместимой с любыми приложениями созданными при помощи Java Micro Edition, появилась возможность написания любых программ для мобильных устройств, в том числе и игр. Выходит, что возможности человека и компьютера дополняют друг друга: способность человека обрабатывать информацию - слабая сторона деятельности компьютера, а преимущества компьютера являются человеческими недостатками. Поэтому такие игры показывают самый высокий уровень производительности и используют все мультимедийные возможности аппарата, но недоступны для других платформ. С этим борются с помощью сертификации игр, однако не все производители или издатели могут позволить себе это, а иногда расходы на сертификацию могут стать причиной более высокой цены на игру.Поиск - это метод решения проблемы, в котором систематически просматривается пространство состояний задачи. Отметим, что поиск является одной из фундаментальных проблем, занимающих разработчиков искусственного интеллекта. Многие ранние исследования в области поиска в пространстве состояний совершались на основе таких распространенных настольных игр, как шашки, шахматы и пятнашки. Большинство игр ведутся с использованием четко определенного набора правил: это позволяет легко строить пространство поиска и избавляет исследователя от неясности и путаницы, присущих менее структурированным проблемам. Поиск в пространстве состояний - принцип, лежащий в основе большинства исследований в области ведения игр.Поэтому в позиционной игре стратегии игроков можно понимать как функции, ставящие в соответствие каждому информационному состоянию игрока (т.е. состоянию, характеризуемому информацией игрока о положении дел в игре в данный момент) выбор некоторой возможной в этом состоянии альтернативы. Переходы игрока из одного информационного состояния в другое могут сопровождаться получением или утратой им информации об уже имевших место информационных состояниях (как самого игрока, так и других игроков) и выбиравшихся в них альтернативах. Так, если позиционная игра, с конечным числом информационных состояний есть игра с полной информацией (т.е. в любой ее момент каждый игрок знает все бывшие информационные состояния и сделанные в них выборы), то в ней имеются ситуации равновесия в чистых стратегиях, т.е. без обращения к смешанным стратегиям. При переходе к позиционной игре с бесконечным множеством информационных состояний (например, два игрока поочередно называют десятичные цифры a1, а2, a3, a4,. и если получающееся в результате число 0, a1a2a3a4. будет принадлежать некоторому множеству, то первый игрок выигрывает единицу; в противном случае единицу выигрывает второй игрок) это утверждение теряет силу, и могут наблюдаться явления парадоксального характера, математически весьма сложные.При создании программ, играющих в такие позиционные игры, как шахматы или нарды, в основном используется так называемая эвристическая схема Шеннона. Другими словами, нужен метод оценки позиции, который не требует информации о возможных вариантах развития ситуации, а использует только информацию о нынешнем расположении фигур или шашек. Такой метод должен давать некоторую численную оценку, по которой можно было бы сравнить любые две позиции и одной из них отдать преимущество, причем желательна по возможности наибольшая адекватность реальному соотношению позиций в игре.Нарды по своей природе - случайная игра (для того, чтобы совершить ход, необходимо бросить игральные кости), что отличает ее от других логических игр типа шахмат, шашек, реверси и др. Существует две вариации правил игры в нарды: длинные нарды и короткие нарды. Короткие нарды - игра для двух игроков, на доске, состоящей из двадцати четырех узких треугольников, называемых пунктами. Пункты нумеруются для каждого игрока отдельно, начиная с дома данного игрока.· Право первого хода разыгрывается броском костей - каждый из игроков бросает одну кость, первым ходит тот, у кого выпало больше очков. Если хотя бы одна из костей вылетела за доску, кости оказались в разных половинах доски, кость попала на шашку или встала неровно (прислонилась к шашке или краю доски), бросок считается недействительным и должен быть повторен. Например, если выпало 2 и 4 очка, игрок может за этот ход передвинуть одну (любую) из шашек на 2 пункта, другую - на 4 пункта, либо передвинуть одну шашку сначала на 2, затем - на 4 пункта (или, наоборот, сначала на 4 потом на 2). Каждое перемещение шашки должно делаться на полное количество очков, выпавшее на кости (если выпало 4 очка, то пойти шашкой на 1, 2 или 3 пункта нельзя - можно только на полные 4). o В варианте игры "гюльбар" если у игрока нет возможности сделать какой-либо из этих ходов, то недоигранные ходы должен сделать соперник. [4] o В варианте игры "бешеный гюльбар" при выпадении дубля игрок делает все ходы

Содержание

Введение

1. Подходы к реализации AI в логических играх

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1.3 Ввод данных

4.1.4 Питание

4.1.5 Память

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

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

4.3 Реализация игры

Заключение

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

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

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

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

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

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

Мобильная игра - игровая программа для мобильных устройств , например сотовых телефонов , смартфонов , коммуникаторов , КПК и прочих (за исключением ноутбуков ).

На данный момент особенно распространены мобильные игры для платформы Java Micro Edition . Эту платформу поддерживают большинство современных мобильных устройств, в том числе большинство сотовых телефонов стандарта GSM, используемого в России.

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

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

В смартфонах и карманных компьютерах применяются устанавливаемые игры на машинном коде (как на обычных компьютерах), например, игры для N-Gage . Как и любая другая программа, такая игра может содержать деструктивный код . С этим борются с помощью сертификации игр, однако не все производители или издатели могут позволить себе это, а иногда расходы на сертификацию могут стать причиной более высокой цены на игру.

Sun J2ME (Java 2 Micro Edition, в просторечии Java ) - одно из самых распространенных средств для разработки игр для мобильных телефонов. Легкость портирования позволяет выпускать одну и ту же игру на большое число различных устройств. Использование виртуальной машины для выполнения промежуточных кодов позволяет ограничить доступ приложения к данным телефона для повышения безопасности, однако это же зачастую приводит к снижению функциональности.

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

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

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