2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 7, 8, 9, 10, 11  След.
 
 Re: Морской бой. Стратегия через теорию вероятностей
Сообщение07.04.2021, 04:07 
Аватара пользователя


06/04/21
138
Уточню свою мысль:
Изображение
Вторая позиция является классической, при игре с дополнительным выстрелом за попадание. Последний 1-катер может расположиться на 19 зелёных полях.
При ваших правилах выгодно пожертвовать всем флотом, случайно выставив на 1-й позиции 1-катер на любое из 48 клеток.

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


16/03/21
70
tonven в сообщении #1513190 писал(а):
Вторая позиция является классической, при игре с дополнительным выстрелом за попадание. Последний 1-катер может расположиться на 19 зелёных полях.
"Классической" является указанная вами позиция без расстановки 1п (останется поле 10x6 клеток). Однопалубники не стоит так плотно размещать, ибо:
"Можно ли улучшить этот результат? Расположим 4 корабля в углу (90,92,70,72) как на рис. 13. Случайный компьютерный алгоритм: 38,2 ходов. Другие подобные варианты с 44 свободными клетками дают примерно тоже самое. Выигрыш ~2 хода. Против компьютерного случайного алгоритма смысл есть, против человека наоборот: после обстрела углов поля 10x6 он выиграет сразу или (если 4-й корабль вы расположите случайно) получит существенное преимущество ~ 30% ходов. Потому что на оставшихся 48 клетках ему придется найти только 1 корабль, а для этого нужно ~24,5 ходов. Так же малоперспективны попытки расположить 1 или 2-х корабля по углам, остальные 1–2 случайно (против человека). См. график. Для одного корабля нужно 30,5 ходов, как и в теории. Для поражения 4 кораблей нужно меньше ходов, чем для 3-х. А для поиска 6 — столько же, что и для одного"
Если вы раскидываете четыре 1п по полю 10x6, противнику нужно ~35,6 ходов для их уничтожения. А если он обнаружил один из однопалубников или несколько сразу (потому что вы прижали их к бортам или к "упаковке"), шансы на выигрыш у него резко возрастают. Зависимость кол-ва ходов от кол-ва 1п кораблей нелинейная.
График:
Изображение

Сегодня вечером опубликую всю статью, вроде готова.

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


06/04/21
138
komand в сообщении #1513224 писал(а):
Однопалубники не стоит так плотно размещать

На доске $10\times 10$ приходится учитывать границы, когда "упакованный" 1п освобождает остальным "бродягам" больше клеток для размещения.
Но переходя к большим размерам, можно смоделировать в рамках теорвера:
Пусть имеется $N$ свободных клеток. Перемешиваем их. И начинаем стрельбу слева. Тогда 1 корабль гибнет в среднем через $N/2$, 2 корабля через $2N/3$, ..., $k $ кораблей через $kN/(k+1)$ ходов. Ваш тезис верен.

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


23/07/05
17973
Москва
Sender в сообщении #1512807 писал(а):
добавил конфигурацию
Используется синтаксис Haskell
russian :: T
russian = fromList [(4,1), (3,2), (2,3), (1,4)]

и пересчитал для неё. Получилось $29688735661308480$. Правда, там однопалубные корабли могут располагаться вертикально и горизонтально, но это легко решается делением числа позиций на $16$. Таким образом, итоговое число позиций $1855545978831780\approx 1.85\cdot 10^{15}.$
У меня возник вопрос по программе. Она считает все легальные расстановки, или расстановки, совмещаемые поворотами и отражениями всего поля, считаются за одну?

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


16/03/21
70
Someone в сообщении #1513262 писал(а):
У меня возник вопрос по программе. Она считает все легальные расстановки, или расстановки, совмещаемые поворотами и отражениями всего поля, считаются за одну?
У меня ощущение, что программа учитывает симметрию, хотя как, не знаю. Что-то уж мало получается, раньше оценка была в 8 раз больше, $10^{16}$. Похоже, что "8" - это как раз учет симметрии.
И еще. Если мои расчетные величины умножать на 2,45, получается их числа. С точностью до 3-го знака. Почему 2,45 - не знаю.

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


14/01/11
2916
Someone в сообщении #1513262 писал(а):
У меня возник вопрос по программе. Она считает все легальные расстановки, или расстановки, совмещаемые поворотами и отражениями всего поля, считаются за одну?

Насколько я могу судить, симметрии не учитываются, т.к. для одного двухпалубного корабля в программе получается 180 вариантов размещения.(а для однопалубного - 200). Я, впрочем, не ручаюсь за отсутствие ошибок в самой программе...

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


23/07/05
17973
Москва
Sender в сообщении #1513276 писал(а):
а для однопалубного - 20
$200$?

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


14/01/11
2916
Someone в сообщении #1513285 писал(а):
$200$?

Да, исправил уже, пардон. :facepalm:

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


16/03/21
70
Sender в сообщении #1513276 писал(а):
для однопалубного - 200
Что-то многовато. Вроде всего 100 должно быть?

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


14/01/11
2916
komand в сообщении #1513300 писал(а):
Что-то многовато. Вроде всего 100 должно быть?

Sender в сообщении #1512807 писал(а):
Правда, там однопалубные корабли могут располагаться вертикально и горизонтально

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


29/04/13
7128
Богородский
Конечно 100.

1п: 100 — 15
2п: 180 — 25
3п: 160 — 20
4п: 140 — 20
5п: 120 — 15

Справа количество уникальных, которое не более чем в 8 раз меньше общего.

-- 07.04.2021, 18:54 --

Sender в сообщении #1512807 писал(а):
Правда, там однопалубные корабли могут располагаться вертикально и горизонтально,

Ага. А ещё их можно на попа поставить :-)

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


14/01/11
2916
Yadryara в сообщении #1513313 писал(а):
Ага. А ещё их можно на попа поставить :-)

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

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


16/03/21
70
Sender в сообщении #1513312 писал(а):
Правда, там однопалубные корабли могут располагаться вертикально и горизонтально
Круто! Я хочу посмотреть на это чудо )

Перекодирую статью из DOC в PDF. Скоро будет.

-- 07.04.2021, 19:33 --

Готово. Статья тут.
10 листов, 32 тыс. знаков, 18 иллюстраций.

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


14/01/11
2916
komand, моя заслуга при расчёте позиций минимальна, я всего лишь взял готовую программу, выложенную по ссылке, указанной grizzly в сообщении https://dxdy.ru/post1512752.html#p1512752.

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


11/12/16
13195
уездный город Н
1.
Цитата:
Ход — ваши действия до передачи хода противнику

Рекурсия не нужна.

2. Не очень понятно, как устроен "случайный обстрел".
После попадания ("ранил") следующий выстрел как делается? Тоже случайно или по какой-то методе добиваем? Что такое "свободная клетка" (этого нет в терминах)?

3. И ещё такой тонкий момент. Вы же минимизируете мат ожидание количества ходов?
Тогда это не гарантирует максимизации вероятности выигрыша партии.
Например, может случиться так, что мат. ожидания количества ходов до выигрыша у разных игроков одинаковые, но один игрок выигрывает чаще.

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

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



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

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


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

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