Стратегия игры в Морской бой на основе моделирования

[komand]

Я уже публиковал эту статью 5 лет назад, однако появилась новая информация и я пересчитал модель и переписал статью.. Вот ссылка на PDF. Если кратко, то суть работы в том, что я написал программу, которая создает начальные позиции в игру "Морской бой" по заданным параметрам, потом играет в нее миллиарды раз, получая статистику по наиболее выгодным стратегиям расстановки и обстрела кораблей.

[komand]

Поменял раздел "Оценка легальных позиций в игре"

Число позиций для одного корабля (без учёта других). Для длины $L > 1$: $Count(L) = 2 \times (10 - L + 1) \times 10$. Для $L = 1$: $Count(1) = 100$. Значения: $L=4$: $140$; $L=3$: $160$ (для каждого из двух); $L=2$: $180$ (для каждого из трёх); $L=1$: $100$ (для каждого из четырёх).

Общее число размещений (корабли различимы). $N_{totaldiff} = 140 \times 160^2 \times 180^3 \times 100^4 \approx 2{,}090189 \times 10^{21}$.

Оценка доли легальных позиций (Монте-Карло). Сгенерировано $10^{10}$ случайных расстановок. Из них легальных - $2,554,511$. Доля $p = 2,554,511 / 10^{10} = 2{,}554511 \times 10^{-4}$.

Число легальных позиций для различимых кораблей. $N_{legaldiff} = p \times N_{totaldiff} \approx 5{,}339 \times 10^{17}$.

Учёт неразличимости кораблей. Перестановки внутри групп: $2! = 2$ (3-палубные), $3! = 6$ (2-палубные), $4! = 24$ (1-палубные). Общий делитель $= 2 \times 6 \times 24 = 288$. $N_{legal} = N_{legaldiff} / 288 \approx 1{,}854 \times 10^{15}$.

Итог с доверительной вероятностью $99{,}7%$. Относительная погрешность: $3 / \sqrt{2,554,511} \approx 0{,}001877$ ($0{,}1877%$). Окончательный результат: $N_{legal} = (1{,}854 \pm 0{,}003) \times 10^{15}$ ($3\sigma$).

С учётом симметрий поля (8 преобразований) число уникальных позиций примерно в 8 раз меньше: $N_{unique} \approx 2{,}32 \times 10^{14}$.

[maxal]

Тема перемещена из форума «Математика (общие вопросы)» в форум «Computer Science»