7
\$\begingroup\$

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.

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

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – glampert May 11 '15 at 1:47
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Corbin May 11 '15 at 2:20
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – Morwenn May 11 '15 at 8:45
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Morwenn May 11 '15 at 8:48
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Edward May 16 '15 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.