Оглавление:
Часть 1: Введение.
Часть 2: Генерация флота, число позиций.
Часть 3: Случайное расположение/обстрел и по системе.
Часть 4: Системы размещения флота.
Часть 5: Выводы
Полная статья PDF: Копия 5 частей здесь, только проще с отображением формул.
Предыдущая часть
10x10, полный флот, случайное расположение/обстрел
Поле сгенерировали, начинаем игру. Обстрел случайный: то есть в любую свободную клетку. Распределение на рис. 2, для наглядности вероятности менее 0,01% обрезаны.
Получается ~31,9 ходов. Или, точнее, 31,8965±0,0001 при надежности оценки 0.99 (в дальнейшем округляем до 2 знаков после запятой). Будем считать нашу выборку представительной, ведь распределение близко к нормальному и число ходов сходится к средней величине с хорошей точностью. Однако теоретической оценки μ нет (иначе зачем нам модель?)
Так же остается открытым вопрос, генерирует ли программа репрезентативную выборку.
Замечание. Если ваш противник выиграл быстрее, чем за 19 ходов, похоже он жульничает (например, подсмотрел вашу карту), потому что вероятность этого меньше 0,01%. Если вы потратили более 50 ходов для выигрыша, вероятность этого тоже менее 0,01% — немалый шанс, что какой-то корабль ваш противник не поставил.
10x 10, полный флот, случайное расположение, обстрел по системе
Если бы флот состоял только из 1п, не существовало бы никакой системы обстрела. Иначе логично топить корабли в последовательности 4п -> 3п -> 2п. Чем больше корабль, тем больше у него мертвая зона, что сужает варианты размещения оставшихся. Проверим это и др. тактики.
«Сетка-4». См. рис. 3. Порядок выбора клеток для стрельбы неважен, если корабли расположены случайно (проверено на выборках 109 позиций). Для поимки 4п требуется ~13,9 ходов (против ~21,3 при случайном переборе).
«Сетка-3». Система на рис. 4 одновременно ловит 4п и 3п. Справа более эффективна по кол-ву ходов (33), чем слева (34), но не обстреливаются углы. А это, как мы увидим далее, важно. Кстати, в выбранных системе отсчета сетка слева легко запоминается: все координаты кратны трем.
Цвет указывает на приоритетность обстрела (т.е. куда стрелять раньше, куда позже): красный -> желтый -> зеленый -> синий, т.е. от периферии к центру. Такой порядок имеет смысл, если противник использует «уплотнение» кораблей , которые будут неизбежно жаться к бортам и углам, см. рис. 9 . Иначе никакой др. приоритет (например, центр) не влияет на кол-во ходов. А раз не влияет, то удобнее все-таки приоритет использовать: в случае «уплотнения» мы получим преимущество, а при случайном размещении кораблей противника ничего не теряем.
Заметим, что человеку не свойственно расставлять корабли случайно; если вы наблюдательны, сможете уловить паттерн и использовать. Поэтому советы в обзорах литературы стрелять в углы или по центру не лишены смысла. Но, если вы не знаете тактику противника, лучше использовать обстрел по сетке.
И еще замечание, касающееся игры с компьютером. Можно реализовать стратегию, которая будет запоминать все сыгранные с вами игры и искать паттерны. Они обязательно проявятся, если только вы не пользуетесь генератором случайных чисел. И тогда компьютер получит устойчивое преимущество, по оценкам, до 10%.
Кстати, если ставить корабли только вертикально или только горизонтально, есть выигрыш в несколько ходов. Но как только противник начинает искать/добивать только горизонтально/вертикально, эффект будет противоположный. Против компьютерного противника можно использовать.
«Центр». Стрельба ведется согласно рассчитанной плотности вероятностей нахождения кораблей согласно рис. 5. После попадания плотность не пересчитывается.
«Оптимизация». Каждый выстрел делается в место наиболее вероятного расположения оставшихся кораблей. Фактически предыдущая стратегия, но пересчитывающая плотности после каждого попадания. Это лучшая, «абсолютная» стратегия, потому что учитывает все факторы. Проще понять эту систему из рис. 6, где осталось поймать 2п. Корабль может размещаться 5 способами. При этом в клетку 00, 01, 10, 11 он попадет 2 раза, в 12 — 1, в 11 — 3 раза. Значит, стреляем 11. Однако, если осталось два корабля: 2п и 1п, то стрелять надо в 00 или 01, потому что др. вариантов размещения нет.
~10^15 возможных размещений кораблей на десктопе не рассчитать, поэтому сначала использовалась «сетка-4» для нахождения 4п, затем «оптимизация». Главное, почему эта тактика не разрабатывалась глубоко: ей не может воспользоваться человек, поэтому в рамках нашего исследования бесполезна. Более подробно здесь . Разница между «оптимизацией» и «центром» получилась ~1 ход. Однако, повторим, данная система обстрела отрабатывалась не полностью.
В таблице 1 сведены все упомянутые тактики обстрела для полного флота при случайном расположении кораблей. Лидер не сетки, а стрельба по центру (оптимизацию невозможно применить человеку). Но эту тактику трудно запомнить, любая ошибка сводит ее преимущество на нет, и она сильно проигрывает при неслучайных размещениях, к которым склонен человек. Особенно это заметно при уплотнении кораблей из-за углов/бортов, см. дальше. Поэтому в дальнейшем используем «сетку-3». Немного хуже, чем «сетка-4», но зато обстреливаются углы, это далее проявится.
После отлова 4п продолжаем «сетку-3» до поражения обоих 3п. Например, на рис. 7 (кресты – «потопленные» корабли, точки — куда уже стреляли, серая заливка — мертвая зона, розовая — войд) 3п топится макс. за 10 ходов (вопросительные знаки). Координата 91 не соответствует сетке, но для нахождения 2п она более логична, чем 92. Отсюда вывод: после поражения 4п не стоит слепо следовать сетке, могут более оптимальные стратегии.
После отлова 3п ловим 2п. Для небольших войдов найти наименьшее кол-во выстрелов несложно. К примеру, на рис. 8. нужно максимум 8 выстрелов.
~30,9 ходов — это «сетка-3» плюс простой алгоритм отлова 2п. Есть ощущение, что этот алгоритм можно улучшить, получив менее 30 ходов. Но за счет усложнения расчета, так что им не сможет воспользоваться человек.
Для поиска 1п системы не существует, только случайный обстрел.
Другие тактики не описаны. Если у вас есть какие-нибудь соображения, пишите, прогоним через программу. Но только такую, которую может реализовать человек. Для компьютера лучше «оптимизации» быть не может.
Замечание. Проблема всех систем обстрела в том, что важной частью версии игры, принятой в РФ, является поиск 1п, а для него не существует алгоритма лучшего, чем случайная стрельба. В результате системы показывают великолепный результат в начале игры, когда вычисляются большие корабли, а затем их эффективность становится не лучше случайного обстрела. И чем быстрее выбиваются корабли, тем менее они эффективны. Поэтому разница между оптимизациями обстрела не так велика. В пределе (для ТКРК) она вообще исчезает, а эта тактика, как мы увидит позже, самая эффективная. Поэтому, если вы видите в некоторых исследованиях оптимизацию «по Нэшу», помните, что она правильная (хотя и реализуется только для компьютера), но работает только для кораблей более одной клетки. И никто не испытывал ее (насколько известно) для полной игры вследствие вычислительных трудностей.
Вариант обсчитать полное дерево игры заранее столкнется с другой трудностью: объемом, который по оценкам займет петабайты. Что опять реализуемо только для компьютерного алгоритма.