Бот для игры в "Морской бой": история, теория, практика

[Barmaley_m]

По большому счёту у меня почти такое же соотношение и получилось, однако метод дал распределения :-)

В принципе, сейчас, кроме метода Монте-Карло, у меня нет других более эффективных методов получения результата. Проблема с методом Монте-Карло заключается в том, что он дает хорошие результаты только в начале игры, а после нескольких выстрелов (как промахов, так и попаданий) количество допустимых комбинаций размещения кораблей уменьшается в тысячи раз. Даже полученные с таким трудом сотни тысяч комбинаций, которые я имею на данный момент, сокращаются до нескольких сотен, что дает большие уровни шума в получаемых на этих этапах картах вероятностей. Поэтому любые новые идеи, усовершенствования или более эффективные методы получения требуемой карты вероятностей - приветствуются.

А как это в режиме реального времени считается?

О расчетах в реальном времени пока что речи не идет. Я думаю, что есть несколько направлений решения этой проблемы:
1) Хранить много комбинаций размещения кораблей. Допустим, несколько десятков мегабайт - это не проблема для современных компьютеров. Как я посчитал, любая коминация может быть закодирована 71 битами, что округляется до 9 байт (72 бит). Такой подход используется, когда не найдено ничего лучшего, например см. взлом хешей методом Rainbow Tables. Для взлома виндошных паролей приходится скачивать сотни мегабайт рассчитанных ранее кем-то таблиц.
2) Хранить разветвляющиеся последовательности оптимальных ходов
3) Изобрести методы, дающие приблизительные результаты (еще менее точные, чем метод Монте-Карло), но за малое время. У меня есть некоторые мысли на этот счет. Метод Монте-Карло можно будет использовать как "золотой стандарт", относительно которого оценивается точность результата менее точных методов.
Думаю, что какие-то варианты проявятся еще по ходу дальнейших исследований.

И опять же, как хранить на несколько ходов вперёд? Ведь вариантов много?

Не так уж и много. Посмотри карту вероятностей для необстрелянного поля. На ней существует 8 клеток с максимальной вероятностью. Если стрелять только в клетки с максимальной вероятностью, то хранить надо только их координаты. В общем-то, даже само значение вероятности нам не так важно, как сам факт, что в данной клетке оно максимально. И вообще, как при хранении, так и при других манипуляциях с вероятностью попадания, всегда следует иметь в виду, что нам не обязательно знать точное число, а важно только знать, в каких клетках оно максимально.