Оглавление:
Часть 1 : Введение.
Часть 2 : Генерация флота, число позиций.
Часть 3 : Случайное расположение/обстрел и по системе.
Часть 4 : Системы размещения флота.
Часть 5 : Выводы
Полная статья PDF: Копия 5 частей здесь, только проще с отображением формул.
Предыдущая часть
10x10, 1п
Для проверки программы и введения некоторых понятий посчитаем вероятность поражения 1п на поле 10x 10. По теории вероятностей μ=50,5 ходов.
Получаем равномерное распределение (см. рис. 1) с отклонением менее 0,001 при 10^6 прогонах (т.е. программа случайно ставила 1п на поле, а потом пыталась его потопить. И так миллион раз). Вероятность поразить корабль с первого выстрела (в данном случае выстрелы совпадают с ходами) или с последнего одинакова и сходится к μ=0,01. В дальнейшем, если не указано особо, каждый раз проводилось 10^7 испытаний, искомая величина сходилась с точностью не менее 0,001. И, если модель простая, сравнивалось с теоретической величиной.
Смысла в этом разделе никакого, просто картинка понравилась и рассуждения умные 😊 .
Генерация флота
Расположим случайно на поле 10x 10 полный флот, 10 кораблей.
Проверено, что при большем кол-ве генераций (от 10^7 ) вероятность занятости любой клетки кораблем равна, ~0,0100±0.0001 (μ=0,01). Т.е. при случайном расположении кораблей (если у вас нет никакой информации о расположении) можно вести обстрел в любом порядке, вероятность первого попадания одинакова.
Это не значит, что корабль с равной вероятностью окажется в любой клетке. Остановимся здесь подробней. Дело в том, что во многих исследованиях демонстрируется плотность распределения кораблей, на основании которой делаются выводы оптимальности стрельбы. Например Thevirtuosi в модели, похожей на нашу, утверждает, что в центре корабль обнаружится с большей вероятностью, чем в углу, т.е. начинать обстрел лучше с центра. Здесь даже можно увидеть, как эта вероятность меняется по мере установки кораблей (или см. рис 5 ). Но у нас три существенных возражения:
1. В дальнейшем мы увидим, что оптимально сначала найти большие корабли; после этого поле разбивается на небольшие войды, в которых выгоднее искать оставшиеся, а не пользоваться матрицей плотности. Уже здесь рассматриваемая модель дает сбой, как признает сам автор: «…линейная модель не знает, как на основании расположения промахов [войды] разместить корабль».
2. Кроме того, если следовать тактике уплотнения кораблей (см. далее), то вероятность обнаружения корабля в углу и на бортах максимальна. По матрице плотности все наоборот.
3. После обнаружения всех больших кораблей начинается поиск 1п, для которых плотность распределения везде одинакова, и модель отказывает совсем.
Т.е. модель с плотностью распределения оптимальна только если противник ставит корабли полностью случайно, а и вы стреляете полностью случайно и нет 1п — см. раздел стрельбы по системе.
Число клеток, не занятых кораблями после генерации ~17,26, поэтому уже на ~9 ходу вы должны попасть в какой-нибудь корабль.
Каждый раз генератор псевдослучайных чисел ( вихрь Мерсенна , использовался этот ) выдает др. последовательность, что гарантирует отсутствие корреляций между генерациями: число позиций намного больше выборки (см. след раздел).
Среди 10^7 позиций ни разу не было найдено повторяющихся (проверено сотни раз).
Число легальных позиций в игре
Это число нужно для оценки представительности наших выборок, т.е. какую часть всех возможных позиций в игре мы обсчитываем при каждой генерации. Также полезно для понимания вычислительной сложности задачи построения полного «дерева игры» или, что тоже самое, нахождения лучшего хода в любой позиции на основе полной информации об игре (см. описание «оптимизации» в разделе «обстрел по системе»).
Пропускаем этот раздел для краткости, можете посмотреть в полной статье. Здесь приведем только окончательный результат: число легальных позиций в игре 1,86 x 10^15 .
Спасибо Sender за расчеты по другому алгоритму (оценка близка до трех знаков) а также Someone за ценные указания. В wikiHaskell можно посмотреть число позиций для разного флота.
Замечание. Для современного десктопа со скоростью ~10^5 игр в секунду для полного обсчета всех игр потребуется тысячи лет, что мало реализуемо на практике. Даже для современного суперкомпьютера потребуются часы. О стоимости таких расчетов даже не стоит заикаться 😊