2014 dxdy logo

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

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




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


11/12/16
13195
уездный город Н
12d3
У меня так же.
Удивительный момент: центр тоже довольно таки выделенная точка. Вероятность, что там есть корабль равна $\frac{1}{3}$.
Но если рассмотреть отдельно стратегии:
а) бьем по серединам сторон, как нащупали корабль, добиваем
б) бьем сразу в центр, потом по серединам сторон, как нашли корабль - добиваем
то ожидаемое количество ходов окажется одинаковым.

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


16/03/21
70
12d3 в сообщении #1510017 писал(а):
У меня получилось проанализировать все стратегии для доски 3 на 3. Оптимальная стратегия расстановки - равновероятно выбрать любую из 12 возможных позиций. Тогда кораблик убивается в среднем за 4.5 хода, первым выстрелом нужно пулять куда угодно, кроме углов.
Забавно, что для трехпалубного корабля тоже требуется 4.5 выстрела, и оптимальная расстановка такая же - равновероятно выбрать любую из возможных позиций.

Обсчет показал ($10^9$ попыток, точность на 4 знаке после запятой при P=0.999), что при случайном обстреле в среднем требуется 3.5 попытки. Если же пользоваться сеткой (см. ниже, точки - обстрел в любом порядке) , то обсчет показал 2.5 попытки. В теории столько же: мин. попыток 1, макс. попыток 4, в среднем $(1+4)/2=2.5$
Для трехпалубного корабля требуется не более 3 выстрелов, в среднем 2. Координаты сетки любая диагональ, например, 00,11,22
Да, не забывайте о "премиальном" выстреле: если вы попали в корабль, следующий выстрел вне очереди. То есть, к примеру, такая последовательность "мимо, ранил, ранил убил, мимо" - это не 4 выстрела, а всего 2. В реальной игре так и есть: если, к примеру, вы точно знаете расположение всех кораблей противника, то можете потопить его флот с единственного выстрела, не дав ему выстрелить в ответ. То есть мы с вами считаем одинаково, но я не добавляю "премиальные" попытки, а вы добавляете. Чаще всего играют с "премией", поэтому мой подсчет ближе к реальной игре.
Изображение

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


11/12/16
13195
уездный город Н
komand в сообщении #1510034 писал(а):
В теории столько же: мин. попыток 1, макс. попыток 4, в среднем (1+4)/2=2.5

Интересно Вы считаете... В среднем $2.5$ хода - это чтобы попасть первый раз, то есть ранить. Дальше ещё убить надо.
Если призовой ход после попаданием за ход не считаем, то ещё в среднем 1 один ход. Итого $3.5$

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


16/03/21
70
EUgeneUS в сообщении #1510037 писал(а):
komand в сообщении #1510034 писал(а):
В теории столько же: мин. попыток 1, макс. попыток 4, в среднем (1+4)/2=2.5

Интересно Вы считаете... В среднем $2.5$ хода - это чтобы попасть первый раз, то есть ранить. Дальше ещё убить надо.
Если призовой ход после попаданием за ход не считаем, то ещё в среднем 1 один ход. Итого $3.5$
Не забываем, что премиальный выстрел не учитывается. Так что все же 2,5, распределение для $10^7$ попыток простое: с первой по 4 попытку вероятность 0,25, с пятой 0. Это с добиванием и премиальным выстрелом.

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


11/12/16
13195
уездный город Н
komand в сообщении #1510041 писал(а):
не забываем,

Не забываем

komand в сообщении #1510041 писал(а):
что после каждого попадания сокращается кол-во клеток, куда может добиваться корабль.

В данном случае (бьем по серединам сторон поля, как попали - добиваем) не сокращается.

komand в сообщении #1510041 писал(а):
Так что все же 2.5, распределение для 10^7 попыток см. выше.

Вот расчет:

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

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


16/03/21
70
EUgeneUS в сообщении #1510047 писал(а):
1. За четыре удара точно попадаем. В среднем $2.5$
2. Дальше добиваем. Где бы и когда бы не ранили, остается ровно три варианта на добитие. С учетом "призового удара", это $0, 1, 2$ хода. В среднем один ход.
3. $2.5 + 1 = 3.5$

Да, где-то в компьютерном обсчете ошибка. Найду, напишу.

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


11/12/16
13195
уездный город Н
Кстати, генерация случайных расстановок так, чтобы каждая возможная расстановка имела одинаковую вероятность - задача весьма нетривиальная.
Под катом иллюстрация

(Оффтоп)

0. Для простоты и определенности: соединение углами кораблей запрещено.
1. Рассмотрим поле $5 \times 5$, на котором нужно разместить один корабль $3 \times 1$ и один $1 \times 1$
2. Без учета второго корабля:
а) корабль $3 \times 1$ можно разместить 30-ю способами.
б) корабль $1 \times 1$ можно разместить 25-ю способами.

3. Разместим случайно (с равномерной вероятностью по всем вариантам) корабль $3 \times 1$
4. А на оставшихся разрешенных клетках разместим корабль $1 \times 1$, считая вероятность выбора каждой оставшейся клетки одинаковой.

Тогда
а) угловая клетка будет запретной для размещения корабля $1 \times 1$ для восьми вариантов размещения корабля $3 \times 1$.
б) а центральная клетка будет запретной для 18 вариантов размещения корабля $3 \times 1$ (то есть в более чем половине случаев).

Таким образом, размещая первым корабль $3 \times 1$ и выбирая каждый вариант с одинаковой вероятность, мы не можем обеспечить, чтобы корабль $1 \times 1$ занимал любую клетку с одинаковой вероятностью.
Автоматически верно обратное: размещая первым корабль $1 \times 1$ в любой клетке с одинаковой вероятностью, мы приходим к тому, что невозможно разместить корабль $3 \times 1$ с одинаковой вероятностью по всем 30-и вариантам размещения.

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


16/03/21
70
EUgeneUS в сообщении #1510069 писал(а):
Кстати, генерация случайных расстановок так, чтобы каждая возможная расстановка имела одинаковую вероятность - задача весьма нетривиальная.
Анализ показал, что начиная с $10^6$ любая клетка занимается с равной вероятностью (поле 10x10, 10 кораблей). Чем меньше поле и чем больше кораблей, тем больше будет несостыковок. У вас один корабль занимает более половины поля, конечно будут сложности. Для простоты иллюстрации попробуйте на поле 3x3 разместить два 2п корабля. Очевидно, центральная клетка имеет нулевую вероятность быть занятой.

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


16/03/21
70
Нашел ошибку: переставил две строчки при переделке под 3x3 поле. Всего один клик, а какой эффект ).
Итак, ловим один 2п на поле $3\times3$. По $10^8$ позициям число попыток $\approx3.49998±0,00001.$ Распределение:
Изображение

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


11/12/16
13195
уездный город Н
komand в сообщении #1510080 писал(а):
Анализ показал, что начиная с 10^6 любая клетка занимается с равной вероятностью (поле 10x10, 10 кораблей).

Я немного о другом. Представим, что у Вас есть поле $10 \times 10$, на котором нужно разместить два квадратных корабля: $2 \times 2$ и $1 \times 1$.
Как Вы будете строить "случайную позицию?"

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


14/01/11
2916
EUgeneUS в сообщении #1510177 писал(а):
Как Вы будете строить "случайную позицию?"

Одна из возможных стратегий уже звучала: выровнять вероятность занятия для всех клеток.

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


11/12/16
13195
уездный город Н
Sender в сообщении #1510178 писал(а):
Одна из возможных стратегий уже звучала: выровнять вероятность занятия для всех клеток.


Как? По шагам.

-- 20.03.2021, 15:10 --

UPD: попробуйте выровнять вероятность занятия всех клеток для размещения корабля $2 \times 1$ на поле $3 \times 3$

(hint)

Это невозможно

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


16/03/21
70
EUgeneUS в сообщении #1510177 писал(а):
Я немного о другом. Представим, что у Вас есть поле $10 \times 10$, на котором нужно разместить два квадратных корабля: $2 \times 2$ и $1 \times 1$.
Как Вы будете строить "случайную позицию?"
Общий алгоритм такой:
1. Корабли расставляем от большего к меньшему
2. Случайно выбирается любая координата
3. Случайно выбирается любое из 4 направлений: вверх, вниз, влево, вправо
4. В этом направлении пытаемся вписать корабль. Если он не вмещается, переходим к 2.
На достаточно большом поле и при небольшом кол-ве кораблей алгоритм обеспечивает случайное занятие каждой клетки, при этом каждый корабль с равной вероятностью может появится в любой клетке. Для базовой игры распределение хорошее.
Однако, если поле маленькое, а кораблей много, или они слишком большие, алгоритм дает сбой. Простейший вариант этого сбоя я уже указывал: на поле 3x3 нельзя разместить два 2п корабля так, чтобы центральная клетка была занята.

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


11/12/16
13195
уездный город Н
komand в сообщении #1510180 писал(а):
3. Случайно выбирается любое из 4 направлений: вверх, вниз, влево, вправо
4. В этом направлении пытаемся вписать корабль. Если он не вмещается, переходим к 2.

В этом месте Вы пытаетесь вписать корабль целиком?

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


16/03/21
70
EUgeneUS в сообщении #1510181 писал(а):
komand в сообщении #1510180 писал(а):
3. Случайно выбирается любое из 4 направлений: вверх, вниз, влево, вправо
4. В этом направлении пытаемся вписать корабль. Если он не вмещается, переходим к 2.

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

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

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



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

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


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

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