artificial-intelligence - 效用函数极小极大搜索

Question

嗨，我很困惑如何使用 minimax 搜索来确定效用函数 用任何可以使用 minimax 搜索的游戏来解释它 基本上我在问你如何确定效用函数 Cheers

Answer 1

效用值只是玩家在游戏中到达某个状态时收到的一些任意值。例如，在井字游戏中，您的效用函数可以简单地为 1 表示获胜，0 表示平局，或 -1 表示失败。对此运行 minmax 最多只能找到一组导致 1（获胜）的动作。

另一个例子是国际象棋（不是说你可以在国际象棋游戏中运行极小极大）。假设您的效用函数来自某个数字，该数字基于您捕获或丢失的物品的价值

Answer 2

确定某一状态下移动的效用值与程序员的经验和他/她对游戏的知识有关。
终端状态的效用值很容易确定。例如，在井字游戏中，玩家 X 的最终状态是当 X 以对角线、垂直或水平对齐时。创建这种状态的任何移动都是最终状态，您可以创建一个检查该状态的函数。如果是终端状态，则函数返回 1 或 -1。如果您的玩家代理是玩家 X，并且在玩家 X 移动后它确定玩家 O 将获胜，则该函数返回 -1。如果该函数确定这是自己的获胜棋步，则该函数返回 1。如果所有单元格都被最后可能的移动占据并且没有人获胜，则该函数返回零。

这仅在终端状态。评估中间状态至关重要，因为即使在 3x3 游戏中，也有很多组合需要考虑。如果你包括对称动作，你有 9！井字游戏中的可能状态。对于那些中间情况，您需要提出一个评估函数，该函数返回每个状态与其他状态相关的分数。

假设我分配了终端状态值 810、0 和 -810。对于每一步，分数将为 810 /（移动数）。因此，如果我在 6 步中达到最终状态，分数将为 810/6 = 135。在 9 步中，分数将为 90。以这种方式构建的评估函数将有利于更快地达到最终状态的移动。但是，它仍然评估为叶节点。不过，我们需要在到达叶节点之前进行评估，但这也可能是评估函数的一部分。假设在下面的游戏中，玩家 1 是 X。所以 X 下一步行动。以下是 X 的合法移动（行、列）： (1) 0,0 (2) 0,2 (3) 2,0 (4) 2,1 (5) 2,2

| |O| | |O|X|X| | | | |

每一步的效用值应该有利于最好的移动。在这种情况下，最好的移动是（2）或（5）。因此，评估函数将分配一个效用值 81，例如分配给其中的每一个。移动 (4) 对 X 玩家来说是最糟糕的移动（并且还可以保证你输掉与聪明玩家的游戏），因此该函数将为该移动分配 -9 值。移动（1）和（3）虽然不理想，但不会让你输，所以我们可以指定一个 1。
所以当 minimax 评估这 5 个移动时，因为你的玩家 X 是最大的，选择将是（2）或 (5)。

如果我们专注于选项（2）或（5），游戏将在这两个动作之后处于终止状态。因此，在现实中，评估函数应该比当前的合法移动提前 2 步来返回效用值。（此策略遵循深度有限搜索的路线，您的函数在某个深度进行评估并产生效用值而不到达叶节点或终端状态）

现在我将回到我的第一个陈述。效用值将由根据程序员的游戏知识编码的评估函数确定。

希望我不会让你感到困惑......