Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.abitu.ru/en2002/closed/viewwork.html?work=179 Дата изменения: Fri May 5 15:26:14 2006 Дата индексирования: Tue Oct 2 02:34:08 2012 Кодировка: koi8-r Поисковые слова: ngc 6559

Анализ динамики боевых действий в стратегических компьютерных играх в
реальном времени.
Макаров Игорь Александрович, Суров Дмитрий Александрович
Н. Новгород, Лицей ? 87, класс 9
Развитие компьютерных технологий привело к созданию новой индустрии
развлечений, компьютерных игр. На компьютере реализованы все настольные
игры созданные человечеством за тысячелетия (шахматы, шашки, го, все
карточные игры и т.д.). Созданы целые классы новых игр, например игры типа
Quest (в играх этого вида игрок проходит сложный лабиринт, сражаясь по пути
с различными монстрами, собирая драгоценности, оружие и раскрывая секретные
клады.), появилось множество логических игр различного уровня сложности. Но
во всех играх решается один и тот же вопрос, как надо играть, чтобы
победить.
Остановимся на одном классе игр, а именно на стратегических играх. Можно
выделить два вида игр: игры с пошаговой стратегией и игры в реальном
времени.
В играх с пошаговой стратегией игрок и компьютер соблюдают очередность
ходов, к этим играм можно отнести шахматы и шашки. Заметим, что технические
возможности компьютера позволили ввести большое число различных «фигур» (в
качестве фигуры может выступать солдат, танк, кавалерист, корабль, самолет
или целое подразделение), задавать различные правила перемещения и
разнообразные игровые поля. Примером таких игр могут служить игры Panzer
General, Napoleon in Russia, Battle Ground, Age of Sail.
Другой вид стратегических игр, это игры происходящие в «реальном
времени». Лучшие игры этой группы: Dune-2, WarCraft ((, Age of Empire,
StarCraft, Crusader.
Приведем основные отличия этих игр от игр с пошаговой стратегией.
1. В стратегических играх в «реальном времени» нет четко расчерченного
игрового пространства (клетки шахматной доски или шестиугольные клетки
в Panzer General). «Фигура» может занять любое место на карте. В
лучших играх (WarCraft (() действие происходит в нескольких
измерениях на земле, в воздухе, на воде и под водой.
2. В этих играх нет очередности ходов. Компьютер последовательно
выполняет команды управления силами игрока и ходит своими «фигурами»,
а поскольку быстродействие компьютера очень высоко, то создается
впечатление непрерывности движения.
3. В этих играх нет строго заданных сил. Игрок и компьютер в процессе
игры, используют ресурсы окружающей среды, и сами создают свои
вооруженные силы.
4. При выборе своего хода компьютер использует генератор случайных чисел.
Следовательно, игру практически нельзя тождественно повторить.
5. Поскольку в игре участвует много боевых единиц, то игрок не в
состоянии одновременно управлять всеми своими войсками. В этом случае,
компьютер, берет на себя управление частью сил игрока, для которых не
поступили прямые приказы, т.е. тем самым имитируется их
самостоятельность действий. Это приводит к тому, что в бою даже свои
солдаты могут вести себя самым неожиданным образом.
Стратегические игры в «реальном времени» очень динамичны и интересны. В
процессе игры возникают ситуации, имеющие высокую степень неопределенности,
игрок не знает ни сил противника, ни его ресурсов, ни где будет нанесен
удар, ни куда он должен наступать сам. Играющий формирует свои силы,
борется за ресурсы и стремится к достижению победы, условия которой
формулируется в задании.
В пакетах игр WarCraft ((, Age of Empire, Crusader и некоторых других
имеются редакторы, которые позволяют создавать собственные сценарии. С
помощью этих редакторов можно создать любой рельеф местности и расставить
вооруженные силы в соответствии с желанием игроков.
Возможность создания игровых позиций и многократного разыгрывания одного
и того же варианта игры, позволяют применить для анализа игры
математическую теорию игр.
Теория игр ( это математическая теория, которая позволяет моделировать
конфликтные ситуации, и на основе математического анализа модели
вырабатывать рекомендации по оптимальному, «правильному» поведению игроков.
В настоящей работе приводится динамический анализ процесса развития
боевого столкновения двух боевых группировок в игре Crusader с помощью
ланчестерской модели [1].
Ланчестерские модели боя используются при описании боя многочисленных
группировок, т.е. в этом случае, когда можно использовать статистические
описание процесса. Если группы боевых средств, участвующих в бою,
достаточно многочисленны, то случайности, связанные с состоянием каждой
отдельной единицы (поражена, ( не поражена; выстрелила, ( не выстрелила),
будут мало сказываться на состоянии всей группы в целом.
Согласно закону больших чисел относительное число сохранившихся боевых
единиц с той и другой стороны будет близко к его математическому ожиданию.
Поэтому для многочисленных групп могут быть созданы сравнительно простые
методы учета противодействия, в которых можно отказаться от рассмотрения
подробностей, связанных с состоянием каждой отдельной боевой единицы.
Рассматривая динамику боя многочисленных группировок, нельзя
зафиксировать моменты отдельных выстрелов и соответственно поражения боевых
единиц. Поэтому будем полагать, что моменты выстрелов отдельных боевых
единиц будут случайными. Последовательность выстрелов во времени будем
рассматривать как некоторый поток событий.
В теории вероятности потоком событий называется последовательность
однородных событий, осуществляющихся одно за другим в какие-то случайные
моменты времени. Будем считать, что рассматриваемый поток выстрелов
является потоком без после действий (выстрелы отдельных боевых единиц не
связаны друг с другом), т.е. пуассоновским потоком.
Заметим, что последовательность выстрелов одной боевой единицы не
образуют пуассоновский поток событий, так как выстрелы разделены некоторыми
постоянными интервалами, однако, если одна и та же цель обстреливается
несколькими единицами, то суммарный поток выстрелов будет близок к
пуассоновскому потоку.
При описании боя более удобным является рассмотрение потока успешных
выстрелов, выстрелов поразивших цель. Поскольку, каждый из выстрелов
поражает цель с некоторой вероятностью [pic], то плотность потока успешных
выстрелов может быть записана в виде [pic], где [pic]( плотность потока
событий (среднее число выстрелов, приходящееся на единицу времени).
Рассмотрим простейшую модель боя. Пусть в бою участвуют две группировки.
В составе группировки ( имеется [pic]однородных боевых единиц (стрелков,
арбалетчиков и т.д.). Во второй группировке [pic]( боевых единиц,
однородных между собой, но необязательно однородных с боевыми единицами
первой группировки.
Примем следующие допущения.
1. Каждая боевая единица любой стороны, пока не поражена, производит
случайный пуассоновский поток выстрелов.
2. Каждая боевая единица первой группировки может стрелять по любой
боевой единице второй группировки и наоборот. Огонь является
прицельным. Одним выстрелом нельзя поразить более одной боевой
единицы.
3. Если боевая единица поражена, то огонь мгновенно переносится на
другую боевую единицу. Пораженная единица выбывает из боя
4. Временем полета стрелы до цели можно пренебречь по сравнению с общей
длительностью боя.
5. В любой момент времени боевая суммарная мощь каждой группировки
пропорциональна не самому случайному числу сохранившихся боевых
единиц, а его среднему значению (математическому ожиданию).
Обозначим через [pic]( среднее число боевых единиц первой группировки,
сохранившихся непораженными к моменту [pic], [pic]( среднюю
скорострельность (число выстрелов в единицу времени) для одной боевой
единицы, [pic]( вероятность с которой каждый выстрел поражает единицу
второй группировки; аналогично введем [pic], [pic], [pic]( для второй
группировки. В принятых обозначениях каждая боевая единица первой
группировки будет осуществлять пуассоновский поток успешных выстрелов
[pic], а второй группировки ( [pic].[pic]
Зафиксируем некоторый момент времени [pic] и запишем, как изменится
средняя численность сторон [pic], [pic] за малый промежуток [pic]
[pic],
Деля оба уравнения на [pic]и устремляя [pic]к нулю ([pic]), получим
систему линейных дифференциальных уравнений описывающих изменение
численности противоборствующих сторон
[pic]
Очевидно, что в начале боя ([pic]) можно положить, что
[pic], (3)
где [pic]( количество боевых единиц перед боем.
Уравнения (2) описывающие изменения численности сторон в процессе боя,
называются уравнениями динамики боя. В частности уравнения (2) называют
также уравнениями Ланчестера 2-го рода.
Если предположить, что [pic],[pic] остаются постоянными в течение боя,
то систему (2),(3) удается проинтегрировать. Выразив из первого уравнения
системы (2) [pic]и подставив его во второе уравнение, получим
[pic].
Решение этого уравнения имеет вид
[pic],
или переходя, к гиперболическим функциям и определяя константы
интегрирования, получим
[pic] (4).
Для второй группировки получим
[pic] (5).
Вид решения можно упростить, если перейти от абсолютной численности боевых
единиц к относительной
[pic].
Начальные условия в этом случае запишутся в виде
[pic].
Введем обозначения [pic]. В числителе выражения [pic] стоит среднее число
успешных выстрелов производимых в единицу времени в начальный момент
времени боевыми единицами первой группировки. Следовательно, величина
[pic]характеризует среднее число успешных выстрелов первой группировки на
боевую единицу второй группировки и называется характеристикой
интенсивности воздействия первой группировки на вторую. Аналогичный смысл
имеет величина [pic].
Решение (4,5) запишем в виде
[pic]
где
[pic]
Если коэффициент преимущества [pic], то первая группировка сильнее
второй группировки и бой закончится ее победой. Если [pic], то сильнее
вторая группировка. При [pic] решение запишется в виде [pic]. Вид решения
при различных значениях [pic] показан на рис. 1.


















Заметим, что приведенная модель справедлива при достаточно больших
значениях, [pic], т.е. если бой идет на истощение, то модель применима пока
[pic](Рис.1).
Построенная модель представляет модель высокоорганизованного боя с полной
и не запаздывающей информацией о состоянии противника и мгновенным учетом
этой информации.
Покажем возможность применения Ланчестерских моделей боя для анализа игры
в компьютерных стратегических играх в реальном времени.
Создадим простейшую позицию в игре Crusader. Возьмем две группировки
синих стрелков ([pic]) и красных ([pic]) и расположим, их друг напротив
друга, в пять шеренг. Поскольку стрелки группировок принадлежат к одному
типу, то их скорострельность, вероятность попадания и степень защищенности
равны, следовательно, коэффициент преимущества одной группировки над другой
[pic] определяется количеством стрелков.
Из системы (6) запишем
[pic]
Учитывая, что [pic], получим
[pic] (8).
Переходя к размерным значениям, определим связь между числом сохранившихся
стрелков в первой и второй группировке
[pic]. (9)
Заметим, что это соотношение справедливо для любого момента времени.
Проверим возможность определения изменения численного состава группировок
с помощью Ланчестерской модели. Начнем бой и остановим его в момент, когда
группировки еще достаточно велики. В таблице 1 приведены экспериментальные
значения количества группировок [pic]в различные моменты времени. Второе
значение [pic] определяется по формуле (9) при заданном начальном
соотношении и [pic]. Можно видеть, найденное значение [pic] близко к
экспериментальному значению.
Таблица 1.
|Эксперимент?|[pic] |[pic] |[pic] |[pic] |[pic] |
|1 | | | | | |
|[pic](экспер|175 |164 |158 |148 |145 |
|.) | | | | | |
|[pic](экспер|100 |80 |65 |45 |20 |
|.) | | | | | |
|[pic](теорет|175 |164,4 |157,7 |150,5 |145 |
|.) | | | | | |
|[pic] | |0,4 |0,3 |2,5 |0 |
|[pic] | |0,2% |0,2% |1,7% |0 |

В игре участвуют разные боевые единицы: стрелки, арбалетчики,
пехотинцы, легкие всадники, рыцари и т.д. Разработчики, по-видимому,
закладывали для них различные величины вероятности обнаружения и попадания
в цель, степень поражения и т.д.. Ланчестерская модель боя позволяет
получить интегральные количественные оценки преимущества одних боевых
единиц над другими.
Например, рассмотрим бой между группировкой арбалетчиков [pic] и
стрелков из лука [pic]. Количественные значения соотношения сторон в
различные моменты времени приведены в таблице 3. Из (8) запишем
[pic],
или, переходя к размерным переменным, получим
[pic].
Вычисленные значения коэффициента преимущества группировки могут быть
использованы для определения преимущества отдельной боевой единицы. Если
ввести обозначение [pic], то учитывая (7), получим
[pic].
Значения коэффициента [pic] приведены в таблице

|Эксперимент |[pic] |[pic] |[pic] |[pic] |[pic] |Ср.знач.|
|?2 | | | | | | |
|[pic](лучники|100 |91 |88 |57 |56 | |
|) | | | | | | |
|[pic](арбалет|50 |45 |41 |41 |37 | |
|чики) | | | | | | |
|[pic] | |5,4 |4,3 |4,8 |4.2 |4,7 |

Развиваемый в работе подход позволяет количественно оценить не только
преимущество одной боевой единицы над другой, но и оценить преимущество
одной позиции над другой.
Приведем пример таких оценок.
1. Атака с двух сторон.




|Эксперимент ?3|[pic] |[pic] |[pic] |[pic] |[pic] |Ср.знач. |
|[pic](экспер.)|100 |90 |60 |50 |40 | |
|[pic](экспер.)|100 |85 |55 |45 |25 | |
|( | |1.208 |1.043 |1.031 |1.056 |1.084 |

В данной позиции преимуществом обладает центральная группировка
2. Атака со всех сторон











|Эксперимен|[pic] |[pic] |[pic] |[pic] | |Ср.знач|
|т ?4 | | | | | |. |
|[pic](эксп|100 |70 |60 |35 |30 | |
|ер.) | | | | | | |
|[pic](эксп|100 |65 |50 |10 |5 | |
|ер.) | | | | | | |
|( | |1.064 |1.082 |1.062 |1.046 |1.063 |

Преимуществом обладает центральная группировка.
3. Бой равных сил, когда одна из сторон занимает высоту










|Эксперимен|[pic] |[pic] |[pic] |[pic] |СР.знач. |
|т ?5 | | | | | |
|[pic](эксп|100 |90 |85 |80 | |
|ер.) | | | | | |
|[pic](эксп|100 |55 |35 |20 | |
|ер.) | | | | | |
|( | |1.915 |1.778 |1.632 |1.775 |







В данной позиции явным преимуществом обладает сторона занимающая
возвышенность.

Заключение.
В работе показано, что для анализа игровых ситуаций в компьютерных
стратегических играх могут быть использованы Ланчестерские модели боя. Эти
модели позволили получить количественные оценки коэффициентов превосходства
для отдельных боевых единиц различного вида, коэффициент превосходства
обусловленный рельефом местности, защитными сооружениями, оценивать
позиционное расположение сил участвующих в бою. Полученные таким образом
оценки тактических характеристик боевых единиц и позиции могут быть
использованы при построении матричной игры решающей, вообще говоря,
стратегические задачи.
В заключение заметим, что предлагаемый подход к моделированию и анализу
боевых столкновений, может быть использован при анализе исторических
сражений и в военном деле.
Литература.
1. Вентцель Е.С. Введение в исследование операций. Изд. «Сов.радио»,
М.1964.,с.388.
2. Ляхов А.Ф. Математика и компьютерные игры. С.Петербург. РАО
Компьютерные инструменты в образовании.?1,2002,с.62-71.


Научный руководитель доцент кафедры теоретической механики механико-
математического факультета ННГУ им. Н.И. Лобачевского Ляхов Александр
Федорович


-----------------------
0

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]
[pic]

[pic]
[pic]

Рис.1


М


t

50

[pic]

50

25

25

25

25

[pic]

N2

N1