《对弈程序基本技术》专题――概述

时间：08-20来源：作者：点击数：

我花了大量时间翻译了F. D. Laramée的《国际象棋程序设计》(Chess Programming)连载，现在已经具备了设计象棋引擎的能力，但是还需要一些资料。为此，我查找了各个象棋程序设计的网站，收集了很多专题性的文章，并且整理成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)

五、其他策略