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

[12d3]

Еще немного оптимальных стратегий для доски 4х4. Я рассмотрел поиск одного корабля (2п, 3п, 4п). Оптимальная расстановка такова, что все неугловые положения равновероятны (для 3п и 4п это тривиально, а вот для 2п - уже нет).
Для 2п: угловые положения выбираем с вероятностью $\frac{7}{120}$, и соответственно неугловые с вероятностью $\frac{1}{30}$. Две наилучших стратегии обстрела:
$\begin{center} \begin{tabular}{| c | c | c | c |} \hline 3 & & 2 & \\ \hline & 1 & & 2 \\ \hline 2 & & 1 & \\ \hline & 2 & & 3 \\ \hline \end{tabular} \end{center}$ и $\begin{center} \begin{tabular}{| c | c | c | c |} \hline 3 & & 2 & \\ \hline & 1 & & 4 \\ \hline 2 & & 5 & 2 \\ \hline & 4 & 2 & \\ \hline \end{tabular} \end{center}$
Здесь циферками обозначен приоритет: сначала стреляем по всем клеткам с цифрой 1, потом по всем клеткам с цифрой 2, и т.д., пока не попадем.
Итого, кораблик убивается в среднем за $\frac{379}{60}$ выстрелов.
Для 3п: угловые положения выбираем с вероятностью $\frac{11}{142}$, и соответственно неугловые с вероятностью $\frac{4}{71}$. Две наилучших стратегии обстрела:
$\begin{center} \begin{tabular}{| c | c | c | c |} \hline & & 2 & \\ \hline & 1 & & \\ \hline 2 & & & 2 \\ \hline & & 2 & \\ \hline \end{tabular} \end{center}$ и $\begin{center} \begin{tabular}{| c | c | c | c |} \hline & & 1 & \\ \hline 1 & 2 & & \\ \hline & & 2 & 1 \\ \hline & 1 & & \\ \hline \end{tabular} \end{center}$
Во второй стратегии могут быть небольшие вариации, но всегда первые четыре выстрела по сторонам, а пятый выстрел в центр.
Корабль убивается в среднем за $\frac{108}{19}$ выстрелов.
Для 4п: все положения равновероятны. Стратегия обстрела такова, что первыми четырьмя выстрелами должны зацепить все вертикали и горизонтали, а дальше добиваем. Корабль убивается за 6 выстрелов в среднем.

[Sender]

Но ведь никакая из этих стратегий обстрела не оптимальна по Нэшу. Если противник заранее знает, какая из них применяется, он, скажем, на первой картинке поставит корабль на тройку и протянет немного дольше.

[12d3]

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

[komand]

$4\times4$ я тоже проверял. Везде рулит сетка, причем где чем больше поле, тем больше. Но на маленьких полях, типа $3\times3$могут проявляться "краевые эффекты". Поэтому не стоит из стратегий на маленьких полях выводить большие. Конкретно для $4\times4$ сетка убивает 2п корабль макс. за 8 ходов, в среднем за 4.5 (без добивания).
3п на таком поле лучше не тестировать, слишком большой, "краевые эффекты".

[Geen]

не надо считать ходы - это неудобно, хотя их вседа ровно на $N-1$ меньше, чем количество выстрелов.

[komand]

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

не надо считать ходы - это неудобно, хотя их вседа ровно на $N-1$ меньше, чем количество выстрелов.

Ходы = выстрелы = попытки. Это просто разное название. Иначе легко запутаться. Но кол-во попыток может различаться в разных играх, если нет "премиального" выстрела Если считать по базовым правилам, премиальный выстрел приходится учитывать. То есть, к примеру, последовательность "попал, мимо, попал, мимо" - это не 4 попытки, а две.
И еще, с премией есть шанс утопить весь флот противника одним выстрелом.
Еще: начинающий первым имеет примерно 3% преимущества, это немало. Стоило бы ввести "посмертный выстрел", т.е. противник имеет право сделать 1 выстрел, когда весь его флот уже утоплен. Это уровняло бы шансы.

[EUgeneUS]

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

Ходы = выстрелы = попытки.

У вас странная, контринтуитивная терминология.
ИМХО, более логично понимать так:
"Выстрел" - одна "точка"(промах), или один "крестик" (попадание). "Один снаряд".
"Ход" - последовательность выстрелов, которые последовательно делает одна сторона.
То есть:

"К9 - пропах" - это один выстрел и один ход.
"А5 - ранил, А6 - убил, Б10 - промах" - это три выстрела, но один ход.

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

не надо считать ходы - это неудобно, хотя их вседа ровно на $N-1$ меньше, чем количество выстрелов.

Количества ходов всегда меньше количество выстрелов на количество попаданий.

[Geen]

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

Количества ходов всегда меньше количество выстрелов на количество попаданий.

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

-- 27.03.2021, 11:48 --

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

У вас странная, контринтуитивная терминология.

Согласен.
Не говоря уж о том, что использовать три синонима в статье или обсуждении это моветон.

[EUgeneUS]

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

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

Не понимаю, как это.
Можете пояснить?

[Geen]

Допустим, Вы всё убиваете первым ходом - выстрелов при этом 20 (суммарное количество занятых клеток).

[EUgeneUS]

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

Допустим, Вы всё убиваете первым ходом - выстрелов при этом 20 (суммарное количество занятых клеток).

Пусть
$n$ - количество выстрелов за ход,
$k$ - количество попаданий за ход.
$l$ - количество промахов за ход.

$N$ - общее количество выстрелов за игру,
$K$ - общее количество попаданий за игру (равно количеству занятых клеток)
$L$ - общее количество промахов за игру
$M$ - общее количество ходов за игру

Тогда справедливы следующие соотношения:
$n = k+1$ и $l=1$, если ход не последний (не всех убили)
$n = k$ и $l=0$, если ход последний (всех убили).

$M = L+1$
$N = L+K = M + K -1$
$M = N - K +1$ (1)

Вот тут:

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

Количества ходов всегда меньше количество выстрелов на количество попаданий.

Я имел в виду (1), но не учел особенность последнего хода и не добавил $1$.

А что Вы имели в виду тут (с учетом моего болда):

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

Нет, на единицу меньше - последним попаданием заканчивается игра. Это в конце.

?

[Geen]

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

А что Вы имели в виду тут (с учетом моего болда):

Неудачно выразился - разница на единицу меньше.

[EUgeneUS]

Geen
Понятно. Спасибо за разъяснение.

[komand]

Хорошо, пусть будет ход - последовательность выстрелов. Хотя в статье я использую слово "попытка" - это ближе к теории вероятностей. Подумаю, может исправлю.
Есть простой способ получить немалое преимущество в игре ($\approx3$ игр на 100): просто всегда начинать первым ).
Кстати, при огромном кол-ве сыгранных партий компьютерной программой (от $10^8$) не было ни одного случая, чтобы игра закончилась менее, чем за 3 хода (вероятность закончить игру за 3 хода 0,0000002) и более, чем за 64 (вероятность закончить за 64 хода 0,0000003). В среднем, противник выиграл ранее, чем на 15 ходу, стоит забеспокоиться (наверное, подсмотрел ваше расположение), а также, если играете более 50 ходов (наверное, один 1п не выставил).
Ниже распределение для поля $10\times10$, полный флот, расположение случайное, обстрел случайный, кол-во испытаний $10^8$. "Попытки" на графике в смысле "ходы", не "выстрелы".

[12d3]

Sender
Выяснилось, что оптимальных по Нэшу стратегий обстрела больно дофига, бесконечное количество, и поэтому не очень понятно, как их все описывать. Приведу простейший пример. Доска 1х3, на ней 1п кораблик. Оптимальная расстановка, очевидно, - равновероятный выбор одной из трех клеток. Если обстреливать таким образом, что в каждом случае равновероятно выбираем одну из оставшихся клеток, то такая стратегия оптимальна по Нэшу. А можно обстреливать по другому: либо с вероятностью 0.5 стреляем слева направо, либо с вероятностью 0.5 справа налево. Где бы ни был корабль, он убивается так же за два хода в среднем, и эта стратегия обстрела тоже оптимальна по Нэшу. И еще куча других стратегий есть. А всë потому, что при оптимальной расстановке чистых стратегий обстрела (в данном примере 6), дающих наилучший результат, намного больше, чем чистых стратегий расстановки вообще(в примере 3).