Battleship strategy evaluation framework

Question

In preparation for the May 2015 Community Challenge, I decided to build a Battleship strategy tester.

Implementing an ocean

First, there is an underlying Ocean class that represents both the 10x10 grid that is the playing field. It has an internal representation for both the grid and for the ships that are placed on it. It has feature that allow it to be used as both the grid on which ships are placed (defense, if you will) and the grid on which the results of guesses are plotted (offense).

Two kinds of strategies

In the classic Battleship game, there are actually two different kinds of strategies used. There is a placement strategy and a bombardment strategy. It seemed to me that it would be useful to match different placement strategies against different bombardment strategies, so I created two different things -- a place() function that places the ships and returns an Ocean object, and a Bomber class which is a pure virtual class that is intended to serve as a base class. It operates on a local copy of a passed Ocean object.

The purpose for doing it this way is that it will allow for various different kinds of placement strategies to create many different varieties of Ocean and then any number of bombardment strategy classes (each derived from the base Bomber class) can all be handed those Ocean objects for a quick head-to-head evaluation. Since I'm interested in the effectiveness of the strategies more than in the actual details of game play, the play object of the Bomber class simply takes as many turns as necessary to sink all of the ships and reports the number of turns.

The concept is that each pairing of placement and bombardment strategies can be evaluated multiple times and descriptive statistics can be generated to answer the question of which strategies are most effective.

Minimal example

At the moment, only one example each of a placement strategy (which always puts the ships side by side in the upper left corner) and one example of a bombardment strategy (which simply guesses randomly) are implemented in concrete form. The intention, as mentioned above is to create a framework for evaluation before embarking on creating multiple strategies.

My specific questions are:

1. Should Ocean be two classes? I'm not sure that having the same class used for both offense and defense makes sense. Maybe one base class and two derived ones would be better?
2. Are the classes sufficient, minimal and complete?
3. Are there better designs to express this intent?

Bomber.h

#ifndef BOMBER_H
#define BOMBER_H
#include "Ocean.h"

/*
 * plays the game with copy of passed Ocean
 */
class Bomber
{
public:
    Bomber(Ocean &o) : ocean(o), tracking(), turns(), verbose(false) {}
    virtual ~Bomber() = default;
    virtual bool turn() = 0;
    unsigned play() { while(turn()); return turns; }
protected:
    Ocean ocean;
    Ocean tracking;
    unsigned turns;
    bool verbose;
};
#endif // BOMBER_H

Ocean.h

#ifndef OCEAN_H
#define OCEAN_H

#include <iostream>
#include <string>
#include <array>

struct Ship
{
    const char *name;
    int len;
};

/*
 * The Ocean class represents the playing field.
 */
class Ocean
{
public:
    Ocean() : squares(), ships() {}
    /*
     * returns empty if empty,
     * hit if hit or the first letter of the ship if sunk
     */
    char bomb(unsigned pos);
    /*
     * places (or test-places) the given ship type according to passed
     * coordinates and orientation.
     *
     * For horizontal, coordinates are leftmost point
     * For vertical, coordinates are topmost point
     * Return true if placement was successful
     */
    bool place(unsigned pos, unsigned shiptype, bool horizontal, bool test=false);
    /*
     * records the passed shiptype at the given location.
     * Only bounds checking is done.
     */
    void record(unsigned pos, unsigned shiptype);
    unsigned operator[](int p) const { return squares[p]; }
    friend std::ostream& operator<<(std::ostream& out, const Ocean &o) {
        auto i=o.dim;
        for (auto &sq : o.squares) {
            if (sq) {
                out << (sq <= o.shipcount ? o.navy[sq-1].name[0] : o.hit);
            } else {
                out << o.empty;
            }
            if (--i == 0) {
                out << '\n';
                i = o.dim;
            }
        }
        return out;
    }
    std::string status() const;
    unsigned remaining() const;
    static constexpr char empty = '.';
    static constexpr char hit = 'x';
    static constexpr int shipcount = 5;
    static constexpr int dim = 10;
    static constexpr Ship navy[shipcount] { 
     {"Aircraft carrier", 5 },
     {"Battleship",       4 },
     {"Cruiser",          3 },
     {"Submarine",        3 },
     {"Patrol boat",      2 }
    };
private:
    // functions
    // oob = Out Of Bounds -- returns true iff point is oob
    bool oob(unsigned index) const {
        return index >= squares.size();
    }
    // data
    std::array<char, dim*dim> squares;
    std::array<int, shipcount> ships;
};
#endif // OCEAN_H

RandomBomber.h

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

class RandomBomber : public Bomber
{
public:
    RandomBomber(Ocean &o) : Bomber(o) {}
    bool turn();
};

#endif // RANDOMBOMBER_H

Ocean.cpp

#include "Ocean.h"
#include <cassert>
#include <iomanip>
#include <sstream>
#include <numeric>

constexpr Ship Ocean::navy[];

char Ocean::bomb(unsigned pos)
{
    assert(!oob(pos));
    int s = squares[pos];
    if (s) {
        squares[pos] = 0;
        return --ships[s-1] ? hit : navy[s-1].name[0];
    } else {
        return empty;
    }
}

void Ocean::record(unsigned pos, unsigned shiptype)
{
    assert(!oob(pos));
    squares[pos] = shiptype;
}

bool Ocean::place(unsigned pos, unsigned shiptype, bool horizontal, bool test)
{
    if (oob(pos) || shiptype >= shipcount)
        return false;
    int len = navy[shiptype].len;
    int delta = horizontal ? 1 : dim;
    if (oob(pos + len*delta))
        return false;
    // don't allow horizontal "wraparound"
    if (horizontal && ((pos % dim) + len >= dim))
        return false;
    bool occupied = false;
    // see if all spaces are available
    for (int d=0; d < len*delta; d += delta)
        occupied |= squares[pos+d];
    if (!occupied && !test) {
        // OK to place the ship
        ships[shiptype] = len;
        char ch = shiptype+1;
        for ( ; len; --len, pos+=delta)  {
            squares[pos] = ch;
        }
    }
    return !occupied;
}
/*
 * returns a string containing the current status of all ships.
 */
std::string Ocean::status() const
{
    std::stringstream status;
    for (int i = 0; i < shipcount; ++i) {
        status << std::setw(20) << navy[i].name <<
            "  " << ships[i] << '/' << navy[i].len << '\n';
    }
    return status.str();
}

unsigned Ocean::remaining() const { 
    return std::accumulate(ships.cbegin(), ships.cend(), 0);
}

RandomBomber.cpp

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

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

bool RandomBomber::turn() {
    ++turns;
    unsigned location;
    for (location = r(rd); tracking[location]; location = r(rd));
    tracking.record(location, ocean.bomb(location));
    if (verbose)
        std::cout << "Turn " << turns << ", bombing " << 
            location << '\n' << ocean << std::endl;
    return ocean.remaining();
}

battleship.cpp

#include <iostream>
#include <string>
#include "Ocean.h"
#include "RandomBomber.h"

/*
 * places ships on the ocean and returns an Ocean
 */
static Ocean place() {
    Ocean o;

    for (int i=0; i < o.shipcount; ++i) {
        o.place(i, i, false);
    }
    return o;
}

int main()
{
    Ocean o = place();
    std::cout << o.status() << o << std::endl;
    RandomBomber rb(o);
    std::cout << rb.play() << std::endl;
}

Sample output

    Aircraft carrier  5/5
          Battleship  4/4
             Cruiser  3/3
           Submarine  3/3
         Patrol boat  2/2
ABCSP.....
ABCSP.....
ABCS......
AB........
A.........
..........
..........
..........
..........
..........

74

Since originally posting this, I've also created a GitHub project which contains all of the source code and everything to build it using CMake. Note that to build, you will have to make sure that your compiler is set to use at least C++11. Under Linux, I do this by executing this command:

export CXXFLAGS="-Wall -Wextra -pedantic -std=c++14"

Then I run CMake and then Make.

Answer 1

Bomber

class Bomber
{
public:
    Bomber(Ocean &o) : ocean(o), tracking(), turns(), verbose(false) {}
    virtual ~Bomber() = default;
    virtual bool turn() = 0;
    unsigned play() { while(turn()); return turns; }
protected:
    Ocean ocean;
    Ocean tracking;
    unsigned turns;
    bool verbose;
};

Don't like how the derived bomber decides that the game is finished (turn() returns false). Or that it is the responsibility of the base class to provide tracking information (if the derived class wants that it can implement it). Also tracking the turn is not the responsibility of the derived class.

Also I would add a check to stop a bomber playing forever.

I would make all those members private.

class Bomber
{
public:
    Bomber(Ocean &o) : ocean(o), turns(), verbose(false) {}
    virtual ~Bomber() = default;
    bool allBoatsDestroyed(char h)
    {
        // keep track of hits and decide when game is over
    }
    unsigned play()
    {
        for(;;)
        {
            unsigned decision = turn();

            // Once the decision has been made
            // The framework plays the move and checks the result.
            char r = ocean.bomb(decision);
            youHit(r);

            // turn is incremented only after bomb dropped.
            ++turns;

            if (allBoatsDestroyed(r)) {
                break;
            }

            if (turns > failThreshold) {
                throw std::runtime_error("Failed to complete task");
            }
        }
        return turns;
    }
    bool isVerbose() {return verbose;}

    // The turn does not need to know anything from
    // the base class it just decides where to to go
    // next.
    virtual int turn() = 0;

    // The result of calling bomb on ocean is fed back
    // to the derived class so it on the next iteration
    // it may use this information to make its decision.
    //
    // Note: Has a default implementation as the strategy
    //       may not even need this.
    virtual void youHit(char x)   {}
private:
    Ocean ocean;
    unsigned turns;
    bool verbose;
};

Placer

In the same vein. For a framework we need a more rigorous way of working with potentially broken (bad code). I like that the output is an Ocean object. But we need a standardized way of asking the caller for placement. Then exiting on an error.

enum {Horz, Vert} DirectionOfBoat;
struct Placement
{
     unsigned         topLeft;
     DirectionOfBoat  direction;
};
class Placer
{
    public:
        virtual ~Placer() = default;
        virtual Placement getPlacement(Boat const& boat) = 0;
};
void doPlacement(Ocean& ocean, Placer& placer)
{
     std::vector<Boat>  boats = ocean.getBoatList();
     for(Boat const& boat: boats)
     {
         Placement place = placer.getPlacement(boat);

         // We assume the placer knows where it has placed
         // other boats so any error indicates a bug in the
         // placer algorithm
         if (!ocean.place(place)) {
             throw std::runtime_error("Bad placement");
         }
    }
}