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
17927
Москва
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
2753
Someone в сообщении #1513262 писал(а):
У меня возник вопрос по программе. Она считает все легальные расстановки, или расстановки, совмещаемые поворотами и отражениями всего поля, считаются за одну?

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

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


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

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


14/01/11
2753
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
2753
komand в сообщении #1513300 писал(а):
Что-то многовато. Вроде всего 100 должно быть?

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

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


29/04/13
4965
Богородский
Конечно 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
2753
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
2753
komand, моя заслуга при расчёте позиций минимальна, я всего лишь взял готовую программу, выложенную по ссылке, указанной grizzly в сообщении https://dxdy.ru/post1512752.html#p1512752.

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


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

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

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

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

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

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



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

Сейчас этот форум просматривают: Dmitriy40


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

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