5.2 博弈树搜索n 20世纪60年代，研制出的西洋跳棋和国际象棋 的博弈程序达到了大师级的水平。 n 1958约翰麦卡锡提出博弈树搜索算法 n 1997年，IBM公司研制的“深蓝”国际象棋 程序，采用博弈树搜索算法，该程序战胜了 国际象棋世界冠军卡斯帕罗夫。 1.概述正在与深蓝下棋的卡斯帕罗夫n 博弈问题特点： n 双人对弈，轮流走步。 n 信息完备，双方所得到的信息是一样的。 n 零和，即对一方有利的棋，对另一方肯定 是不利的，不存在对双方均有利或无利的 棋。 1.概述n 博弈的特性 两个棋手交替地走棋 ； 比赛的最终结果，是赢、输和平局中的 一种； 可用图搜索技术进行，但效率很低； 博弈的过程，是寻找置对手于必败态的 过程； 双方都无法干预对方的选择。 1.概述2.Grundy 博弈 n 下棋的双方是对立的，命名博弈的双方，一方为“正 方”，这类节点称为“MAX”节点；另一方为“反方” ，这类节点称为“MIN”节点。正方和反方是交替走 步的，因此MAX节点和MIN节点会交替出现。2.Grundy 博弈 n Grundy博弈是一个分钱币的游戏。有 一堆数目为N的钱币，由两位选手轮
