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 State
s 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 State
s 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
- 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 defineBoard
as a template and specialize it for different games as I don't think there is a need for dynamic binding. - Define
State
as a plain class that contains a smart pointer toBoard
. 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?