《对弈程序基本技术》专题
　
概述
　
象棋百科全书网 (webmaster@xqbase.com)　2005年9月
　
　　我花了大量时间翻译了F. D. Laramée的《国际象棋程序设计》(Chess Programming)连载，现在已经具备了设计象棋引擎的能力，但是还需要一些资料。为此，我查找了各个象棋程序设计的网站，收集了很多专题性的文章，并且整理成Laramée写他的连载时形成的体系。
　　我整理的文章除了T. A. Marsland的《国际象棋程序剖析》一文外，把它们分成四类，它们分别对应了Laramée的连载的四个部分。由于是从不同的网站上收集的，作者也各不相同，他们分别是：
一、数据结构
　
　　这部分内容极其丰富，不仅包括棋盘的表示方法，还包括着法产生当中需要用到的数据结构。我把关于“着法产生”的文章也并入其中，因为这部分内容实在很难归为一类，因此它代表了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)
  • 上一篇　国际象棋程序设计(六)：局面评估函数
  • 下一篇　数据结构——简介
  • 返　回　象棋百科全书——电脑象棋
    •

    www.xqbase.com