2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 3, 4, 5, 6, 7, 8, 9 ... 11  След.
 
 Re: Морской бой. Стратегия через теорию вероятностей
Сообщение26.03.2021, 17:00 
Заслуженный участник


04/03/09
902
Еще немного оптимальных стратегий для доски 4х4. Я рассмотрел поиск одного корабля (2п, 3п, 4п). Оптимальная расстановка такова, что все неугловые положения равновероятны (для 3п и 4п это тривиально, а вот для 2п - уже нет).
Для 2п: угловые положения выбираем с вероятностью $\frac{7}{120}$, и соответственно неугловые с вероятностью $\frac{1}{30}$. Две наилучших стратегии обстрела:
$\begin{center}
    \begin{tabular}{| c | c | c | c |}
    \hline
    3 &   & 2 &   \\ \hline
      & 1 &   & 2 \\ \hline
    2 &   & 1 &   \\ \hline
      & 2 &   & 3 \\ \hline
    \end{tabular}
\end{center}$ и $\begin{center}
    \begin{tabular}{| c | c | c | c |}
    \hline
    3 &   & 2 &   \\ \hline
      & 1 &   & 4 \\ \hline
    2 &   & 5 & 2 \\ \hline
      & 4 & 2 &  \\ \hline
    \end{tabular}
\end{center}$
Здесь циферками обозначен приоритет: сначала стреляем по всем клеткам с цифрой 1, потом по всем клеткам с цифрой 2, и т.д., пока не попадем.
Итого, кораблик убивается в среднем за $\frac{379}{60}$ выстрелов.
Для 3п: угловые положения выбираем с вероятностью $\frac{11}{142}$, и соответственно неугловые с вероятностью $\frac{4}{71}$. Две наилучших стратегии обстрела:
$\begin{center}
    \begin{tabular}{| c | c | c | c |}
    \hline
      &   & 2 &   \\ \hline
      & 1 &   &   \\ \hline
    2 &   &   & 2  \\ \hline
      &   &  2 &   \\ \hline
    \end{tabular}
\end{center}$ и $\begin{center}
    \begin{tabular}{| c | c | c | c |}
    \hline
      &   & 1 &   \\ \hline
    1 & 2 &   &   \\ \hline
      &   & 2 & 1 \\ \hline
      & 1 &   &  \\ \hline
    \end{tabular}
\end{center}$
Во второй стратегии могут быть небольшие вариации, но всегда первые четыре выстрела по сторонам, а пятый выстрел в центр.
Корабль убивается в среднем за $\frac{108}{19}$ выстрелов.
Для 4п: все положения равновероятны. Стратегия обстрела такова, что первыми четырьмя выстрелами должны зацепить все вертикали и горизонтали, а дальше добиваем. Корабль убивается за 6 выстрелов в среднем.

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


14/01/11
2796
Но ведь никакая из этих стратегий обстрела не оптимальна по Нэшу. Если противник заранее знает, какая из них применяется, он, скажем, на первой картинке поставит корабль на тройку и протянет немного дольше. :-)

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


04/03/09
902
А я пока и не знаю, как найти оптимальную по Нэшу стратегию обстрела. Могу только найти множество чистых стратегий, которые дают наилучший результат при условии, что расстановка оптимальна по Нэшу. Надо было аккуратнее выражаться. Из этого множества парочку я и привел. А как посчитать вероятности, в какой ситуации в какую клеточку стрелять - это надо думать.

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


16/03/21
70
$4\times4$ я тоже проверял. Везде рулит сетка, причем где чем больше поле, тем больше. Но на маленьких полях, типа $3\times3$могут проявляться "краевые эффекты". Поэтому не стоит из стратегий на маленьких полях выводить большие. Конкретно для $4\times4$ сетка убивает 2п корабль макс. за 8 ходов, в среднем за 4.5 (без добивания).
3п на таком поле лучше не тестировать, слишком большой, "краевые эффекты".

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


01/09/13
3301
не надо считать ходы - это неудобно, хотя их вседа ровно на $N-1$ меньше, чем количество выстрелов.

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


16/03/21
70
Geen в сообщении #1511475 писал(а):
не надо считать ходы - это неудобно, хотя их вседа ровно на $N-1$ меньше, чем количество выстрелов.
Ходы = выстрелы = попытки. Это просто разное название. Иначе легко запутаться. Но кол-во попыток может различаться в разных играх, если нет "премиального" выстрела Если считать по базовым правилам, премиальный выстрел приходится учитывать. То есть, к примеру, последовательность "попал, мимо, попал, мимо" - это не 4 попытки, а две.
И еще, с премией есть шанс утопить весь флот противника одним выстрелом.
Еще: начинающий первым имеет примерно 3% преимущества, это немало. Стоило бы ввести "посмертный выстрел", т.е. противник имеет право сделать 1 выстрел, когда весь его флот уже утоплен. Это уровняло бы шансы.

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


11/12/16
10985
уездный город Н
komand в сообщении #1511485 писал(а):
Ходы = выстрелы = попытки.


У вас странная, контринтуитивная терминология.
ИМХО, более логично понимать так:
"Выстрел" - одна "точка"(промах), или один "крестик" (попадание). "Один снаряд".
"Ход" - последовательность выстрелов, которые последовательно делает одна сторона.
То есть:

"К9 - пропах" - это один выстрел и один ход.
"А5 - ранил, А6 - убил, Б10 - промах" - это три выстрела, но один ход.

Geen в сообщении #1511475 писал(а):
не надо считать ходы - это неудобно, хотя их вседа ровно на $N-1$ меньше, чем количество выстрелов.

Количества ходов всегда меньше количество выстрелов на количество попаданий.

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


01/09/13
3301
EUgeneUS в сообщении #1511515 писал(а):
Количества ходов всегда меньше количество выстрелов на количество попаданий.

Нет, на единицу меньше - последним попаданием заканчивается игра. Это в конце.
А в середине зависит от того, где мы "прервались".

-- 27.03.2021, 11:48 --

EUgeneUS в сообщении #1511515 писал(а):
У вас странная, контринтуитивная терминология.

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

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


11/12/16
10985
уездный город Н
Geen в сообщении #1511558 писал(а):
Нет, на единицу меньше - последним попаданием заканчивается игра. Это в конце.
А в середине зависит от того, где мы "прервались".

Не понимаю, как это.
Можете пояснить?

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


01/09/13
3301
Допустим, Вы всё убиваете первым ходом - выстрелов при этом 20 (суммарное количество занятых клеток).

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


11/12/16
10985
уездный город Н
Geen в сообщении #1511565 писал(а):
Допустим, Вы всё убиваете первым ходом - выстрелов при этом 20 (суммарное количество занятых клеток).

Пусть
$n$ - количество выстрелов за ход,
$k$ - количество попаданий за ход.
$l$ - количество промахов за ход.

$N$ - общее количество выстрелов за игру,
$K$ - общее количество попаданий за игру (равно количеству занятых клеток)
$L$ - общее количество промахов за игру
$M$ - общее количество ходов за игру

Тогда справедливы следующие соотношения:
$n = k+1$ и $l=1$, если ход не последний (не всех убили)
$n = k$ и $l=0$, если ход последний (всех убили).

$M = L+1$
$N = L+K = M + K -1$
$M = N - K +1$ (1)

Вот тут:
EUgeneUS в сообщении #1511515 писал(а):
Количества ходов всегда меньше количество выстрелов на количество попаданий.

Я имел в виду (1), но не учел особенность последнего хода и не добавил $1$.

А что Вы имели в виду тут (с учетом моего болда):
Geen в сообщении #1511558 писал(а):
Нет, на единицу меньше - последним попаданием заканчивается игра. Это в конце.

?

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


01/09/13
3301
EUgeneUS в сообщении #1511569 писал(а):
А что Вы имели в виду тут (с учетом моего болда):

Неудачно выразился - разница на единицу меньше.

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


11/12/16
10985
уездный город Н
Geen
Понятно. Спасибо за разъяснение.

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


16/03/21
70
Хорошо, пусть будет ход - последовательность выстрелов. Хотя в статье я использую слово "попытка" - это ближе к теории вероятностей. Подумаю, может исправлю.
Есть простой способ получить немалое преимущество в игре ($\approx3$ игр на 100): просто всегда начинать первым ).
Кстати, при огромном кол-ве сыгранных партий компьютерной программой (от $10^8$) не было ни одного случая, чтобы игра закончилась менее, чем за 3 хода (вероятность закончить игру за 3 хода 0,0000002) и более, чем за 64 (вероятность закончить за 64 хода 0,0000003). В среднем, противник выиграл ранее, чем на 15 ходу, стоит забеспокоиться (наверное, подсмотрел ваше расположение), а также, если играете более 50 ходов (наверное, один 1п не выставил).
Ниже распределение для поля $10\times10$, полный флот, расположение случайное, обстрел случайный, кол-во испытаний $10^8$. "Попытки" на графике в смысле "ходы", не "выстрелы".
Изображение

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


04/03/09
902
Sender
Выяснилось, что оптимальных по Нэшу стратегий обстрела больно дофига, бесконечное количество, и поэтому не очень понятно, как их все описывать. Приведу простейший пример. Доска 1х3, на ней 1п кораблик. Оптимальная расстановка, очевидно, - равновероятный выбор одной из трех клеток. Если обстреливать таким образом, что в каждом случае равновероятно выбираем одну из оставшихся клеток, то такая стратегия оптимальна по Нэшу. А можно обстреливать по другому: либо с вероятностью 0.5 стреляем слева направо, либо с вероятностью 0.5 справа налево. Где бы ни был корабль, он убивается так же за два хода в среднем, и эта стратегия обстрела тоже оптимальна по Нэшу. И еще куча других стратегий есть. А всë потому, что при оптимальной расстановке чистых стратегий обстрела (в данном примере 6), дающих наилучший результат, намного больше, чем чистых стратегий расстановки вообще(в примере 3).

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

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



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

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


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

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