Pull to refresh

Comments 17

Итак, теперь вы знаете как оптимально вести огонь по противнику
Я бы не назвал такой алгоритм «оптимальным».

Так, если на поле осталось пять клеток в линии и два корабля 1х2, то оптимальный алгоритм уничтожит их за 4 выстрела без промахов. Ваш же алгоритм определит, что «вероятность» нахождения корабля в центре — максимальна, и может попытаться выстрелить туда (в одном случае из трех).

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

Все это, я так думаю, еще долго не сможет проделать ни один компьютер (разве что Deep Blue на морской бой переделают), но другие алгоритмы называть «оптимальными» не следует.
Осталось только стравить два таких оптимальных алгоритма!
Делающий первый ход будет побеждать не менее чем в половине случаев при оптимальной игре обоих сторон. Это и так ясно, можно никого не стравливать.
Спасибо за комментарий! По поводу учёта всей эскадры — Вы абсолютно правы. Добавил в статью.
Кстати, посчитать все комбинации для обычного морского боя (10x10, прямые корабли) возможно и несложно — написанная «на коленке» программа справляется быстрее, чем за минуту. Полное число комбинаций у меня получилось 1855545978831780, самая заполненная клетка — A3 (и симметричные ей) — на них корабли есть в 475795243932227 случаях (25.6%), самая незаполненная — Б2 (и симметричные) — она заполнена в 273993917558420 случаях (14.7%).
Конечно, перебрать возможные стратегии противника и найти седловую точку в полученной матрице игры значительно сложнее.
Вот про стратегии я и говорил, потому что без учета возможных стратегий противника все эти подсчитанные комбинации разбиваются простейшей расстановкой кораблей по краям поля.
Не разбиваются: по краям поля как раз находятся самые популярные клетки.
Хм, моя интуиция говорила обратное… Но нам ничего не мешает сунуть катеры в Б2 и симметричные. Это для алгоритма уж точно окажется подляной.
Ваш алгоритм — это лишь первый шаг к определению вероятности размещения корабля или его фрагмента в данной клетке. Я проводил более глубокий анализ этого вопроса в теме на форуме о ZX Spectrum. При этом рассматривалась вероятность не только подбить самый длинный из оставшихся кораблей противника, а вероятность подбить хоть какой-нибудь корабль при любых возможных способах размещения на поле всех кораблей. Из этого алгоритма естественным образом следует обстрел краев поля в начале игры как наиболее вероятных мест нахождения кораблей противника; также для добивания корабля после того, как он был «ранен», не требуется отдельная ветка алгоритма. В принципе могут существовать даже ситуации, когда искать другой корабль на поле выгоднее, чем добивать ранее найденный (вероятность попасть выше), но они редки, так что мой алгоритм обычно будет все-таки добивать.

К сожалению, мой «всеобъемлющий» подход столкнулся со сложностями вычислительного характера, что даже на современных компьютерах просчитать все комбинации невозможно, а можно лишь искать некоторое приближение методом Монте-Карло, но и это оказалось затруднительно в реальном времени. Пока что работа над дальнейшим развитием алгоритма остановлена, но может быть я когда-нибудь вернусь к этому. А тему почитайте, там интереснее, чем во многих других исследованиях «Морского боя», в том числе тех, что были уже на Хабре, или у Перельмана.
Меня уже третий пост мучает мысль об отсутствия необходимости добивать. В принципе для победы важнее не затопить больше клеток (например линкор), а обнаружить все корабли (например все катера). А ранив корабль, мы тем самым уменьшаем вероятность нахождения другого корабля рядом. Т.е. если линкор потоплен, а я ранил не катер, то вероятность нахождения в соседней клетке другого корабля равна нулю, через клетку чуть уже больше, но не 0.5. К около 0.5 она повысится только на достаточном удалении от места ранения. Я думаю это не такой редкий случай и он может резко изменить ход боя. Эх, написать бы пару AI, натравить бы их друг на друга и посмотреть статистику.
Спасибо! Мысль интересная — надо попробовать.
Спасибо! Постараюсь ознакомиться с Вашим исследованием. Добавил ссылку в статью.
Статья интересная, скриншоты красивые.
Я, конечно, не вы, но на вашем месте, был бы чуть более осторожным со словом «оптимальный».

<зануда>
Для того, чтобы доказать, что метод/алгоритм/и т.п. оптимальный, надо сначала определить показатель эффективности, общий для всех возможных алгоритмов (для данной задачи). А уже потом доказать, что рассматриваемый алгоритм обеспечивает минимальное/максимальное значение этого показателя эффективности ;-)
</зануда>
Всё верно: «оптимальный» тут не к месту. Исправлю.
Only those users with full accounts are able to leave comments. Log in, please.