1

I was wondering if anyone could help me go through this question. I looked up the Min Max theory, but I still don't know how to apply this concept to this question below.

The following tree represents possible moves in a competitive game, showing that player X currently has a choice between move A and move B. Following the move of player X, player Y is allowed to select a move, and then player X is allowed to select the last move of the game. The leaf nodes of the tree are labeled W, L, or T, depending on whether that ending represents a win, loss, or tie for player X.

Use the min-max search to determine if player X should move A or B to obtain the best result X can expect.

enter image description here

To review min-max search, see http://www.nada.kth.se/kurser/kth/2D1350/progp02/lecture2.pdf

Player X should move A.

Player X should move B.

4

1 回答 1

2

我为节点添加了数字，并突出显示了“最大”行。未突出显示的行是“最小”行（即玩家想要最小化结果）。显然，L 是最低值，W 是最高值。我们通常将 1 分配给胜利，将 -1 分配给失败，将 0 分配给平局。玩家 Y 想要使数字尽可能低（如果玩家 X 得到 L，他们就赢了）。玩家 X 想让数字尽可能高（他想要 W）。

在此处输入图像描述

如果游戏进行到节点 4，您知道玩家 X 无论如何都会赢。因此，4 标记为 W（或 1）。如果游戏进行到节点 5，你知道他输了，所以它被标记为 L。6 也会发生同样的情况（它得到一个 W）。

要分配给节点 2，我们注意到 2 位于“最小”行（轮到玩家 Y）。4、5、6，分别有W、L、W。玩家 Y 可以通过选择节点 5 来最小化这一点，从而获胜。因此，玩家 X 知道，如果玩家 Y 聪明，那么玩家 X 选择 A 就会输。

我们可以在另一边做同样的事情来证明如果玩家 X 选择 B，他会打平。因此，玩家 X 应该选择 B。

当为 minimax 编写代码时，代码会执行后序树遍历，并通过查看后代为节点分配值。

于 2015-04-22T04:24:59.560 回答