电脑棋手的思维汇总课件.ppt

1、电脑棋手的思维电脑棋手的思维王金一你可曾听说过你可曾听说过“深蓝深蓝”？1997年5月11日，IBM开发的“深蓝深蓝”击败了国际象棋冠军卡斯帕罗夫。1980年他获得世界少年组冠军 1982年他并列夺得苏联冠军 1985年22岁的卡斯帕罗夫成为历史上最年轻的国 际象棋冠军现在的积分是2849，这一分数是有史以来最高分。远远领先于第二位的克拉姆尼克的2770 卡氏何许人也？卡氏何许人也？电脑棋手：永不停歇的挑战！电脑棋手：永不停歇的挑战！1988年“深思深思”击败了丹麦特级大师拉森。1993年“深思深思”第二代击败了丹麦世界优秀女棋手小波尔加。电脑棋手：永不停歇的挑战！电脑棋手：永不停歇的挑战！2

2、001年“更弗里茨更弗里茨”击败了除了克拉姆尼克之外的所有排名世界前十位的棋手。2002年10月“更弗里茨更弗里茨”与世界棋王克拉姆尼克在巴林交手，双方以4比4战平。2003年1至2月“更年少者更年少者”与卡斯帕罗夫在纽约较量，3比3战平。领域在延伸领域在延伸CheckersSokobanChinese chessGoOthelloPokerLines of action Hex AwariAmatons Shogi Rosambo Domineering 许多人在努力许多人在努力 他们来自于何方？他们来自于何方？Canada、America、England、China、Japan、Holla

3、nd、MexicoUniversity of Alberta、University of Wisconsin、University of Maryland、MIT、University of Tokyo、University of Albama、University of California、Erasmus University、Cambrige University解谜：电脑是怎样下棋的解谜：电脑是怎样下棋的 人机博弈程序的一般设计方法人机博弈程序的一般设计方法以中国 棋为例（1）第一步该做什么？）第一步该做什么？数据结构的选取棋盘表示占用空间-少操作速度-快是否方便-方便在机器中表示棋局

4、，让程序知道博弈状态。九列十行十四种不同的棋子三十二个棋子几种棋盘表示的方式几种棋盘表示的方式二维数组直观 紧凑的数据结构省空间，不直 观，速度?比特棋盘用于8*8棋盘（国际象 棋），64位主机（2）接下来怎么办？）接下来怎么办？产生合法走步的规则，使博弈能公正的进行，并且能够判断对手是否乱走。依赖于具体棋类特征。是一段将局面所有可能的正确走法罗列出来的程序。称之为走法产生。几种走法产生的实现方式几种走法产生的实现方式一般做法 建立小型数据库 位运算位运算走法产生之例位运算走法产生之例寻找象的可走步位运算走法产生之要求位运算走法产生之要求一个基于比特棋盘的完善的数据库该数据库应位于内存中（3）

5、终于到核心了）终于到核心了从所有的走法中找出最佳的走法，也就是搜索的基本方法搜索的基本方法极大极小值负极大值Alpha-Beta搜索极大极小值搜索极大极小值搜索对抗性搜索静态估值有限深度深度优先负极大值算法负极大值算法重点在于：父节点的值是各子节点的值的负数的极大值。红走黑走红走Alpha-Beta剪枝剪枝Alpha-Beta搜索搜索和极大极小搜索结合在奇数层进行Alpha剪枝，偶数层Beta剪枝。和负极大值搜索结合在每一层都进行Beta剪枝。优化的搜索算法优化的搜索算法渴望搜索极小窗口搜索置换表哈希表Zobrist哈希技术优化的搜索算法优化的搜索算法迭代深化历史启发杀手启发SSS*/DUAL

6、*算法MTD(f)算法（4）最后）最后评估局面优劣，配合搜索技术做出智能的选择估值技术棋子价值评估 SideValue=Sum(piecenumber*piecevalue)棋子灵活性 Mobility=Sum(movenumber*movevalue)棋盘控制棋子关系的评估（威胁、保护、形、定势。并且要考虑到谁走棋）估值的几种形式估值的几种形式终点估值 思路清晰，容易设计，模块独立性高，同搜索算法耦合程度低 速度慢棋子价值表 TpieceTypeboardWidthboardHeight二者结合动态棋子价值表估值函数的内容及其调试估值函数的内容及其调试Score=aX+bY+cZ+dK+X=

7、车+马+炮+参数确定的方法参数确定的方法手工调整爬山法蒙特卡罗模拟退火遗传算法爬山法的缺陷爬山法的缺陷初值依赖初值依赖蒙特卡罗蒙特卡罗使用多种初始参数，从不同的地方开始多次爬山有足够多次的爬山，出现频率最高的结果是最优解的概率就会足够大不同初值的大量采样，使运算效率低模拟退火模拟退火MetroPolis重要性采样的基本思想：在寻优的开始使用较高的概率进行随机突跳，随着寻优过程的深入逐步降低这一接受不佳参数概率。并且随着搜索的深入，可接受的参数的不佳程度也越来越小。模拟退火模拟退火一次对参数改变一点，测试。提高，保留不提高，在一定概率上继续由粗到细，逼近最优参数遗传算法遗传算法随机产生一组初始个

8、体构成初始种群，并评价每一个体的适配值。判断算法收敛准则是否满足，若满足则输出搜索结果，否则执行以下步骤。根据适配值大小以一定方式执行复制操作。按交叉概率pc之行交叉操作。按变异概率pm执行变异操作。返回上面第二步骤。遗传算法遗传算法适配值：对个体进行评价的指标，算法优化的主要信息，与个体的目标值对应复制：复制概率正比于适配值交叉：交换父代个体中的部分信息产生后代，继承变异：随机改变个体中的某些信息产生新个体，增加种群多样性标准遗传算法优化框图使用遗传算法优化参数估值的过程Genetic Algorithms 优越性优越性全空间并行搜索，重点集中在高性能部分，防止陷入局部最优孰优孰劣？孰优孰劣？名局测试和其他博弈程序对弈选不同的参数，自相对弈同向下几层的搜索结果比较