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++.