使用C++进行通用Alpha Beta搜索

Question

我正在尝试设计一个函数模板来搜索任何游戏的最佳移动 - 当然这个函数模板的用户必须实现一些游戏特定的功能.我想要做的是用功能模板推广alpha beta搜索算法.

此函数模板的声明如下所示:

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

除其他功能外,该功能还包括:

• 确定游戏是否已结束: bool EndGame(g)
• 评估游戏状态: int Evaluate(g)
• 获得可能的举措: std::vector<Move> moves = GetMoves(g)
• 采取行动: Gamestate gnew = MakeMove(g, moves[i])

你认为这个函数有很多模板参数吗？有没有办法减少参数的数量？一个想法是使用评估游戏状态或决定游戏是否结束的成员扩展GameState类.但是alpha beta搜索树包含很多Gamestate实例,可能导致不必要的内存需求,因此我喜欢将Gamestate保持在较小的状态.一般来说,功能模板实际上是正确的吗？

Answer 1

您可以定义一个抽象的界面,例如game_traits,并为每个游戏设置专门的game_traits实现:

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);
  ...
}

请参阅C++标准库中的char_traits如何在那里使用它.

或者,你可以使它们只是Game类的方法,你不需要从一些抽象类继承,因为你提供它作为模板参数.当你的模板函数试图访问时,你会发现一个,也许不那么透明的编译错误,例如game.has_ended(),当没有这样的方法时.这种机制在标准模板库中也经常使用.

顺便说一句,有一个新的功能计划为此; 概念:

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();
  ...
}

不幸的是,概念被推迟到标准的未来版本,并且还没有出现在c ++ 0x :(