Хочу заметить, что несмотря на довольно долгое время работы моих программ на довольно быстром компьютере, получено было не очень много комбинаций, и еще меньше - легальных. Мои программы нуждаются в переводе на C и оптимизации, чтобы выдавать более точные результаты.
С любовью к вам, Yandex.Direct
Размещение рекламы на форуме способствует его дальнейшему развитию
Переписал программу на Си, чем удалось добиться ее ускорения более чем в 100 раз. Если раньше мне приходилось довольно долго ждать чтобы получить хотя бы 1000 допустимых правилами случайных комбинаций размещения кораблей, то теперь с легкостью удается генерировать десятки тысяч таких комбинаций.
Например, после первого запуска моей программы было перебрано 300 миллионов комбинаций координат кораблей, из них оказалось допустимыми 76944, а соотношение составляет 1:3898.
Программа прилагается. Она является почти идентичным переводом опубликованной ранее программы на Матлабе. Ввиду трудности генерации случайных допустимых размещений кораблей, программа сохраняет сгенерированные легальные комбинации в файл, оставляя возможность дальнейшей обработки этих комбинаций другими программами.
Я не вылизывал сильно эту программу, поэтому думаю, что в рамках языка Си ее можно еще более ускорить, а в перспективе - перевести на ассемблер, с использованием векторных инструкций MMX. Вот тогда ее можно будет запускать на неделю всем сообществом и потом дружно анализировать результаты.
Немного переделал программу, чтобы она крутилась в бесконечном цикле и сохраняла полученные комбинации в файлы.
Пришлось отказаться от библиотечного генератора случайных чисел rand(), так как он имеет слишком малый период повторения последовательности (около 2 млрд). Я написал программу для проверки расположений кораблей, сгенерированных mc_ship_placement.c, на предмет повторений. В пределах одного файла (~77000 комбинаций) повторений не было обнаружено, но вот во втором файле уже пошел повтор. При генерации 300 миллионов размещений кораблей производится в 30 раз больше случайных чисел (по 3 на каждый корабль), что исчерпывает библиотечную последовательность очень быстро.
Я реализовал генератор ran2 из книги William H. Press - "Numerical Recipes in C", который имеет период повторения порядка 1E+18. Этого достаточно на первое время, хотя впоследствии нам следовало бы обратиться к более мощным генераторам случайных чисел, таким как Mersenne-Twister. На форумах пишут, что ran2 медленнее, чем Mersenne-Twister, при гораздо более коротком периоде повторения. Но последний метод сложнее в реализации, а я хотел получить результат побыстрее.
Последний раз редактировалось Barmaley_m; 29.04.2011 в 23:03. Причина: Исправил название книги "Numerical Recipes"
Дальнейшая генерация случайных размещений кораблей и сохранение их в файлы лишь для целей определения соотношения количества допустимых комбинаций к общему количеству координат кораблей - это стрельба из пушки по воробьям. Даже один прогон 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 комбинаций, и она имела тот же вид, только была более зашумлена. Так что метод Монте-Карло для ее расчета действительно сходится к некоторому пределу.
Любопытно, не правда ли? Максимальные шансы попасть в корабль имеются у границ поля, но не в углах! Излюбленное место для размещения кораблей опытных игроков, было найдено моим методом без каких-либо указаний на предпочтения игроков и их стратегии!
Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)
Ваши права
Ответить с цитированием
