1

所以我最近在研究零和游戏中使用的极小极大函数。我完全理解它，除了如何为实际功能实现板：

例如，我发现的这个示例实现有这个声明：

int miniMax(Board eval, int iterations)

我唯一的问题是到底是Board什么？它是结构、类、数组还是其他结构？另外，我将如何为 mini-max 实现示例板，例如井字游戏板（例如）？在维基百科或谷歌上找不到任何东西。

4

2 回答 2

3

棋盘只是当前的棋盘游戏。它可以是您用来代表游戏棋盘的任何结构。

当第一次调用时，minimax 函数将接收当前棋盘配置，由到目前为止所做的不同游戏（游戏的当前状态）达到。在 minimax 函数中，您所做的是修改棋盘，每个修改都应代表根据游戏规则的可能移动。每个修改过的板都应该作为参数传递给新的 minimax 调用。一旦达到一定的深度（即多次迭代），您就可以使用评估函数选择最佳移动，为每个修改过的棋盘打分，然后选择得分最高的棋盘。

您正在阅读的算法是通用的，适用于任何游戏。您可以根据方便来定义棋盘，即最适合您要表示的游戏的棋盘。

对于井字游戏，您可能希望用 3x3 数组表示棋盘，以便更改棋盘：

int miniMax(char board[3][3], int iterations)

或者，您可能希望为每个正方形使用 2 位来表示您的电路板：

typedef struct {
    unsigned square1: 2;
    unsigned square2: 2;
    unsigned square3: 2;
    unsigned square4: 2;
    unsigned square5: 2;
    unsigned square6: 2;
    unsigned square7: 2;
    unsigned square8: 2;
    unsigned square9: 2;
} Board;

不过，对于井字游戏，您不需要轻量级的棋盘表示，因为它的最大深度仅为 9。我只是给您提供示例，让您了解它可以是您用来表示棋盘游戏的任何结构。

如果您要处理极小极大函数并且游戏比井字游戏复杂得多，您应该认真考虑使用alpha-beta 剪枝，这是一个很大的改进。

编辑：我认为你不应该称你的董事会为“eval”，因为这可能与完全不同的评估函数混淆。

于 2012-07-25T04:08:27.113 回答
2

正如您所写的那样，板只是用于极小极大值和许多其他决策树算法的常见结构。

它旨在成为包含有关游戏特定状态的信息的结构。在算法本身中，从逻辑的角度来看，这个参数应该是不可修改的，因为您将在棋盘上进行移动并生成新的棋盘快照（因此旧的棋盘快照不会被修改），而您正在深入树您正在评估的动作以找到更好的策略。

事实上，在棋盘内部有两个元素是很有用的：一组规则（您可以通过移动来有效地修改其状态）和一个状态，它将在每次迭代中发生变化（即使棋盘本身仍然是相同），并且该对象将用于评估玩家的移动有多好（当达到最大深度时，您被迫仅通过状态来估计移动的好坏）。

所以它可以是任何东西，它只是一个概念参数。如果您真的想要更实用的东西，我会以类似于以下方式想象它：

class BoardSnapshot {
  Board b;

  float alpha;    
  State state;
  int evaluate();
}

class Board {
  List<Players> players;
  List<Rules> rules;

  State applyMove(State current, Player player, Rule rule, params ...);
}

这样您就可以BoardSnapshot使用没有当前状态的状态对其进行初始化，然后应用规则并生成一个新状态，该状态将是当前选择的树枝的快照。

于 2012-07-25T03:06:13.310 回答