题目
-
1）对于如图所示的博弈树，假若A在极大值层，它该选什么样的走步？
2）在上题的博弈树中，用剪枝过程需要检查哪些节点？
-
A → D → J → W A\rightarrow D\rightarrow J\rightarrow W A→D→J→W
-
L , M , N , P , Q , R , S , V , W , X L,M,N,P,Q,R,S,V,W,X L,M,N,P,Q,R,S,V,W,X
-
-
有一种N/M或“最后者输”的博弈游戏，其玩法如下：开始有9枚硬币，两人轮流取出1、2或3枚，取出最后一枚者为输，使用搜索树证明后起步者总能取胜。
-
1）请指出 α \alpha α剪枝过程与 β \beta β剪枝过程的差别。
- α \alpha α剪枝： M A X MAX MAX节点的 α ≥ M I N \alpha\geq MIN α≥MIN子结点中的 β \beta β，则剪去此子节点， α \alpha α剪枝发生在 M I N MIN MIN层
- β \beta β剪枝： M I N MIN MIN节点的 β ≤ M A X \beta\leq MAX β≤MAX子结点中的 α \alpha α，则剪去此子节点， β \beta β剪枝发生在 M A X MAX MAX层
2）极小极大过程体现了怎样的思想？
- 下棋的双方是对立的
- 一方为正方，这类节点称为 M A X MAX MAX节点
- 另一方为反方，这类节点称为 M I N MIN MIN节点
- 正方从其所有子结点中，选取具有最大评估值的节点
- 反方从其所有子结点中，选取具有最小评估值的节点
- 反复进行这种选取，就可以得到双方各个节点的评估值。这种确定棋步的方法，称为极大极小搜索法
行这种选取，就可以得到双方各个节点的评估值。这种确定棋步的方法，称为极大极小搜索法