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

[komand]

Всем привет!
Я написал программу, которая тестирует игру "Морской бой": $10\times10$ клеток, корабли, убил-ранил, думаю, все знают. Программа играет сама с собой миллиарды раз и выводит статистику. На основе обработки этой статистики я написал статью о лучшей тактики размещения кораблей и их обстрела. Статья некоммерческая, будет выложена во всеобщий доступ в ближайшее время. Если хотите, прямо здесь.
Однако у меня слабое математическое образование (ФЕН НГУ) и хотелось бы найти кого-то, кто лучше меня разбирается в теории вероятности и статистике, чтобы проверил выводы. Все довольно несложно: нормальное и не очень распределение, дисперсия и пр. Важнее правильная методология. Я возьму его/их в соавторы. Смысла сейчас же выкладывать во всеобщий доступ не вижу: возможны существенные ошибки, которые так и распостранятся, будет стыдно.
Жду предложений. Если серьезные, высылаю статью (DOCX, 232 кб, внутри 12 рисунков), посмотрите. Сделаете замечания - замечательно, нет - тоже понятно.
Кто хочет посмотреть программу - легко, Jscript под Node.

[kotenok gav]

Перепишите статью в TeX и выложите прямо здесь. Ну или сделайте её pdf и выложите на любом файлообменнике.

[EUgeneUS]

komand
А рассматриваются ли в Вашей статье следующие моменты:
1. Оптимальная стратегия нанесения огня. ИМХО, это первично, чем распределение кораблей. Если да, то нельзя ли её озвучить? (В школьные годы чудесные, задумывался над этим вопросом )
2. Будет ли Ваше тактика\стратегия расстановки кораблей оптимальной, если противник знает, что Вы её следуете?

Просто интересно.

[komand]

kotenok gav в сообщении #1509665 писал(а):

Перепишите статью в TeX и выложите прямо здесь. Ну или сделайте её pdf и выложите на любом файлообменнике.

Так и сделаю после правок. Если же выложу сейчас же, с ошибками и она так разойдется, будет по меньшей мере неудобно. Но, если рецензентов не найдется, видимо так и сделаю.
-- 17.03.2021, 15:35 --

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

komand
А рассматриваются ли в Вашей статье следующие моменты:
1. Оптимальная стратегия нанесения огня. ИМХО, это первично, чем распределение кораблей. Если да, то нельзя ли её озвучить? (В школьные годы чудесные, задумывался над этим вопросом )
2. Будет ли Ваше тактика\стратегия расстановки кораблей оптимальной, если противник знает, что Вы её следуете?
Просто интересно.

1. Да. И это также важно, как и распределение кораблей. рассматриваются 3 вида огня: случайное, сеткой (по системе) и "оптимизация": "Пытаемся каждый выстрел оптимизировать с учетом наиболее вероятного расположения оставшихся кораблей. Иначе говоря, выстрел делается туда, где чаще всего располагается корабль." Хотя последняя тактика подходит только для компьютера.
2. Цитата: "Давайте попробуем найти лучшую тактику игры, без скидок, т.е. предполагая, что и ваш противник тоже знает ее" и "при случайном расположении кораблей приоритет стрельбы (сеткой или случайно) по центру, углам или периферии не влияет на кол-во попыток. В пределах выбранной точности 0.01%. А раз не влияет, то удобнее все-таки приоритет использовать: в случае «уплотнения» вы получите преимущество, а при случайном порядке кораблей противника ничего не потеряете."
Если же вы об расстановке кораблей "по Перельману", т.е. все, кроме однопалубников на борту, то вот вывод:
"Если ваш противник располагает свои корабли случайно, но знает о том, что вы расположили все корабли компактно на борту, уничтожил 6 кораблей первым же выстрелом и ищет оставшиеся 4 однопалубники, вы все равно будете иметь небольшое преимущество в 3%. Если вы вместо ТКРК используете уплотненное расположение, ваше преимущество возрастет до 11%.
В конце статьи делаются количественные вывода, какая расстановка и обстрел оптимальны.

[EUgeneUS]

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

Если же вы об расстановке кораблей "по Перельману", т.е. все, кроме однопалубников на борту,

Вот оно как называется, оказывается.

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

Тогда сразу два комментария.
1. Вы знакомы с теорией игр, хоть в каком-то объеме? Вполне возможно, что выигрышная стратегия отыщется среди смешанных стратегий, а не среди чистых.
2. Ещё есть проблема, связанная с ограниченностью множества стратегий, которые Вы рассматриваете.
На примере стратегии расстановки "по Перельману". Её смысл в том, чтобы оставить как можно больше разрешенных клеток для одноклеточных кораблей, чтобы противник получил малую вероятность их найти на заключительной фазе игры.
а) Но этого можно добиться не только, прижимая корабли к краям поля. Если их "кучковать" другим образом, то количество разрешенных клеток не сильно уменьшится (типовые значения: $55$ клеток "по Перельману" и $52$, если кучковать по середине одной стороны центре от одного края до другого - по другой стороне).
б) Далее. А сколько одноклеточных кораблей из 4-х нужно ставить случайно в разрешенных клетках, а сколько "прижимать к куче"?
Это только примеры модификаций стратегий, которые Вы не рассматриваете.
Поэтому говорить, что Вы нашли именно оптимальную стратегию не совсем верно, так ведь? Вы нашли оптимальную стратегию из заранее заданного множества стратегий..

[komand]

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

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

Если же вы об расстановке кораблей "по Перельману", т.е. все, кроме однопалубников на борту,

Вот оно как называется, оказывается.

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

Тогда сразу два комментария.
1. Вы знакомы с теорией игр, хоть в каком-то объеме? Вполне возможно, что выигрышная стратегия отыщется среди смешанных стратегий, а не среди чистых.
2. Ещё есть проблема, связанная с ограниченностью множества стратегий, которые Вы рассматриваете.
На примере стратегии расстановки "по Перельману". Её смысл в том, чтобы оставить как можно больше разрешенных клеток для одноклеточных кораблей, чтобы противник получил малую вероятность их найти на заключительной фазе игры.
а) Но этого можно добиться не только, прижимая корабли к краям поля. Если их "кучковать" другим образом, то количество разрешенных клеток не сильно уменьшится (типовые значения: $55$ клеток "по Перельману" и $52$, если кучковать по середине одной стороны центре от одного края до другого - по другой стороне).
б) Далее. А сколько одноклеточных кораблей из 4-х нужно ставить случайно в разрешенных клетках, а сколько "прижимать к куче"?
Это только примеры модификаций стратегий, которые Вы не рассматриваете.
Поэтому говорить, что Вы нашли именно оптимальную стратегию не совсем верно, так ведь? Вы нашли оптимальную стратегию из заранее заданного множества стратегий..

а) Я выбираю ВСЕ расстановки кораблей, которые возможны вообще, т.е. случайные. Оценочно всех расcтановок $10^{19}$, каждая выборка это $\approx10^7$ позиций, после чего комп играет сам с собой и считает кол-во попыток. Сходимость высокая, более 0.99. Затем я моделирую НЕслучайные расстановки, т.е. прижатие кораблей к бортам. На самом деле есть единственный параметр, который влияет на игру: кол-во свободных полей. Чем их больше, тем лучше расстановка. Но чем их больше, тем более предсказуема расстановка, потому что корабли вынуждены жаться к бортам. И снова заставляю комп играть эти расстановки.
б). Проще. Просто случайно или (по какому-то методу) обстреливаю сгенерированную позицию. И смотрю, сколько для этого нужно попыток (выстрелов). И так $10^7$ раз. Затем кол-во попыток усредняю. Сходимость высокая.
в) Я сравниваю три стратегии расположения кораблей: случайное, уплотненное и "по Перельману", т.е. предельно уплотненное. Зависимость четкая: чем более уплотненные корабли, тем попыток для их уничтожения больше. И три стратегии стрельбы: случайная, по разным "сеткам" и "оптимальная", т.е. выборка лучшего выстрела в каждой ситуации (подходит только для компа). Этого достаточно для полного исчерпания всех стратегий игры.

1. Игра слишком простая, чтобы искать ее решение в теории игр. На самом деле, нет никакой зависимости от того, что делает противник. Вы можете сгенерить поле, дать ее обстрелять противнику (только отвечая "мимо", "ранил", "убил"), зафиксировав кол-во попыток (выстрелов) для полного уничтожения вашего флота. Потом попросить сгенерить поле вашему противнику и обстрелять его поле. Потом сравнить ваши попытки. У кого их меньше, тот и выиграл. Поэтому, нет никакой необходимости учитывать ходы противника. Достаточно перебрать все начальные расстановки и оптимальные тактики обстрела. Легко выводится, что начальная расстановка характеризуется единственным важным параметром: числом свободных полей. А тактика обстрела самая лучшая "оптимальная", которая находит лучший ход в данной ситуации, просто перебирая все возможные расположения кораблей и находя лучший выстрел. На самом деле, "сетка" показала себя не хуже.
2. Любая стратегия размещения кораблей на самом деле характеризуется единственным параметром: числом свободных полей. И все. А число свободных полей зависит от уплотненности кораблей. А уплотнять можно, только прижимая к бортам. Чем сильнее прижал, тем лучше. Перельман рассматривает крайний случай, когда ВСЕ корабли, кроме однопалубника, кучно стоят в углу. Однако я доказал, что это не самая выигрышная стратегия. Проблема этой стратегии в том, что противник изначально знает (или узнает за пару выстрелов) расположение 6 кораблей. А выигрыш по выстрелам по оставшимся однопалубникам не такой боьшой. Это ответ на ваше (а). Что касается (б), то в игре с компом есть смысл прижать однопалубники к куче, но в игре с человеком - нет, потому что он быстро их разыщет. Конкретно, потеря будет от 30-50%.

Вы можете предложить свою стратегию, я прогоню ее через программу. В этом смысл рецензирования статьи. Вы готовы ее рассмотреть серьезно и сделать замечания? Будете первым, кто познакомится со статьей.

[EUgeneUS]

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

Этого достаточно для полного исчерпания всех стратегий игры.

Нет, не достаточно.
а) Очевидно: среди Ваших стратегий обстрела ("случайная, по разным "сеткам" и "оптимальная", т.е. выборка лучшего выстрела в каждой ситуации (подходит только для компа)"), нет "комплиментарной" для расстановки по Перельману. Конечно, Ваш третий вариант когда-то научится, что у краев корабли встречаются чаще. Но зачем учиться в том случае, если это известно заранее.
б) менее очевидно: у Вас не доказано, что других стратегий нет (а они есть, как минимум модификации этих - примеры я приводил), и не доказано, что если другие стратегии есть, то они н еболее эффективны, чем те, которые Вы рассматриваете.

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

Игра слишком простая, чтобы искать ее решение в теории игр.

Нет. Простота игры не повод не рассматривать её в рамках теории игр. Кстати, "простота игры" это не синоним простоты правил игры. А тут, похоже, равновесия в чистых стратегиях нет. Но это не точно.

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

А уплотнять можно, только прижимая к бортам.

Нет. Еще можно "прижимать корабли" друг другу плоскими сторонами.

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

то в игре с компом есть смысл прижать однопалубники к куче, но в игре с человеком - нет, потому что он быстро их разыщет.

Тут вопрос не в том, с кем ведется игра - с человеком или с компом, а в наличие или отсутствии знания о выборе стратегии противником.

-- 17.03.2021, 20:38 --

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

Вы можете предложить свою стратегию, я прогоню ее через программу.

Исключительно, чтобы удовлетворить моё любопытство из школьных времен

Первая стратегия расстановки:
1. Либо максимально плотно упаковываем 6 крупных кораблей в одном из четырех углов.
2. Либо максимально плотно упаковываем 6 крупных кораблей вдоль бортов.
3. Вариант из пяти возможных (в одном из четырёх углов и вдоль бортов) выбирается случайно.
4. На оставшихся клетках случайно располагаем четыре одноклеточных.

Вторая стратегия расстановки:
1. Либо максимально плотно упаковываем 6 крупных кораблей и три одноклеточных в одном из четырех углов.
2. Либо максимально плотно упаковываем 6 крупных кораблей и три одноклеточных вдоль бортов.
3. Вариант из пяти возможных (в одном из четырёх углов и вдоль бортов) выбирается случайно.
4. На оставшихся клетках случайно располагаем один одноклеточный.

Первая стратегия обстрела (против первой стратегии расстановки):
1. Пока никого не найдено - долбим сеткой с шагом 4 (то есть между выстрелами - три клетки) от случайного угла, пока не попадем.
2. Если не попали - сужаем шаг сетки до 2-х и снова долби вдоль краев, пока не попадем
3. Как попали - убиваем в кого попали. Дальше обстреливаем соседние с убитым клетки.
(так убьем 6 крупных кораблей).
4. После чего случайными выстрелами ловим одноклеточных на оставшихся свободных клетках.

Вторая стратегия обстрела (против второй стратегии расстановки):
1. Пока никого не найдено - долбим сеткой с шагом 4 (то есть между выстрелами - три клетки) от случайного угла, пока не попадем.
2. Если не попали - сужаем шаг сетки до 2-х и снова долби вдоль краев, пока не попадем
3. Как попали - убиваем в кого попали. Дальше обстреливаем соседние с убитым клетки.
(так убьем 6 крупных кораблей и три одноклеточных).
4. После чего случайными выстрелами ловим одного одноклеточного на оставшихся свободных клетках.

Посчитать среднее число выстрелов до убития всех кораблей.

-- 17.03.2021, 20:40 --

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

В этом смысл рецензирования статьи.

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

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

Вы готовы ее рассмотреть серьезно и сделать замечания? Будете первым, кто познакомится со статьей.

Нет. Не являюсь действующим\остепененным учёным и не могу рецензировать научные статьи.

[komand]

Цитата:

Нет, не достаточно.
а) Очевидно: среди Ваших стратегий обстрела ("случайная, по разным "сеткам" и "оптимальная", т.е. выборка лучшего выстрела в каждой ситуации (подходит только для компа)"), нет "комплиментарной" для расстановки по Перельману. Конечно, Ваш третий вариант когда-то научится, что у краев корабли встречаются чаще. Но зачем учиться в том случае, если это известно заранее.
б) менее очевидно: у Вас не доказано, что других стратегий нет (а они есть, как минимум модификации этих - примеры я приводил), и не доказано, что если другие стратегии есть, то они н еболее эффективны, чем те, которые Вы рассматриваете.

Есть, она рассматривается отдельно. Как в случайном обстреле, так и в "сначала убиваем все 6 кораблей, потом ищем оставшиеся 4 однопалубники". Кстати, кроме перельмановской, есть еще одна плотная "упаковка", тоже дает 60 свободных полей.
В рамках программы я рассматривал самые разные размещения, но они одинаковы, если одинаково число оставшихся свободных полей. То есть разные начальные позиции отличаются только числом свободных полей. Еще надо учесть, конечно, что при плотной "упаковке" кораблей их можно быстро найти.

Цитата:

Нет. Еще можно "прижимать корабли" друг другу плоскими сторонами.

Можно. Это тоже рассматривается. Но менее эффективно, чем к бортам. Еще раз поймите, что разные расстановки кораблей отличаются только числом оставшихся свободных полей. Или предложите свою расстановку, я прогоню через программу, дам среднее число попыток для выигрыша. Пока ничего лучше, чем прижать в борту (или упаковать совсем плотно) не было найдено.

Цитата:

Тут вопрос не в том, с кем ведется игра - с человеком или с компом, а в наличие или отсутствии знания о выборе стратегии противником.

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

Ваши расстановки я уже проверил.
1. Однопалубники нет смысла вовлекать в "упаковку", невыгодно.
2. "Вдоль бортов" - это и есть "упаковка", но не полная, рассмотрено.
По поводу обстрела - ловим сеткой 4-палубные ("сетка-4"), потом 3-х, потом 2-х - проверено. Есть более оптимальная "сетка-3", которая ловит сразу 4-х и 3-х палубные, но ее преимущество по сравнению с "сеткой-4" минимальное.

В целом, дискуссия выходит неинтересной, потому что все эти варианты я давно рассмотрел. Если вы будете рецензировать статью, продолжим, иначе мне просто неинтересно все это разбирать.

[EUgeneUS]

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

ловим сеткой 4-палубные ("сетка-4"), потом 3-х, потом 2-х - проверено.

Тут у меня возникает когнитивный диссонанс.
"Сетка-4" легко дополняется сразу до "сетки-2". А вот последовательное дополнение "стека-4" $\to$ "сетка-3" $\to$ "сетка-2" выглядит весьма затратным.

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

Еще раз поймите, что разные расстановки кораблей отличаются только числом оставшихся свободных полей.

Если противник ничего не знает о стратегии расстановки и каждую игру играет "с чистого листа", считая расстановку случайной - то да. В противном случае - нет.

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

Если противник не знает о таком расположении однопалубников, вы выигрываете, но мало. Однако если он знает, тогда вы проигрываете, и очень много.

Вот это как раз и указывает на то, что равновесия в чистых стратегиях может и не быть.

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

В целом, дискуссия выходит неинтересной,

Да, пожалуй.

[komand]

Цитата:

Нет. Не являюсь действующим\остепененным учёным и не могу рецензировать научные статьи.

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

[Padawan]

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

Игра слишком простая, чтобы искать ее решение в теории игр.

Все-таки как раз с точки зрения теории игр (насколько я её знаю) игра "Морской бой" очень сложная. По крайней мере, если не пытаться её упрощать. Начнем с того, что является стратегией игрока? Расстановка кораблей -- это понятно. Но что такое стратегия обстрела?

[mihaild]

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

А тут, похоже, равновесия в чистых стратегиях нет.

Очевидно нет: если мы ставим корабли детерменированно, то противнику выгодно стрелять ровно по ним, а нам тогда выгодно переставить.

[komand]

Padawan в сообщении #1509928 писал(а):

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

Игра слишком простая, чтобы искать ее решение в теории игр.

Все-таки как раз с точки зрения теории игр (насколько я её знаю) игра "Морской бой" очень сложная. По крайней мере, если не пытаться её упрощать. Начнем с того, что является стратегией игрока? Расстановка кораблей -- это понятно. Но что такое стратегия обстрела?

Стратегии обстрела две: случайная и по системе. Система имеет небольшое преимущество из-за того, что выгодно сначала искать большие корабли из-за их "ореола" или "мертвой зоны". Это простые "сетки", с помощью которой 4-х палубный гарантировано ловится за 24 хода (в среднем за 13,1, а если случайно, то требуется 20,7 попыток). И, как вершина стратегии обстрела, "оптимизация", "Каждый выстрел делается в место наиболее вероятного расположения оставшихся кораблей", но она реализуется только для компа.

[mustitz]

А зачем брать сразу 10x10, если можно взять 3x3 c одним двухпалубным, найти точное решение в терминах теории игр и посмотреть, насколько согласованный результат даст Ваш метод? Потом можно взять 4x4 с однопалубным и двухпалубным и т. п. И выводы проверяться сами собой.

[EUgeneUS]

mihaild в сообщении #1509930 писал(а):

Очевидно нет: если мы ставим корабли детерменированно, то противнику выгодно стрелять ровно по ним, а нам тогда выгодно переставить.

Рассматривать в качестве чистой стратегии расстановки конкретную позицию это, конечно, идеологически верно. Но путь тупиковый из-за огромного количества вариантов.

Padawan в сообщении #1509928 писал(а):

Расстановка кораблей -- это понятно. Но что такое стратегия обстрела?

Если в качестве чистой стратегии рассматривать конкретную позицию (см. выше), то логично в качестве чистой стратегии обстрела рассматривать конкретную последовательность выстрелов, которых будет $100! \approx 10^{158}$

ИМХО, перспективным выглядит такой путь
а) сконструировать некоторое количество "элементарных" смешанных стратегий. Каждая из которых покроет большое количество чистых, условно эквивалентных, стратегий. Как для расстановок, так и для обстрелов. По сути это будут некоторые алгоритмы расстановок\обстрелов со стохастической составляющей.
б) и уже в рамках этих стратегий искать "чистое" или смешанное решение.
Путь, конечно, тернист. Но хоть какой-то свет в конце тоннеля есть.
ТС по нему и пошёл.

-- 18.03.2021, 20:33 --

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

Стратегии обстрела две: случайная и по системе.

Вы используете слово "стратегия" не в том смысле, что уважаемые mihaild и Padawan.
У Вас "стратегий" обстрела две, потому что Вы два алгоритма ведения огня рассматриваете.
А уважаемые mihaild и Padawan говорят о чистых стратегиях в терминах теории игр. Тогда чистых стратегий ведения огня $\approx 10^{158}$, сильно больше, чем атомов в видимой части Вселенной.