|
|
|
Welcome to my blog!
| 电脑围棋中的人工智能技术(二) |
1. 博弈与计算科学
现在的世界上有各种各样电脑棋手。能够在普通计算机上运行的国际象棋程序已经达到了职业棋手的水平，就黑白棋而言，人类已经不是计算机的对手。但是就围棋而言，计算机与人进行抗衡的路还很遥远。
如果电脑棋手战胜了人类棋手，那么是否就可以说它和人一样具有智能？这个问题，将放到最后进行讨论。我首先将向大家展示，电脑棋手是如何下棋的。
2. 择优而行
电脑棋手下棋的原理，简单地说，就是选出它所认为最有利的下法。
|.....A
|.../ | \
|...B C D
|...4 3 -1
我们来看上面这个图。假设在某一个时刻，摆在电脑棋手面前的是一个局面A。当然，电脑棋手懂下棋的规则，于是它发现一共有三种符合规则的下法（为了画图方便，所以少了一些，事实上，在国际象棋和中国象棋中，符合规则的下法一般为数十种，围棋则多达两三百种）。这三种下法将分别形成局面B、C、D。现在，我们假设电脑棋手能够判断局面的优劣，为每一个局面都计算一个分数，比如局面B的得分为4，局面C的得分为3，局面D的得分为-1。当然，我们可以作一些规定：分数越高局面越好，分数越低局面越差；当分数为0时表示双方均势，则正分表示电脑棋手方优势，负分表示电脑棋手处于劣势。于是，电脑棋手就选择对它最有利的下法，即第一种下法，最后形成了局面B。此时，在这种情况下，作为一个副产品，那就是局面A被认为是4分，因为后面两种下法对计算机而言是没有意义的，所以B的分数也就是A的分数。
接下来的问题是计算机如何做到为每一个局面评出一个得分。这在下棋中被称为形势判断。
现在以中国象棋或国际象棋为例（这个问题对围棋而言是很复杂的），最简单的形势判断就是评价以下棋局中双方的子力对比。例如，在中国象棋中，每个车记8分，每个马或炮记3.5分，每个兵、士、相都记1分，将帅无价，姑且记1000分，那么很容易就可以计算出双方的兵力，两者的差就形成了一种最简单的形势判断。当然，这种形势判断是十分粗糙的。
稍稍复杂一些的形势判断，除了考虑子力优势之外，还要考虑局面优势。比如一方的马处于十分积极的盘河位置，而另一方的马则还留在原位没有跳出，两者之间显然存在着差距。这时，需要将这些差距折算成分数，加到形势判断中去。在计算机中，这是最通俗、或者说最常用的形势判断方法。
一般说，对局面的形势判断可以用一个数学式子计算得出。举一个简单的例子：
设在形势中一共考虑n个因素（或特征）。用xi表示第i个因素是否在当前的局面G中出现，如果出现则取1，没有出现则取0，比如第6个因素是指一方的第1个车，那么当这个车还存在时，x6=1，这个车不存在时，x6=0。用wi表示第i个因素在形势判断中所计算的分数，这被称为权重，例如一个车的分数为8，则w6=8。那么对局面G的形势判断为：
| f(G)=W1*X1+W2*X2+...Wi*Xi=S(i=1 to i)WiXi
符号S被称为累加符，如果读者以前不知道这个符号，只要看着上面的等式，将它想像为在for循环中套了一个加法的命令，就很容易理解了。这是为了书写方便而引入的符号。
3. 搜索的魔术
如果形势判断十分准确，故事就简单地结束了。可惜的是，问题没有这么简单。我们（无论是计算机还是人类）永远不可能得到一个准确的形势判断。这是因为，形势判断是静态的，而棋局是动态的，要从静态的特征中获取动态的信息，这并非易事。当然，如果需要做到万无一失，那么在形势判断中，必须包括所有可以想到的对局面产生影响的因素，但这时，因素的数量是一个天文数字，我们既不可能对所有的因素都赋一个权重，也不可能在有限的时间内计算出局面的形势判断。
我们回过来看，人在下棋时也不能一眼就对静态的局势作出准确的判断，笼统地说，他们往往需要向后面计算几步，看看在走了几步棋之后，局面的形势如何。这被称为“多算胜”，也就是说，谁看得越深远，谁就可以获胜。这个思维方式立刻被用到了计算机上。
3.1 最小最大树
以第2部分中出现过的图为例，假设向后再多考虑一步，得到下图
|...........A
|........./ | \
|........B C D
|......./ | / \ | \
|.......E F G H I J
|.......5 3 2.5 2 -2 10
这是一棵树。从图中看到，假设在三个局面B、C、D下，都恰好有两种符合规则的下法，可以形成局面E、F、G、H、I、J，而这些局面的形势判断已经得到了。电脑棋手的任务是利用这些已知条件，选择局面B、C、D的中对它最有利的一个局面。我们可以发现，局面J的得分最大，那么是不是应该选择局面D，以便形成对电脑棋手最有利的局面J呢？
假设电脑棋手的对手（可能是人，也可能是一个计算机程序，现在为了便于说明问题时不产生混淆，假设对手是人）面对的是局面B，那么他一定会选择对自己最有利的下法。由于是零和博弈，对人最有利的下法就是计算机最不利的下法，那么在E和F之中，他会选择F。这时，如果电脑棋手选择局面B，那么对方就会选择F，最后电脑棋手得到的结果是3，也就是说，B的形势判断结果应该为3。同样道理，如果人处于C中，他会选择H，于是f(C) = f(H) = 2。同理，f(D) = -2。最后，发现是B的得分最高，因此电脑会选择B，此时f(A) = f(B) = 3。
按前面的猜测，如果因为f(J)=10而计算机选择了局面D，那么对手就会选择I，最后计算机得到了最差的结果-2。
从这里我们可以看出，在电脑棋手下棋的局面中，它总是选择下一个层次中由该局面衍生出的局面中得分最高的，而在对手下棋的局面中，它总是选择下一个层次中由该局面衍生出的局面中得分最低的。用数据结构中的术语，假设对于某一个局面，已经将在几步棋之后的所有可能形成的局面的得分都计算了出来，那么从这棵树的最底层一层层向上推，在对手下棋的层次中，每一个结点取其子结点的最小值，在电脑下棋的层次中，每一个结点取子结点的最大值。这就被称为最小最大树。
最后，问题转化为对某一局面下衍生出的最小最大树的遍历。这种遍历用一个深度优先搜索就很可以处理了。在搜索的过程中，当前路径上的每一个结点上都保存着搜索到目前为止的当前最优值。搜索用一个递归函数实现，该函数的功能是计算某个结点的最优值。每当一个结点得到子结点的返回值时，就从当前最优值和返回值中选取一个更优的值作为当前最优值。当一个结点的子结点都搜索完毕之时，其当前最优值就是该结点的实际最优值，也就是这个结点的得分，这时，将这个值返回其父结点。下面给出最大最小搜索的伪码：
…………………………………………
需要注意的是，在搜索过程中，我们不仅仅关心每个局面的得分是多少，我们同样关心是如何得到这个得分的，也就是说，在这个局面下，电脑棋手或是对手应选择什么下法，才能得到这个得分。这个功能没有包括在上面的伪码中。不过只要读者理解了上面的伪码，就一定能够自己将相应的代码加进去。
进一步，由于是零和博弈，假设从对手角度考虑形式判断函数为g，则有g = -f。这样，在深度优先搜索中，电脑下棋的结点时考虑取子结点中f最大的，而对手下棋的结点中取f最小的，也就是g最大的，这样两者就完全统一成取最大值。而在返回值时，只需要把符号改变一下，就可以把f和g值相互转换了。例如在前面的例子中，当位于对手下棋的局面B时，有g(E)= -f(E)= -5，g(F)= -f(F)= -3，g(B)取最大值，则g(B)= -3，随后返回到电脑下棋的局面A时，改变符号，使用f(B)= -g(B)= 3，在A点取f的最大值。这被称为负最大搜索，它比最小最大搜索来得简单。下面给出负最大搜索的伪码，相信有一定基础的读者看了之后就会明白。
……………………………………………………..
3.2 a-b裁剪(alphabeta裁剪)
新的问题又出现了，假设我们考虑的是中国象棋或国际象棋，现在希望每次都可以搜索到5个回合之后。5个回合就相当于双方一共下10步棋，每一次都有几十种下法可以选择，姑且算每次有30种选择，于是最小最大树的叶结点个数总共多达30^10，这是一个非常庞大的数字。搜索的结点越多就相当于在搜索中花费的时间更多，我们总不能忍受电脑棋手一年才下一步棋。减少搜索结点的最简单的方法是减小搜索深度，但这大大影响了电脑棋手的棋力。是否有办法在不减小搜索深度的前提下将需要搜索的结点减小一些？
|......A 3
|......|
|......B 2
|..../ | \
|....C D E
|....4 ? ?
假设上图是在深度优先搜索过程中的一个局部，用fnow表示搜索到当前状态结点的当前最优值。B是电脑下棋的结点，A和C则是对手下棋的结点，当前正处于结点C所属的子树已经搜索完毕，从结点C返回至结点B的时刻，方框中的结点表示搜索到目前为止的当前最优值，即fnow(A)=3，fnow(B)=2，fnow(C)=f(C)=4。我们知道，由于B是电脑下棋的结点，因此当f(C)>fnow(B)时，应当更新结点B的当前最优值，即令fnow (B)=f (C)=4。此时，虽然结点E、F尚未搜索，但由于结点B处为电脑下棋，应取子结点中最大值，其当前最优值随着搜索的进行只会增加而不会减小，因此有f(B)>=fnow(B)=4。而结点A是对手下棋，应取子结点的最小值，而f(B)>=4>3=fnow(A)，其当前值必然小于结点B的实际最优值，因此对手处于结点A时必然不会选择到结点B的下法，也就是说，结点B不会对结点A的最优值产生影响。因此，不必再进行结点E和结点F的搜索，结点B就可以直接返回其父结点A。
在搜索过程中，电脑下棋结点的当前最优值被称为a值（即前面的例子中局面B的最大值），对手下棋结点的当前最优值被称为b值（即例子中A的最小值）。在搜索过程中，a值递增，b值递减，两者构成了一个区间。这个区间被称为窗口，而对手下棋的结点最终的最优值将落在这个窗口中。一旦在电脑下棋的结点得到其子结点的返回值大于b值，则发生剪枝。
同样，a-b裁剪也有简洁的负最大的版本，这时对手的a值即负的电脑的b值，对手的a值即负的电脑的b值。a-b裁剪的伪码如下：
…………………………………………………….
3.3 NegaScout搜索
正常情况下，在搜索树的根结点，也就是电脑棋手需要决策的局面，我们可以调用3.2中给出的函数alphabeta来得到根结点的分值，同时也可以得到应该走哪一步棋的结论。这时，调用该函数时，我们应使参数alpha=-1000，beta=1000，这里1000是一个足够大的数。这是因为在根结点时，我们需要把窗口初始化成最大，在搜索过程中，随着信息的获得，这个窗口会渐渐地减小，最后收敛到根结点的最优值上。
现在我们来看一个有趣的现象：如果我们调用alphabeta( d, b – 0.1, b, p )会产生什么结果？这里0.1是一个较小的常数，而b是某一个数值。
直接从程序中分析，现在形式参数beta就等于b。如果函数的返回值大于b（也就是beta），说明对于局面p，至少有一个子结点的返回值比b大，所以其最优值必然大于b。这时，我们知道b是局面p最优值的下界。注意，在这种情况下，后面也许还有子结点根本来不及搜索就被裁剪了，所以这时的返回值并不代表局面p的实际最优值，可能比实际最优值小。如果函数的返回值小于b，说明没有一个子结点的最优值比b大，于是局面p的最优值必然小于b（事实行，由于初始的窗口在函数递归过程中被反复传递下去，所有的返回值都只体现了是否比b大的信息，所以返回值不是局面p的实际最优值）。此时，b是局面p最优值的上界。于是，我们得到结论，运用这种类型的alphabeta函数调用，根据返回值是否比b大，可以得出局面p的最优值是否比b大的结论。
注意到在函数调用过程中，alpha和beta很接近，因此窗口很小，在窗口很小的情况下，搜索树的各个层次中，得到的返回值比beta大的可能性就大大增加了，这样剪枝的可能性也变大了。
这种类型的alphabeta函数调用被称为零窗口a-b搜索，由于产生了大量的剪枝，它的时间消耗比正规的a-b裁剪少。但正规的a-b裁剪可以得到一个局面的实际最优值，而零窗口a-b调用只能得到实际最优值和某一个特定值b比大小的结果，也就是说，一个上界或下界的信息。
于是，我们可以对a-b裁剪作一个改进：在每次向下搜索之前，首先先用零窗口a-b调用判断一下，这个搜索是否能够改善当前的最优值，即局面p某一个子结点的实际最优值是否比alpha大。如果比alpha小，则跳过这个子结点。进一步，当该子结点的返回值大于alpha时，从前面的分析中已经知道，它的实际最优值大于这个值，所以当返回值大于beta时，其实际最优值也超过了beta，这时就应该进行剪枝。这就是NegaScout搜索。在这个新算法中，增加的时间消耗是零窗口a-b调用，而如果零窗口a-b调用的返回值比alpha小，那么就可以节约一个较大窗口的a-b调用花费的时间，当零窗口a-b调用的返回值比beta大时，则直接产生了进一步的剪枝。实践证明，由于零窗口a-b裁剪中产生了大量的剪枝，所以其实践消耗相对于大窗口a-b调用而言是很小的。总的说，NegaScout搜索较a-b裁剪有效。下面依照前述的思想，给出一个不算太规范的NegaScout算法的伪码（这里也使用了负最大搜索）：
…………………………………………………..
关于NegaScout的细节及其进一步的优化，读者可以查阅文献[1]。
3.4 魔术所在
按理说，搜索技术发展到这个地步，似乎已经很完善了。而事实上，这只是一个开始而已。
首先出现的是一些改进的技术。例如，在前面讨论的各种搜索中，除了保存当前的搜索路径（搜索树的一个分支）的堆栈之外，不需要其它的内存消耗。这种做法并没有充分利用资源。在实际的计算机博弈程序中，需要建立散列，用以保存在以前的搜索过程中所遇到的局面。这样，一旦在搜索过程中再次遇到相同的局面（这很常见，如几种不同的行棋次序可能导致相同的局面），就可以利用以前计算的结果。关于这方面的细节，有兴趣的读者可以参阅文献[2]。
然而，真正的革命在于搜索算法全新的变化。
MTD(f)（全称是Memory-enhanced Test Driver）就是其中一个相当优秀的新方法。它的思想非常简单：既然零窗口的a-b调用可以判断局面的最优值是否大于或小于一个固定的值，那么就反复运用这个调用。假设已知局面的最优值f的范围是min <= f <= max（例如在最初，min=-1000，max=1000），那么就在这个范围选一个值g，然后用这个值进行零窗口a-b调用。如果调用结果比g大，那么说明g是f的下界，就得到min=g，反之max=g，这样，范围就缩小了。以上过程反复进行，直到上下界收敛到相同的一个值为止。
MTD(f)算法中，虽然也利用了a-b裁剪，但其仅仅作为一个辅助工具出现。其思想却非常有趣，完全跳出了前面的思维，以全新的方式出现在了我们的面前。
如果在搜索过程中能够使用散列保存已经搜索过的局面的特性，那么这个算法的效率将优于NegaScout。关于MTD(f)的细节，请有兴趣的读者查阅文献[3]。在此，我只简单地给出算法的伪码：
……………………………………………………………….
需要注意的是，既然算法的名称中有Memory-enhanced，在这里使用的a-b裁剪应使用散列保存以前的搜索结果（这里使用了函数alphabetawithmemory，以区分于原先的不使用散列的a-b裁剪）。在MTD(f)中，被重复搜索的相同局面大大增加，当以前的结果被保留下来时，才可能提高效率。在国际象棋的实验中，该算法使效率提高了15%。
此外，还有其它的一些搜索算法，如SSS*[4]、B*[5]、Probcut[6]，这些算法和我们讨论的算法多少有些不同（或在局面的评价上、或在剪枝上、或在搜索的次序上），在这里就不再论述，有兴趣的读者可以自行参阅文献，进行研究。
4. 电脑棋手的学习
机器学习技术的发展为电脑下棋水平的提高带来了新的希望。各种各样的学习技术都被试图应用于博弈的某一个部分。文献[7]综述了机器学习在计算机象棋对弈中的应用。
在此，我将展示一个典型的方案：对形势判断函数进行学习。
4.1 监督学习
回顾一下第2部分中的内容，一个一般的形势判断函数（或称估价函数）具有如下的形式：
| f(G)=W1*X1+W2*X2+...+WiXi=S(i=0 to n)WiXi
|
其中，xi表示局面的某一个因素（或特征），而wi是这个特征在形势判断中所起的重要程度（即相应的分值），通常被称为权重。如果当这个因素是子力时，在中国象棋或国际象棋中，还是比较容易给出一个相对准确的值，而当这个因素是某些局面性的优势时，如何准确地估价这些优势，可能令有经验的大师都会感到烦恼。
虽然大师们很难对于一个孤立的局面因素给出具有普遍性的估计，例如在中国象棋中，一个处于巡河位置的车具有多大的分值，但对于一些特定的局面，大师们还是可以较为准确地给出综合评价。这为学习形势判断函数提供了可能。
一个很简单的方法就是找出许多局面，然后请大师为每一个局面作出自己的形势判断。然后把大师们给出的形势判断作为标准答案，训练形势判断函数。这种学习方式被称为监督学习（或称有师学习），因为这种学习就如在老师的监督指导下进行。
例如现在有k个局面G1, G2, …, Gk。第j个局面Gj的n个特征用X1j,X2j,...,Xnj表示。对这k个局面，大师给出的形势判断为h1, h2, …, hk。现在的任务是找出合适的权重w1, w2, …, wn，使得以下的方程组尽可能地得到满足：
| j=1 W1X1j+W2X2j+...+WnXnj=h1
| j=2 W1X1j+W2X2j+...+WnXnj=h2
| j= ... M
| j=k W1X1j+W2X2j+...+WnXnj=hk
注意，之所以说是尽可能得到满足，是因为以上关于w1, w2, …, wn的方程组不一定有解，我们所希望的是实际形势判断结果f1, f2, …, fk与大师给出的结果h1, h2, …, hk尽可能接近。
当形势判断函数非常复杂时，这个问题实际上是一个优化问题。解决这个问题的通用方法是梯度下降法（有兴趣的读者可以参阅有关最优化的书籍）。由于现在的形势判断函数非常简单，也可以应用许多其它方法（如最小二乘）。下面仅仅给出梯度下降方法在这个简单的实际问题上的应用。
首先对所有的权重w1, w2, …, wn赋以随机的数值。然后反复进行以下的迭代：在时刻t，对局面G1, G2, …, Gk计算形势判断结果f1, f2, …, fk，依照下式得到下一时刻（即t +1时刻）的权重为
| wi(t+1)=wi(t)+H*S(j=1 to k)(hj-fj)*xij
以上对权重的更新过程反复进行，直到形势判断的结果不能再改善为止。式子中的H被称为学习速率，当取值较大时，学习速度较快（即需要迭代的次数变少），但学习的精度较低（准确地说，在最后阶段会产生振荡），当取值较小时精度提高，但学习速度变慢。
如果哪位读者对人工神经网络有一定的了解，也可以将以上的过程看作是一个连续型感知器的学习过程。
4.2 强化学习
监督学习并不是一个令人满意的学习方法（虽然在某些情况下是不可替代的）。毕竟，当这样的“老师”也是很累的，很难想像去请一个大师对数百个甚至数千个局面给出自己的形势判断。
强化学习是监督学习的一个特例。这时，“老师”不再每次都给出准确的答案，他（她、它）只是对电脑的计算结果给出一个好或不好的评价，或者是告诉电脑究竟好到何种程度，作为一个带有模糊性的判断。在下棋中，这种“老师”是随处可得的。电脑棋手和每一个对手的对局都有可能成为这种“老师”，对局的胜负就可以看作是“老师”对电脑棋手的评价。当然，如何有效地利用这种评价是学习技术的关键。
以中国象棋或国际象棋为例，在一局棋的进行过程中，一个形势判断函数的结果往往时好时差。这是因为在形势判断函数中的权重w1, w2, …, wn中，有些比较准确（比如子力因素的权重），而其它的一些并不准确（如一些表示局面优势因素的权重）。在棋局的进行中，经常出现的状况是一方首先取得了局面优势，随后转化成了子力的优势，最后取胜，或者更一般地说，一方首先取得了一些潜在的优势，随后将这些潜在的优势转化为实在的优势。一般地说，电脑棋手对潜在的优势往往不能给出准确的判断，而对较为实在的优势（例如子力优势或者直接构成的杀局）则判断正确。于是我们可以得到一个基本准确的结论，电脑棋手在其对局的后期（更特殊的状况是对局结束的时刻），得到的形势判断往往是比较正确的。同时，我们可以设想，在对局的前面的一些时刻，正确的形势判断应该和对局后期的形势判断较为接近。如果计算机能够有效地参考对局后期正确的形势判断，就有可能自行给出对局前期的一些局面的相对准确的形势判断，作为在前一节所提到的监督训练中的标准答案h1, h2, …, hk。
TD( )就是一个实用的强化学习技术。TD（Temporal Difference）即瞬时差异，就是指在一个对局中相邻两个时刻的局面的形势判断之差。如果这个形势判断函数比较准确，则这个差（即瞬时差异）应该接近于0。假设G1, G2, …, Gk, Gk+1是在一个对局中，从某一时刻到对局结束的连续的k+1个局面。这时根据前面的假设，在对局结束时的形势判断是准确的，即对于第k+1个局面，形势判断的标准答案hk+1=f(Gk+1)。现在我们利用这个值来形成前k个局面的形势判断标准答案：从对局结束开始，向前一步步倒退，在每一个时刻，其形势判断标准答案为
|.......h =(1-y)f(G )+y*k
|........i i+1 i+1
从这个式子中可以看到，当y=0时，第i个局面的形势判断标准答案应该接近于在此之后的局面的形势判断；当y=1时，所有局面的形势判断标准答案都接近于hk+1，即对局结束时刻的形势判断。于是，当y取介于0和1之间的某一个数值时，形势判断的标准答案将成为以上两者的折中。经过了学习之后的形势判断函数将在对局中的一系列连续的局面中，相邻局面的判断结果相似，并逐渐逼近终局时的结果。
TD( )被应用于多个计算机博弈程序之中。在文献[8]中，一个应用了该技术（稍作了一些改变，有兴趣的读者请自行查阅文献）的国际象棋程序在国际互联网上进行了300多局对局后，其等级分从1650分（一般水平）上涨到了2110分（美国大师水平）。 |
| [ 阅读全文 | 回复(0) | 引用通告 | 编辑 ] |
Post by 杨威利 发表于 2008-3-24 4:33:00
|
|
 | |
