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

📄 局面评估函数——简介(一).htm

📁 象棋程序设计全资料集(介绍编写象棋程序的方法思路）
💻 HTM
📖 第 1 页 / 共 2 页
字号:
🔍
12 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0054)http://www.elephantbase.net/computer/evalue_intro1.htm -->
<HTML><HEAD><TITLE>局面评估函数——简介(一)</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="" name=Owner>
<META content="" name=Reply-To>
<META content="MSHTML 6.00.3790.2817" 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">David Eppstein */</FONT>文 
</CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT><FONT face="Times New Roman">* </FONT>加州爱尔文大学<FONT 
  face="Times New Roman">(UC Irvine)</FONT>信息与计算机科学系 </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT>　 </CENTER></DT></DIV>
  <DT><FONT face=楷体_GB2312 size=5><STRONG>整体考虑</STRONG></FONT> 
  <DT>　 
  <DT>　　在你的程序中，评价函数综合了大量跟具体棋类有关的知识。我们从以下两个基本假设开始： 
  <DT>　　<FONT face="Times New Roman">(1) 
  </FONT>我们能把局面的性质量化成一个数字。例如，这个数字可以是对取胜的概率作出的估计；但是大多数程序不给这个数字以如此确定的含义，因此这仅仅是一个数子而已。 

  <DT>　　<FONT face="Times New Roman">(2) </FONT>我们衡量的这个性质应该跟对手衡量的性质是一样的<FONT 
  face="Times New Roman">(</FONT>如果我们认为我们处于优势，那么反过来对手认为他处于劣势<FONT 
  face="Times New Roman">)</FONT>。真实情况并非如此，但是这个假设可以让我们的搜索算法正常工作，而且在实战中它跟真实情况非常接近。 

  <DT>　　评价可以是简单的或复杂的，这取决于你在程序中加了多少知识。评价越复杂，包含知识的代码就越多，程序就越慢。通常，程序的质量<FONT 
  face="Times New Roman">(</FONT>它棋下得怎样<FONT 
  face="Times New Roman">)</FONT>可以通过知识和速度的乘积来估计： 
  <DT>　 
  <DIV align=center>
  <CENTER></DIV>
  <DT>　 </CENTER>
  <DIV></DIV>
  <DIV align=center>
  <CENTER></DIV>
  <DT><IMG height=305 src="局面评估函数——简介(一)_files/evalue_intro1.gif" width=428> 
  </CENTER>
  <DIV></DIV>
  <DT>　 
  <DT>　　因此，如果你有一个快速而笨拙的程序，你通常可以加一些知识让它慢下来，使它工作得更好。但是同样是增加知识让程序慢下来，对一个比较聪明但很慢的程序来说，可能会更糟；知识对棋力的增长作用会减少的。类似地，你增加程序的速度，到一定程度后，速度对棋力的提高作用也会减少，你最好在速度和知识上寻求平衡，达到图表中间的位置。平衡点也会随着你面对的对手而改变；对于击败其他电脑，速度的表现更好，而人类对手则善于寻找你的程序中对于知识的漏洞，从而轻松击败基于知识的程序。<FONT 
  color=#0000ff>【译注：如果你的程序要和人类棋手比，那么最好给程序加上足够多的知识。】</FONT> 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>实现方法</STRONG></FONT> 
  <DT>　 
  <DT>　　就评价方法而言主要有两个类型。第一个是“终点评价”<FONT face="Times New Roman">(End-Point 
  Evaluation)</FONT>，即用你擅长的评价算法，简单地评价每个局面，而不受其他局面的影响。这通常会给出好的结果，但是非常慢。因此一些程序设计师用了下面的诀窍，称为预先计算<FONT 
  face="Times New Roman">(Pre-Computation)</FONT>，一阶评价<FONT 
  face="Times New Roman">(First-Order Evaluation)</FONT>，或棋子<FONT 
  face="Times New Roman">-</FONT>格子数组<FONT face="Times New Roman">(Piece-Square 
  Tables)</FONT>。 
  <DT>　　在我们对一个局面搜索最佳着法之前，我们认真检查棋局本身，在数组<FONT 
  face="Times New Roman">T[</FONT>格子，棋子类型<FONT 
  face="Times New Roman">]</FONT>中保存计算值。在搜索过程中评价任何局面，只要简单地把棋子在数组中的值加起来就行了。我们不必每一步都重新计算它们的和，在把棋子从一个格子移到另一个格子时，可以用下面的公式更新评价值： 

  <DD>　 
  <DD>score += T[新的格子，棋子] - T[旧的格子，棋子] 
  <DT>　 
  <DT>　　下面就举一个例子说明国际象棋中的棋子<FONT 
  face="Times New Roman">-</FONT>格子数组：当王被易位到棋盘的角落时，王前面的几个兵对防御来说是非常有用的。它们前进后防御能力就变差。因此，如果搜索的开始局面王在角落里，我们就应该为这些兵建立一个棋子<FONT 
  face="Times New Roman">-</FONT>格子数组，其值如下： 
  <DD>　 
  <DD>
  <TABLE border=1>
    <TBODY>
    <TR>
      <TD align=middle><FONT 
      face="Times New Roman"><STRONG>...</STRONG></FONT></TD>
      <TD align=middle><FONT 
      face="Times New Roman"><STRONG>...</STRONG></FONT></TD>
      <TD align=middle><FONT 
      face="Times New Roman"><STRONG>...</STRONG></FONT></TD>
      <TD align=middle><FONT 
      face="Times New Roman"><STRONG>...</STRONG></FONT></TD>
      <TD align=middle><FONT 
      face="Times New Roman"><STRONG>...</STRONG></FONT></TD></TR>
    <TR>
      <TD align=middle><FONT 
      face="Times New Roman"><STRONG>...</STRONG></FONT></TD>
      <TD align=middle><FONT 
      face="Times New Roman"><STRONG>1</STRONG></FONT></TD>
      <TD align=middle><FONT 
      face="Times New Roman"><STRONG>1</STRONG></FONT></TD>
      <TD align=middle><FONT 
      face="Times New Roman"><STRONG>1</STRONG></FONT></TD>
      <TD align=middle><FONT 
      face="Times New Roman"><STRONG>1</STRONG></FONT></TD></TR>
    <TR>
      <TD align=middle><FONT 
      face="Times New Roman"><STRONG>...</STRONG></FONT></TD>
      <TD align=middle><FONT 
      face="Times New Roman"><STRONG>1</STRONG></FONT></TD>
      <TD align=middle><FONT 
      face="Times New Roman"><STRONG>1.1</STRONG></FONT></TD>
      <TD align=middle><FONT 
      face="Times New Roman"><STRONG>1.1</STRONG></FONT></TD>
      <TD align=middle><FONT 
      face="Times New Roman"><STRONG>1.1</STRONG></FONT></TD></TR>
    <TR>
      <TD align=middle><FONT 
      face="Times New Roman"><STRONG>...</STRONG></FONT></TD>
      <TD align=middle><FONT 
      face="Times New Roman"><STRONG>1</STRONG></FONT></TD>
      <TD align=middle><FONT 
      face="Times New Roman"><STRONG>1.2</STRONG></FONT></TD>
      <TD align=middle><FONT 
      face="Times New Roman"><STRONG>1.2</STRONG></FONT></TD>
      <TD align=middle><FONT 
      face="Times New Roman"><STRONG>1.2</STRONG></FONT></TD></TR>
    <TR>
      <TD align=middle><FONT 
      face="Times New Roman"><STRONG>...</STRONG></FONT></TD>
      <TD align=middle><FONT face="Times New Roman">-</FONT></TD>
      <TD align=middle><FONT face="Times New Roman">-</FONT></TD>
      <TD align=middle><FONT face="Times New Roman">-</FONT></TD>
      <TD align=middle><FONT 
  face="Times New Roman">-</FONT></TD></TR></TBODY></TABLE>
  <DT>　 
  <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>格子数组的值就会非常不准确，因为它只是让兵防御王原来待的地方，而不是防御王本身。 
  <DT>　　用棋子<FONT face="Times New Roman">-</FONT>格子数组的程序通常需要结合终点评价。另一个建立棋子<FONT 
  face="Times New Roman">-</FONT>格子数组的策略，就是把数组的建立延迟到后面的搜索中。例如，你要搜索<FONT 
  face="Times New Roman">9</FONT>步后续着法，那么可以在<FONT 
  face="Times New Roman">5</FONT>步的后续着法下建立数组，为剩下的<FONT 
  face="Times New Roman">4</FONT>步搜索作准备。如果你想这么做，就应该使一个<FONT 
  face="Times New Roman">5</FONT>步着法产生的数组和其他着法产生的数组保持一致，使得所有的评价值都有可比性。在我的课上<FONT 
  face="Times New Roman">O. Dave</FONT>提出另一个改进的建议：用增量的办法修改棋子<FONT 
  face="Times New Roman">-</FONT>格子数组，例如当王走掉时，对王前几个兵的奖励值也去掉了。这看上去是个不错的思想，但是我不知道如何来实现，也不知道如果实现了，效果会是怎样。 

  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>如何组合评价要素</STRONG></FONT> 
  <DT>　 
  <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">bs</FONT>表示而白方用<FONT 
  face="Times New Roman">ws</FONT>，在很多回合以后获胜<FONT 
  face="Times New Roman">(</FONT>即不是很快获胜<FONT 
  face="Times New Roman">)</FONT>的可能性是<FONT 
  face="Times New Roman">bm</FONT>或<FONT 
  face="Times New Roman">wm</FONT>，而在残局中获胜的可能性是<FONT 
  face="Times New Roman">be</FONT>或<FONT 
  face="Times New Roman">we</FONT>，那么整个获胜的可能性就是： 
  <DD>　 
  <DD>bs + (1 - bs - ws) * bm + (1 - bs - ws - bm - wm) * be，或者 
  <DD>ws + (1 - bs - ws) * wm + (1 - bs - ws - bm - wm) * we 
  <DT>　 
  <DT>　　我想，通过和类似上面的公式把若干单独概率结合起来，在评价函数中或许是个很好的估计概率的思路。每种概率是否估计得好，这就需要用程序的估计来和数据库中棋局的真实结果来作比较，这就需要让程序具有基本判断的能力<FONT 
  face="Times New Roman">(</FONT>判断某种攻击是否能起到效果<FONT 
  face="Times New Roman">)</FONT>。但是这纯粹是我的假想，并没有在程序中测试过，如果你只用加法将不会犯多大的错。 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>评价函数中要加入哪些信息？</STRONG></FONT> 
  <DT>　 
  <DT>　　典型的评价函数，要把下列不同类型的知识整理成代码，并组合起来： 
  <DT>　 
  <DT><STRONG>　　</STRONG><FONT face="Times New Roman"><STRONG>(1) 
  </STRONG></FONT><STRONG>子力</STRONG><FONT 
  face="Times New Roman"><STRONG>(Material)</STRONG></FONT><STRONG>：</STRONG>在国际象棋中，它是子力价值的和，在围棋或黑白棋中，它是双方棋盘上棋子的数量。这种评价通常是有效的，但是黑白棋有个有趣的反例：棋局只由最后的子数决定，而在中局里，根据子力来评价却是很差的思路，因为好的局势下子数通常很少。其他像五子棋一样的游戏，子力是没有作用的，因为好坏仅仅取决于棋子在棋盘上的位置，看它是否能发挥作用。 

  <DT>　
12

⌨️ 快捷键说明

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