Homework 3
PB17000297 罗晏宸
March 16 2020
1 Exercise 5.8
考虑图1中描述的两人游戏。
图 1: 一个简单游戏的初始棋局
选手 A 先走。两个选手轮流走棋,每个人必须把自己的棋子移动到任一方
向上的相邻空位中。如果对方的棋子占据着相邻的位置,你可以跳过对方的
棋子到下一个空位。(例如,A 在位置 3,B 在位置 2,那么 A 可以移回 1。)
当一方的棋子移动到对方的端点时游戏结束。如果 A 先到达位置 4,A 的
值为 +1;如果 B 先到达位置 1,A 的值为 −1。
a 根据如下约定画出完整博弈树:
• 每个状态用 (s
A
, s
B
) 表示,其中 s
A
和 s
B
表示棋子的位置。
• 每个终止状态用方框画出,用圆圈写出它的博弈值。
• 把循环状态(在到根结点的路径上已经出现过的状态)画上双层方框。
由于不清楚他们的值,在圆圈里标记一个“?”。
b 给出每个结点倒推的极小极大值(也标记在圆圈里)。解释怎样处
理“?”值和为什么这么处理。
1
评论0