A Smarter random bomber for Battleship

Question

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 << "\nTracking:\n" << tracking << std::endl; 
    }
private:
    unsigned guess();
    void result(unsigned location, char bombresult);
    void reset() {next.clear(); tracking.reset(); }
    unsigned randLocation();
    bool isBadLocation(unsigned loc) const {
        unsigned col = loc % Ocean::dim;
        unsigned row = loc / Ocean::dim;
        if (col & 1) {
            return (row & 1);
        } 
        return !(row & 1);
    }
private:
    // vector holding the next guesses
    std::vector<unsigned> next;
    Ocean tracking;
};

#endif // SMARTERRANDOM_H

SmarterRandom.cpp

#include <iostream>
#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::hit) {  // generic hit
            unsigned shortship = Ocean::shipcount-1;
            if (tracking.place(location, shortship, true, true))
                next.push_back(location+1);
            if (tracking.place(location, shortship, false, true))
                next.push_back(location+Ocean::dim);
            if (tracking.place(location-1, shortship, true, true))
                next.push_back(location-1);
            if (tracking.place(location-Ocean::dim, shortship, false, true))
                next.push_back(location-Ocean::dim);
        } else {  // specific ship was just sunk
            //next.clear();
        }
    }
    tracking.record(location, bombresult); 
}

unsigned SmarterRandom::randLocation()
{
    unsigned loc = randSq(gen);
    // only allow the location if it's an odd row or odd colum
    // but not both
    for ( ; isBadLocation(loc); loc=randSq(gen));
    return loc;
}

Results

I used two different placement strategies (as explained in the Battleship test framework question) and three different bombardment strategies. The first was a relatively stupid random bombing strategy, the second was posted in the previous question and this one, which performs much better. (The numbers are the number of turns it took to sink all ships.)

There are 2 placers, and 3 bombers
Running 10 iterations
UpperLeft/RandomBomber  UpperLeft/SmartRandom   UpperLeft/SmarterRandom RandomPlacer/RandomBomber       RandomPlacer/SmartRandom        RandomPlacer/SmarterRandom
100     87      27      80      53      62
99      60      26      93      54      70
100     47      21      100     67      34
99      39      21      91      61      55
98      65      24      91      68      56
98      97      18      99      64      52
100     56      19      98      75      60
98      96      30      97      45      53
97      70      25      82      58      54
87      99      21      92      42      44

I'm currently working on some code in R to analyze these results, but it's pretty clear that the latest algorithm is the best of the three so far.

Questions

I'm interested in comments on the code, of course, but also in suggestions for improvements to the algorithm. Specifically, should the random search pattern remember when the smallest ship has been sunk and widen the guess grid spacing as a result? If so, how might that best be done?

Answer 1

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.