6

I am currently developing a simple AI for Othello using minimax and alpha-beta pruning.

My question is related to the evaluation function for the state of the board.

I am currently looking to evaluate it by looking at:

  1. Disc count (parity)

  2. Number of legal moves

  3. Importance of particular positions

So lets say the root node is the initial game state. The first action is the the AI's action while the second action is the opponent's action.

                   0    
                  / \           AI's Action
                 1   1
                / \   \         Opponent's action
               2   2   2

At node level 1, do I evaluate the disc count of my AI's chips and the number of legal moves it can make at the point of time after it has completed an action?

At node level 2, do I evaluate the disc count of the opponent's chips and the number of legal moves it can make at the point of time after the opponent has completed an action?

Meaning AI move -> Opponent move ==> At this point of time I evaluate the opponent's disc count and the number of legal the opponent can make.

4

2 回答 2

10

生成游戏树时，不应评估节点，除非它是叶节点。也就是说，您生成一棵树，直到第 N 级（对应于在棋盘当前状态之前进行 N 次移动的棋盘），除非您已到达对应于游戏结束情况的节点。只有在这些节点中，您才应该使用评估函数评估棋盘游戏的状态。这就是极小极大算法的意义所在。我知道在每个玩家移动后评估节点的唯一情况是 迭代加深算法，这似乎你没有使用。

评估功能负责提供对特定位置的“分数”的快速评估——换句话说，哪一方获胜以及获胜多少。它也被称为静态评估函数，因为它只查看特定的板配置。所以是的，当你达到 N 级时，你可以计算计算机和用户可能的移动并减去它们。例如，如果结果为正，则表示计算机具有优势，如果结果为 0，则表示平局，如果结果为负，则表示用户在移动性方面处于劣势。对代表游戏板配置结束的节点进行评分是微不足道的，如果你赢了就分配一个最大值，如果你输了就分配一个最小值。

移动性是大多数棋盘游戏（有价值的棋盘游戏）评估功能中要考虑的最重要特征之一。为了评估它，你计算给定静态棋盘配置的每个玩家可能的移动，无论接下来轮到谁。即使一个玩家最近做了一个动作，当同一个玩家做出最后一个动作（因此，在相同的条件下对它们进行评分）时，您也会在树的同一级别 N 中给棋盘打分，并选择那些具有最佳得分。

您在评估中考虑的功能非常好。通常，您想在它们非常有价值的游戏中考虑材料和移动性（您是）（尽管，我不知道材料是否总是在奥赛罗中的优势，您应该更了解它，因为它是您的游戏正在努力）争取获胜的局面，所以我想您走在正确的道路上。

编辑：小心！在叶节点中，您唯一要做的就是为板配置分配特定分数。它在其父节点中返回该分数并与其他分数（对应于其他子节点）进行比较。为了选择对特定玩家可用的最佳移动，请执行以下操作：如果父节点对应于对手的移动，则选择具有最小（最小）值的移动。如果轮到计算机移动，则选择具有最高（最大值）值的分数，以便它代表该玩家可能的最佳移动。

于 2012-09-09T04:19:49.767 回答
5

结束游戏评价功能

如果您的搜索达到一个完整的棋盘，那么评估应该简单地基于光盘数来确定谁赢了。

中局评价功能

合法移动的数量在开局和中期很有用，因为对你来说大量的移动（而对对手来说很少）通常表明你有很多稳定的棋子你的对手无法攻击的好位置，而对手的位置不好，他们可能会用尽所有动作并被迫下一个糟糕的动作（例如让你在角落里玩）。

为此，在计算移动时轮到谁并不重要，所以我认为你走在正确的道路上。

（请注意，在游戏的早期阶段，拥有较少棋子的人通常是一个优势，因为这通常意味着您的对手几乎没有安全动作。）

随机评价函数

曾几何时，我听说只对奥赛罗评估函数使用随机数（令我惊讶的是）也是一个完全合理的选择。

逻辑是，拥有最多选择的玩家将能够引导游戏获得最高的随机数，因此这种方法再次意味着 AI 将偏爱给它提供很多选择的动作，而他的对手则很少。

于 2012-09-08T21:51:03.490 回答