基本信息
- 项目名称：
- 三方对弈中国象棋软件
- 来源：
- 第十一届“挑战杯”国赛作品
- 小类：
- 信息技术
- 大类：
- 科技发明制作B类
- 简介：
- 三方对弈中国象棋是在传统中国象棋的基础上发展而来的，是一种新的游戏机制。 本软件作为第一款三方对弈中国象棋软件， 在文化上，旨在为弈者提供一个分享智慧的舞台，在实战中锻炼和提高弈者的“合作意识”。 本作品以三方博弈为切入点， 研究多方博弈下的博弈搜索算法。在三方博弈下，博弈各方的利益并不总是对立的，可能有合作的关系，这正是区别于双方博弈之处。本作品立足于三方中国象棋游戏，设计和实现了三方博弈搜索算法，改进了Alpha-Beta剪枝的应用范围，填补了我国关于多方博弈搜索算法的空白，并在此基础上，实现了机器学习功能和网络对战功能。
- 详细介绍：
- 本作品研究的多方博弈问题属于国际学术研究的空白领域，国内外几乎找不到合适的研究文献。加拿大阿尔伯塔大学有过研究这方面的论文《Current Challenges in Multi-player Game Search》，但其描述的算法未涉及多方博弈的新特点，因此也有其局限性。在多方博弈下，博弈各方的利益在短时间内不再是只存在“你死我亡”的必然关系，还可能有合作的关系，这正是区别于双方博弈的特点。 作品创新点列举如下： 1、提出新型的搜索算法并在软件上通过测试。 本作品提出的线性矢量搜索算法打破了传统博弈算法框架（传统的机器博弈都局限于代数方法），把几何学引入机器博弈研究，该算法能够解决三方博弈的合作与竞争问题（合作方不固定），而且对多方博弈问题也提出了通用解法。 2、提出新型的剪枝算法并在软件上通过测试。 三方博弈的复杂度非常高，建立一棵传统象棋的50轮搜索树就很困难，而50轮三方对弈的博弈复杂更达到传统象棋的10的111次方倍。本作品提出的新型矢量剪枝算法，可有效地剪枝掉冗余的搜索结点，博弈方越多，产生的剪枝条件越多，剪枝效率就越高。 3.提出新型的机器学习算法并在软件上通过测试。 由于三方博弈的解空间相当庞大，所以搜索算法常常陷于计算量过于巨大这一问题中。本作品提出一种新的估值学习算法，并在测试中显示出高效的自学习自调整能力。
作品图片
作品专业信息
设计、发明的目的和基本思路、创新点、技术关键和主要技术指标
- 本作品以三方博弈为切入点， 研究多方博弈下的博弈搜索算法，是第一款三方中国人机对弈象棋软件，作品创新点列举如下： 1、提出新型的棋盘储存数据结构并在软件上通过测试。 在传统中国象棋软件里，通常用来描述棋盘及其上棋子信息的数据结构是一个二维数组。本作品提出了三维数据结构来表示三方对弈中国象棋棋局，巧妙地处理了棋盘存贮量和操作规则实现复杂性的问题。 2、提出新型的搜索算法并在软件上通过测试。 本作品提出的线性矢量搜索算法打破了传统博弈算法框架（传统的机器博弈都局限于代数方法），把几何学引入机器博弈研究，该算法能够解决三方博弈的合作与竞争问题（合作方不固定），而且对多方博弈问题也提出了通用解法。 3、提出新型的剪枝算法并在软件上通过测试。 三方博弈的复杂度非常高，建立一棵传统象棋的50轮搜索树就很困难，而50轮三方对弈的博弈复杂更达到传统象棋的10的111次方倍。本作品提出的新型矢量剪枝算法，可有效地剪枝掉冗余的搜索结点，博弈方越多，产生的剪枝条件越多，剪枝效率就越高。 4、提出新型的机器学习算法并在软件上通过测试。 由于三方博弈的解空间相当庞大，所以搜索算法常常陷于计算量过于巨大这一问题中。本作品提出一种新的估值学习算法，并在测试中显示出高效的自学习自调整能力。
科学性、先进性
- 本作品指向明略，特点突出，既具有巨大的研究价值，又极富娱乐性，在实践上和理论上都有明显的创新性。 就理论研究领域而言，完全信息的多方游戏几乎没有，多方博弈研究在国内外也基本是一片空白，所找到的技术资料仅限于文献《Current Challenges in Multi-player Game Search》和《四国军棋游戏中搜索算法的实验和分析》。这两篇论文均没能涉及到多方博弈下具有合作状态这个根本的问题。本作品所提出博弈算法能够解决合作并且合作方不固定的博弈问题，并在此基础上提出了高效的剪枝算法。算法已写成论文发表在第2届国际智能技术应用学术会议，该论文已被EI(工程检索 )、ISTP(科技会议检索 ) 收录。 目前网络上只找到一款名为《三国演义》的同类产品（2D网络游戏）,但其并不能实现彻底的三方对弈情况，也不含人机对战功能。本作品含有此功能且为3D网络游戏。
获奖情况及鉴定结果
- 本作品于2008年12月荣获第十一届全国“挑战杯”大学生课外学术科技作品竞赛校赛特等奖。 本作品于2009年5月荣获第十届某省“挑战杯”大学生课外学术科技作品竞赛特等奖。
作品所处阶段
- 生产阶段
技术转让方式
作品可展示的形式
- 磁盘， 现场演示， 产品
使用说明,技术特点和优势,适应范围,推广前景的技术性说明,市场分析,经济效益预测
- 本作品有很好的学术研究价值和商业价值。以中国象棋为媒介, 提出了一种多方博弈的搜索算法和剪枝算法，N方博弈则应建立一个N-1维空间的数据结构进行评估和搜索。 本作品富有娱乐性和益智性， 值得向市场推广和进行商业活动，可以马上实现产学研。与传统竞技游戏总是培养人的“竞争意识”不同的是，在博弈中培养人的“合作意识” 。三方对弈合作下的一系列“组合拳”（合作对象不固定），具有1+1>2的效果， 各种经典的围魏救赵、隔岸观火和声东击西等计谋都可得到展现, 这就迫使玩家学会与人合作，与人相处。 在商业和文化上，“合作意识”使这款软件便于向广大民众推广，培养青少年的修养，启迪民智，有利于建设和谐社会。在技术上承前启后，有望应用于军事和经济等领域多方博弈问题的研究。
同类课题研究水平概述
- 研究成果对比： 台湾学者最早在七十年代末开始了计算机中国象棋的研究，并在八十年代开发和出版了中国象棋程序。随后，中国象棋人机对弈领域得到了长足发展。双方博弈的研究从极大极小值法和AlphaBeta剪枝，到置换表和历史启发，再到极小窗口搜索(PVS)等技术, 已发展到相当成功的地步了。 但我们研究发现，双方博弈只是多方博弈里的一个特例。双方博弈技术是建立在简单的纯竞争状态下的，而在三方博弈下，短时间内博弈各方的利益在短时间并不总是对立的，可能有合作的关系，至于合作者是谁，也不是固定的。这就导致原来双方博弈的基础算法极大极小值法不适用于三方博弈情况。 关于完全信息多方博弈的研究则几乎一片空白，目前只找到两份, Alberta大学Nathan Sturtevant的《Current Challenges in Multi-player Game Search》 和 南京航空航天大学陆慧和夏正友的《四国军棋游戏中搜索算法的实验和分析》。 这两篇论文均停留在旧有的双方博弈框架内的进行剪枝，没能涉及到多方博弈下具有合作状态这个根本问题。由于对局势的描述不精确， 搜索方法也有其相应的不足之处。 本作品提出的线性矢量搜索算法打破了传统博弈算法框架（传统的机器博弈都局限于代数方法），把几何学引入机器博弈研究，该算法能够解决三方博弈的合作与竞争的问题（合作方不固定），而且不但能解决三方博弈问题，对于多方博弈问题也提出了解决方法。在此基础上，本作品提出了新型的矢量剪枝算法，可以有效地剪枝掉冗余的搜索结点，博弈方越多，产生的剪枝条件越多，剪枝效率就越高。(详情请见论文）。 软件对比： 目前网络上只找到一款名为《三国演义》的同类产品，首先， 《三国演义》是“十”字棋盘，2D网络游戏；三方中国象棋软件是“Y”字棋盘，3D网络游戏。 其次《三国演义》的参与者共有4方，通过一方不可控来实现三方搏弈，但是不能达到地利平衡；三方中国象棋软件是彻底3方，地利平衡。再次，《三国演义》不含人机对战和机器学习功能；三方中国象棋软件实现了作者提出的基于矢量估值形式的搜索算法和机器学习算法，实现了人机对战和机器学习功能。三方中国象棋软件还具有走法提示功能（一提子即显示可行地点），用户不用学习走法规则即可使用。
