Но и случайность, и регулярность обхода должны постоянно сбиваться, поскольку при ранении корабля его всегда добивают.
Понятно. При попадании в корабль происходит переход на второстепенную подпрограмму SUB_DESTROY() добивания. Если корабль уничтожен, то при выходе из SUB_DESTROY() должен поменяться контекст, чтобы вызывающая функция была "в курсе".
И здесь тоже важно определить, в какую сторону добивать без промаха. Как это сделать, пока неизвестно.
Warning: Spoiler![ Click to expand ][ Click to hide ]
Запрограммировал упрощенный алгоритм оценки случайных расстановок кораблей. Берем случайную расстановку и начинаем ее обстреливать тоже случайным образом. И как только корабль ранен, добиваем его без промахов - упрощение состоит в этом, поскольку промахи должны быть. В наилучшем, идеальном случае, чтобы уничтожить все корабли, нужно 20 выстрелов, а в наихудшем - 100 выстрелов.
Я рассмотрел 1 млн случайных расстановок, в среднем потребовалось 53 выстрела. Не будь сделанного упрощения, получилось бы несколько больше. В наилучшем случае потребовалось 22 выстрела, а в наихудшем - 87.
Запрограммировал упрощенный алгоритм оценки случайных расстановок кораблей. Берем случайную расстановку и начинаем ее обстреливать тоже случайным образом. И как только корабль ранен, добиваем его без промахов - упрощение состоит в этом, поскольку промахи должны быть. В наилучшем, идеальном случае, чтобы уничтожить все корабли, нужно 20 выстрелов, а в наихудшем - 100 выстрелов.
Я рассмотрел 1 млн случайных расстановок, в среднем потребовалось 53 выстрела. Не будь сделанного упрощения, получилось бы несколько больше. В наилучшем случае потребовалось 22 выстрела, а в наихудшем - 87.
Убрал это упрощение. Зато программа усложнилась (анализатор пишет, что ее цикломатическую сложность 52 надо бы уменьшить до 26). Теперь все происходит хоть и случайно, но реалистично.
Снова рассмотрел 1 млн случайных расстановок. Теперь для уничтожения всех кораблей требуется от 37 до 92 выстрелов, в среднем 64. Заодно посчитал, сколько клеток остаются чистыми (без кораблей, зон вокруг и выстрелов): оказалось, что от 0 до 25, в среднем 3.
Если хотите, можете предложить какую-нибудь другую стратегию игры, а я попробую оценить ее вместо рассмотренной случайной.
Вот, нашел распределение вероятности по типу корабля, уничтоженного 1-м, 2-м, ..., 10-м. Первая, априори очевидная строчка, говорящая о том, что 1-м скорее всего (30 + 30 = 60 % случаев) будет уничтожен крейсер или эсминец, свидетельствует, что программа работает верно. Последние же строчки, указывающие на то, что к концу игры вероятнее всего выживут только катера, в общем тоже ожидаемы - качественно, но вряд ли количественно. При чисто случайном обнаружении кораблей, разумеется.
Напрашивается следующая полуслучайная стратегия игры в Морской бой. Раскрасим игровое поле в виде шахматной доски и будем стрелять по клеткам одного цвета, пока гарантированно не уничтожим все большие корабли, а потом - по оставшимся клеткам, если катера еще остались.
И снова рассмотрим 1 млн случайных расстановок кораблей. При чисто случайной стрельбе (см. выше) требовалось 37-92 выстрела, в среднем 64, а теперь требуется 37-86 выстрелов, в среднем 63. Небольшое, но улучшение есть. Вероятности тоже изменились.
Вместо рассмотренных случайных расстановок я рассмотрел также 1 млн расстановок не совсем случайных, тоже упомянутых выше: большие корабле прижимаются к краям игрового поля и/или друг к другу, а катера размещаются равномерно в оставшихся клетках. Такие расстановки действительно оказалось поразить труднее. Потребовалось 40-89 выстрелов, в среднем 67. Странно, но вероятности почему-то вышли те же самые, надо будет перепроверить.
Насчет вероятностей вроде все верно, практически одно и то же. Подсчитал еще, сколько выстрелов нужно, чтобы уничтожить все большие корабли: 22-75, в среднем 51 (в случае 63 выстрелов) или 52 (в случае 67 выстрелов).
Выше я раскрасил игровое поле в шахматном порядке, но не сказал, с какого цвета начинать обстрел. На самом деле я выбирал его наугад индивидуально для каждой расстановки кораблей. А теперь усовершенствовал идею и для статистики обстреливаю каждую расстановку дважды, так и так.
Я рассматривал 1 млн расстановок. Достаточно этого статистически или нет? Отдельную расстановку можно описать последовательностью, в которой предложенная стратегия уничтожает корабли, а теперь даже двумя последовательностями. Одни последовательности встречаются чаще, другие реже: например, катера чаще уничтожаются последними. Сколько их, этих последовательностей может быть всего? Очевидно,
Так вот, 1 млн расстановок - это вроде как маловато, поскольку не все указанные последовательности встречаются. (Даже при двух последовательностях на расстановку мне встретилось не 12 600, а только 12 386 штук. В качестве хеш-кода я использовал число, составленное из номеров - от 0 до 9 - катеров в получаемой последовательности, чаще всего это 6789.) А сколько не маловато? Я пока не знаю.
Если повороты и зеркальные отражения не учитываются, то можно говорить об уникальных расстановках.
Одна расстановка имеет 2 зеркальных отражения и 4 поворота. Итого 2*4=8.
Так вот, 1 млн расстановок - это вроде как маловато, поскольку не все указанные последовательности встречаются. (Даже при двух последовательностях на расстановку мне встретилось не 12 600, а только 12 386 штук. В качестве хеш-кода я использовал число, составленное из номеров - от 0 до 9 - катеров в получаемой последовательности, чаще всего это 6789.) А сколько не маловато? Я пока не знаю.
Рассмотрел 5 млн расстановок, или 10 млн последовательностей, различных среди последних оказалось 12 599 штук, т.е. не оказалось всего одной, какой-то типа 1*1***11**, где 1 обозначает катер.
Обнаружил неожиданную вещь. Казалось бы, вероятность, с которой корабль данного типа будет уничтожен первым, пропорциональна суммарной площади кораблей этого типа. Т.е. линкор и катер будут уничтожены первыми с одинаковой вероятностью (4 = 1 + 1 + 1 + 1), то же самое крейсер и эсминец (3 + 3 = 2 + 2 + 2). Но по факту это не совсем так. Оказалось, эта вероятность зависит от последовательности, в которой корабли расставляются на игровом поле, и эта зависимость не исчезает с увеличением числа рассматриваемых расстановок. Я объясняю это тем, что равномерно случайно на поле можно поставить только первый корабль, а последующие ставятся уже не совсем равномерно.
Поэтому я решил последовательность расстановки также сделать случайной. Правда, не часто, но изредка линкор или второй крейсер не удается вставить в поле - такие расстановки я пропускаю, в расчет не беру. Вот какие вероятности того, что корабль данного типа будет уничтожен 1-м, 2-м, ..., 10-м, получились для 1 000 000 расстановок (или 1 001 262 вместе с пропущенными).
Ну наверное. Только разница вероятностей хоть и есть, но небольшая, в сотых. Опять же если начинать с катеров, то линкору или крейсеру может места не хватить, придется переделывать.
Вот какая идея. Допустим, мы рассматриваем (измеряем, оцениваем и т.п.) некоторый объект с помощью некоего метода. Метод этот обладает определенной двойственностью, "бинокулярностью", так сказать. С одной стороны, он дает числовой результат x, а с другой - число y, пусть y > x > 0. Данную бинокулярность можно определить как
k = (y - x)/(y + x).
Параллельно объект характеризуется сопряженной величиной, не знаю, как ее назвать образно,
k* = x/y.
В нашем случае объектом является расстановка кораблей, а методом - стратегия ее обстрела. Если начинать обстрел с клеток одного цвета, удастся уничтожить все корабли за x > 20 выстрелов, а если начнем с другого, потребуется y < 100 выстрелов. Я подсчитал на 1 млн расстановок, что в 5% случаев k = 0, но бывает и k > 30%, а в средневзвешенном k = 5%.
Как можно было бы назвать k и k* в этом случае, что скажете?
В нашем случае объектом является расстановка кораблей, а методом - стратегия ее обстрела.
И в любом ином случае понятия эти (объект и метод) имеют место быть, не только в играх. Так как на примере шахмат защищались и экономические диссертации, то данные коэффициенты очевидно универсальнополезными могут быть не только для "уничтожения уорабликов" или удовольствия ради... Поэтому, даже если меня неспрашивают, вставлю свой пятак я так:
Как можно было бы назвать k и k* в этом случае, что скажете?
С учетом того что в любой теории ключевое понятие может быть произвольным и на конечные результаты название термина не влияет, называю ТРИварианта (формально абстрактно, по автору, объективно по эффективности, субъективно - произвольно):
1. k и k* Это коэффициенты Ксс
2. По аналогии, есть же
коэффициент вариации
- коэффициент эффективности МЕТо = метода с объектом.
3. кнс= каждый назовет свое.
З павагай да неабыякавых
Расстановку кораблей назовем связной, если существует змейка, их всех содержащая;
минимальную длину этих змеек назовем степенью связности. Сразу возникает несколько вопросов.
1. Существуют ли несвязные расстановки?
2. Каковы минимальная и максимальная степени связности?
3. Влияет ли степень связности на скорость уничтожения расстановки?
С 23 февраля! С праздником (в той теме есть картинка с одним фасадом +2 за).
С учетом предыдущего (см. выше)
Я объясняю это тем, что равномерно случайно на поле можно поставить только первый корабль, а последующие ставятся уже не совсем равномерно.
Поэтому я решил последовательность расстановки также сделать случайной.
отмечу:
1. Расстановку кораблей назовем связной, если существует змейка, + "случайная" расстановка подсказывают ответ на 1?
2. Здорово было бы,чтобы k и k* в этом случае поучавствовали в ответе на 2?
3. 3? сугубо "криптографический": определив конечное число для пп 1 и2, найдя "ключ" можно повлиять на "скорость уничтожения расстановки". Таковы мои инфолиопримитивнослучайные предположения сегодня после вчерашнего.
З павагай да неабыякавых
1. Существуют ли несвязные расстановки?
2. Каковы минимальная и максимальная степени связности?
1. Проверил 100 тысяч случайных расстановок. Все оказались связными.
2. Очевидно, минимум = 20 + 9 = 29. С максимумом сложнее. Проверил 10 тысяч расстановок (~ 10 минут компьютерного времени). Для каждой расстановки змейка минимальной длины искалась до тех пор, пока очередная найденная змейка не совпадала по длине с одной из найденных ранее. Конечно, логичнее было бы, чтобы повторилась не какая-то длина, а минимальная среди найденных ранее, но этого слишком долго жать. Вот какое распределение получилось - со средней степенью связности e = 44 и со средним числом n = 4 найденных змеек разной длины на одну расстановку.
P.S. Забыл пояснить, что ради минимальности все найденные змейки обрезаются до корабля со стороны старта и кораблем же финишируют. Кстати, по факту это не то же самое, что при поиске (случайном) всегда стартовать с корабля.
Решил посмотреть, кораблем какой длины l змейка начинается (после обрезания) и какой кончается. Рассмотрел 40 тысяч змеек (39 555, точнее), в среднем по 4 змейки (разной длины) на 10 тысяч расстановок кораблей; именно про них говорится в предыдущем посте. Соответствующие распределения a и b, в процентах, получились следующие.
По идее змейка минимальной длины, содержащая все корабли, может начинаться и кончаться катером, эсминцем, крейсером и линкором (длиной l = 1, 2, 3 и 4). Всего 15 возможностей (16-я отсутствует, поскольку линкор только один).
Возникает смутная мысль об аналогии с игрой в пятнашки в коробочке 4х4, где требуется упорядочить исходную случайную комбинаций из 15 пронумерованных подвижных клеток-костяшек за (желательно) минимальное число движений. Тогда разрешимость этой задачи - исследованной вдоль и поперек - аналогична (?) связности расстановки кораблей. С известной оговоркой задача всегда разрешима -
Вики wrote:
Если допустить поворот коробки на 90 градусов, при котором изображения цифр окажутся лежащими на боку, то можно перевести неразрешимые комбинации в разрешимые (и наоборот). Таким образом, если вместо цифр на костяшки нанести точки и не фиксировать положение коробки, то неразрешимых комбинаций вообще не окажется.
Вот, объединил две таблички из предыдущего поста в одну. Строки - это корабль в начале змейки, а столбцы - в конце.
Выше получилось, что в среднем длина змейки, содержащей все корабли, равна 44. Это значение можно немного уменьшить. Как только установлена последовательность кораблей в змейке, нетрудно вычислить манхеттенское расстояние между ними и тем самым оценить снизу минимальную длину змеек, содержащих корабли в данной последовательности, чтобы по факту уменьшить 44 от силы до 41.
В принципе задачу нахождения змейки, содержащей все корабли и имеющей минимальную длину, можно решать как задачу коммивояжера. Десять кораблей не так уж и много. Никто не хочет попробовать?
В принципе задачу нахождения змейки, содержащей все корабли и имеющей минимальную длину, можно решать как задачу коммивояжера. Десять кораблей не так уж и много. Никто не хочет попробовать?
В принципе задачу нахождения змейки, содержащей все корабли и имеющей минимальную длину, можно решать как задачу коммивояжера. Десять кораблей не так уж и много. Никто не хочет попробовать?
Сложновато будет, я пас.
Я было попробовал полным перебором, хотя это и довольно медленно, но тут же выяснилось, что не всякую заданную последовательность кораблей (именно эти последовательности для данной расстановки кораблей и перебирались) можно пройти в виде змейки, и как эту непроходимость быстро определить, непонятно.
Зато возникла новая идея.
Раньше я брал произвольную расстановку кораблей и старался найти змейку минимальной длины, проходящую через них. Но ведь можно и наоборот. Можно взять змейку максимальной длины и попытаться найти все расстановки кораблей, помещающиеся в нее, - с целью выяснить, всегда ли они существуют, эти расстановки, и сколько их в среднем. А главное, змейку (или змейки) максимальной в этом смысле "емкости" можно было бы рекомендовать (?!) в качестве стратегии расстановки кораблей.
Но для этого нужно сначала найти все змейки максимальной длины. Эта задача уже решалась выше, но там игровое поле было меньше - не 10х10, а 8х8, и максимальная длина змейки была известна - 42 клетки. А здесь пока ничего не известно.
Идея предыдущего поста неплохая, но труднореализуемая. Из тех змеек, что я нашел, максимальные имеют длину 63 клетки. И число помещающихся в них расстановок кораблей так велико, что не поддается счету. Поэтому пришлось взять змейки покороче и ограничить их количество. Я взял 10 первых попавшихся змеек длиной по 35 клеток. В качестве примера изображена последняя змейка, самая емкая из 10 (стартующая в середине игрового поля и финиширующая в углу), в которую помещается 46 592 расстановки кораблей: линкор (4 клетки), 2 крейсера (по 3 клетки), 3 эсминца (по 2 клетки) и 4 катера (одноклеточных); крестики - это клетки змейки, остальные клетки пустые; корабли не должны касаться друг друга. Вот какая статистика получилась, причем 2 змейки оказались нулевой емкости.
Я не придумал ничего лучше, чем запрограммировать 10 вложенных циклов, чтобы перебрать все возможные взаимные положения 10 кораблей, одновременно отбрасывая повторяющиеся расстановки, повторяющиеся из-за того, что корабли одного типа неразличимы, так что найденные расстановки нужно еще и запоминать.
Я не придумал ничего лучше, чем запрограммировать 10 вложенных циклов, чтобы перебрать все возможные взаимные положения 10 кораблей, одновременно отбрасывая повторяющиеся расстановки, повторяющиеся из-за того, что корабли одного типа неразличимы, так что найденные расстановки нужно еще и запоминать.
Усовершенствовал программу, чтобы расстановки не повторялись, и теперь их не нужно запоминать и сравнивать, коль скоро нам надо просто их сосчитать. Программа заработала на два порядка быстрее, и предыдущая статистика получилась за 10 секунд вместо 22 минут, так что теперь можно брать змейки и подлиннее. Вот, например, статистика для змеек в 40 клеток за менее чем 5 минут. Приведена также одна из 10 змеек, попавшаяся последней.
: объединить две предыдущие задачи!
