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

📄 其他策略——开局库.htm

📁 象棋程序设计全资料集(介绍编写象棋程序的方法思路）
💻 HTM
字号:
🔍 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0051)http://www.elephantbase.net/computer/other_book.htm -->
<HTML><HEAD><TITLE>其他策略——开局库</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="MSHTML 6.00.3790.2759" name=GENERATOR></HEAD>
<BODY background=其他策略——开局库_files/background.gif>
<DL>
  <DIV align=center>
  <CENTER>
  <DT>《对弈程序基本技术》专题 </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT>　 </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT><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">Martin Fierz */ </FONT>文 </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT><FONT face="Times New Roman">* </FONT>瑞士<FONT 
  face="Times New Roman">Windisch</FONT>应用科学学院<FONT 
  face="Times New Roman">(Aargau</FONT>学院<FONT face="Times New Roman">)</FONT> 
  </CENTER></DT></DIV>
  <DT>　 
  <DT>　　不管你是否喜欢，开局库在很多棋类中都是非常重要的。很多棋类已经被人类积累了大量知识<FONT 
  face="Times New Roman">(</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>例如国际象棋<FONT 
  face="Times New Roman">)</FONT>，建立开局库有个非常简单的办法，即手工产生，选择高手走的棋。这种方法不是我们感兴趣的，而对于一些没有理论可寻的，或者电脑足以战胜人类<FONT 
  face="Times New Roman">(</FONT>例如西洋跳棋<FONT 
  face="Times New Roman">)</FONT>的棋类，用这个方法是不可取的。我们将会关注一种没有人工干预的生成开局库的方法。 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>从数据库自动生成</STRONG></FONT> 
  <DT>　 
  <DT>　　要生成开局库，有个简单的方法就是找一个对局数据库，根据对局结果来选择可靠的着法。我的国际象棋程序的开局库就是这样生成的，很多国际象棋程序也都使用这种方法。对于国际象棋来说，有高质量的数据库，其中包括很多高等级分棋手下的，因此你可以决定仅仅使用高等级分棋手的对局。对于每个局面，可以生成所有着法的统计数字，例如这步着法的分数，下这步着法的棋手平均等级分，这步着法得到的平均结果，以及用结果衡量和用棋手等级分衡量的不同之处。有的对局会以符号“<FONT 
  face="Times New Roman">!</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>妙着<FONT 
  face="Times New Roman">)</FONT>作评论，把这种评论考虑进去也是可行的，但我不知道是否有人这么做。我的国际象棋程序的开局库只参照统计数字，采用棋手等级分最高的着法。 

  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>由“脱离棋谱的扩展”自动生成</STRONG></FONT> 
  <DT>　 
  <DT>　　如果没有人类积累的棋类理论，那么你就不得不自己计算开局库了。任何计算开局库的方法，都需要用称为“博弈树”的图来表达，图上的每个结点代表一个局面。对于每个局面，你需要计算所有可能着法的值，因此每个候选着法都要扩展。跟这个图表相应，你还必须找到一个方法来决定哪些结点是需要展开的，也就是说，图表上的哪个叶子结点需要再添加结点。这里我将介绍一个称为“脱离棋谱的扩展”<FONT 
  face="Times New Roman">(DOE</FONT>，<FONT face="Times New Roman">Drop-out 
  Expansion)</FONT>的方法，它是由<FONT face="Times New Roman">Thomas 
  Lincke</FONT>发明的。<FONT 
  face="Times New Roman">DOE</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>。因此，开局库生成器只能对一方生成最好的一些着法，而对方应该能走好的或不好的着法。首先，<FONT 
  face="Times New Roman">DOE</FONT>生成器会需要产生一个图表，它对每个结点的后续着法都有一个评价。然后需要一个优先函数，对每个可能的路径<FONT 
  face="Times New Roman">(</FONT>在<FONT 
  face="Times New Roman">DOE</FONT>限制下，一方只走最好的着法<FONT 
  face="Times New Roman">)</FONT>都可以给出一个优先值，对优先级高的路径的叶子结点作扩展。这个策略使得它要做很烦琐的并行计算，如果你有计算机集群，那么你可以在主机上运行<FONT 
  face="Times New Roman">DOE</FONT>生成器，而众多子机上对每个局面做精确的计算。路径优先级的计算相对来说比较随意，你可以用类似下面的方法来做： 

  <DD>　 
  <DD><FONT size=3>delta = sum_of_errors(path);</FONT> 
  <DD><FONT size=3>depth = length(path);</FONT> 
  <DD><FONT size=3>priority = -delta - CONST * depth;</FONT> 
  <DT>　 
  <DT>　　这个优先函数会使对手的好的着法搜索得深一些，对手犯错误的着法搜索得浅一些。你可以在优先级的计算中加入其他因素，例如衡量结点重要性的因素。<FONT 
  face="Times New Roman">Thomas Lincke</FONT>在他的优先函数中使用过“策略数”<FONT 
  face="Times New Roman">(Conspiracy Number)</FONT>，我的程序则衡量结点的单一性<FONT 
  face="Times New Roman">(Singularity)</FONT>，也就是说，最好和次好的着法差距很大，这条路线就搜索得深一些。 
  <DT>　 
  <DT><FONT face=Arial size=5><STRONG>DOE</STRONG></FONT><FONT face=楷体_GB2312 
  size=5><STRONG>的现状</STRONG></FONT> 
  <DT>　 
  <DT>　　<FONT face="Times New Roman">DOE</FONT>是一个比较新的技术，在西洋跳棋<FONT 
  face="Times New Roman">(</FONT>我和<FONT face="Times New Roman">Ed 
  Gilbert</FONT>的程序<FONT face="Times New Roman">)</FONT>和<FONT 
  face="Times New Roman">Awari(Thomas Lincke</FONT>的程序<FONT 
  face="Times New Roman">)</FONT>中用得比较成功。我的西洋跳棋的<FONT 
  face="Times New Roman">DOE</FONT>生成器已经在一台单机上运行了近<FONT 
  face="Times New Roman">2</FONT>年了，生成的开局库基本上不再有差错了<FONT 
  face="Times New Roman">(</FONT>在一台很快的个人电脑上计算了<FONT 
  face="Times New Roman">1</FONT>年半以后<FONT 
  face="Times New Roman">)</FONT>，或许还能够纠正人们对这种棋类在开局上的错误认识。我之所以说“基本上”，是因为目前我知道的着法中没有错误，但是也有可能开局库的成千上万个着法里会隐藏着几个坏的着法。半年前我和<FONT 
  face="Times New Roman">Ed Gilbert</FONT>让我们的引擎比了<FONT 
  face="Times New Roman">624</FONT>盘棋，我的程序<FONT 
  face="Times New Roman">Cake</FONT>战绩是<FONT 
  face="Times New Roman">3</FONT>胜<FONT face="Times New Roman">1</FONT>负，其余<FONT 
  face="Times New Roman">620</FONT>盘是和棋，和棋率是那么的高！输的那局揭示了我的开局库里的一个问题，现在已经修补好了。 
  <DT>　 
  <DT>　　原文：<A href="http://www.fierz.ch/strategy4.htm" target=_blank><FONT 
  face="Times New Roman">http://www.fierz.ch/strategy4.htm</FONT></A> 
  <DT>　　译者：黄晨 <FONT face="Times New Roman">(</FONT><A 
  href="mailto:webmaster@elephantbase.net"><FONT 
  face="Times New Roman">webmaster@elephantbase.net</FONT></A><FONT 
  face="Times New Roman">)</FONT> 
  <DT>　　类型：全译 </DT></DL>
<DIR>
<LI>上一篇　<A 
href="http://www.elephantbase.net/computer/other_egtb.htm">其他策略——残局库</A> 
<LI>下一篇　<A 
href="http://www.elephantbase.net/computer/other_stragy.htm">其他策略——策略和技巧</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>

⌨️ 快捷键说明

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