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

[mihaild]

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

то логично в качестве чистой стратегии обстрела рассматривать конкретную последовательность выстрелов, которых будет $100! \approx 10^{158}$

Нет, логично в качестве стратегии рассматривать функцию из текущего состояния поля (куда стреляли, куда попадали) в координаты следующего выстрела. Это еще один-два нолика в показатель степени добавит.
Если же считать, что цель игры - выбить корабли противника раньше, чем он выбьет наши, а не выбить его как можно быстрее, то может быть важно и ситуация с нашим полем (если мы видим, что противник нас скоро добьет - берем стратегию, которая имеет больше шансов на очень быстрый выигрыш, пусть даже увеличивая ожидание времени до победы).

[komand]

Цитата:

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

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

[mustitz]

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: какая цена игры, если её результат — количество ходов, затраченное на уничтожение корабля.

[komand]

mustitz в сообщении #1509963 писал(а):

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

Привете пример такой cтратегии: конкретное расположение кораблей. Я пока видел только лучшую стратегию (по кол-ву оставшихся ходов) и худшую. Только учтите, что к концу игры всегда остаются одни однопалубники, а стратегии их отлова нет. Если конкретно, при случайном расположении все корабли, кроме однопалубников, отлавливаются к 20-25 ходу (средняя игра 37,7 ходов), при "уплотненном" уже к 10-15 ходу, а "по Перельману" тупо на ПЕРВОМ ходу. Конец игры - это тупой расстрел оставшихся клеток в поисках последнего однопалубника.

[mihaild]

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

Только учтите, что к концу игры всегда остаются одни однопалубники

Это совершенно не обязано быть правдой.
Вообще вы, кажется, обсуждаете какие-то эвристики, без сколь-нибудь формальных результатов. Не очень понятно, как это оценивать.
А в строгом виде задача, скорее всего, неподъемна даже для случая двух кораблей.

[komand]

mihaild в сообщении #1509967 писал(а):

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

Только учтите, что к концу игры всегда остаются одни однопалубники

Это совершенно не обязано быть правдой.
Вообще вы, кажется, обсуждаете какие-то эвристики, без сколь-нибудь формальных результатов. Не очень понятно, как это оценивать.
А в строгом виде задача, скорее всего, неподъемна даже для случая двух кораблей.

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

[mihaild]

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

Я не публикую статью пока, поэтому кажется, что все голословно.

Я вполне готов поверить, что вы правильно посчитали результаты для какого-то класса стратегий. Но разница между таким подсчетом и строгим описанием оптимальной стратегии колоссальная.

[Geen]

mihaild в сообщении #1509967 писал(а):

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

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

[mihaild]

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

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

Если у нас один выстрел (и цель - попасть им), то равновесия Нэша - равомерная стрельба против любой равномерной (дающей одинаковую вероятность быть занятой для любой клетки) расстановки.
Для двух выстрелов это уже непонятно, но, наверное, можно посчитать (если скажем всего 2 корабля), там с учетом симметрий не так много стратегий.

[Geen]

mihaild в сообщении #1509975 писал(а):

и цель - попасть им

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

[mihaild]

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

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

Тут нужно уточнять, как её замерять. Потому что если противник ставит корабли детерменированно, то мы никаким выстрелом информации не получим)

[Sender]

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

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

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

[Sender]

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

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

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

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

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

[komand]

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

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

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

[12d3]

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

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

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