6.2 博弈中的优化决策
我们现在只考虑两个游戏者：MAX和MIN（至于为什么这样命名，一会儿就显而易见了）。MAX先行，然后两人轮流出招，直到游戏结束。在游戏最后，给优胜者加分，给失败者罚分。游戏可以形式地定义成含有下列组成部分的一类搜索问题：
• 初始状态，包括棋盘局面和确定该哪个游戏者出招。
• 后继函数，返回(move, state)对（两项分别为招数、状态）的一个列表，其中每一对表示一个合法的招数和其结果状态。
• 终止测试，测试判断游戏是否结束。游戏结束的状态称为终止状态。
• 效用函数（又称为目标函数或者收益函数），对终止状态给出一个数值。在国际象棋中，结果是赢、输或平，分别赋予数值+1，−1或0。有些游戏有更多的可能结果，例如双陆棋的收益范围从−192到+192。虽然后面会简单提到非零和的游戏，不过本章主要讨论零和游戏。
每方的初始状态和合法招数定义了游戏的博弈树。图 6.1 给出了井字棋（圈与叉游戏）的部分博弈树。在初始状态，MIN有9个可能的行棋。游戏交替进行，MAX下X，MIN下O，直到我们到达了树的叶节点对应的终止状态，也就是说一方的三个棋子连成一条直线或者所有棋位都填满了。叶节点上的数字指示了这个终止状态对于MAX来说的效用值；值越高被认为对MAX越有利，而对MIN则越不利（这也是游戏者得以如此命名的原因）。所以MAX的任务是利用搜索树（特别是终止状态的效用值）来确定最佳的招数。
图6.1 井字棋游戏的搜索树（部分）。顶层的节点是初始状态，MAX先走棋，放置一个X在空位上。我们显示了搜索树的一部分，给出MIN和MAX的交替行棋过程，直到我们最终到达终止状态。按照游戏规则对终止状态赋予了效用值
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
