#algorithm
#алгоритм
Вопрос:
Я создаю помощника по вероятности для игры Battleship — по сути, для данного состояния игры (состояние поля и доступные корабли), это создаст поле, в котором все свободные ячейки будут иметь вероятность попадания.
Мой текущий подход заключается в том, чтобы выполнить вычисления, подобные монте-Карло — получить случайную свободную ячейку, получить случайный корабль, получить случайное вращение корабля, проверить, действительно ли это размещение, если да, продолжить со следующим кораблем из доступного набора. Если доступный набор пуст, добавьте, как были установлены корабли, в выходной стек. Повторите это несколько раз, используйте выходные данные для вычисления вероятности каждой ячейки.
Существует ли разумный алгоритм для обработки всех возможных размещений кораблей для данного состояния поля?
Комментарии:
1. Я думаю, это зависит от того, что вы считаете разумным. Проведя некоторую математическую обработку, для каждого из пяти кораблей существует не менее 100 мест размещения, так что вы просматриваете большую часть, по крайней мере, 10 ^ 10 конфигураций, что много, но не так много, чтобы невозможно было представить реализацию в полуреальном режиме, которая широко использовала растровые изображения.
2. @DavidEisenstat Существует 5 видов кораблей, но есть до 15 кораблей. Это увеличивает размер проблемы за пределы простого перебора.
3. Ах да, это не сработает. Вероятно, лучшим оставшимся вариантом было бы каким-то образом выполнить MCMC, но я не знаю, насколько сложно было бы хорошо выполнить условную выборку, если есть много точек данных.
Ответ №1:
Точное решение возможно. Но не считается нормальным в моих книгах.
Тем не менее, вот идея.
Существует много вариантов игры, но давайте предположим, что мы начинаем с наихудшего сценария: 1 корабль размером 5, 2 размера 4, 3 размера 3 и 4 размера 2.
«Обнаруженное состояние» доски — это все места, где были сделаны выстрелы или были обнаружены корабли, плюс количество оставшихся кораблей. Обнаруженное состояние наивно требует 100 бит для доски (10×10, любой может быть снят) плюс 1 бит для подсчета оставшихся кораблей размера 5, 2 бита для оставшихся кораблей размера 4, 2 бита для оставшихся кораблей размера 3 и 3 бита для оставшихся кораблей размера 2. Это составляет 108 бит, что соответствует 14 байтам.
Теперь концептуально идея состоит в том, чтобы вычислить карту, снимая каждый квадрат по очереди в первом ряду, во втором ряду и так Далее, и записывая состояние игры вместе с переходами. Мы можем записывать прямые переходы и подсчеты, чтобы определить, сколько существует способов добраться до любого состояния.
Затем найдите конечное состояние всего законченного и всех используемых кораблей и пройдите переходы назад, чтобы узнать, сколько существует способов перехода из любого состояния в конечное состояние.
Теперь пройдитесь по структуре данных вперед, зная вероятность достижения любого состояния на пути к концу, но на этот раз мы можем вычислить вероятность каждого способа нахождения корабля на каждой клетке по мере продвижения вперед. Суммируйте их, и мы получим нашу тепловую карту вероятности.
Это выполнимо? В памяти нет. Хотя в распределенной системе это может быть.
Помните, я говорил, что запись состояния занимает 14 байт? Добавление количества к этому занимает еще 8 байт, что приводит нас к 22 байтам. Добавление обратного счета приводит нас к 30 байтам. По моим подсчетам, в любой точке нашего пути может быть порядка полумиллиарда состояний, в которых мы можем находиться с различными оставшимися кораблями, торчащими убитыми кораблями и так далее. Это 15 ГБ данных. Потенциально для каждого из 100 квадратов. Что составляет 1,5 терабайта данных. Который мы должны обработать за 3 прохода.
Комментарии:
1. спасибо за ваши оценки, данных может быть еще больше, поскольку нам нужно учитывать, что каждый корабль может иметь допустимое вращение (например, 2 квадрата могут быть выровнены по вертикали и горизонтали, 3 квадрата могут быть горизонтальными, вертикальными и L-образными в 4 типах — таким образом, всего один квадрат 3корабль может быть размещен 6 возможными способами — это тип линкоров, в которые я играл в детстве).
2. @jozefow Это действительно может быть. Я только оценил горизонталь, а затем добавил коэффициент выдумки.