Board game design in C++

Question

I'm trying to build a board game and solve it using algorithms such as Monte Carlo Tree Search in C++. My current design follows this python project, in which I have a class hierarchy for Board and a State template as follows

// board.hpp
#ifndef GAME_BOARD_H_
#define GAME_BOARD_H_

#include <vector>
#include <unordered_set>
#include <string>
#include <utility>

#include "basics.hpp"

namespace game {    
    class Board {
    public:
        using type = std::vector<std::vector<Piece>>;
        explicit Board(int);
        Board(const Board&);
        Board(Board&&);

        Board& operator=(const Board&);
        Board& operator=(Board&&);

        virtual ~Board() {}

        virtual void display() const = 0;

        /* Queries */
        bool is_on_board(Point p) const { return is_on_board(p.first, p.second); }
        bool is_valid(Point p) const { return is_valid(p.first, p.second); }
        
        /* Access */
        std::unordered_set<Point, PointHash> get_valid_moves();
        Piece get_piece(Point p) const { return get_piece(p.first, p.second); }
        int get_board_size() const { return n; }

        /* Modifiers */
        bool reset(Point);
        bool move(Point, Piece);
    protected:
        bool is_on_board(int i, int j) const { return i >= 0 && i < n && j >= 0 && j < n; }
        virtual bool is_valid(int i, int j) const = 0;

        const type& get_board() const { return board; }
        Piece get_piece(int i, int j) const { return board[i][j]; }
    private:
        int n;
        type board;
    };
}

#endif

// state.hpp
#ifndef GAME_STATE_H_
#define GAME_STATE_H_

#include <vector>
#include <memory>
#include <unordered_set>

#include "basics.hpp"

namespace game {
    template<typename Board>
    class State {
    public:
        State(Board={}, Piece=Piece::White, int u=0);
        State(const State&);
        State(State&&);
        
        State& operator=(const State&);
        State& operator=(State&&);

        ~State() {}
        
        void display() const { board.display(); }
        bool is_over() const;

        /* Modifiers */
        bool update_board(Point, Piece);
        void update_utility(int);

        /* Access */
        int get_utility() const { return utility; }
        // get utility for piece p
        int get_utility(Piece p) const { return p == curr_piece? utility: -utility; }
        Piece to_move() const { return next_piece(curr_piece); }
        const Board& get_board() const { return board; }
        std::unordered_set<Point, PointHash> get_valid_moves() { return valid_moves; }
    private:
        Piece curr_piece;
        Board board;
        int utility;
        Point curr_move;
        std::unordered_set<Point, PointHash> valid_moves;
    };
}

template<typename Board>
game::State<Board>::State(Board b, Piece p, int u):
        board(b), curr_piece(p), utility(u) {
    valid_moves = board.get_valid_moves();
}

template<typename Board>
game::State<Board>::State(const State& rhs): 
        curr_piece(rhs.curr_piece), 
        board(rhs.board),
        utility(rhs.utility),
        curr_move(rhs.curr_move) {
    
}

template<typename Board>
game::State<Board>::State(State&& rhs):
        curr_piece(rhs.curr_piece),
        board(std::move(rhs.board)),
        utility(rhs.utility),
        curr_move(rhs.curr_move) {
}

template<typename Board>
game::State<Board>& game::State<Board>::operator=(const State& rhs) {
    if (this != &rhs) {
        auto tmp = rhs;
        swap(*this, tmp);
    }
    return *this;
}

template<typename Board>
game::State<Board>& game::State<Board>::operator=(State&& rhs) {
    if (this != &rhs) {
        curr_piece = rhs.curr_piece;
        swap(board, rhs.board);
        utility = rhs.utility;
        curr_move = rhs.curr_move;
    }
    return *this;
}

template<typename Board>
bool game::State<Board>::update_board(Point point, Piece piece) {
    curr_piece = piece;
    curr_move = point;

    auto succ = board.move(point, piece);
    if (succ)
        valid_moves.erase(point);
    
    return succ;
}

template<typename Board>
void game::State<Board>::update_utility(int u) {
    utility = u;
}

#endif

I define Board as a base class so that derived classes can have their own implementation of display and is_valid. For example, the following code is my implementation of these functions for Hex

// hex_board.cpp
    
void HexBoard::display() const {
    static constexpr char RESET[] = "\033[0m";
    static constexpr char RED[] = "\033[31m";
    static constexpr char BLUE[] = "\033[34m";
    auto n = get_board_size();
    for (auto i = 0; i != n; ++i) {
        std::cout << std::string(i, ' ');
        for (auto j = 0; j != n; ++j) {
            auto x = Board::get_piece(i, j);
            switch (x) {
                case Piece::Blank: std::cout << ". "; 
                    break;
                case Piece::White: std::cout << RED << "x " << RESET; 
                    break;
                case Piece::Black: std::cout << BLUE << "o " << RESET; 
                    break;
            }
        }
        std::cout << std::endl;
    }
}

vector<Point> game::HexBoard::get_adjacent_points(Point point, Piece piece) const {
    int i = point.first, j = point.second;
    int n = get_board_size();
    std::vector<Point> ans;
    for (const auto& s: HexNeighbor) {
        int x = i + s.first, y = j + s.second;
        if (is_on_board(x, y) && get_piece(x, y) == piece) {
            ans.push_back(make_pair(x, y));
        }
    }
    return ans;
}

The State is a template because it owns a Board. If I define it as a plain class, then it has to store the board via a (smart) pointer so that it can point to a subclass of Board. I don't do that in the first place because in algorithms, like Monte Carlo tree search, we usually have to create many subsequent States so as to see which action performs best. Regarding the number of potential states the algorithm has to create, I think it's better to put States on the heap. And if State stores a pointer to Board then there will be two indirect access, which I'm not so sure if it's good.

Now I'm about to write Player, in which algorithms such as Monte Catlo tree search are implemented. Now a problem arises: because Player takes in State to make an action and State is a template, Player has also to be a template. On the other hand, I'd like to define Player as a base class so that subclasses can implement different strategies. I know that defining a hierarchy on a template class can cause code bloating because of the virtual functions. This makes me rethink all design and I come with two solutions

1. Don't define any virtual function in Player and subclass it for different algorithms. This dispenses with the concerns of code bloating. Furthermore, I can define Board as a template and specialize it for different games as I don't think there is a need for dynamic binding.
2. Define State as a plain class that contains a smart pointer to Board. In this way, there is no template anymore.

Which one is a better way to go? How should I make the choice? Or are there any other better solutions?

Answer 1

Inevitably, as you have mentioned, it all comes down to the choice between two approaches — templates and virtuals. These two approaches each have their own benefits and drawbacks.

The problem with your current code, though, is that it mixes the two approaches in a suboptimal way. Your Board class is intended to be an interface, but it tries to implement a common representation as well. The problem with this approach is that it forces subclasses to carry the same data, which often turns out to be unnecessary and burdensome — the square representation used in Board may not turn out suitable for all boards, for example. (See also C.121)

To solve this problem, we first destroy the interface nature of Board, and rename it to reflect that it only serves as a helper for implementing square boards:

class RectangularBoardBase /* : public Board */ {
public:
    explicit RectangularBoardBase(std::size_t size_);
    // default implementations that subclasses can inherit
    // if they do not require special treatment
    void display() const /* override */;
    bool is_valid(Point) const /* override */;
    // ... queries, accessors, modifiers ...
protected:
    using Representation = std::vector<std::vector<Piece>>;
    // ... implementation helpers ...
private:
    std::size_t size;
    Representation pieces;
};

note that the special member functions are gone, and that display has been reduced to an ordinary member function in case you have a default rectangular display (you can get rid of it altogether if there is no default display, as is the case with your original code, where you leave display pure virtual).

After this point, the solutions are slightly different for the two approaches.

---

Approach 1 — templates

Board types derive from RectangularBoardBase if it is helpful, or, for non-rectangular boards, start from scratch. For board types that implement their own display, like HexBoard, simply ignore the display from the base class. The board types are related by the common interface that you decide without the presence of a common base class.

For maintenance, you can make a concept (since C++20) or add a set of old-style static_asserts to your tests to make sure that board types implement the common interface.

The board type becomes a template parameter of State, and State stores the Board directly.

---

Approach 2 — virtuals

Make the interface class an abstract class with pure virtuals only:

class Board {
public:
    virtual void display() const = 0;
    virtual bool is_valid(Point) const = 0;
    // ... other common virtuals, if necessary ...
    virtual ~Board() {}
protected:
    Board() = default;
    Board(const Board&) = default;
    Board& operator=(const Board&) = default;
};

RectangularBoardBase derives from Board, and board types then indirectly derive from this interface and implement the virtual methods accordingly:

class HexBoard : public RectangularBoardBase {
public:
    // ...
    using RectangularBoardBase::RectangularBoardBase;
    // own version of display
    void display() const override;
    // inherit existing is_valid
private:
    //...
};

Alternatively, a board type may derive directly from Board and start from scratch if RectangularBoardBase is unhelpful:

class EmptyBoard : public Board {
public:
    Emptyboard() = default;

    void display() const override {
        std::cout << "nothing\n";
    }
    bool is_valid(Point) const override {
        return false;
    }

    // ...
};

State contains a std::unique_ptr<Board>, and accesses the board through dynamic dispatch.

---

Miscellaneous issues

std::vector<std::vector<Piece>> is not a compact representation — it stores the pieces noncontiguously, allows jagged boards, and introduces double allocation and double indirection overhead. The usual solution is to flatten the representation into a std::vector<Piece> and calculate indexes on the fly.

You seem to have the habit of writing out special member functions (copy/move constructors/assignment operators) manually, which is not necessary. Leave them out, and the compiler will be able to synthesize optimal versions of them on its own. An exception is when a virtual destructor is present — ideally, this should only happen in an abstract base class, where the issue is resolved as I demonstrated above.

Instead of int, use std::size_t to store indexes and dimensions. Also, it seems unnecessary to have both (Point) and (int, int) overloads — I'd keep the first.

Is there a specific reason why White is considered the default piece? If there isn't, I'd consider mandating the Piece argument in the constructor of State.

Consider making display take an std::ostream& argument for extra flexibility. Instead of char arrays, you can use std::string_view (C++17) for more type safety. Instead of endl, consider using \n to avoid unnecessary performance drop due to gratuitous flushing (std::endl vs \n).

---

Last, all of the design choices I presented here are general guidelines only, and the details may have been somewhat arbitrary. Since you have a much more comprehensive grasp of your project, feel free to make modifications and adapt them to your needs as appropriate.