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

[komand]

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

komand, моя заслуга при расчёте позиций минимальна, я всего лишь взял готовую программу, выложенную по ссылке, указанной grizzly в сообщении https://dxdy.ru/post1512752.html#p1512752.

Программу нужно было скомпилить и адаптировать к наличию 1п. Спасибо.

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

1.

Цитата:

Ход — ваши действия до передачи хода противнику

Рекурсия не нужна.

Моя ошибка, исправлю.

Цитата:

2. Не очень понятно, как устроен "случайный обстрел".
После попадания ("ранил") следующий выстрел как делается? Тоже случайно или по какой-то методе добиваем? Что такое "свободная клетка" (этого нет в терминах)?

1. Случайный обстрел может быть трех видов: совсем случайный, некоторой матрице (массиву) и некий алгоритм.
1.1. Совсем случайный обстрел - генерируем любую координату и смотрим, стреляли ли туда. Если нет, стреляем. И так до исчерпания всех координат или до победы. На самом деле чуть хитрее: уже стрелянная координата удаляется из пула возможных. И след. выстрел идет уже по сократившемся пуле. Проще показать на примере. Допустим, у нас есть поле $2\times2$, в нем 4 координаты: 00,01,10,11. Эти числа записаны в отдельный массив. У него длина 4. Генерим случайно число от 0 до "длина массива", т.е. "4". Допустим, это 11. Стреляем туда. Координату из массива убираем. Теперь в нем три координаты: 00,01,10. Генерим случайное число от о 0 до 3. Ну и так далее, пока массив не исчерпается. Конечно учитывается "мертвая зона" вокруг кораблей, и сами корабли, эти координаты тоже вычеркиваются из маccива.
1.2. Обстрел по системе. Допустим, для поля $10\times10$ у нас система "сетка-4", т.е. наилучшая для поимки 4п. Координаты в массиве такие:
[03, 07, 12, 16, 21, 25, 29, 30, 34, 38, 43, 47, 52, 56, 61, 65, 69, 70, 74, 78, 83, 87, 92, 96]. Далее, как в 1.1: генерим случайное число и выбираем координату из этого массива. Если он закончился, может быть след. массив. Если все приоритеты кончились, переходим к 1.1., т.е. заканчиваем случайно.
1.3. Обстрел по алгоритму. Программа исследует каждый войд и строим матрицу плотностей. Далее стреляет по координате, в которой наиболее вероятен корабль. И так каждый раз. Однако, если две или более вероятности равны, из них выбирается одна случайно.

"Свободная клетка" - клетка, в которую еще не стреляли и в которая не занята уже потопленным кораблем или его аурой. Исправлю в описании.

Цитата:

3. И ещё такой тонкий момент. Вы же минимизируете мат ожидание количества ходов?
Тогда это не гарантирует максимизации вероятности выигрыша партии.
Например, может случиться так, что мат. ожидания количества ходов до выигрыша у разных игроков одинаковые, но один игрок выигрывает чаще.

Не очень понятно, как у разных игроков может быть разное мат. ожидание, если игра одна? Более того, наличие противника в модели не нужно. Достаточно минимизировать кол-во ходов до победы и вы будете выигрывать чаще.

[EUgeneUS]

По системам обстрела - их как минимум нужно описать в тексте. (Я конечно мог пропустить, но не нашел описаний)

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

Не очень понятно, как у разных игроков может быть разное мат. ожидание, если игра одна?

Разное (или одинаковое) мат. ожидание количества ходов до уничтожения флота противника.

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

Достаточно минимизировать кол-во ходов до победы и вы будете выигрывать чаще.

Нет. Вы не можете минимизировать количество ходов до победы (а точнее - до уничтожения флота противника). Вы можете минимизировать, например, мат. ожидание количества ходов до уничтожения флота противника. И да, этого может оказаться недостаточно, чтобы максимизировать вероятность победы в игре.

[komand]

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

Нет. Вы не можете минимизировать количество ходов до победы (а точнее - до уничтожения флота противника). Вы можете минимизировать, например, мат. ожидание количества ходов до уничтожения флота противника. И да, этого может оказаться недостаточно, чтобы максимизировать вероятность победы в игре.

А что еще в игре "морской бой" существует, что влияет на победу, кроме кол-ва ходов? Эта величина как раз и характеризует вероятность вашего выигрыша на длинной дистанции. Если я открою, ВДРУГ стратегию, которая в среднем выигрывает за 20 ходов (с нормальным распределением), то я могу выиграть у любого (опять же на длинной дистанции). Или есть что-то, чего я не понял в игре?

Конечно, в каждой отдельной партии мат. ожидание ($\mu$) не гарантирует победы, разве что \mu=1. Модель дает только вероятность чаще или реже выигрывать. Но если модель адекватная, распределение не кривое, сходимость хорошая, то по закону больших чисел у вычисленная величина будет сходится к $\mu$. У какой стратегии $\mu$ выигрыша выше, та и будет чаще выигрывать. Допустим, в американской рулетке $\mu$ вашего выигрыша 0,95, а в в блекджеке 0,97 (зависит от правил). В обе игры вы проигрываете. Но, если вы играете в блекджек, в среднем будете будете проигрывать на 0,02 реже. Так и в моей модели. Если у вас $\mu$ 37,5 ходов, а у противника 37,7, у вас преимущество, хотя и очень маленькое. То есть оно проявится на сотнях, если не тысячах партий. Другой пример: "дан" в некоторых играх, как обозначение меры мастерства игрока. Если мастер высшего дана сел играть с новичком, допустим в нарды, нет гарантий, что он выиграет, потому что есть случайность. Но в большинстве партий он будет выигрывать. Насколько часто, как раз дан и говорит (условно, конечно).

И еще: вычисленное средняя величина на любой выборке - это не $\mu$, это по-прежнему случайная величина. Но она может бесконечно сходиться к $\mu$, поэтому нередко понятия подменяют.
Еще соображение: модель может не учитывать какие-то факторы, тогда вычисленная ей $\mu$ не соответствует реальности и тогда да, не гарантирует победы (на длинной дистанции).
Вообще, в теории вероятностей я неглубоко разбираюсь, пусть меня поправят более знающие люди.

[EUgeneUS]

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

У какой стратегии $\mu$ выигрыша выше, та и будет чаще выигрывать.

Нет. В том смысле, что необязательно.
Модель такая:
а) Играют два игрока.
б) У каждого есть какая-то случайная величина с какими-то распределениями (это количество ходов до уничтожения всего флота противника).
в) Играют в больше-меньше. У кого значение случайной величины в конкретном опыте меньше - тот выиграл.
г) Так вот. Равенство мат. ожиданий случайных величин игроков, не гарантирует равенство вероятностей выиграть в игру больше-меньше.

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

И еще: вычисленное средняя величина на любой выборке - это не $\mu$, это по-прежнему случайная величина.

Да, это случайная величина, которая является оценкой мат. ожидания.

[komand]

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

) Так вот. Равенство мат. ожиданий случайных величин игроков, не гарантирует равенство вероятностей выиграть в игру больше-меньше.

Объясните подробней. К примеру, мы играем с противников на броски кости d6. Если выпадает единица, он выигрывает, если любое др. число - я. Мое $\mu$=^ 5/_6$. Как я могу проиграть на длинной дистанции?
Да, и за распределениями в своей модели я следил. Они не сильно отклоняются от нормального распределения. То есть мы играем в "морской бой", по одинаковым правилам, распределения наших стратегий близки, у меня некое преимущество по ходам, но все равно я могу не выиграть (на длинной дистанции)? Почему?
Допускаю, что в некой игре преимущества по $\mu$ будет недостаточно. Наверняка есть игры с распределением Коши. Но почему такое может случиться в морском бое?

[EUgeneUS]

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

К примеру, мы играем с противников на броски кости d6. Если выпадает единица, он выигрывает, если любое др. число - я.

Это не правильная модель. Бросается две кости. Каждым игроком - своя. Выигрывает тот, у кого выпало больше (или меньше - как договориться).
Далее предположим, что вероятность выпадения на костях разных чисел - разная. Но распределена так, что матожидание выпавшего числа ровно $3.5$ для обоих костей - как и для обычного "честного" кубика.
Так вот, эти распределения могут быть такими, что один из игроков будет выигрывать чаще, чем другой.

[komand]

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

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

К примеру, мы играем с противников на броски кости d6. Если выпадает единица, он выигрывает, если любое др. число - я.

Это не правильная модель. Бросается две кости. Каждым игроком - своя. Выигрывает тот, у кого выпало больше (или меньше - как договориться).
Далее предположим, что вероятность выпадения на костях разных чисел - разная. Но распределена так, что матожидание выпавшего числа ровно $3.5$ для обоих костей - как и для обычного "честного" кубика.
Так вот, эти распределения могут быть такими, что один из игроков будет выигрывать чаще, чем другой.

А почему вероятность на костях разная? Потому что кости разные? Тогда как это применить к игре "морской бой"? Разные тетрадки, ручки, цвет чернил? Кстати, в моей модели противника нет. Это обосновано в начале статьи с ссылкой на источник. То есть программа соревнуется сама с собой. Какие основания считать, что какие-то генерации не такие, как другие (то есть кости неравные)?
И еще. Я же не просто мат. ожидание сравниваю, я смотрю распределение. Если оно бы отличалось от нормального, то и модель бы не стал программировать. То есть "кости" одинаковы не только мат. ожиданием, но и распределением.

Кстати, для "разных" костей. Допустим, у нас с противником d6. У меня "честная", а у противника грани "1" и противоположная "6" равномерно (если неравномерно, собьется мат. ожидание, это можно будет уловить в игре) утяжелены так, что они выпадают чаще других на 10% (или на др. величину). Мат. ожидание такой кости та же, 3,5. В некоторых играх (типа "крэпс") это дает серьезное преимущество. Поймать мошенника с такой костью трудно: нужно сделать тысячу бросков и убедиться, что распределение не гладкое, имеет лишние пики. Но в "обычной" игре, на "больше-меньше", это даст преимущество?

[Geen]

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

Так вот, эти распределения могут быть такими, что один из игроков будет выигрывать чаще, чем другой.

Например?

[komand]

Geen в сообщении #1513357 писал(а):

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

Так вот, эти распределения могут быть такими, что один из игроков будет выигрывать чаще, чем другой.

Например?

Мне тоже интересен такой пример.
Кстати, насчет распределения. Такой пример: у противника кость d6, а у меня монетка. На одной стороне монетки 6, на другой 1. А у третьего участника "забега" вообще все просто: у него карточка с надписью 3,5, т.е. у него всегда выпадает это число. У всех троих мат. ожидание одинаковое, но распределения кардинально различаются.
Играем в простую игру: тестируем наши ГСЧ. У кого выпало больше, тот выиграл. Вопрос: кто выиграет на длинной дистанции?

Теперь пример игры, в которой в самом деле не будет выигравшего. Допустим, поместили очень тонкую пудру в маленькую лужицу воды. Навели микроскоп и наблюдаем за какой-то одной частицей пудры. Она движется хаотично (броуновское движение), но за некий промежуток времени (допустим, минута) продвигается больше влево или вправо. Мы с противником делаем ставки, куда она сдвинется. Так вот, каждый из нас может иметь какой угодно выигрыш/проигрыш, его нельзя просчитать. В этой игре нет мат. ожидания, а дисперсия бесконечно велика.
Но согласитесь, эта игра довольна необычна. Поэтому, прежде чем писать статью, я многократно убедился, что распределения в "морском бое" близки к нормальному.

[EUgeneUS]

Geen в сообщении #1513357 писал(а):

Например?

Конечно, у меня есть пример.
Но мне казалось, что это довольно тривиальный факт.
А если не тривиальный, то опубликую в олимпиадных задачах

-- 08.04.2021, 08:46 --

UPD: опубликовал

[komand]

Попытался вставить ссылку на статью в подпись, что-то не отображается подпись.

[Geen]

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

Но мне казалось, что это довольно тривиальный факт.

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

[komand]

В этой статье доказывается, что "Морской бой" относится к NP-полной задаче, т.е. решается только перебором за экспоненциальное время. Хотя там разбирается другая игра, а именно "Battleship puzzle", но все равно интересно.