c++ - 使用 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 类评估游戏状态或决定游戏是否结束。但是一个阿尔法贝塔搜索树包含大量 Gamestate 实例，这可能会导致不必要的内存需求，因此我喜欢保持 Gamestate 小。一般来说，函数模板实际上是正确的方法吗？

Answer 1

您可以定义一个抽象接口(interface) 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();
  ...
}

不幸的是，Concepts 已被推迟到标准的 future 版本中，并且不会出现在 c++0x 中:(