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

[Sender]

EUgeneUS в сообщении #1510179 писал(а):

UPD: попробуйте выровнять вероятность занятия всех клеток для размещения корабля $2 \times 1$ на поле $3 \times 3$

Для достаточно больших полей это возможно. Например, в упомянутом случае корабля $2 \times 1$ достаточно поля $4 \times 4$.

[EUgeneUS]

komand
Рассмотрим установку первого корабля - $4 \times 1$.
Всего вариантов установки $N_4 = 7 \cdot \ 10 \cdot 2 = 140$
Да, Ваш алгоритм обеспечивает, что любая из возможных установок для первого корабля будет выбрана с одинаковой вероятностью.

У Вас какой второй корабль? Тоже 4-х клеточный или 3-х клеточный?
Рассмотрим установку трех-клеточного корабля (он будет вторым или третьим).
Возможных вариантов на пустом поле: $N_3 = 8 \cdot \ 10 \cdot 2 = 160$
Я утверждаю, что при Вашем алгоритме эти варианты будут выбираться с разной вероятностью.
Можете проверить. Вариантов не много, их все можно пронумеровать и посчитать сколько раз каждый из них выбирается после $10^6$ прогонов.
Тоже самое касается и расстановки более мелких кораблей.

Это означает, что варианты расстановки всех кораблей (которых уже огромное количество, несколько меньше, чем $(1 \cdot 140) \cdot (2 \cdot 160) \cdot (3 \cdot 180) \cdot (4 \cdot 100)$) Ваш алгоритм тоже выбирает с разной вероятностью.

-- 20.03.2021, 16:49 --

Sender в сообщении #1510191 писал(а):

Например, в упомянутом случае корабля $2 \times 1$ достаточно поля $4 \times 4$.

Да, в этом случае можно. Но приходится выбирать: либо равновероятны положения корабля, либо равновероятны заполнения клеток.

[komand]

Цитата:

Да, в этом случае можно. Но приходится выбирать: либо равновероятны положения корабля, либо равновероятны заполнения клеток..

Я генерил $10^7$ расстановок, среди них нет повторяющихся. Тестировал около сотни раз. В среднем после генерации остается после примерно 17,7 клеток, число всех размещений 10 кораблей на поле $10\times10$ можно примерно оценить, как $C^{18}_{100}$ \approx$10^1^9$. Это достаточно много, чтобы исчерпать 10 млн. попыток. В среднем, вероятность обнаружить в некой клетке некий корабль (1п, 2п, 3п и 4п) одинакова. Но это на больших генерациях, от миллиона. Конечно, и размещение кораблей неравновероятны, и заполнение клеток. Но все это усредняется на сотнях миллионах игр. Я ставил несколько кораблей до генерации, генерил только вертикальные или только горизонтальные корабли, в разном порядке (например, от маленьких к большим), делал перемешивание после генерации и пр. Все это крайне мало влияет на распределение кораблей. Самое главное, не меняет среднее число попыток для потопления такой генерации.
Что действительно влияет - это число оставшихся свободных клеток. Но при случайной генерации оно постоянно, 17.7. А вот если потребовать от программы уплотнять корабли, прижимать друг другу и бортам, тогда картина игра существенно меняется.
У меня нет аналитического решения задачи, у меня есть решение вероятностное с какой-то точностью. Но спасибо что вы обратили внимание на распределение кораблей, сейчас я его как раз изучаю и вношу поправки в статью.

[EUgeneUS]

komand
Когда Вы что-то считаете методом Монте-Карло (а Вы делаете именно это).
Вам критически важно, чтобы каждый вариант был равновероятен. Или делать поправки на неравномерную вероятность.
А Ваш алгоритм генерации случайного поля этого не обеспечивает.

Вот иллюстрация. Поле $10 \times 10$, два корабля $4 \times 1$ и $1 \times 1$. Легко (но нудно) посчитать, что всего вариантов расстановок $N = 11760$. То есть с вероятностью $\frac{1}{11760}$ должна генерироваться каждая расстановка.

а) Посчитаем, с какой вероятностью будет генерироваться расстановка: большой корабль в левом верхнем углу горизонтально, малый в правом нижнем углу. По вашему алгоритму вероятность будет $p = \frac{1}{140} \frac{1}{90} = \frac{1}{12600}$. На 7% меньше

б) Посчитаем, с какой вероятностью будет генерироваться расстановка: большой корабль в точках $b2...b5$, малый в правом нижнем углу. По вашему алгоритму вероятность будет $p = \frac{1}{140} \frac{1}{82} = \frac{1}{11480}$. На 2.4 % больше

Различия вроде бы небольшие, но они есть. И никак не оценивается,
а) какие перекосы возникают при полной расстановки 10 кораблей.
б) как это влияет это на окончательные выводы.

[komand]

EUgeneUS в сообщении #1510218 писал(а):

Различия вроде бы небольшие, но они есть. И никак не оценивается,
а) какие перекосы возникают при полной расстановки 10 кораблей.
б) как это влияет это на окончательные выводы.

В статье я сказал, что неравномерность есть и она влияет на результат. На третий знак после запятой.

[EUgeneUS]

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

На третий знак после запятой.

Хорошо.
А как это оценивалось? (В примере влияние есть на второй значащий знак).

[Geen]

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

Случайно выбирается любое из 4 направлений: вверх, вниз, влево, вправо

неверно

-- 20.03.2021, 20:19 --

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

Я генерил 10^7 расстановок, среди них нет повторяющихся.

Если число расстановок на 10 порядков больше, то это ни о чём.

[Pphantom]

Тема перемещена из форума «Математика (общие вопросы)» в форум «Карантин»
Поскольку само это все же не проходит:

- наберите правильно числа со степенями и умножения (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы) во всей теме.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Математика (общие вопросы)»

[komand]

Сделал паузу, чтобы исправить формулы в теме и разобраться с распределением 2п корабля на поле $3\times3$
Для начала анекдот в тему.
Приходит аспирант-математик (А) к шефу (Ш).
А: Я решил крупную задачу для своей диссертации (подает решение).
Ш: (смотрит решение) Так, так... Формула сложная, давайте проверим ее на простом примере? Ага, видите, ошибка? Исправляйте.
А. приходит через год.
А: Шеф, я целый год искал ошибку и нашел.
Ш: И где она была?
А: В вашем примере.

О чем это я. Ув. EUgeneUS написал:

Цитата:

1. За четыре удара точно попадаем. В среднем $2.5$
2. Дальше добиваем. Где бы и когда бы не ранили, остается ровно три варианта на добитие. С учетом "призового удара", это $0, 1, 2$ хода. В среднем один ход.3. $2.5 + 1 = 3.5$

Все верно... но не совсем. Из-за больших кораблей для такого поля возникают "краевые эффекты". А именно, корабль может иметь от 0.5 до 1.5 попытки на добитие (с учетом премии), см. рис.

Однако из-за особенностей сетки

всегда получалось попадание в клетку, имеющую "2 степени свободы", т.е. 1 попытку на добитие.

Сейчас я проверяю программу на таких положениях, для которых можно рассчитать вероятность теоретически. Как отлажу, вернусь к дискусии.

[EUgeneUS]

komand
Что у Вас посчитано на первой картинке, мне не очень понятно.

А дальше у Вас довольно странные рассуждения. Правильно так:
а) До начала обстрела есть 12 различных положений корабля, все они равновероятны (так расставляли).
б) После попадания первый раз (если стреляем "по сетке") у нас всегда остаётся три варианта расстановки корабля. И они всё так же равновероятны. Поэтому корабль убивается после ранения в среднем за 2 удара. С учетом призового удара - в среднем за 1 ход.

[komand]

На первой картинке показано неравное расположение кораблей. Если попадание будет в середину, на добитие потребуется 1.5 попытки, а если в угол, всего 0.5. И таких положений разное кол-во: 4 по 0,5, 4 по 1 и 1 по 1,5. Все из-за "краевых эффектов". На поле $10\times10$ таких эффектов будет меньше. На бесконечной доске бортовые и угловые расположения вообще можно не учитывать. К чему эти рассуждения? К тому, что проверять некое утверждение с помощью простых примеров надо осторожно.
Если случайно (без сетки) искать один 2п на $3\times3$, то получается в среднем 3.944 (с добитием) или 3.333 (без добития).

[komand]

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

[komand]

Кстати, верно ли я оцениваю число возможных начальных расстановок кораблей, как $C_{100}^{10}\approx1,73\times10^{13}$ ? Имеется ввиду поле $10\times10$, 10 кораблей. Поскольку не все размещения легальны (корабли не могут каcаться друг друга), то это верхняя оценка. Но даже такая маленькая что-то. Где-то ошибку допустил?
А, понял, ведь каждый корабль кроме размещения еще может и поворачиваться.

[Geen]

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

Где-то ошибку допустил?

Две ориентации.