Разработка игры за компьютер на основе технологии java на примере игры в реверси



Скачать 28.42 Kb.
Дата26.07.2014
Размер28.42 Kb.
ТипДокументы

УДК 004(06) Информатика и процессы управления


Н.В. КОРОБКОВ, А.A. ЛУКАШОВ

Московский инженерно-физический институт (государственный университет)
РАЗРАБОТКА ИГРЫ ЗА КОМПЬЮТЕР НА ОСНОВЕ ТЕХНОЛОГИИ JAVA НА ПРИМЕРЕ ИГРЫ В РЕВЕРСИ
Рассмотрены подходы к созданию логических игр, на основе которых разработан и реализован алгоритм игры в реверси на основе технологии Java.
В настоящее время большое распространение получили вычислительные устройства с ограниченным размером памяти и вычислительными ресурсами, к которым можно отнести сотовые телефоны, КПК (компьютеры-наладонники) и игровые консоли. Большинство из этих устройств поддерживает выполнение игр и приложений разработанных на основе технологии Java. В настоящей работе рассмотрена задача создания алгоритма игры за компьютер в реверси на таких устройствах. Алгоритм и интерфейс игры был реализован в среде разработки Java на платформе J2ME.

Разработка игры за компьютер в логических играх на таких устройствах требует оптимизации по скорости и размеру используемой памяти. В ходе разработки алгоритма изучалась возможность оптимизации:



  • генерации ходов;

  • алгоритма перебора ходов;

  • вычисления оценочной функции позиции.

Наилучшие результаты при генерации ходов обеспечил алгоритм, основанный на использовании битовых полей (1). Идея данного алгоритма состоит в том, что для хранения одной ячейки поля используется не байт, а несколько бит.

Для перебора вариантов ходов рассматривались несколько вариантов рекурсивного перебора. Простейший вариант с Alpha-Beta отсечением NegaMax, NegaScout и MTD(F) (1-3). Проведенное сравнение скорости работы алгоритмов показало, что наилучшую скорость обеспечивает алгоритм MTD(F), второй NegaScout, а третий NegaMax. Однако, ускорение в алгоритме MTD(F) достигается за счет создания хэш-таблицы, требующей дополнительной памяти. Кроме того, накладываются ограничения на используемую функцию оценки качества позиции.

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

Для построения функции оценки позиции изучались три подхода:



  • классический, основанный на вычислении оценки как линейной комбинации ряда факторов (количество занятых клеток, занятые углы и края, количество возможных ходов и т.д.);

  • вероятностный, суть которого состоит в подстройке коэффициентов оценки на основе большой базы партий, сыгранных сильными игроками;

  • на основе нейронной сети, которая обучалась на большой выборке позиций.


В третьем случае использовалась нейронная сеть, имеющая топологию с одним скрытым уровнем и обратной связью (обратная связь при обучении)- трехслойный перцептрон (MLP).

Наилучшие результаты были достигнуты при втором подходе. Использование нейронных сетей оказалось не достаточно эффективным из-за большего времени вычисления функции оценки и трудностей с выбором структуры сети.



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


  1. David Eppstein, Dept. Information & Computer Science, UC Irvine Strategy and board game programming. Lecture notes for 1997

  2. Knuth D.E., Moore R.W. (1975). “An analysis of Alpha-Beta Pruning”, Artificial Intelligence, Vol. 6, Pp. 293-326

  3. Aske Plaat, Erasmus University, “Best-First Fixed-Depth Minimax Algorithms”

  4. Michael Buro 1995, “An Evaluation Function In Othello Based on Statistics”, NEC Research Institute

  5. Ф. Уоссермен “Нейрокомпьютерная техника: Теория и практика”, Перевод на русский язык, Ю. А. Зуев, В. А. Точенов, 1992.




ISBN 5-7262-0555-3. НАУЧНАЯ СЕССИЯ МИФИ-2005. Том 12

Похожие:

Разработка игры за компьютер на основе технологии java на примере игры в реверси iconВлияние компьютерных игр на психику ребёнка» Компьютер игры это третий по популярности запрос, который задается поисковому серверу Yandex ru включающий слово
«компьютер». Лично для меня является загадкой, что подразумевают под этим запросом пользователи, которые его делают, однако именно...
Разработка игры за компьютер на основе технологии java на примере игры в реверси iconТехника и тактика игры в волейбол классификация техники игры
Для последовательного изучения и анализа всего многообра­зия техники игры пользуются классификацией. Классификация— это соподчиненное...
Разработка игры за компьютер на основе технологии java на примере игры в реверси iconЛогика и игры
Важными примерами являются семантические игры, использовавшихся для определения истины, игры назад-вперед, использующиеся для сравнения...
Разработка игры за компьютер на основе технологии java на примере игры в реверси iconПрограмма для игры в отелло (реверси). На самом высоком уровне обыграть зебру почти невозможно
Новая тренировочная игра, и ходим на те квадраты где цифра горит светло голубым цветом
Разработка игры за компьютер на основе технологии java на примере игры в реверси iconЭкономические деловые игры
Из них две игры отнесены к I типу – аудиторные деловые, игры, а одна к II типу – групповые деловые игры. Проведением экономических...
Разработка игры за компьютер на основе технологии java на примере игры в реверси iconПрограмма по курсу: современные технологии программирования на языке java (по выбору) по направлению
Данный курс предполагает базовое знание языка java. Курс рассчитан на изучение не самого языка, а технологии программирования на...
Разработка игры за компьютер на основе технологии java на примере игры в реверси iconИгры, развивающие силу и выносливость Подвижные игры. Праздничные игры скакалки
Цель игры: развить физическую силу и выносливость. Необходимые материалы и наглядные пособия: скакалки
Разработка игры за компьютер на основе технологии java на примере игры в реверси iconCastlevania chronicles история
В основе этой игры для платформы PlayStation лежит оригинальная версия игры, которая в японском прокате называлась Akumajo Dracula....
Разработка игры за компьютер на основе технологии java на примере игры в реверси iconSu Краткое содержание курса. Тема Общее понятие игры. 1 Тема Биматричные игры. 4 Тема Биматричные игры в смешанных стратегия
В результате курса студент должен знать понятие, игры, стратегии, матрицы игры, доминирования, (под)игрового элемента, смешанной...
Разработка игры за компьютер на основе технологии java на примере игры в реверси iconВикторина «Олимпийские игры»
В каком году первая российская команда, в составе скольких человек, поехала на Олимпийские игры? Где проходили эти игры?
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org