Еще немного оптимальных стратегий для доски 4х4. Я рассмотрел поиск одного корабля (2п, 3п, 4п). Оптимальная расстановка такова, что все неугловые положения равновероятны (для 3п и 4п это тривиально, а вот для 2п - уже нет).
Для 2п: угловые положения выбираем с вероятностью
![$\frac{7}{120}$ $\frac{7}{120}$](https://dxdy-02.korotkov.co.uk/f/d/1/7/d173e0fa06d0ff7bd46473c89f5277c982.png)
, и соответственно неугловые с вероятностью
![$\frac{1}{30}$ $\frac{1}{30}$](https://dxdy-02.korotkov.co.uk/f/d/4/1/d41ccc70f932e60cd1124acb90130a5a82.png)
. Две наилучших стратегии обстрела:
![$\begin{center}
\begin{tabular}{| c | c | c | c |}
\hline
3 & & 2 & \\ \hline
& 1 & & 2 \\ \hline
2 & & 1 & \\ \hline
& 2 & & 3 \\ \hline
\end{tabular}
\end{center}$ $\begin{center}
\begin{tabular}{| c | c | c | c |}
\hline
3 & & 2 & \\ \hline
& 1 & & 2 \\ \hline
2 & & 1 & \\ \hline
& 2 & & 3 \\ \hline
\end{tabular}
\end{center}$](https://dxdy-03.korotkov.co.uk/f/6/8/c/68c4cb18ca721a2176902a03b9f37c6882.png)
и
![$\begin{center}
\begin{tabular}{| c | c | c | c |}
\hline
3 & & 2 & \\ \hline
& 1 & & 4 \\ \hline
2 & & 5 & 2 \\ \hline
& 4 & 2 & \\ \hline
\end{tabular}
\end{center}$ $\begin{center}
\begin{tabular}{| c | c | c | c |}
\hline
3 & & 2 & \\ \hline
& 1 & & 4 \\ \hline
2 & & 5 & 2 \\ \hline
& 4 & 2 & \\ \hline
\end{tabular}
\end{center}$](https://dxdy-01.korotkov.co.uk/f/0/d/f/0dfcdec8965c3fbcb5eb4ec2a796853882.png)
Здесь циферками обозначен приоритет: сначала стреляем по всем клеткам с цифрой 1, потом по всем клеткам с цифрой 2, и т.д., пока не попадем.
Итого, кораблик убивается в среднем за
![$\frac{379}{60}$ $\frac{379}{60}$](https://dxdy-03.korotkov.co.uk/f/a/3/c/a3c289bd2cc2f5a1ff19ddab6a7d927882.png)
выстрелов.
Для 3п: угловые положения выбираем с вероятностью
![$\frac{11}{142}$ $\frac{11}{142}$](https://dxdy-03.korotkov.co.uk/f/e/0/7/e07b2c9018a3ce1b3e5937e7323f84bf82.png)
, и соответственно неугловые с вероятностью
![$\frac{4}{71}$ $\frac{4}{71}$](https://dxdy-04.korotkov.co.uk/f/3/1/4/3149963c40b8ab266ec64022a10d4f4a82.png)
. Две наилучших стратегии обстрела:
![$\begin{center}
\begin{tabular}{| c | c | c | c |}
\hline
& & 2 & \\ \hline
& 1 & & \\ \hline
2 & & & 2 \\ \hline
& & 2 & \\ \hline
\end{tabular}
\end{center}$ $\begin{center}
\begin{tabular}{| c | c | c | c |}
\hline
& & 2 & \\ \hline
& 1 & & \\ \hline
2 & & & 2 \\ \hline
& & 2 & \\ \hline
\end{tabular}
\end{center}$](https://dxdy-02.korotkov.co.uk/f/9/9/7/99749761feb378e581386ebd5fdf6c0582.png)
и
![$\begin{center}
\begin{tabular}{| c | c | c | c |}
\hline
& & 1 & \\ \hline
1 & 2 & & \\ \hline
& & 2 & 1 \\ \hline
& 1 & & \\ \hline
\end{tabular}
\end{center}$ $\begin{center}
\begin{tabular}{| c | c | c | c |}
\hline
& & 1 & \\ \hline
1 & 2 & & \\ \hline
& & 2 & 1 \\ \hline
& 1 & & \\ \hline
\end{tabular}
\end{center}$](https://dxdy-04.korotkov.co.uk/f/f/3/1/f317f75cf5e33b92936997badf7e2be282.png)
Во второй стратегии могут быть небольшие вариации, но всегда первые четыре выстрела по сторонам, а пятый выстрел в центр.
Корабль убивается в среднем за
![$\frac{108}{19}$ $\frac{108}{19}$](https://dxdy-01.korotkov.co.uk/f/4/0/b/40bf6b32094a4760aec1c2dcb60b2c8982.png)
выстрелов.
Для 4п: все положения равновероятны. Стратегия обстрела такова, что первыми четырьмя выстрелами должны зацепить все вертикали и горизонтали, а дальше добиваем. Корабль убивается за 6 выстрелов в среднем.