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

[Barmaley_m]

Математический анализ игры в "Морской бой" занимал меня с давних пор. Все началось с 1996 года, когда я замахнулся реализовать сильного бота для игры в "Морской бой" на сувенирных часах с микропроцессором Z80, причем бота, играющего честно, не подсматривая в корабли противника.

Интернета тогда не было, а где еще можно было найти подобную теорию, я также не представлял. Было решено начать с опроса одногруппников, которые были сильны в этой игре. Но опрос показал, что эти люди либо скрывают, либо не имеют формального метода наилучшей стрельбы. Действуют интуитивно. Сообщили мне пару приемов, но описание было такое, которое трудно поддается алгоритмизации. Оставалось только действовать самому. И я начал думать.

Вообще говоря, сильная игра в морской бой состоит из двух составляющих: правильное расположение своих кораблей и правильная стрельба по кораблям противника. Но в 1996-1997г я занимался только стрельбой, а к расположению так и не сообразил, как подступиться. Так что начнем и мы сейчас разговор со стрельбы, вернувшись к расположению впоследствии.

Исходный пункт моих размышлений на тот момент - это был один красивый прием, подсказанный спектрумистом Андреем Гетало, во время игры в "Battleships". Там корабли были большие, поэтому этот прием очень хорошо действовал. Например, чтобы найти корабль длиной в 4 клетки, нужно в первую очередь стрелять по открытым длинным линиям, причем с интервалом в 3 клетки, т.е. так, чтобы между выстрелами этот корабль не мог спрятаться. Причем каждый выстрел, в идеале, должен максимально сокращать длинные линии как по горизонтали, так и по вертикали.

С другой стороны, поскольку "Морской бой" - игра со случайностью, то было ясно, что необходимо каким-то образом привлекать теорию вероятностей и, в ее терминах, пытаться стрелять туда, где существует максимальная вероятность поразить корабль противника.

Сформулировать задачу стрельбы в рамках теорвера - дело непростое, тем более для меня на 2м курсе, когда мы теорвер только начали проходить. Но все же я тогда додумался до следующей идеи, которая оказалась очень близкой к оптимуму. Я начал вычислять для каждой свободной клетки величину, которую я назвал "число возможностей размещения". Что это такое?

Представим себе чистое (необстрелянное) поле противника и какую-нибудь клетку в центре поля. Рассмотрим корабль длиной в 4 клетки. Сколько существует возможностей разместить этот корабль, чтобы он одной из своих частей оказался в этой клетке? Ответ простой. Корабль можно разместить по горизонтали четырьмя способами, чтобы одна из его клеток попала в искомую, и еще четырьмя по вертикали. Всего 8.

Теперь представим ту же ситуацию, но клетка справа от искомой уже обстреляна (там "мимо"). Сколькими способами можно разместить 4-палубный корабль, чтобы одна из его частей попала в рассматриваемую клетку? Очевидно, что никакая часть корабля теперь не может оказаться в той клетке, где "мимо". Следовательно, по горизонтали 4-палубный корабль может быть размещен только одним способом: так, чтобы крайняя правая его клетка была в рассматриваемой, а остальные слева. По вертикали число возможностей размещения остается нетронутым, т.е. 4, а всего 5 возможностей размещения.

Число возможностей размещения связано с вероятностью нахождения корабля в данной клетке. Почему? Ответ можно доказать строго. Корабль длиной в 4 клетки может быть размещен на поле конечным числом способов - назовем это число m. Из них n приходится на рассматриваемую нами клетку. Если все размещения корабля на поле равновероятны (а у нас пока нет причин считать иначе) - то вероятность нахождения корабля в данной клетке будет n/m, где n - число возможностей размещения, как я определил это число выше. Таким образом, вероятность нахождения корабля в клетке пропорциональна числу возможностей его размещения в ней. Важно: вышеприведенное рассуждение справедливо только для случая, когда на поле нет других кораблей. Когда есть другие корабли, ситуация значительно усложняется, и вероятность больше не зависит так явно от числа возможностей размещения.

Получить некое число, соответствующее вероятности, для случая многих кораблей, на 1996г мне не удалось, поэтому я ограничился следующим алгоритмом стрельбы:
1) для каждой свободной клетки вычислить число возможностей размещения в ней самого длинного корабля противника, который еще остается на поле.
2) Найти все клетки, где число возможностей размещения достигает максимума.
3) Выстрелить случайным образом в одну из этих клеток с максимумом.

Например, для чистого (необстрелянного) поля число возможностей размещения 4-палубного корабля выглядит следующим образом для каждой клетки:

2 3 4 5 5 5 5 4 3 2
3 4 5 6 6 6 6 5 4 3
4 5 6 7 7 7 7 6 5 4
5 6 7 8 8 8 8 7 6 5
5 6 7 8 8 8 8 7 6 5
5 6 7 8 8 8 8 7 6 5
5 6 7 8 8 8 8 7 6 5
4 5 6 7 7 7 7 6 5 4
3 4 5 6 6 6 6 5 4 3
2 3 4 5 5 5 5 4 3 2

После выстрела в клетку с максимальным числом возможностей размещения (например, Г-4) карта менялась следующим образом:

2 3 4 4 5 5 5 4 3 2
3 4 5 4 6 6 6 5 4 3
4 5 6 4 7 7 7 6 5 4
4 4 4 0 5 6 7 7 6 5
5 6 7 5 8 8 8 7 6 5
5 6 7 6 8 8 8 7 6 5
5 6 7 7 8 8 8 7 6 5
4 5 6 7 7 7 7 6 5 4
3 4 5 6 6 6 6 5 4 3
2 3 4 5 5 5 5 4 3 2

Как видно, даже один выстрел существенно меняет картину распределения возможностей размещения 4-палубного корабля. Выстрел в клетку с максимальным числом таких возможностей не только обнулял это число в самой клетке, но и максимально уменьшал его значение во всех остальных клетках. Число клеток с максимумом в рассматриваемом примере упало с 16 до 9, сокращая выбор возможностей для следующего выстрела. В конечном итоге, до подбития 4-палубного корабля, поле противника покрывалось "узором" из выстрелов, который принимал различные формы, но всегда в нем соблюдалось одно свойство: расстояние между соседними выстрелами по горизонтали и вертикали не превышало 3, что не позволяло 4-палубнику "проскочить" этот узор.

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

Когда подбивался какой-нибудь корабль, алгоритм стрельбы переходил в режим добивания корабля. Здесь я не смог на тот момент найти каких-либо критериев повышения вероятности поражения, поэтому стрелял в любую из клеток вокруг той, которая подбита, если по этой линии мог быть размещен корабль противника минимальной длины из оставшихся. После подбития второй клетки корабля противника стрельба проводилась только вдоль линии, в которой расположен этот корабль. Добивание корабля противника всеми игроками, в том числе моим алгоритмом, считается приоритетным перед поиском оставшихся кораблей. Обоснование простое: подбитие корабля исключает из игры не только обстрелянные клетки, но и клетки вокруг подбитого корабля, тем самым существенно уменьшая возможности размещения остальных кораблей, а также меняя картину максимумов числа возможностей этого размещения.

Размещение своих кораблей на поле на 1997г проводилось мной по следующему методу. Сначала на поле размещался корабль максимальной длины случайным образом. Потом проводилась попытка разместить следующий корабль случайным образом. Если сгенерированные случайные числа попадали так, что новый корабль не может быть размещен (он попадает в уже имеющийся корабль или в его "ореол") - то попытка повторялась, и так до победного конца. Таким образом, я на тот момент не пытался разместить корабли таким образом, чтобы противнику было труднее их найти. Это предопределило относительно слабую игру моего бота 1997г.

Изложенные выше концепции я сначала реализовал в программе на Паскале - seaboy.pas. Так было проще проводить наладку, у меня был компилятор Turbo Pascal под CP/M. Когда алгоритм на Паскале был налажен, я приступил к его переводу на ассемблер.

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

Алгоритм стрельбы имеет, однако, один важный недостаток. Он в первую очередь обстреливает середину поля, а границы его - в последнюю очередь. Так что, если размещать корабли вдоль границ поля - то мой алгоритм стрельбы 1997г очень нескоро их найдет. Отсюда видно, что алгоритм стрельбы можно улучшить. Об этом и о других алгоритмах сильной игры речь пойдет в следующих сообщениях.

Прилагаю файл seaboy.pas - отладочная версия моего бота 1996-1997г.

[doorsfan]

Миш, столько много букв..... длинные корабли нужно располагать вдоль стенок, короткие раскидать по полю. обстреливать сначала каждую четвёртую клетку, когда результат будет достигнут - каждую третью. децкий сад ;)

[esl]

в тему Теория и практика игры «Морской бой» — по-честному (http://habrahabr.ru/blogs/subconsciousness/82221/)

[Vadim]

Я могу предложить только свой алгоритм, которым пользовался в Battle Ships. В самом начале игры стреляем наиболее хаотично. Так несколько первых ходов. До 5-го, 7-го. Уже, как правило, пара попаданий будет. Далее, смотрим картинку, используя подсказку, в какие корабли попали. И прикидываем, как они могут располагаться. Игра для выяснения начинает обставлять каждый квадрат у больших кораблей по периметру, да и у мелких тоже. Налицо не оптимальность алгоритма. Потом выяснив, как расположен корабль (возможно за 2-3 хода) уже ставит более нацеленно. Я делаю не так. Продолжаю хаотические выстрелы и бью соседние клетки подбитых, но не весь периметр,а по одной две. Помнится комп у меня выиграл всего раз или два. Игра проходится за 10 минут. Самый длинный корабль анализируем очень просто. Если попали в него, смотрим его возможные размещения (которых может быть 4) и бьем по ним. Т.е. фактически 4 клетки а не 8. как делает комп. и т.д. с другими. Хотя как это запрограммировать я не знаю. Не представляю пока.

[Barmaley_m]

esl, спасибо за линк, указанную статью я читал недавно, собирался сделать на нее ссылку в своих дальнейших постах. Мои сегодняшние результаты по теории игры в "Морской бой" заходят дальше материалов этой статьи. Обрати внимание, кстати: метод обстрела для поиска 4-палубного корабля, приведенный в той статье, получается автоматически у моего алгоритма поиска клетки с максимальным числом возможностей размещения этого корабля. Более того, когда обстрел по шаблону, приведенному в статье, становится невозможным (например, подбиты другие корабли вместо 4-палубного), мой алгоритм продолжает эффективно действовать. Так что не смотрите даже на этот, имеющий недостатки, алгоритм свысока!

doorsfan, твои рассуждения, в общем, верные, но они не подтверждаются сколько-нибудь строгими доказательствами. Именно публикацией доказательств я занимаюсь в этой ветке. В чем польза наличия доказательств?
1) Они позволяют убедиться в истинности некоторых утверждений;
2) Они позволяют выяснить, нет ли еще более оптимального метода решения задачи.
И как показывают мои изыскания, такие методы есть! Подождите только немного, пока я напишу продолжение.

[osa]

будет ли оформлена отдельная статья на тот же хабр по этому поводу?

[Barmaley_m]

будет ли оформлена отдельная статья на тот же хабр по этому поводу?
Возможно, материалов, которые я выложу на этой ветке, будет достаточно для написания статьи. Если хватит времени и вдохновения - я этим займусь. Что такое хабр?

---------- Post added at 01:04 ---------- Previous post was at 00:07 ----------

Итак, продолжим. Рассмотрим главный недостаток моего бота 1996-1997г: он неэффективен в случае размещения кораблей противника у краев поля. Противник мог легко заметить тенденцию моего алгоритма начинать обстрел с центра, и размещать свои корабли всегда у краев. Тем самым он получал огромное преимущество, фактически гарантируя промах бота на первой паре десятков выстрелов.

Размещение длинных кораблей у краев поля вовсе не является редкостью для игры в "Морской бой". Наоборот, большинство опытных игроков только так свои корабли и расставляют. Причина - то, что подбитие длинного корабля в центре поля окружает его большим ореолом из клеток "мимо", тем самым значительно сужая поле для дальнейших поисков. Данный вопрос был рассмотрен детально Я.И. Перельманом (1882-1942), российским и советским ученым, популяризатором науки. Статья "Морской бой" в русской Википедии со слов Перельмана описывает стратегию, основанную на размещении кораблей у краев поля, и обосновывает ее преимущество. То же описано в статье пользователя habrahabr.ru Подсознание - "Теория и практика игры «Морской бой» — по-честному", на которую дал ссылку esl.

Очевидно, что алгоритм стрельбы надо каким-то образом изменить, чтобы он больше обстреливал края поля. Но как, по каким критериям? За прошедшие со времени создания моего бота более 10 лет я иногда возвращался к размышлениям на эту тему, но так до недавних пор и не смог придумать хорошего решения. Если приблизительный расчет вероятности, основанный на подсчете числа возможностей размещения, говорит о том, что корабль более вероятно находится в центре поля - значит стрельба куда-либо, кроме центра, в общем случае уменьшает вероятность попадания. И только в специальном случае, когда противник специально размещает корабли у краев, где найти их легче, чем в центре (если знать, что они там) - такая стрельба имеет преимущество. Одно дело человеку понимать все это, а другое дело - реализовать в программе. Это была бы своего рода стрельба, адаптивная к противнику: если бы бот решил, что человек имеет тенденцию размещать корабли у краев - то он начал бы охотнее обстреливать края, а если нет - то снова смещал бы акцент в центр. Интуитивно понятно, но формальных критериев нет по-прежнему. Поэтому я не пытался реализовать эти идеи в виде программы, уж очень все было зыбко. Как потом убедиться, что бот играет сильнее, чем предыдущий? Особенно если противник начал бы адаптироваться к его новому поведению и снова принял какую-то иную стратегию размещения кораблей, которая обеспечила бы ему преимущество?

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

Второй недостаток решается легким изменением алгоритма стрельбы. В подсчете числа возможностей размещения учитывается теперь не только четырехпалубник, но и трех- и двухпалубники. Число возможностей их размещения в каждой клетке теперь суммируется, и стрельба снова проводится в одну из клеток, где это число достигает максимума.

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

Вопросов накопилось больше, чем ответов, и вот недавно я созрел к математической атаке на "Морской бой" с целого ряда направлений, о чем и пойдет речь ниже.

[daniel]

Как потом убедиться, что бот играет сильнее, чем предыдущий?

Это же очевидно, запускать ботов против друг друга...

[Barmaley_m]

Ну а сейчас начинаю излагать мою новую теорию игры в "Морской бой". Мы начнем с обсуждения только оптимальной стрельбы, а потом, поняв, какие существуют возможности оптимальной стрельбы, вернемся к вопросу оптимального размещения кораблей на своем поле.

Существует конечное множество комбинаций размещения всех кораблей на игровом поле. Это следует из конечности и дискретности самого поля.

Если предположить, что противник с одинаковой вероятностью может использовать любую комбинацию из этого множества - то вероятность попасть в корабль в клетке с координатами (x,y) равна отношению чисел M/N, где N - общее число комбинаций,
а M - число таких комбинаций, при которых в клетке с координатами (x,y) имеется корабль или его часть.

Стрельба должна вестись в первую очередь в те клетки, где вероятность подбить вражеский корабль максимальна. Хоть это утверждение является интуитивно понятным, оно нуждается в строгом обосновании, которое я получил и приведу позднее.

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

В упрощенных случаях получить числа M и N легко, и сейчас я приведу пару таких примеров.

1. Рассмотрим тривиальный случай, когда у нас на всем поле есть лишь один однопалубный корабль. Очевидно, что он может быть размещен в любой из клеток без каких-либо дополнительных ограничений. Поэтому всего существует столько возможностей его размещения, сколько есть клеток, и оно равно 100. Для каждой клетки только одна из таких возможностей соответствует наличию в ней корабля. Поэтому вероятность попасть в корабль для каждой клетки при первом выстреле одинакова и равна 0.01, или 1%. Оптимальная стрельба в этом случае является просто случайным выбором из всех клеток (Данное утверждение доказывается в рамках теории игр).

2. Рассмотрим случай, когда на поле имеется два однопалубных корабля. Если бы их можно было размещать вплотную друг к другу, а также два корабля в одной клетке, то общее число комбинаций размещения составляло бы 10000. С учетом правил "Морского боя" о недопустимости размещения кораблей вплотную, допустимых комбинаций будет меньше. А именно: размещение первого из кораблей в середине поля уменьшает количество клеток для размещения второго корабля на 9. Размещение первого корабля у границ уменьшает число клеток для второго корабля на 6, а когда первый корабль стоит в углу, второй корабль может быть размещен
во всех клетках, кроме четырех. Подсчет числа N выглядит так:

N = 8*8*(100-9) + 8*4*(100-6) + 4*(100-4) = 5824+3008+384=9216

Число M можно рассчитать из следующих соображений. Возьмем угловую клетку (1,1). Существует 96 комбинаций, при которых первый корабль будет размещен в этой клетке, а второй - в одной из оставшихся. Существует столько же комбинаций, при который второй корабль размещен в этой клетке, а первый - в другом месте. Складываем, получается 96+96=192 комбинации, при которых в клетке (1,1) размещен корабль. Вероятность попасть в корабль при стрельбе в эту клетку будет равна 192/9216~=2.0833%.

Рассмотрим клетку в центре, например (4,4). При размещении в этой клетке первого корабля второй может быть размещен в любой из оставшихся 91. Такое же число имеем для случая размещения в этой клетке второго корабля, а первого - в любой из оставшихся. В сумме получится p=(91+91)/9216 ~= 1.9748%.

Для клеток у границ поля, например, (1,5), вероятность попадания составит p=(94+94)/9216 ~= 2.0399%.

Так что уже для простого случая двух однопалубных кораблей карта вероятностей попадания оказывается неравномерной, и вероятность попасть в корабль, стреляя в угол, больше вероятности попасть, стреляя в середину поля, на 5 с половиной процента. Не так уж и мало! Любопытно, что вероятность попадания увеличивается ближе к границам поля. Позже мы увидим, что эта закономерность наблюдается и при учете более сложных комбинаций размещения всех кораблей. Так что горе тем игрокам, которые любят размещать свои корабли у границ! Новый бот быстро их разобьет.

Продолжение следует.

[doorsfan]

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

---------- Post added at 12:22 ---------- Previous post was at 12:19 ----------

вероятно, это ситуации описанные в последнем абзаце #9 поста?

[Barmaley_m]

Прежде, чем мы возьмемся вычислять вероятность попадания в корабли,
сделаем небольшое отступление, чтобы рассмотреть игру в "Морской бой"
с другой стороны.

"Морской бой" как задача поиска.

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

Для победы в "Морском бое" необходимо организовать этот поиск наиболее
эффективным образом, то есть за минимальное число попыток найти
избранную противником комбинацию кораблей.

Разбивание множества возможных решений на две части при каждой итерации напоминает
задачу двоичного поиска, или игру в угадывание чисел. Например, если требуется
угадать число от 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,
и если мы будем всегда загадывать одно из них - то обеспечим противнику
максимум трудностей. Конечно, только до тех пор, пока противник не
догадается, что мы загадываем только такие числа - тогда он начнет
угадывать их быстрее. Этот же принцип можно распространить на размещение
кораблей в "Морском бое" после того, как мы получим последоватлельность
оптимального (с точки зрения быстрейшего сокращения множества возможных
размещений кораблей) обстрела поля.

[Andrew771]

Поэтому, рассматривая стрельбу в "Морской бой" как задачу поиска размещения
кораблей противника на всем множестве возможных размещений в конкретный
игровой момент, следует стремиться, чтобы каждый выстрел делил это множество
на две равные части. При соблюдении этого условия размер множества, в котором
предстоит вести дальнейший поиск, будет уменьшаться с максимальной скоростью.
т.е., лупить сначала точно по центру игрового поля, разбивая его на 4 воображаемых прямоугольника, потом в центры этих прямоугольников, получая новые четверки меньших прямоугольников, и т.д.? А расставлять корабли, не попадая в эти центры?

[GriV]

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

X-попадание
_-промах

0000000
0000000
000X000
000_000
0000000

0000000
0000000
000X000
0000000
000_000


вэтих схемах более правильным будет горизонтальное продолжение атаки,

0000000
0000000
000X0_0
000_000
0000000

В такой схеме более правильным будет горизонтальное продолжение атаки влево.

0000000
0000000
000X_00
000_000
0000000

Такая схема не даёт вероятностно лучший исход в одном из направлений, можно атаковать рандомом вверх или влево.


Оптимальный способ решения задачи такого поиска известен. Его называют
"половинное деление", "дихотомия", "бисекция"
Этот метод крайне долог (с точки зрения сходимости и соотвественно достижения решения). Однако в силу дискретности значений результирующей функции другие методы плохо применимы. Хотя метод золотого сечения возможно тоже будет применим? А чтобы человек, играющий против бота не использовал слабость какой-то конкретной методики - тогда рандомом выбирать одну из них на старте?

[Barmaley_m]

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

Этот метод крайне долог (с точки зрения сходимости и соотвественно достижения решения).
Долог? Ты что! Метод имеет экспоненциальную сходимость. С каждой итерацией интервал, в котором находится решение, уменьшается в 2 раза. Угадать число от 1 до 100 за 7 попыток - это, я бы сказал, довольно-таки неплохо. Для угадывания числа от 1 до 1000 тем же методом требуется всего 10 попыток! Разве это не впечатляет?

В программировании, если требуется найти элемент в последовательности, иногда прибегают к сортировке этой последовательности, чтобы была возможность выполнять двоичный поиск в ней. Так что метод очень даже хороший.

При численном решении уравнений имеются методы, сходящиеся быстрее, чем метод половинного деления, однако эти более быстрые методы пользуются тем, что искомая функция является гладкой, ее аппроксимируют какими-нибудь полиномами, а в нашем случае "Морского боя" как ты что-то здесь аппроксимируешь?

Хотя метод золотого сечения возможно тоже будет применим?
Метод золотого сечения применяется для поиска экстремумов, и по сути он имеет такую же экспоненциальную сходимость, как и метод половинного деления. Сходится чуть медленнее: интервал уменьшается не в 2 раза за каждую итерацию, а в 1.6 раза. Связано это с тем, что для локализации экстремума требуется 3 точки, тогда как для локализации корня - только 2.

А чтобы человек, играющий против бота не использовал слабость какой-то конкретной методики - тогда рандомом выбирать одну из них на старте?
Ну да, рандом. Дело в том, что множество всех допустимых размещений кораблей в "Морском бое", является многосвязным, поэтому точек выстрела, разбивающих его на две по возможности равные части, существует в общем случае несколько. Лишь в некоторых игровых ситуациях такая точка одна. Поэтому можно случайно выбирать одну из них.

Скажем, если построить карту вероятностей размещения кораблей в каждой клетке на необстрелянном поле - то такая карта должна быть симметричной относительно поворотов и зеркального отражения, поэтому клеток с максимальной вероятностью попадания должно быть не менее 4.

---------- Post added at 20:14 ---------- Previous post was at 20:05 ----------


т.е., лупить сначала точно по центру игрового поля, разбивая его на 4 воображаемых прямоугольника, потом в центры этих прямоугольников, получая новые четверки меньших прямоугольников, и т.д.?
Нет, все сложнее.

Выстрелы в середину поля, как будет показано далее (когда я опубликую результаты расчетов), вообще говоря, не делят все множество допустимых размещений кораблей на равные части. Связность множества размещений кораблей не является такой простой, как связность клеток на поле. Поэтому первые выстрелы бота будут в клетки типа В-1 или А-3. Именно они имеют на необстрелянном поле максимальную вероятность попасть в корабль - около 25%. Выстрелы в эти клетки делят множество допустимых размещений кораблей в пропорции примерно 1:3. Но лучше нельзя в начале игры.

[GriV]

Долог? Ты что! Метод имеет экспоненциальную сходимость
Для предопределённой функции с поиском экстремума :-) Там лучше вообще метод градиентного спуска использовать :-) А как предопределена функция в случае морского боя? ;-) Там либо попадание либо промах, либо вероятностные кривые, к которым метод половинного деления никакого отношения не имеет :-)

---------- Post added at 17:20 ---------- Previous post was at 17:17 ----------


При численном решении уравнений имеются методы, сходящиеся быстрее, чем метод половинного деления, однако эти более быстрые методы пользуются тем, что искомая функция является гладкой, ее аппроксимируют какими-нибудь полиномами, а в нашем случае "Морского боя" как ты что-то здесь аппроксимируешь?
Именно про это я и говорю... То, что используешь - это скорее какой то продвинутый метод сетки.

[Barmaley_m]

А как предопределена функция в случае морского боя? ;-) Там либо попадание либо промах, либо вероятностные кривые, к которым метод половинного деления никакого отношения не имеет :-)
В морском бое мы ищем не корень или экстремум функции, а элемент множества. А именно: конкретное размещение кораблей противника во всем множестве допустимых размещений. Выстрел делит исходное множество на две части, и поиск продолжается в одной из этих частей. Здесь прямая аналогия с методом половинного деления.

Именно про это я и говорю... То, что используешь - это скорее какой то продвинутый метод сетки.
Если под методом сетки ты имеешь в виду что-то типа метода Эйлера для решения дифуров - то нет, аналогии здесь не просматривается.

[Barmaley_m]

Теперь перейдем к практике: вычисление вероятности попадания для каждой клетки.

Исходя из сказанного мною выше, для вычисления этой вероятности необходимо рассмотреть все возможные размещения вражеских кораблей на поле, и посчитать количество таких размещений, у которых в рассматриваемой клетке имеется корабль или его часть.

Каким образом можно рассмотреть все возможные размещения кораблей на поле? Задача имеет тривиальное решение, приводимое ниже.

Для определенности положим (эта конвенция принята во всех моих программах для игры в морской бой, в том числе в seaboy.pas), что координата корабля - это координата его верхней левой клетки; кроме координаты, у многопалубных кораблей существует параметр ориентации: горизонтальная или вертикальная.

Примем также, что вместо традиционного выражения координат "Морского боя" (буква-число) у нас будут два числа, как в декартовой системе координат, причем первое будет означать горизонтальную координату (номер столбца) начиная слева, а второе - вертикальную координату (номер строки) начиная сверху. Таким образом традиционная координата клетки "Г-2" будет в принятой нами системе выражаться как (4,2).

Координаты однопалубных кораблей могут быть произвольными в пределах размеров поля, а координаты многопалубных кораблей имеют ограничения, связанные с их размером. Так, для четырехпалубного корабля, расположенного горизонтально, горизонтальная координата может принимать только значения 1-7.

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

Прикинем вычислительную сложность алгоритма. Сколько всего комбинаций размещения вражеского флота нам придется рассмотреть?

Для четырех однопалубных кораблей будет рассмотрено по 100 возможностей, так что общее число рассмотренных комбинаций будет составлять N1 = 100^4=100000000. Это уже очень большое число, и составлять цикл с таким числом повторений на Спектруме мало смысла: его завершения придется ждать очень долго. И это только для четырехпалубных кораблей!

Для двухпалубных кораблей есть ограничения на координаты, но имеется две ориентации, так что каждый корабль может быть размещен 90+90=180 способами. Всего кораблей три, так что число комбинаций будет N2 = 180^3=5832000.

Для трехпалубных кораблей имеем 80+80=160 возможных размещений для каждого из них, всего 2 корабля, число комбинаций = N3 = 160^2=25600.

И, наконец, для четырехпалубного корабля, число всех рассматриваемых возможностей размещения будет N4 = 70+70=140

А всего для вражеского флота в полном составе будет рассмотрено N = N1*N2*N3*N4 ~= 2E+21 комбинаций. Это огромное число, которое не под силу не только Спектруму, но и современным компьютерам, по крайней мере, в рамках минуты - приемлемого времени "размышления" компьютера при выполнении очередного выстрела.

Поэтому моя теория оптимальной игры в "Морской бой" имеет трудности вычислительного характера. Отчасти мне удалось их решить, о чем и пойдет речь в следующих сообщениях.

[GriV]

Если под методом сетки ты имеешь в виду что-то типа метода Эйлера для решения дифуров - то нет, аналогии здесь не просматривается.

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

---------- Post added at 23:48 ---------- Previous post was at 23:45 ----------


Прикинем вычислительную сложность алгоритма. Сколько всего комбинаций размещения вражеского флота нам придется рассмотреть?

Имеется в виду, что каждый раз после промаха надо перерасчитывать эту матрицу, верно?

[Barmaley_m]

Метод сетки - это метод поиска значения любой (не обязательно гладкой) функции. Заключается в разбиении на части и сканирование гребёнкой.
Понятно. Нет, стрельба в "Морской бой" с точки зрения поиска по множеству размещения кораблей противника, не является аналогичной методу сетки. Даже неоптимальная стрельба наобум сходится экспоненциально, ведь прикинь порядок величины количества всех возможных размещений флота - 1E20! А даже в самом худшем случае, самой неудачной стрельбе, максимально за 100 выстрелов мы находим нужный элемент в этом множестве. Иначе, как экспонентой, такое множество нельзя победить за человеческое время :)

Имеется в виду, что каждый раз после промаха надо перерасчитывать эту матрицу, верно?
Да, надо пересчитывать, как в случае промаха, так и в случае попадания.

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

Ну и еще один метод есть для составления базы данных первых ходов и для расчетов в промежуточных ситуациях, который я собираюсь описать в следующих сообщениях. Это метод Монте-Карло. Он дает приближенный, не точный результат. А полный перебор всех 1E20 комбинаций - это задача неподъемная даже для современных компьютеров. Если представить себе, что в секунду мы рассматриваем миллиард размещений кораблей (1E9) - то для полного перебора потребуется 1E11 секунд - это около 3000 лет. Даже взлом 56-битного шифра DES является более легкой задачей (там меньше комбинаций).

[GriV]

Понятно. Нет, стрельба в "Морской бой" с точки зрения поиска по множеству размещения кораблей противника, не является аналогичной методу сетки. Даже неоптимальная стрельба наобум сходится экспоненциально, ведь прикинь порядок величины количества всех возможных размещений флота - 1E20!

В общем то количество состояний никакого отношения к методике решения задачи не имеет.
Вот метод сетки - http://ru.wikipedia.org/wiki/Метод_перебора


то для полного перебора потребуется 1E11 секунд

Здесь, возможно, можно делать первые выстрелы таким способом, чтобы они значительно сокращали подмножество оставшихся вариантов (тот самый дебют), а потом уже считать.

И ещё, можно хранить уже рассчитанные матрицы для первых 2-3 выстрелов (матрицы вероятности расположения). Можно сэкономить около 3e11 секунд :-)


Иначе, как экспонентой, такое множество нельзя победить за человеческое время

Оно побеждается правилами игры - расположением кораблей, их ориентацией и т.д.. При потоплении 4хпалубника сразу куча клеток улетает (мин 10, макс 18, коэффициент освобождения - min 250%, max 450%), а для однопалубника коэффициант освобождения даже выше (min 400% max 900%) :-) А методика поиска просто сокращает количество выстрелов до победы. При самом неудачном расположении кораблей и неудачном расположении промахов, это будет чуть меньше количество выстрелов, т.к. каждый корабль закрывает собой минимум ещё такое же количество клеток, сколько он сам занимает, т.е. 4+2*3+3*2+4*1 = 20, т.е. максимальное количество выстрелов будет 80.


А всего для вражеского флота в полном составе будет рассмотрено N = N1*N2*N3*N4 ~= 2E+21 комбинаций

А то, что установка предыдущего корабля резко сокращает количество вариантом для оставшихся - учитывается?

После установки 1нопалубников (если начинать с них), будет занято минимум 16 клеток, максимум - 36 клеток. Установка двухпалубников займёт минимум 18 максимум 36 клеток, установка трёхпалубников - мин 16, макс 30 клеток, 4хпалубный - мин 10, макс 18 клеток.

Если начинать сверху вниз (от больших кораблей к малым, что в общем то логичнее), то установка 4хпалубника (с вариантами = N4 = 140) cокращает для оставшихся кораблей число свободных клеток минимум на 10. Тогда для оставшихся трёхпалубников остаётся максимум 90 клеток.

Движок форума меня подвёл уже два раза :-( По привычке нажимаю "ответить" из окна правки сообщения... ну и текст сообщения теряется, хотя полдня набирал и считал.

Результаты расчётов получились такие:

N4 = 140
N43 = 17440 (установка 1го 4 и 1го 3хпалубного)
N433 = 1958320
N4332 = 228234080
N43322 = 23919593920
N433222 = 2,22688E+12
N4332221 = 1,1295E+14
N43322211 = 5,2956E+15
N433222111 = 2,28058E+17
N4332221111 = 8,95513E+18
У меня получилось около 280 лет на 1 млрд операций пересчёта в секунду, так что хоть и изменились сильно порядки (как у тебя 3000 лет получилось???), но задача пока далека от обозримого пересчёта.
Учёт заслоняемости кораблей может немного (я думаю около 20%) снизить количество вариантов, но там всё равно больше 2х веков.

Сама задача легко распараллеливается на суперкомпьютере.

Эй, есть тут у кого суперкомпьютер? :-) Нам для морского боя не хватает ;-)

[Andrew771]

После установки 1нопалубников (если начинать с них), будет занято минимум 16 клеток, максимум - 36 клеток. Установка двухпалубников займёт минимум 18 максимум 36 клеток, установка трёхпалубников - мин 16, макс 30 клеток, 4хпалубный - мин 10, макс 18 клеток.
Вот так и надо устанавливать, чтобы минимум клеток было занято после попадания. Тогда больше вероятность у противника не попасть.
У меня в реале была такая хитрая стратегия: все корабли от 2 до 4 клеток расставлялись по краям. Их, как правило, быстро подбивали. Зато в центре оставалось огроменное непаханное поле, где прятались в случайных клетках одиночные кораблики - долгая изнурительная угадайка для противника получалась, которую сложно обыграть. :)

[Barmaley_m]

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

Здесь, возможно, можно делать первые выстрелы таким способом, чтобы они значительно сокращали подмножество оставшихся вариантов
Совершенно верно, об этом я и говорил, когда обосновывал необходимость стрелять в те клетки, где рассчитанная вероятность нахождения корабля максимальна, поскольку даже при промахе в этих клетках подмножество оставшихся вариантов сокращается быстрее всего.

(тот самый дебют), а потом уже считать.

И ещё, можно хранить уже рассчитанные матрицы для первых 2-3 выстрелов (матрицы вероятности расположения). Можно сэкономить около 3e11 секунд :-)
Вот, ты пришел к тому же выводу, что и я в предыдущем сообщении. Более того, хранение базы данных дебютов в "Морском бое" можно сделать довольно глубоким, до 7-8 ходов и более. Это ведь в шахматах каждый ход имеет очень много вариантов, поэтому базы данных дебютов имеют большой размер, а в "морском бое" все проще.

А методика поиска просто сокращает количество выстрелов до победы.
Вот именно, наша задача как раз и заключается в максимальном сокращении кол-ва выстрелов, чтобы противник не успел за это же количество выстрелов уничтожить наш флот.

При самом неудачном расположении кораблей и неудачном расположении промахов, это будет чуть меньше количество выстрелов, т.к. каждый корабль закрывает собой минимум ещё такое же количество клеток, сколько он сам занимает,
Но ты не учитываешь, что можно ведь в случае неудачи сначала обстрелять все клетки вокруг корабля, а только потом подбить сам корабль, т.е. окружение его ореолом клеток после подбития само по себе уже не поможет в такой ситуации сократить поле для дальнейшего поиска.

Я вот не знаю пока, можно ли обосновать для конкретной методики максимальное количество выстрелов до потопления флота противника в наихудшем случае, т.е. при самой неудачной стрельбе. Может быть мы вернемся к этому вопросу после полного составления алгоритма для стрельбы.

А то, что установка предыдущего корабля резко сокращает количество вариантом для оставшихся - учитывается?
Существует разница между тем, какие комбинации подвергаются анализу алгоритмом, который я ранее описал, и какие из них являются допустимыми по правилам "Морского боя". Я вот пока не нашел способа, чтобы до анализа комбинации, определить, допустима ли она по правилам. Или, иначе говоря, генерировать только такие расположения кораблей, которые заведомо являются допустимыми. Поэтому нет, сокращение вариантов для оставшихся не учитывается. Мой алгоритм должен перебрать все расположения, как допустимые, так и недопустимые, но конечно же, в результат расчета вероятностей эти недопустимые расположения не включаются. А вот во время выполнения программы они включаются, к сожалению.

Я сильно подозреваю, что множество допустимых расположений кораблей значительно, в сотни раз меньше, чем общее множество всех координат кораблей, по которому я веду перебор своим алгоритмом. О точном соотношении количества элементов в этих двух множествах мы еще поговорим - это не праздный вопрос.


Результаты расчётов получились такие:

N4 = 140
N43 = 17440 (установка 1го 4 и 1го 3хпалубного)
Как ты получил это и следующие числа, можно подробнее?
Рассмотрим следующую ситуацию. Допустим, у тебя 4-палубник стоит вертикально в координате (4,1). Ты при этом не можешь разместить трехпалубник горизонтально в клетках типа (1,1), потому что он будет соприкасаться с четырехпалубником, хотя вроде бы клетки в прямоугольнике с диагональю (1,1)-(2,5) свободны. Учитывает ли твой расчет такие ситуации, особенно когда кораблей на поле уже несколько?


(как у тебя 3000 лет получилось???),
миллиард секунд - 30 лет примерно, у нас было около 100 миллиардов секунд - что и составляет 3000 лет; тут в общем-то точность прикидок и не важна особо, всяко ведь не доживем :)

Сама задача легко распараллеливается на суперкомпьютере.
Это да. Шутки шутками, но для составления базы дебютов вполне можно себе позволить погонять свои компы с недельку-другую, а если еще с товарищами объединиться - то и вовсе дело в шляпе. Ну, проги для расчетов, понятное дело, желательно будет оптимизировать, чтобы зря электричество не жечь.

[GriV]

Как ты получил это и следующие числа, можно подробнее?
Рассмотрим следующую ситуацию. Допустим, у тебя 4-палубник стоит вертикально в координате (4,1). Ты при этом не можешь разместить трехпалубник горизонтально в клетках типа (1,1), потому что он будет соприкасаться с четырехпалубником, хотя вроде бы клетки в прямоугольнике с диагональю (1,1)-(2,5) свободны. Учитывает ли твой расчет такие ситуации, особенно когда кораблей на поле уже несколько?
Я как раз и написал, что полдня алгоритм писал сюда (его описание), но изза кривизны своих же рук похерил это сообщение.

1. Ставим 4х палубный.
Будет 20 вариантов по 12 клеток, 8 вариантов по 10 клеток, 32 варианта по 15 клеток и оставшиеся 80 вариантов по 18 клеток
2. Ставим 1й 3хпалубник. Тут для каждого из вариантов предыдущего расположения надо так же разбивать его варианты по 10, 8, 12, 15 клеток, причём я полностью тогда расписал (сейчас лень повторять, но следя за рассуждением ты сможешь повторить эти рассуждения сам) что есть проблема что 4хпалубник может закрыть некоторые комбинации для 3хпалубника (это часть вариантов для 15 и 18 клеточного расположения 4хпалубника), оттуда получилось N43 самым точным и подсчитанным.
3. Дальше ветвить стало просто сложно и стало тем более сложно это описывать, поэтому я просто брал что в дальнейшем остаётся некое число клеток, уже откусанное кораблями и для них высчитываются варианты. Откусывается самое минимальное количество (4 - для 1но, 6 - для 2х, 8 - для 3х палубных кораблей), что в общем то делает результат больше чем действительное значение. Для набора кораблей есть тема что они могу закрыть расположения, не связанные с близостью длинного корабля и борта. Т.е. если в один ряд положить 4палубник и 2 трёхпалубника, то ряд может быть полностью закрыт и отсекается около половины поля для двухпалубников определённого расположения. Это я тоже не учитывал.
Собственно потому и написал, что реальный результат будет ниже, а полученные значения вариантов завышены.
А в чём проблема считать "легальные" расположения кораблей? долго?
Я приложил вычисления экселя, вот смотри как считал.

[GriV]

Количество состояний в "морском бое" уменьшается экспоненциально с каждым выстрелом, а метод перебора сходится к решению линейно.
Используй ты золотое сечение, метод бисекции или метод гребёнки - каждый выстрел уменьшает вероятности расположений экспоненциально. Я не вижу что хоть один из методов обладает преимуществом. Результат хоть при переборе, хоть при любом другом методе - 100 выстрелов максимум. Поэтому - ещё раз - сложность вычисления вероятностей никак не связана тем, как уменьшаются вероятности. В разных ситуциях разные методы (не в общем случае, а в частном) будут давать разное (не)преимущество.
Без разницы какую ты выберешь методику - главное чтобы оно как можно сильнее уменьшало оставшиеся варианты, а вот для этого уже тебе и надо использовать понимание того, что осталось на доске.


довольно глубоким, до 7-8
это как? У тебя на каждый ход вначале 100, потом 99, потом 98, потом 97 и т.д. (если ничего не подбил, конечно) вариантов развития. Итого на 7 это будет 100*99*98*97*96*95*94 = 8,06781E+13. У меня тут такие цифры получаются аж страшно. Или ты что то другое имеешь в виду?


Но ты не учитываешь, что можно ведь в случае неудачи сначала обстрелять все клетки вокруг корабля, а только потом подбить сам корабль, т.е. окружение его ореолом клеток после подбития само по себе уже не поможет в такой ситуации сократить поле для дальнейшего поиска.
Согласен :-)

---------- Post added at 01:48 ---------- Previous post was at 01:35 ----------

Сейчас понял, что для 4хпалубного относительно 3хпалубного надо ещё сильнее сузить количество вариантов, не учёл что прислонённый к борту 4хпалубник может тоже мешать установке 3хпалубника в некоторых ситуациях... Можно подумать как это сделать, но именно правила тут являются тем самым, что сильно срезает количество вариаций расположения.

[Barmaley_m]

Как мы уже убедились, в том числе с помощью GriV, даже подсчитать, сколько всего существует легальных комбинаций размещения кораблей - непростая задача. Мне удалось применить к ее решению метод Монте-Карло. Сначала рассмотрим аналогичную задачу.

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

Метод Монте-Карло заключается в том, чтобы сгенерировать некоторое количество (N) случайных точек, равномерно распределенных по прямоугольнику U (рис. 2), и посчитать, сколько из них (M) находятся внутри области D. Тогда отношение M/N будет приблизительно равно отношению площадей D/U. Зная площадь U, таким образом, можно найти площадь D. Результат будет тем точнее, чем больше сгенерировано точек.

Теперь посмотрим, как эту концепцию можно применить к вычислению количества легальных размещений кораблей в игре "Морской бой".

Рассмотренные выше прямоугольник U и область D - это, в сущности, множества, при этом множество U включает в себя множество D. При расчетах для "Морского боя" мы имеем, с одной стороны, множество всех координат кораблей U, размер которого легко подсчитать (в одном из предыдущихсообщений я привел результат - около 2E+21). С другой стороны мы имеем множество легальных размещений кораблей D, границы которого определить трудно, но точно известно, что D является подмножеством U. Для любого элемента Xi множества U (таким элементом является комбинация коорданат и ориентации кораблей) мы можем проверить, принадлежит ли этот элемент множеству D (является ли комбинация координат и ориентаций легальной по правилам "Морского боя"). Для применения метода Монте-Карло необходимо сгенерировать некоторое количество (N) случайных комбинаций координат кораблей Xi и проверить, сколько из них (M) являются легальными. Разделив M на N и умножив на количество элементов U, получим оценку количества элементов D, которая будет тем точнее, чем больше N.

Поскольку без ограничений на пересечения и ореолы кораблей, корабли друг другу не мешают, можно обоснованно считать, что мы будем генерировать случайные размещения Xi, равномерно распределенные по множествам U и D, если будем брать равномерно распределенные, независимые случайные числа в качестве координат и ориентации каждого корабля.

[Barmaley_m]

Публикую программы, реализующие вышеописанный алгоритм Монте-Карло. Для ускорения получения результата я написал их на Матлабе. Запускать следует скрипт "mc_ship_placement.m". Он генерирует случайные комбинации координат кораблей Xi до тех пор, пока не будет сгенерировано 1000 легальных комбинаций. При этом подсчитывается общее число сгенерированных комбинаций.

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

Результат работы моей программы: для получения M=1000 легальных комбинаций было сгенерировано N=3857458 случайных размещений кораблей. Иными словами, в среднем имеется одно легальное размещение кораблей на 3857 комбинаций произвольных их координат и ориентаций. Метод Монте-Карло сходится медленно, и поэтому мой результат имеет погрешность. Существуют обоснованные теоретически формулы для оценки этой погрешности, но мне лень сейчас их искать. Грубо можно прикинуть, что в полученном мною числе верны первые две значащие цифры. Поэтому, учитывая, что существует примерно 2E+21 комбинаций координат кораблей, из них легальных примерно в 3900 раз меньше. А всего в "Морском бое" существует примерно 5.42E+017 допустимых комбинаций размещения кораблей.

[Barmaley_m]

Хочу заметить, что несмотря на довольно долгое время работы моих программ на довольно быстром компьютере, получено было не очень много комбинаций, и еще меньше - легальных. Мои программы нуждаются в переводе на C и оптимизации, чтобы выдавать более точные результаты.

[Barmaley_m]

Переписал программу на Си, чем удалось добиться ее ускорения более чем в 100 раз. Если раньше мне приходилось довольно долго ждать чтобы получить хотя бы 1000 допустимых правилами случайных комбинаций размещения кораблей, то теперь с легкостью удается генерировать десятки тысяч таких комбинаций.

Например, после первого запуска моей программы было перебрано 300 миллионов комбинаций координат кораблей, из них оказалось допустимыми 76944, а соотношение составляет 1:3898.

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

Я не вылизывал сильно эту программу, поэтому думаю, что в рамках языка Си ее можно еще более ускорить, а в перспективе - перевести на ассемблер, с использованием векторных инструкций MMX. Вот тогда ее можно будет запускать на неделю всем сообществом и потом дружно анализировать результаты.

[Barmaley_m]

Немного переделал программу, чтобы она крутилась в бесконечном цикле и сохраняла полученные комбинации в файлы.

Пришлось отказаться от библиотечного генератора случайных чисел 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]

Дальнейшая генерация случайных размещений кораблей и сохранение их в файлы лишь для целей определения соотношения количества допустимых комбинаций к общему количеству координат кораблей - это стрельба из пушки по воробьям. Даже один прогон 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 комбинаций, и она имела тот же вид, только была более зашумлена. Так что метод Монте-Карло для ее расчета действительно сходится к некоторому пределу.

Любопытно, не правда ли? Максимальные шансы попасть в корабль имеются у границ поля, но не в углах! Излюбленное место для размещения кораблей опытных игроков, было найдено моим методом без каких-либо указаний на предпочтения игроков и их стратегии!

[GriV]

Метод Монте-Карло
По большому счёту у меня почти такое же соотношение и получилось, однако метод дал распределения :-) А как это в режиме реального времени считается? И опять же, как хранить на несколько ходов вперёд? Ведь вариантов много?

[Barmaley_m]

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

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

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

[GriV]

1) Хранить много комбинаций размещения кораблей. Допустим, несколько десятков мегабайт - это не проблема для современных компьютеров. Как я посчитал, любая коминация может быть закодирована 71 битами, что округляется до 9 байт (72 бит).
Речь про спектрум или вообще?


Не так уж и много. Посмотри карту вероятностей для необстрелянного поля. На ней существует 8 клеток с максимальной вероятностью
Даже если так, то хранение наиболее вероятных клеток подразумевает какое то хранение предыдущего состояния. Соотвественно каждый выстрел подразумевает ветвление... Не знаю как ты собираешься на 8 ходов хранить таблитсы...

[Barmaley_m]

Речь про спектрум или вообще?
Для начала - хотя бы вообще, а потом будет видно, можно ли реализовать алгоритм на Спектруме, сохранив его эффективность (хотя бы частично).

У меня в этом деле такой подход, чтобы двигаться к решению постепенно и не пытаться заткнуть сразу все дыры.

Даже если так, то хранение наиболее вероятных клеток подразумевает какое то хранение предыдущего состояния. Соотвественно каждый выстрел подразумевает ветвление... Не знаю как ты собираешься на 8 ходов хранить таблитсы...
Ну смотри, допустим для начала простой случай - клетка с максимальной вероятностью одна после каждого выстрела. Ее координаты можно закодировать 7ю битами. После каждого хода идет ветвление на 2 направления: попал или не попал. Количество клеток для запоминания после каждого хода будет увеличиваться в 2 раза, так что мы имеем дело с суммой геометрической прогрессии. Для запоминания всех ветвлений из 8 ходов достаточно 511 координат, что равняется 448 байтам (у нас 7 бит на одну пару координат). Вполне приемлемо даже для Спектрума. Если клеток с макс. вероятностью больше одной после каждого хода - то таблица возрастет в несколько раз, но мне бы даже 32кБ было не жалко для такой таблицы, а то и под завязку забить всю память до 128К.

Таблицу можно также оптимизировать, как это делается и в шахматах, сохраняя более интересные ветки с большей глубиной, чем менее интересные. Скажем, промахнуться при первых выстрелах больше вероятность, чем попасть, поэтому ветки, начинающиеся с промахов, можно сохранять с большей глубиной. А когда будет подбито несколько вражеских кораблей - то может стать возможным рассчитывать оптимальную стрельбу в реальном времени, так что эти ветки тоже сохранять не надо.

[GriV]

Для запоминания всех ветвлений из 8 ходов достаточно 511 координат
Погоди, а разве не по количеству оставшихся клеток будет увеличиваться вероятность? И потом, ты хочешь использовать детерменированный алгоритм? Комп всегда будет начинать встрелать в клетку (1,1), потом (1,2) и т.д.? Тогда алгоритм будет уязвимым.

[Barmaley_m]

Погоди, а разве не по количеству оставшихся клеток будет увеличиваться вероятность?
Что ты имеешь в виду?

И потом, ты хочешь использовать детерменированный алгоритм? Комп всегда будет начинать встрелать в клетку (1,1), потом (1,2) и т.д.? Тогда алгоритм будет уязвимым.
Не совсем детерминированный. Для каждого хода будет выбор из нескольких клеток (положим, до 4х), и компьютер будет выбирать одну из них случайно.

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

Я уже раньше рассматривал аналогию этой ситуации с угадыванием чисел методом половинного деления. Зная о том, каким методом пользуется угадывающий, загадывающий игрок может оттянуть свой конец, но не более, чем на некоторое число ходов, соответствующее наихудшему случаю.

Стрельба в клетки с максимальной вероятностью попадания, которую я сейчас реализую, оптимизирует как каждый конкретный выстрел, так и число ходов для наихудшего случая, когда все выстрелы, какие только возможно, идут мимо кораблей. Любые отступления от этой стратегии могут увеличить число выстрелов для наихудшего случая. Противник лишь может пытаться реализовать этот наихудший случай. Но к адаптации противника уязвимы любые стратегии, в принципе. Какой бы метод мы ни реализовали - могут существовать способы располагать корабли специально так, чтобы этот метод долго их не мог найти.

Наличие же некоторой, хоть и небольшой, случаности в выборе координат для следующего выстрела затрудняет адаптацию противника к нашей стратегии. Так же как можно сделать вариацию алгоритма угадывания чисел от 1 до 100 с добавкой случайности, которая уменьшила бы шансы противника реализовать наихудший случай при угадывании, при этом не увеличивая число ходов для наихудшего случая, если он все-таки реализуется.

[GriV]

Что ты имеешь в виду?
Ты написал что на кучу комбинаций у тебя уйдёт около 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 ходов.

[GriV]

Вот, немного не в тему, ребята рассчитали судоку для однозначного разрешения. Там тоже матстат и аналитика: В Ирландии рассчитали минимальное количество подсказок в судоку (http://www.fcenter.ru/online.shtml?softnews/2012/01/12#material_id=32735)