《对弈程序基本技术》专题
概述
象棋百科全书网 (webmaster@xqbase.com) 2005年9月
我花了大量时间翻译了F. D. Laramée的《国际象棋程序MATCH_
word
word文档格式规范word作业纸小票打印word模板word简历模板免费word简历
_1715978800689_0》(Chess Programming)连载，现在已经具备了设计象棋引擎的能力，但是还需要一些
资料
新概念英语资料下载李居明饿命改运学pdf成本会计期末资料社会工作导论资料工程结算所需资料清单
。为此，我查找了各个象棋程序设计的网站，收集了很多专题性的文章，并且整理成Laramée写他的连载时形成的体系。
我整理的文章除了T. A. Marsland的《国际象棋程序剖析》一文外，把它们分成四类，它们分别对应了Laramée的连载的四个部分。由于是从不同的网站上收集的，作者也各不相同，他们分别是：
· D. Eppstein，加州爱尔文大学(UC Irvine)的计算机教授，我收录了他1997到1999年做专题讲座的9篇文章，基本上是概述性的，也有细节上的东西，包括源代码(这可能是读者最感兴趣的)。
· J. Swafford，公开源代码的国际象棋引擎Galahad的作者(Galahad并不算很成功，现在已经销声匿迹的)，Laramée的连载中提到过他的文章，我收录的3篇文章(都是关于位棋盘的)则是一个叫Allen Liu的网友翻译的，其实肯定不止这3篇。不过现在他的网站现在已经关闭了，因此没有他的原文，这点让我非常遗憾。
· B. Moreland，微软(Microsoft)的程序设计师，业余从事国际象棋引擎Ferret的开发，在电脑奥林匹克大赛国际象棋业余组里，它和著名的Crafty一样处于领先水平。Moreland的文章涵盖的范围最广(除了局面评价以外都涉及到了)，所以我收集得最多。
· M. Fierz，瑞士Aargau学院的物理学家，国际象棋业余棋手，业余从事棋类程序的设计，作品有Muse(国际象棋)、Cake(西洋跳棋)等。我收录了Fierz写的关于残局库、开局库等其他方面的译文，使得整个专题更为完整。
一、数据结构
这部分内容极其丰富，不仅包括棋盘的表示方法，还包括着法产生当中需要用到的数据结构。我把关于“着法产生”的文章也并入其中，因为这部分内容实在很难归为一类，因此它代表了Laramée的连载的第二和第三部分。
1.1 数据结构——简介(D.Eppstein)；
1.2 数据结构——位棋盘(J.Swafford)；
1.3 数据结构——旋转的位棋盘(J.Swarford)；
1.4 数据结构——着法生成器(J.Swarford)；
1.5 数据结构——0x88着法产生方法(B.Moreland)；
1.6 数据结构——Zobrist键值(B.Moreland)。
二、基本搜索方法
目前象棋程序的搜索算法，都是在“带置换表的启发式Alpha-Beta搜索”基础上发展起来的，这就涵盖了最小-最大搜索、Alpha-Beta搜索、迭代加深和置换表四个内容，把他们归入基本搜索方法的范畴是非常恰当的。
2.1 基本搜索方法——简介(一)(D.Eppstein)
2.2 基本搜索方法——简介(二)(D.Eppstein)
2.3 基本搜索方法——简介(三)(D.Eppstein)
2.3 基本搜索方法——“最小-最大”搜索(B.Moreland)
2.4 基本搜索方法——Alpha-Beta搜索(B.Moreland)
2.5 基本搜索方法——迭代加深(B.Moreland)
2.6 基本搜索方法——换位表(B.Moreland)
三、高级搜索方法
这些方法都是“带置换表的启发式Alpha-Beta搜索”的扩展，其中静态搜索和空着裁剪是消除“水平线效应”的基本手段，而期望窗口、主要变例搜索(PVS)和MTD(f)都是Alpha-Beta搜索的改进。并非所有的棋类游戏都会用到这些方法，而且使用起来会有一些负作用，因此归入高级搜索方法一点也不过分。
3.1 高级搜索方法——简介(一)(D.Eppstein)
3.2 高级搜索方法——简介(二)(D.Eppstein)
3.3 高级搜索方法——静态搜索(B.Moreland)
3.4 高级搜索方法——空着裁剪(B.Moreland)
3.5 高级搜索方法——期望窗口(B.Moreland)
3.6 高级搜索方法——主要变例搜索(B.Moreland)
3.7 高级搜索方法——搜索的不稳定性(B.Moreland)
四、局面评估函数
局面评估函数是对弈程序的核心，很少有特别详细的报道，通常引擎的作者是不愿意公开的。
4.1 局面评估函数——简介(一)(D.Eppstein)
4.2 局面评估函数——简介(二)(D.Eppstein)
五、其他策略
这里包含的内容比较杂，除了后台思考(属于时间控制的范畴)以外，其他方法都不能提高引擎的效率，但能时程序更完善，这些方法主要是针对国际象棋的。
5.1 其他策略——获胜局面(D.Eppstein)
5.2 其他策略——主要变例的获取(B.Moreland)
5.3 其他策略——重复检测(B.Moreland)
5.4 其他策略——藐视因子(B.Moreland)
5.5 其他策略——后台思考(B.Moreland)
5.6 其他策略——残局库(M.Fierz)
5.7 其他策略——开局库(M.Fierz)
5.8 其他策略——策略和技巧(M.Fierz)
浙公网安备 33021202002483