Please note:
The code was not optimized for speed and has plenty of potential for performance improvement, esp. regarding nested looping. The competition rules included an upper time limit of 500ms per shot. This implementation runs at 1ms per shot in average, so there was no point in tuning that esp. as readability might have suffered.
The algorithm does not take into consideration opponents' behavior. The C# Pirates competition environment itself placed the ships randomly, and did not provide state storage on any larger scope than a single game, so it was not possible to react on opponent's behavior when shooting, or on different ship placement strategies.
Here is the spec: The battlefield consists of 10x10 cells. Ships are laid out either horizontally or vertically, with a margin of at least one cell between each ship. There is one ship of size 5, one of size 4, two of size 3 and one of size 2. Battleship algorithms are being called back on each round and must return the cell to shoot at next. The state of each cell can be queried through the C# Pirates API. Those states are: Unknown (cell has not been shot at yet), Water (cell has been shot at before and contains no ship) and Ship (cell has been shot at before and contains a ship).
Unknown cell
Water cell
Ship cellSo on each round of the game there is a decision to be made: at which cell to shoot at next. It soon becomes clear that we need two different modes of operation: Trialshot mode and Sinkshot mode. Trial shots occure while scanning the battlefield for ships. Sink shots happen once a ship has been hit in order to continue sinking it. We are going to talk about trial shots in part 1 and part 2, while sink shots will be covered in part 3.
In trialshot mode it's clearly a good idea to choose the cell that is most likely to be occupied by a ship. The probability of a ship residing at a certain cell can be calculated by scanning for unknown neighbor cells in each direction.
Let's have a look at an example. Say that there are the following ships left to be sunk: One of size 5, one of size 3 and one of size 2 (we know that because we kept track on which ships we sank already), and we are about to examine the cell marked with a shot impact.
There are following possibilities for this cell to contain a ship: 1 option for a ship of size 5 (filling out the whole horizontal space), 1 option for a ship of size 3 (to the east), and 2 options for a ship of size 2 (north and east). So this gives us 4 options for ships to be placed on that very cell.
What about the next unknown cell?
Again there is 1 option for a ship of size 5 (horizontally), 2 options for a ship of size 3 (both horizontally, one to the east, the other one with the proposed target cell located in the center of the ship), and 3 options for a ship of size 2 (east, west and south). There is no way for a ship to fit to the north although the northern neighbor has not been shot at yet, as it's itself restricted by the sunken ship next to it (one cell margin between ships). Still, 6 options beat 4 options, so the algorithm would choose the second cell among those two cells.
The fact that there is a margin of one cell between ships creates another cell state that we must consider: the cell has not been shot at, but is next to a ship, hence cannot be part of a ship itself. Let's call that state Impossible, and keep this information in an internal data structure between callbacks, because the C# Pirates API does not support that state, and querying all neighbors of state Unknown each time is kind of cumbersome.
So what we basically do is to iterate over all cells of state Unknown, calculate their probabilities to contain a ship, and select the highest-rated option. The question is what to do when there are several target cells with the same probability (which by the way is quite likely to happen). Making a good decision at that point is crucial and will differentiate our algorithm from competing ones which apply the same basic strategy. We will discuss that in part 2.
Followup Postings: