Solving a game in C++

Question

I wrote a game solver similar (but with reduced features) to an application called GamesmanClassic but in C++. The general idea is that (roughly speaking) board games can be represented with the four following functions:

initial_position    -> Starting board position
generate_moves(pos) -> Generate all valid moves given a position.
do_move(pos, move)  -> Given a position perform a valid move on it.
primitive           -> Check if the game is over.

Using these methods a game tree can be generated that traverses every possible state. Then one can go back up the tree to determine if player 1 wins a game. (Well, it can do more than that, but that's all I have my program do.)

I implement the four functions for a game called four to one. The game four to one works by starting off with four balls. The first player may choose to take away 2 or 1 balls, then the second player may do the same. This is repeated until there are no balls left. Whoever can't make a move looses.

Here is the C++ code I wrote:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

enum Status {
    /**
       Is a particular position a WIN, LOSS, TIE, or is it not
       immediately obvious (UNDECIDED).
    */
    WIN,
    LOSS,
    TIE,
    UNDECIDED
};

Status reduce_statuses(std::vector<Status> children) {
    /**
       Takes statuses and reduces them to (ultimately) determine
       a parent node's status.
       To illustrate say we have a portion of a game tree:
                P1       A
                       /   \
                P2    B     C
       Say that we don't know A's status, but B is a WIN for P2
       and C is a LOSS for P2. At position A, P1 can go down and
       choose position C forcing P2 to lose (and P1 to win).
       In general if there is one losing position, the current 
       player can go down it. If there is no losing position then
       the current player must lose.
    */
    auto tie = find(children.begin(), children.end(), TIE);
    if (tie != children.end()) return TIE;
    //Check if there is a loss in the children.
    auto loss = find(children.begin(), children.end(), LOSS);
    if (loss != children.end()) return WIN;
    return LOSS;
}

std::string to_string(Status s) {
    /**
       Convert a status to a string representation.
    */
    switch (s) {
        case WIN:       return "WIN";
        case LOSS:      return "LOSS";
        case TIE:       return "TIE";
        case UNDECIDED: return "UNDECIDED";
    }
}

template <class P, class M> // Movement, or action on a board
class Game {
    /**
       Abstract class that describes an Abstract Two Player
       Strategy Game.
       initial_position: The start state of the board game.
       generate_moves: Generate all valid moves given a 
       particular board state.
       do_move: Given a position, perform a move on that 
       position.
       primitive: Test if the game is over.
    */
    public:
        virtual P initial_position() = 0;
        virtual std::vector<M> generate_moves(P position) = 0;
        virtual P do_move(P position, M move) = 0;
        virtual Status primitive(P position) = 0;
};

class FourToOne : public Game<int, int> {
    /**
       Implementation of the game FourToOne.

       Description of Game:
       Imagine you and a friend are playing with 4 balls.
       You go first and may either take 1 or 2 away.
       Then your friend goes and can take 1 or 2 away.
       This is reapeated until there are no balls left.
       Who ever cannot make a move looses.
    */
    public:
        FourToOne() : Game() {}
        int initial_position();
        std::vector<int> generate_moves(int position);
        int do_move(int position, int move);
        Status primitive(int position);
};

int FourToOne::initial_position() {
    /**
       Start the game at 4.
    */
    return 4;
}

std::vector<int> FourToOne::generate_moves(int position) {
    /**
      Generate the moves for FourToOne.
      You can either decided to take 2 or 1 away from the board
      unless you are at 1 (in which case you can only take 1
      away), or when you are at 0 (you lost).
      Note: Moves have been represented as negative integers i.e.
      -1 -> take one away
      -2 -> take two away
    */
    std::vector<int> moves(0);
    if (position == 1) {
        moves.push_back(-1);
        return moves;
    } else if (position == 0) {
        return moves; // No moves!
    } else {
        moves.push_back(-1);
        moves.push_back(-2);
        return moves;
    }
    // Should really never get here...
    return std::vector<int>();
}

int FourToOne::do_move(int position, int move) {
    /**
      Perform a (valid) move on a given position.
      Moves are either -1 or -2, so adding it to the current
      board position gives a new position.
    */
    return position + move;
}

Status FourToOne::primitive(int position) {
    /**
      It is obvious a game is over when you are at 0, return 
      a LOSS.
      Otherwise, we can't tell immediately (in which case
      return UNDECIDED).
    */
    if (position == 0) return LOSS;
    return UNDECIDED;
}

template <typename P, typename M>
Status solve_pos(Game<P, M>& game, P position) {
    /**
      Solve a game at a particular position.
      (Assume it is from P1's perspective)
    */
    // If the position can be trivial solved, we are done.
    if (game.primitive(position) != UNDECIDED) {
        return game.primitive(position);
    }
    // Otherwise we must recurse downward!
    std::vector<Status> children_statuses;
    for (P& move : game.generate_moves(position)) {
        children_statuses.push_back(
                solve_pos(game, game.do_move(position, move)));
    }
    return reduce_statuses(children_statuses);
}

template <typename P, typename M>
Status solve(Game<P, M>& game) {
    /**
      Determine whether it is a WIN, LOSS, or TIE for P1.
    */
    return solve_pos(game, game.initial_position());
}

int main() {
    /**
      Launches the game FourToOne and then sovles it.
    */
    FourToOne game = FourToOne();
    std::cout << to_string(solve(game));
    return 0;
}

The resulting code prints out WIN as P1 can always win.

I am not too particularly concerned about speed, as I plan to make optimizations later (including threading and memoization). I am mostly concerned about writing idiomatic C++.

Answer 1

Avoid making a copy of the vector

Status reduce_statuses(std::vector<Status> children)

Here you're making a copy of the vector you pass in. That's completely unnecessary, better pass by const reference:

Status reduce_statuses(std::vector<Status> const & children)

Isn't a Game const? What is it, either way?

When you call, for example Game::initial_position() or Game::generate_moves(pos) twice with the same arguments (if any), do you expect any change in the outcome?

I'd say no. State is handled by your "solver", not by the game. Thus I'd recommend making this a bit more explicit by making these member functions const:

virtual P initial_position() const = 0;
virtual std::vector<M> generate_moves(P position) const = 0;
virtual P do_move(P position, M move) const = 0;
virtual Status primitive(P position) const = 0;

But a class with only virtual const member functions looks ... like a bit too much of an OOP dose to me. What a game actually is is ...

[..] The general idea is that (roughly speaking) board games can be represented with the four following functions [..]

... a "collection" of 4 functions. Why not represent it as such, then?

template<typename InitialFn,
         typename GenerateFn,
         typename DoMoveFn,
         typename PrimitiveFn>
struct Game {
  InitialFn initial_position;
  GenerateFn generate_moves;
  DoMoveFn do_move;
  PrimitiveFn primitive;
};

Now you don't need a class for each game. A single distinct game is just an object of (an instance of) above Game. This makes also sense when you think about what FourToOne{} == FourToOne{} should return in your original design (even if not implemented, it's more about the idea of equality).

I made another "radical" change above: Weakening the requirements on these functions. Why should we force a game to actually return a vector of moves in generate_moves when (for example) a set makes more sense for that particular game?

Solving a position remains basically the same:

template <typename Game, typename Position>
Status solve_pos(Game game, Position position) {
    // If the position can be trivial solved, we are done.
    auto status_of_position = game.primitive(position);
    if (status_of_position != UNDECIDED) {
        return status_of_position;
    }
    // Otherwise we must recurse downward!
    std::vector<Status> children_statuses;
    auto const moves = game.generate_moves(position);
    std::transform(std::begin(moves), std::end(moves),
                   std::back_inserter(children_statuses),
                   [] (auto const & move) {
                     return solve_pos(game,
                                      game.do_move(position, move)); });
    return reduce_statuses(children_statuses);
}

I'm using std::transform instead of the for loop because it better expresses what we're doing: Transforming the contents of one container (moves) and storing the results in another one (children_statuses). Also, with C++17 and its execution policies this might enable easy parallelization.

find and != container.end()

auto tie = find(children.begin(), children.end(), TIE);
if (tie != children.end()) return TIE;

This combination can be expressed differently:

if (std::any_of(std::begin(children), std::end(children),
                [] (auto const & child) { return child == TIE; })) {
    return TIE;
}

This, too, allows for use of execution policies. Too me it more clearly expresses the intent, too, but YMMV.

Use the free functions std::begin and std::end

Almost forgot this. Don't use container.begin(). Better is std::begin(container). For a few reasons why see this stackoverflow question.