Оглавление:
Часть 1: Введение.
Часть 2: Генерация флота, число позиций.
Часть 3: Случайное расположение/обстрел и по системе.
Часть 4: Системы размещения флота.
Часть 5: Выводы
Полная статья PDF: Копия 5 частей здесь, только немного проще с отображением формул.
Предыдущая часть
10x10, полный флот расположение/обстрел по системе
Если вы дочитали до этого раздела, то должны уже понять, что никакое «фигурное», симметричное или др. «красивое» расположение флота не влияет на результат игры, потому что есть только один значимый критерий позиции: кол-во клеток, не занятых кораблями. Чем у вас больше больших кораблей и чем равномерней они размещены, тем хуже ваша позиция. Иначе говоря, расположение кораблей различается только степенью близости друг другу. Будем уплотнять. См. рис. 9.
Уплотнение в центре мало влияет на кол-во ходов; более того, оно ухудшает вашу позицию в игре против человека, т.к. скученные корабли проще расстрелять. Корабли, прижатые к бортам/углам, тоже просто найти, но зато такое размещение дает больше свободных клеток для оставшихся. Далее мы рассчитаем, сколько стоит жертвовать кораблей ради такой свободы.
В табл. 2 видим зависимость кол-ва ходов от кол-ва уплотненных кораблей (полный флот) для разных систем обстрела. Зависимость нелинейная, потому что кораблям мало места у бортов, появляются «краевые эффекты». Кол-во ходов не совпадает с расчетами в пред. разделе, потому что в данном случае размещения неслучайны: например, при 0 уплотненных кораблей мы избегаем позиций, где хотя бы один корабль прижат к борту, при 1 корабле 5 кораблей должны быть не прижаты к бортам и т.д.
Стратегия «центр» оказалась даже хуже случайного обстрела, поскольку не уделяет внимание углам/бортам. При этом «сетки» хорошо выступают как при случайном, так и любом др. схеме размещения. Поэтому, повторим, если вы не знаете, какие размещения предпочитает противник, «сетки» будут лучшим выбором для обстрела.
Плотно расположить все 6 «многопалубных» кораблей выгодно на ~20%.
«Сетка-3» в большинстве вариантов выгодней «сетки-4», потому что корабли при упаковке неизбежно жмутся к углам. Когда упакованы все корабли, разница исчезает, потому что любая система обстрела с приоритетом углы/борты быстро уничтожает такую группировку (кроме «центр»).
Следующий раздел можно не читать, но мы все же продолжим, потому что тактика, описанная в нем, очень популярна. Фактически, мы разбираем то же уплотнения, но иначе, как ее излагал Я.Перельман:
«Виктор свои многоклеточные корабли располагает компактно в одном из углов поля, «вжимая», как только возможно. Одноклеточные корабли равномерно распределяет по оставшейся части поля. Петр [противник] быстро уничтожит все корабли Виктора, кроме одноклеточных. После этого, чтобы найти остальные, ему придется исследовать большую площадь, поскольку ореолы многоклеточных кораблей Виктора перекрываются, плюс львиная доля ореолов кораблей, прижатых к кромке поля, оказывается за пределами поля. По мере того, как игроки топят корабли друг друга, не исследованная площадь поля Петра [войды] уменьшается быстрее, чем у Виктора. Благодаря этому Виктор быстрее поразит корабли противника» (в сокращении).
10x6, 1п
Рассмотрим предельный вариант уплотнения. Эта Тактика Компактного Расположения Кораблей (ТКРК) настолько популярна, что требует отдельного исследования. Три варианта (с точностью до поворота 10) на рис. 10 дают 60 свободных клеток для размещения 4-х 1п. Считается, что даже если ваш противник первым же ходом разнесет зону «А», ему придется искать 4 оставшихся 1п в зоне «Б» (алгоритм «Перельмана»). Фактически, эта другая игра: поиск 1п на поле 10x 6. Испытания показали, что все варианты дают одинаковое распределение, поэтому использовался (1) для упрощения программирования.
Для начала посчитаем, сколько нужно ходов для поражения нескольких 1п на поле 10x 6. См. рис. 11. Для одного корабля ~30,5 ходов, как и μ. Заметим, что для поражения 4 кораблей нужно меньше ходов, чем для 3-х. А для поиска 6 — столько же, что и для одного. Впрочем, результаты более 7 кораблей неточны, потому что разместить столько кораблей на небольшом поле бессистемно невозможно.
Но нас больше интересует 4 корабля. Распределение для этого случая на рис. 12. Для него необходимо ~35,6 ходов.
Можно ли улучшить этот результат? Расположим 4 корабля в углу (90,92,70,72) как на рис. 13. Случайный компьютерный алгоритм: 38,2 ходов. Другие подобные варианты с 44 свободными клетками дают примерно тоже самое. Выигрыш ~2 хода. Против компьютерного случайного алгоритма смысл есть, против человека наоборот: после обстрела углов поля 10x 6 он выиграет сразу или (если 4-й корабль вы расположите случайно) получит существенное преимущество ~ 30% ходов. Потому что на оставшихся 48 клетках ему придется найти только 1 корабль, а для этого нужно μ=24,5 ходов. Так же малоперспективны попытки расположить 1 или 2-х корабля по углам, остальные 1–2 случайно (против человека).
Уничтожить «упаковку» легко, только если она постоянна, тогда вы тратите на это всего один ход. Если вы ее меняете, противнику потребуется доп. ~2,5 хода, чтобы распознать, какой из 10 возможных вариантов перед ним. 35,6+2,5=38,1, это хуже на 0,4 хода против «сетки». Т.е. если противник меняет варианты ТКРК, нет смысла тратить ходы в надежде ее распознать и быстро уничтожить; проще использовать «сетку-3», она и в этом случае сработает не хуже.
Итого: попытка улучшить обстрел за счет раннего разгрома «упаковки» не удалась. Считаем, что вариант с ТКРК требует все те же ~37,7 ходов для победы.