2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5 ... 11  След.
 
 Re: Морской бой. Стратегия через теорию вероятностей
Сообщение18.03.2021, 20:45 
Заслуженный участник
Аватара пользователя


16/07/14
5319
Москва
EUgeneUS в сообщении #1509951 писал(а):
то логично в качестве чистой стратегии обстрела рассматривать конкретную последовательность выстрелов, которых будет $100! \approx 10^{158}$
Нет, логично в качестве стратегии рассматривать функцию из текущего состояния поля (куда стреляли, куда попадали) в координаты следующего выстрела. Это еще один-два нолика в показатель степени добавит.
Если же считать, что цель игры - выбить корабли противника раньше, чем он выбьет наши, а не выбить его как можно быстрее, то может быть важно и ситуация с нашим полем (если мы видим, что противник нас скоро добьет - берем стратегию, которая имеет больше шансов на очень быстрый выигрыш, пусть даже увеличивая ожидание времени до победы).

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


16/03/21
70
Цитата:
Если в качестве чистой стратегии рассматривать конкретную позицию (см. выше), то логично в качестве чистой стратегии обстрела рассматривать конкретную последовательность выстрелов, которых будет $100! \approx 10^{158}$
Начальных расстановок кораблей много меньше, \approx$10^{19}$ (по др. оценкам, \approx$10^{17}), так что возможно даже рассчитать все позиции с начала игры. У меня десктоп такое не тянет (всего лишь 30000 игр в секунду), поэтому рассчитывал ВСЕ позиции после отлова 4-палубников, это много проще. Особого выигрыша против "сетка-3" + отлов двухпалубников не дало.

-- 18.03.2021, 22:40 --

mihaild в сообщении #1509952 писал(а):
Если же считать, что цель игры - выбить корабли противника раньше, чем он выбьет наши, а не выбить его как можно быстрее, то может быть важно и ситуация с нашим полем (если мы видим, что противник нас скоро добьет - берем стратегию, которая имеет больше шансов на очень быстрый выигрыш, пусть даже увеличивая ожидание времени до победы).
Забудьте о противнике! Считайте, что его нет. Ваш противник - число ходов (попыток) до полного потопления чужого флота. Чем быстрее, тем лучше. Вы можете играть асинхронно: сначала вы сыграет против его размещения кораблей, потом он против вашего и сравниваете кол-во ходов (попыток). У кого меньше, тот и выиграл. Поэтому можно сосредоточится только на одном важном критерии игры: кол-во попыток (ходов), требуемых для уничтожения некого расположения (слчайного или по какой-то системе).

-- 18.03.2021, 22:44 --

EUgeneUS в сообщении #1509951 писал(а):
Вы используете слово "стратегия" не в том смысле, что уважаемые mihaild и Padawan.
У Вас "стратегий" обстрела две, потому что Вы два алгоритма ведения огня рассматриваете.
А уважаемые mihaild и Padawan говорят о чистых стратегиях в терминах теории игр. Тогда чистых стратегий ведения огня $\approx 10^{158}$, сильно больше, чем атомов в видимой части Вселенной.
Стратегий на самом деле огромное кол-во. Но их можно классифицировать по одному критерию: случайно вы стреляете или нет. Сначала разбирается случайная стратегия, а потом "абсолютная", т.е. каждый ход делается с учетом наиболее вероятного расположения чужих кораблей. Лучше стратегии быть просто не может по определению. К сожалению, как я писал выше, десктоп такие расчеты не тянет с начальной позиции, но после отлова 4-х палубников - неплохо. И эта стратегия обстрела показала минимальное преимущество перед классикой (отлов 4-х, 3-х, 2-х палубников последовательно), при этом требует ресурсы на много порядков больше и недоступна человеку.
На самом деле еще хуже: на самом деле "абсолютная" стратегия обстрела не сильно выигрывает у случайной. Конкретные цифры я пока не хочу публиковать, это раскрытие статьи.

-- 18.03.2021, 22:55 --

mustitz в сообщении #1509950 писал(а):
А зачем брать сразу 10x10, если можно взять 3x3 c одним двухпалубным, найти точное решение в терминах теории игр и посмотреть, насколько согласованный результат даст Ваш метод? Потом можно взять 4x4 с однопалубным и двухпалубным и т. п. И выводы проверяться сами собой.
Я рассматривал все поля, от $2\times2$ до $20\times20$ и разное кол-во кораблей (от 1 до 30). Метод согласуется с теорией (когда удается подсчитать). Да и как он может не согласоваться? Программа же генерирует начальное расположения флота и сама же потом его топит. И так $10^7-10^9$ раз. После чего строится распределение, высчитывается среднее, дисперсия, квадратичное отклонение, стандартная ошибка (все это возможно, потому что распределение получается близко к нормальному). Можно возразить, что $10^9$ - это только $10^{-10}$ от всех расположений кораблей. Но последовательности в $10^7$ генерировались сотни раз и сравнивались, существенных расхождений нет. Цитата:
1. Проверено, что при большем кол-ве генераций позиций (от $10^7$) вероятность занятости некой клетки кораблем одинакова, $\approx0.01000±0.00003$. Т.е. при случайном расположении кораблей можно вести обстрел в любом порядке, разницы в попытках не будет.
2. Число свободных клеток после генерации $\approx17,7$. Отсюда можно оценить число возможных позиций в игре, как С_{100}^{18}$ $\approx10^{19}$. Здесь на основе др. алгоритма оценка ниже, $\approx5$\times$10^{17}$
3. Среди $10^7$ позиций ни разу не было найдено повторяющихся (проверено сотни раз). Это плохо: хотелось бы протестировать все возможные позиции. Но на современном десктопе удавалось достичь скорости < 30000/сек позиций на одном процессоре, это слишком мало (см. п. 2).

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

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


10/04/12
688
komand в сообщении #1509960 писал(а):
Забудьте о противнике! Считайте, что его нет. Ваш противник - число ходов (попыток) до полного потопления чужого флота. Чем быстрее, тем лучше. Вы можете играть асинхронно: сначала вы сыграет против его размещения кораблей, потом он против вашего и сравниваете кол-во ходов (попыток). У кого меньше, тот и выиграл. Поэтому можно сосредоточится только на одном важном критерии игры: кол-во попыток (ходов), требуемых для уничтожения некого расположения (слчайного или по какой-то системе).


Надо доказать, что все три игры эквивалентны, для меня это неочевидно. Основное различие может проявляться в том, что в случае когда мы отстаём, то может быть выгоднее выбирать вариант с бо́льшей дисперсией и меньшим математическим ожиданием. Например, соперник следующим ходом нас 100% потопит, а у нас есть стратегия, которая убивает за один ход с вероятностью 30%, за два с вероятностью 40% и за три с вероятностью 30%, и другая, которая за один ход 40%, за два хода 10% и три хода 50%, то математическое ожидание первой стратегии 2 хода, второй стратегии 2.1, так что вторая стратегия хуже. Но с точки зрения результата, первая даёт шанс 30% на победу, вторая 40%.

-- 18.03.2021, 22:14 --

komand в сообщении #1509960 писал(а):
Если хотите, назовите размер поля, число и состав кораблей, я дам вам распределение попыток для их уничтожения, среднее и дисперсию.


Это ерунда и мне это неинтересно. Мне интереснее другие вопросы:

У нас есть поле 3x3, на котором можно расположить один двухпалубный корабль. У защищающейся стороны есть две расстановки (двухпалубный в центре и возле борта). Вопрос №1: с какой вероятностью эти расстановки должны выбираться в случае оптимальной игры. Вопрос №2: какие вообще есть стратегии обстрела? Вопрос №3: какая оптимальная стратегия обстрела? Вопрос №4: какая цена игры, если её результат — количество ходов, затраченное на уничтожение корабля.

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


16/03/21
70
mustitz в сообщении #1509963 писал(а):
Например, соперник следующим ходом нас 100% потопит, а у нас есть стратегия, которая убивает за один ход с вероятностью 30%, за два с вероятностью 40% и за три с вероятностью 30%, и другая, которая за один ход 40%, за два хода 10% и три хода 50%, то математическое ожидание первой стратегии 2 хода, второй стратегии 2.1, так что вторая стратегия хуже. Но с точки зрения результата, первая даёт шанс 30% на победу, вторая 40%.
Привете пример такой cтратегии: конкретное расположение кораблей. Я пока видел только лучшую стратегию (по кол-ву оставшихся ходов) и худшую. Только учтите, что к концу игры всегда остаются одни однопалубники, а стратегии их отлова нет. Если конкретно, при случайном расположении все корабли, кроме однопалубников, отлавливаются к 20-25 ходу (средняя игра 37,7 ходов), при "уплотненном" уже к 10-15 ходу, а "по Перельману" тупо на ПЕРВОМ ходу. Конец игры - это тупой расстрел оставшихся клеток в поисках последнего однопалубника.

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


16/07/14
5319
Москва
komand в сообщении #1509965 писал(а):
Только учтите, что к концу игры всегда остаются одни однопалубники
Это совершенно не обязано быть правдой.
Вообще вы, кажется, обсуждаете какие-то эвристики, без сколь-нибудь формальных результатов. Не очень понятно, как это оценивать.
А в строгом виде задача, скорее всего, неподъемна даже для случая двух кораблей.

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


16/03/21
70
mihaild в сообщении #1509967 писал(а):
komand в сообщении #1509965 писал(а):
Только учтите, что к концу игры всегда остаются одни однопалубники
Это совершенно не обязано быть правдой.
Вообще вы, кажется, обсуждаете какие-то эвристики, без сколь-нибудь формальных результатов. Не очень понятно, как это оценивать.
А в строгом виде задача, скорее всего, неподъемна даже для случая двух кораблей.

У меня статистическая обработка $10^7$-$10^9$ расположения кораблей. Распределение близко к нормальному, сходимость хорошая, 3-4 знака после запятой при P=0.999. Так вот, даже при случайном поиске в конце игры не остается многопалубников, точнее вероятность этого запредельно мала. Могу посчитать точнее. Тем более при поиске "сеткой", которая заточена на поиск 4x-3x-2x палубников последовательно.
Я не публикую статью пока, поэтому кажется, что все голословно.

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


16/07/14
5319
Москва
komand в сообщении #1509972 писал(а):
Я не публикую статью пока, поэтому кажется, что все голословно.
Я вполне готов поверить, что вы правильно посчитали результаты для какого-то класса стратегий. Но разница между таким подсчетом и строгим описанием оптимальной стратегии колоссальная.

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


01/09/13
3187
mihaild в сообщении #1509967 писал(а):
А в строгом виде задача, скорее всего, неподъемна даже для случая двух кораблей.

Я думаю, для начала можно рассмотреть только один выстрел...

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


16/07/14
5319
Москва
Geen в сообщении #1509974 писал(а):
для начала можно рассмотреть только один выстрел...
Если у нас один выстрел (и цель - попасть им), то равновесия Нэша - равомерная стрельба против любой равномерной (дающей одинаковую вероятность быть занятой для любой клетки) расстановки.
Для двух выстрелов это уже непонятно, но, наверное, можно посчитать (если скажем всего 2 корабля), там с учетом симметрий не так много стратегий.

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


01/09/13
3187
mihaild в сообщении #1509975 писал(а):
и цель - попасть им

Конечно нет - цель получить наибольшую информацию.

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


16/07/14
5319
Москва
Geen в сообщении #1509976 писал(а):
Конечно нет - цель получить наибольшую информацию.
Тут нужно уточнять, как её замерять. Потому что если противник ставит корабли детерменированно, то мы никаким выстрелом информации не получим)

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


14/01/11
2681
Если у противника ровно один двухпалубный случайно размещённый корабль, то что-то мне подсказывает, что оптимальной стратегией будет раскрасить доску шахматной раскраской, случайным образом выбрать цвет и случайным образом пулять по клеткам этого цвета, пока не попадём.

-- Пт мар 19, 2021 10:47:23 --

Хотя нет. Если у нас поле $n\times n$, у нас каждая угловая клетка будет занята в двух возможных размещениях, неугловая клетка на стороне - в трёх, а остальные - в четырёх.

 Профиль  
                  
 
 Re: Морской бой. Стратегия через теорию вероятностей
Сообщение19.03.2021, 11:32 


14/01/11
2681
Столько мороки с этими угловыми. Может, сначала для простоты рассмотреть случай сферического в вакууме тороидального поля?

-- Пт мар 19, 2021 12:16:29 --

Sender в сообщении #1509993 писал(а):
Если у противника ровно один двухпалубный случайно размещённый корабль, то что-то мне подсказывает, что оптимальной стратегией будет раскрасить доску шахматной раскраской, случайным образом выбрать цвет и случайным образом пулять по клеткам этого цвета, пока не попадём.

В принципе, эта стратегия работает на тороидальном поле при чётном $n$ для одного двухпалубного корабля :-). В этом случае в силу симметрии все расстановки эквивалентны, и оптимальной стратегией противника будет случайный выбор. Каждый неудачный выстрел отсеивает 4 расстановки, образующие крестик. При чётном $n$ шахматная сетка замыкается, и крестики с центрами на полях одного цвета не пересекаются. После первого попадания надо проверить $4$ соседние клетки(опять-таки, тут полная симметрия). В случае нечётного $n$ сетка не замыкается, и опять возникают граничные эффекты...

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


16/03/21
70
Sender в сообщении #1510002 писал(а):
Столько мороки с этими угловыми. Может, сначала для простоты рассмотреть случай сферического в вакууме тороидального поля?
Обсчет показал, что все поля на достаточно большом поле эквиваленты. Примерно с положения, когда поле в два-три раза больше самого большого корабля. Т.е. на поле $10\times10$ при одном 4п корабле их можно считать несущественными (при достаточно больших генерациях, от $10^5$). Краевые эффекты проявляют себя др. способом: они дают меньший "ореол" (мертвую зону) вокруг потопленных кораблей и потому увеличивают число оставшихся свободных клеток. Но опять же обсчет показал, что преимущество компактных расположений кораблей (в углах, на бортах) не так существенно, как принято считать.

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


04/03/09
899
Sender в сообщении #1509993 писал(а):
Если у противника ровно один двухпалубный случайно размещённый корабль, то что-то мне подсказывает, что оптимальной стратегией будет раскрасить доску шахматной раскраской, случайным образом выбрать цвет и случайным образом пулять по клеткам этого цвета, пока не попадём.

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

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

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



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

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


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

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