Морской бой. Стратегия через теорию вероятностей

[Someone]

komand в сообщении #1510979 писал(а):

Но даже такая маленькая что-то. Где-то ошибку допустил?

Если не мелочиться, то левая верхняя клетка корабля может быть любой, но может принадлежать только одному кораблю. С учётом порядка выбора, получаем $A_{100}^{10}=\frac{100!}{(100-10)!}$. На касания и пересечения, а также на вылезания за поле не обращаем внимание, иначе запутаемся. Тогда корабль, содержащий больше одной клетки, можно поставить двумя способами, поэтому умножаем на $2^6$. Корабли одинаковой длины неразличимы, поэтому делим на $4!\cdot 3!\cdot 2!\cdot 1!$. В итоге получаем

$$\frac{100\cdot 99\cdot 98\cdot 97\cdot 96\cdot 95\cdot 94\cdot 93\cdot 92\cdot 91\cdot 2^6}{4!\cdot 3!\cdot 2!\cdot 1!}=13\,959\,033\,545\,673\,216\,000\approx 1{,}4\cdot 10^{19}.$$

[komand]

Someone в сообщении #1510982 писал(а):

komand в сообщении #1510979 писал(а):

Но даже такая маленькая что-то. Где-то ошибку допустил?

Если не мелочиться, то левая верхняя клетка корабля может быть любой, но может принадлежать только одному кораблю. С учётом порядка выбора, получаем $A_{100}^{10}=\frac{100!}{(100-10)!}$. На касания и пересечения, а также на вылезания за поле не обращаем внимание, иначе запутаемся. Тогда корабль, содержащий больше одной клетки, можно поставить двумя способами, поэтому умножаем на $2^6$. Корабли одинаковой длины неразличимы, поэтому делим на $4!\cdot 3!\cdot 2!\cdot 1!$. В итоге получаем

$$\frac{100\cdot 99\cdot 98\cdot 97\cdot 96\cdot 95\cdot 94\cdot 93\cdot 92\cdot 91\cdot 2^6}{4!\cdot 3!\cdot 2!\cdot 1!}=13\,959\,033\,545\,673\,216\,000\approx 1{,}4\cdot 10^{19}.$$

Спасибо! Корабль можно поставить всего двумя способами, не четырьмя? Или они сокращаются из-за симметрии?

Здесь немного др. оценка, но похожа.

Цитата:

После установки 1нопалубников (если начинать с них), будет занято минимум 16 клеток, максимум - 36 клеток. Установка двухпалубников займёт минимум 18 максимум 36 клеток, установка трёхпалубников - мин 16, макс 30 клеток, 4хпалубный - мин 10, макс 18 клеток.
Если начинать сверху вниз (от больших кораблей к малым, что в общем то логичнее), то установка 4хпалубника (с вариантами = N4 = 140) cокращает для оставшихся кораблей число свободных клеток минимум на 10. Тогда для оставшихся трёхпалубников остаётся максимум 90 клеток.
Результаты расчётов получились такие:
N4 = 140
N43 = 17440 (установка 1го 4 и 1го 3хпалубного)
N433 = 1958320
N4332 = 228234080
N43322 = 23919593920
N433222 = 2,22688E+12
N4332221 = 1,1295E+14
N43322211 = 5,2956E+15
N433222111 = 2,28058E+17
N4332221111 = 8,95513E+18

И еще одна оценка, они почти на 100% ошибочна, но почему-то совпадает с этими двумя ))
Число свободных клеток после генерации ~17,26. Отсюда можно оценить число возможных позиций в игре, как С_{100}^{17,26}\approx10^{19}.

То есть верхняя оценка $10^{19}$ ? А как бы оценить нижнюю? Можно прикинуть, что нижняя оценка $10^{17}$ или что-то около?
Я каждый раз тестирую $10^7-10^8$ расположений кораблей, понимаю, что это мало (. Есть обоснованные сомнения, что выборка репрезентативна. Тестировал несколько раз по $10^9$ расположения (по правилам игры, без касаний), ни разу не попалось два совпадающих. Еще бы, если всех расположений $10^{19}$, то это всего 10^{-10}, немного. К сожалению, на моем компьютере расчет $10^9$ - это уже 5 часов.

[Someone]

komand в сообщении #1510986 писал(а):

Здесь немного др. оценка, но похожа.

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

[komand]

Someone в сообщении #1510991 писал(а):

komand в сообщении #1510986 писал(а):

Здесь немного др. оценка, но похожа.

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

Еще раз спасибо!
Нижнюю оценка "отброса" нелегальных позиций можно посчитать вот след. образом. Если считать, что корабли могут коснуться друг друга в 88 местах (в среднем 44), как минимум с верхней оценки можно скинуть 1-2 порядка. Верхняя оценка "отброса": случайная генерация кораблей показывает, что только 1 из 3900 получившихся позиций легальна. Отсюда число легальных начальных позиций в игре можно оценить как $10^{16}$
Впрочем, это мало поможет, все равно моя выборка крайне мала. Одно радует: уже на на $10^6$ искомые величины (например, среднее число выстрелов до победы) имеют среднеквадратичное отклонение менее 3$\sigma$. Но это может означать, что моя начальная генерация кораблей систематически ошибается. Кстати, тестирование генератора псевдослучайных чисел показало, что он дает равномерные последовательности без повторов в нужном мне промежутке. Хоть что-то утешает...

[Geen]

komand в сообщении #1510992 писал(а):

имеют среднеквадратичное отклонение менее 3$\sigma$.

Простите?

[komand]

Geen в сообщении #1510995 писал(а):

komand в сообщении #1510992 писал(а):

имеют среднеквадратичное отклонение менее 3$\sigma$.

Простите?

Практически все значения нормально распределённой случайной величины лежат в интервале $\mu$±3$\sigma$, где $\mu$ - мат. ожидание случайно величины, $\sigma$ - среднеквадратичное отклонение, $\sqrt{D}$, где D - дисперсия случ. величины.
Я "измеряю" некую величину много раз и оцениваю погрешность измерения через дисперсию (разброс). При этом слежу, чтобы распределение не сильно отклонялось от нормального.
Или более подробно. По некоторому алгоритму генерирую $10^7$позиций, вычисляю величину, например, вероятность победы с N-попытки. Потом генерирую еще $10^7$ или около позиций, но по немного др. алгоритму, снова слежу за искомой величиной. И так десятки раз. Потом беру полученную выборку искомой величины, высчитываю среднее арифметическое (считаю ее мат. ожиданием), дисперсию, среднеквадратичное отклонение. Далее смотрю, чтобы разброс величины не сильно отклонялся от 3 сигм. Если отклоняется сильно, значит, увеличиваю выборку. Если не помогает, значит, либо распределение не нормальное, либо имеет место систематическая ошибка, методика неверна. Если же все хорошо, то возможно, моя выборка генераций позиций репрезентативна. Или есть какие-то факторы, которые я не учитываю при генерации и тогда у меня только видимость гладкости.
Что-то не так делаю или выразился криво?

[Someone]

komand в сообщении #1510986 писал(а):

Корабль можно поставить всего двумя способами, не четырьмя? Или они сокращаются из-за симметрии?

Я написал "левая верхняя клетка корабля". Корабль от неё можно поставить либо направо, либо вниз.

komand в сообщении #1510986 писал(а):

Тестировал несколько раз по $10^9$ расположения (по правилам игры, без касаний), ни разу не попалось два совпадающих.

Пусть у нас есть $N$ элементов, которые мы выбираем $n$ раз (с возвращением и независимо) с одинаковой вероятностью $\frac 1N$ каждый. Вероятность того, что в полученной выборке объёма $n$ найдутся совпадающие элементы, равна

$$P_N(n)=1-\prod_{k=0}^{n-1}\left(1-\frac kN\right).$$

У нас $n=10^9$, и пусть $N=10^{19}$. Вычислять вероятность совпадений по этой формуле, конечно, весьма накладно, но можно получить приближённую.
Раскрывая скобки, получим

$$P_N(n)=\sum_{k=0}^{n-1}\frac kN-\sum_{0\leqslant k_1<k_2\leqslant n-1}\frac{k_1k_2}{N^2}+\sum_{0\leqslant k_1<k_2<k_3\leqslant n-1}\frac{k_1k_2k_3}{N^3}-\ldots=$$

(число слагаемых конечное; 26/III в 21:52 удалил ненужные факториалы, которые тут оказались по недоразумению; далее их и не было)

$$=\frac 1N\sum_{k=0}^{n-1}k-\frac 1{N^2}\sum_{k_1=0}^{n-2}\left(k_1\sum_{k_2=k_1+1}^{n-1}k_2\right)-\frac 1{N^3}\sum_{k_1=0}^{n-3}\left(k_1\sum_{k_2=k_1+1}^{n-2}\left(k_2\sum_{k_3=k_2+1}^{n-1}k_3\right)\right)+\ldots=$$

$$=\frac{n(n-1)}{2N}-\frac{n(n-1)(n-2)(3n-1)}{24N^2}+\frac{n^2(n-1)^2(n-2)(n-3)}{48N^3}-\ldots=$$

$$=\frac{n(n-1)}{1!\cdot 2N}-\frac{n(n-1)(n-\frac 13)(n-2)}{2!\cdot(2N)^2}+\frac{n^2(n-1)^2(n-2)(n-3)}{3!\cdot(2N)^3}-\ldots\approx$$

(знаменатели дробей устроены вполне закономерно, а числители мы заменим соответствующими степенями произведения $n(n-1)$, а также продолжим сумму "до бесконечности")

$$\approx\frac 1{1!}\left(\frac{n(n-1)}{2N}\right)-\frac 1{2!}\left(\frac{n(n-1)}{2N}\right)^2+\frac 1{3!}\left(\frac{n(n-1)}{2N}\right)^3-\ldots=1-e^{-\frac{n(n-1)}{2N}}.$$

Оценкой погрешности не заморачиваюсь, так как наверняка эта формула (или похожая с $n^2$ вместо $n(n-1)$) уже лет сто как опубликована и с оценкой погрешности. Просто покажу величину погрешности на графиках.
Слева — это графики $P_N(n)$ и $1-e^{-\frac{n(n-1)}{2N}}$ для $N=365$ (классическая задача о днях рождения) и для $N=100\,000$, а справа — графики разности $P_N(n)-\left(1-e^{-\frac{n(n-1)}{2N}}\right)$.

Вложение:

Sovpadenia-365pd.gif [ 5.72 Кб | Просмотров: 1549 ]

Вложение:

Sovpadenia-100000pd.gif [ 6.41 Кб | Просмотров: 1549 ]

Хорошо видно, что при больших $N$ погрешность маленькая.
Для $N=10^{19}$ и $n=10^9$ формула даёт $P\approx 0{,}04877$.
Обратная величина вероятности $\frac 1P\approx 20{,}5$, поэтому для получения первого совпадения в среднем требуется $20{,}5$ независимых выборок объёмом $10^9$. На этом пути можно и оценить объём генеральной совокупности, но для этого требуется сколько-то сотен таких выборок (для $n=10^7$ получается $P\approx 5\cdot 10^{-6}$, поэтому таких выборок требуются миллионы).

[komand]

Спасибо! Ценное исследование для моей работы. Вы потратили кучу своего времени на этот вопрос. Спасибо!

Пара замечаний.
1. Я генерирую не все возможные положения $10^{19}$, а по по правилам игры, а их меньше примерно в 3900 раз, т.е. $10^{16}$. При этом на выборках $10^9$ совпадений не было (тестировал всего 2 раза, все-таки это очень затратно, по 5 часов работы компьютера).
2. То, что совпадений не было, это интересно, но малопрактично для моего исследования. Более важен вопрос: "Насколько случайная выборка в $10^7$ положений из $10^{16}$ репрецентативна? В этой теме были сомнения в том, что моя выборка слишком маленькая, я мог упустить какие-то начальные расположения кораблей, важные для игры.
Для этого я меняю генерации (от больших кораблей к маленьким, и наоборот, смена ГСЧ, доп. перемешивание кораблей, только вертикальные или только горизонтальные и пр.) и потом сравниванию распределения по ключевым точкам. Если есть существенные различия, значит, что-то упускаю. Пока различий нет. Но это не значит, что все хорошо.

В общем, вопрос остается: насколько выборка в $10^7$ может быть репрезентативна для множества всех положений в $10^{16}$?

Пока я нашел, что единственный фактор, влияющий на игру - число оставшихся свободных клеток. Или, формулируя по другому, насколько корабли прижимаются в бортам. Чем меньше поле и чем больше кораблей, тем более заметен "краевой" эффект. На поле $3\times3$, с кораблем 2п например, он играет ключевую роль. А на поле $12\times12$ с полным флотом (10 кораблей) эффекта почти нет.

[Someone]

komand в сообщении #1511095 писал(а):

Я генерирую не все возможные положения $10^{19}$, а по по правилам игры, а их меньше примерно в 3900 раз, т.е. $10^{16}$. При этом на выборках $10^9$ совпадений не было (тестировал всего 2 раза, все-таки это очень затратно, по 5 часов работы компьютера).

При $N=10^{16}$ и $n=10^9$ вероятность того, что совпадений не будет, меньше $2\cdot 10^{-22}$ для одной выборки, и меньше $4\cdot 10^{-44}$ для двух независимых выборок, поэтому такого не может быть. Как Вы проверяете, что совпадений нет? Вы запоминаете в том или ином виде весь миллиард сгенерированных расстановок? Может быть, Вы под "совпадениями" понимаете совсем не то, что я? Сформулируйте, пожалуйста, своё определение совпадения.

[komand]

Someone в сообщении #1511130 писал(а):

komand в сообщении #1511095 писал(а):

Я генерирую не все возможные положения $10^{19}$, а по по правилам игры, а их меньше примерно в 3900 раз, т.е. $10^{16}$. При этом на выборках $10^9$ совпадений не было (тестировал всего 2 раза, все-таки это очень затратно, по 5 часов работы компьютера).

При $N=10^{16}$ и $n=10^9$ вероятность того, что совпадений не будет, меньше $2\cdot 10^{-22}$ для одной выборки, и меньше $4\cdot 10^{-44}$ для двух независимых выборок, поэтому такого не может быть. Как Вы проверяете, что совпадений нет? Вы запоминаете в том или ином виде весь миллиард сгенерированных расстановок? Может быть, Вы под "совпадениями" понимаете совсем не то, что я? Сформулируйте, пожалуйста, своё определение совпадения.

Я понимаю под "совпадением" две одинаковые генерации внутри одной выборки. Выюорки не запоминаются, каждый раз генерируется новая. И так несколько десятков раз.
Алгоритм такой:
1. Генерируем расположение. Проходим по сгенерированному полю, вычленяем ячейки, занятые кораблями и записываем их координаты в строковую переменную.
2. Записываем переменную в массив.
3. После $10^9$ таких генераций проверяем полученный массив на совпадения. Это короткая функция на Jscript, возвращает кол-во совпадений в массиве "а":

function calc(a) {
var count={}, res=0, q;
for (q=0; q<a.length; ++q) {count[a[q]] = ~~count[a[q]] + 1;}
for (q in count) {if (count.hasOwnProperty(q) && count[q] > 1) {res += count[q];}}
return res;}

Проще на примере, см. рисунок. Система координат 0-9 по вертикали сверху вниз, затем по горизонтали слева направо.

Здесь три корабля, строковая переменная: "00010220304050" (на самом деле каждый раз строка в 40 знаков, типа такой: 0613162029343536394252626972747779848996)

Правда, я только что обнаружил, что генерация была максимум $2\times10^8$, на больше не хватает памяти. На $10^9$ получается 400 Гб, а у меня памяти только 32 Гб. Сейчас попробую найти решение с памятью.
И еще: на выборках более $2\times10^9$ совпадения будут обязательно, потому что период генератора псевдослучайных чисел именно такой. ГПСЧ Мерсена длинней, могу попробовать использовать его.

Нашел способ тестировать выборки $10^8$.Совпадений пока нет. Но проверка на совпадения в таком массиве идет очень долго, много не проверю. (

[komand]

Прогнал десяток выборок с $8\times10^7$. Совпадений внутри выборок не найдено. Выборки длиннее сложно тестировать.

[Geen]

А каков период этого генератора?

[komand]

Geen в сообщении #1511198 писал(а):

А каков период этого генератора?

Найти сведения трудно, можно оценить, как $2\times19^9$. Я тестировал и на генераторе Мерсенна, он имеет период $4,3\times10^{6001}$. Кроме того, я сравнивал разные генераторы много раз в разных длинных тестах (на моих задачах). Разницы не заметил. Видимо, ГПСЧ, встроенный в Jsript Node.js на движке V8 Chrome, достаточно хорош (для моих задач) на выборках менее $2^{32}$

[Geen]

komand в сообщении #1511200 писал(а):

можно оценить, как $2\times19^9$

Вас не смущает, что таким генератором принципиально нельзя получить $10^{19}$ позиций?

[komand]

Geen в сообщении #1511203 писал(а):

komand в сообщении #1511200 писал(а):

можно оценить, как $2\times19^9$

Вас не смущает, что таким генератором принципиально нельзя получить $10^{19}$ позиций?

Во-первых, не $10^{19}$, а $10^{16}$. Во-вторых, эта самая нижняя граница ГПСЧ. Jscript на node.js использует движок V8 от Google, наверняка там лучшие генераторы, вплоть до $2^{64}$, а может и "вихрь Мерсенна", у него безумный период. Третье, самое главное: зачем мне $10^{19}$ или даже $10^{16}$? Каждая выборка - это $10^7$-$10^8$ позиций. Следующая генерация - другие, независимые случайные числа, потому что seed другое. Документацией гарантируется, что корреляций между выборками нет.
Но вы правы, все равно сомнения остались. Поэтому, для теста я погонял ГПСЧ на "вихре Мерсенна", различий не обнаружил.