2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 5, 6, 7, 8, 9, 10, 11  След.
 
 Re: Морской бой. Стратегия через теорию вероятностей
Сообщение04.04.2021, 09:38 
Заслуженный участник
Аватара пользователя


09/09/14
6328
komand в сообщении #1512761 писал(а):
Как они вычисляют число позиций, не очень понял. Но точно не для 10 кораблей на поле $10\times10$
Они считают для любого количества кораблей от 0 до 10 на поле $10\times10$. И интуиция мне подсказывает, что они считают абсолютно точно. Только набор кораблей у них не такой. Набор из всех 10 кораблей выглядит там вот так: 4 корабля по 2 клетки, 3 по 3, 2 по 4 и 1 по 5 (об этом указано в шапке таблицы). Очевидно, что количество вариантов для такого набора намного меньше. Но 6 порядков? Теперь я склонен сомневаться в том, что Ваша программа считает правильно.

Попытайтесь посчитать своей программой либо их полную конфигурацию и проверить, получится ли 26509655816984 вариантов (хотя я сомневаюь, что не оптимизированный под всякие симметрии алгоритм сможет посчитать это за разумное время), либо какую-нибудь часть их конфигурации, например 1 корабль по 4 клетки, 2 по 3 и 3 по 2. Должно получиться в точности 55828223540 (это уже должна быть посильная по вычислительной сложности задача, а если нет, то можно взять набор кораблей ещё чуть попроще).

Я посмотрел за пару минут Вашу критику их статьи и потратил примерно такое же время на беглый просмотр самой статьи. У меня не сложилось впечатления, что Вы поняли статью настолько, чтобы иметь моральное право её так сильно критиковать :)

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


16/03/21
70
grizzly в сообщении #1512773 писал(а):
Я посмотрел за пару минут Вашу критику их статьи и потратил примерно такое же время на беглый просмотр самой статьи. У меня не сложилось впечатления, что Вы поняли статью настолько, чтобы иметь моральное право её так сильно критиковать :)
У них статья имеет заголовок: "Оптимальная стратегия для игры в морской бой". А где она, эта "оптимальная стратегия"? Где перебор стратегий, доказательство, что он полон, выбор лучшей и доказательство, что она лучшая? Вместо этого идет разбор среднего кол-ва ходов в игре (доя поля $10\times10$). Какая польза от этого игроку? Т.е. я согласен, что статья полезная. У меня претензии к названию.
grizzly в сообщении #1512773 писал(а):
Попытайтесь посчитать своей программой либо их полную конфигурацию и проверить, получится ли 26509655816984 вариантов (хотя я сомневаюь, что не оптимизированный под всякие симметрии алгоритм сможет посчитать это за разумное время), либо какую-нибудь часть их конфигурации, например 1 корабль по 4 клетки, 2 по 3 и 3 по 2. Должно получиться в точности 55828223540 (это уже должна быть посильная по вычислительной сложности задача, а если нет, то можно взять набор кораблей ещё чуть попроще).
Я пока не понимаю, как они считают конфигурации, а без этого нет смысла проверять: при несовпадении непонятно, чей алгоритм неверен.
grizzly в сообщении #1512773 писал(а):
Но 6 порядков? Теперь я склонен сомневаться в том, что Ваша программа считает правильно.
Так она считает по-другому: просто все конфигурации, в т.ч. за пределами поля. Поэтому их гораздо больше, чем в статье. Но зато и модель гораздо проще.
Я особо не защищаю свою программу, в моей статье можно без этой вообще можно обойтись, к оптимальной стратегии она не имеет отношения.

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


01/09/13
4318
komand в сообщении #1512790 писал(а):
У меня претензии к названию.

А что именно Вы называете "оптимальной стратегией", и что Вы называете "стратегией"?...

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


16/03/21
70
Geen в сообщении #1512791 писал(а):
komand в сообщении #1512790 писал(а):
У меня претензии к названию.

А что именно Вы называете "оптимальной стратегией", и что Вы называете "стратегией"?...
Есть игра, в ней есть стратегия: как победить противника. Оптимальная стратегия - как победить при лучших ответах противника. Если более конкретно к игре "морской бой", то понятное объяснение, как оптимально расставлять свои корабли и как обстреливать чужие с количественными оценками.
В приведенной статье я не увидел ничего о том, как же мне выиграть в этой игре.

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


14/01/11
2918
komand в сообщении #1512790 писал(а):
Я пока не понимаю, как они считают конфигурации

Вроде из этого не делается тайны. По ссылке говорится:
Цитата:
The table assumes that ships cannot be placed adjacent to one another, though not all versions of the game use this rule.

И двухпалубный корабль на поле 10x10 у них размещается 180 способами, мне кажется, этого вполне достаточно, чтобы понять принцип.

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


16/03/21
70
Sender в сообщении #1512802 писал(а):
И двухпалубный корабль на поле 10x10 у них размещается 180 способами, мне кажется, этого вполне достаточно, чтобы понять принцип.
Для одного корабля можно посчитать аналитически: $N(N-K+1)\times2$, где N - сторона поля, K - размер корабля. Для поля $10\times10$ получаем $10\times(10-2+1)\times2=180$. Сложность в том, как они высчитывают касания множества кораблей.
Но в данный момент я посчитал свою программу для простейших случаев (поля от $3\times3$ до $10\times10$ с одним 2п и 3п кораблем), она выдает неверные результаты. Тем более она врет на полном флоте. Так что я, наверное, признаю поражение в высчитывании всех конфигураций и вернусь к оценкам $10^{16}$ для полного флота.

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


09/09/14
6328
Посмотрел статью. Оптимальная стратегия там дана в виде Алгоритма 2, а не в виде "человеческого" описания. Она идеальна, но бесполезна для большой сетки, поскольку работает слишком медленно. Для неё дана оценка снизу, которая говорит, что в среднем потребуется не меньше чем 30,8 выстрелов для победы на случайном размещении их варианта набора кораблей (весьма упрощённого -- всего 5 кораблей, без одиночных).

Далее на Рисунке 10 приводится простая "человеческая" стратегия (для такого же набора кораблей), которая даёт не более чем 58,7 выстрелов (в среднем). Примерно такой стратегии и придерживался бы нормальный игрок, наверное (может, не точно такой, но примерно с такой же эффективностью). Потом эта стратегия чуть улучшается (ещё на пару выстрелов). Предполагается, что это ещё не предел "человеческих" стратегий.

Всё это вряд ли применимо для игры с одиночными кораблями. Но в той постановке вопроса игра с одиночными кораблями вряд ли вообще интересна (по понятным причинам).

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


14/01/11
2918
Удалось скомпилить и запустить их программу для подсчёта количества позиций. Для флота по умолчанию на поле 10x10 (конфигурация german) получилось значение как в статье(последняя строка таблицы): $26509655816984$.
По аналогии с
Используется синтаксис Haskell
{- |
The main configuration given
in <https://de.wikipedia.org/wiki/Schiffe_versenken>.
-}

german :: T
german = fromList [(5,1), (4,2), (3,3), (2,4)]

{- |
The main configuration given
in <https://en.wikipedia.org/wiki/Battleship_(game)>.
-}

english :: T
english = fromList [(2,1), (3,2), (4,1), (5,1)]

добавил конфигурацию
Используется синтаксис Haskell
russian :: T
russian = fromList [(4,1), (3,2), (2,3), (1,4)]

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

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


16/03/21
70
Sender в сообщении #1512807 писал(а):
и пересчитал для неё. Получилось $29688735661308480$. Правда, там однопалубные корабли могут располагаться вертикально и горизонтально, но это легко решается делением числа позиций на $16$. Таким образом, итоговое число позиций $1855545978831780\approx 1.85\cdot 10^{15}.$
Ну и буду пользоваться этой оценкой. Хотя у меня было ощущение, что число всех конфигураций флота на поле $10\times10$ ближе к $10^{16}$

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


14/01/11
2918
Куда уж ближе? :-)

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


09/09/14
6328
Вот что могло бы быть действительно интересно и полезно с моей точки зрения в рамках данной темы:

Найти (предложенным автором темы методом) какую-то более эффективную "человеческую" стратегию (для их же набора из 5 кораблей) и на всех вариантах (около 2 млрд. конфигураций) прямым пересчётом доказать, что эта найденная стратегия действительно лучше опубликованной в статье верхней оценки. Если бы такое удалось, это был бы не просто вычислительный шаг вперёд, а как раз методологический (найти метод нахождения метода). Получится ли что-то из этого? Не знаю, но уверен, что усилия в этом направлении были бы полезны и (в случае хоть какого-то успеха) достойны публикации.

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

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


16/03/21
70
grizzly в сообщении #1512810 писал(а):
К сожалению, наличие одиночных кораблей в наборе практически убивают саму постановку задачи, имхо.
Именно. Более того, их наличие практически сравнивает все стратегии - в этом основной вывод моей статьи. А все компьютерные оптимизированые стратегии мало отличаются по эффективности от простых "сеток", а самое главное, неприменимы человеком.
Sender в сообщении #1512809 писал(а):
Куда уж ближе? :-)
Все-таки разница на порядок. Вы посчитали для конфигурации 1п - 4, 2п - 3, 3п - 2, 1п - 1?

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


14/01/11
2918
Кстати, в английской и немецкой версиях игры однопалубных кораблей нет вовсе.

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


16/03/21
70
Sender в сообщении #1512812 писал(а):
Кстати, в английской и немецкой версиях игры однопалубных кораблей нет вовсе.
Что резко увеличивает значимость любой стратегии поиска кораблей от больших к малым. Для 1п вообще нет никакой стратегии.

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

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


09/09/14
6328
Sender в сообщении #1512812 писал(а):
Кстати, в английской и немецкой версиях игры однопалубных кораблей нет вовсе.
Так и я о том же. И задача для этих версий куда более содержательна (а сама игра между двумя людьми должна быть намного интереснее -- стратегически).

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

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



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

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


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

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