SmartRandom bombing strategy for Battleship game

Question

Now that I have some infrastructure in place to test it (see my Battleship test framework and the updated GitHub project for the full context), I have finally written a non-trivial bombing strategy class for the May 2015 Community Challenge.

The SmartRandom class guesses randomly until it gets a hit. It then checks for possible ship positions based on that hit, and caches those guesses. It then uses the cached guesses until either a ship is sunk (at which point it dumps the cache) or until the cache of guesses is exhausted.

SmartRandom.h

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

class SmartRandom : public Bomber
{
public:
    SmartRandom() : Bomber(), next() {}
    SmartRandom(Ocean &o) : Bomber(o), next() {}
    bool turn();
    const char *id() const { return "SmartRandom"; }
private:
    // vector holding the next guesses
    std::vector<unsigned> next;
};

#endif // SMARTRANDOM_H

SmartRandom.cpp

#include <iostream>
#include <string>
#include <random>
#include "SmartRandom.h"

static std::random_device rd;
static std::uniform_int_distribution<> r{0, Ocean::dim*Ocean::dim-1};

/*
 * The strategy here is to bomb randomly, but to follow
 * up promptly when a ship is found.
 */
bool SmartRandom::turn() {
    ++turns;
    unsigned location = r(rd);
    // 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 = r(rd); 
                tracking[location]; 
                location = r(rd))
        { }
    char result = ocean.bomb(location);
    if (result != ocean.empty) {
        if (result == 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, result); 
    if (verbose)
        std::cout << "Turn " << turns << ", bombing " << 
            location << '\n' << ocean << std::endl;
    return ocean.remaining();
}

Results

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

There are 2 placers, and 2 bombers
Running 10 iterations
UpperLeft/RandomBomber  UpperLeft/SmartRandom   RandomPlacer/RandomBomber   RandomPlacer/SmartRandom    
95  45  94  84  
94  57  95  61  
98  97  97  90  
76  81  89  79  
96  52  95  82  
96  36  96  44  
92  51  87  66  
92  62  83  40  
96  84  81  74  
91  70  96  62  

Questions

I'm interested in comments on the code, of course, but also in suggestions for improvements to the algorithm.

Answer 1

It looks good to me. The random_device and its distribution were the only things to catch my attention.

• It seems like overkill in this case. random_device produces cryptography quality number sequences, which is probably much more accuracy than you need. Since its implementation is platform-specific, it is hard to tell how much more expensive a random_device is, but I'd start with something more usual, like a Mersenne Twister seeded with one call from a random_device - That's a very common usage pattern by the way.

• No apparent reason to make it a global. That makes your code unsuitable for multithreaded use. (I would expect random_device to hold some member state that is most likely not synchronized). A member instance would be cleaner and avoids threading issues.

• Lastly, r is a bit of a weak name for a file-scoped global. Eventually you might want to declare loop counters and iterators named r and that could shadow the random generator... Perhaps consider a slightly longer name just to avoid this potential for shadowing.