2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 7, 8, 9, 10, 11
 
 Re: Морской бой. Стратегия через теорию вероятностей
Сообщение07.04.2021, 20:55 
Аватара пользователя


16/03/21
70
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. И ещё такой тонкий момент. Вы же минимизируете мат ожидание количества ходов?
Тогда это не гарантирует максимизации вероятности выигрыша партии.
Например, может случиться так, что мат. ожидания количества ходов до выигрыша у разных игроков одинаковые, но один игрок выигрывает чаще.
Не очень понятно, как у разных игроков может быть разное мат. ожидание, если игра одна? Более того, наличие противника в модели не нужно. Достаточно минимизировать кол-во ходов до победы и вы будете выигрывать чаще.

 Профиль  
                  
 
 Re: Морской бой. Стратегия через теорию вероятностей
Сообщение07.04.2021, 21:19 
Аватара пользователя


11/12/16
10346
уездный город Н
По системам обстрела - их как минимум нужно описать в тексте. (Я конечно мог пропустить, но не нашел описаний)

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

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

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

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

 Профиль  
                  
 
 Re: Морской бой. Стратегия через теорию вероятностей
Сообщение07.04.2021, 21:35 
Аватара пользователя


16/03/21
70
EUgeneUS в сообщении #1513333 писал(а):
Нет. Вы не можете минимизировать количество ходов до победы (а точнее - до уничтожения флота противника). Вы можете минимизировать, например, мат. ожидание количества ходов до уничтожения флота противника. И да, этого может оказаться недостаточно, чтобы максимизировать вероятность победы в игре.

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

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

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

 Профиль  
                  
 
 Re: Морской бой. Стратегия через теорию вероятностей
Сообщение07.04.2021, 22:10 
Аватара пользователя


11/12/16
10346
уездный город Н
komand в сообщении #1513336 писал(а):
У какой стратегии $\mu$ выигрыша выше, та и будет чаще выигрывать.

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

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

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

 Профиль  
                  
 
 Re: Морской бой. Стратегия через теорию вероятностей
Сообщение07.04.2021, 22:21 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Морской бой. Стратегия через теорию вероятностей
Сообщение07.04.2021, 23:29 
Аватара пользователя


11/12/16
10346
уездный город Н
komand в сообщении #1513344 писал(а):
К примеру, мы играем с противников на броски кости d6. Если выпадает единица, он выигрывает, если любое др. число - я.


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

 Профиль  
                  
 
 Re: Морской бой. Стратегия через теорию вероятностей
Сообщение08.04.2021, 00:19 
Аватара пользователя


16/03/21
70
EUgeneUS в сообщении #1513347 писал(а):
komand в сообщении #1513344 писал(а):
К примеру, мы играем с противников на броски кости d6. Если выпадает единица, он выигрывает, если любое др. число - я.

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

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

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

 Профиль  
                  
 
 Re: Морской бой. Стратегия через теорию вероятностей
Сообщение08.04.2021, 00:40 
Заслуженный участник
Аватара пользователя


01/09/13
3233
EUgeneUS в сообщении #1513347 писал(а):
Так вот, эти распределения могут быть такими, что один из игроков будет выигрывать чаще, чем другой.

Например?

 Профиль  
                  
 
 Re: Морской бой. Стратегия через теорию вероятностей
Сообщение08.04.2021, 01:36 
Аватара пользователя


16/03/21
70
Geen в сообщении #1513357 писал(а):
EUgeneUS в сообщении #1513347 писал(а):
Так вот, эти распределения могут быть такими, что один из игроков будет выигрывать чаще, чем другой.

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

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

 Профиль  
                  
 
 Re: Морской бой. Стратегия через теорию вероятностей
Сообщение08.04.2021, 08:28 
Аватара пользователя


11/12/16
10346
уездный город Н
Geen в сообщении #1513357 писал(а):
Например?

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

-- 08.04.2021, 08:46 --

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

 Профиль  
                  
 
 Re: Морской бой. Стратегия через теорию вероятностей
Сообщение08.04.2021, 13:03 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Морской бой. Стратегия через теорию вероятностей
Сообщение08.04.2021, 13:41 
Заслуженный участник
Аватара пользователя


01/09/13
3233
EUgeneUS в сообщении #1513372 писал(а):
Но мне казалось, что это довольно тривиальный факт.

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

 Профиль  
                  
 
 Re: Морской бой. Стратегия через теорию вероятностей
Сообщение19.04.2021, 01:24 
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 163 ]  На страницу Пред.  1 ... 7, 8, 9, 10, 11

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group