📄 结语——国际象棋程序剖析.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0048)http://www.elephantbase.net/computer/anatomy.htm -->
<HTML><HEAD><TITLE>结语——国际象棋程序剖析</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="MSHTML 6.00.3790.2817" name=GENERATOR><!-- This document was created from RTF source by rtftohtml version2.7.5 --></HEAD>
<BODY background=结语——国际象棋程序剖析_files/background.gif>
<DL>
<DIV align=center>
<CENTER>
<DT><FONT size=3>《对弈程序基本技术》专题</FONT> </CENTER></DT></DIV>
<DT>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face=隶书 size=6>国际象棋程序剖析</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman" size=3>T.A. Marsland */ </FONT><FONT
size=3>文</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT><FONT face="Times New Roman" size=3>* </FONT><FONT
size=3>阿尔伯达大学计算机科学系</FONT> </CENTER>
<DIV></DIV>
<DIV align=center>
<CENTER></DIV>
<DT> </CENTER>
<DIV></DIV>
<DT><FONT face=楷体_GB2312 size=5><STRONG>一、简介</STRONG></FONT>
<DT>
<DT><FONT
size=3> 从理论上说，让机器下国际象棋是一个简单的游戏，只要每一步都考虑各种可能的着法，以及每种着法的后续变化，如此下去直到将死或和棋。但是实际操作中，这种策略是不可行的，因为需要考虑的每种着法加起来会是天文数字。</FONT>
<DT><FONT
size=3> 不管人类还是机器去下棋，都有一整套下棋的理论，人类好几百年前就开始下棋，在近二百年里有很多理论资料，而机器下棋只有五十多年的历史，在机器下棋的诸多理论中，最著名的属</FONT><FONT
face="Times New Roman" size=3>Claude Shannon</FONT><FONT size=3>在</FONT><FONT
face="Times New Roman" size=3>1949-50</FONT><FONT
size=3>年提出的两个完全对立的策略——用蛮力考虑所有着法的策略</FONT><FONT face="Times New Roman"
size=3>(A</FONT><FONT size=3>策略</FONT><FONT face="Times New Roman"
size=3>)</FONT><FONT size=3>，以及靠知识来选择其中一部分着法的策略</FONT><FONT
face="Times New Roman" size=3>(B</FONT><FONT size=3>策略</FONT><FONT
face="Times New Roman" size=3>)</FONT><FONT size=3>。尽管早在</FONT><FONT
face="Times New Roman" size=3>Shannon</FONT><FONT
size=3>以前，就有一些电子机械可以下比国际象棋简单的棋类，然而</FONT><FONT face="Times New Roman"
size=3>Shannon</FONT><FONT size=3>的理论却是现代电脑象棋发展的基础。</FONT>
<DT>
<DT><FONT size=3> 如今的象棋程序把棋局看成树状结构，每个局面表示成棋局树中的一个结点，每个着法代表它的一个分枝</FONT><FONT
face="Times New Roman" size=3>(</FONT><FONT size=3>一个结点和深一个结点的连接</FONT><FONT
face="Times New Roman" size=3>)</FONT><FONT
size=3>。这样，树就由双方不同层面上的所有着法组成</FONT><FONT face="Times New Roman"
size=3>(</FONT><FONT size=3>树的一个层面用“层”</FONT><FONT face="Times New Roman"
size=3>(Ply)</FONT><FONT size=3>这个术语表示，代表一方走的一步棋</FONT><FONT
face="Times New Roman" size=3>)</FONT><FONT size=3>。</FONT>
<DT><FONT size=3> 现在通常的策略是，把树由浅至深分为三个阶段，第一阶段用蛮力搜索</FONT><FONT
face="Times New Roman" size=3>(Shannon</FONT><FONT size=3>的</FONT><FONT
face="Times New Roman" size=3>A</FONT><FONT size=3>策略</FONT><FONT
face="Times New Roman" size=3>)</FONT><FONT size=3>，第二阶段用选择性搜索</FONT><FONT
face="Times New Roman" size=3>(B</FONT><FONT size=3>策略</FONT><FONT
face="Times New Roman" size=3>)</FONT><FONT size=3>，第三阶段用称为“静态搜索”</FONT><FONT
face="Times New Roman" size=3>(Quiescence Search)</FONT><FONT
size=3>的策略，来处理最后变化非常剧烈的局面，在最后一个阶段里，程序只评价吃子着法，兵升变的潜力，将军产生的后果，以及一些强制性着法。所有的程序都使用相同的算法——深度优先的</FONT><FONT
face="Times New Roman" size=3>Alpha-Beta</FONT><FONT
size=3>算法，而不同之处在于每个阶段选择什么样的深度。</FONT>
<DT><FONT
size=3> 通常搜索的深度不是固定的，而是根据当前搜索到的着法在小范围内变动，例如某个结点是将军的局面，那么它的分枝数很少，这个区域内搜索应当加深一些。策略上有非常多的选择，使得程序使用相同模型的时，他们的走棋风格和搜索速度会有显著的差别。</FONT>
<DT>
<DT><FONT face=楷体_GB2312 size=5><STRONG>二、树状搜索</STRONG></FONT>
<DT>
<DT><FONT
size=3> 人类下棋时，往往分析一小部分着法并作展开，相比选择着法而言，机器更愿意考虑得完备，所以需要发展一套逐步求精的技术。“迭代加深”</FONT><FONT
face="Times New Roman" size=3>(Iterative Deepening)</FONT><FONT
size=3>这一技术取代了固定的深度，让机器一次次做更深层的搜索</FONT><FONT face="Times New Roman"
size=3>(</FONT><FONT size=3>先是搜索</FONT><FONT face="Times New Roman"
size=3><EM>N</EM></FONT><FONT size=3>层，然后搜索</FONT><FONT face="Times New Roman"
size=3><EM>N</EM> + 1</FONT><FONT size=3>层，</FONT><FONT face="Times New Roman"
size=3><EM>N</EM> + 2</FONT><FONT size=3>层，等等</FONT><FONT
face="Times New Roman" size=3>)</FONT><FONT
size=3>，直到按计划分配的时间用完为止，这样就可以让机器在有限的时间内找出最好的着法。诸如反驳表和置换表等技术，在与迭代加深结合起来后，可以对着法重新排序，使得下一次迭代时“主要变化”</FONT><FONT
face="Times New Roman" size=3>(Principal Variation)(</FONT><FONT
size=3>上一次找到的最好着法</FONT><FONT face="Times New Roman" size=3>)</FONT><FONT
size=3>优先考虑。</FONT>
<DT><FONT
size=3> 另一个排序着法的技术就是记录一些“杀手”着法，这些着法要优先试探，杀手着法就是在搜索树的其他位置能产生截断或裁剪的着法。杀手着法通常是吃子的着法，因此可以简单地认为，吃子的着法应该在其他着法之前考虑。在很多程序中，这个技术被拓展为“历史启发表”</FONT><FONT
face="Times New Roman" size=3>(History Heuristic Table)</FONT><FONT
size=3>，通常是</FONT><FONT face="Times New Roman" size=3>64x64</FONT><FONT
size=3>的数组，每个元素存放了该着法引起裁剪的次数。</FONT>
<DT>
<DT><FONT size=3> 排序着法可以大幅度提高深度优先</FONT><FONT face="Times New Roman"
size=3>Alpha-Beta</FONT><FONT size=3>搜索的效率，此外还有三个算法也起到同样作用——</FONT><FONT
face="Times New Roman" size=3>Pearl</FONT><FONT size=3>的侦察</FONT><FONT
face="Times New Roman" size=3>(Scout)</FONT><FONT
size=3>算法以及相关的负值侦察</FONT><FONT face="Times New Roman"
size=3>(NegaScout)</FONT><FONT size=3>和主要变例搜索</FONT><FONT
face="Times New Roman" size=3>(Principal Variation Search</FONT><FONT
size=3>，简称</FONT><FONT face="Times New Roman" size=3>PVS)</FONT><FONT
size=3>方法，它们具有同一个思想：当主要变例找到时，可以先去验证其他着法是否都不如这个着法好，如果验证下来不是这样，那么它们必须重新搜索</FONT><FONT
face="Times New Roman" size=3>(</FONT><FONT
size=3>因为它们是更好的着法，必须做完全的搜索</FONT><FONT face="Times New Roman"
size=3>)</FONT><FONT size=3>。</FONT>
<DT><FONT size=3> 另一个能减少搜索量的技术称为“期望搜索”</FONT><FONT face="Times New Roman"
size=3>(Aspiration Search)</FONT><FONT size=3>，根据当前局面估计一个范围</FONT><FONT
face="Times New Roman" size=3>(</FONT><FONT size=3>通常正负半个兵</FONT><FONT
face="Times New Roman" size=3>)</FONT><FONT
size=3>，用这样一个窗口进行搜索。尽管期望搜索并不那么有效，但是用它的人还是很多的，因为它比主要变例搜索更容易理解。</FONT>
<DT>
<DT><FONT
size=3> 深层次的搜索到底能提高多少精确度，这是很难衡量的。任意局面其搜索树的大小有很大的差异，很多残局每方有约</FONT><FONT
face="Times New Roman" size=3>8</FONT><FONT
size=3>种着法，而复杂的中局里每方可能有多达</FONT><FONT face="Times New Roman"
size=3>80</FONT><FONT size=3>种着法，就现在的技术而言，一般程序在中局阶段能完全考虑</FONT><FONT
face="Times New Roman" size=3>7</FONT><FONT size=3>到</FONT><FONT
face="Times New Roman" size=3>10</FONT><FONT size=3>层的变化</FONT><FONT
face="Times New Roman" size=3>(</FONT><FONT
size=3>有个程序设计师声称选择性地搜索能达到</FONT><FONT face="Times New Roman"
size=3>40</FONT><FONT size=3>层！</FONT><FONT face="Times New Roman"
size=3>)</FONT><FONT size=3>。</FONT>
<DT><FONT size=3> “选择性延伸”</FONT><FONT face="Times New Roman"
size=3>(Selective Extension)</FONT><FONT
size=3>是对一些关键着法作更深入的探索，每个程序设计师对这些着法都有自己的界定——可以是防御杀棋的着法，或是为避免失子而作的反击。选择性延伸不能和“单步延伸”</FONT><FONT
face="Times New Roman" size=3>(Singular Extension)</FONT><FONT
size=3>混淆起来，后者是对最好的一步着法进行的更深层次的检查，来验证这个着法是否仍旧是最好的。从某种意义上说它对主要变例进行了短的延伸，是一种很花时间但很有意义的方法。</FONT>
<DT>
<DT><FONT size=3> 而用得最广泛的做法是“空着启发”</FONT><FONT face="Times New Roman"
size=3>(Null-Move Heuristic)</FONT><FONT
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -