So far we have done our best to hit a ship. But let's face it, it's more likely to hit the water. How can we benefit from a missed shot as well?
By applying a checkerboard-like shooting pattern we will find each ship by only having to hit only 50% of the cells (and that's a worst case scenario). E.g. there is no way for a ship of size 2 to hide anywhere here:
Great, we now have an additional selection criteria for choosing the next target cell: the checkerboard pattern.
Still there might be plenty of cells left with equal ship location probabilities which also fit into the checkerboard. Which other value can be gained from a missed shot? The value of learning something about unknown neighbor cells! When an unknown cell A has a water cell neighbor B (or an impossible cell neigbor, which is a cell that adjoins a sunk ship), this clearly limits the options for a ship to be located on cell A - because cell B is out of the game for a joined ship location.
If cell A is surrounded by two water/impossible cells the probabilities decrease further, and even more of course with three water/impossible neighbors (just one direction left to place a ship). Finally if we happen to shoot at the last remaining unknown neighbor cell of A (and hit water only), we can abandon that cell A for future consideration all together.
So what we are going to do is to count the water and impossible neighbors for each of our potential target's unknown neighbors (our target's unknown neighbors' water/impossible neighbors so to speak), and prefer the one target with the highest score.
This cell here might be a good choice for a shot (neighbor score is 7, 2 water neighbors for the western unknown neighbor + 2 water/impossible neighbors for the northern unknown neighbor + 0 for the eastern impossible neighbor + 3 water/impossible neighbors for the southern unknown neighbor):
In the following case that cell would score even higher (neighbor score is 9, 3 water neighbors for the western unknown neighbor + 3 water/impossible neighbors for the northern unknown neighbor + 0 for the eastern impossible neighbor + 3 water/impossible neighbors for the southern unknown neighbor):
So the neigbor score becomes our second target selection criteria, right after to the ship location probability.
If there are cells with equal ship location probability and equal neighbor score, we choose one that fits the checkerboard (by the way, applying the neighbor score almost naturally leads to a checkerboard as well, so this is just to go sure for special cases, e.g. a more or less empty battlefield). If more than one of the top-ranked cells fits the checkerboard, we'll randomly select any of them.
In part 3 we will discuss how to proceed once the first cell of a ship has been hit. There is a lot of potential for tuning as well.
Previous Postings:
Followup Postings: