用C++通用α-β搜索

您可以定义一个抽象接口,如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++标准库中的字符特征。

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中:(

就我所能理解的观点而言,我会将一些事情进行汇总:

• GameState、EndGame、GetMoves、Evaluate-使用单一特征类型GameStateTraits包装
• MakeMove是独立算法的职责,因此GameMovePolicy

我故意将特质和政策区分为不同的类型。正如Boost的 Generic Programming Techniques ,特征通常携带类型信息,即类型属性的描述。这个想法非常适合携带静态信息,一种游戏状态。策略提供行为-MakeMove是游戏动态行为算法的一部分。

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

向类添加方法不会使该类的对象变大。这些方法为整个类存储一次,并由对任何实例的调用使用。因此,将函数添加到GameState类不会导致算法需要更多内存。

然后,函数模板只需要一个参数 GameState 而作为此参数使用的类将需要实现正确的方法。

更灵活的方法是在算法中简单地使用自由函数:

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

在这里 endGame 和 getMoves 是依赖名称,它们依赖于模板参数(因为 g 作为参数)。因此,在声明模板时,编译器不会搜索这些名称的实际定义(它还不知道这些函数应该具有什么类型) 配子状态

仅当模板被实例化时,这些函数的重载才需要可用,以适合它们在模板中的使用方式:

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
}

通过这种方式,您可以使任何游戏状态对象适应您的算法,而无需对这些对象使用特殊方法。为了避免这些新函数污染全局名称空间,可以将它们放入它们自己的名称空间或traits类中。

因此,基本上您可以省略其他模板参数,只要在实例化模板后定义了正确名称和类型的函数。

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

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

函数本身会删除除gamestate之外的所有指针(我假设这就是函数返回结果的地方,其他的都是临时的?)。

现在做这一切更好的方法是只通过一个可以做任何事情的类,因为“makemove”,“getmove”,“evaluate”,它们都是相同逻辑的一部分。没有理由做5个不同的类,C++允许你重写类中的一个以上的虚拟函数。

太多了为什么它是一个模板呢?这正是使用模板时需要注意的那种“用无限的锤子敲钉子”。特别是像人工智能这样的东西,大多数问题在很大程度上难以解决,性能至关重要。

方法 成员 )在gamestate类中,因此不占用额外的每个实例内存?只是问。。。