С любовью к вам, Yandex.Direct
Размещение рекламы на форуме способствует его дальнейшему развитию
В принципе, сейчас, кроме метода Монте-Карло, у меня нет других более эффективных методов получения результата. Проблема с методом Монте-Карло заключается в том, что он дает хорошие результаты только в начале игры, а после нескольких выстрелов (как промахов, так и попаданий) количество допустимых комбинаций размещения кораблей уменьшается в тысячи раз. Даже полученные с таким трудом сотни тысяч комбинаций, которые я имею на данный момент, сокращаются до нескольких сотен, что дает большие уровни шума в получаемых на этих этапах картах вероятностей. Поэтому любые новые идеи, усовершенствования или более эффективные методы получения требуемой карты вероятностей - приветствуются.
О расчетах в реальном времени пока что речи не идет. Я думаю, что есть несколько направлений решения этой проблемы:
1) Хранить много комбинаций размещения кораблей. Допустим, несколько десятков мегабайт - это не проблема для современных компьютеров. Как я посчитал, любая коминация может быть закодирована 71 битами, что округляется до 9 байт (72 бит). Такой подход используется, когда не найдено ничего лучшего, например см. взлом хешей методом Rainbow Tables. Для взлома виндошных паролей приходится скачивать сотни мегабайт рассчитанных ранее кем-то таблиц.
2) Хранить разветвляющиеся последовательности оптимальных ходов
3) Изобрести методы, дающие приблизительные результаты (еще менее точные, чем метод Монте-Карло), но за малое время. У меня есть некоторые мысли на этот счет. Метод Монте-Карло можно будет использовать как "золотой стандарт", относительно которого оценивается точность результата менее точных методов.
Думаю, что какие-то варианты проявятся еще по ходу дальнейших исследований.
Не так уж и много. Посмотри карту вероятностей для необстрелянного поля. На ней существует 8 клеток с максимальной вероятностью. Если стрелять только в клетки с максимальной вероятностью, то хранить надо только их координаты. В общем-то, даже само значение вероятности нам не так важно, как сам факт, что в данной клетке оно максимально. И вообще, как при хранении, так и при других манипуляциях с вероятностью попадания, всегда следует иметь в виду, что нам не обязательно знать точное число, а важно только знать, в каких клетках оно максимально.
Для начала - хотя бы вообще, а потом будет видно, можно ли реализовать алгоритм на Спектруме, сохранив его эффективность (хотя бы частично).
У меня в этом деле такой подход, чтобы двигаться к решению постепенно и не пытаться заткнуть сразу все дыры.
Ну смотри, допустим для начала простой случай - клетка с максимальной вероятностью одна после каждого выстрела. Ее координаты можно закодировать 7ю битами. После каждого хода идет ветвление на 2 направления: попал или не попал. Количество клеток для запоминания после каждого хода будет увеличиваться в 2 раза, так что мы имеем дело с суммой геометрической прогрессии. Для запоминания всех ветвлений из 8 ходов достаточно 511 координат, что равняется 448 байтам (у нас 7 бит на одну пару координат). Вполне приемлемо даже для Спектрума. Если клеток с макс. вероятностью больше одной после каждого хода - то таблица возрастет в несколько раз, но мне бы даже 32кБ было не жалко для такой таблицы, а то и под завязку забить всю память до 128К.
Таблицу можно также оптимизировать, как это делается и в шахматах, сохраняя более интересные ветки с большей глубиной, чем менее интересные. Скажем, промахнуться при первых выстрелах больше вероятность, чем попасть, поэтому ветки, начинающиеся с промахов, можно сохранять с большей глубиной. А когда будет подбито несколько вражеских кораблей - то может стать возможным рассчитывать оптимальную стрельбу в реальном времени, так что эти ветки тоже сохранять не надо.
Что ты имеешь в виду?
Не совсем детерминированный. Для каждого хода будет выбор из нескольких клеток (положим, до 4х), и компьютер будет выбирать одну из них случайно.
Да, в этом есть некоторая уязвимость, так же как и при угадывании чисел методом половинного деления, последовательность ходов угадывающего заранее известна. Но загадывающий (противник нашего бота) мало что может с этим поделать, потому что даже если он разместит корабли там, куда бот поначалу не стреляет - серия выстрелов мимо все равно существенно сократит поле для поиска, и начиная с определенного момента бот разгромит противника серией точных выстрелов.
Я уже раньше рассматривал аналогию этой ситуации с угадыванием чисел методом половинного деления. Зная о том, каким методом пользуется угадывающий, загадывающий игрок может оттянуть свой конец, но не более, чем на некоторое число ходов, соответствующее наихудшему случаю.
Стрельба в клетки с максимальной вероятностью попадания, которую я сейчас реализую, оптимизирует как каждый конкретный выстрел, так и число ходов для наихудшего случая, когда все выстрелы, какие только возможно, идут мимо кораблей. Любые отступления от этой стратегии могут увеличить число выстрелов для наихудшего случая. Противник лишь может пытаться реализовать этот наихудший случай. Но к адаптации противника уязвимы любые стратегии, в принципе. Какой бы метод мы ни реализовали - могут существовать способы располагать корабли специально так, чтобы этот метод долго их не мог найти.
Наличие же некоторой, хоть и небольшой, случаности в выборе координат для следующего выстрела затрудняет адаптацию противника к нашей стратегии. Так же как можно сделать вариацию алгоритма угадывания чисел от 1 до 100 с добавкой случайности, которая уменьшила бы шансы противника реализовать наихудший случай при угадывании, при этом не увеличивая число ходов для наихудшего случая, если он все-таки реализуется.
Последний раз редактировалось Barmaley_m; 01.05.2011 в 23:41. Причина: из-за глюка сети сообщение было отправлено дважды
Ты написал что на кучу комбинаций у тебя уйдёт около 500 байт.
Я спрашиваю - а разве не по оставшимся клеткам будет идти расчёт?
Ты же не можешь перерасчитывать каждый раз в ходе игры, ты хранишь все варианты развитий. Я понимаю так: ты можешь хранить каждый выстрел семью битами, но в итоге у тебя каждый следующий выстрел значительно усложняет варианты.
Я мыслю так: при выстреле в первую клетку у тебя останется 99 клеток (вне зависимости, попадание или нет, попадание просто резко сузит необходимые варианты обстрела).
Соотвественно вначале у тебя 100 вариантов выстрела, потом 99, потом 98 и т.д. И каждую из комбинаций тебе надо хранить.
Я тут вижу, что ты можешь кодировать только наиболее вероятные клетки для следующих выстрелов, но всё равно это тебе надо 7 бит на каждую вероятную клетку, в итоге - чтобы алгоритм не был детерменированным, тебе надо хранить минимум 2 ячейки далее. На каждый новый ход по 14 бит данных на промах (наиболее вероятные ячейки следующих двух ходов) и 14 бит данных на попадание (аналогично). Каждый ход добавляет 28 бит данных, каждые 7 бит которых порождают ещё 28 бит данных и т.д. Т.е. таблица каждый следующий ход вариант ветвления увеличивается в 4 раза . Даже для такого примитивного случая тебе надо будет 14*(4^N) бит на маску некоего хода N. Вся память, занимаемая масками будет записана как Mem = 14 * (1 + 4 + 4^2 + 4^3 + 4^4 + 4^5 + .... + 4^N), для 8 ходов это будет 152916,75 байт, почти влезло в 128к...
Беру свои слова назад... по крайней мере это близко к осуществимости...
Если продумать формат, чтобы занимаемая память была меньше 28 бит на выстрел, тогда возможно, получится уложить даже 9 или 10 ходов.
Вот, немного не в тему, ребята рассчитали судоку для однозначного разрешения. Там тоже матстат и аналитика: В Ирландии рассчитали минимальное количество подсказок в судоку
Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)