Возможно, материалов, которые я выложу на этой ветке, будет достаточно для написания статьи. Если хватит времени и вдохновения - я этим займусь. Что такое хабр?Сообщение от osa
---------- Post added at 01:04 ---------- Previous post was at 00:07 ----------
Итак, продолжим. Рассмотрим главный недостаток моего бота 1996-1997г: он неэффективен в случае размещения кораблей противника у краев поля. Противник мог легко заметить тенденцию моего алгоритма начинать обстрел с центра, и размещать свои корабли всегда у краев. Тем самым он получал огромное преимущество, фактически гарантируя промах бота на первой паре десятков выстрелов.
Размещение длинных кораблей у краев поля вовсе не является редкостью для игры в "Морской бой". Наоборот, большинство опытных игроков только так свои корабли и расставляют. Причина - то, что подбитие длинного корабля в центре поля окружает его большим ореолом из клеток "мимо", тем самым значительно сужая поле для дальнейших поисков. Данный вопрос был рассмотрен детально Я.И. Перельманом (1882-1942), российским и советским ученым, популяризатором науки. Статья "Морской бой" в русской Википедии со слов Перельмана описывает стратегию, основанную на размещении кораблей у краев поля, и обосновывает ее преимущество. То же описано в статье пользователя habrahabr.ru Подсознание - "Теория и практика игры «Морской бой» — по-честному", на которую дал ссылку esl.
Очевидно, что алгоритм стрельбы надо каким-то образом изменить, чтобы он больше обстреливал края поля. Но как, по каким критериям? За прошедшие со времени создания моего бота более 10 лет я иногда возвращался к размышлениям на эту тему, но так до недавних пор и не смог придумать хорошего решения. Если приблизительный расчет вероятности, основанный на подсчете числа возможностей размещения, говорит о том, что корабль более вероятно находится в центре поля - значит стрельба куда-либо, кроме центра, в общем случае уменьшает вероятность попадания. И только в специальном случае, когда противник специально размещает корабли у краев, где найти их легче, чем в центре (если знать, что они там) - такая стрельба имеет преимущество. Одно дело человеку понимать все это, а другое дело - реализовать в программе. Это была бы своего рода стрельба, адаптивная к противнику: если бы бот решил, что человек имеет тенденцию размещать корабли у краев - то он начал бы охотнее обстреливать края, а если нет - то снова смещал бы акцент в центр. Интуитивно понятно, но формальных критериев нет по-прежнему. Поэтому я не пытался реализовать эти идеи в виде программы, уж очень все было зыбко. Как потом убедиться, что бот играет сильнее, чем предыдущий? Особенно если противник начал бы адаптироваться к его новому поведению и снова принял какую-то иную стратегию размещения кораблей, которая обеспечила бы ему преимущество?
Другой, менее значимый недостаток бота - это то, что он всегда сосредотачивался только на поиске 4-палубника. Ясно, что подбитие любого корабля очень желательно в ходе игры, так как выводит из круга поиска больше клеток, чем занимает сам корабль. Поэтому, если на поле складывается ситуация, что высоко вероятно нахождение трехпалубника в конкретном месте (т.е. велик шанс его подбить) - мой первоначальный алгоритм не воспользовался бы этой возможностью, предпочитая охотиться за 4-палубником, даже если клетки, где он еще может быть размещен, имеют число возможностей размещения много меньше 8.
Второй недостаток решается легким изменением алгоритма стрельбы. В подсчете числа возможностей размещения учитывается теперь не только четырехпалубник, но и трех- и двухпалубники. Число возможностей их размещения в каждой клетке теперь суммируется, и стрельба снова проводится в одну из клеток, где это число достигает максимума.
В такой ситуации возможно наличие клеток с максимумами числа возможностей размещения всех кораблей, которые не совпадают с клетками максимумов для одного лишь 4-палубника. В целом такая стрельба является более эффективной, но все же проблема размещения кораблей у краев не решается и здесь. Модифицированный алгоритм по-прежнему выдает низкие числа у краев поля, тем самым ставя их на последнее место в очередь для обстрела.
Вопросов накопилось больше, чем ответов, и вот недавно я созрел к математической атаке на "Морской бой" с целого ряда направлений, о чем и пойдет речь ниже.
Ответить с цитированием
