《民间棋类计算机博弈11》由会员分享，可在线阅读，更多相关《民间棋类计算机博弈11（82页珍藏版）》请在金锄头文库上搜索。
1、民间棋类计算机博弈文中华2010年3月主要内容v什么是计算机博弈（机器博弈）？v机器博弈的艰苦历程与辉煌成果v民间棋类计算机博弈机器博弈的入门课v计算机是如何实现博弈过程的？v机器博弈的技术构成与内涵v开展机器博弈活动的意义与展望什么是计算机博弈？计算机博弈, 机器博弈 Computer Games 主要是指计算机下棋、玩牌 像人一样的思维 最先提出的就是计算机下国际象棋、西洋跳棋等各种棋类 机器博弈是一个特殊的研究领域v它是非常实际的计算机科学与技术的研究课题v它是非常富于挑战性的人工智能领域的研究方向v它来不得任何理想化和虚假成分v它是现代博弈论所不能解决的动态博弈技术v它是需求牵引的典型
2、课题，具有很强的泛化能力因为它是人工智能的基本问题v它具有广阔的应用前景对策问题（控制、决策、对策） 机器博弈的艰苦历程与辉煌成果v国际象棋v 最先提出的计算机应用课题之一v 计算机前辈所关注的研究课题v 半个世纪的艰苦拼搏v IBM深蓝的辉煌业绩v 继续向新的高峰攀登追寻历史的踪迹v1946年第一台电子计算机 问世于美国。v冯.诺依曼数学家，博弈论的创始人计算机之父提出极大极小定理为验证机器的正确性和性能， 首先为它编写了象棋程序Programming a computer for playing chess, Shannon,1950 v“用极大极小值算法可以找到想下的棋， 但由于这个游戏
3、的变化太多，不可能搜索 到终结点，所以就要寻找一种合适的方法 只搜索部分节点，然后就可以判断该走哪 步棋，进而走棋 ”v现代计算机博弈的理论基础许多人在努力他们来自于何方？vCanada、America、England、China 、Japan、Holland、MexicoUniversity of Alberta, University of Wisconsin, University of Maryland, MIT, University of Tokyo, Universityof Albama, University of California, Erasmus University
4、, Cambrige University世纪之战v许峰雄深蓝之父1997年深蓝战胜 卡斯帕罗夫电脑棋手：永不停歇的挑战！v2001年“更弗里茨” 击败了除了克拉姆 尼克之外的所有排名世界前十位的棋 手。v2002年10月“更弗里茨”与世界棋王克 拉姆尼克在巴林交手，双方以4比4战 平。v2003年1至2月“更年少者”与卡斯帕罗 夫在纽约较量，3比3战平。克拉姆尼科最新赛事(2006.11)须知：深弗里茨比当年“深蓝”运算能力快2个数量级连续三届奥林匹克冠军 Kramnik 2 - 4 Deep Fritz 棋类机器博弈的发展v机器博弈涉及的范围： Othello 奥塞罗 Checkers 西
5、洋跳棋 Go-moku五子棋 Chess国际象棋 Chinese chess中国象棋 Shigo日本将棋 Go围棋v领域在延伸 Poker纸牌游戏vSokobanLines of action Hex Awari Amatons Rosambo Domineering 机器博弈的艰苦历程与辉煌成果v中国象棋v机器博弈工作者新的挑战v 可喜的初战胜利v 还有很长的路要走v围棋的机器博弈水平还很低 台湾电脑象棋之父前台湾大学 资讯工程系教授 许舜钦 80年代开始 机器博弈研究 “Elephant” 现在台南长荣大学中国电脑围棋的骄傲中山大学化学系 陈志行教授 “手谈” 汇编语言 1995,1996
6、,1997 连续3年 6项世界冠军棋天大圣 勇夺 全国冠军2006.8.8浪潮杯首届中国计算机博弈锦标赛左起： 卜凤波 徐天红 柳大华 张 强 汪 洋浪潮杯首届中国象棋人机大战 对阵5位象棋大师2006年8月9日国家奥林匹克中心 综合馆人机大战终极 PK（2006.8.15）中国象棋第一人 许银川 vs 棋天大圣民间棋类计算机博弈v最简单的机器博弈项目机器博弈入门课v麻雀虽小，五脏俱全v从一个实例出发牛角棋民间棋类的特点v规则简单，很容易入门；v不受专业知识限制；v棋盘小，棋子少，复杂度不高；v输赢容易识别，局面容易判断；v完全信息，编程相对简单；v人工智能的“果蝇”。牛角棋 v牛角棋广泛见于
7、各地，别 名较多，如憋死牛、憋死 井、娃娃下山、娘子下山 等。v棋盘形状及棋位数目也稍 有差异。但是棋子、棋规 都相同。牛角棋棋规v红子可上可下，可左可右， 一次一步，只能走向空位， 不得重合与跳跃；v蓝子只上不下，可左可右， 一次一步，只能走向空位， 不得重合与跳跃；v胜负判断：憋死憋不死？红先红胜 (7步)红先蓝胜 (18步)为什么输赢？需要不断地摸索经验，试验所有的局面。博弈思维过程 展开博弈树红方走棋红方走棋蓝方走棋红方先手计算机是如何实现博弈过程的？计算机如何进行博弈思维？如何编写机器博弈程序？计算机如何进行博弈思维？v如何存储思维信息？棋盘、棋子、棋 局、博弈树v如何判断局面的胜负
8、？v如何展开博弈树？v如何选择当前的着法？v如何编写程序？v如何总结博弈的规律？ 如何存储思维信息？v 编码 数据结构v 棋盘编码（棋位编码）v 棋子编码v 初始局面的表示v 棋位向量：(1000000023)v 棋子向量：(089)2034567891棋局演化的形式化描述v 状态变量 棋子向量表示v 初始状态v 状态演化方程v 其中 为棋子i 第n+1步的着法（算子）v着法规则：红子可上可下，可左可右，一次一步，只能走向空位，不得重合与跳跃； 蓝子只上不下，可左可右，一次一步，只能走向空位，不得重合与跳跃；着法的形式化描述通过扫描棋盘，如果“落址”为空位，便是合法着法（算子）。203 45
9、67 891如何判断局面的胜负？v红胜：“逃出” v蓝胜：“憋死” v和棋局面的无限次重复203 45 67 891如何展开博弈树？红方走棋红方走 棋蓝方走 棋红方先手如何表示博弈树？两种不同的展开方式广度 优先室两种不同的展开方式深度 优先广度优先的展开与存储深度优先的展开与存储如何选择当前的着法？v 在展开的博弈树中搜索博弈搜索引擎v 如果红方走棋，他总要找到博弈树中最好 的棋局，而在考虑对方（蓝方）走棋时， 就要考虑最坏的局面，因为双方都是理智 的博弈者，不应该抱有任何侥幸的心理。v 如果给每个棋局打分，那红方可以称得上 是MAX方，蓝方便是MIN方。深度为3的博弈树局面（取极大值）局面
10、（取极小值）着法RootRoot MovesLeavesPly = 0Ply = 1Ply = 2Ply = 3Depth = 3Depth = 2Depth = 1Depth = 0图例：深度层数MAXMAXMIN1298765433213极大极小搜索找到最佳路径与最佳着法MAXMAXMIN1298765433213从极大极小搜索到负极大值搜索Current best PV and best move-3-2-1NegaMaxNegaMaxMAXMAXMIN45682434Alpha剪枝=4找到最佳路径与最佳着法-剪枝（1）174298MAXMINMIN77由此产生最佳路径和最佳着法 =7-
11、剪枝（2）835791MAXMINMIN8426由此产生最佳路径和最佳着法448 =4负极大值形式的Alpha-beta搜索vAlpha的含义：当前方已经存在某个着法， 其估值至少为alpha；vBeta的含义：对手存在着某个着法，令当前 方的着法的估值无论如何也超不过beta。v负极大值形式的alpha-beta剪枝只有beta剪 枝。（alpha，beta）窗口A1A2A3An（alpha，beta）Value = -Search()If (Value = beta)A1A2A3An（alpha，beta）Value = -Search()An（alpha，beta）窗口博弈树搜索过程Mo
12、ve Generation Make MoveMove GenerationMake Move10Evaluation1010UnMake Move1010 121210 12121210 12121210 12121212101212121061212612106121261210613121261210613Cut off1212131210613121213121061312121312106131212131210613121213121061318121213121061318181212131212106131818121213121210613181812121312121061
13、31818129998Cut off1212131212106131818129998Best PV人 机 对 弈 信 息 流 程红方先行。 人选红方，输入着法；人选蓝方，输入goHumans Move人机界面（CHI） 界面更新，胜负判定搜索引擎（递归BEITA-剪枝） Move Generation Make/Unmake Move Evaluation数据结构：棋子棋盘表示 棋局系列，着法列表Root Move牛 角 棋 软 件 结 构棋子的表示#define REDSTONE 0#define BLUESTONE1 1#define BLUESTONE2 22034567891局面的表
14、示（一）v初始局面的表示int board10 = REDSTONE,0, 0, 0, 0,0, 0, 0, BLUESTONE1,BLUESTONE2, ; 2034567891局面的表示（二）v初始局面的表示记录有子的交叉点编号 （stone Intersection-si）int si3 = 0, 8, 9 ;(注意off-by-one错误)2034567891等价的局面表示v等价的初始局面int si3 = 0, 8, 9 ;int si3 = 0, 9, 8 ;2034567891着法的表示绝对着法的三个要素Piece：哪个棋子 From：出发点编号 To： 目标点的编号203456
15、7891着法的表示相对着法更方便Piece：哪个棋子 To： 目标点的编号涵义：Piece To 位： 5 4 3 2 1 02034567891着法生成v着法生成是和棋类知识关系最为紧密的部分v着法生成是博弈树展开和搜索的先决条件v着法生成是博弈程序中一个相当复杂而且耗 费运算时间的部分v通过良好的数据结构（棋盘表示，着法表示 ），可以显著地提高生成的速度v着法生成 、实现(make move)、评估、选择 之后，还要恢复到父节点(unmake move)着法生成（一）棋盘扫描法/以红子为例 for (each piecei) if(piecei+1 siBLUESTONE1) | (siREDSTONE siBLUESTONE2) )2）蓝走红胜 ( (wtm = BLUE) &(siREDSTONE & 1 = 0) & (siBLUESTONE1 = siREDSTONE+1) & (siBLUESTONE2 = siREDSTONE+2) | (siBLUESTONE1 = siREDSTONE+2
