Морской бой. Стратегия через теорию вероятностей

[komand]

Мы с ув. Someone обсуждали в личном чате варианты подсчета общего кол-ва позиций в игре, как всех, так и по правилам. Выношу на общее обсуждение.

Пусть оценка всех возможных позиций сверху будет X. Посчитать ее несложно. Пусть корабли выходят за пределы поля, пересекаются, касаются и пр. Главное, чтобы начальная координата принадлежала полю $10\times10$
Тогда X, число всех возможных размещений 10 кораблей можно посчитать как:

С_{100}^{4}\times C_{100}^{3}\times C_{100}^{2}\times C_{100}^{1}\times4^6$ = 1,28557\times10^{21}$

Только меня $4^6$ смущает. Хотя не надо забывать, что корабль может иметь 4 ориентации, если ориентироваться на одну координату при его создании.

Оценку снизу комбинаторикой найти крайне сложно, если вообще возможно. Поэтому прибегаем к методу Монте-Карло: генерим позиции, легко вычисляемые теорией, а затем компьютером ищем среди них легальные. Доля "легальных позиций" деленная на "все позиции", вычисленное программой, пусть будет К.
$X\times K$ и будет искомой величиной "всех легальных позиций в игре". И чем точнее наш коэффициент К (и если он сходится и распределение нормальное), тем точнее будет оценка.

Я написал программу, которая генерирует начальные позиции кораблей, а потом вычисляет легальные, т.е. размещенные по правилам. На $10^9$ позиций (сейчас запустил на $10^{10}$) выходит только $7,76\times10^{-6} $разрешенных.
То есть генерация самая простая, как только возможно: в любое место, даже не проверяется, попала ли генерированная координата в место, занятое другим кораблем (это проверяется потом). Зато и вычисление в теории всех позиция упрощается, потому что не нужно учитывать клетки, занятые уже и соприкосновения. Ваш алгоритм интересен, но сложен, поэтому возможна ошибка при реализации.

Самое важно, я понял, что нет необходимости генерировать все поле. Какая разница, одна ошибка будет на нем или много? Все равно брак. Достаточно поле генерировать до ПЕРВОЙ ошибки. Это сильно (на пару порядков) увеличило скорость генерации.
1. Генерируем случайную координату. Координаты сначала по вертикали сверху вниз от 0 до 9, потом по горизонтали слева направо от 0 до 9. Сначала "y" в промежутке [0,9], затем "x" [0,9].
2. Генерируем случайно направление корабля [1,4] - вверх, вниз, влево, вправо.
3. Пробуем "вписать" корабль в поле. Если получается (не выходит за пределы), далее. Иначе тут же прерываемся.
4. Если корабль вписался, проверяем его на контакт с уже созданными кораблями. Если не получается, прерываемся. Иначе повторяем (1) до создания полного флота.
5. Когда генерация заканчивается, определяем долю "легальных" позиций, сгенерированных по правилам, как "число позиций по правилам" деленное на "число всех позиций".
Таким образом, при генерации корабли размещаются случайно и независимо. Могут не просто касаться друг друга, а создаваться по тем же координатам, что и уже существующие.

Теперь что получается.
Всего сгенерировано:$10^8$ правильных:776 доля:0.00000776
Всего сгенерировано:$10^9$ правильных:7540 доля:0,00000754
Всего сгенерировано:$10^{10}$ правильных:76139 доля:0.0000076139
Сейчас генерю 10^{11} позиций, это на сутки. Думаю, выборка немалая, если считать, что всего позиций ~$10^{21}$, а легальных ~$10^{16}$

ГПСЧ - "вихрь Мерсенна", у него безумный период и доказанная равномерность распределения. Начальная затравка - число миллисекунд с 1970 года плюс некоторый случайный "разогрев".

Мне важно понять, сколько легальных позиций в игре, чтобы оценить, насколько мои типичные выборки ($10^7$) представительны.

Цитата:

Ничего сказать не могу по этому поводу, кроме того, что доля "отходов" существенно зависит от способа генерации. Более того, оценку сверху можно уменьшить ещё почти в $7$ раз, если учесть, что левая верхняя клетка, скажем, двухпалубного корабля может занимать только одну из $81$ позиций, трёхпалубного — одну из $64$, четырёхпалубного — одну из $49$ (и каждый из этих $6$ кораблей имеет $2$ ориентации): число возможных расстановок заведомо не превосходит

$$\frac{100\cdot 99\cdot 98\cdot 97}{4!}\cdot\frac{81\cdot 80\cdot 79\cdot 2^3}{3!}\cdot\frac{64\cdot 63\cdot 2^2}{2!}\cdot\frac{49\cdot 2}{1!}=2\,115\,140\,355\,643\,392\,000\approx 2{,}12\cdot 10^{18}.$$

Это число можно ещё уменьшить, но рассуждения становятся громоздкими, а результат вряд ли будет впечатляющим.

Приведённой здесь формуле соответствовал бы такой алгоритм генерации.
1) Выбираем $4$ попарно различные клетки из полного квадрата $10\times 10$ для однопалубных кораблей.
2) Выбираем $3$ попарно различные клетки из левого верхнего квадрата $9\times 9$ для левых верхних клеток двухпалубных кораблей, не обращая внимания на $4$ ранее выбранные клетки. Проверяем совпадения клеток ($4\cdot 3=12$ пар). Если они есть, засчитываем попытку как неудачную и переходим к следующей попытке (к пункту 1).
3) Выбираем $2$ различные клетки из левого верхнего квадрата $8\times 8$ для трёхпалубных кораблей, не обращая внимания на $7$ ранее выбранных клеток. Проверяем совпадения клеток ($7\cdot 2=14$ пар). Если они есть, засчитываем попытку как неудачную и переходим к следующей попытке (к пункту 1).
4) Выбираем $1$ клетку из квадрата $7\times 7$, не обращая внимания на $9$ ранее выбранных клеток. Проверяем совпадения клеток ($9\cdot 1=9$ пар). Если они есть, засчитываем попытку как неудачную и переходим к следующей попытке (к пункту 1).
5) Выбираем ориентации для $6$ последних кораблей (возможны $2$ ориентации каждого корабля: направо или вниз от выбранной клетки).
6) Проверяем построенную расстановку на соответствие правилам. Если какие-нибудь корабли пересекаются или соприкасаются, засчитываем попытку как неудачную и переходим к следующей попытке (к пункту 1). Вылезть за границу поля при таком способе расстановок корабли не могут.
7) Засчитываем попытку как удачную, прибавив $1$ к соответствующему счётчику, определяем общее число попыток и решаем вопрос о продолжении или окончании расчётов.
Проверять полученные расстановки на совпадения можно, но если Вас интересует доля удачных попыток среди всех попыток, то отбрасывание совпадений должно происходить после прибавления $1$ в пункте 7), а для числа сгенерированных различных позиций нужно завести отдельный счётчик. Это, кстати, позволит оценить и вероятность совпадений. И, конечно, чтобы оценка числа возможных позиций была достаточно надёжной, число сгенерированных различных позиций должно быть достаточно большим.
P.S. Кстати, при использовании всяких генераторов псевдослучайных чисел категорически рекомендуется использовать только малую часть периода генератора.

[komand]

Someone писал(а):

Как я понял, Вы генерируете не сочетания, а просто упорядоченные выборки с повторениями, и, выбирая, например, $4$ позиции для одноклеточных кораблей, Вы просто $4$ раза выбираете пары $(x,y)$ чисел из диапазона $0\ldots 9$. В результате некоторые пары могут совпадать, хотя происходит это редко (с вероятностью $0{,}058906$, если выбор клеток происходит независимо с одинаковой вероятностью $0{,}01$ для каждой). Так же и для кораблей других размеров. В итоге ваш алгоритм даёт

$$100^4\cdot(100^3\cdot 4^3)\cdot(100^2\cdot 4^2)\cdot(100\cdot 4)=409\,600\,000\,000\,000\,000\,000\,000=4{,}096\cdot 10^{23}$$

вариантов. Это более чем в 300 раз превышает то число, которое у Вас получилось раньше, и, вероятно, именно этим объясняется такое колоссальное количество отходов.

Я сегодня довольно много размышлял на эти темы и, в частности, понял, что я в своих подсчётах тоже был не прав, и что надо считать иначе. Получается несколько большая оценка. Но мне требуется некоторое время, чтобы написать всё это и выложить на форум.

Но мы ведь договорились перенести обсуждение в открытую часть форума, поэтому давайте уж обсуждать там. Вдруг кто-нибудь что-нибудь подскажет.

komand в сообщении #225695 писал(а):

Ну а касание кораблей неважно когда проверять - до генерации или после, это одно и тоже по времени и алгоритму. Это самый затратный по времени код, но от него никуда не денешься.

Вы не совсем правы. Действительно, время генерации и проверки одного варианта не очень сильно зависит от предварительных отсечений, но, уменьшая количество мусора, мы уменьшаем количество генерируемых и проверяемых вариантов для получения одного допустимого расположения. Что в конечном итоге даёт экономию времени для получения заданного количества допустимых расположений.

komand в сообщении #225695 писал(а):

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

А где Вы её собираетесь публиковать?

1. О генерации. Похоже, вы правы. Если бы я сразу расставлял 4 корабля, то это было бы число сочетаний. Однако я расставляю каждый корабль независимо, по очереди: сначала один, потом второй. При этом каждый следующий корабль может наложиться на предыдущий. Тогда получается просто степень 100? Постоянно оценка меняется, это нервирует (.
2. О скорости генерации. Проще быстро сгенерировать позицию по простым правилам, и быстро ее отсечь, чем создавать по сложным правилам. Еще и следить за теоретической моделью. Сейчас простейшая модель, и все равно мы не может придти к консенсусу, сколько же всех позиций (и легальных, и нелегальных) в игре.
3. О публикации. Здесь же и выложу, в форуме. Но, чтобы не начать сразу править и исправлять ошибки, хотелось бы сначала кое-какие моменты выяснить у знающих людей. Насчет кол-ва позиций - похоже, последний вопрос. Выясню точно - выложу всю статью.
4. Выкладываю дискуссию на форум. Пишите туда.

-- 02.04.2021, 03:46 --

То есть, если генерация начальной позиции идет по правилам:
1. Для каждого корабля создаем случайную координату корабля от [00, 99] и его направление [1,4]. Все, генерация считается оконченной. Выход корабля за пределы поля, наложение на др. корабль, пересечение с др. кораблем не учитывается.
То тогда число возможных начальных расстановок будет:
P = $100^{10}\times4^6$ ?
Объясняю, в чем смысл расчета. Дальше я проверяю:
2. Проверяем, не заходит ли корабль за границы поля. Если заходит, сразу прекращаем генерацию. Иначе идем к п. 3.
3. Проверяем, касается ли новый корабль старых. Если да, прекращаем генерацию. Иначе ставим корабль.
4. Повторяем п. 1-3 до создания полного флота, т.е. 1 палубных - 4 корабля, 2п - 3, 3п - 2, 4п - 1.
После генерации $P_a$ раз считаем число легальных (т.е. по правилам игры) генераций, $P_l$
Высчитываем коэффициент $K =$P_l / P_a, т.е. отношение числа легальных позиций ко всем сгенерированным позициям.
Предполагая что наша модель подобна реальной ситуации, находим число всех легальных позиций в реальной игре $P_i$ в игре, как
$P_i = P \times K $

Если совсем просто, то:
Теоретически высчитываем, сколько всего позиций в игре. По модели ищем долю легальных позиций при случайной генерации. Переносим модель на реальность, умножая все позиции (легальные и нет) на рассчитанную долю.

[komand]

Цитата:

Вы не совсем правы. Действительно, время генерации и проверки одного варианта не очень сильно зависит от предварительных отсечений, но, уменьшая количество мусора, мы уменьшаем количество генерируемых и проверяемых вариантов для получения одного допустимого расположения. Что в конечном итоге даёт экономию времени для получения заданного количества допустимых расположений.

Сейчас я генерирую все подряд простейшим образом, ничего не проверяя. Проверяю потом. Зато модель расчета очень простая, $100^{10}\times4^6$. Вы предлагаете отсечь большую часть мусора, но как? В программе всего две проверки: 1) вмещается ли корабль в поле и 2) пересекается ли он с др. кораблями. Разбираем по пунктам.
1. Генерируем заведомо "входящий" корабль". Это не сильно упростит генерацию, потому что вместо одной проверки на "входит корабль или нет" в две строчки кода, в программу добавится проверка типа "если корабль 4п, то генерим не ближе к стенке на 4 клетки", одна строчка кода. Но при этом усложняется модель расчета, как-то надо учитывать, что к примеру, 4п может встать не $100\times4$ способами, а меньше.
2. Проверять корабль на касание все равно придется, не придумать алгоритма, который "интуитивно" ставит корабль туда, где нет касаний. Если бы расчетная модель могла рассчитать такие корабли, то и программу можно было не писать.
Но можно хотя бы не делать пересечений, т.е. не генерить координату, уже занятую др. кораблем. Но смысл? Это и так проверяется при проверке на касание, не ускорит генерацию. А вот модель точно усложнит. После генерации 1п к примеру, следующий ставится уже не на 100 клеток, а на 99.

В общем, чем проще модель, тем лучше. Проще модель, проще не сделать в коде ошибки, проще потом доказать результат. Да, небольшой проигрыш в скорости генерации. Но проценты, не в разы, и уж точно не на порядки. Сейчас у меня $10^{11}$ позиций проверяется сутки, что дает 3-4 значащих цифры в получаемом числе, хотя в программе всего 50 строчек кода на JavaScript под Node.js. Вот если бы ее переписать на ассемблер, можно было бы надеяться на ускорение на порядок. Но было бы не $10^{11}$ генераций, а $10^{12}$, дало бы еще одну значащую цифру, достижение так себе. Для моих целей в принципе и одной значащей цифры достаточно, хотя бы вычислить число всех легальных начальных расстановок в игре с точностью до порядка величины.

В общем, хотелось бы уверенности в том, что число всех возможных позиций при такой генерации $100^{10}\times4^6$. И можно не усложнять модель. Коэффициент (доля легальных позиций) сейчас $7,588\times10^{-6}$, ($10^{11}$) генераций) все цифры значащие, что дает примерное кол-во легальных позиций в игре $4,096\times10^{23} \times $7,588\times10^{-6}$ = 3,11\times10^{18}$

[Pphantom]

komand, пожалуйста, разберитесь с цитированием нужных участков сообщений. Это делается так - выделяете требуемый участок и нажимаете кнопку "Вставка" в правом нижнем углу соответствующего сообщения. Тогда вы, во-первых, сможете цитировать то, что нужно (а не практически все сообщения собеседников), во-вторых, в заголовок цитаты автоматически подставится информация о том, кто и когда это писал (и этот участник увидит, что вы его упомянули).

[komand]

Pphantom в сообщении #1512526 писал(а):

komand, пожалуйста, разберитесь с цитированием нужных участков сообщений. Это делается так - выделяете требуемый участок и нажимаете кнопку "Вставка" в правом нижнем углу соответствующего сообщения. Тогда вы, во-первых, сможете цитировать то, что нужно (а не практически все сообщения собеседников), во-вторых, в заголовок цитаты автоматически подставится информация о том, кто и когда это писал (и этот участник увидит, что вы его упомянули).

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

[Someone]

Someone в личном сообщении писал(а):

$$\frac{100\cdot 99\cdot 98\cdot 97}{4!}\cdot\frac{81\cdot 80\cdot 79\cdot 2^3}{3!}\cdot\frac{64\cdot 63\cdot 2^2}{2!}\cdot\frac{49\cdot 2}{1!}=2\,115\,140\,355\,643\,392\,000\approx 2{,}12\cdot 10^{18}.$$

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

Достаточно генерировать левые верхние клетки кораблей, а для неодноклеточных кораблей нужно указывать их ориентацию. От левой верхней клетки корабль может быть направлен либо направо, либо вниз. Рассматривать направления влево и вверх не надо.
Левая верхняя клетка определяется двумя координатами — горизонтальной $x$ и вертикальной $y$. Удобно считать, что $0\leqslant x\leqslant 9$ и $0\leqslant y\leqslant 9$. Для некоторых целей может быть полезным упаковать эти координаты в одно число $10x+y$, помещающееся в одном байте.
Постараемся исключить все случаи, когда корабль вылезает за границу поля и некоторую часть случаев, когда корабли пересекаются. Проще всего отбросить случаи, когда левые верхние клетки кораблей совпадают, но если отбрасывать все такие случаи, то будет очень сложно подсчитать количество генерируемых вариантов.
Будем называть два корабля, выставленных на поле, однотипными, если они содержат одинаковое число клеток, и если это число больше $1$, то корабли имеют одинаковые направления, то есть, либо оба направлены от своих левых верхних клеток направо, либо оба вниз.
Будем требовать, чтобы левые верхние клетки однотипных кораблей были различными, а на совпадения левых верхних клеток для разнотипных кораблей не обращаем внимание.
Координаты левой верхней клетки одноклеточного корабля (его единственной клетки) должны изменяться в диапазоне $0\leqslant x\leqslant 9$, $0\leqslant y\leqslant 9$; горизонтального $m$-клеточного ($2\leqslant m\leqslant 4$) — в диапазоне $0\leqslant x\leqslant 10-m$, $0\leqslant y\leqslant 9$; вертикального $m$-клеточного — в диапазоне $0\leqslant x\leqslant 9$, $0\leqslant y\leqslant 10-m$.
Поэтому одноклеточный корабль можно расположить на поле $10\cdot 10=100$ способами, а горизонтальный или вертикальный $m$-клеточный корабль — $10(11-m)$ способами каждый. При $m=2,3,4$ получаем, соответственно, $90,80,70$ способов.
Поскольку алгоритм генерирует клетки последовательно, то при генерации расположений однотипных кораблей мы получаем не сочетания, а размещения.

Для размещения четырёх одноклеточных кораблей генерируем четыре попарно различные клетки (сохраняем их в порядке генерации, не сортируя). Всего у нас будет

$$A_{100}^4=100\cdot 99\cdot 98\cdot 97=94\,109\,400$$

вариантов размещения одноклеточных кораблей (с учётом порядка генерации), где

$$A_n^m=\frac{n!}{(n-m)!}=\begin{cases}1&\text{ при }m=0,\\ \prod_{k=0}^{m-1}(n-k)&\text{ при }1\leqslant m\leqslant n\end{cases}\text{ ---}$$

число размещений из $n$ элементов по $m$.

Часть двухклеточных кораблей может быть горизонтальными (от $0$ до $3$), а остальные (от $3$ до $0$ соответственно) будут вертикальные. Поэтому выбираем число $m=0,1,2,3$, где $m$ — число горизонтальных кораблей; тогда число вертикальных равно $3-m$, а число способов выбрать левые верхние клетки для этих кораблей равно $A_{90}^mA_{90}^{3-m}$. Первые $m$ из $3$ сгенерированных кораблей располагаются горизонтально, остальные — вертикально.
Складывая все эти числа, получим, что число способов размещения двухклеточных кораблей равно

\begin{multline*}A_{90}^0A_{90}^3+A_{90}^1A_{90}^2+A_{90}^2A_{90}^1+A_{90}^3A_{90}^0=90\cdot 89\cdot 88\cdot 1+90\cdot 89\cdot 90+90\cdot 90\cdot 89+1\cdot 90\cdot 89\cdot 88=\\ =90\cdot 89\cdot(88+90+90+88)=2\,851\,560.\end{multline*}$$

Чтобы все возможные расположения генерировались с одинаковыми вероятностями, значения числа $m=0,1,2,3$ нужно выбирать с вероятностями, пропорциональными числам $A_{90}^0A_{90}^3,A_{90}^1A_{90}^2,A_{90}^2A_{90}^1,A_{90}^3A_{90}^0$, то есть,

$$P_0:P_1:P_2:P_3=(90\cdot 89\cdot 88\cdot 1):(90\cdot 89\cdot 90):(90\cdot 90\cdot 89):(1\cdot 90\cdot 89\cdot 88)=88:90:90:88=44:45:45:44.$$

Такой выбор требует генерации одного (псевдо)случайного целого числа $r$ от $0$ до $44+45+45+44-1=177$ включительно. Если полученное число меньше $44$, то $m=0$; иначе если меньше $44+45=89$, то $m=1$; иначе если меньше $44+45+45=134$, то $m=2$; в противном случае $m=3$.

Аналогично для трёхклеточных кораблей получаем

$$A_{80}^0A_{80}^2+A_{80}^1A_{80}^1+A_{80}^2A_{80}^0=80\cdot 79\cdot 1+80\cdot 80+1\cdot 80\cdot 79=80\cdot(79+80+79)=19\,040.$$

Значения $m=0,1,2$ должны выбираться с вероятностями, пропорциональными числам $A_{80}^0A_{80}^2,A_{80}^1A_{80}^1,A_{80}^2A_{80}^0$, то есть, $$P_0:P_1:P_2=80\cdot 79\cdot 1:80\cdot 80:1\cdot 80\cdot 79=79:80:79$.

Для размещения четырёхклеточного корабля выбираем с равными вероятностями горизонтальную или вертикальную ориентацию и получаем

$$A_{70}^0A_{70}^1+A_{70}^1A_{70}^0=1\cdot 70+70\cdot 1=140$$

вариантов размещения.

Перемножая полученные числа, получаем число генерируемых по описанным правилам позиций, большинство которых, однако, не удовлетворяют правилам из-за пересечений и касаний кораблей:

$$94\,109\,400\cdot 2\,851\,560\cdot 19\,040\cdot 140=715\,336\,685\,929\,958\,400\,000\approx 7{,}2\cdot 10^{20}.$$

Было бы хорошо, чтобы это кто-то проверил. Меня терзают неясные сомнения. Поскольку, если численные результаты komand верны, и у него пригодной оказывается одна позиция из $1/(7{,}588\cdot 10^{-6})\approx 132\,000$, то у меня должна быть пригодной одна позиция из $230$. Мне кажется, что это слишком хорошо.

komand в сообщении #1512499 писал(а):

В общем, хотелось бы уверенности в том, что число всех возможных позиций при такой генерации $100^{10}\times4^6$.

Я не вижу, почему бы это было не так. Если только Вы не напортачили в программе, но о программе я ничего сказать не могу.

komand в сообщении #1512499 писал(а):

Коэффициент (доля легальных позиций) сейчас $7,588\times10^{-6}$, ($10^{11}$) генераций) все цифры значащие

Здесь речь идёт об оценке параметра $p$ (вероятность успеха) геометрического распределения, но имеющейся информации, наверное, маловато для оценки доверительного интервала. Впрочем, на форуме есть люди, опытные в математической статистике, может быть, они что-то скажут.

Потом ещё кое что напишу.

[komand]

Уважаемый Someone, по вашей формуле получается сложная генерация. То есть алгоритм, как я понял, следующий:
I. Для 1п
1. Генерим 4 случайных разные координаты.
2. Проверяем на касание с др. кораблями. Если касаются, засчитываем попытку, как неудачную.
II. Для палуб больше 1.
1. Генерим случайную координату верхнего левой клетки корабля так и два направления, чтобы корабль заведомо вошел.
2. Проверяем на касание с др. кораблями. Если касаются, засчитываем попытку, как неудачную.

То есть по сравнению с моей генерацией (все случайно) появляются дополнительные проверки в п. (1). При этом выигрыш в отбросе мусора (коэффициент, доля легальных позиций) ожидается как 1 из 230, что на примерно на три порядка лучше, чем у меня. У меня сомнения по этому поводу, потому что оценки этого коэффициента по Монте-Карло уже делались. Вот здесь оценивается общее число размещений кораблей, вписывающихся в поле как $2\times10^{21}$, (близок к вашему $7\times10^{20}$, а коэффициент, как 1:3900.

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

Сейчас же модель простейшая и программа простая, в ней крайне трудно сделать ошибку. Повторю:
1. Генерим любую координату в промежутке [00, 99] и направление [1,4].
2. Проверяем, вписывается ли корабль в поле. Если да, идем к пунту 3. Иначе прекращаем генерацию и считаем попытку неудачной.
3. Проверяем корабль на касание с уже сгенерированными. Если нет, ставим корабль на поле. Если да, прекращаем генерацию и считаем попытку неудачной.
После генерации считаем коэффициент, как отношение "полученных легальных позиций" к "всего сгенерированным позициям", или что тоже самое "число попыток генерации".
Я проверил коэффициент на разных объемах генерациях, он сходится:

$10^8$ - $7,76\times10^{-6}$
$10^9$ - $7,64\times10^{-6}$
$10^{10}$ - $7,614\times10^{-6}$
$5\times10^{10}$ - $ 7,6032\times10^{-6}$
$7\times10^{10}$ - $7,5901\times10^{-6}$
$10^{11}$ - $7,58839\times10^{-6}$

откуда мы можем считать значащими две-три цифры, т.е. $7,59\times10^{-6}$ Однако, вопрос, является ли выборка в $10^{11}$ представительной для множества $10^{21}$ остается открытым. Для $10^{11}$ генераций требуется сутки работы компьютера, поэтому больше запустить затруднительно. Но для моих целей (с точностью хотя бы до порядка оценить число легальных позиций) это можно считать достаточно. Ведь статья не о числе всех легальных позиций, а о стратегии игры.

Откуда
P, Число всех генераций по теории: $100^{10} \times 4^6$
К, коэффициент (доля) "легальных позиций", деленное на "общее число позиций", вычисленное программой: $7,58839\times10^{-6}$
Откуда искомое число легальных позиций в игре (число возможных позиций в игре "морской бой" по правилам): $ P \times K = 3,11\times10^{18}$, или, упрощая, $10^{18}$

Сейчас разные оценки дают число легальных позиций от $10^{17}$ до $10^{19}$, разброс на два порядка не слишком важен, если сравнить с типичной генерацией при проверке стратегий игры: $10^7$ - $10^8$. К сожалению, перебрать все позиции в игре, будь они хоть $10^{17}$, хоть $10^{19}$ на одном домашнем компьютере не представляется возможным (более 6000 лет счета). Даже привлечение облачных вычислений не поможет, разве что на суперкомпьютере можно посчитать за часы. Но опять же считать придется не раз, а сотни раз, проверяя различные стратегии. Вряд ли кто согласится на такое использование времени суперкомпьютеров ).

В общем, упростить подсчет можно только за счет усложнения теоретической модели и программы, что будет вызывать резонные сомнения в надежности и той и другой. А привлечь высококвалифицированных математиков, программистов и арендовать машинное время ложно следствии малого интереса к данной игре.

[Someone]

komand в сообщении #1512661 писал(а):

по вашей формуле получается сложная генерация.

Вы преувеличиваете. Там те же действия, что и у Вас, но в чуть более аккуратном варианте. Но программа, конечно, будет длиннее. Но я ведь не предлагаю Вам срочно выбросить свою программу и писать новую, тем более, что Вы уже фактически свои вычисления закончили и то, что хотели, получили. Я просто излагаю альтернативный вариант, причём, без ряда деталей. Если понадобится, я попробую изложить на каком-нибудь псевдоязыке. Но я пишу программы медленно, поскольку делаю это редко, и мне приходится постоянно заглядывать в соответствующие руководства. К псевдоязыку это не относится, но тут мешает стремление к идеалу.

Кстати, поскольку здесь интересно в первую очередь быстродействие программы, особо экономить на длине программы вредно. Вплоть до развёртывания коротких циклов известной длины. Впрочем, это может зависеть от свойств компилятора.

Кстати, мне интересно, как Вы проверяете пересечения и соприкосновения кораблей. У меня пара идей есть, но я потом их опишу, если понадобится.

komand в сообщении #1512661 писал(а):

Вот здесь оценивается общее число размещений кораблей, вписывающихся в поле как $2\times10^{21}$, (близок к вашему $7\times10^{20}$, а коэффициент, как 1:3900.

Количество размещений, генерируемых моим методом, равно (после некоторых упрощений)

$$A_{100}^4\cdot 2(A_{90}^3+A_{90}^2A_{90}^1)\cdot(2A_{80}^2+A_{80}^1A_{80}^1)\cdot 2A_{70}^1=715\,336\,685\,929\,958\,400\,000\approx 7{,}2\cdot 10^{20}.$$

Но здесь много повторов, поскольку генерируются все перестановки однотипных кораблей. Чтобы исключить перестановки, нужно все размещения $A_n^m$ заменить на сочетания $C_n^m$:

$$C_{100}^4\cdot 2(C_{90}^3+C_{90}^2C_{90}^1)\cdot(2C_{80}^2+C_{80}^1C_{80}^1)\cdot 2C_{70}^1=6\,674\,691\,502\,432\,800\,000\approx 6{,}675\cdot 10^{18},$$

всего примерно в $2$ раза больше вашей эмпирической оценки

komand в сообщении #1512661 писал(а):

$ P \times K = 3,11\times10^{18}$, или, упрощая, $10^{18}$

Ну, так-то уж "упрощать", наверное, не стоит, пусть хотя бы $3\cdot 10^{18}$ будет. Иначе из-за чего же Вы свой компьютер столько гоняли.

Кстати, сравнение $10^7$ расстановок кораблей с целью поиска совпадений вполне осуществимо, если их накапливать не в массиве или списке, а в бинарном дереве (Д. Кнут. Искусство программирования для ЭВМ. Том 3. Сортировка и поиск. "Мир", Москва, 1978). Сравнивать все расстановки, генерируемые программой, включая и нелегальные, не удовлетворяющие правилам игры, нет смысла, поскольку их слишком много, да и вероятность совпадения будет чрезвычайно маленькой даже для выборки объёмом $10^{11}$ ($\approx 1{,}22\cdot 10^{-6}$ для вашего алгоритма и $\approx 0{,}000\,7$ для моего; проще обработать расстановку повторно, чем выяснять, совпадает ли она с ранее обработанной). Сравнивать нужно только отобранные правильные расстановки. Информацию, однозначно идентифицирующую расстановку, можно без труда упаковать в 10 байтов (по одному байту на корабль). Кроме этой информации, каждый узел дерева должен содержать две ссылки на другие узлы, так что речь идёт о немногих сотнях мегабайт оперативной памяти, что для современных компьютеров немного.
Однако смысла затевать такой поиск практически нет. При $3{,}11\times 10^{18}$ легальных позиций и выборке объёма $10^7$ вероятность наличия совпадений равна примерно $0{,}000\,016$, при выборке в $10^8$ позиций — примерно $0{,}001\,6$, и даже для $10^9$ позиций вероятность совпадений равна примерно $0{,}148\,514$.

komand в сообщении #1512661 писал(а):

При этом выигрыш в отбросе мусора (коэффициент, доля легальных позиций) ожидается как 1 из 230

Обижаете. В $\frac{409\,600\,000\,000\,000\,000\,000\,000}{715\,336\,685\,929\,958\,400\,000}\approx 572$ раза. Правда, я не буду утверждать, что программа будет работать именно во столько раз быстрее вашей. Тут многое зависит от оптимизации.

[komand]

Очень много ценных мыслей, спасибо!
Если вы напишите простым языком, как должна работать программа, удовлетворяющая вашей модели, я попытаюсь ее реализовать. Тогда появится еще одна оценка кол-ва легальных позиций.

Программу на совпадения я написал, проверил на $4\times10^8$, больше моя программа не тянет. На хранение одной генерации требуется 20 байт, если не упаковывать (если упаковывать, в дальнейшем расходуется много времени на распаковку). Для $4\times10^8$ 8 Гб памяти, это уже близко к пределу памяти на моем компе (16 Гб), а ведь еще надо время и место для поиска в этом массиве совпадений. А она занимает много времени даже с лучшим алгоритмом. А алгоритмы поиска ушли далеко вперед от произведений Д. Кнута, по которым я учился в студенчестве, а это было 35 лет назад. В JavaScript, например, он реализуется всего в одну строчку и оптимизирован Google, так что ничего изобретать не надо. А еще, как вы сказали, вероятность такого совпадения существенна только с $10^{10}$ - $10^{11}$ генераций (чтобы добиться десятки процентов). И сделать их придется не менее сотни, чтобы таким образом оценить число всех легальных размещений в игре. Потребуется или террабайты памяти, либо скоростной SSD на пару Тб и уйма времени. Не самый оптимальный путь, IMHO.

О пересечении кораблей. Тупой и простой путь: для всех клеток вокруг корабля смотрим смотрим совпадения к массивом уже установленных кораблей. Кстати, вот скриншот кода для интереса:


Статья сейчас в целом закончена, шлифую язык. Если больше новых мыслей здесь не появится, опубликую здесь же в PDF.

Сейчас самый волнующий вопрос - применимость метода Монте-Карло к игре вообще (на основе его построена вся статья) и представительность выборок в программе общему множеству размещения кораблей. Думаю, вокруг этих двух вопросов развернется главная дискуссия в этой теме. Если, конечно, я не сделал простых тупых ошибок ))

[kotenok gav]

(Программистское бу-бу-бу)

Конструкция test = true; if (abc) test = false; return test, безусловно, гениальна. Ну напишите просто return !abc, разве это не проще? А ещё не забывайте про использование let для объявления переменных.
UPD: теперь я увидел у вас ещё конструкции a = b + c ? 1 : 0... Пишите просто a = b + c.
UPD2: да, кстати, могут ли принимать конструкции вида pole[y][x] значения помимо $0$ и $1$? Если нет, то можно заменить pole[y][x] == 1 на pole[y][x].

[komand]

kotenok gav в сообщении #1512741 писал(а):

(Программистское бу-бу-бу)

Конструкция test = true; if (abc) test = false; return test, безусловно, гениальна. Ну напишите просто return !abc, разве это не проще? А ещё не забывайте про использование let для объявления переменных.
UPD: теперь я увидел у вас ещё конструкции a = b + c ? 1 : 0... Пишите просто a = b + c.
UPD2: да, кстати, могут ли принимать конструкции вида pole[y][x] значения помимо $0$ и $1$? Если нет, то можно заменить pole[y][x] == 1 на pole[y][x].

Спасибо за советы, учту. Хотя я не стремлюсь к красоте кода, только к скорости исполнения.
Конструкция xp = x+ (x + 1 < sh?1:0) проверяет, не вышла ли координата (x+1) за пределы поля (sh). Если вышла, вместо нее тестируется не координата рядом с кораблем, а координата самого корабля, что тоже полезно. Можно было записать еще красивее конструктором, но не стремлюсь к красоте и компактности. Да и читать мою программу точно никто не будет, а сам я ее хорошо понимаю.
Вообще, я не программист, последний раз программировал в студенчестве 35 лет назад на Фортране IV, так что уровень сами можете представить )
pole[][] может принимать и другие значения, кроме 0 и 1. Но учту, что 0 тоже самое, что true, хотя смешение типов данных вроде не очень хорошая идея. А еще использовать двумерный массив для координат было глупой идеей, проще был одномерный, с координатами от 00 до 99, все равно у меня непрерывно координаты то сворачиваются в одну переменную, то разворачиваются.
Функция эта не отдельно от программы написана, использует те же глобальные переменные, объявленные в основной программе, поэтому объявлять новые переменные не нужно. Так сложилось, сейчас менять лень. Поэтому var x.

Модератору: символы в сообщении не формулы, а код программы.

[grizzly]

komand
Здесь кто-то считал число комбинаций в подобной игре. Там чуть другой набор кораблей, но Вы можете на их данных протестировать свою программку.

Ещё можете посмотреть статью из первой ссылки в гугле по запросу:
"Optimal strategies against a random opponent in battleship" (точная фраза в кавычках). Ссылка выше из этой статьи. Саму статью я не смотрел, так что не обессудьте, если не совсем в тему.

[Mikhail_K]

komand в сообщении #1512745 писал(а):

Но учту, что 0 тоже самое, что true

Нет, 0 это false.

kotenok gav в сообщении #1512741 писал(а):

могут ли принимать конструкции вида pole[y][x] значения помимо $0$ и $1$? Если нет, то можно заменить pole[y][x] == 1 на pole[y][x].

[komand]

grizzly в сообщении #1512752 писал(а):

komand
Здесь кто-то считал число комбинаций в подобной игре. Там чуть другой набор кораблей, но Вы можете на их данных протестировать свою программку.

Ещё можете посмотреть статью из первой ссылки в гугле по запросу:
"Optimal strategies against a random opponent in battleship" (точная фраза в кавычках). Ссылка выше из этой статьи. Саму статью я не смотрел, так что не обессудьте, если не совсем в тему.

Статья выглядит интересной, почитаю обязательно. Пока выложил сюда для всеобщего обозрения.
Насчет проверки комбинаций посмотрю, как будет со временем, наверное, проверю.

-- 04.04.2021, 01:54 --

Mikhail_K в сообщении #1512754 писал(а):

Нет, 0 это false.

Да, ошибся, 0 - это false.

[komand]

Посмотрел статью, к сожалению, не слишком интересна для нашей темы. Автор вычисляет полное дерево игры для маленьких полей, до ($4\times5$). После чего оценивает оценивает среднее число ходов сверху и снизу для поля $10\times10$. То есть даже не точное число, а промежуток. И почему-то называет это "optimal average number of shots". И какая польза игроку от этого знания? И какое это имеет отношение к названию статьи: "Optimal Strategies against a Random Opponent in Battleship"? Где эта самая "стратегия"? Для поля $10\times10$ о ней не сказано ни слова. Это как, например, пойти шахматным тренером и сказать: "Я знаю оптимальную стратегию игры. Среднее число ходов в шахматной партии от 30,8 ходов до 55,6". (как в статье, кстати).

Как они вычисляют число позиций, не очень понял. Но точно не для 10 кораблей на поле $10\times10$, оно на 6 порядков сложнее.

Но статья интересна подходом. Раньше я думал, что термин "среднее число ходов для победы" я сам придумал. Ан нет, надо умерить гордыню ).
А также моя идея, что "После создания позиции ваши действия никак не отражаются на действиях противника. Вы можете сначала обстрелять его поле до победы, потом он ваше. Кто сделал меньше ходов, тот выиграл."
как будто списана со статьи:
"A game of Battleship can be decomposed into two sub-games played in parallel with no interaction. In each sub-game, the opponent places the ships, and the main player tries to sink them as quickly as possible".
И прочее. В конце концов может оказаться, что все, что я "исследовал", сделано до меня. Надо просто лучше искать источники )