中国象棋“深蓝”含苞待放.doc

中国象棋“深蓝”含苞待放野生的鱼从接触计算机时起，我就有一个梦想，自己设计出一个顶级的中国象棋或围棋人机对弈系统，达到甚至打败特级大师、专业九段的水平。那时由于无知者无畏，不知深浅。现如今已在此道潜心修行了二十多载，蓦然回首，梦想未果，怅然若失。今放眼环视，悲喜交加，个中情愫，现一并道来，以慰平生，以飨棋朋博友。你可能会问我，早过不惑之年了，此种情结为何经久不散呢？我想主要有一下三个原因吧。一则它确实能满足我作为超级棋迷的实际需要；二来想发挥自己软件工程专业所长找些成就感；再者也是为我国棋类事业尽微薄之力吧。当前三大棋国际象棋，中国象棋，围棋人机对弈算法中以国际象棋最强，中国象棋次之，围棋最弱。造成此格局的主要原因很多，如普及程度，科技水平及科研经费，复杂度不同等。以复杂度为例，具体如下表：表 几种棋类的空间复杂度及树的复杂度对比 （表中的数字为搜索的复杂度的自然对数值） 棋类 棋盘大小 空间复杂度 树的复杂度 国际象棋 8 8 50 123 中国象棋 10 9 52 150 围棋 19 19 172 400可以看出，中国象棋的状态空间复杂度和博弈复杂度都比国际象棋要高，围棋就更高，显然这是对中国学者提出的严峻挑战。所幸的是，经过半个世纪的发展，及计算机界大师积极的参与，国际象棋的人机对弈已经得相当成熟。早在上世纪， 信息论及数字通信时代的奠基人美国的香农(1950)与英国被称为计算机科学之父、人工智能之父的图灵(1953)提出了对象棋博弈编程的方案，成为机器博弈的创始人。系统的博弈论的研究是从国际象棋开始的，被称为“计算机之父”和“博弈论之父”的冯诺依曼通过对两人零和一类博弈游戏的分析，提出了极大极小值定理，这也是博弈论产生的第一个里程碑。 国际象棋是影响最大研究时间最长投入研究精力最多的博弈项目，成为计算机博弈发展的主线。具体的国际象棋的编程可以通过优秀的评估函数和修剪搜索树解决，国际象棋软件的协议UCI(Universal Chess Interface即通用象棋接口)就一直在发展和完善，并已逐步成为国际象棋程序设计的标准，在此基础上的国际象棋程序自动对弈比赛也在大规模地开展，1997年IBM 公司的超级计算机深蓝战胜了国际象棋世界冠军卡斯帕罗夫 ，成为人工智能领域的一个里程碑。我想，对于我们中国象棋，两者的相似度又很高，我们完全可以借鉴其经验，通过适当的改造甚至发展，早就我们自己的中国象棋“深蓝”。近年来，我们欣喜的看到，我们的中国象棋人机博弈的发展非常迅速，如作者赵明阳设计的象棋奇兵，在家用普通PC上达到了中国象棋业余高手水平，在高性能计算机上达到了中国象棋特级大师水平。软件特征：棋盘表示基于Bitboard；规则判断；后台思考；置换表；迭代深化；开局库；历史表；空着裁剪；学习文件；PVS搜索算法；LBR裁剪算法。荣获第十届奥林匹克中国象棋电脑软件大赛冠军，2006年8月“浪潮杯”首届中国象棋人机大赛中一胜一和中国象棋特级大师卜风波。另外东北大学开发的棋天大圣，荣获2006 年和2007 年的世界冠军，其研发小组深入研究了中国象棋计算机博弈的特点，研究了中国象棋计算机博弈状态空间表示、搜索算法、数据结构、审局函数、开局库、残局库等关键技术，建立了数字化的象棋博弈模型，开发出了可以达到人类特级大师水平的中国象棋博弈软件“棋天大圣”。有力开展了计算机博弈的普及活动，实实在在地推动了中国计算机博弈的发展进程等。尽管中国象棋计算机博弈已经取得了很好的成绩，但是毕竟离战胜世界冠军还有一定的差距，同国际象棋相比也逊色不少，中国象棋有它自己独特的特点，如大的棋盘，不同的子力和走法规则等，要做的工作还有很多，我认为主要应在以下方面做好研究：棋盘的表示不象国际象棋刚好用6位位图表示，还没有统一高效的方法；局面采用64位HASH函数表示，高效唯一；开局库的高效检索优化；尤其是核心算法博弈树的-剪枝优化，引进最新的遗传变异算法，BP神经网络技术，自适应学习方法等，尤其是后者；评价函数需要快速科学精准；残局库的完备性等。令人欣慰的是，以上方面国内有许多业内人士已在开展了研究，其中也有不少硕士博士加盟，如大连交通大学的鹿荣硕士，提出了一种新的混合博弈树的搜索算法，其基本搜索算法如：PVS 搜索、静寂搜索等；高级搜索算法为1) 历史启发；2）杀手启发；3) 迭代深化；4)迭代深化，它能够根据搜索所需要的时间选择搜索深度；5) 改进的置换表等。同时也设计了一种新的评估函数在中国象棋开局库中的应用，结合了利用共轭梯度求解二次最优的方法，尽可能的保证系统在开局阶段便处于优势，并使开局库具有一定的自学习能力，提高了博弈水平。哈尔滨工程大学的硕士王一非的具有自学习功能的计算机象棋博弈系统的研究与实现工学硕士学位论文，其中主要运用神经网络结合时间差分算法的方法来代替传统的线性估值函数 ,利用强化学习的方法，使象棋程序具有自学习的功能 ,使计算机在对弈的过程中不断地学习。这是一种非常有意义的尝试 。我认为这也是以后人工智能研究的方向，也是攻克围棋博弈算法