通过有趣人工智能程序来认识游戏世界

刘英杰

（白城师范学院 计算机科学学院 吉林 白城 137000）

引言

随着计算机技术的快速发展，对游戏软件的设计也提出更高的要求。以人工智能技术为典型代表，是近年来游戏软件开发应用的主要技术之一，能够满足实时特性要求，为游戏玩家带来更丰富的体验[1-3]。

1 游戏树

本文我们将讨论双人对弈，一方称为选手，另一方称为对手。两人轮流走棋，局面不断地变化。用节点代表局面，节点与节点之间的连线表示从一个局面到另一个局面的走步，选手处于某一局面时，他将有若干个局面供选择，使他走到下一个局面。同理，对手处于一个局面时，也将有若干个局面供选择，使他走到下一步。

于是，双人对交过程就可用树表示：

此树停止在所谓静态局面(Quiet Βoard)上，在静态局面上，由静态计分函数给出静态值(static-value)。

显然，静态局面的父节点，如果是选手的局面，则选手必选择有最大分数的静态局面做为自己下一步的走法。如果是对手的局面，则对手必选择有最小分数的静态局面做为自己下一步的走法。

因此，在游戏树上，选手是极大化者，对手是极小化者，游戏过程就是一个极大极小搜索过程。

例如，有一个选手处于如下一个局面：

显然，选手将选择最左边的路走下去，这样他就能取得最大可能的分值2。虽然最右边的路有最大分值8，但是，如果对手不失误的话，选手将不会拿到这个分值。

2 α-β剪枝技术

在游戏树上，对属于选手的节点，则选手对此节点下面的所有子节点，选择有最大值的节点，从而确定出本节点的α值。

对属于对手的节点，则对手对此节点下面的所有子节点，选择有最小值的节点，从而确定出本节点的β值。

选手(或对手)在某节点处，确定该节点的α值(或β值)时，是从该节点下面所有子节点中，从左到右逐次取max(或取min)而做到的。

亦即，设选手在节点N处，有m个子节点，从左到右排列为N1，…，Nm。设Ni处的β值为βi(i＝1，…，m)，于是，确定N处α值的过程如下：

(1)N处α值，暂定为β1

(2)看β2

若β2≤α，则α值仍暂定为β1；

若β2＞α，则α值暂定为β2。

看β3，

若β3≤α，则α值仍不变；

若β3:＞α，则α值暂定为β3。

……

看βm，

若βm≤α，则α值就确定为上面得到的α值;

若βm＞α，则α值就确定为βm。

同理，某节点处的β值的确定过程同上。

但是，选手在N处通过逐次取“最大”确定α值时，每得到一个暂时的α’，如果α’≥β(其中β是N的父节点由对手确定的β值)，则N处确定为α’的子节点右边所有的子节点，都不再有继续考虑的必要，可以剪去，这称为β剪枝。

同理，对手在某节点处确定β值时，也要不断地和其父节点所确定的值比较，以确定是否α剪枝。

我们将把这一技术，运用于我们下面的设计中。

3 博奕函数的LISP程序设计

学习是人类和某些高级动物所具有的重要智能行为。学习使人们能够不断地吸收新的知识，总结自己的经验，改正错误，提高自己解决问题的能力。使计算机系统具有学习能力是机器学习的重要目的之一。1956年Samuel研制的跳棋程序首次使计算机具备了学习能力，这个程序可以在与对手不断的对奕中总结经验，提高自己的技能。1959年这个程序战胜了设计者本人，1962年这个程序战胜了美国一个州的冠军。机器学习的另外一个著名系统是Langley的发现系统 BACON，这能根据现有的数据，用83条产生规则重新发现许多著名的物理定律，如理想气体定律、行星运动定律及欧姆定律，等等[4-5]。

4 结论

本文利用LISP程序设计阐述了人机对弈的过程，人工智能领域看似简单，但实际上是一个十分困难的课题。这也许是本世纪人类所从事的各种科学研究中，最富有挑战性与创造性的一个领域。人工智能的发展已经走过了六十多年的历程，人工智能取得了举世瞩目的发展。现在，人工智能技术已被誉为当代三大尖端技术之一，但仍有许多问题等待我们去探索。