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
2916
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
2916
Удалось скомпилить и запустить их программу для подсчёта количества позиций. Для флота по умолчанию на поле 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
2916
Куда уж ближе? :-)

 Профиль  
                  
 
 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
2916
Кстати, в английской и немецкой версиях игры однопалубных кораблей нет вовсе.

 Профиль  
                  
 
 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  След.

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



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

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


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

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