Generic Alpha Beta Search with C++

Question

I'm trying to design a function template which searches for the best move for any game - of course the user of this function template has to implement some game specific functions. What i'm trying to do is to generalize the alpha beta search algorithm with a function template.

The declaration of this function template looks like this:

template<class GameState, class Move,
         class EndGame, class Evaluate, class GetMoves, class MakeMove)
int alphaBetaMax(GameState g, int alpha, int beta, int depthleft);

Among other things the function has to:

• Determine if a game has ended: bool EndGame(g)
• Evaluate the state of a game: int Evaluate(g)
• Get the possible moves: std::vector<Move> moves = GetMoves(g)
• Make a move: Gamestate gnew = MakeMove(g, moves[i])

Do you think the function has to many template arguments? Is there a way to reduce the number of arguments? One idea is to extend the GameState class with members that evaluate the gamestate or decide if the game has ended. But a alpha beta search tree contains a lot of Gamestate instances which may leads to unnecessary memory requirements, thus i like to keep Gamestate small. In general, is a function template actually the right way?

Answer 1

Naive question: shouldn't the gamestate evaluation and "game has ended" decision be additional methods (you wrote members) in the gamestate class, and thus occupy no additional per-instance memory? Just asking...

Answer 2

Personally I'd write this as:

int alphaBetaMax(GameState *g, Move *move, EndGame *endgame, 
    Evaluate *evaluate, GetMoves* getmoves, MakeMove* makemove, 
    int alpha, int beta, int depthleft);

You'd call it as:

GameState gs;
alphaBetaMax(&gs, new ChessMove(), new ChessEndGame(), new ChessEvaluate(),
    new ChessGetMoves(), new ChessMakeMove(), a, b, 40);

The function itself would delete every pointer but gamestate (I'm assuming that's where your function returns the result, everything else is temporary?).

Now an even better way to do all this is to pass just one class that can do everything, since "make move", "get move", "evaluate", they're all part of the same logic. There's no reason to make 5 different classes, C++ allows you to override more than one virtual function in a class.

Answer 3

You could define an abstract interface say game_traits and have specialized game_traits implementation for each game:

template<typename Game>
class game_traits {
  ...
};

class Chess {
  ...
};

template<>
class game_traits<Chess> {
  static bool endGame(Chess game);
  ...
};

template <typename Game, typename traits = game_traits<Game> >
int alphaBetaMax(Game game, int alpha, int beta, int depthleft) {
  ended = traits::endGame(game);
  ...
}

See char_traits in the C++ standard library how it is used there.

Alternatively, you could make them just methods of the Game classes, you don't need inheritence here from some abstract class since you supply it as a template argument. You will just get a, perhaps not so transparent, compile error when your template function tries to access, say game.has_ended(), when no such method exists. This kind of mechanism is also used a lot in the standard template library.

btw, there was a new feature planned for this; Concepts:

auto concept GameType<typename Game>
{
  bool has_ended(Game&);
  ...
};

template<typename Game> requires GameType<Game>
int alphaBetaMax(Game game, int alpha, int beta, int depthleft) {
  bool ended = game.has_ended();
  ...
}

Unfortunately Concepts have been postponed to a future version of the standard and will not yet appear in c++0x :(

Answer 4

As far as I can understand the idea, I would aggregate things a bit:

• GameState, EndGame, GetMoves, Evaluate - wrap with single traits type GameStateTraits
• MakeMove is a responsibility of separate algorithm, so GameMovePolicy

I intentionally distinguish traits and policy as separate type. As it's explained in Boost's Generic Programming Techniques, traits usually carry type information, a description of type properties. This idea fits well to carry static information, a game state. Policy provides behaviour - MakeMove is a part of game dynamic, behavioural algorithm.

template<typename GameStateTraits, typename GameMovePolicy>
int alphaBetaMax(GameStateTraits const& state, int alpha, int beta, int depthleft);

Answer 5

Adding methods to a class doesn't make objects of that class bigger. The methods are stored once for the whole class and used by calls on any instances. Therefore adding the functions to the GameState class would not cause the algorithm to require more memory.

The function template then would only require the single parameter GameState and classes used as this parameter would be required to implement the right methods.

A more flexible approach would be to simply use free functions in the algorithm:

template<class GameState>
int alphaBetaMax(GameState g, int alpha, int beta, int depthleft) {
   if (endGame(g)) {
     return 1;
   }
   std::vector<Move> moves = getMoves(g);
   // ...   
}

Here endGame and getMoves are dependent names, they depend on the template parameter (since they take g as a parameter). Therefore the compiler won't search for actual definitions of these names when the template is declared (it doesn't know yet what type these functions should have since GameState is not specified yet).

Only when the template is instantiated the overloads for these functions need to be available that fit the way they are used in the template:

struct MyGameState {};

bool endGame(const MyGameState &st) {
  return false;
}

std::vector<Move> getMoves(const MyGameState &st) {
  // ...
}

void tst() {
  MyGameState s;
  alphaBetaMax(s, 1, 1, 1); // uses the new functions
}

This way you can adapt any GameState object to your algorithm without having to require special methods on these objects. To avoid polluting the global namespace with these new functions you could put them into their own namespace or a traits class.

So basically you can just leave out the additional template parameters, as long as functions of the correct names and types will be defined once you instantiate the template.

Answer 6

Too many? Why is it a template at all? This is exactly the kind of 'hitting a nail with infinite hammers' you need to be careful of with templates. Especially something like AI where most problems are largely intractable and performance is crucial.