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
9256
уездный город Н
По системам обстрела - их как минимум нужно описать в тексте. (Я конечно мог пропустить, но не нашел описаний)

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
9256
уездный город Н
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
9256
уездный город Н
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
3052
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
9256
уездный город Н
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
3052
EUgeneUS в сообщении #1513372 писал(а):
Но мне казалось, что это довольно тривиальный факт.

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

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


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

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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