Ключевое слово
22 | 02 | 2020
Новости Библиотеки
Шахматы Онлайн
Welcome, Guest
Username: Password: Remember me

TOPIC: алгоритмические задачки

алгоритмические задачки 09 Фев 2020 11:50 #151

  • Andralex
  • Andralex's Avatar
  • OFFLINE
  • Сокольничий
  • Posts: 392
  • Thank you received: 8
  • Karma: 3
Но и случайность, и регулярность обхода должны постоянно сбиваться, поскольку при ранении корабля его всегда добивают.

Понятно. При попадании в корабль происходит переход на второстепенную подпрограмму SUB_DESTROY() добивания. Если корабль уничтожен, то при выходе из SUB_DESTROY() должен поменяться контекст, чтобы вызывающая функция была "в курсе".
И здесь тоже важно определить, в какую сторону добивать без промаха. Как это сделать, пока неизвестно.

Warning: Spoiler! [ Click to expand ]
...не мы первые, не мы последние...

алгоритмические задачки 09 Фев 2020 12:38 #152

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1058
  • Thank you received: 22
  • Karma: 3
Да, при добивании придется рассматривать множество случаев. Пожалуй, не буду заморачиваться. :(
Сам себе доктор наук

алгоритмические задачки 11 Фев 2020 07:03 #153

  • Andralex
  • Andralex's Avatar
  • OFFLINE
  • Сокольничий
  • Posts: 392
  • Thank you received: 8
  • Karma: 3
Есть некоторые стратегии выигрыша в "морском бое".
...не мы первые, не мы последние...

алгоритмические задачки 11 Фев 2020 07:29 #154

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1058
  • Thank you received: 22
  • Karma: 3
Andralex wrote:
Есть некоторые стратегии выигрыша в "морском бое".

Там все формулы непропечатаны, читать одно неудовольствие. ((
Сам себе доктор наук

алгоритмические задачки 12 Фев 2020 16:12 #155

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1058
  • Thank you received: 22
  • Karma: 3
Запрограммировал упрощенный алгоритм оценки случайных расстановок кораблей. Берем случайную расстановку и начинаем ее обстреливать тоже случайным образом. И как только корабль ранен, добиваем его без промахов - упрощение состоит в этом, поскольку промахи должны быть. В наилучшем, идеальном случае, чтобы уничтожить все корабли, нужно 20 выстрелов, а в наихудшем - 100 выстрелов.

Я рассмотрел 1 млн случайных расстановок, в среднем потребовалось 53 выстрела. Не будь сделанного упрощения, получилось бы несколько больше. В наилучшем случае потребовалось 22 выстрела, а в наихудшем - 87.
Сам себе доктор наук
Last Edit: 12 Фев 2020 16:14 by Sam Sebe.

алгоритмические задачки 13 Фев 2020 13:51 #156

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1058
  • Thank you received: 22
  • Karma: 3
Sam Sebe wrote:
Запрограммировал упрощенный алгоритм оценки случайных расстановок кораблей. Берем случайную расстановку и начинаем ее обстреливать тоже случайным образом. И как только корабль ранен, добиваем его без промахов - упрощение состоит в этом, поскольку промахи должны быть. В наилучшем, идеальном случае, чтобы уничтожить все корабли, нужно 20 выстрелов, а в наихудшем - 100 выстрелов.

Я рассмотрел 1 млн случайных расстановок, в среднем потребовалось 53 выстрела. Не будь сделанного упрощения, получилось бы несколько больше. В наилучшем случае потребовалось 22 выстрела, а в наихудшем - 87.

Убрал это упрощение. Зато программа усложнилась (анализатор пишет, что ее цикломатическую сложность 52 надо бы уменьшить до 26). Теперь все происходит хоть и случайно, но реалистично.

Снова рассмотрел 1 млн случайных расстановок. Теперь для уничтожения всех кораблей требуется от 37 до 92 выстрелов, в среднем 64. Заодно посчитал, сколько клеток остаются чистыми (без кораблей, зон вокруг и выстрелов): оказалось, что от 0 до 25, в среднем 3.

Если хотите, можете предложить какую-нибудь другую стратегию игры, а я попробую оценить ее вместо рассмотренной случайной.
Сам себе доктор наук

алгоритмические задачки 14 Фев 2020 06:17 #157

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1058
  • Thank you received: 22
  • Karma: 3
Вот, нашел распределение вероятности по типу корабля, уничтоженного 1-м, 2-м, ..., 10-м. Первая, априори очевидная строчка, говорящая о том, что 1-м скорее всего (30 + 30 = 60 % случаев) будет уничтожен крейсер или эсминец, свидетельствует, что программа работает верно. Последние же строчки, указывающие на то, что к концу игры вероятнее всего выживут только катера, в общем тоже ожидаемы - качественно, но вряд ли количественно. При чисто случайном обнаружении кораблей, разумеется.

probability_battle.png
Сам себе доктор наук

алгоритмические задачки 15 Фев 2020 06:27 #158

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1058
  • Thank you received: 22
  • Karma: 3
Напрашивается следующая полуслучайная стратегия игры в Морской бой. Раскрасим игровое поле в виде шахматной доски и будем стрелять по клеткам одного цвета, пока гарантированно не уничтожим все большие корабли, а потом - по оставшимся клеткам, если катера еще остались.

И снова рассмотрим 1 млн случайных расстановок кораблей. При чисто случайной стрельбе (см. выше) требовалось 37-92 выстрела, в среднем 64, а теперь требуется 37-86 выстрелов, в среднем 63. Небольшое, но улучшение есть. Вероятности тоже изменились.

battle_37-63-86_0-3-24.png


Вместо рассмотренных случайных расстановок я рассмотрел также 1 млн расстановок не совсем случайных, тоже упомянутых выше: большие корабле прижимаются к краям игрового поля и/или друг к другу, а катера размещаются равномерно в оставшихся клетках. Такие расстановки действительно оказалось поразить труднее. Потребовалось 40-89 выстрелов, в среднем 67. Странно, но вероятности почему-то вышли те же самые, надо будет перепроверить.

battle_40-67-89_0-4-28.png
Сам себе доктор наук
Last Edit: 15 Фев 2020 06:32 by Sam Sebe.

алгоритмические задачки 15 Фев 2020 15:39 #159

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1058
  • Thank you received: 22
  • Karma: 3
Насчет вероятностей вроде все верно, практически одно и то же. Подсчитал еще, сколько выстрелов нужно, чтобы уничтожить все большие корабли: 22-75, в среднем 51 (в случае 63 выстрелов) или 52 (в случае 67 выстрелов).
Сам себе доктор наук
Last Edit: 15 Фев 2020 15:41 by Sam Sebe.

алгоритмические задачки 17 Фев 2020 07:10 #160

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1058
  • Thank you received: 22
  • Karma: 3
Выше я раскрасил игровое поле в шахматном порядке, но не сказал, с какого цвета начинать обстрел. На самом деле я выбирал его наугад индивидуально для каждой расстановки кораблей. А теперь усовершенствовал идею и для статистики обстреливаю каждую расстановку дважды, так и так.

Я рассматривал 1 млн расстановок. Достаточно этого статистически или нет? Отдельную расстановку можно описать последовательностью, в которой предложенная стратегия уничтожает корабли, а теперь даже двумя последовательностями. Одни последовательности встречаются чаще, другие реже: например, катера чаще уничтожаются последними. Сколько их, этих последовательностей может быть всего? Очевидно,

C(10, 4)*C(6, 3)*C(3, 2)*C(1, 1) = 12 600 штук (4 катера, 3 эсминца, 2 крейсера, 1 линкор).

Так вот, 1 млн расстановок - это вроде как маловато, поскольку не все указанные последовательности встречаются. (Даже при двух последовательностях на расстановку мне встретилось не 12 600, а только 12 386 штук. В качестве хеш-кода я использовал число, составленное из номеров - от 0 до 9 - катеров в получаемой последовательности, чаще всего это 6789.) А сколько не маловато? Я пока не знаю.
Сам себе доктор наук
Last Edit: 17 Фев 2020 07:11 by Sam Sebe.

алгоритмические задачки 17 Фев 2020 10:21 #161

  • Andralex
  • Andralex's Avatar
  • OFFLINE
  • Сокольничий
  • Posts: 392
  • Thank you received: 8
  • Karma: 3
Если повороты и зеркальные отражения не учитываются, то можно говорить об уникальных расстановках.
Одна расстановка имеет 2 зеркальных отражения и 4 поворота. Итого 2*4=8.
...не мы первые, не мы последние...

алгоритмические задачки 17 Фев 2020 10:30 #162

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1058
  • Thank you received: 22
  • Karma: 3
Sam Sebe wrote:
Так вот, 1 млн расстановок - это вроде как маловато, поскольку не все указанные последовательности встречаются. (Даже при двух последовательностях на расстановку мне встретилось не 12 600, а только 12 386 штук. В качестве хеш-кода я использовал число, составленное из номеров - от 0 до 9 - катеров в получаемой последовательности, чаще всего это 6789.) А сколько не маловато? Я пока не знаю.

Рассмотрел 5 млн расстановок, или 10 млн последовательностей, различных среди последних оказалось 12 599 штук, т.е. не оказалось всего одной, какой-то типа 1*1***11**, где 1 обозначает катер.
Сам себе доктор наук

алгоритмические задачки 18 Фев 2020 13:28 #163

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1058
  • Thank you received: 22
  • Karma: 3
Обнаружил неожиданную вещь. Казалось бы, вероятность, с которой корабль данного типа будет уничтожен первым, пропорциональна суммарной площади кораблей этого типа. Т.е. линкор и катер будут уничтожены первыми с одинаковой вероятностью (4 = 1 + 1 + 1 + 1), то же самое крейсер и эсминец (3 + 3 = 2 + 2 + 2). Но по факту это не совсем так. Оказалось, эта вероятность зависит от последовательности, в которой корабли расставляются на игровом поле, и эта зависимость не исчезает с увеличением числа рассматриваемых расстановок. Я объясняю это тем, что равномерно случайно на поле можно поставить только первый корабль, а последующие ставятся уже не совсем равномерно.

Поэтому я решил последовательность расстановки также сделать случайной. Правда, не часто, но изредка линкор или второй крейсер не удается вставить в поле - такие расстановки я пропускаю, в расчет не беру. Вот какие вероятности того, что корабль данного типа будет уничтожен 1-м, 2-м, ..., 10-м, получились для 1 000 000 расстановок (или 1 001 262 вместе с пропущенными).

battle_1001262.png
Сам себе доктор наук
Last Edit: 18 Фев 2020 13:33 by Sam Sebe.

алгоритмические задачки 18 Фев 2020 15:54 #164

  • Andralex
  • Andralex's Avatar
  • OFFLINE
  • Сокольничий
  • Posts: 392
  • Thank you received: 8
  • Karma: 3
Получается, что сначала лучше расставить мелкие катера, тогда случайность будет наибольшей. А линкор последним, - он слишком неповоротливый.
...не мы первые, не мы последние...

алгоритмические задачки 18 Фев 2020 16:12 #165

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1058
  • Thank you received: 22
  • Karma: 3
Ну наверное. Только разница вероятностей хоть и есть, но небольшая, в сотых. Опять же если начинать с катеров, то линкору или крейсеру может места не хватить, придется переделывать.
Сам себе доктор наук

алгоритмические задачки 19 Фев 2020 07:51 #166

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1058
  • Thank you received: 22
  • Karma: 3
Вот какая идея. Допустим, мы рассматриваем (измеряем, оцениваем и т.п.) некоторый объект с помощью некоего метода. Метод этот обладает определенной двойственностью, "бинокулярностью", так сказать. С одной стороны, он дает числовой результат 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* в этом случае, что скажете?
Сам себе доктор наук
Last Edit: 19 Фев 2020 07:56 by Sam Sebe.

алгоритмические задачки 19 Фев 2020 16:05 #167

  • инфолиократ
  • инфолиократ's Avatar
В нашем случае объектом является расстановка кораблей, а методом - стратегия ее обстрела.
И в любом ином случае понятия эти (объект и метод) имеют место быть, не только в играх. Так как на примере шахмат защищались и экономические диссертации, то данные коэффициенты очевидно универсальнополезными могут быть не только для "уничтожения уорабликов" или удовольствия ради... Поэтому, даже если меня неспрашивают, вставлю свой пятак я так:
Как можно было бы назвать k и k* в этом случае, что скажете?
С учетом того что в любой теории ключевое понятие может быть произвольным и на конечные результаты название термина не влияет, называю ТРИварианта (формально абстрактно, по автору, объективно по эффективности, субъективно - произвольно):
1. k и k* Это коэффициенты Ксс
2. По аналогии, есть же
коэффициент вариации
- коэффициент эффективности МЕТо = метода с объектом.
3. кнс= каждый назовет свое.
З павагай да неабыякавых

алгоритмические задачки 20 Фев 2020 14:37 #168

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1058
  • Thank you received: 22
  • Karma: 3
:idea:: объединить две предыдущие задачи!

Расстановку кораблей назовем связной, если существует змейка, их всех содержащая;
минимальную длину этих змеек назовем степенью связности. Сразу возникает несколько вопросов.

1. Существуют ли несвязные расстановки?
2. Каковы минимальная и максимальная степени связности?
3. Влияет ли степень связности на скорость уничтожения расстановки?
Сам себе доктор наук
Moderators: Grigoriy
Рейтинг@Mail.ru

Научно-шахматный клуб КвантоФорум