⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 解剖大象的眼睛——中国象棋程序设计探索(四)：启发算法.htm

📁 象棋程序设计全资料集(介绍编写象棋程序的方法思路）
💻 HTM
📖 第 1 页 / 共 2 页
字号:
🔍
12 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0057)http://www.elephantbase.net/computer/eleeye_heuristic.htm -->
<HTML><HEAD><TITLE>解剖大象的眼睛——中国象棋程序设计探索(四)：启发算法</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="MSHTML 6.00.3790.536" name=GENERATOR></HEAD>
<BODY background=解剖大象的眼睛——中国象棋程序设计探索(四)：启发算法_files/background.gif>
<DL>
  <DIV align=center>
  <CENTER>
  <DT><FONT face=隶书 size=6>解剖大象的眼睛</FONT><FONT 
  size=6><STRONG>——</STRONG></FONT><FONT face=隶书 size=6>中国象棋程序设计探索</FONT> 
  </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT>　 </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT>黄晨 <FONT face="Times New Roman">*</FONT>　<FONT 
  face="Times New Roman">2005</FONT>年<FONT 
  face="Times New Roman">6</FONT>月初稿，<FONT 
  face="Times New Roman">2005</FONT>年<FONT face="Times New Roman">11</FONT>月修订 
  </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT><FONT face="Times New Roman">( * </FONT>联系地址：复旦大学化学系表面化学实验室，<FONT 
  face="Times New Roman">eMail</FONT>：<A 
  href="mailto:webmaster@elephantbase.net"><FONT 
  face="Times New Roman">webmaster@elephantbase.net</FONT></A><FONT 
  face="Times New Roman">)</FONT> </CENTER></DT></DIV>
  <DT>　 
  <DT><FONT face=Arial size=5><STRONG>(</STRONG></FONT><FONT face=楷体_GB2312 
  size=5><STRONG>四</STRONG></FONT><FONT face=Arial size=5><STRONG>) 
  </STRONG></FONT><FONT face=楷体_GB2312 size=5><STRONG>启发算法</STRONG></FONT> 
  <DT>　 
  <DT><FONT face=Arial size=4><STRONG>4.1 </STRONG></FONT><FONT face=楷体_GB2312 
  size=4><STRONG>启发算法概述</STRONG></FONT> 
  <DT>　 
  <DT>　　<FONT face="Times New Roman">Laram</FONT>é<FONT 
  face="Times New Roman">e</FONT>的《<A 
  href="http://www.elephantbase.net/computer/basic_search.htm" 
  target=_blank>国际象棋程序设计<FONT face="Times New Roman">(</FONT>四<FONT 
  face="Times New Roman">)</FONT>：基本搜索方法</A>》连载中曾经提到，<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索的结点数，数量相当于最笨的“最小<FONT 
  face="Times New Roman">-</FONT>最大”搜索的平方根。严格来说，如果搜索树在每个结点的分枝因子都是<FONT 
  face="Times New Roman"><EM>b</EM></FONT>，那么<FONT 
  face="Times New Roman"><EM>d</EM></FONT>层<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索在最好情况下搜索的结点数是：<FONT 
  face="Times New Roman"><EM>b</EM><SUP>[<EM>d</EM> / 2]</SUP> + 
  <EM>b</EM><SUP>[(<EM>d </EM>+ 1) / 2] </SUP></FONT><FONT 
  face=Symbol>-</FONT><FONT face="Times New Roman"> 1(</FONT>都是指叶子结点，其中<FONT 
  face="Times New Roman"><EM>b</EM><SUP>[<EM>d</EM> / 2] </SUP></FONT><FONT 
  face=Symbol>-</FONT><FONT face="Times New Roman"> 1</FONT>个是<FONT 
  face="Times New Roman">Alpha</FONT>结点，<FONT 
  face="Times New Roman"><EM>b</EM><SUP>[(<EM>d</EM> + 1) / 2] 
  </SUP></FONT><FONT face=Symbol>-</FONT><FONT face="Times New Roman"> 
  1</FONT>个是<FONT face="Times New Roman">Beta</FONT>结点，<FONT 
  face="Times New Roman">1</FONT>个是<FONT face="Times New Roman">PV</FONT>结点<FONT 
  face="Times New Roman">)</FONT>，这样的搜索树称为“最小树”。因此，让<FONT 
  face="Times New Roman">Alpha-Beta</FONT>的搜索树尽可能地接近最小树是非常重要的，相关的措施在广义上都称为“启发”<FONT 
  face="Times New Roman">(Heuristic)</FONT>。 
  <DT>　　由于<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索对着法顺序非常敏感，因此对着法进行排序，是体现<FONT 
  face="Times New Roman">Alpha-Beta</FONT>算法效率的关键所在，这就是我们狭义上所说的启发，即通过排序尽量首先搜索最好的着法。着法启发通常有置换表启发、吃子启发、杀手着法启发和历史表启发这四种最为常用的算法。广义上的启发还可以通过改变窗口宽度来实现，因为改变窗口宽度也可以提高<FONT 
  face="Times New Roman">Alpha-Beta</FONT>的截断效率，因此很多<FONT 
  face="Times New Roman">Alpha-Beta</FONT>的变种算法实际上都属于启发这个范畴，例如期望窗口、<FONT 
  face="Times New Roman">PVS</FONT>和<FONT 
  face="Times New Roman">MTD(<EM>f</EM>)</FONT>。 
  <DT>　　本章我们只讨论着法启发。 
  <DT>　 
  <DT><FONT face=Arial size=4><STRONG>4.2 </STRONG></FONT><FONT face=楷体_GB2312 
  size=4><STRONG>静态着法启发</STRONG></FONT> 
  <DT>　 
  <DT>　　静态着法启发是指不依赖于搜索结果的着法排序方式，即程序分析了某个局面后，不经过搜索，就大致应该知道哪些着法应该首先尝试。在上面提到的<FONT 
  face="Times New Roman">4</FONT>种着法启发中，吃子启发是静态着法启发，因为吃子着法数量不多，而且往往很多情况能立刻得到实惠，所以需要首先考虑。而置换表启发、杀手着法启发和历史表启发，都依赖于以前搜索的结果，因此属于动态着法启发的范畴。 

  <DT>　　在<FONT 
  face="Times New Roman">ElephantEye</FONT>中，吃子着法是有选择的，即“表面上立刻能得到实惠”的着法。为此<FONT 
  face="Times New Roman">ElephantEye</FONT>用了一个称为<FONT 
  face="Times New Roman">MVV(LVA)</FONT>的策略，在被吃子有保护的情况下，考虑<FONT 
  face="Times New Roman">MVV(</FONT>被吃子价值<FONT 
  face="Times New Roman">)-LVA(</FONT>攻击子价值<FONT 
  face="Times New Roman">)</FONT>的值，而在被吃子没保护的情况下，只考虑<FONT 
  face="Times New Roman">MVV</FONT>的值，然后对这种策略产生的<FONT 
  face="Times New Roman">MVV(LVA)</FONT>值作排序，并选择<FONT 
  face="Times New Roman">MVV(LVA)</FONT>大于零的着法首先搜索。为此，<FONT 
  face="Times New Roman">&lt;genmoves.cpp&gt;</FONT>提供了一个称为“<FONT 
  face="Times New Roman">Protected()</FONT>”的函数，对某个棋子是否有保护作快速判断。 
  <DT>　　吃子启发仅仅是静态着法启发的最明显的表现，事实上这类启发还体现在其他地方。当搜索进行初期，置换表、杀手着法、历史表等动态着法启发还没起作用，此时着法生成的顺序就起了主要作用。因此，在着法生成时，考虑首先生成车的着法，最后生成帅<FONT 
  face="Times New Roman">(</FONT>将<FONT 
  face="Times New Roman">)</FONT>的着法，往往是很有效的；而在生成车的着法时，首先生成车向前走的着法，然后生成车向后走的着法，也能起到一定的启发作用。因此，这种静态着法启发也是很多程序所考虑的。 

  <DT>　 
  <DT><FONT face=Arial size=4><STRONG>4.3</STRONG></FONT><FONT face=楷体_GB2312 
  size=4><STRONG> 置换表启发和低出</STRONG></FONT><FONT face=Arial 
  size=4><STRONG>(</STRONG></FONT><FONT face=楷体_GB2312 
  size=4><STRONG>高出</STRONG></FONT><FONT face=Arial 
  size=4><STRONG>)</STRONG></FONT><FONT face=楷体_GB2312 
  size=4><STRONG>边界的修正</STRONG></FONT> 
  <DT>　 
  <DT>　　在置换表中保存一个着法，一方面可以利用置换表来获得主要变例，但最主要的作用是置换表启发。在探测置换表时，尽管局面命中但深度没达到要求时，至少可以得到一个着法，这个着法应该首先搜索，几乎所有的象棋程序都是这么做的。哪些着法应该被保存到置换表中呢？实践证明，<FONT 
  face="Times New Roman">PV</FONT>结点中的最佳着法，以及<FONT 
  face="Times New Roman">Beta</FONT>结点中产生截断的着法，都应该被保存到置换表中，而<FONT 
  face="Times New Roman">Alpha</FONT>结点尽管也要保存，但不要保存着法<FONT 
  face="Times New Roman">(</FONT>置换表着法是空的<FONT 
  face="Times New Roman">)</FONT>，因为<FONT 
  face="Times New Roman">Alpha</FONT>结点的每个着法都返回<FONT 
  face="Times New Roman">Alpha</FONT>值，我们不知道哪个着法是最好的。 
  <DT>　　显然，当探测置换表时找到<FONT face="Times New Roman">PV</FONT>结点或<FONT 
  face="Times New Roman">Beta</FONT>结点<FONT 
  face="Times New Roman">(</FONT>但深度不够<FONT 
  face="Times New Roman">)</FONT>，就会有需要首先搜索的置换表着法。那么，找到<FONT 
  face="Times New Roman">Alpha</FONT>结点时，是否还会有置换表着法呢？中国象棋程序“纵马奔流”采取了一个称为“低出<FONT 
  face="Times New Roman">(</FONT>高出<FONT 
  face="Times New Roman">)</FONT>边界的修正”策略，使得某些<FONT 
  face="Times New Roman">Alpha</FONT>结点也存在置换表着法。 
  <DT>　　“低出边界的修正”指的是，当某个<FONT 
  face="Times New Roman">Alpha</FONT>结点覆盖某个相同局面的置换表项时，保留该表项的最佳着法。相应地，当某个<FONT 
  face="Times New Roman">Beta</FONT>结点没能覆盖某个相同局面的置换表项<FONT 
  face="Times New Roman">(</FONT>该表项记录了一个没有着法的<FONT 
  face="Times New Roman">Alpha</FONT>结点<FONT 
  face="Times New Roman">)</FONT>时，只把这个<FONT 
  face="Times New Roman">Beta</FONT>结点的截断着法写入该置换表项，称为“高出边界的修正”。在前一章介绍的双层置换表的覆盖策略中，第一层<FONT 
  face="Times New Roman">(</FONT>深度优先<FONT 
  face="Times New Roman">)</FONT>需要考虑“低出边界的修正”和“高出边界的修正”，而第二层<FONT 
  face="Times New Roman">(</FONT>始终覆盖<FONT 
  face="Times New Roman">)</FONT>则只需要考虑“低出边界的修正”。 
  <DT>　 
  <DT><FONT face=Arial size=4><STRONG>4.4 </STRONG></FONT><FONT face=楷体_GB2312 
  size=4><STRONG>杀手着法启发</STRONG></FONT> 
  <DT>　 
  <DT>　　杀手着法启发<FONT face="Times New Roman">(Killer 
  Heuristic)</FONT>是基于这样一个思想，搜索某个结点时首先尝试着法<FONT 
  face="Times New Roman"><EM>a</EM><SUB>1</SUB></FONT>，由<FONT 
  face="Times New Roman"><EM>a</EM><SUB>1</SUB></FONT>的后续着法<FONT 
  face="Times New Roman"><EM>b</EM><SUB>1</SUB></FONT>产生截断，回到原来的结点时再搜索<FONT 
  face="Times New Roman"><EM>a</EM><SUB>1</SUB></FONT>的兄弟结点<FONT 
  face="Times New Roman"><EM>a</EM><SUB>2</SUB></FONT>时，如果<FONT 
  face="Times New Roman"><EM>b</EM><SUB>1</SUB></FONT>仍旧是<FONT 
  face="Times New Roman"><EM>a</EM><SUB>2</SUB></FONT>的后续着法，那么<FONT 
  face="Times New Roman"><EM>b</EM><SUB>1</SUB></FONT>很有可能也会产生截断。 
  <DT>　　采用杀手着法启发时，需要构造一个称为<FONT 
  face="Times New Roman">KillerMoves[MaxPly]</FONT>的全局数组。搜索到深度为<FONT 
  face="Times New Roman">Ply</FONT>的结点时，首先尝试<FONT 
  face="Times New Roman">KillerMoves[Ply]</FONT>的着法<FONT 
  face="Times New Roman">(</FONT>前提是该着法在当前局面下是合理的<FONT 
  face="Times New Roman">)</FONT>，搜索完这个结点时，把产生截断的着法<FONT 
  face="Times New Roman">(</FONT>如果有的话<FONT
12

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -