Морской бой. Стратегия через теорию вероятностей

[EUgeneUS]

12d3
У меня так же.
Удивительный момент: центр тоже довольно таки выделенная точка. Вероятность, что там есть корабль равна $\frac{1}{3}$.
Но если рассмотреть отдельно стратегии:
а) бьем по серединам сторон, как нащупали корабль, добиваем
б) бьем сразу в центр, потом по серединам сторон, как нашли корабль - добиваем
то ожидаемое количество ходов окажется одинаковым.

[komand]

12d3 в сообщении #1510017 писал(а):

У меня получилось проанализировать все стратегии для доски 3 на 3. Оптимальная стратегия расстановки - равновероятно выбрать любую из 12 возможных позиций. Тогда кораблик убивается в среднем за 4.5 хода, первым выстрелом нужно пулять куда угодно, кроме углов.
Забавно, что для трехпалубного корабля тоже требуется 4.5 выстрела, и оптимальная расстановка такая же - равновероятно выбрать любую из возможных позиций.

Обсчет показал ($10^9$ попыток, точность на 4 знаке после запятой при P=0.999), что при случайном обстреле в среднем требуется 3.5 попытки. Если же пользоваться сеткой (см. ниже, точки - обстрел в любом порядке) , то обсчет показал 2.5 попытки. В теории столько же: мин. попыток 1, макс. попыток 4, в среднем $(1+4)/2=2.5$
Для трехпалубного корабля требуется не более 3 выстрелов, в среднем 2. Координаты сетки любая диагональ, например, 00,11,22
Да, не забывайте о "премиальном" выстреле: если вы попали в корабль, следующий выстрел вне очереди. То есть, к примеру, такая последовательность "мимо, ранил, ранил убил, мимо" - это не 4 выстрела, а всего 2. В реальной игре так и есть: если, к примеру, вы точно знаете расположение всех кораблей противника, то можете потопить его флот с единственного выстрела, не дав ему выстрелить в ответ. То есть мы с вами считаем одинаково, но я не добавляю "премиальные" попытки, а вы добавляете. Чаще всего играют с "премией", поэтому мой подсчет ближе к реальной игре.

[EUgeneUS]

komand в сообщении #1510034 писал(а):

В теории столько же: мин. попыток 1, макс. попыток 4, в среднем (1+4)/2=2.5

Интересно Вы считаете... В среднем $2.5$ хода - это чтобы попасть первый раз, то есть ранить. Дальше ещё убить надо.
Если призовой ход после попаданием за ход не считаем, то ещё в среднем 1 один ход. Итого $3.5$

[komand]

EUgeneUS в сообщении #1510037 писал(а):

komand в сообщении #1510034 писал(а):

В теории столько же: мин. попыток 1, макс. попыток 4, в среднем (1+4)/2=2.5

Интересно Вы считаете... В среднем $2.5$ хода - это чтобы попасть первый раз, то есть ранить. Дальше ещё убить надо.
Если призовой ход после попаданием за ход не считаем, то ещё в среднем 1 один ход. Итого $3.5$

Не забываем, что премиальный выстрел не учитывается. Так что все же 2,5, распределение для $10^7$ попыток простое: с первой по 4 попытку вероятность 0,25, с пятой 0. Это с добиванием и премиальным выстрелом.

[EUgeneUS]

komand в сообщении #1510041 писал(а):

не забываем,

Не забываем

komand в сообщении #1510041 писал(а):

что после каждого попадания сокращается кол-во клеток, куда может добиваться корабль.

В данном случае (бьем по серединам сторон поля, как попали - добиваем) не сокращается.

komand в сообщении #1510041 писал(а):

Так что все же 2.5, распределение для 10^7 попыток см. выше.

Вот расчет:

1. За четыре удара точно попадаем. В среднем $2.5$
2. Дальше добиваем. Где бы и когда бы не ранили, остается ровно три варианта на добитие. С учетом "призового удара", это $0, 1, 2$ хода. В среднем один ход.
3. $2.5 + 1 = 3.5$

[komand]

EUgeneUS в сообщении #1510047 писал(а):

1. За четыре удара точно попадаем. В среднем $2.5$
2. Дальше добиваем. Где бы и когда бы не ранили, остается ровно три варианта на добитие. С учетом "призового удара", это $0, 1, 2$ хода. В среднем один ход.
3. $2.5 + 1 = 3.5$

Да, где-то в компьютерном обсчете ошибка. Найду, напишу.

[EUgeneUS]

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

(Оффтоп)

0. Для простоты и определенности: соединение углами кораблей запрещено.
1. Рассмотрим поле $5 \times 5$, на котором нужно разместить один корабль $3 \times 1$ и один $1 \times 1$
2. Без учета второго корабля:
а) корабль $3 \times 1$ можно разместить 30-ю способами.
б) корабль $1 \times 1$ можно разместить 25-ю способами.

3. Разместим случайно (с равномерной вероятностью по всем вариантам) корабль $3 \times 1$
4. А на оставшихся разрешенных клетках разместим корабль $1 \times 1$, считая вероятность выбора каждой оставшейся клетки одинаковой.

Тогда
а) угловая клетка будет запретной для размещения корабля $1 \times 1$ для восьми вариантов размещения корабля $3 \times 1$.
б) а центральная клетка будет запретной для 18 вариантов размещения корабля $3 \times 1$ (то есть в более чем половине случаев).

Таким образом, размещая первым корабль $3 \times 1$ и выбирая каждый вариант с одинаковой вероятность, мы не можем обеспечить, чтобы корабль $1 \times 1$ занимал любую клетку с одинаковой вероятностью.
Автоматически верно обратное: размещая первым корабль $1 \times 1$ в любой клетке с одинаковой вероятностью, мы приходим к тому, что невозможно разместить корабль $3 \times 1$ с одинаковой вероятностью по всем 30-и вариантам размещения.

[komand]

EUgeneUS в сообщении #1510069 писал(а):

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

Анализ показал, что начиная с $10^6$ любая клетка занимается с равной вероятностью (поле 10x10, 10 кораблей). Чем меньше поле и чем больше кораблей, тем больше будет несостыковок. У вас один корабль занимает более половины поля, конечно будут сложности. Для простоты иллюстрации попробуйте на поле 3x3 разместить два 2п корабля. Очевидно, центральная клетка имеет нулевую вероятность быть занятой.

[komand]

Нашел ошибку: переставил две строчки при переделке под 3x3 поле. Всего один клик, а какой эффект ).
Итак, ловим один 2п на поле $3\times3$. По $10^8$ позициям число попыток $\approx3.49998±0,00001.$ Распределение:

[EUgeneUS]

komand в сообщении #1510080 писал(а):

Анализ показал, что начиная с 10^6 любая клетка занимается с равной вероятностью (поле 10x10, 10 кораблей).

Я немного о другом. Представим, что у Вас есть поле $10 \times 10$, на котором нужно разместить два квадратных корабля: $2 \times 2$ и $1 \times 1$.
Как Вы будете строить "случайную позицию?"

[Sender]

EUgeneUS в сообщении #1510177 писал(а):

Как Вы будете строить "случайную позицию?"

Одна из возможных стратегий уже звучала: выровнять вероятность занятия для всех клеток.

[EUgeneUS]

Sender в сообщении #1510178 писал(а):

Одна из возможных стратегий уже звучала: выровнять вероятность занятия для всех клеток.

Как? По шагам.

-- 20.03.2021, 15:10 --

UPD: попробуйте выровнять вероятность занятия всех клеток для размещения корабля $2 \times 1$ на поле $3 \times 3$

(hint)

Это невозможно

[komand]

EUgeneUS в сообщении #1510177 писал(а):

Я немного о другом. Представим, что у Вас есть поле $10 \times 10$, на котором нужно разместить два квадратных корабля: $2 \times 2$ и $1 \times 1$.
Как Вы будете строить "случайную позицию?"

Общий алгоритм такой:
1. Корабли расставляем от большего к меньшему
2. Случайно выбирается любая координата
3. Случайно выбирается любое из 4 направлений: вверх, вниз, влево, вправо
4. В этом направлении пытаемся вписать корабль. Если он не вмещается, переходим к 2.
На достаточно большом поле и при небольшом кол-ве кораблей алгоритм обеспечивает случайное занятие каждой клетки, при этом каждый корабль с равной вероятностью может появится в любой клетке. Для базовой игры распределение хорошее.
Однако, если поле маленькое, а кораблей много, или они слишком большие, алгоритм дает сбой. Простейший вариант этого сбоя я уже указывал: на поле 3x3 нельзя разместить два 2п корабля так, чтобы центральная клетка была занята.

[EUgeneUS]

komand в сообщении #1510180 писал(а):

3. Случайно выбирается любое из 4 направлений: вверх, вниз, влево, вправо
4. В этом направлении пытаемся вписать корабль. Если он не вмещается, переходим к 2.

В этом месте Вы пытаетесь вписать корабль целиком?

[komand]

EUgeneUS в сообщении #1510181 писал(а):

komand в сообщении #1510180 писал(а):

3. Случайно выбирается любое из 4 направлений: вверх, вниз, влево, вправо
4. В этом направлении пытаемся вписать корабль. Если он не вмещается, переходим к 2.

В этом месте Вы пытаетесь вписать корабль целиком?

Да. Но он может коснуться борта или др. корабля, тогда меняем координату. И еще: для проверки разных гипотез бывает сначала ставлю некоторое кол-во кораблей фиксировано, оставшиеся - случайно.