Комментарии 17
Итак, теперь вы знаете как оптимально вести огонь по противникуЯ бы не назвал такой алгоритм «оптимальным».
Так, если на поле осталось пять клеток в линии и два корабля 1х2, то оптимальный алгоритм уничтожит их за 4 выстрела без промахов. Ваш же алгоритм определит, что «вероятность» нахождения корабля в центре — максимальна, и может попытаться выстрелить туда (в одном случае из трех).
Оптимальный алгоритм должен
1) при подсчете вероятности размещать на поле не один корабль, а всю эскадру противника с учетом ограничений на соседство;
2) учитывать, что противник может намеренно разместить свою эскадру в наименее вероятной позиции (по краям, например), и предпринимать ответные действия уже в первой игре, вместо обучения под конкретного соперника. Обучение под соперника, хотя и является неплохим ходом, не поможет, если соперник действует оптимально.
Все это, я так думаю, еще долго не сможет проделать ни один компьютер (разве что Deep Blue на морской бой переделают), но другие алгоритмы называть «оптимальными» не следует.
Осталось только стравить два таких оптимальных алгоритма!
Спасибо за комментарий! По поводу учёта всей эскадры — Вы абсолютно правы. Добавил в статью.
Кстати, посчитать все комбинации для обычного морского боя (10x10, прямые корабли) возможно и несложно — написанная «на коленке» программа справляется быстрее, чем за минуту. Полное число комбинаций у меня получилось 1855545978831780, самая заполненная клетка — A3 (и симметричные ей) — на них корабли есть в 475795243932227 случаях (25.6%), самая незаполненная — Б2 (и симметричные) — она заполнена в 273993917558420 случаях (14.7%).
Конечно, перебрать возможные стратегии противника и найти седловую точку в полученной матрице игры значительно сложнее.
Конечно, перебрать возможные стратегии противника и найти седловую точку в полученной матрице игры значительно сложнее.
Ваш алгоритм — это лишь первый шаг к определению вероятности размещения корабля или его фрагмента в данной клетке. Я проводил более глубокий анализ этого вопроса в теме на форуме о ZX Spectrum. При этом рассматривалась вероятность не только подбить самый длинный из оставшихся кораблей противника, а вероятность подбить хоть какой-нибудь корабль при любых возможных способах размещения на поле всех кораблей. Из этого алгоритма естественным образом следует обстрел краев поля в начале игры как наиболее вероятных мест нахождения кораблей противника; также для добивания корабля после того, как он был «ранен», не требуется отдельная ветка алгоритма. В принципе могут существовать даже ситуации, когда искать другой корабль на поле выгоднее, чем добивать ранее найденный (вероятность попасть выше), но они редки, так что мой алгоритм обычно будет все-таки добивать.
К сожалению, мой «всеобъемлющий» подход столкнулся со сложностями вычислительного характера, что даже на современных компьютерах просчитать все комбинации невозможно, а можно лишь искать некоторое приближение методом Монте-Карло, но и это оказалось затруднительно в реальном времени. Пока что работа над дальнейшим развитием алгоритма остановлена, но может быть я когда-нибудь вернусь к этому. А тему почитайте, там интереснее, чем во многих других исследованиях «Морского боя», в том числе тех, что были уже на Хабре, или у Перельмана.
К сожалению, мой «всеобъемлющий» подход столкнулся со сложностями вычислительного характера, что даже на современных компьютерах просчитать все комбинации невозможно, а можно лишь искать некоторое приближение методом Монте-Карло, но и это оказалось затруднительно в реальном времени. Пока что работа над дальнейшим развитием алгоритма остановлена, но может быть я когда-нибудь вернусь к этому. А тему почитайте, там интереснее, чем во многих других исследованиях «Морского боя», в том числе тех, что были уже на Хабре, или у Перельмана.
Меня уже третий пост мучает мысль об отсутствия необходимости добивать. В принципе для победы важнее не затопить больше клеток (например линкор), а обнаружить все корабли (например все катера). А ранив корабль, мы тем самым уменьшаем вероятность нахождения другого корабля рядом. Т.е. если линкор потоплен, а я ранил не катер, то вероятность нахождения в соседней клетке другого корабля равна нулю, через клетку чуть уже больше, но не 0.5. К около 0.5 она повысится только на достаточном удалении от места ранения. Я думаю это не такой редкий случай и он может резко изменить ход боя. Эх, написать бы пару AI, натравить бы их друг на друга и посмотреть статистику.
Идея для Russian AI Cup 2 :-)
Спасибо! Мысль интересная — надо попробовать.
Есть ситуации, когда добивать невыгодно. Пример здесь.
Спасибо! Постараюсь ознакомиться с Вашим исследованием. Добавил ссылку в статью.
Статья интересная, скриншоты красивые.
Я, конечно, не вы, но на вашем месте, был бы чуть более осторожным со словом «оптимальный».
<зануда>
Для того, чтобы доказать, что метод/алгоритм/и т.п. оптимальный, надо сначала определить показатель эффективности, общий для всех возможных алгоритмов (для данной задачи). А уже потом доказать, что рассматриваемый алгоритм обеспечивает минимальное/максимальное значение этого показателя эффективности ;-)
</зануда>
Я, конечно, не вы, но на вашем месте, был бы чуть более осторожным со словом «оптимальный».
<зануда>
Для того, чтобы доказать, что метод/алгоритм/и т.п. оптимальный, надо сначала определить показатель эффективности, общий для всех возможных алгоритмов (для данной задачи). А уже потом доказать, что рассматриваемый алгоритм обеспечивает минимальное/максимальное значение этого показателя эффективности ;-)
</зануда>
Неделя Морского Боя на Хабре!
habrahabr.ru/post/180995/
habrahabr.ru/post/95126/
habrahabr.ru/post/82221/
habrahabr.ru/post/180995/
habrahabr.ru/post/95126/
habrahabr.ru/post/82221/
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Алгоритм игры в «морской бой»: обстрел противника