Цитата:
Если в качестве чистой стратегии рассматривать конкретную позицию (см. выше), то логично в качестве чистой стратегии обстрела рассматривать конкретную последовательность выстрелов, которых будет
![$100! \approx 10^{158}$ $100! \approx 10^{158}$](https://dxdy-02.korotkov.co.uk/f/5/3/f/53f44c25bc08bac0f00f389b1159d10582.png)
Начальных расстановок кораблей много меньше,
![\approx$10^{19}$ \approx$10^{19}$](https://dxdy-02.korotkov.co.uk/f/1/b/8/1b80f75e12020fd8d3e951c30a1181ac82.png)
(по др. оценкам,
![\approx$10^{17} \approx$10^{17}](https://dxdy-04.korotkov.co.uk/f/b/5/5/b552f54353e31d4321158d89aef08fe482.png)
), так что возможно даже рассчитать все позиции с начала игры. У меня десктоп такое не тянет (всего лишь 30000 игр в секунду), поэтому рассчитывал ВСЕ позиции после отлова 4-палубников, это много проще. Особого выигрыша против "сетка-3" + отлов двухпалубников не дало.
-- 18.03.2021, 22:40 --Если же считать, что цель игры - выбить корабли противника раньше, чем он выбьет наши, а не выбить его как можно быстрее, то может быть важно и ситуация с нашим полем (если мы видим, что противник нас скоро добьет - берем стратегию, которая имеет больше шансов на очень быстрый выигрыш, пусть даже увеличивая ожидание времени до победы).
Забудьте о противнике! Считайте, что его нет. Ваш противник - число ходов (попыток) до полного потопления чужого флота. Чем быстрее, тем лучше. Вы можете играть асинхронно: сначала вы сыграет против его размещения кораблей, потом он против вашего и сравниваете кол-во ходов (попыток). У кого меньше, тот и выиграл. Поэтому можно сосредоточится только на одном важном критерии игры: кол-во попыток (ходов), требуемых для уничтожения некого расположения (слчайного или по какой-то системе).
-- 18.03.2021, 22:44 --Вы используете слово "стратегия" не в том смысле, что уважаемые mihaild и Padawan.
У Вас "стратегий" обстрела две, потому что Вы два алгоритма ведения огня рассматриваете.
А уважаемые mihaild и Padawan говорят о чистых стратегиях в терминах теории игр. Тогда чистых стратегий ведения огня
![$\approx 10^{158}$ $\approx 10^{158}$](https://dxdy-02.korotkov.co.uk/f/d/8/8/d8834d755f2068c053f5691f1633d10582.png)
, сильно больше, чем атомов в видимой части Вселенной.
Стратегий на самом деле огромное кол-во. Но их можно классифицировать по одному критерию: случайно вы стреляете или нет. Сначала разбирается случайная стратегия, а потом "абсолютная", т.е. каждый ход делается с учетом наиболее вероятного расположения чужих кораблей. Лучше стратегии быть просто не может по определению. К сожалению, как я писал выше, десктоп такие расчеты не тянет с начальной позиции, но после отлова 4-х палубников - неплохо. И эта стратегия обстрела показала минимальное преимущество перед классикой (отлов 4-х, 3-х, 2-х палубников последовательно), при этом требует ресурсы на много порядков больше и недоступна человеку.
На самом деле еще хуже: на самом деле "абсолютная" стратегия обстрела не сильно выигрывает у случайной. Конкретные цифры я пока не хочу публиковать, это раскрытие статьи.
-- 18.03.2021, 22:55 --А зачем брать сразу 10x10, если можно взять 3x3 c одним двухпалубным, найти точное решение в терминах теории игр и посмотреть, насколько согласованный результат даст Ваш метод? Потом можно взять 4x4 с однопалубным и двухпалубным и т. п. И выводы проверяться сами собой.
Я рассматривал все поля, от
![$2\times2$ $2\times2$](https://dxdy-02.korotkov.co.uk/f/5/6/4/5642f62a9faca8d26da9e24171f4974782.png)
до
![$20\times20$ $20\times20$](https://dxdy-03.korotkov.co.uk/f/2/a/2/2a24785b8d811afdc64c110e6dc02bd182.png)
и разное кол-во кораблей (от 1 до 30). Метод согласуется с теорией (когда удается подсчитать). Да и как он может не согласоваться? Программа же генерирует начальное расположения флота и сама же потом его топит. И так
![$10^7-10^9$ $10^7-10^9$](https://dxdy-02.korotkov.co.uk/f/1/6/3/16373842ce50c19461742c0e1e16e3f482.png)
раз. После чего строится распределение, высчитывается среднее, дисперсия, квадратичное отклонение, стандартная ошибка (все это возможно, потому что распределение получается близко к нормальному). Можно возразить, что
![$10^9$ $10^9$](https://dxdy-01.korotkov.co.uk/f/0/6/5/065159456ed4c790e33155c119a0726f82.png)
- это только
![$10^{-10}$ $10^{-10}$](https://dxdy-04.korotkov.co.uk/f/7/e/6/7e66fb4017db9bbbc21f10b17fe18e4282.png)
от всех расположений кораблей. Но последовательности в
![$10^7$ $10^7$](https://dxdy-04.korotkov.co.uk/f/3/e/0/3e02422f64842442ef4a4ea4be527fc382.png)
генерировались сотни раз и сравнивались, существенных расхождений нет. Цитата:
1. Проверено, что при большем кол-ве генераций позиций (от
![$10^7$ $10^7$](https://dxdy-04.korotkov.co.uk/f/3/e/0/3e02422f64842442ef4a4ea4be527fc382.png)
) вероятность занятости некой клетки кораблем одинакова,
![$\approx0.01000±0.00003$ $\approx0.01000±0.00003$](https://dxdy-01.korotkov.co.uk/f/4/b/2/4b2ddeccbde7c751848241c9d9e7a92882.png)
. Т.е. при случайном расположении кораблей можно вести обстрел в любом порядке, разницы в попытках не будет.
2. Число свободных клеток после генерации
![$\approx17,7$ $\approx17,7$](https://dxdy-02.korotkov.co.uk/f/1/c/c/1cca9b240a81c7d78752feb284e36b0d82.png)
. Отсюда можно оценить число возможных позиций в игре, как
![$\approx10^{19}$ $\approx10^{19}$](https://dxdy-01.korotkov.co.uk/f/4/9/d/49d4c3a9a6af0da44a02a6a14f34fbc582.png)
.
Здесь на основе др. алгоритма оценка ниже,
![$\approx5$\times$10^{17}$ $\approx5$\times$10^{17}$](https://dxdy-04.korotkov.co.uk/f/3/5/d/35db623b9440f447bd19a7a67cfd60d782.png)
3. Среди
![$10^7$ $10^7$](https://dxdy-04.korotkov.co.uk/f/3/e/0/3e02422f64842442ef4a4ea4be527fc382.png)
позиций ни разу не было найдено повторяющихся (проверено сотни раз). Это плохо: хотелось бы протестировать все возможные позиции. Но на современном десктопе удавалось достичь скорости < 30000/сек позиций на одном процессоре, это слишком мало (см. п. 2).
Если хотите, назовите размер поля, число и состав кораблей, я дам вам распределение попыток для их уничтожения, среднее и дисперсию.