Дальнейшая генерация случайных размещений кораблей и сохранение их в файлы лишь для целей определения соотношения количества допустимых комбинаций к общему количеству координат кораблей - это стрельба из пушки по воробьям. Даже один прогон mc_ship_placement.c дает хорошую оценку этого соотношения (примерно 1:3900). Однако нам все же нужны эти комбинации, и как можно больше, потому что с ними можно делать очень интересные вещи!
В сообщении №17 я описал алгоритм, который позволяет получить точные значения вероятности попасть в корабль для каждой клетки. Для этого необходимо перебрать все допустимые размещения кораблей, представив каждое из таких размещений в виде двоичной карты (1 - клетка занята, 0 - клетка свободна). Затем сложить все эти двоичные карты, в результате получится матрица чисел. Разделить ее на количество рассмотренных комбинаций размещения кораблей - и получится искомая матрица вероятностей.
Реализовать этот метод на современных компьютерах невозможно из-за того, что множество допустимых размещений кораблей слишком велико (в сообщении №26 была получена оценка этого числа в 5.42E+17). Но можно получить приближенный результат опять-таки методом Монте-Карло!
Если мы будем перебирать не все множество допустимых размещений кораблей D, а лишь случайную выборку из него (т.е. некоторое количество допустимых размещений, выбранных из общего множества равномерно случайным образом) - то сумма двоичных карт таких случайных выборок будет сходиться к тому же результату, который получается путем полного перебора. Это утверждение доказывается в рамках общей теории семейства методов Монте-Карло. Для нашего случая я пока не буду его конкретно доказывать, но мы может быть вернемся к этому вопросу позже, особенно в случае, если появятся сомнения. Но пока что их нет, моя практика совпадает с предсказаниями теории.
Чтобы осуществить вышеописанное, нам нужно генерировать случайные размещения кораблей, равномерно распределенные по множеству D всех допустимых размещений. Если мы пронумеруем по порядку все элементы множества D, то есть поставим в соответствие каждому элементу этого множества натуральное число от 1 до size(D) - то тогда дальше становится легко. Генерируем случайное число с равномерным распределением в диапазоне от 1 до size(D) и находим соответствующее ему расположение кораблей. Полученные таким образом расположения будут равномерно распределены по D.
Проблема в том, что мы на данный момент не получили способа нумерации допустимых комбинаций размещения кораблей по порядку, так что вышеописанный способ неприменим. Но можно показать, что случайные допустимые расположения кораблей, полученные mc_ship_placement.m, равномерно распределены по D.
mc_ship_placement.m генерирует расположения, равномерно распределенные по множеству U всех их координат, и отбирает из них только те комбинации, которые принадлежат множеству D. Но так как D является подмножеством U - то эти отобранные комбинации являются равномерно распределенными и по D. Поэтому комбинации, сгенерированные и сохраненные в файлы программой mc_ship_placement.m, могут быть использованы для расчета карты вероятностей попадания в корабли при выстрелах.
Прилагаю карту вероятностей, рассчитанную мной для необстрелянного поля на основе сложения 843076 допустимых комбинаций размещения кораблей, полученных mc_ship_placement.c. Этот результат является довольно "чистым" и "симметричным", поскольку было учтено довольно большое число случайных комбинаций. Ранее я получал ту же карту только на основе 2000 и 80000 комбинаций, и она имела тот же вид, только была более зашумлена. Так что метод Монте-Карло для ее расчета действительно сходится к некоторому пределу.
Любопытно, не правда ли? Максимальные шансы попасть в корабль имеются у границ поля, но не в углах! Излюбленное место для размещения кораблей опытных игроков, было найдено моим методом без каких-либо указаний на предпочтения игроков и их стратегии!
Ответить с цитированием
