--- from Splain

 

Поговорим о прострелах.

 

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

 

Для начала немного теории.

 

  1. О вычислениях в баттлимитаторе.

 

Теорема Бернулли. Если x - число успехов в n испытаниях Бернулли с вероятностью p успеха в одном испытании, то для любого e > 0 справедливо

.

Это означает, что с ростом числа испытаний n относительная частота успехов x /n приближается к вероятности p успеха в одном испытании.

Определим, сколько нужно произвести испытаний, чтобы с вероятностью, больше или равной b, отклонение относительной частоты успехов x /n от вероятности p было меньше e . Т.е. найдем n, для которого выполняется неравенство

.

Доказано, что для числа n, которое обеспечивает выполнение этого неравенства, справедливо

,

где xb - решение уравнения .

Следует обратить особое внимание на замечательный факт - искомое значение n не зависит от p!

 

Вычислим, сколько имитаций нужно произвести, чтобы с вероятностью 0,9 точность вычислений была 0,01.

 

Найдем значение n для которого выполняется неравенство

 

Здесь b = 0.9, e = 0.01

 

 

 

Искомое значение n находим из неравенства

 

Здесь xb - квантиль уровня (1+ b)/2 стандартного нормального распределения,

т.е. решение уравнения 

qnorm(p,0,1) - квантиль уровня p стандартного нормального распределения, или, что то же самое, значение в точке p функции, обратной к функции распределения стандартного нормального закона.

 

 

 

 

Искомое значение значение n равно 6764.

 

Именно это значение мы и будем использовать в дальнейшем при расчете имитаций битв.

 

Небольшую дискуссию по этому поводу можно прочитать например здесь: http://bbs.pbem.ru/?read=16651

 

Но вернемся к нашим мифам.

 

Миф 1. Рандом на МСК – сервере обладает особенностями, благодаря которым часто бывают прострелы.

 

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

 

Тем не менее некоторые особенности реализации конечно могут быть.

 

Сначала комментарии самих ГМ:

 

Автор: Roman A.Makhnenko <gvng@mail.ru>
Дата: Вторник, 26 Августа 2003, 11:10

В ответ на: Re: ГМ-а на мыло!!! Даешь настоящий RANDOM!!! (KAPJICOH)

Если Антон ничего не менял в ядре, то рандомы _АБСОЛЮТНО_ идентичны, что на Первом Московском, что на DG (да заодно и в GVNG, и, насколько мне известно, в GComm'е тоже). Так что... Не... В школу, в школу!

Однако ГМ МСК Антон Круглов говорил, что в его сервере используется самый настоящий и самый справедливый хардварный эмулятор. Несмотря на такие разногласия в показаниях, можно утверждать, что функция получения случайного числа в серверах реализована вполне адекватно и нареканий не вызывает.

 

Попробуем проэмулировать процесс битвы.

 

Возьмем стандартный эмулятор battle.c и два флота в стандартной конфигурации:

 

;A W [:TW] S [:TS] M [#]

; first fleet

 87 1.7 24.2 198 1

 1  29  20.5 99  1

 0  0   1    2   150

 

; second fleet

 87 1.7 24.2 198 1

 1  29  20.5 99  1

 0  0   1    2   150

 

Естественно, вероятность выигрыша каждого из них ½:

 

 87      1.7   12.9013     198.00          1 : 0.395     

  1       29   13.7694      99.00          1 : 0.500     

  0        0   2.46621       2.00        150 : 4.423     

   * * *  

 87      1.7   12.9013     198.00          1 : 0.393     

  1       29   13.7694      99.00          1 : 0.500     

  0        0   2.46621       2.00        150 : 4.358     

   * * *  

 Cycles:  7.03  7.19         Average: 7.11   

   6764:  50.0  50.0         M_killed:  460.52/597.00   460.95/597.00 

 

Теперь посмотрим, как можно использовать результаты процедуры получения случайного числа в движке вычисления результатов битвы. Пусть у нас есть функция rand(), возвращающая случайное число в диапазоне от 0 до RAND_MAX.

 

1.

int myrandom(int l) { return (int)(rand()/(float)RAND_MAX * (l-0.5)); }

 

2.

int myrandom(int l) { return (int)(rand()/(float)RAND_MAX * (l-1)); }

 

соответственно меняем строки:

 

...

  while(fires==0 || arm==0) {

     ll=myrandom(l);

     for(j=0;j<ship_no;++j)

      if ((ll-=ships[j].can_kill)<0) goto brk1;

...

    {int ii,jj, tar_cnt=act_total-act[i]; ship* tar;

     if (tar_cnt<=0) {arm=1/* to be last shot */;goto __retry;}

     ll=myrandom(tar_cnt);

...

 

Меняем входной файл и проводим имитации:

 

;A W [:TW] S [:TS] M [#]

; first fleet

 1  29  20.5 99  1

 0  0   1    2   150

 87 1.7 24.2 198 1

 

 

; second fleet

 87 1.7 24.2 198 1

 1  29  20.5 99  1

 0  0   1    2   150

 

И получаем для случая 1.

 

29   13.7694      99.00          1 : 0.449     

  0        0   2.46621       2.00        150 : 4.839     

 87      1.7   12.9013     198.00          1 : 0.375     

   * * *  

 87      1.7   12.9013     198.00          1 : 0.409     

  1       29   13.7694      99.00          1 : 0.551     

  0        0   2.46621       2.00        150 : 2.510      

   * * *  

 Cycles:  6.95  6.96         Average: 6.96   

   6764:  44.9  55.1         M_killed:  468.55/597.00   456.58/597.00  

 

Для случая 2.:

 

  1       29   13.7694      99.00          1 : 0.407     

  0        0   2.46621       2.00        150 : 4.573     

 87      1.7   12.9013     198.00          1 : 0.407     

   * * *  

 87      1.7   12.9013     198.00          1 : 0.470     

  1       29   13.7694      99.00          1 : 0.593     

  0        0   2.46621       2.00        150 : 0.683     

   * * *  

 Cycles:  6.72  6.60         Average: 6.65   

   6764:  40.7  59.3         M_killed:  467.01/597.00   443.86/597.00 

 

Причина такого эффекта проста. Перфоратор во входном файле стоит последним. При таком подходе к использованию результатов получения случайного числа он (перфоратор) будет стрелять в два раза чаще последним в случае 1. и все время последним в случае 2. Таким образом вероятность победы второго флота увеличиться. Происходить будет это из-за неправильно реализованного округления чисел.

Итак, озвучим наконец миф полностью. Старые и очень седые ветераны говорят: “Неправильно реализованное округление ведет к тому, что последний в списке корабль будет стрелять чаще всего последним. На остальные корабли округление не влияет”. Так это или нет на самом деле, нам доподлинно неизвестно. Оставляем дело проверки высказанной гипотезы на читателей.

 

Миф 2. Не везет только конкретным расам.

 

Собственно говоря этот миф является следствием мифа №1. Действительно, в правилах сказано: сторона, которая стреляет, выбирается случайно. Приводя аналогичные п.1 рассуждения, приходим к выводу:

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

 

 

Миф 3. Лучше строить корабли побольше массой.

 

Вернем баттлимитатор в исходное состояние и посмотрим на вероятность победы флотов:

 

;A W [:TW] S [:TS] M [#]

; first fleet

 1  29  20.5 99  1

 0  0   1    2   150

 43 1.7 12.1 99  2

 

; second fleet

 87 1.7 24.2 198 1

 1  29  20.5 99  1

 0  0   1    2   150

 

  1       29   13.7694      99.00          1 : 0.568     

  0        0   2.46621       2.00        150 : 4.376     

 43      1.7   8.12732      99.00          2 : 0.832     

   * * *  

 87      1.7   12.9013     198.00          1 : 0.338     

  1       29   13.7694      99.00          1 : 0.432     

  0        0   2.46621       2.00        150 : 2.356     

   * * *  

 Cycles:  6.98  7.80         Average: 7.34   

   6764:  56.8  43.2         M_killed:  449.68/597.00   482.51/597.00

 

Как видим вероятность победы первого флота больше. Происходит это благодаря тому, что первый флот более устойчив к прострелам на последних стадиях битвы, более равномерно расстреливает прикрышку противника и лучше защищает турели когда заканчивается своя прикрышка. Такие выводы справедливы только для первых стадий игры и небольших масс флота. Впрочем, и на последних стадиях в обычных партиях строить корабли массой больше 200-т оказывается не особенно выгодно, если только это не непробивашки. Но это уже совсем другая история …

 

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

 

 

 

 

Опубликовано в электроной газете "Galaxy Club" #2 09.02.2004

 

Подписаться на текстовую рассылку газеты "Galaxy Club" можно здесь:

http://www.galaxyplus.org/mailman/listinfo/galaxyclub/

 

Архив текстовых выпусков газеты "Galaxy Club" можно скачать отсюда:

http://www.galaxyplus.org/pipermail/galaxyclub/

 

Можно посылать свои мысли по адресу:

mailto:galaxyclub@list.ru

 

Сайт газеты:

http://www.uplanet.ru/GalaxyClub/