《Nim》是一款双人游戏,玩家轮流移动。一开始,玩家会拿到几堆木棍。每一摞可以有任意数量的木棍。在每一回合中,玩家可以从一摞纸牌中取出任意数量的木棍。玩家必须从牌堆中取出至少一根木棍,也可以取出整个牌堆。拿起最后一根木棍的玩家输。 i)最初有3个桩,桩的数量等于(1,2,2)。绘制这个游戏的完整搜索树。注意,(a, b, c)和(a, c, b)的堆被视为相同的状态,例如(1,2,1)与(1,1,2)相同。 (10分) ii)假设两个玩家,最小和最大,玩这个石头游戏。马克斯先玩。具有效用函数值: = 0如果min赢了游戏 = 1如果Max赢了游戏 将极大极小算法应用于搜索树,为所有状态分配效用函数 iii)如果最小值和最大值都打出完美的比赛,谁会赢?解释你的答案。
时间: 2023-06-14 10:04:56 浏览: 46
i) 搜索树如下所示:
```
(1,2,2)
/ | \
(0,2,2) ... (1,2,1)
/ | \ / | \
... ... ... (0,2,1) ...
/ | \
... ...
```
注意到 (1,2,1) 和 (1,1,2) 是相同的状态,因此搜索树中没有对它们进行重复扩展。
ii) 对于每个叶子节点,可以通过判断最后一次取走木棍的玩家来确定叶子节点的效用函数值。具体而言,如果是最小玩家取走最后一根木棍,则效用函数值为0;如果是最大玩家取走最后一根木棍,则效用函数值为1。
然后,可以使用极大极小算法来为搜索树中的所有状态分配效用函数值。从根节点开始,最大玩家将选择它的子节点中效用函数值最大的节点,而最小玩家将选择它的子节点中效用函数值最小的节点。如此反复进行,直到达到叶子节点并分配效用函数值为止。
搜索树的效用函数值如下所示:
```
(1,2,2) 1
/ | \
(0,2,2) 0 1 1 ...
/ | \
... ... ...
/ | \
... 0
```
iii) 通过搜索树中的效用函数值,我们可以看到最大玩家可以在第一回合中取走两根木棍,然后每回合都可以取走两根木棍,直到只剩下一根木棍时,最小玩家不管取几根都会输。因此,如果最小值和最大值都打出完美的比赛,最大值将获胜。