Привет, Хабр! Продолжая неделю морских боев, хочу предложить еще один способ построения оптимальной стратегии стрельбы.
Он использует древовидное представление стратегии, что довольно распространено в теории игр.
Представление задачи в виде таблицы решений заимствовано из теории испытаний, которая была популярна в 70-е годы прошлого века и использовалась, в частности, для контроля и диагностики неисправностей электронных схем.
Этот метод позволяет найти оптимальную стратегию, но имеет очень высокую вычислительную сложность.
К сожалению, проанализировать игру на поле 10х10 не удалось.
Древо решений
А когда Великобритания, а затем и Германия построили дредноуты, война между ними стала неизбежной.(Вольная цитата из пьесы «Дредноуты» Е.Потому что, кроме вопросов о тактике применения новых кораблей, на которые можно было хоть как-то ответить умозрительно, был такой, на который теоретически ответить совершенно невозможно.
Звучало это так: «ЧЬИ DEADNIGHTS ЛУЧШЕ?!»
Гришковца) Для начала давайте найдём удобный способ представления стратегии в виде дерева решений.
Например, вот как можно расстрелять крейсер и две лодки на поле 3х3. 
На вершинах дерева расположено игровое поле с уже сделанными выстрелами.
Текущий кадр отмечен красным.
Ребрам присваивается результат удара: промах (.
) или попадание (х).
На листьях показано расположение кораблей.
Стратегию можно описать такими словами.
Сначала мы стреляем в б1 .
Если ударим, то станет понятно, как расположены корабли, и останется только их добить.
Если нет, то стреляем в в 2 .
Если мы доберемся туда, все снова станет ясно.
Если мы промахнемся, останется два варианта позиции и удар по б3 вносит окончательную ясность.
Понятно, что так можно описать любую стратегию стрельбы; все, что потребуется, это бумага.
Но чтобы найти хорошую стратегию, нам нужно формализовать то, чего мы действительно хотим.
Отметим, что стратегия описывает действия игрока «на все случаи жизни», а конкретная игра с ее расположением кораблей описывается путем в дереве от корня до одного из листьев.
Доиграв до конца и победив, мы ударим столько раз, сколько было труб на кораблях противника.
Правила можно переформулировать так: каждый игрок стреляет до полного уничтожения вражеской эскадрильи, а затем побеждает тот, у кого меньше промахов.
Это означает, что хорошая стратегия отличается от плохой количеством ошибок.
И теперь у нас есть два варианта.
Оценить стратегию можно по тому, сколько ошибок она допустит в худшем случае.
Тогда из двух стратегий лучше та, которая имеет минимальное количество промахов на пути от корня к листу.
Либо можно предположить, что противник выбирает локацию случайным образом с равной вероятностью, и попытаться уменьшить ожидал количество промахов.
Тогда из двух стратегий лучшей будет та, у которой сумма промахов по всем путям от корня каждого из листьев листа будет наименьшей.
Например, наша стратегия позволяет гарантировать уничтожение кораблей не более чем за три промаха, а ожидаемое количество промахов равно (3+2+1+0)/4=1,5. Кстати, вы можете попытаться найти стратегию, которая будет лучшей в обоих смыслах.
Звучит заманчиво? К сожалению, обе задачи слишком похожи на NP-hard. задать задачу покрытия , что обещает нам отсутствие простых алгоритмов решения.
Но, проявив терпение и компьютерное время, мы все равно попробуем что-нибудь сделать.
Таблица решений и алгоритмы построения стратегии
Представим задачу в виде так называемой таблицы решений.Построим прямоугольную таблицу, в которой столбцы соответствуют клеткам игрового поля, а строки – всем возможным вариантам расположения кораблей.
Ячейка таблицы на пересечении строки и столбца содержит знак «Х», если в данной ячейке игрового поля находится корабль в заданном расположении кораблей, и «.
» в противном случае.
Например, вот таблица, описывающая четыре возможных варианта расположения крейсера и двух лодок на поле 3х3 (каждой строке справа отведена ячейка, в которой находится середина крейсера - в нашем примере это однозначно определяет местонахождение кораблей).
Глядя на таблицу, можно понять, что стрелять по Би 2 , потому что корабля там нет ни в какой комплектации.
Выстрелы в а1 , а3 , в 1 , в 3 гарантирует попадание, но не дает дополнительной информации о местонахождении кораблей.
Их можно выполнить вначале, чтобы запугать противника.
Выстрел в каждую из оставшихся ячеек при попадании однозначно определяет линию, а при промахе уменьшает количество гипотез на одну.
Вы можете представить этот процесс как удаление строк из таблицы, которые противоречат накопленной информации.
Приближенный жадный алгоритм строит дерево, начиная с корня.
Алгоритм выбирает столбец таблицы (ячейку для стрельбы) так, чтобы доля строк, в которых есть корабль в этой ячейке, была как можно ближе к 1/2. Выделенная ячейка присваивается корню дерева, от корня рисуются два ребра, соответствующие промаху/попаданию, и к концам ребер присоединяются две новые вершины.
Каждая из новых вершин получает подтаблицу, в которой вычеркиваются строки, противоречащие результатам первого выстрела.
Та же процедура применяется к каждому из листьев, пока все результирующие таблицы не будут содержать только одну строку.
Соответствующие вершины становятся листьями, и алгоритм завершается.
Другой алгоритм использует динамическое программирование.
Он анализирует огромный граф подтаблиц, но гарантирует, что найденное решение является оптимальным.
К сожалению, подробный рассказ об этом заслуживает отдельного поста.
Когда-нибудь соберусь с силами и напишу, а сейчас предлагаю поверить в его существование и перейти к экспериментальной части.
Ээксперимент
Теоретик решает, что он может, как нужно, а практик решает, что нужно, как может.Количество конфигураций (1,85*10 15 ), озвученный уважаемым Мррл , застал меня в процессе написания кода и изрядно охладил мой пыл.
Подумав, я решил закончить работу, при этом уменьшив размер поля.
Точный алгоритм согласился отработать задачу стрельбы по эскадре из одного крейсера, двух эсминцев и трех лодок на поле 5х5. Число возможных конфигураций всего 1428, но граф подзадач состоит из внушительных 10 191 257 вершин и 214 464 800 ребер.
Оптимальный алгоритм позволяет уничтожить эскадрилью не более чем за семь промахов, а в среднем она совершает 4,51 промаха.
На рисунке ниже показано, как можно определить положение кораблей по пяти промахам (т.е.
при реализации самой правой ветви дерева решений).
Жадный алгоритм для той же задачи построил стратегию, допускающую в худшем случае 11 промахов с ожидаемым количеством промахов 5,46. На рисунке ниже показана стратегия промаха (самая правая ветвь дерева решений).
Краткое содержание
Классический жадный алгоритм работал плохо.Я думаю, что это помогло бы минимизировать длину пути в дереве, а количество промахов явно требует другого эмпирического подхода для выбора ячейки для стрельбы.
Точный алгоритм решил проблему с половиной кораблей на четверти поля, так что хвастаться особо нечем.
Немного греет душу то, что для этой небольшой задачи мы теперь знаем количество промахов для оптимальной стратегии (7 в худшем случае, в среднем 4,51).
Буду рад, если это поможет коллегам в построении приближенных алгоритмов.
Обновлять
1) Рассматриваемая задача отличается от классического «морского боя» тем, что вместо «убит» игрок дает ответ «попал».Введение третьего ответа не позволяет нам описать подзадачу только списком мест, совместимых с предыдущими снимками, и применить к решению динамическое программирование.
Я понятия не имею, как искать оптимальный алгоритм для классической задачи — кроме как прямым поиском с исключением проверенных неоптимальных ветвей.
2) Жадный алгоритм, выбирающий на каждом шаге столбец с максимальным количеством символов.
Икс (т.е.
выбирая клетку для выстрела с наибольшей вероятностью обнаружения корабля), показывает результат, близкий к оптимальному: 8 промахов в худшем случае и 4,595 в среднем.
Введение ответа «убит» существенно повышает производительность: 4 промаха в худшем случае и 2,04 промаха в среднем.
Спасибо Мррл за дополнения.
Теги: #Алгоритмы #линкор #распознавание образов #Алгоритмы
-
Азбука Выбора Веб-Хостинга
19 Oct, 24 -
Слякоть 2018. Предварительный День
19 Oct, 24 -
Почему Openvpn Медленный?
19 Oct, 24 -
Галерея С Использованием Slimbox 1.4
19 Oct, 24 -
Нио: Между Сциллой И Харибдой?
19 Oct, 24 -
Как Мы Придумали Систему Анализа Текста
19 Oct, 24
