黑白文档.docVIP

基础 首先感谢那些在我研究程序算法时给我帮助的人，如Zebra的作者Gunnar Andersson，微软亚洲研究院的李聪，台湾大学的许舜钦教授等。正是由于站在了无数前辈们多年研究成果的肩膀上，电脑人工智能才得以一步步的成长。我编辑这篇文章的目的在于，希望使更多的人了解人工智能的基本原理，激起大家的兴趣，能有更多有志者研究它，并推动人工智能的发展。这篇文章中部分引用了Gunnar Andersson/李聪/许舜钦教授的文章，在此表示感谢。 黑白棋程序设计是用编程的方法教会电脑下黑白棋，使之可以与对手对抗，一较棋力高下。由于黑白棋的算法设计在各种棋类游戏中是比较简单的，所以编程相对要容易，而棋力则可以达到非常的强，一般都可以击败它的设计者。黑白棋程序Logistello已于1997年大比分击败世界冠军Takeshi Murakami。现在，人类玩者几乎不可能击败强力的黑白棋程序，如Hannibal、Logistello、Wzebra、Keyano等。看来，要想击败他们，只有依靠自己的程序了。：) 我的程序的源代码可以在相关程序中下载。　 那么，怎样设计黑白棋程序呢？以下将以Pascal语言为例加以说明。 Java Applet is not Supported by your Browser 现在有如图示的这样一个棋局，轮到电脑下棋。现在它发现有这样三个地方可以下：e3,c3,c5。这三种下法分别会形成三种局面：A、B、C。如果是人在下棋，就会思考：那一种下法更好呢？比如A被别人占角，B没什么变化，C占了别人的角。当然棋手会选择下C。电脑也是如此，它会对每一种棋局评一个分，比如它判断，如果被别人占角，就减80分，相反占别人的角就加80分。那么A=-80分,B=0分,C=80分。电脑会选择下C。电脑程序对棋局评分的部分，称为“估值函数”(Evaluation Function)。真正的估值函数当然不会这么简单。它会用到技巧篇提到的如行动力、潜在行动力、余裕手、边角判断、稳定子等综合因素来判断。具体的估值函数，我会在“估值函数”一节中详细讲述。 初始棋局(-1) ------------------+------------------ | | | e3 c3 c5 (A) (B) (C) 接下来，如果人就这么判断。那么它顶多也就是个初学者。为什么呢？因为它不会推理，碰到对手弃角之类的战术，如“边角判断”中示例的一些情况，就输得一塌糊涂了。当然，可以告诉电脑，碰到“边角判断”中的几种情况，就如何如何下。但是，真实的棋局是非常复杂的，电脑（也包括人脑）几乎不可能对动态的棋局给出静态的评估。因为实际对局总会出现这样那样的情况，是无法预先估计的。碰到这些情况，人就会向后推几步，看一看会是怎样的一个局面。一些棋类大师往往可以推十几步甚至更深。电脑也是如此。 还是刚才那一幅图的演化。 电脑下棋 对手下棋 初始棋局 ------------------+------------------ | | | e3 c3 c5 -----+----- ----+---- -----+----- | | | | | | | | | | | | | | f2 f3 f4 f5 f6 c2 d3 e6 f5 b6 c6 d6 e6 f6 +84+36+12 +5 -1 +11 -1 +6 +6 +6 +0 -5 +3 +5 电脑在自己下棋以后，把对手的下棋情况也推理出来。然后加以评分。（最下一排是电脑评估的得分）这一次电脑又如何下呢？这时电脑假设对手是高手。如果电脑下e3，对手就会下对电脑最不利的情况f6。同样，电脑下c3，对手就会下d3，电脑下c5，对手就会下d6。这三种情况，c5是最不好的(因为c5的下一步d6的得分最低)，c3与e3一样。因此电脑会下c3或者e3。用程序化的语言这样描述： 电脑从棋盘初始状态出发，以后双方轮流下子，形成一种倒树状结构。树的层数就是电脑有哪些信誉好的足球投注网站的深度。在树状结构的叶子节点，对棋盘状态进行估值，即估计形式的好坏。得出一个分值。将此分值赋给叶子节点，之后，如果父节点该电脑下棋，则将子节点的最大节点值赋给其父，如果父节点