The game of "sea battle" requires two players each armed with a pencil and a piece of paper, preferably with preprinted square pattern. Each player draws two 12x10 grids, labels the columns A through L and the rows 1 to 10 on their paper. One grid for keeping track of the game in either direction. Each player marks off his five ships in one of his two grids, one which takes up 5 grid points, one which takes up 4 grid points, two which take up 3 grid points and one which takes up 2 grid points. Each ship may be placed horizontally or vertically but not on a diagonal, and the ships may not overlap or reach out of the 12 by 10 grid. When both players are ready, the game commences with each of then firing a salvo by calling out the coordinates where the shot is aimed, for instance "A4", the opponent must answer truthfully if the shot is a miss, a hit and if so if the ship is sunk. The player who first sinks all his oppnents ships wins. A large number of variations exist, but the basic game remains the same.
Analyzing the game, the first question that presents itself is how may ways can you arrange your ships ? The answer is 101,832,786,704, that is 101 billion ways. There is obviously two instances of symmetry but even then the number is big enough to make a table-lookup strategy not entirely impossible, but very time consuming to set up.
The layout of the opponents ships is of course not random, but since we don't know much about the game yet, we will assume that neither does our opponent, so random layout is a good approximation for now.
Letting a computer chew through all the possible layouts in the game (this takes about a day), we can derive a table which shows how many layouts have each grid point occupied by a ship. If we normalize by the total possible layouts, we get a probability that for a ship occupying each gridpoint:
A B C D E F G H I J K L
1 0.0631 0.0914 0.1145 0.1267 0.1329 0.1322 0.1322 0.1329 0.1267 0.1145 0.0914 0.0631
2 0.0914 0.1150 0.1345 0.1447 0.1498 0.1493 0.1493 0.1498 0.1447 0.1345 0.1150 0.0914
3 0.1145 0.1344 0.1510 0.1597 0.1642 0.1637 0.1637 0.1642 0.1597 0.1510 0.1344 0.1145
4 0.1268 0.1447 0.1598 0.1680 0.1723 0.1719 0.1719 0.1723 0.1680 0.1598 0.1447 0.1268
5 0.1333 0.1501 0.1644 0.1725 0.1767 0.1764 0.1764 0.1767 0.1725 0.1644 0.1501 0.1333
6 0.1333 0.1501 0.1644 0.1725 0.1767 0.1764 0.1764 0.1767 0.1725 0.1644 0.1501 0.1333
7 0.1268 0.1447 0.1598 0.1680 0.1723 0.1719 0.1719 0.1723 0.1680 0.1598 0.1447 0.1268
8 0.1145 0.1344 0.1510 0.1597 0.1642 0.1637 0.1637 0.1642 0.1597 0.1510 0.1344 0.1145
9 0.0914 0.1150 0.1345 0.1447 0.1498 0.1493 0.1493 0.1498 0.1447 0.1345 0.1150 0.0914
10 0.0631 0.0914 0.1145 0.1267 0.1329 0.1322 0.1322 0.1329 0.1267 0.1145 0.0914 0.0631
Notice that the highest probability does not occur in the four grid points in the center [F,G][5,6], but rather in the four points on either side of them [E,H][5,6]. It follows that our best chance of hitting something in our first shot is to aim at one of these four. There is symmetry between them, so we will take E5 as our first shot.
Pretend that we miss, we can run through all the layouts again, sorting the 16.42% out which had a ship in this grid point and see what the situation looks like then. Plotting the 83,835,189,168 remaining layouts we find:
A B C D E F G H I J K L
1 0.0653 0.0946 0.1187 0.1317 0.1324 0.1374 0.1371 0.1377 0.1312 0.1185 0.0945 0.0653
2 0.0946 0.1190 0.1395 0.1508 0.1392 0.1556 0.1549 0.1549 0.1494 0.1387 0.1187 0.0945
3 0.1187 0.1395 0.1576 0.1683 0.1341 0.1724 0.1708 0.1699 0.1648 0.1555 0.1387 0.1185
4 0.1318 0.1509 0.1684 0.1797 0.1181 0.1836 0.1807 0.1789 0.1735 0.1645 0.1493 0.1313
5 0.1328 0.1395 0.1344 0.1184 0.0000 0.1233 0.1479 0.1679 0.1736 0.1705 0.1554 0.1382
6 0.1386 0.1566 0.1732 0.1842 0.1234 0.1882 0.1853 0.1835 0.1781 0.1694 0.1550 0.1381
7 0.1315 0.1501 0.1667 0.1767 0.1432 0.1807 0.1790 0.1782 0.1733 0.1646 0.1494 0.1313
8 0.1185 0.1389 0.1563 0.1660 0.1545 0.1701 0.1695 0.1694 0.1646 0.1556 0.1387 0.1185
9 0.0945 0.1188 0.1389 0.1497 0.1502 0.1545 0.1543 0.1548 0.1493 0.1387 0.1187 0.0945
10 0.0653 0.0945 0.1184 0.1311 0.1384 0.1368 0.1369 0.1377 0.1312 0.1185 0.0945 0.0653
Notice how the probabilities in the grid points horizontally or vertically next to E5 drops in probability, this is to be expected because any ship covering E5 would also cover at least one of these neighbors grid points.
The field which now carries the highest probability of being covered by an enemy ship is now F6 so we Lop a shot at it and let computer chew again. 68,059,333,932 layouts later we find that G7 is where to aim next.
A B C D E F G H I J K L
1 0.0679 0.0981 0.1232 0.1368 0.1375 0.1436 0.1425 0.1432 0.1363 0.1230 0.0981 0.0679
2 0.0981 0.1232 0.1444 0.1564 0.1442 0.1563 0.1609 0.1607 0.1546 0.1435 0.1229 0.0981
3 0.1232 0.1444 0.1632 0.1750 0.1394 0.1624 0.1782 0.1765 0.1705 0.1607 0.1435 0.1230
4 0.1369 0.1565 0.1750 0.1884 0.1244 0.1527 0.1910 0.1871 0.1800 0.1702 0.1545 0.1364
5 0.1380 0.1446 0.1397 0.1247 0.0000 0.0598 0.1581 0.1766 0.1806 0.1767 0.1609 0.1437
6 0.1450 0.1573 0.1632 0.1535 0.0604 0.0000 0.1300 0.1541 0.1689 0.1707 0.1617 0.1440
7 0.1366 0.1559 0.1739 0.1870 0.1532 0.1239 0.1924 0.1881 0.1805 0.1704 0.1545 0.1364
8 0.1229 0.1439 0.1623 0.1738 0.1629 0.1388 0.1793 0.1773 0.1709 0.1609 0.1434 0.1229
9 0.0981 0.1230 0.1439 0.1559 0.1569 0.1436 0.1615 0.1612 0.1548 0.1435 0.1229 0.0981
10 0.0679 0.0981 0.1230 0.1365 0.1445 0.1367 0.1428 0.1434 0.1364 0.1230 0.0981 0.0679
It is interesting to note that we here see a diagonal tactic which I have seen employed by many players of the game, but never have I seen one of them start in one of the four optimal grid points, they invariably start in one of the four central grid points or in one of the corners.
Letting the computer chew on for some days, the sequence of optimal shots assuming random placement of ships emerges and we find that it can take as much as 28 shots to locate the first hit.
Number Target Layouts % of all % eliminated
eliminated layouts layouts
------------------------------------------------------
1 E5 17997597536 17.67 17.67
2 F6 15775855236 15.49 33.16
3 G7 13092028056 12.85 46.02
4 D4 10743820628 10.55 56.57
5 H8 8752785724 8.59 65.16
6 I5 7257173140 7.12 72.29
7 H4 6079208760 5.96 78.26
8 G3 4913599616 4.82 83.08
9 J6 3980630302 3.90 86.99
10 F2 2943729994 2.89 89.88
11 C7 2369206344 2.32 92.21
12 D8 1939387722 1.90 94.12
13 E9 1546913500 1.51 95.63
14 B6 1207538906 1.18 96.82
15 K7 872845658 0.85 97.68
16 I9 668561146 0.65 98.33
17 C3 505896540 0.49 98.83
18 A5 378368810 0.37 99.20
19 E1 277196134 0.27 99.47
20 F10 197410466 0.19 99.67
21 L5 130984232 0.12 99.80
22 J1 82032920 0.08 99.88
23 K2 55509976 0.05 99.93
24 J10 30112016 0.02 99.96
25 B2 18009568 0.01 99.98
26 A10 10093348 0.00 99.99
27 L8 4719058 0.00 99.99
28 H3 1571368 0.00 100.00
Here is the same list shown on the grid of the game:
A B C D E F G H I J K L
1 . . . . 19 . . . . 22 . .
2 . 25 . . . 10 . . . . 23 .
3 . . 17 . . . 8 28 . . . .
4 . . . 4 . . . 7 . . . .
5 18 . . . 1 . . . 6 . . 21
6 . 14 . . . 2 . . . 9 . .
7 . . 11 . . . 3 . . . 15 .
8 . . . 12 . . . 5 . . . 27
9 . . . . 13 . . . 16 . . .
10 26 . . . . 20 . . . 24 . .
It is pretty obvious this at this point in time that a strategy exists which works better than random layout if playing against an opponent which uses the table above to play from: Just use one of the 1,571,368 layouts which take no hit until the 28th shot.
In the other hand, such a counter-strategy would be easy to find a counter-counter-strategy for: Shot the list in reverse order, and for good measure, hit the four corners first.
But we have to take the four fold symmetry into account, A wise player using the list from above would mirror it about one or both center axis in order to reduce predictability.
If we plot the first 20 shots we find that the pattern does actually not overlap with its own symetries. Shot number 21 breaks this pattern, but there is nontheless probably a profund insight hidden in this non-overlap.
A B C D E F G H I J K L
1 . . . . 19 20 20 19 . . . .
2 . . . 16 13 10 10 13 16 . . .
3 . . 17 12 5 8 8 5 12 17 . .
4 . 15 11 4 7 3 3 7 4 11 15 .
5 18 14 9 6 1 2 2 1 6 9 14 18
6 18 14 9 6 1 2 2 1 6 9 14 18
7 . 15 11 4 7 3 3 7 4 11 15 .
8 . . 17 12 5 8 8 5 12 17 . .
9 . . . 16 13 10 10 13 16 . . .
10 . . . . 19 20 20 19 . . . .
That's how far I got, feel free to continue from here...
My C source code
