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

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

📁 象棋程序设计全资料集(介绍编写象棋程序的方法思路）
💻 HTM
📖 第 1 页 / 共 2 页
字号:
🔍
12 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0051)http://www.elephantbase.net/computer/other_egtb.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=楷体_GB2312 size=5><STRONG>简介</STRONG></FONT> 
  <DT>　 
  <DT>　　残局库在很多棋类游戏中扮演着非常重要的角色，例如九人<FONT 
  face="Times New Roman">Morris</FONT>，<FONT 
  face="Times New Roman">Awari</FONT>和西洋跳棋<FONT 
  face="Times New Roman">(Checkers)(</FONT>其中九人<FONT 
  face="Times New Roman">Morris</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>，无论如何残局库取决于具体的棋类。例如在国际象棋中，有多达<FONT 
  face="Times New Roman">6</FONT>子的残局库<FONT 
  face="Times New Roman">(</FONT>王车兵对王车兵等<FONT 
  face="Times New Roman">)</FONT>，而这种残局<FONT 
  face="Times New Roman">(</FONT>包括其他不超过<FONT 
  face="Times New Roman">6</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">8</FONT>子的残局库，而<FONT 
  face="Times New Roman">10</FONT>子的残局库也已经在计算了，这就意味着在有吃必吃的规则下，很多棋局会很快走到有残局库的局面中，因此残局库使得西洋跳棋的棋力有了很大的提高。要让某种棋类完全可解，通常总是要借助于残局库的——从起始局面开始向前搜索，结合残局库，就能解出这盘棋。<FONT 
  face="Times New Roman">Gasser</FONT>用这种办法解决了九人<FONT 
  face="Times New Roman">Morris</FONT>，而<FONT 
  face="Times New Roman">Chinook(</FONT>最著名的西洋跳棋程序<FONT 
  face="Times New Roman">)</FONT>的小组正在用这个方法解西洋棋。 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>残局库的不同类型</STRONG></FONT> 
  <DT>　 
  <DT>　　残局库有不同的类型，而它们都可以知道残局库中某个特定的局面是赢棋、是输棋还是和棋。如果这就是残局库包含的所有信息，就称为“胜负和”<FONT 
  face="Times New Roman">(WLD)</FONT>残局库；如果知道多少步以后棋局会结束，就称为“杀棋步数”<FONT 
  face="Times New Roman">(DTM</FONT>，<FONT 
  face="Times New Roman">Distance-to-Mate)</FONT>残局库；如果只知道多少步以后会转换为另一种类型的局面，就称为“转换步数”<FONT 
  face="Times New Roman">(DTC</FONT>，<FONT 
  face="Times New Roman">Distance-to-Conversion)</FONT>残局库。<FONT 
  face="Times New Roman">WLD</FONT>残局库有个问题，即便程序处于胜利局面，也未必能赢下棋局。尽管残局库知道某个局面已经是胜利局面，并且知道走哪步能继续保持胜利局面，但是保持胜利局面的着法可能会距离杀棋更远，而程序又不知道该选择哪步保持胜利局面的着法。<FONT 
  color=#0000ff>【译注：更具体的说明请参阅《</FONT><A 
  href="http://www.elephantbase.net/computer/other_winning.htm" 
  target=_blank><FONT color=#0000ff size=3>胜利局面中的强制过程</FONT></A><FONT 
  color=#0000ff>》一文。】</FONT><FONT 
  face="Times New Roman">DTM</FONT>残局库显然在这个方面做得比较好，因为你只要选择<FONT 
  face="Times New Roman">DTM(</FONT>转换步数<FONT 
  face="Times New Roman">)</FONT>最少的那个保持胜利局面的着法。<FONT 
  face="Times New Roman">DTC</FONT>残局库也能够在胜利局面下走出取得胜利的着法，但程序走的步数可能会比必要的步数多。至今还有人使用<FONT 
  face="Times New Roman">WLD</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">(Retrograde Analysis)</FONT>，它是由<FONT 
  face="Times New Roman">Ken Thompson</FONT>发明的<FONT 
  face="Times New Roman">(</FONT>至少是首先使用的<FONT 
  face="Times New Roman">)</FONT>。以下就是整个过程： 
  <DT>　　以我们要生成“王车对王”的残局为例，你要从“索引函数”<FONT face="Times New Roman">(Index 
  Function)</FONT>开始，每个可能的王车对王局面都有一个数字。索引函数必须能倒过来映射到以数字<FONT 
  face="Times New Roman"><EM>x</EM></FONT>为代表的局面。理想情况下，索引函数会把所有<FONT 
  face="Times New Roman"><EM>N</EM></FONT>个合理的王车对王局面映射为<FONT 
  face="Times New Roman">0, 1, ..., <EM>N</EM> </FONT><FONT 
  face=Symbol>-</FONT><FONT face="Times New Roman"> 
  1</FONT>。如果是这种情况，我们称之为“无间隙”<FONT 
  face="Times New Roman">(Gapless)</FONT>的索引。一般情况下，索引函数把所有合理局面编号为<FONT 
  face="Times New Roman">0, 1, ..., <EM>M</EM> </FONT><FONT 
  face=Symbol>-</FONT><FONT face="Times New Roman"> 1</FONT>，而<FONT 
  face="Times New Roman"><EM>M</EM> &gt; <EM>N</EM></FONT>，我们称其为“有间隙”<FONT 
  face="Times New Roman">(Gapped)</FONT>的索引。有间隙的索引往往更简单，因为构造一个有间隙的索引函数要比无间隙的索引函数简单得多。后退式分析需要的存储器跟索引号的最大值成正比，因此如果构造了一个<FONT 
  face="Times New Roman"><EM>M</EM></FONT>比<FONT 
  face="Times New Roman"><EM>N</EM></FONT>大得多的索引函数，那么你会浪费很多存储器。 
  <DT>　　一旦有了索引函数，后退式分析算法就只要做以下几件事： 
  <DT>　 
  <DT>　　<FONT face="Times New Roman">(1) </FONT>初始化：生成两个长度都为<FONT 
  face="Times New Roman">N</FONT>的数组，分别存放结果<FONT 
  face="Times New Roman">(WIN/LOSS/DRAW</FONT>，代表胜负和<FONT 
  face="Times New Roman">)</FONT>和<FONT 
  face="Times New Roman">DTC</FONT>。把所有的结果都设成<FONT 
  face="Times New Roman">UNKNOWN(</FONT>代表未知<FONT 
  face="Times New Roman">)</FONT>，所有的<FONT 
  face="Times New Roman">DTC</FONT>计数器都设成<FONT 
  face="Times New Roman">0</FONT>。你会发现，你需要<FONT 
  face="Times New Roman">4</FONT>个数来表示结果，因此数组的数据类型是<FONT 
  face="Times New Roman">4</FONT>个值的数<FONT face="Times New Roman">(</FONT>即<FONT 
  face="Times New Roman">2</FONT>位<FONT 
  face="Times New Roman">)</FONT>。当然，还有些根本不存在的局面，你需要自行处理。 
  <DT>　　<FONT face="Times New Roman">(2) 
  </FONT>杀棋遍历：逐一检查每个局面是否是杀棋局面，如果是的，就把这个局面的结果设成<FONT 
  face="Times New Roman">LOSS</FONT>，表示即将走的一方输了。如果棋类允许“逼和”的存在，也必须作逼和的检查，并赋值为<FONT 
  face="Times New Roman">DRAW</FONT>。把每个<FONT 
  face="Times New Roman">UNKNOWN</FONT>局面的<FONT 
  face="Times New Roman">DTC</FONT>计数器加<FONT face="Times New Roman">1</FONT>。 
  <DT>　　<FONT face="Times New Roman">(3) </FONT>对每个<FONT 
  face="Times New Roman">UNKNOWN</FONT>的局面，生成所有后续局面并看它们都有哪些结果。只要其中有一个后续局面是<FONT 
  face="Times New Roman">LOSS</FONT>，就把这个局面设成<FONT 
  face="Times New Roman">WIN</FONT>。如果所有后续局面都是<FONT 
  face="Times New Roman">WIN</FONT>，就把这个局面设成<FONT 
  face="Times New Roman">LOSS</FONT>。如果你遍历了所有局面但没有一个局面能设<FONT 
  face="Times New Roman">WIN</FONT>或<FONT 
  face="Times New Roman">LOSS</FONT>的，就跳到第<FONT 
  face="Times New Roman">5</FONT>步。 
  <DT>　　<FONT face="Times New Roman">(4) </FONT>把每个<FONT 
  face="Times New Roman">UNKNOWN</FONT>局面的<FONT 
  face="Times New Roman">DTC</FONT>计数器加<FONT 
  face="Times New Roman">1</FONT>，并回到第<FONT face="Times New Roman">3</FONT>步。 
  <DT>　　<FONT face="Times New Roman">(5) </FONT>把每个<FONT 
  face="Times New Roman">UNKNOWN</FONT>局面设成<FONT 
  face="Times New Roman">DRAW</FONT>，算法就结束了。 
  <DT>　 
  <DT>　　这个算法显然是确保完成的。在第<FONT 
  face="Times New Roman">3</FONT>步里当吃子发生时，你就要读取少一个子的残局库。很明显，没有王车对王的残局库，你无法独立地生成王车对王马的残局库。如果你只要生成<FONT 
  face="Times New Roman">WLD</FONT>残局库，就可以不要<FONT 
  face="Times New Roman">DTC</FONT>计数器。如果你需要生成<FONT 
  face="Times New Roman">DTM</FONT>残局库，你就需要在局面转换时传递<FONT 
  face="Times New Roman">DTM</FONT>值。以上算法有很多优化方案，但是我不想展开讨论，最基本的算法已经非常简单明了了，为什么再舍弃它呢？ 

  <DT>　　明白了整个算法后，你就知道为什么叫做“后退式”了——该算法总是从已知局面<FONT 
  face="Times New Roman">(</FONT>杀棋或能转换为低级别的残局库局面<FONT 
  face="Times New Roman">)</FONT>向后找，按照上述算法的第<FONT 
  face="Times New Roman">3</FONT>和第<FONT 
  face="Times New Roman">4</FONT>步，每次遍历就后退半步。我们拿一个局面举例说明，白王在<FONT 
  face="Times New Roman">g3</FONT>，黑王在<FONT 
  face="Times New Roman">h1</FONT>，白车在<FONT 
  face="Times New Roman">a2</FONT>，黑先走<FONT color=#0000ff>【</FONT><FONT 
  face="Times New Roman" color=#0000ff>8/8/8/8/8/6K1/R7/7k b - - 0 1</FONT><FONT 
  color=#0000ff>】</FONT>。在遍历杀棋局面时，按照上述算法找到白王在<FONT 
  face="Times New Roman">g3</FONT>，白车在<FONT 
  face="Times New Roman">a1</FONT>，黑王在<FONT 
  face="Times New Roman">g1</FONT>，黑先走<FONT color=#0000ff>【</FONT><FONT 
  face="Times New Roman" color=#0000ff>8/8/8/8/8/6K1/8/R5k1 b - - 0
12

⌨️ 快捷键说明

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