Бот для игры в "Морской бой": история, теория, практика

[GriV]

Понятно. Нет, стрельба в "Морской бой" с точки зрения поиска по множеству размещения кораблей противника, не является аналогичной методу сетки. Даже неоптимальная стрельба наобум сходится экспоненциально, ведь прикинь порядок величины количества всех возможных размещений флота - 1E20!

В общем то количество состояний никакого отношения к методике решения задачи не имеет.
Вот метод сетки - http://ru.wikipedia.org/wiki/Метод_перебора

то для полного перебора потребуется 1E11 секунд

Здесь, возможно, можно делать первые выстрелы таким способом, чтобы они значительно сокращали подмножество оставшихся вариантов (тот самый дебют), а потом уже считать.

И ещё, можно хранить уже рассчитанные матрицы для первых 2-3 выстрелов (матрицы вероятности расположения). Можно сэкономить около 3e11 секунд :-)

Иначе, как экспонентой, такое множество нельзя победить за человеческое время

Оно побеждается правилами игры - расположением кораблей, их ориентацией и т.д.. При потоплении 4хпалубника сразу куча клеток улетает (мин 10, макс 18, коэффициент освобождения - min 250%, max 450%), а для однопалубника коэффициант освобождения даже выше (min 400% max 900%) :-) А методика поиска просто сокращает количество выстрелов до победы. При самом неудачном расположении кораблей и неудачном расположении промахов, это будет чуть меньше количество выстрелов, т.к. каждый корабль закрывает собой минимум ещё такое же количество клеток, сколько он сам занимает, т.е. 4+2*3+3*2+4*1 = 20, т.е. максимальное количество выстрелов будет 80.

А всего для вражеского флота в полном составе будет рассмотрено N = N1*N2*N3*N4 ~= 2E+21 комбинаций

А то, что установка предыдущего корабля резко сокращает количество вариантом для оставшихся - учитывается?

После установки 1нопалубников (если начинать с них), будет занято минимум 16 клеток, максимум - 36 клеток. Установка двухпалубников займёт минимум 18 максимум 36 клеток, установка трёхпалубников - мин 16, макс 30 клеток, 4хпалубный - мин 10, макс 18 клеток.

Если начинать сверху вниз (от больших кораблей к малым, что в общем то логичнее), то установка 4хпалубника (с вариантами = N4 = 140) cокращает для оставшихся кораблей число свободных клеток минимум на 10. Тогда для оставшихся трёхпалубников остаётся максимум 90 клеток.

Движок форума меня подвёл уже два раза :-( По привычке нажимаю "ответить" из окна правки сообщения... ну и текст сообщения теряется, хотя полдня набирал и считал.

Результаты расчётов получились такие:

N4 = 140
N43 = 17440 (установка 1го 4 и 1го 3хпалубного)
N433 = 1958320
N4332 = 228234080
N43322 = 23919593920
N433222 = 2,22688E+12
N4332221 = 1,1295E+14
N43322211 = 5,2956E+15
N433222111 = 2,28058E+17
N4332221111 = 8,95513E+18
У меня получилось около 280 лет на 1 млрд операций пересчёта в секунду, так что хоть и изменились сильно порядки (как у тебя 3000 лет получилось???), но задача пока далека от обозримого пересчёта.
Учёт заслоняемости кораблей может немного (я думаю около 20%) снизить количество вариантов, но там всё равно больше 2х веков.

Сама задача легко распараллеливается на суперкомпьютере.

Эй, есть тут у кого суперкомпьютер? :-) Нам для морского боя не хватает ;-)