Создание интеллектуальной компьютерной игры «Бобры»

, класс 9, гимназия №4, Мурманск

*****@***ru

Научный руководитель , доцент, Мурманский государственный педагогический университет

Цель работы – создание компьютерной игры нового типа, в которой победа игрока даже при наличии некоторой удачи не может быть добыта только интуитивно без расчётов, а возможна лишь при применении стратегии, близкой к оптимальной. Игра создавалась с целью проверки знаний студентов Мурманского Педагогического Университета, изучающих матричные антагонистические игры. Она представляет также интерес для интеллектуально развитых людей, желающих «размять мозги».В ходе работы потребовалось освоить основы теории матричных антагонистических игр, технику проведения расчётов в пакете Maple-8, мультимедийную программу Flash, технику анимации, программирование на языке ActionScript, возможности обработки изображений в PhotoShop для оформления игры. Кроме того, потребовалось понять, как можно использовать Интернет для получения материалов, которые необходимы для оформления работы, как увидеть в деталях элементы имеющихся компьютерных игр, чтобы понять принципы создания различных эффектов. Освоена также программа перевода Lingvo как для работы с системой подсказок Help, так и для культурной, осмысленной записи на английском языке переменных в компьютерной программе. Файл для игры выполнен в формате swf, имеет объём более 3 Мбт и требует для работы стандартный Flash проигрыватель. Файл создан с помощью пакета Flash-MX. Размер fla – файла 10МБ.

НЕ нашли? Не то? Что вы ищете?

СОДЕРЖАНИЕ

1. Введение

2. Составление уравнений, описывающих задуманную игру.

3. Решение уравнений в пакете Maple-8. Расчёт вероятностей активных стратегий.

4. Программа расчёта стратегий компьютера в игре – программирование игры.

5. Сценарий игры.

6. Оформление игры.

7. Заключение

8. Литература

1. Введение

Люди начали придумывать игры с незапамятных времен. Наверное, человеку всегда было свойственно создавать виртуальные, выдуманные ситуации, которые позволяли бы ему стать участником какого-либо соревнования. Первыми играми (сначала настольными, подвижными, а потом компьютерными) были игры на скорость. В ходе такой игры надо быстрее противника выполнить некоторое действие: добраться до конечной точки путешествия, проехать по трассе с большей скоростью, чем соперник или выстрелить раньше, чем это сделает компьютерный противник. Одна из древнейших игр подобного типа – Сенет – была популярна в Египте более чем 4 000 лет назад. Затем появились игры, являющиеся имитацией военных сражений. Задача такой игры состоит в уничтожении всех (или главного) объектов противника. Таковы шашки, шахматы, компьютерные игры типа «стратегия». Считается, что первую «стратегию» придумал Герберт Уэллс. Она применялась для тренировки военачальников. Усовершенствованием военных игр стали ролевые и приключенческие игры, в которых игра сопровождалась красивым изображением. Они изменили традиционное представление об играх. Игроки ждут от них новых ярких ощущений, и производители игр стараются оправдать их ожидания. В ход идут новые компьютерные технологии: качественное изображение, фонограммы, сложный пользовательский интерфейс, трёхмерная графика. Такие игры, как «Doom», создали новый жанр – 3D-action («стрелялка») от первого лица. К середине 90-х годов практически каждая игра, в которой происходило какое-либо динамическое действие, попадала в эту категорию.

Конкурентами «стрелялок» в настоящее время являются игры-загадки, в которых главное – не впечатляющие компьютерные спецэффекты, а интересные задачи, появляющиеся по ходу сюжета и побуждающие игрока применить нестандартное мышление. Многие такие игры называются «Квест», что в переводе с английского означает вопрос. Мне очень нравятся игры студии Pilot, такие как «По следам полосатого слона». Правда, такие игры имеют общий недостаток: пройдя хотя бы раз всю игру, решив все загадки, игрок теряет к ней интерес. Это не грозит играм «традиционного» типа, в которых силой ума и интуиции меряются игроки-люди или игрок и компьютер. Только раньше в подобных играх использовались простые подручные средства: палочки, камешки, расчерченный лист бумаги, либо специально изготовленные предметы (шахматы, карты…). Сегодня возможности компьютера позволяют сделать такие игры еще более интересными.

Игры выполняют учебную роль, помогая играющему осваивать компьютер. Игровые ситуации заставляют часами размышлять над необычными проблемами, логическими задачами. Игры позволяют отдохнуть и расслабиться, хотя часть из них (те же «стрелялки») формируют жестокое отношение к окружающему миру.

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

Цель данной работы и проблема исследования заключается в разработке компьютерной игры нового типа, в которой победа игрока даже при наличии некоторой удачи не может быть добыта только интуитивно без расчётов, а возможна лишь при применении стратегии, близкой к оптимальной. Требовалось, чтобы игра была достаточно вариативной и не становилась тривиальной после первой победы, как это происходит с играми типа QWEST. Хотелось, чтобы игра была достаточно интересно и красиво оформлена и оказалась привлекательной для моих сверстников.

2. Составление уравнений, описывающих задуманную игру.

Для того, чтобы научиться эффективно обыгрывать соперника, люди придумали теорию игр. Сегодня – это раздел математики, рассматривающий многие сложные аспекты нашей жизни и применяемый для обоснования подходов, используемых в жизни и в военных действиях для обоснованного принятия решений. Я изучил лишь очень малую часть этой теории, содержащую те знания, которые понадобились мне для создания моей игры. Конкретно – теорию антагонистических игр, в которых интересы двух игроков противоположны, то есть выигрыш одного является проигрышем другого. Обычно эти игры также имеют характер борьбы, в которой выигрывает тот, у которого больше сил. Прототипом для созданной мной игры послужила игра полковника Блотто, описанная в учебнике по теории игр ([1]). В этой игре два участника имеют некоторое количество равноценных полков, которые направляются для захвата двух позиций. Каждый участник, независимо от другого, принимает решение о том, сколько сил направит на каждую позицию. После того, как оба участника приняли некоторое решение, позиция «вскрывается» и тот, у которого больше сил на позиции, получает выигрыш, равный числу полков противника плюс единицу за занятие позиции. К сожалению, при числе полков более пяти или при равных силах стратегия игры достаточно примитивна. Надо все силы направлять на одну из двух позиций случайным образом с равной вероятностью. Для победы в такой игре проще всего подбрасывать монету и при выпадении орла всеми силами идти на первую позицию, решки (решётки) – на вторую. Ситуация существенно усложняется, и, соответственно, игра становится интересней, если при вскрытии позиции выигрывает тот, у которого сил на ней меньше, однако он получает выигрыш, равный числу своих объектов плюс единицу за занятие позиции, то есть ему выгодно иметь больше полков, но меньше, чем у противника. В такой игре уже не просто разработать разумный способ действий. Это называется – разработать стратегию. Понятно, что создателю игры требуется разработать такие стратегии для всех возможных условий игры и обучить компьютер как использовать такие специально рассчитанные оптимальные стратегии. В то же время в игре с конечным числом туров игрок может обыграть компьютер, причём вероятность выигрыша резко возрастает и приближается к половине, если действия игрока близки к оптимальным. То есть в среднем можно выигрывать каждую вторую игру.

Любая игра начинается с правил. В данной игре участвуют двое – игрок, сидящий за компьютером, и сам компьютер. Каждый из них имеет в подчинении несколько объектов, число которых в настоящий момент не более семи и не менее трёх. В начале игры игрок произвольно определяет количество объектов у себя и у компьютера, а также число раундов игры (от 5 до 20). По условию, количества объектов не могут быть равными. Компьютер рассчитывает справедливую начальную сумму очков у того соперника, у которого больше объектов. Этому игроку труднее. Он в невыгодных условиях. Стартовый «капитал» определяет компьютер по цене игры, то есть по среднему выигрышу одного из участников, который получается, если оба участника играют оптимальным образом.

В разработанной мной игре такими объектами являются бобры, которые в каждом раунде игры отправляются работать на две делянки. Каждый раунд происходит так. Игрок определяет число своих бобров, отосланных им на первую делянку. Остальные следуют на вторую. Компьютер распределяет по делянкам своих бобров. В теории игр такое состояние, когда соперники определили свои стратегии на данный раунд, называется ситуацией. Затем происходит сопоставление этих количеств. Тот, у кого на данном поле бобров меньше, получает выигрыш, равный своему числу бобров плюс единицу. Сумма выигрышей в раунде называется «платёж». Прямоугольная таблица, содержащая все возможные платежи во всех возможных ситуациях, называется платёжной матрицей. Во избежание дробных чисел в начале игры, число очков определяется путём умножения выигрыша на десять. Это количество очков добавляется к имеющейся перед раундом сумме очков. Выигравшим игру в целом считается тот, у которого окончательное число очков окажется больше.

Рассмотрим пример. Пусть число бобров у игрока четыре, у противника (в игре я назвал его КОМПом) – три. Игрок имеет на выбор пять возможностей распределения бобров по делянкам. Он может послать на первую делянку четырёх бобров, трёх, двух, одного или не одного. Оставшиеся бобры обязаны пойти на вторую делянку. КОМП имеет на выбор четыре стратегии. Он может послать на первую делянку трёх бобров, двух, одного или не одного. Пусть каждый из игроков выбрал первую стратегию. Тогда на первой делянке находятся четыре бобра игрока и три бобра КОМПа. Тех бобров, которых больше, забирает некто Базай. В данной ситуации он забирает четырёх бобров игрока. Поэтому КОМП получает суммарный выигрыш 3 условные единицы, а игрок – проигрыш одну условную единицу. При записи в платёжной матрице фигурирует только «выигрыш» игрока, который в данной ситуации равен (–4) условные единицы или –40 очков. Аналогично можно рассчитать все другие ситуации. В результате возникает «платёжная матрица». Каждое число в этой матрице – это платёж, который платит противник игроку при выборе пары стратегий, соответствующих данному элементу матрицы. Рассчитаем выигрыш в общем случае. Пусть m – число бобров игрока, n – компьютера, mn = m – n. В строчке i и в столбце j на первую делянку отправилось m – i + 1 бобров игрока и n – j + 1 бобров компьютера, на вторую делянку i – 1 бобров игрока и j – 1 бобров компьютера. На первой делянке у игрока меньше бобров, чем у компьютера, если  m – i + 1 < n – j + 1 ⇔ mn < i – j, на этой делянке имеем выигрыш m – i + 1 + 1. Если m – i + 1 = n – j + 1 ⇔ mn = i – j, то количество бобров одинаковое и выигрыш равен нулю. Если m – i + 1 > n – j + 1 ⇔ mn > i – j, у компьютера бобров меньше и «выигрыш» игрока отрицателен: j – n – 1 – 1 = j – n – 2.

На второй делянке у игрока меньше бобров, чем у компьютера, если  i – 1 < j – 1  ⇔ i < j. На этой делянке имеем выигрыш i – 1 + 1 = i. Если i = j, то количество бобров одинаковое и выигрыш равен нулю. Если i > j, то у компьютера бобров меньше и «выигрыш» игрока отрицателен:  – i + 1 – 1 = – i. Складывая эти числа, получаем выигрыш на двух полях, который и определяет элементы платёжной матрицы. Эти расчёты выполняет следующая программа:

for i to m+1 do for j to n+1 do if (i>j and mn>i-j) then a[i, j]:=-n-2 fi;

if (i>j and mn=i-j) then a[i, j]:=-j fi;

if (i>j and mn<i-j) then a[i, j]:=m-i-j+2 fi;

if (i=j and mn>i-j) then a[i, j]:=-n+j-2 fi;

if (i=j and mn=i-j) then a[i, j]:=0 fi;

if (i=j and mn<i-j) then a[i, j]:=m-i+2 fi;

if (i<j and mn>i-j) then a[i, j]:=-n+j+i-2 fi;

if (i<j and mn=i-j) then a[i, j]:=i fi;

if (i<j and mn<i-j) then a[i, j]:=m+2 fi;od;od;

Платёжная матрица для игры 4 – 3 (m = 4, n = 3) приведена ниже. Первый (левый верхний) элемент матрицы соответствует рассчитанному в примере «выигрышу» игрока, равному (–4). В игре это дает КОМПу 30 очков, а очки игрока уменьшаются на 10.

Известно, что каждая антагонистическая игра имеет свою цену и решение. Цена игры – это такое число, которое равно среднему результату бесконечного количества игр, в которых оба игрока используют оптимальные стратегии. Для того, чтобы игра стала честной, одному из игроков необходимо перед началом игры выплатить сумму, равную произведению цены игры на предполагаемое количество игр. В этом случае игрок и противник находятся в равном положении. Их итоговый выигрыш определяется двумя факторами – насколько точно они способны следовать оптимальной стратегии и как им улыбнётся «госпожа Удача».

3. Решение уравнений в пакете Maple-8. Расчёт вероятностей активных стратегий.

Решением игры называется список активных стратегий с указанием вероятности их применения. Активная стратегия отличается от неактивной тем, что использование неактивной стратегии игроком приводит к уменьшению его выигрыша, а использование неактивной стратегии противником приводит к увеличению его проигрыша. Другими словами, активные стратегии – это те стратегии, которые стоит применять. Вероятность применения стратегии равна относительной частоте её использования, то есть отношению числа раз в серии игр, когда стратегия использовалась, к общему числу игр.

Для расчета цены игры и вероятностей я использовал стандартную программу пакета Maple-8, автоматически находящую минимум или максимум функции. Фрагменты программы таковы:

yy:=VectorMatrixMultiply(y, a):

ys:=minimize(y1+y2+y3+y4+y5+y6,{yy[1]>= 1,yy[2]>= 1,yy[3]>= 1,yy[4]>= 1,yy[5]>=1},NONNEGATIVE); assign(ys);su:=(y1+y2+y3+y4+y5+y6):v:=1/su-abs(maxmin): px[1]:=y1/su: px[2]:=y2/su:px[3]:=y3/su:px[4]:=y4/su: px[5]:=y5/su:px[6]:=y6/su: 

Здесь получены как цена игры V, так и вероятности рх. Рассчитанные значения цен игры и вероятностей для всех 22 реализованных мной игр приведены в таблице. Они явились исходными данными для программы на языке ActionScript, которая и является «мышлением» компьютера в данной игре.

№

Соотношение бобров

Цена игры

Стратегии первого игрока

Стратегии второго игрока

1

7:6

2

0-0-2-1-1-2-0-0

0-0-1-1-1-0-0

2

7:5

25/12

0-5-0-1-1-0-5-0

0-7-5-5-7-0

3

7:4

24/11

0-10-0-1-1-0-10-0

4-7-0-7-4

4

7:3

1.9

2-2-1-0-0-1-2-2

4-1-1-4

5

6:5

1.7

0-3-2-0-2-3-0

0-1-4-4-1-0

6

6:4

2

0-2-0-1-0-2-0

0-1-0-1-0

7

6:3

17/9

2-2-0-1-0-2-2

7-2-2-7

8

5:4

11/7

0-5-2-2-5-0

0-2-3-2-0

9

5:3

31/18

4-4-1-1-4-4

4-5-5-4

10

4:3

3/2

0-1-0-1-0

0-1-1-0

4. Создание программы расчёта стратегий компьютера в игре – программирование игры

Для программирования настоящей игры был выбран язык высокого уровня ActionScript. По имеющимся в литературе данным, именно этот язык является наиболее подходящим для создания интерактивных приложений. Современный ActionScript создан на основе языка JavaScript, который используется для разработки Web-страниц. Каждая программа представляет собой список инструкций, которые выполняются программой Flash и может быть помещена в любые места Flash-ролика. Это сценарии для кадров, кнопок, клипов. При помощи ActionScript создаваемый ролик реагирует, например, на выбор, сделанный игроком, или на другие события. Обычно к достоинствам ActionScript относят возможность быстрой разработки игр и мультимедийность. Когда я писал работу по мировой художественной литературе, я выполнил сканирование рисунка из книги непосредственно в файл Word. Когда я захотел его доработать (стереть не удовлетворяющий меня фон), этот файл не удавалось обработать никакими программами, даже такими, как PageMaker и Photoshop. При импорте он странным образом менял структуру. Однако при импорте во Flash он открылся нормально, а затем уже был экспортирован в Photoshop для дальнейшей обработки. Собственно Flash очень прост в использовании и позволяет создавать мультфильмы, видеоролики, игры. Некоторую сложность представляют временные шкалы, в которых можно запутаться, однако по мере работы в ActionScript это перестает быть проблемой. Считается, что программа Flash относительно медлительна в работе. Однако на современном компьютере с тактовой частотой около 2 ГГц такая медлительность уже не ощущается.

Созданная программа снабжена комментариями, достаточными для того, чтобы разобраться в работе основных её элементов. Любая часть программы может быть объяснена путем демонстрации их возможностей по запросу жюри.

5. Сценарий игры

Для создания интересной игры понадобилась разработка увлекательного сценария. Я решил остановиться на актуальной для страны проблеме использования природных ресурсов – лесоповале. Главными действующими лицами я сделал очень нравящихся мне трудолюбивых и красивых животных – бобров.

Игрок решает организовать лесоповал для заготовки древесины, необходимой для изготовления мебели для школ. Рубку леса он поручает симпатичным работящим бобрам, которые умеют валить лес при минимальном воздействии на окружающую природу. Его противником является американский мультимиллионер КОМП, который также пользуется дрессированными американскими бобрами, удивительно похожими на отечественных бобров, за исключением того, что их мех имеет темный, почти черный оттенок. Для выполнения работ российское государство выделило две делянки, на которых могут работать и те, и другие бобры одновременно. Леса на них много, но на беду в соседнем посёлке живет хитрый безнравственный браконьер Базай. Он охотится за бобриными шкурами, мечтая сшить из них большую одноцветную шубу, и регулярно посещает обе делянки. К счастью, он может захватить в свой большой мешок только одну группу бобров. Мех у двух групп бобров разный, поэтому Базай не берёт разных по цвету бобров. Если числа бобров равны, то Базай теряется. Бобры благополучно разбегаются по домам. Если одна

группа

бобров по численности больше, Базай выбирает именно её. Меньшая по численности группа бобров выполняет работу. Каждый бобр в этой группе приносит своему работодаочков. Таким образом, игроку выгодно, чтобы бобров в группе было как можно больше, но меньше, чем в группе бобров соперника. Бобры, захваченные Базаем, достаточно умны, и в конце концов вырываются на волю. Однако на усиленное питание ослабевших в неволе бобров, их хозяин вынужден потратить дополнительных 10 очков. Все бобры желают работать, поэтому ни один бобер не остаётся дома. В начале игры, игрок выбирает число своих бобров, число бобров КОМПа (они не могут быть равными) и количество туров – рабочих дней. Тот, у которого бобров больше, находится в менее выгодном положении и поэтому получает стартовый капитал. Выигравшим игру считается тот, у которого окончательное число очков окажется больше. Эта информация содержится во вводном мультфильме игры.

6. Оформление игры

Об оформлении игры нет большого смысла говорить – её надо просто смотреть. Специалист поймет объём работ, которые мне пришлось выполнить. Для неспециалиста это всё равно мало значащие слова. Например, для создания бобров пришлось полазить по Интернету и, на моё счастье, там оказался сайт с бобрами в любых видах от анекдотов, читать которые не было времени, до фотографий и художественных рисунков бобров. Однако эти рисунки мне не понравились, и я потратил время на стилизацию изображений. Чтобы не делать слишком много рисунков, некоторых бобров, которые появляются в редких играх (если у игрока 7 бобров) причём в конце (то есть шестого и седьмого на одной делянке), я выполнил просто в виде зеркального отражения. При создании надписей выяснилось много неприятных нюансов программы. Авторы хороших книг, которые мне нравятся, и по которым я изучал программирование, пишут надписи на английском языке. Он привычен для компьютера. А мне хотелось иметь русские надписи. Однако русские буквы исчезали с экрана, хотя исправно значились в программе. Пришлось выводить надписи разными шрифтами, благодаря чему я узнал, что единственный шрифт, который надёжно понимает Flash – это Courier New Cyr. В обычно используемом для надписей шрифте Times New Roman Cyr почти половина букв исчезает, а шрифт Courier New Cyr способен показать все малые буквы и половину больших. К сожалению, вторую половину больших букв я пока ввести в текст не могу, поэтому некоторые надписи меня не совсем устраивают в литературном смысле. Как говорили римляне: Сделал, что мог. Другие сделают лучше.

7. Заключение

Создана увлекательная компьютерная игра для проверки знаний студентов по теории игр. Она прошла отработку на группе из 32 студентов, сдававших теорию игр. Каждый студент должен был не менее, чем пять раз обыграть компьютер, и объяснить, как это удалось. В ходе апробации подтверждена надёжность созданной программы и её дееспособность. Многие студенты, имеющие компьютеры, попросили копию программы «для дома». Файл для игры выполнен в формате swf, имеет объём более 3 Мбт и требует для работы стандартный Flash проигрыватель. Файл создан с помощью пакета Flash-MX. Размер fla – файла 10МБ.

8. Литература

1. , , . Теория игр. –М.: Высш. Школа., «Университет», 1998, – 304 с.

2. . Основы теории игр.  – М.: 1984. 64 с.

3. Г. Розенцвейг. Macromedia Flash MX. Создание игр с помощью ActionScript. – М.: ДМК Пресс, 2003. – 576 с.

4. Б. Сандерс. Эффективная работа: Flash 5.  – СПб: Питер, 2002. – 352 с.

5. П. Шалин. Энциклопедия Windows XP. – СПб: Питер, 2002. – 688 с.

6. . Новейшая энциклопедия персонального компьютера 2003. – М.: ОЛМА-Пресс, 2003. – 920 с.