使用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的小型化。总的来说，函数模板是否真的是正确的方法？

- Christian Ammer

---

我对一个需要六个不同类的模板函数感到惊讶，但是我对这个问题的答案很感兴趣，所以给个赞。:) - Jakob Borg

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()等不存在的方法时，您将只会得到一个可能不太透明的编译错误。这种机制在标准模板库中也经常使用。

顺便说一下，这里曾计划有一项新功能;概念（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();
  ...
}

很遗憾，C++0x标准中的“概念（Concepts）”已经被推迟到未来版本，目前还无法使用 :(

- wich

---

谢谢你提供抽象接口（game_traits）的提示，我需要了解一下它以及STL如何使用这个概念。 - Christian Ammer

Answer 2

向类中添加方法并不会使该类的对象变得更大。这些方法只在整个类中存储一次，并被任何实例的调用使用。因此，将函数添加到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作为参数）。因此，当声明模板时，编译器不会搜索这些名称的实际定义（因为它还不知道这些函数应该具有什么类型，因为GameState尚未指定）。

只有在实例化模板时，这些函数的重载才需要可用，以适应它们在模板中使用的方式。

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
}

这样，您就可以将任何GameState对象适应到您的算法中，而无需在这些对象上要求特殊方法。为了避免使用这些新函数来污染全局名称空间，您可以将它们放入自己的命名空间或特征类中。

所以基本上只要正确名称和类型的函数在实例化模板时被定义，您就可以省略其他附加的模板参数。

- sth

---

如果我将getMoves、endGame函数放在一个命名空间中，那么alphaBetaMax函数需要知道这个命名空间吗？仅为清晰起见：Move必须是一个模板参数（它是特定于游戏的），因为你只声明了GameState作为模板参数。到目前为止，我还不知道traits的概念，感谢所有人的提示。 - Christian Ammer

关于命名空间：想法是将这些函数放在 alphabeta 命名空间中，并让算法使用该命名空间中的函数。此外，当为新的 GameState 类型实现新函数时，请将它们放入 alphabeta 命名空间中。这样，所有特定于此算法的辅助函数都被限制在自己的命名空间中。 - sth

我会说这取决于情况，你可以把它们放在alphabeta命名空间中，或者就放在MyGameState旁边（因为它本身就有自己的命名空间，对吧？）。我认为更自然的做法是将它们与MyGameState一起放置，因为它们扩展了其接口。此外，我们应该考虑基于实际成员函数提供默认实现方法，以便简化开发 :) - Matthieu M.

Answer 3

据我所理解，我会稍微概括一下这个想法：

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

我有意将特征和策略区分为不同的类型。正如Boost的泛型编程技术中所解释的那样，特征通常携带类型信息，即类型属性的描述。这个想法非常适合携带静态信息，例如游戏状态。策略提供行为——MakeMove是游戏动态行为算法的一部分。

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

- mloskot

Answer 4

个人而言，我会这样写：

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之外的每个指针（我假设这是您的函数返回结果的位置，其他所有内容都是临时的？）。

现在更好的方法是传递只能完成所有操作的一个类，因为“进行移动”，“获取移动”，“评估”它们都是相同逻辑的一部分。没有理由制作5个不同的类，C++允许您在一个类中覆盖多个虚拟函数。

- Blindy

---

我的意图是设计一个通用方法，就像 STL 算法一样。但也许通用方法的缺点（6 个模板参数）会让我使用一个抽象的 GameState 基类。 - Christian Ammer

Answer 5

太多了吗？为什么还要用模板呢？这正是要小心处理模板时会出现的“无限使用锤子打钉子”类型的问题。尤其是像 AI 这样大部分问题都难以解决且性能至关重要的领域。

- Charles Eli Cheese

---

我喜欢像STL算法一样以通用的方式解决问题的想法。我为一个简单的井字棋游戏编写了Alpha-Beta搜索，现在我想将这个搜索变成通用的，以便用于其他游戏。对我来说，模板概念似乎是一个有前途的方法。 - Christian Ammer

你正在泛化什么呢？如果某个东西是一个类，那么它总是可以以其他方式泛化的。如果你有每个参数的两种类型，你将生成64个模板，这些模板将不断地互相推出缓存。当你需要在某个项目上拥有无限的泛型性并且它与其他项目没有任何共同点时，模板才是有用的。比如数据结构。对于此，它根本没有任何用处。 - Charles Eli Cheese

Answer 6

天真的问题：游戏状态评估和“游戏已结束”决策不应该是游戏状态类中的附加方法（您写的是成员），因此不会占用额外的每个实例内存吗？只是问一下...

- Pascal Cuoq

---

我不是很了解C++，但我认为除了类之外的所有内容都需要一些内存。例如，井字游戏的GameState可以仅由一个int表示。 - Christian Ammer

不，一旦您决定拥有一个真正的类（即除了Tic Tac Toe之外），额外的方法就不会有任何每个实例的内存成本。非虚拟方法被编译为函数调用。虚拟方法在方法表中引用，这是正确的，但是对于该类只有一个这样的表。所有实例都只是使用指向它的指针。 - Pascal Cuoq