2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6, 7 ... 11  След.
 
 Re: Морской бой. Стратегия через теорию вероятностей
Сообщение20.03.2021, 16:13 


14/01/11
2796
EUgeneUS в сообщении #1510179 писал(а):
UPD: попробуйте выровнять вероятность занятия всех клеток для размещения корабля $2 \times 1$ на поле $3 \times 3$

Для достаточно больших полей это возможно. Например, в упомянутом случае корабля $2 \times 1$ достаточно поля $4 \times 4$.

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


11/12/16
10985
уездный город Н
komand
Рассмотрим установку первого корабля - $4 \times 1$.
Всего вариантов установки $N_4 = 7 \cdot \ 10 \cdot 2 = 140$
Да, Ваш алгоритм обеспечивает, что любая из возможных установок для первого корабля будет выбрана с одинаковой вероятностью.

У Вас какой второй корабль? Тоже 4-х клеточный или 3-х клеточный?
Рассмотрим установку трех-клеточного корабля (он будет вторым или третьим).
Возможных вариантов на пустом поле: $N_3 = 8 \cdot \ 10 \cdot 2 = 160$
Я утверждаю, что при Вашем алгоритме эти варианты будут выбираться с разной вероятностью.
Можете проверить. Вариантов не много, их все можно пронумеровать и посчитать сколько раз каждый из них выбирается после $10^6$ прогонов.
Тоже самое касается и расстановки более мелких кораблей.

Это означает, что варианты расстановки всех кораблей (которых уже огромное количество, несколько меньше, чем $(1 \cdot 140) \cdot (2 \cdot 160) \cdot (3 \cdot 180) \cdot (4 \cdot 100)$) Ваш алгоритм тоже выбирает с разной вероятностью.

-- 20.03.2021, 16:49 --

Sender в сообщении #1510191 писал(а):
Например, в упомянутом случае корабля $2 \times 1$ достаточно поля $4 \times 4$.

Да, в этом случае можно. Но приходится выбирать: либо равновероятны положения корабля, либо равновероятны заполнения клеток.

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


16/03/21
70
Цитата:
Да, в этом случае можно. Но приходится выбирать: либо равновероятны положения корабля, либо равновероятны заполнения клеток..

Я генерил $10^7$ расстановок, среди них нет повторяющихся. Тестировал около сотни раз. В среднем после генерации остается после примерно 17,7 клеток, число всех размещений 10 кораблей на поле $10\times10$ можно примерно оценить, как $C^{18}_{100}$ \approx$10^1^9$. Это достаточно много, чтобы исчерпать 10 млн. попыток. В среднем, вероятность обнаружить в некой клетке некий корабль (1п, 2п, 3п и 4п) одинакова. Но это на больших генерациях, от миллиона. Конечно, и размещение кораблей неравновероятны, и заполнение клеток. Но все это усредняется на сотнях миллионах игр. Я ставил несколько кораблей до генерации, генерил только вертикальные или только горизонтальные корабли, в разном порядке (например, от маленьких к большим), делал перемешивание после генерации и пр. Все это крайне мало влияет на распределение кораблей. Самое главное, не меняет среднее число попыток для потопления такой генерации.
Что действительно влияет - это число оставшихся свободных клеток. Но при случайной генерации оно постоянно, 17.7. А вот если потребовать от программы уплотнять корабли, прижимать друг другу и бортам, тогда картина игра существенно меняется.
У меня нет аналитического решения задачи, у меня есть решение вероятностное с какой-то точностью. Но спасибо что вы обратили внимание на распределение кораблей, сейчас я его как раз изучаю и вношу поправки в статью.

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


11/12/16
10985
уездный город Н
komand
Когда Вы что-то считаете методом Монте-Карло (а Вы делаете именно это).
Вам критически важно, чтобы каждый вариант был равновероятен. Или делать поправки на неравномерную вероятность.
А Ваш алгоритм генерации случайного поля этого не обеспечивает.

Вот иллюстрация. Поле $10 \times 10$, два корабля $4 \times 1$ и $1 \times 1$. Легко (но нудно) посчитать, что всего вариантов расстановок $N = 11760$. То есть с вероятностью $\frac{1}{11760}$ должна генерироваться каждая расстановка.

а) Посчитаем, с какой вероятностью будет генерироваться расстановка: большой корабль в левом верхнем углу горизонтально, малый в правом нижнем углу. По вашему алгоритму вероятность будет $p = \frac{1}{140} \frac{1}{90} = \frac{1}{12600}$. На 7% меньше

б) Посчитаем, с какой вероятностью будет генерироваться расстановка: большой корабль в точках $b2...b5$, малый в правом нижнем углу. По вашему алгоритму вероятность будет $p = \frac{1}{140} \frac{1}{82} = \frac{1}{11480}$. На 2.4 % больше

Различия вроде бы небольшие, но они есть. И никак не оценивается,
а) какие перекосы возникают при полной расстановки 10 кораблей.
б) как это влияет это на окончательные выводы.

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


16/03/21
70
EUgeneUS в сообщении #1510218 писал(а):
Различия вроде бы небольшие, но они есть. И никак не оценивается,
а) какие перекосы возникают при полной расстановки 10 кораблей.
б) как это влияет это на окончательные выводы.
В статье я сказал, что неравномерность есть и она влияет на результат. На третий знак после запятой.

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


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

Хорошо.
А как это оценивалось? (В примере влияние есть на второй значащий знак).

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


01/09/13
3301
komand в сообщении #1510180 писал(а):
Случайно выбирается любое из 4 направлений: вверх, вниз, влево, вправо

неверно

-- 20.03.2021, 20:19 --

komand в сообщении #1510211 писал(а):
Я генерил 10^7 расстановок, среди них нет повторяющихся.

Если число расстановок на 10 порядков больше, то это ни о чём.

 Профиль  
                  
 
 Posted automatically
Сообщение20.03.2021, 21:05 
Заслуженный участник
Аватара пользователя


09/05/12
25190
Кронштадт
 i  Тема перемещена из форума «Математика (общие вопросы)» в форум «Карантин»
Поскольку само это все же не проходит:

- наберите правильно числа со степенями и умножения (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы) во всей теме.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

 Профиль  
                  
 
 Posted automatically
Сообщение22.03.2021, 20:15 
Заслуженный участник
Аватара пользователя


09/05/12
25190
Кронштадт
 i  Тема перемещена из форума «Карантин» в форум «Математика (общие вопросы)»

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


16/03/21
70
Сделал паузу, чтобы исправить формулы в теме и разобраться с распределением 2п корабля на поле $3\times3$
Для начала анекдот в тему.
Приходит аспирант-математик (А) к шефу (Ш).
А: Я решил крупную задачу для своей диссертации (подает решение).
Ш: (смотрит решение) Так, так... Формула сложная, давайте проверим ее на простом примере? Ага, видите, ошибка? Исправляйте.
А. приходит через год.
А: Шеф, я целый год искал ошибку и нашел.
Ш: И где она была?
А: В вашем примере.

О чем это я. Ув. EUgeneUS написал:
Цитата:
1. За четыре удара точно попадаем. В среднем $2.5$
2. Дальше добиваем. Где бы и когда бы не ранили, остается ровно три варианта на добитие. С учетом "призового удара", это $0, 1, 2$ хода. В среднем один ход.3. $2.5 + 1 = 3.5$

Все верно... но не совсем. Из-за больших кораблей для такого поля возникают "краевые эффекты". А именно, корабль может иметь от 0.5 до 1.5 попытки на добитие (с учетом премии), см. рис.
Изображение
Однако из-за особенностей сетки
Изображение
всегда получалось попадание в клетку, имеющую "2 степени свободы", т.е. 1 попытку на добитие.

Сейчас я проверяю программу на таких положениях, для которых можно рассчитать вероятность теоретически. Как отлажу, вернусь к дискусии.

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


11/12/16
10985
уездный город Н
komand
Что у Вас посчитано на первой картинке, мне не очень понятно.

А дальше у Вас довольно странные рассуждения. Правильно так:
а) До начала обстрела есть 12 различных положений корабля, все они равновероятны (так расставляли).
б) После попадания первый раз (если стреляем "по сетке") у нас всегда остаётся три варианта расстановки корабля. И они всё так же равновероятны. Поэтому корабль убивается после ранения в среднем за 2 удара. С учетом призового удара - в среднем за 1 ход.

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


16/03/21
70
На первой картинке показано неравное расположение кораблей. Если попадание будет в середину, на добитие потребуется 1.5 попытки, а если в угол, всего 0.5. И таких положений разное кол-во: 4 по 0,5, 4 по 1 и 1 по 1,5. Все из-за "краевых эффектов". На поле $10\times10$ таких эффектов будет меньше. На бесконечной доске бортовые и угловые расположения вообще можно не учитывать. К чему эти рассуждения? К тому, что проверять некое утверждение с помощью простых примеров надо осторожно.
Если случайно (без сетки) искать один 2п на $3\times3$, то получается в среднем 3.944 (с добитием) или 3.333 (без добития).

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


16/03/21
70
После правки, тестирования программы выводы получились довольно банальные. Немного "причешу" статью и опубликую, как есть, без рецензирования.

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


16/03/21
70
Кстати, верно ли я оцениваю число возможных начальных расстановок кораблей, как $C_{100}^{10}\approx1,73\times10^{13}$ ? Имеется ввиду поле $10\times10$, 10 кораблей. Поскольку не все размещения легальны (корабли не могут каcаться друг друга), то это верхняя оценка. Но даже такая маленькая что-то. Где-то ошибку допустил?
А, понял, ведь каждый корабль кроме размещения еще может и поворачиваться.

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


01/09/13
3301
komand в сообщении #1510979 писал(а):
Где-то ошибку допустил?

Две ориентации.

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

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



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

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


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

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