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

[Sender]

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

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

Да (у вас опечатка, там 4п - 1, конечно).

[komand]

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

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

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

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

К сожалению, самая распостраненная версия игры у нас именно с 1п. И понятное дело, читателям прежде всего интересна именно она.

-- 04.04.2021, 17:51 --

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

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

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

Да (у вас опечатка, там 4п - 1, конечно).

Да, конечно, 1палубных - 4 штуки, 2п -3, 3п - 2 и 4п - 1. Базовая версия игры в РФ. Спасибо за ваш расчет, укажу в статье.

[tolstopuz]

Вот здесь был контест на C# по поиску стратегии, есть исходники: https://stackoverflow.com/questions/163 ... tleship-ai.
Правда, некоторые стратегии уже оптимизированы на отсутствие однопалубных кораблей.

Вот здесь пример работы стратегии, строящей плотность вероятности по всему полю: https://www.datagenetics.com/blog/december32011/. Исходника нет, но, думаю, некоторые из стратегий по первой ссылке работают так же.

Ну и еще одна статья про стратегию, основанную на суперпозиции плотностей вероятности положения отдельных кораблей: http://thevirtuosi.blogspot.com/2011/10 ... eship.html.

[komand]

tolstopuz в сообщении #1512824 писал(а):

Вот здесь был контест на C# по поиску стратегии, есть исходники: https://stackoverflow.com/questions/163 ... tleship-ai.
Правда, некоторые стратегии уже оптимизированы на отсутствие однопалубных кораблей.
Вот здесь пример работы стратегии, строящей плотность вероятности по всему полю: https://www.datagenetics.com/blog/december32011/. Исходника нет, но, думаю, некоторые из стратегий по первой ссылке работают так же.
Ну и еще одна статья про стратегию, основанную на суперпозиции плотностей вероятности положения отдельных кораблей: http://thevirtuosi.blogspot.com/2011/10 ... eship.html.

Да, спасибо, я смотрел эти работы раньше. Хотя уже после начала работы, а так может быть не потратил лишнее время на тупиковые поиски. Спасибо!

[Someone]

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

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

Да, видимо, не зря у меня сомнения возникли…

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

Перемножая полученные числа, получаем число генерируемых по описанным правилам позиций, большинство которых, однако, не удовлетворяют правилам из-за пересечений и касаний кораблей:

$$94\,109\,400\cdot 2\,851\,560\cdot 19\,040\cdot 140=715\,336\,685\,929\,958\,400\,000\approx 7{,}2\cdot 10^{20}.$$

Было бы хорошо, чтобы это кто-то проверил. Меня терзают неясные сомнения. Поскольку, если численные результаты komand верны, и у него пригодной оказывается одна позиция из $1/(7{,}588\cdot 10^{-6})\approx 132\,000$, то у меня должна быть пригодной одна позиция из $230$. Мне кажется, что это слишком хорошо.

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

Количество размещений, генерируемых моим методом, равно (после некоторых упрощений)

$$A_{100}^4\cdot 2(A_{90}^3+A_{90}^2A_{90}^1)\cdot(2A_{80}^2+A_{80}^1A_{80}^1)\cdot 2A_{70}^1=715\,336\,685\,929\,958\,400\,000\approx 7{,}2\cdot 10^{20}.$$

Но здесь много повторов, поскольку генерируются все перестановки однотипных кораблей. Чтобы исключить перестановки, нужно все размещения $A_n^m$ заменить на сочетания $C_n^m$:

$$C_{100}^4\cdot 2(C_{90}^3+C_{90}^2C_{90}^1)\cdot(2C_{80}^2+C_{80}^1C_{80}^1)\cdot 2C_{70}^1=6\,674\,691\,502\,432\,800\,000\approx 6{,}675\cdot 10^{18},$$

всего примерно в $2$ раза больше вашей эмпирической оценки

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

$ P \times K = 3,11\times10^{18}$, …

Стало быть, приведённая мной оценка завышена в $\frac{6\,674\,691\,502\,432\,800\,000}{1\,855\,545\,978\,831\,780}\approx 3\,597$ раз. Это больше похоже на правду.

[komand]

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

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

Кстати, если чуть поправить мою теорию, то наши данные совпадут.
Итак, моя модель предполагала, что 10 кораблей могут размещаться $100^{10}$ способами. И каждый корабль (кроме 1п) может еще в 4 направлениях, поэтому добавляем множитель $4^6$. Коэффициент (К), вычисленный программой = "число легальных позиций" / " все позиции" = $7,58839^{-6}$, откуда я получал число легальных позиций, как $100^{10}$\times 4^6 \times $7,58839^{-6}$ $ = 3,1082^{18}

Однако если использовать немного другую модель: каждый корабль (кроме 1п) может размещаться в 4 направлениях, в среднем в 2.45 направлении. Почему именно 2,45, не знаю. Теперь, если поставить это число в модель вместо $4^6$, получим $100^{10}$ \times 2.45 \times $7,58839^{-6}$ = 1,85916 \times 10^{15}, что довольно близко к вашему $1,855\times 10^{15}.
Только, боюсь, это не вычисления, а подгонка ()
-- 04.04.2021, 19:23 --

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

Стало быть, приведённая мной оценка завышена в $\frac{6\,674\,691\,502\,432\,800\,000}{1\,855\,545\,978\,831\,780}\approx 3\,597$ раз. Это больше похоже на правду.

Я проверил модель на тестовых полях, на которых можно точно вычислить число размещений: на поле $N\timesN$ и одного корабля длиной M оно равно $N\times(N-M+1)\times2$
По моей-вашей модели число размещений в таких случаях будет как $N \times N \times 4$ \times K, где K - коэффициент "число легальных размещений" / "все размещения".
Так вот, теория и модель для 2п хорошо согласуются только в том случае, если в этой формуле подставить вместо "4" другое число: 2,45:
$N \times N \times 2,45 \times K
И для размещений всего флота, вычисленное Sender (см. выше) коэффициент 2,45 дает совпадение до трех знаков. То есть опять вместо $4^6$ нужно использовать 2,45.
Но вообще, после расчета Sender вопрос о числе размещений флота наверное можно закрыть, он равен $1,85\times10^{15}$
И, если мы наконец закрываем эту многострадальную тему о числе размещений, я наконец поставлю это число в статье, поправлю некоторые выводы и смогу публиковать.

[Yadryara]

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

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

Хотя уникальных способов-то всего 25.

[Sender]

Yadryara в сообщении #1512878 писал(а):

Хотя уникальных способов-то всего 25.

Ну тогда можете итоговое число позиций ещё на $4$ поделить, благо четырёхпалубник позволяет это сделать. С пятипалубником можно было бы делить на $8$.

[komand]

Yadryara в сообщении #1512878 писал(а):

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

Комбинаторный принцип я понимаю, а вот как они вычисляют все расположения, нет. Перебор $10^{15}$ положений кажется слишком велик. И ранее звучали оценки в $10^{17}$ размещений. Возможно их оценка, на два порядка меньшая, как раз учитывает симметрию.

[Sender]

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

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

Если бы учитывали, то двухпалубник у них размещался бы 25 способами, а не 180.

[EUgeneUS]

Yadryara в сообщении #1512878 писал(а):

Хотя уникальных способов-то всего 25.

Вся симметрия уже нарушена нумерацией клеток. Так что уникальных размещений, всё таки 180, а не 25.

[komand]

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

Вся симметрия уже нарушена нумерацией клеток. Так что уникальных размещений, всё таки 180, а не 25.

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

[tonven]

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

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

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

[Geen]

tonven в сообщении #1513172 писал(а):

Но как принято в классике, игрок после попадания делает ещё один выстрел, - и так до промаха.

Это ничего не меняет.

tonven в сообщении #1513172 писал(а):

Здесь полагается, что ходы делаются по очереди: твой выстрел - выстрел противника.

И это тоже не нужно.

[komand]

tonven в сообщении #1513172 писал(а):

Извините, что вмешиваюсь.
Случайно попала на ваш сайт. И удивилась разнообразию тем.

Вмешиваться нужно, для этого тема и создана )

tonven в сообщении #1513172 писал(а):

Отсюда следует простейшая контрстратегия. Первыми выстрелами нащупываем "гавань". В ней вариантов расстановки меньше рандомного. Попадаем в "причальный" корабль. Следующий выстрел делаем по сетке вне гавани. Таким образом, для поиска мелочи мы имеем в 2 раза больше ходов.

К сожалению, не в 2 раза, а все лишь 6 дополнительных ходов. Из средней партии примерно в 35 ходов. Далеко не подавляющее преимущество.
Статья вышла на финишную прямую, опубликую сегодня-завтра. Тогда и поговорим.

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

Это ничего не меняет.

Да, "премия" мало меняет рисунок игры.

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

И это тоже не нужно.

Тут вы совершенно правы. Цитата из моей статьи:

Цитата:

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

Сравните отсюда

Цитата:

"A game of Battleship can be decomposed into two sub-games played in parallel with no interaction. In each sub-game, the opponent places the ships, and the main player tries to sink them as quickly as possible".

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