Прежде, чем мы возьмемся вычислять вероятность попадания в корабли,
сделаем небольшое отступление, чтобы рассмотреть игру в "Морской бой"
с другой стороны.
"Морской бой" как задача поиска.
Стрельбу в "Морской бой" можно рассматривать как задачу поиска.
Вначале имеется множество всех комбинаций размещения кораблей
на поле. Каждый выстрел разбивает это множество на две части.
Первая часть - это те комбинации, у которых обстреливаемая клетка
свободна, вторая часть - те комбинации, у которых в обстреливаемой
клетке имеется корабль или его часть. Всякий раз после выстрела количество
оставшихся комбинаций размещения кораблей уменьшается, и в конце концов
сжимается до одной конкретной комбинации, которую избрал противник -
этот момент наступает при потоплении всех его кораблей.
Для победы в "Морском бое" необходимо организовать этот поиск наиболее
эффективным образом, то есть за минимальное число попыток найти
избранную противником комбинацию кораблей.
Разбивание множества возможных решений на две части при каждой итерации напоминает
задачу двоичного поиска, или игру в угадывание чисел. Например, если требуется
угадать число от 1 до 100, задуманное противником, и после каждой попытки
противник сообщает, больше или меньше задуманного им числа является названное
число.
Оптимальный способ решения задачи такого поиска известен. Его называют
"половинное деление", "дихотомия", "бисекция", что в общем-то означает одно
и то же. Сначала нужно разбить интервал на 2 равные части, назвав число 50.
В случае неугадывания становится известно, в какой из половин интервала
находится задуманное число, а размер оставшегося интервала для угадывания
уменьшается в 2 раза. Вторая попытка должна быть произведена в середину
оставшегося интервала, т.е. 25 или 75. В результате второй попытки интервал
для угадывания снова сократится в 2 раза. И так далее. В итоге после максимум
7 попыток (для интервала 1-100) задуманное число будет угадано.
Метод половинного деления приходит к ответу, в худшем случае,
за число попыток, равное log2(N), где N - число элементов множества возможных ответов,
при этом, если значение логарифма оказывается дробным, то его следует округлить
в большую сторону.
При отсутствии какой-либо иной информации об элементах множества, в котором
производится поиск, кроме ответов "больше-меньше", метод половинного деления
является оптимальным, т.е. любой другой метод поиска, хоть в частных случаях
может и приводящий к ответу быстрее, чем за ceil(log2(N)) попыток, в наихудшем
случае будет тратить больше попыток, чем метод половинного деления. В самом деле,
если мы будем разбивать интервал для угадывания на неравные части, то в случае
невезения (задуманное число всякий раз будет оказываться в большей из двух частей)
затратим больше попыток, чем если бы делили интервал пополам.
Поэтому, рассматривая стрельбу в "Морской бой" как задачу поиска размещения
кораблей противника на всем множестве возможных размещений в конкретный
игровой момент, следует стремиться, чтобы каждый выстрел делил это множество
на две равные части. При соблюдении этого условия размер множества, в котором
предстоит вести дальнейший поиск, будет уменьшаться с максимальной скоростью.
Пропорции, в которых выстрел делит множество комбинаций размещения кораблей
на части, равны вероятности попасть в корабль в данной клетке в том смысле,
в котором эта вероятность была определена ранее. Поэтому, для деления множества
на две равные части, вероятность попасть в корабль должна быть равна 50%.
Не меньше, но и не больше. Парадокс, но при вероятности попадания более 50%
общее количество выстрелов до полного обнаружения кораблей противника может быть
больше, чем если стрелять в клетки с вероятностью попадания 50%.
В реальной игре следует, несмотря на вышесказанное, стрелять в клетки с
максимальной вероятностью попадания, даже если она превышает 50%, потому
что во-первых, корабли мало обнаружить, их надо еще и потопить. Во-вторых, в
случае попадания дается повторный выстрел. Т.е. первый выстрел как бы не
считается в общем числе попыток. В-третьих, потопленный корабль окружается
ореолом клеток "мимо", что является эквивалентом целой группы бесплатных
выстрелов.
Ситуации, в которых вероятность попадания может достичь и превысить 50%, возникают
в игре не сразу. При необстрелянном поле размером в 100 клеток у нас имеется 20
клеток, занятых кораблями. При расчете вероятности попадания на необстрелянном поле
исходя из идей, высказанных мной ранее, удается найти клетки с максимальной
вероятностью попадания примерно 25%. До 50% дотянуть не удается. Ну, что ж делать,
приходится довольствоваться тем, что есть. Но чем выше вероятность попадания в
обстреливаемой клетке - независимо от результата выстрела - тем быстрее
мы сужаем круг для дальнейших поисков.
Хоть идеи, высказанные выше, и не добавляют ничего принципиально нового к
идее стрельбы в клетки с максимальной вероятностью попадания, но зато
мы подходим сейчас к решению вопроса об оптимальном размещении кораблей.
Рассмотрим снова игру в угадывание чисел с позиции задумывающего.
Если мы будем всякий раз задумывать числа не случайно, а в
какой-то закономерности (например, только числа меньше 50) - то угадывающий
противник со временем уловит эту закономерность и адаптируется к ней,
повысив эффективность своего угадывания. Например, если мы не загадываем
числа больше 50 - то он и не будет их искать на этом интервале, тем
самым сократив число попыток до гарантированного отгадывания. Поэтому,
отдавая предпочтения определенным размещениям кораблей, таким как
"все длинные корабли у границ" или "все длинные корабли вдоль одного края
поля", мы заведомо сужаем противнику круг для их поиска. Стоит дважды
подумать прежде, чем отдавать определенным размещениям предпочтение
по сравнению с равновероятным выбором своей комбинации размещения
кораблей из всего множества допустимых.
Выбор размещения кораблей равновероятно из всего множества допустимых
размещений - это нетривиальная задача, но я нашел ее решение, которое
опубликую в дальнейших постах.
Если мы знаем, что противник, угадывая наши числа, пользуется наилучшим
для общего случая алгоритмом - методом половинного деления - то нам
становится понятно, что противник угадает наше число максимум за 7 попыток,
что бы мы ни делали. Повысить верхнюю границу на число попыток мы не
можем. Но мы можем задумывать такие числа, чтобы при их угадывании методом
половинного деления было затрачено как раз максимальное число попыток.
Например, если мы задумали число 33 - то противник будет угадывать его в
такой последовательности: 50, 25, 37, 31, 34, 32, 33, т.е. затратит
ровно 7 попыток. Таких чисел всего существует 37 штук на промежутке 1-100,
и если мы будем всегда загадывать одно из них - то обеспечим противнику
максимум трудностей. Конечно, только до тех пор, пока противник не
догадается, что мы загадываем только такие числа - тогда он начнет
угадывать их быстрее. Этот же принцип можно распространить на размещение
кораблей в "Морском бое" после того, как мы получим последоватлельность
оптимального (с точки зрения быстрейшего сокращения множества возможных
размещений кораблей) обстрела поля.
