中国象棋
对弈
软件的
设计 中国象棋对弈软件的设计
摘 要:随着人工智能及
计算机硬件的发展,计算机象棋
程序的下棋水平也不断地得到提高。20世纪60年代初,麦卡锡提出了alpha-beta修剪算法,把为决定下一个走步而需对棋盘状态空间的
搜索量从指数级减少为指数的平方根,大大地提高了机器下棋的水平。IBM的超级计算机"Deep Blue"更是一个神话,让棋迷们神往。本文根据国际象棋程序设计的一些成功经验,提出中国象棋程序设计的一些思路和方法。
关 键 词:中国象棋,位棋盘,Zobrist键值,alpha-beta搜索,置换表,局面评价
Abstract:Along with the development of the Artificial Intelligence and computer hardware, the capability of computer chess program have advanced continually.At the beginning of 60s,20th century, McCaxi brought for
word alpha-beta pruning algorism which made the chess program advanced more by reducing the order of magnitude of the number of searching nodes deciding next step,named "State Space" from O(Xn) to O(Xn/2). IBM's super-computer "Deep Blue" is more like a myth for all computer chess fans. In my article, I will describe some ideas and methods of designing Chinese Chess program along with some successful experiences and cases of the Chess.
Keywords: Chinese Chess, bit b
oard, zobrist keys, alpha-beta search, transposition table,
Evaluation
源码网整理:www.codepub.com
目 录
引 言 3
第一章 概述 4
1.1 棋盘的标记 4
1.2 棋子的名称 5
1.3 棋谱的记录方法 5
1.4 历史局面的表示及存储 7
1.5 棋谱记录文件的格式 8
第二章 基本数据结构--位棋盘 10
2.1 什么是位棋盘 10
2.2 位棋盘的作用 10
2.3 位棋盘的基本运算 12
2.4
Java中位棋盘的实现 13
第三章 基本数据结构--Zobrist键值 17
3.1 比较局面的方法 17
3.2 Zobrist键值的实现方法 17
3.3 Zobrist键值的
工作原理及用途 17
3.4 Java中实现Zobrist键值 18
第四章 着法生成 20
4.1伪合法着法的生成 20
4.2 合法着法的生成 25
第五章 搜索算法 29
5.1 最小-最大搜索 29
5.2 Alpha-Beta搜索 33
5.3 迭代加深 36
5.4 置换表 37
5.5 其他策略 41
第六章 局面评价函数 47
6.1 评价函数的实现方法 48
6.2 评价函数所需的信息 48
第七章 程序的设计及实现 51
7.1 搜索引擎的实现(engine包) 51
7.2 信息传输机制(message包) 52
7.3 棋子生成(pieces包) 52
7.4 主控模块(main包) 52
附件1:搜索算法主程序SearchMove.java 55
附件2:程序运行界面及功能说明 74
引 言
象棋水平的发展是需要靠信息技术来推动的,国际象棋有两个很好的范例,一个是象棋棋谱编辑和对弈程序的公共平台--WinBoard平台,另一个是商业的国际象棋数据库和对弈软件--ChessBase,他们为国际象棋爱好者和研究者提供了极大的便利。国际象棋软件有着成功的商业运作,已发展成一种产业。然而,电脑在中国象棋上的运用还刚刚起步,尽管国内涌现出一大批中国象棋的专业网站和专业软件,但是由于缺乏必要的基础工作,电脑技术在中国象棋上的应用优势还无法体现出来。
在设计中国象棋软件过程中,国际象棋软件有很多值得借鉴的成功经验和优秀的思想。例如B. Moreland,微软(Microsoft)的程序设计师,业余从事国际象棋引擎Ferret的开发,他的一系列关于国际象棋程序设计的文章非常值得其他棋类程序设计人员借鉴。然而,中国象棋与国际象棋存在着很大的差异,因此国际象棋的某些成熟技术,无法直接应用于中国象棋,需要对其加以改进和创新。