Морской бой как задача распознавания

[Mrrl]

Выстрелы в a1, a3, в1, в3 гарантирует попадание, но не дает дополнительно информации о расположении кораблей.

В реальных правилах (по крайней мере, по которым мы играли) это не так. Там кроме ответа «попал — не попал» сообщается ещё «потоплен ли корабль, в который попали». Так что 4 выстрела по углам полностью определят конфигурацию, без единого промаха.

А «жадный» алгоритм, стреляющий в поле, вероятность заполнения которого близка к 1/2, не учитывает, что в клетку, гарантированно занятую кораблём, всё равно придётся стрелять. Он может быстрее распознать ситуацию, но потом ему придётся тратить время на все известные клетки. Похоже, что стрелять в клетку с наибольшей вероятностью заполнения было бы выгоднее — мы тратим в среднем 1-p хода, а получаем -p*log(p)-(1-p)*log(1-p) информации. Количество полученной информации на затраченное число ходов при p->1 стремится к бесконечности.

[ich76]

кроме ответа «попал — не попал» сообщается ещё «потоплен ли корабль, в который попали»

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

стрелять в клетку с наибольшей вероятностью заполнения было бы выгоднее

и здесь вы правы. Вечером поиграю с измененным алгоритмом и отпишусь, что получилось.

[Mrrl]

В общем, жадный алгоритм, которому сообщают «корабль уничтожен», справляется за не более 4 промахов и 2.04 промаха в среднем, а если не сообщают — то не более 8 промахов и 4.595 в среднем. Похуже оптимального, но ненамного.

[ich76]

Проверил, получил тот же результат. Дополнил пост. Спасибо :)