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

[grizzly]

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

Как они вычисляют число позиций, не очень понял. Но точно не для 10 кораблей на поле $10\times10$

Они считают для любого количества кораблей от 0 до 10 на поле $10\times10$. И интуиция мне подсказывает, что они считают абсолютно точно. Только набор кораблей у них не такой. Набор из всех 10 кораблей выглядит там вот так: 4 корабля по 2 клетки, 3 по 3, 2 по 4 и 1 по 5 (об этом указано в шапке таблицы). Очевидно, что количество вариантов для такого набора намного меньше. Но 6 порядков? Теперь я склонен сомневаться в том, что Ваша программа считает правильно.

Попытайтесь посчитать своей программой либо их полную конфигурацию и проверить, получится ли 26509655816984 вариантов (хотя я сомневаюь, что не оптимизированный под всякие симметрии алгоритм сможет посчитать это за разумное время), либо какую-нибудь часть их конфигурации, например 1 корабль по 4 клетки, 2 по 3 и 3 по 2. Должно получиться в точности 55828223540 (это уже должна быть посильная по вычислительной сложности задача, а если нет, то можно взять набор кораблей ещё чуть попроще).

Я посмотрел за пару минут Вашу критику их статьи и потратил примерно такое же время на беглый просмотр самой статьи. У меня не сложилось впечатления, что Вы поняли статью настолько, чтобы иметь моральное право её так сильно критиковать :)

[komand]

grizzly в сообщении #1512773 писал(а):

Я посмотрел за пару минут Вашу критику их статьи и потратил примерно такое же время на беглый просмотр самой статьи. У меня не сложилось впечатления, что Вы поняли статью настолько, чтобы иметь моральное право её так сильно критиковать :)

У них статья имеет заголовок: "Оптимальная стратегия для игры в морской бой". А где она, эта "оптимальная стратегия"? Где перебор стратегий, доказательство, что он полон, выбор лучшей и доказательство, что она лучшая? Вместо этого идет разбор среднего кол-ва ходов в игре (доя поля $10\times10$). Какая польза от этого игроку? Т.е. я согласен, что статья полезная. У меня претензии к названию.

grizzly в сообщении #1512773 писал(а):

Попытайтесь посчитать своей программой либо их полную конфигурацию и проверить, получится ли 26509655816984 вариантов (хотя я сомневаюь, что не оптимизированный под всякие симметрии алгоритм сможет посчитать это за разумное время), либо какую-нибудь часть их конфигурации, например 1 корабль по 4 клетки, 2 по 3 и 3 по 2. Должно получиться в точности 55828223540 (это уже должна быть посильная по вычислительной сложности задача, а если нет, то можно взять набор кораблей ещё чуть попроще).

Я пока не понимаю, как они считают конфигурации, а без этого нет смысла проверять: при несовпадении непонятно, чей алгоритм неверен.

grizzly в сообщении #1512773 писал(а):

Но 6 порядков? Теперь я склонен сомневаться в том, что Ваша программа считает правильно.

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

[Geen]

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

У меня претензии к названию.

А что именно Вы называете "оптимальной стратегией", и что Вы называете "стратегией"?...

[komand]

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

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

У меня претензии к названию.

А что именно Вы называете "оптимальной стратегией", и что Вы называете "стратегией"?...

Есть игра, в ней есть стратегия: как победить противника. Оптимальная стратегия - как победить при лучших ответах противника. Если более конкретно к игре "морской бой", то понятное объяснение, как оптимально расставлять свои корабли и как обстреливать чужие с количественными оценками.
В приведенной статье я не увидел ничего о том, как же мне выиграть в этой игре.

[Sender]

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

Я пока не понимаю, как они считают конфигурации

Вроде из этого не делается тайны. По ссылке говорится:

Цитата:

The table assumes that ships cannot be placed adjacent to one another, though not all versions of the game use this rule.

И двухпалубный корабль на поле 10x10 у них размещается 180 способами, мне кажется, этого вполне достаточно, чтобы понять принцип.

[komand]

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

И двухпалубный корабль на поле 10x10 у них размещается 180 способами, мне кажется, этого вполне достаточно, чтобы понять принцип.

Для одного корабля можно посчитать аналитически: $N(N-K+1)\times2$, где N - сторона поля, K - размер корабля. Для поля $10\times10$ получаем $10\times(10-2+1)\times2=180$. Сложность в том, как они высчитывают касания множества кораблей.
Но в данный момент я посчитал свою программу для простейших случаев (поля от $3\times3$ до $10\times10$ с одним 2п и 3п кораблем), она выдает неверные результаты. Тем более она врет на полном флоте. Так что я, наверное, признаю поражение в высчитывании всех конфигураций и вернусь к оценкам $10^{16}$ для полного флота.

[grizzly]

Посмотрел статью. Оптимальная стратегия там дана в виде Алгоритма 2, а не в виде "человеческого" описания. Она идеальна, но бесполезна для большой сетки, поскольку работает слишком медленно. Для неё дана оценка снизу, которая говорит, что в среднем потребуется не меньше чем 30,8 выстрелов для победы на случайном размещении их варианта набора кораблей (весьма упрощённого -- всего 5 кораблей, без одиночных).

Далее на Рисунке 10 приводится простая "человеческая" стратегия (для такого же набора кораблей), которая даёт не более чем 58,7 выстрелов (в среднем). Примерно такой стратегии и придерживался бы нормальный игрок, наверное (может, не точно такой, но примерно с такой же эффективностью). Потом эта стратегия чуть улучшается (ещё на пару выстрелов). Предполагается, что это ещё не предел "человеческих" стратегий.

Всё это вряд ли применимо для игры с одиночными кораблями. Но в той постановке вопроса игра с одиночными кораблями вряд ли вообще интересна (по понятным причинам).

[Sender]

Удалось скомпилить и запустить их программу для подсчёта количества позиций. Для флота по умолчанию на поле 10x10 (конфигурация german) получилось значение как в статье(последняя строка таблицы): $26509655816984$.
По аналогии с

Используется синтаксис Haskell

{- |
The main configuration given
in <https://de.wikipedia.org/wiki/Schiffe_versenken>.
-}
german :: T
german = fromList [(5,1), (4,2), (3,3), (2,4)]

{- |
The main configuration given
in <https://en.wikipedia.org/wiki/Battleship_(game)>.
-}
english :: T
english = fromList [(2,1), (3,2), (4,1), (5,1)]

добавил конфигурацию

Используется синтаксис Haskell

russian :: T
russian = fromList [(4,1), (3,2), (2,3), (1,4)]

и пересчитал для неё. Получилось $29688735661308480$. Правда, там однопалубные корабли могут располагаться вертикально и горизонтально, но это легко решается делением числа позиций на $16$. Таким образом, итоговое число позиций $1855545978831780\approx 1.85\cdot 10^{15}.$

[komand]

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

и пересчитал для неё. Получилось $29688735661308480$. Правда, там однопалубные корабли могут располагаться вертикально и горизонтально, но это легко решается делением числа позиций на $16$. Таким образом, итоговое число позиций $1855545978831780\approx 1.85\cdot 10^{15}.$

Ну и буду пользоваться этой оценкой. Хотя у меня было ощущение, что число всех конфигураций флота на поле $10\times10$ ближе к $10^{16}$

[Sender]

Куда уж ближе?

[grizzly]

Вот что могло бы быть действительно интересно и полезно с моей точки зрения в рамках данной темы:

Найти (предложенным автором темы методом) какую-то более эффективную "человеческую" стратегию (для их же набора из 5 кораблей) и на всех вариантах (около 2 млрд. конфигураций) прямым пересчётом доказать, что эта найденная стратегия действительно лучше опубликованной в статье верхней оценки. Если бы такое удалось, это был бы не просто вычислительный шаг вперёд, а как раз методологический (найти метод нахождения метода). Получится ли что-то из этого? Не знаю, но уверен, что усилия в этом направлении были бы полезны и (в случае хоть какого-то успеха) достойны публикации.

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

[komand]

grizzly в сообщении #1512810 писал(а):

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

Именно. Более того, их наличие практически сравнивает все стратегии - в этом основной вывод моей статьи. А все компьютерные оптимизированые стратегии мало отличаются по эффективности от простых "сеток", а самое главное, неприменимы человеком.

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

Куда уж ближе?

Все-таки разница на порядок. Вы посчитали для конфигурации 1п - 4, 2п - 3, 3п - 2, 1п - 1?

[Sender]

Кстати, в английской и немецкой версиях игры однопалубных кораблей нет вовсе.

[komand]

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

Кстати, в английской и немецкой версиях игры однопалубных кораблей нет вовсе.

Что резко увеличивает значимость любой стратегии поиска кораблей от больших к малым. Для 1п вообще нет никакой стратегии.

Сегодня вечером окончательно отредактирую статью и опубликую здесь.

[grizzly]

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

Кстати, в английской и немецкой версиях игры однопалубных кораблей нет вовсе.

Так и я о том же. И задача для этих версий куда более содержательна (а сама игра между двумя людьми должна быть намного интереснее -- стратегически).