结语——国际象棋程序剖析.htm

象棋程序设计全资料集(介绍编写象棋程序的方法思路）

  size=3>，即假设一方连走两步，如果产生的结果更糟的话，后面那步变化就应该抛弃掉。由于水平线效应，一些看不到的不可避免的失子，通过这种方法能看到。很多向前裁剪方法起不到很好的效果，但空着向前裁剪往往是很有效的。</FONT> 

  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>三、置换表</STRONG></FONT> 
  <DT>　 
  <DT>　　置换表的作用如同缓冲存储器，用来记录前面搜索过的局面，这些局面通常在迭代加深的早期搜索过。之所以称为“置换表”<FONT 
  face="Times New Roman">(Transposition 
  Table)</FONT>，是因为当着法次序发生置换时会有相同的局面。置换表中存储的信息除了局面以外，还有局面的评分，它的最佳着法，以及前一次搜索的深度。 
  <DT>　　“评分”指的是在搜索树的顶端结点(搜索能够到达的水平)对局面进行的评价，这个评价通常包括了静态搜索，来消除由吃子等着法引起的局面的不确定性，包括考虑兵的升变等。 

  <DT>　　在残局的搜索中，置换表的作用发挥得更为明显，每个局面只有很少的着法需要考虑，其他着法都因为置换的发生而不必再去搜索。 
  <DT>　　置换表并不增加代码的长度和复杂性，为置换表分配空间是小事一桩。置换表的每个局面一般需要约<FONT 
  face="Times New Roman">10</FONT>个字节，通常程序使用可以记录<FONT 
  face="Times New Roman">32K</FONT>到<FONT 
  face="Times New Roman">1M</FONT>个局面的置换表。<FONT 
  face="Times New Roman">1993</FONT>年超级电脑<FONT 
  face="Times New Roman">(Supercomputer)</FONT>程序自称他们使用了<FONT 
  face="Times New Roman">1G</FONT>个局面的置换表，而对于程序员来说这完全取决于存储器的容量。 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>四、程序的性能及其测评方法</STRONG></FONT> 
  <DT>　 
  <DT>　　尽管各种程序基本方法是一样的，但是在相同硬件条件下，它们的表现有很大程度的差异，一定程度上这体现了程序设计师对程序所作的投入。 
  <DT>　　比如说，尽管每个程序都有开局库，但开局库是没有哪本书规定的，每个程序小组都在开发自己的开局库。现在开局库的大小从<FONT 
  face="Times New Roman">10,000</FONT>个局面到<FONT 
  face="Times New Roman">500,000</FONT>个局面不等<FONT 
  face="Times New Roman">(</FONT>也有程序试验过<FONT 
  face="Times New Roman">1.7M</FONT>个局面的开局库<FONT 
  face="Times New Roman">)</FONT>。 
  <DT>　　相反，只有少数人使用<FONT face="Times New Roman">Ken Tompson</FONT>制作在<FONT 
  face="Times New Roman">CD-ROM</FONT>上的<FONT 
  face="Times New Roman">5</FONT>子到<FONT 
  face="Times New Roman">6</FONT>子的残局库，一方面原因是目前数据的读取非常缓慢，另一方面原因是大部分棋局都会在用到这些残局库之前结束<FONT 
  face="Times New Roman">(</FONT>程序设计师们在利用时间的问题上，可能考虑得比较现实吧<FONT 
  face="Times New Roman">)</FONT>。 
  <DT>　 
  <DT>　　在运行速度的层面上，当今的程序在单处理器上每秒钟可以分析<FONT 
  face="Times New Roman">3,000</FONT>到<FONT 
  face="Times New Roman">500,000</FONT>个局面。在相同机器上程序速度的差别是巨大的，这当然有很多解释，用汇编语言写的程序能有比较快的速度，用同一语言来写的程序，用不同的编译器也会导致速度的不同。 

  <DT>　　其中更多的因素在于蛮力搜索、选择性搜索和静态搜索这三个阶段所占的比例。选择性搜索阶段需要额外的时间，因为它还判断哪些着法需要搜索，而在这个慢速、以知识为基础的阶段中，诸多程序在速度上的差别是非常明显的。 

  <DT>　　另一个影响搜索速度和强度的因素，是程序使用的置换表的大小。 
  <DT>　 
  <DT>　　尽管很多象棋程序非常相似，它们的棋力差别仍旧可能非常大。测试棋力是很复杂的过程，由于在正式比赛中程序仍然是可调节的，因此“瑞典排名表”<FONT 
  face="Times New Roman">(Swedish Rating 
  List)</FONT>的制作小组提出了一个传统的方案——所有的商业程序都连续自动地进行对决，得到几百场比赛的胜负结果，并从这些结果中计算出<FONT 
  face="Times New Roman">ELO</FONT>等级分，即美国和其他地方棋手们通用的等级分。 
  <DT>　　美国棋手的平均等级分从<FONT face="Times New Roman">1500</FONT>开始，专家的分数在<FONT 
  face="Times New Roman">2000-2200</FONT>，大师在<FONT 
  face="Times New Roman">2200-2400</FONT>。世界排名<FONT 
  face="Times New Roman">300</FONT>以内的特级大师，等级分则更高。在第八届世界电脑象棋锦标赛中，大多数程序的等级分在<FONT 
  face="Times New Roman">2100-2500</FONT>。现在瑞典排名表刊登在每期的《国际电脑象棋协会杂志》<FONT 
  face="Times New Roman">(<EM>International Computer Chess Association 
  Journal</EM>)</FONT>上。 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>五、展望</STRONG></FONT> 
  <DT>　 
  <DT>　　如今顶极的电脑可以挑战特级大师了，尤其是在快棋赛中，单机要比多处理器的并行系统更有优势。单机之所以快，是因为它们不必通过网络来传输着法，而由<FONT 
  face="Times New Roman">10</FONT>到<FONT 
  face="Times New Roman">100</FONT>个处理器组成的多处理器系统，则在两小时内完成<FONT 
  face="Times New Roman">40</FONT>步的标准赛制中表现得更好。不久我们将会有由<FONT 
  face="Times New Roman">1000</FONT>个高性能处理器组成的系统，到那个时候电脑毫无疑问能比人类棋手算得更远，这将多少能弥补电脑的不足——不具备人类棋手所擅长的战略构思。 

  <DT>　　人类棋手对于局势的简化和基本形势的判断方面都具有高超技巧，他们也善于在对手身上找到弱点，除非局面是无法挽回的。尽管人类棋手有这些优势，我们一直以来都预测说，机器在<FONT 
  face="Times New Roman">5</FONT>年内能击败人类，现在这个目标正越来越近。要实现这个目标可能需要花上十多年，但是最终肯定会实现的。 

  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>《国际象棋程序剖析》参考资料</STRONG></FONT> 
  <DT>　 
  <DT>　　<FONT face="Times New Roman">1. </FONT>《电脑象棋概论》<FONT 
  face="Times New Roman">(<EM>Computer Chess Compendium</EM>)</FONT>，<FONT 
  face="Times New Roman">D.N.L. Levy</FONT>著，<FONT 
  face="Times New Roman">Springer-Verlag</FONT>出版社，<FONT 
  face="Times New Roman">1988</FONT>年； 
  <DT>　　<FONT face="Times New Roman">2. </FONT>《电脑象棋与搜索》<FONT 
  face="Times New Roman">(<EM>Computer Chess and Search</EM>)</FONT>，<FONT 
  face="Times New Roman">T.A. Marsland</FONT>文，《人工智能百科全书》<FONT 
  face="Times New Roman">(<EM>Encyclopedia of Artificial 
  Intelligence</EM>)</FONT>一书的<FONT face="Times New Roman">224-241</FONT>页，<FONT 
  face="Times New Roman">S. Shapiro</FONT>主编，<FONT face="Times New Roman">J. 
  Wiley &amp; Sons</FONT>出版社，<FONT face="Times New Roman">1992</FONT>年第二版； 
  <DT>　　<FONT face="Times New Roman">3. </FONT>《<FONT 
  face="Times New Roman">ICCA(</FONT>国际电脑象棋协会<FONT 
  face="Times New Roman">)</FONT>杂志》<FONT 
  face="Times New Roman">(<EM>International Computer Chess Association 
  Journal</EM>)</FONT>，自<FONT face="Times New Roman">1983</FONT>年以来每年四期，<FONT 
  face="Times New Roman">ICCA</FONT>编辑部<FONT 
  face="Times New Roman">([</FONT>荷兰马斯特里赫特<FONT 
  face="Times New Roman">]</FONT>林堡大学<FONT face="Times New Roman">(University of 
  Limburg)</FONT>计算机系，<FONT face="Times New Roman">P.O. Box 616, 6200 MD 
  Maastricht, The Netherlands)</FONT>出版； 
  <DT>　　<FONT face="Times New Roman">4. </FONT>电脑、象棋与认知<FONT 
  face="Times New Roman">(<EM>Computers, Chess and Cognition</EM>)</FONT>，<FONT 
  face="Times New Roman">T.A. Marsland</FONT>和<FONT face="Times New Roman">J. 
  Schaeffer</FONT>主编，<FONT 
  face="Times New Roman">Springer-Verlag</FONT>出版社，<FONT 
  face="Times New Roman">1990</FONT>年； 
  <DT>　　<FONT face="Times New Roman">5. </FONT>电脑象棋进展<FONT 
  face="Times New Roman">(<EM>Advances in Computer 
  Chess</EM>)</FONT>，一至七卷，从<FONT face="Times New Roman">1977</FONT>到<FONT 
  face="Times New Roman">1994</FONT>年由多人主编，由多个出版社出版。 
  <DT>　 
  <DT>　　出处：<A href="http://www.cs.ualberta.ca/~tony/ICCA/anatomy.html" 
  target=_blank><FONT 
  face="Times New Roman">http://www.cs.ualberta.ca/~tony/ICCA/anatomy.html</FONT></A> 

  <DT>　　译者：黄晨 <FONT face="Times New Roman">(</FONT><A 
  href="mailto:[e-mail]"><FONT 
  face="Times New Roman">[e-mail]</FONT></A><FONT 
  face="Times New Roman">)</FONT> 
  <DT>　　类型：全译 </DT></DL>
<DIR>
<LI>上一篇　<A 
href="http://www.elephantbase.net/computer/other_stragy.htm">其他策略——策略和技巧</A> 
<LI>下一篇　<A 
href="http://www.elephantbase.net/computer/eleeye_intro.htm">中国象棋程序设计探索<FONT 
face="Times New Roman">(</FONT>一<FONT face="Times New Roman">)</FONT>：引言</A> 
<LI>返　回　<A href="http://www.elephantbase.net/computer.htm">象棋百科全书——电脑象棋</A> 
</LI></DIR>
<DIV align=center>
<CENTER>
<TABLE border=0>
  <TBODY>
  <TR>
    <TD>
      <P align=center><A href="http://www.elephantbase.net/" target=_blank><IMG 
      height=31 src="结语——国际象棋程序剖析_files/elephantbase.gif" width=88 
      border=0></A></P></TD></TR>
  <TR>
    <TD><A href="http://www.elephantbase.net/" target=_blank><FONT face=Arial 
      size=2><STRONG>www.elephantbase.net</STRONG></FONT></A></TD></TR></TBODY></TABLE></CENTER></DIV></BODY></HTML>