A Smarter random bomber for Battleship

In a further exercise of my original Battleship test framework, I have enhanced and refactored the SmartRandom class from an earlier question and have updated GitHub project to incorporate most of the suggestions I received for the previous questions. This is the second non-trivial bombing strategy class for the May 2015 Community Challenge.

Like the previous SmartRandom class, the SmarterRandom class guesses randomly until it gets a hit. It then checks for possible ship positions based on that hit, and caches those guesses. Unlike the previous version, though, it does not dump the cached guesses even if a ship is sunk and only guesses points that have at least one space between them. That is, on the first row, the hits would look like this: x.x.x.x.x..

SmarterRandom.h

#ifndef SMARTERRANDOM_H
#define SMARTERRANDOM_H
#include "Ocean.h"
#include "Bomber.h"

class SmarterRandom : public Bomber
{
public:
    const char *id() const { return "SmarterRandom"; }
    std::ostream& printTo(std::ostream &out) { 
        return out  next;
    Ocean tracking;
};

#endif // SMARTERRANDOM_H

SmarterRandom.cpp

```
#include
#include "SmarterRandom.h"

/*
* The strategy here is to bomb mostly randomly, but
* to only randomly select every other point
* and to follow up promptly when a ship is found.
*/
unsigned SmarterRandom::guess() {
unsigned location = randLocation();
// try using our pre-stored guesses first
if (!next.empty()) {
for (location = next.back();
tracking[location] && !next.empty();
location = next.back())
{
next.pop_back();
}
}
if (tracking[location]) {
for (location = randLocation();
tracking[location];
location = randLocation())
{ }
}
return location;
}

void SmarterRandom::result(unsigned location, char bombresult)
{
if (bombresult != Ocean::empty) {
if (bombresult == Ocean::h

You should definitively hit randomly on a diagonal hit pattern just tight enough to hit the smallest boat still on the board, and sink a boat in the event of a hit.

Note that the grid should be placed randomly on the board. This point should be anywhere in (0..N-1, 0..N-1) (where N is the maximum size of a ship). That way opponents could not exploit the knowledge of where the player will try to hit.

Detecting a sunk boat may be tricky. I presume the feedback says 'hit' and 'sunk'.

One typical placement is consistent in putting boats next to each other. (e.g.: in a line or perpendicular to each other).

To take this into account, the player should remember the first hit on a previously unknown area.
From there it should try to find a direction where to hit and proceed on that direction until the "sunk" event is triggered.

Then it should try further until it finds water.
Then again, from the first hit, it should go in the opposite direction until it finds water.

Boats next to each other will not escape that move.

On the hit pattern that has just been found, at least every external 'angle' should be tried in all directions. Every neighbor hit from the current grid should be tried too.

In the following example: '?' a hit on a ship. 'x' the additional tries, 'r' neighbor hits from the current diagonal grid.

x r x
 x?????x
  x r x

 x
x?x
 ? x
x???x
 x x

The two above seem obvious, but the next one would escape the above algorithm:

x
x?x
 ?  x
x????x
 x  x

Looks like:

x           x
x3x         x2x
 3  x   or   2  x
x3333x      x4444x
 x  x        x  x

And depending on the first hit and where the sunk events were received, the boats could be detected, but they could as well not.
In the above pattern, let the first hit be on the second boat part from the bottom line.

Going left, then right : for both it would look that a boat 4 has been sunk, then a boat two has been found and sunk. But it could as well be 2 size 3 boats.

Going right, then left : for the left one it would look like if a boat of size 3 has been found and sunk, then another 3 one. For the right one like a size 4 has been sunk, then a size 2.

So there is no certainty.

Worse : it could actually be:

x
x3x
 34 x
x3422x
 x4 x
  4

And that's why I wrote 'at least' the external angles. In this case testing also the internal angle would have detected the size-4.

Here are other examples:

x   x
x22333x
 x   x

 x
x2x x
x2333x
 x  x

 xx
x22xx
x4444x
 x  x

Using only this, detecting what boats have really with certainty seems impossible against any tricky opponent.

So what more could be done ?

With the knowledge of what pieces are on the board (thus, removing the ones that have been sunk with certainty).
The hit an tried hit pattern should be used to match every fitting combination of ships. Using the resulting set, new-found possible hits should be tried, until the set cannot be reduced anymore.

If said set contains only one element (and, to be clear, that element can contain more than one ship), then the situation is certain and the collection of the pieces on the board can be reduced further (and the grid size updated accordingly).

If it contains more than one, it should be kept on the side and updated every time the collection of the pieces on the board is updated.

Victory is near.

StackExchange Code Review Q#91354, answer score: 3