当计算机诞生时, 人们便想将计算机技术与博弈游戏相结合,这就是机器博弈,机器博弈 是人工智能领域里一个重要研究领域, 在国际上已经开展了半个多世纪。
1996年2月10日,IBM的超级电脑装载国际象棋程序“深蓝”首次挑战国际象棋世界冠军加里·卡斯帕罗夫,但以2-4落败。2月17日比赛结束后研究小组对深蓝做了进一步的改良。
1997年5月11日,卡斯帕罗夫以 2.5:3.5 (1胜2负3平)输给“深蓝”。
电子计算机开端于国外, 国际象棋在国际上开展较广泛, 所以国际象棋机器博弈的研究在国外相对较早。中国象棋虽是世界上历史最为悠久的棋类, 早在两千多年前的战国时代就已经有了关于象棋的记载, 但是因为在中国的电子计算机的普及及相关技术的发展远远落后于国外先进国家,中国象棋计算机博弈的研究近二十年才起步。
2006 年,为庆祝人工智能学科诞生50 周年, 浪潮集团赞助、中国人工智能学会举办了“ 浪潮杯” 首届中国计算机博弈锦标赛暨2006 机器博弈学术研讨会。2006 年8 月,来自全世界18 支中国象棋计算机博弈软件代表队参加了锦标赛,分别是棋天大圣、象棋奇兵、象眼竞技、 理治棋壮、棋乐无穷、棋之梦、将神传说、落花、青羽堂、天机、象棋ABC、象棋旋风、宝岛一号(台湾)、兵芯(台湾)、深象(台湾)、梦入神机(美国)、神乎棋技(美国)、谢谢大师(法国)。前五名棋天大圣、象棋奇兵、象棋旋风、天机、将神传说分别与徐天红、卜凤波、柳大华、张强、汪洋等象棋专业选手进行了中国象棋人机大战。结果棋软以3 胜5 和2 负略占上风。
1 象棋软件组成
中国象棋软件就是利用计算机来下棋,将棋局状态、行棋规则输入计算机,由计算机根据规则进行计算,然后再给出一步合理着法的程序。
象棋软件包括界面程序、引擎程序、开局库、审局库、残局库等。
象棋软件各部分各自独立,以界面程序为基础,引擎程序为核心。
(因为各部分遵守共同的UCCI或CCI协议,所以可以独自开发,然后由界面程序集成到一起。)
打开界面程序,可设置引擎程序(可选)、开局库(可选),以下是两个界面程序(兵河五四、鲨鱼象棋)与引擎程序和开局库的关系:
一般来说,界面程序、引擎程序都只有几十个M,体积庞大的是各类开局库、对局库、残局库(可选择加载)。
1.1 界面程序
界面程序是提供象棋对奕的图形界面程序,需要加载引擎(计算和分析工具)才具备棋力(一些界面程序也自带引擎)。在对弈、拆棋时,引擎的计算与分析能够直观地显示在不同的界面子窗口中。
基于UCCI的象棋界面程序完成用户与人工智能博弈引擎的交互功能,一般在具有人人、人机(人与象棋博弈程序)、机机对战的基本功能之外,还有棋谱编辑、棋局管理等辅助功能。
免费的界面程序有 :
32位系统:
兵河五四3. 6,
鲨鱼象棋,
鹏飞象棋v3. 3. 0.9
64位系统:
兵河五四4.0,
兵河五四4.1
1.2 引擎程序
引擎程序是一个着法生成、搜索、评估、给出最佳着法的博弈程序。
免费引擎程序有:
32位系统:
象棋名手326六核版(老版破解引擎,残局棋力尚可)
象棋旋风6. 3破解版(运算较慢,棋力差)
南澳1.6双核版(棋力一般)
64位系统:
国圣双核破解版(棋力一般)
三元加强版(棋力略优于名手326)
佳佳象棋(最高支持12S线程,强机下棋力明显优于其他免费引擎)
ggzero (用显卡来运算的AI引擎,目前还在训练提高棋力中)
1.3 开局库
博弈程序如果能借鉴常用的开局模式,可以大大节省时间, 为中局思考留下更多时间。由于开局阶段棋子多,棋型变化大, 搜索不会进行很深, 搜索的结果往往不如人们通过千遍万遍演练得到的常用开局, 避免搜索得到一些不太好的走法。
将成千上万的开局局面存储在计算机中, 形成一个开局库, 每一个局面都有一个最佳走法, 同时要注意走棋方。博弈引擎程序在开局阶段首先搜索开局库,如果有相同棋局, 则直接取出最佳走法作为当前搜索的结果。当开局库中对应局面有多个时, 则要采取一个策略从多个中优选一个来。如果开局库中没有相同局面, 则用搜索算法重新进行搜索。一旦开局库中没有相同局面,在后续搜索中都不再查找开局库了。
开局库必须要做到既方便存储, 又方便检索。可以用数据库,也可以用文本文件。在程序开始时, 将开局库中的内容读入内存, 在内存中检索。如果在硬盘中检索,时间花费太大了。
开局库是制作出来的棋谱,加载开局库可减轻引擎开局的运算压力,一般一直跟库走至少不输,也有制作出来通过亏一步棋专门让对方脱库的开局库。
开局库也可以存储在服务器上(云库),由界面程序网络连接调用。
1.4 对局库
当行棋到一定的局面,只要加载的对局库里有这个局面,界面程序会自动在对局库里搜索到这局面的所有棋谱。
1.5 残局库
同样可以把常见的残局棋型及其最佳走法存储在计算机中, 形成残局库, 供引擎程序在残局阶段检索。开局库因为开局是固定的, 前面几步局面变化不大, 开局库并不大。但残局库棋子没有固定位置, 可以在它们能去的任何地方, 残局库蜇实在太大。
2 象棋软件使用
2.1 打开界面程序
打开界面程序及加载需要的窗口。
2.2 设置和加载引擎
包括多引擎加载、时间设置、开局库设置、hash设置、线程设置等。
例如有的引擎在某些局面走得好,此时可以很方便地切换引擎,例如开局、中盘、残棋需要3个引擎,不需要打开三个界面占用系统资源。
2.3 启动分析模式
点击“分析模式”按钮即可启动分析模式,可看到搜索层数、提示着法及评分。
可在【视图】菜单中打开需要的子窗口:
【思考细节】:显示引擎的思考细节,人机参考棋步很有用;
【着法窗口】:显示开局库的棋步;
【对局库窗口】:显示对局库中的棋谱。
3 名词
3.1 UCCI协议
中国象棋通用协议(Universal Chinese Chess Protocol,简称UCCI),是一种象棋界面和象棋引擎之间的基于文本的通讯协议。
设立中国象棋通用引擎协议的目的有:
(1) 使一个“可视化象棋软件”可以使用不同的“核心智能部件”,这些核心智能部件称为“引擎”,凡是遵循UCCI的引擎,都可以被该可视化象棋软件(也称为“界面”)所调用;
(2) 针对所有遵循UCCI的引擎,都可以开发不同的界面,使其具有不同的功能。
这样,“可视化象棋软件”和“核心智能部件”实现了分离,使得一部分程序设计师能专注于前者(界面)的开发,而另一部分程序设计师能专注于后者(引擎)的开发,让中国象棋软件的设计工作系统化、分工化,提高软件设计效率。
UCCI是模仿国际象棋的UCI协议来制定的。UCCI协议是开放式的协议,并且具有UCI协议的所有特点。
该协议由业余研究电脑象棋程序的复旦大学研究生黄晨首倡于2004年,经过推广目前支持UCCI协议的公开发表的引擎已经增加到17个(截至2006年11月底),为中国象棋的信息化铺平了道路。
3.2 界面程序
界面程序一般集对弈、拆棋、连线于一体。
界面的主要元素有(以兵河五四为例)棋盘窗口、棋谱窗口、着法窗口、引擎信息、局势曲线、联赛窗口、图形连线、弈天登录及自动打擂、引擎联赛等。
界面程序一般基于多线程设计,界面线程负责显示,辅助线程负责与引擎通讯。
3.3 引擎程序
包括棋局局面表示,着法表示与生成(生成一棵博弈树),逐层逐个搜索树节点并做局面评估。其策略核心在于棋局评估函数,核心方法是博弈树搜索。同时开局库和残局库的构建对算法的性能也有重要的影响。
首先使用一个数据结构来描述棋局信息,对某一特定的棋局信息由着法生成器生成当前下棋方所有合法的着法并依次存入着法队列。然后通过搜索算法来逐一读取着法并调用局面评估函数对该着法所产生的后继局面进行评估打分,从中选出一个最有可能导致走棋方取胜的着法。在搜索的过程中还可以采用一些辅助手段来提高搜索的效率。
局面就是一盘棋经过若干回合之后当前所处的形势,包括棋盘、红黑双方所剩棋子及其在棋盘上的分布、当前该走棋一方、双方所剩时间、双方所剩走棋步数等内容。局面表示是象棋程序的基础, 局面表示的好坏直接关系到走法生成、搜索算法和局面评估的效率, 从而影响象棋程序得到的最佳走法。
象棋程序每一次思考的目的是获取一个最佳走法(至少在程序看来是最佳的)。要实现这一目标的简单方法就是生成全部所有可能的走法(及可能走法下的新的书面的可能走法……), 然后再一个一个的比较(局面评估), 找出最佳的一个。
局面评估就是判断局面对红方(或者黑方, 或者是当该前走棋一方) 的优势,并把优势进行量化。由于象棋程序搜索复杂度太大, 搜索函数不可能搜索到棋局终了的状态, 所以必须在某个深度的结点上结束并返回上一层。这个结点并没有达到棋局结束(胜平负),应该给它一个值, 反映局面状况, 对红方有利还是对黑方有利,有多少优势。必须把这种优势量化,以便不同结点的优势可以进行比较, 以确定哪一个结点更好。
中国象棋的局面变化实在是太多了,有时候一个局面可能走法达100多种,一般局面也有40多种走法。要完全搜索10步棋需要3.3年,即使完全搜索7步棋也要27分钟(按每秒搜索10^8个结点计)。按一盘棋平均100步(50个回合)计,要完全搜索100步是绝对不可能的。如何让计算机在有限的时间内搜索到更多的空间和更深的步数,是计算机引擎程序必须考虑的问题。这除了与计算机硬件有关之外,与搜索算法关系很大。这是因为在搜索树空间中有些分支是多余的,搜索的时候可以跳过某些分支。跳过的分支越多,搜索的速度越快, 但漏掉最优解的可能性也在增加。搜索算法必须又快又准地找到最优解。
对于每一个局面,都可以生成一个如下类似的“博弈树”——树的每一个结点表示每一种可能的着法,形成新的局面。对每一个局面(结点)根据不同的走法又产生不同的局面(生出新的结点),根据思考的步数增加,树的结点以几何倍数扩展。搜索函数可以通过搜索以当前局面为根结点、限定层数以内的整棵树来获得一个最佳的着法。有些“暂时”看来很不错的局面由于可能会产生很糟糕的局面因而根本没有考虑的价值。所以当你看到某个局面有可能产生很糟糕的局面时(确切地说这里的“很糟糕”是与之前所分析的情况相比较而言的),你应当立刻停止对其剩余子结点的分析。
上图所示,每展开一步就是一层,象棋软件中所说的深度就是我们所说的层数,对应多少步棋。其搜索和局面评估的计算以指数级增长。
另外,如果把中国象棋棋谱上一些公认为最佳的开局着法和残局着法存储在数据库中,在开局和残局时用查询取代搜索和评估,那么会大大提高计算机的对弈水平。
3.4 连线下棋
所谓“连线下棋”就是利用软件连线到各个游戏平台,让软件辅助你下棋或自动下棋。
界面程序一般都可以图形连线各大网站的客户端的棋盘,可以自动连线桌面上最上面的象棋客户端。打开图形连线界面,可以做更新方案、删除方案、测试连线、连线对弈、人机观战等操作。
选定了人机模式后,如果选定不保持同步,人机模式,是兵河五四的走棋不传到客户端的棋盘,你在兵河五四的棋盘尽管拆棋,拆好了按按钮就把棋子传到客户端棋盘上了。相当于拆棋后的立即出步,这点很方便人机模式,防止自己手工搬错子!
3.5 开局库
开局库几乎是每个象棋程序必备的部件,它的好处是:
(1) 即使再笨的程序,开局库能使得它们在开局阶段看上去不那么业余;
(2) 通过随机选择走法,让开局灵活多变,增加对弈的趣味性。
3.6 FEN文件格式
FEN(Forsyth-Edwards Notation)是专门用来表示象棋局面的记录规范,在这个规范下,一个局面可以简单地用一行“FEN格式串”来表示,而不必烦琐地说:“红帅在四路次底线,黑将在5路底线……”。由于它是文本格式的(只牵涉到很有限的几个字母、数字和符号),因此网上传递棋局就非常方便,不用把棋图画在纸上或用文字笨拙地描述了,而是用棋谱编辑软件摆好局面,自动得到FEN格式串,使得棋谱交流快速而高效。
FEN格式串用来表示一个局面,局面发生变化时,界面程序向引擎程序传递局面信息,如以下的一个FEN格式串:
rnbakabnr/9/1c5c1/p1p1p1p1p/9/9/P1P1P1P1P/1C5C1/9/RNBAKABNR w - - 0 1
(1) 前面最长的一串,表示棋盘布局,中国象棋棋盘有10行,所以要用9个“/”把每一行隔开;棋子名称用英文字母表示。小写表示黑方,大写表示红方。
(2) w,表示轮到哪一方走子,“w”表示红方,“b”表示黑方。
(3) -,空缺,始终用“-”表示。
(4) -”,空缺,始终用“-”表示。
(5) 0,表示双方没有吃子的走棋步数(半回合数),通常该值达到120就要判和(六十回合自然限着),一旦形成局面的上一步是吃子,这里就标记“0”。
(6) 1,表示当前的回合数,在研究中局或排局时,作为研究对象的局面,这一项可以写1,随着局势的发展逐渐增加。
4.7 PGN文件格式
PGN(Portable Game Notation)是棋类游戏过程的文件格式。
(1) PGN文件是文本格式的,可以用任何文本编辑软件建立和修改;
(2) PGN文件分为“标签部分”和“着法部分”,两部分都规范整齐,既方便阅读,也便于棋谱编辑软件产生和解读;
5 历年棋软比赛成绩
2006年棋软比赛成绩:
1.棋天大圣 (王骄)
2.象棋奇兵 (赵明阳)
3.象棋旋风(陈朝营)
4.天机 (张旭)
5.将神传说(雷春鸣)
2007年棋软比赛成绩:
1.象棋旋风(陈朝营)
2.天机 (郑旭)
3.棋天大圣 (王骄)
4.佳佳象棋 (李国来)
5.象棋奇兵(赵明阳)
2008年棋软比赛成绩:
1. Intella 倚天象棋(陈朝营、韦余涛)
2. Cyclone 象棋旋风(张闽谭卓勋)
3. EThinker 天机(郑 旭)
4. Gagachess 佳佳象棋(李国来)
5. MonkeyKing 猴王(徐心和)
6. NEUChess 棋天大圣(王 骄)
7. 3DChess 3D象棋(刘 进)
8. XQMASTER 象棋奇兵(赵明阳)
2009年棋软比赛成绩:
1.象棋名手 (蒋志敏)
2.佳佳象棋 (李国来)
3.陶情弈趣 (谭卓勋.张闽(孤独)
4.倚天象棋 (韦余涛)
5.天机 (郑 旭)
6.新奇兵 (王贤谷(赵明阳))
2010年棋软比赛成绩:
1.象棋旋风Tornado (陈朝营)
2.佳佳象棋Gaga chess (李国来)
3.象棋名手XQMS (蒋志敏.张闽)
4.先知象棋OracleX (张志福)
5.棋 弈Sunrise (北京理工大学)
6.哈工程 (赵国东(哈工程))
7.哈理工象棋 (哈尔滨理工大学)
2019年第三届楚河汉界象棋人工智能对决:
1. “旋风”
2. “名手”
3. GGZero
4. 国圣象棋
2019年10月在北京举行的第13届中国计算机博弈锦标赛中,小虫象棋以8胜2和的战绩获得中国象棋组冠军。
6 资源
棋中论坛:
中国象棋云库:
以下视频有相关免费资源的下载链接:
ref
《C/C 中国象棋程序入门与提高》
-End-