# SmartRandom bombing strategy for Battleship game

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.

• Do we have a server to submit bombers to that will run the code automatically? – Martin York May 12 '15 at 16:42
• @LokiAstari: unfortunately, no, not yet. I haven't yet had the time. – Edward May 12 '15 at 18:25

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.

• @Edward, to be honest, I can't confirm this, but I would expect that a random_device holds some member state, which is probably not synchronized with a mutex, so concurrent calls could mess up the internal states. But I might be wrong. And sure if you don't ever intend to thread your code, that is not an issue at all. – glampert May 11 '15 at 1:47
• @Edward "it's not clear to me that it holds for a random device." That's a pretty risky assumption. You can't assume something is threadsafe (at least not portably or reliably) unless it's explicitly specified. – Corbin May 11 '15 at 2:20
• @Edward To avoid state problems, the best thing to do is to make the random-related classes thread_local: that way, there are very few instances and it ensures thread-safety with no concurrent access to the state. – Morwenn May 11 '15 at 8:45
• And yeah, std::random_device is sometimes not even random at all on some platforms (I look at you MinGW). Since its entropy may be limited, it is best suited to initialize other pseudo-random number generators. – Morwenn May 11 '15 at 8:48
• @glampert: according to this question over on stackoverflow the random classes are not thread safe, and it supports Morwenn's idea of having one per thread. – Edward May 16 '15 at 16:40