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

[tonven]

Уточню свою мысль:

Вторая позиция является классической, при игре с дополнительным выстрелом за попадание. Последний 1-катер может расположиться на 19 зелёных полях.
При ваших правилах выгодно пожертвовать всем флотом, случайно выставив на 1-й позиции 1-катер на любое из 48 клеток.

[komand]

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

Вторая позиция является классической, при игре с дополнительным выстрелом за попадание. Последний 1-катер может расположиться на 19 зелёных полях.

"Классической" является указанная вами позиция без расстановки 1п (останется поле 10x6 клеток). Однопалубники не стоит так плотно размещать, ибо:
"Можно ли улучшить этот результат? Расположим 4 корабля в углу (90,92,70,72) как на рис. 13. Случайный компьютерный алгоритм: 38,2 ходов. Другие подобные варианты с 44 свободными клетками дают примерно тоже самое. Выигрыш ~2 хода. Против компьютерного случайного алгоритма смысл есть, против человека наоборот: после обстрела углов поля 10x6 он выиграет сразу или (если 4-й корабль вы расположите случайно) получит существенное преимущество ~ 30% ходов. Потому что на оставшихся 48 клетках ему придется найти только 1 корабль, а для этого нужно ~24,5 ходов. Так же малоперспективны попытки расположить 1 или 2-х корабля по углам, остальные 1–2 случайно (против человека). См. график. Для одного корабля нужно 30,5 ходов, как и в теории. Для поражения 4 кораблей нужно меньше ходов, чем для 3-х. А для поиска 6 — столько же, что и для одного"
Если вы раскидываете четыре 1п по полю 10x6, противнику нужно ~35,6 ходов для их уничтожения. А если он обнаружил один из однопалубников или несколько сразу (потому что вы прижали их к бортам или к "упаковке"), шансы на выигрыш у него резко возрастают. Зависимость кол-ва ходов от кол-ва 1п кораблей нелинейная.
График:


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

[tonven]

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

Однопалубники не стоит так плотно размещать

На доске $10\times 10$ приходится учитывать границы, когда "упакованный" 1п освобождает остальным "бродягам" больше клеток для размещения.
Но переходя к большим размерам, можно смоделировать в рамках теорвера:
Пусть имеется $N$ свободных клеток. Перемешиваем их. И начинаем стрельбу слева. Тогда 1 корабль гибнет в среднем через $N/2$, 2 корабля через $2N/3$, ..., $k $ кораблей через $kN/(k+1)$ ходов. Ваш тезис верен.

[Someone]

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

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

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

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

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

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

[komand]

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

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

У меня ощущение, что программа учитывает симметрию, хотя как, не знаю. Что-то уж мало получается, раньше оценка была в 8 раз больше, $10^{16}$. Похоже, что "8" - это как раз учет симметрии.
И еще. Если мои расчетные величины умножать на 2,45, получается их числа. С точностью до 3-го знака. Почему 2,45 - не знаю.

[Sender]

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

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

Насколько я могу судить, симметрии не учитываются, т.к. для одного двухпалубного корабля в программе получается 180 вариантов размещения.(а для однопалубного - 200). Я, впрочем, не ручаюсь за отсутствие ошибок в самой программе...

[Someone]

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

а для однопалубного - 20

$200$?

[Sender]

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

$200$?

Да, исправил уже, пардон.

[komand]

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

для однопалубного - 200

Что-то многовато. Вроде всего 100 должно быть?

[Sender]

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

Что-то многовато. Вроде всего 100 должно быть?

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

Правда, там однопалубные корабли могут располагаться вертикально и горизонтально

[Yadryara]

Конечно 100.

1п: 100 — 15
2п: 180 — 25
3п: 160 — 20
4п: 140 — 20
5п: 120 — 15

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

-- 07.04.2021, 18:54 --

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

Правда, там однопалубные корабли могут располагаться вертикально и горизонтально,

Ага. А ещё их можно на попа поставить

[Sender]

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

Ага. А ещё их можно на попа поставить

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

[komand]

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

Правда, там однопалубные корабли могут располагаться вертикально и горизонтально

Круто! Я хочу посмотреть на это чудо )

Перекодирую статью из DOC в PDF. Скоро будет.

-- 07.04.2021, 19:33 --

Готово. Статья тут.
10 листов, 32 тыс. знаков, 18 иллюстраций.

[Sender]

komand, моя заслуга при расчёте позиций минимальна, я всего лишь взял готовую программу, выложенную по ссылке, указанной grizzly в сообщении https://dxdy.ru/post1512752.html#p1512752.

[EUgeneUS]

1.

Цитата:

Ход — ваши действия до передачи хода противнику

Рекурсия не нужна.

2. Не очень понятно, как устроен "случайный обстрел".
После попадания ("ранил") следующий выстрел как делается? Тоже случайно или по какой-то методе добиваем? Что такое "свободная клетка" (этого нет в терминах)?

3. И ещё такой тонкий момент. Вы же минимизируете мат ожидание количества ходов?
Тогда это не гарантирует максимизации вероятности выигрыша партии.
Например, может случиться так, что мат. ожидания количества ходов до выигрыша у разных игроков одинаковые, но один игрок выигрывает чаще.