v .1.32, апрель 2021
Оглавление:
Часть 1: Введение
Часть 2: Генерация флота, число позиций.
Часть 3: Случайное расположение/обстрел и по системе .
Часть 4: Системы размещения флота.
Часть 5: Выводы
Полная статья PDF: Копия 5 частей здесь, только проще с отображением формул.
Аннотация
Есть коротко, прочитав статью, вы станете мастером этой игры :-).
Новый подход к поиску лучшей стратегии игры «морской бой» на основе стохастической компьютерной модели по методу Монте-Карло. Последовательно разбираются начальные расстановки, системы обстрела и даются количественные рекомендации.
Будет много цифр и выкладок. Если все это лень читать, идите сразу к части 5, выводы
Термины и правила
Предполагаем, что вы знакомы с игрой. Если нет, почитайте источники в «обзор литературы». Здесь мы сформулируем термины и правила, используемые в статье.
· Поле — связный прямоугольник, разбитый на клетки, обычно 10x 10.
· Корабль — несколько клеток (палуб) в пределах поля. Корабли прямые, связные, без изгиба. Нельзя касаться друг друга ни бортами, ни углами.
· Палуба (п) — часть корабля, одна клетка. Однопалубный (1п) — корабль в одну клетку, 2п — две и т.д.
· Флот — все корабли. Например, в базовой версии флот состоит из 10 кораблей: 4п — 1, 3п — 2, 2п — 3, 1п — 4.
· Выстрел (попытка) — запрос координаты у противника. Стрельба ведется по очереди.
· Ответы противника. «Мимо» — клетка пустая. «Попал (ранил)» — клетка занята кораблем. «Убил (потопил)» — все клетки корабля уничтожены.
· Ход — ваши действия до передачи очереди противнику.
· Премия — дополнительный выстрел после попадания во вражеский корабль. Не учитывается при подсчете ходов. Примеры (до последовательности было «мимо»):
o «мимо, мимо» — 2 выстрела и два хода;
o «1 выстрел: ранил; премиальный выстрел: мимо; 3 выстрел: мимо» — 3 выстрела, но 2 хода;
o «ранил, ранил, ранил, убил, победа!» — 4 выстрела, но 1 ход.
· Обстрел — последовательность выстрелов. Кто раньше потопил флот противника, тот победил. Ничьих не бывает.
· Расстановка, позиция — начальное (или текущее) положение кораблей.
· Мертвая зона (аура) — клетки вокруг кораблей, куда нельзя ставить др. корабли.
· Координаты: 0–9 по вертикали сверху вниз (первая цифра) и 0–9 по горизонтали слева направо (вторая цифра), так проще для ссылок, см. рис. 7 .
· Войд — пустое связное пространство, неисследованная часть поля противника. В начале игры — все поле, в дальнейшем может быть несколько. Например, на рис. 8 три войда.
· Упаковка — близкое расположение кораблей, см. рис. 10 .
· Свободная клетка — клетка (координата поля), в которую: 1) еще не стреляли; 2) не занята уже потопленным кораблем или его аурой.
Обзор литературы
Игра известна с начала прошлого века, популярная стратегия изложена Я.И. Перельманом в 30-х гг XX века. Изложено например, в б-ке математики или пульсе на mail .ru .
В wikiHow даются вредные советы, типа «не расставляйте корабли близко к друг другу» или «если вы дважды промазали в одном месте игрового поля, на другом участке вероятность снова промазать будет меньше» . Там же говорят бить по центру, «потому что вероятность попадания первого выстрела по кораблю будет выше». Как это сочетается с советом располагать корабли по углам, загадка.
В «Розовом жирафе» сообщают: «известно, что вероятность попадания выше на диагонали» . Откуда? Из википедии : «Выигрышная стратегия состоит в расположении своих кораблей максимально компактно в одном из углов поля» . Это хорошая тактика, но не настолько, как пишет joto .me : «позволяет на 100% обыграть человека, у которого корабли расположены в центре» .
Сайт советов дает тактики обстрела, но нет ответа, какая лучшая. КиберЛенинка пытается аналитически найти лучшую стратегию, но застряла на частных вопросах. Это вообще характерно для математического подхода к проблеме: много выкладок (англ), но нет ответа на главный вопрос игрока: какая стратегия лучше и насколько?
Редкая концентрация ценных мыслей на habr .com : born2fly , impersonalis , agorkov . Неплохо изложено и на КакПросто! . Еще 10 лет назад на форуме Спектрума хотели написать полное «дерево игры». Есть инструкция instructables.com (англ), неплохо разобрано на datagenetics.com (англ). О плотности распределения кораблей (англ). Советую ознакомиться. Большая благодарность авторам: они помогли понять мне многие моменты и вдохновили на написание моей статьи.
Поиграть в игру можно в разных местах, например на блоге CleanJS . Там же опубликован исходный код игры на JS с комментариями. Много вариантов на игроутке . Но не все честные, например самый распространенный на яндексе последний корабль всегда «зажимает».
На dxdy.ru обсуждение данной статьи. В дальнейшем будут ссылки на др. исследования.
Из обзора можно вывести стратегию: располагать свои корабли компактно, обстреливать чужие по системе. Но насколько это выгодно, ответа нет, потому что никто не пытался подробно сравнить разные стратегии игры и дать количественные рекомендации. В обзоре мы видим попытки либо дать общие качественные рекомендации, либо математический разбор каких-то частей игры.
В иностранных источниках используется др. конфигурация игры. Во-первых, чаще всего нет 1п, но есть 5п. Во-вторых, нет «премиального выстрела» и ответа «убил». Вместе эти отличия немало меняют стратегию игры и рекомендации становятся неприменимы для базовой версии игры, принятой в России.
Методы и инструменты
Это скучный раздел про устройство модели игры. Он необходим для обоснования применимости инструментов. Можете его пропустить и сразу заглянуть в «выводы», там всего пара советов. В статье стараемся избегать сложных терминов, но цифр будет много. В этом суть исследования: дать количественные ответы.
Мы используем два инструмента. Первый — анализ на основе теории вероятностей. К сожалению, игра слишком сложна, чтобы дать точные теоретические оценки. Поэтому мы привлекаем второй инструмент — компьютерную модель игры. Она умеет расставлять корабли и «обстреливать» их по заданным критериям. На ней мы протестируем игру очень много раз, добиваясь сходимости результата. Это метод Монте-Карло , разновидность доказательного вычисления в экспериментальной математике: «Вместо того, чтобы использовать комбинаторику, можно просто поставить эксперимент большое число раз и, подсчитав число удачных исходов, оценить вероятность». Подробней для игр от Nick Filatov , на kaper .pro или на вики . Полученный результат будет вероятностным , ошибку укажем.
Обоснуем применимость стохастического метода к игре «морской бой».
После создания позиции ваши действия никак не отражаются на действиях противника. Вы можете сначала обстрелять его поле до победы, потом он ваше. Кто сделал меньше ходов, тот выиграл. Стратегия, дающая шанс сэкономить даже долю хода (в среднем), может быть немалым преимуществом на длинной дистанции (точные цифры см. далее). Это позволяет нам сосредоточится на главном критерии успешности стратегии: кол-ве ходов до победы.
Программа состоит из двух частей: первая расставляет корабли по заданной схеме: количество кораблей, их тип, полностью случайно, или N кораблей прижаты к стенке, или только горизонтальные корабли и пр. В рамках заданного критерия каждая такая расстановка случайна. Отдельно тестировалось равномерность распределения кораблей, отсутствие корреляций при генерации и оценивалось репрезентативность выборки.
Вторая часть обстреливает полученную позицию по заданному критерию: случайный обстрел, по заданным координатам, или др. алгоритму. Эта часть самая важная, она дает искомый результат: сколько нужно ходов до победы. Конечно, в каждой игре результат будет разный. Но, если компьютер сыграет сам с собой миллионы раз, результаты, надеемся, будут сходиться к некой средней величине (в дальнейшем слово «средний» будем заменять для краткости на «~»). Фактические, это оценка математического ожидания (μ). После чего мы строим распределение: какая вероятность победить на 1, 2,…N ходу. Множество симуляций показало, что распределение близко к нормальному, поэтому для упрощения будем брать единственную величину: «среднее кол-во ходов для победы», которое должно сходиться к μ. К примеру, «~35,7 ходов» означает: для заданных критериев расстановки кораблей/обстрела для победы требуется в среднем 35,7 ходов. В чем смысл этого результата? Если вы, к примеру, используете стратегию «~31,9 ходов», а противник «~39,3», в среднем вы будете иметь преимущество 31,9/39,3 ~ 19%, это +10 побед на 100 партий.
Аналитически подобную задачу пытался найти Maxime Audinot в статье «Optimal Strategies against a Random Opponent in Battleship » (для флота с кораблем 5п), но смог указать только верхнюю и нижнюю границы числа, т.к. вычисления оказались слишком сложны.
Пример. Вы делаете ставку на бросок кости d 6. Если выпадет шестерка, вы выигрываете, иначе проигрываете. Легко подсчитать, что μ = 1 /6. Или по-другому: из 100 партий в среднем вы будете проигрывать 83. Можно доказать это по-другому: сыграв много партий; результат по закону больших чисел будет стремиться к μ. Первый способ расчета предпочтителен точностью, но для сложных игр неприменим. Второй способ работает всегда, но не дает точного результата, требует адекватной модели и множество вычислений.
Выбор программной платформы см. в разделе «Заключение». Рассматриваются стратегии, которые человек может применить на практике, вычислительные только упоминаются.