通過有趣人工智能程序來認識游戲世界

劉英杰

（白城師范學院 計算機科學學院 吉林 白城 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程序設計闡述了人機對弈的過程，人工智能領域看似簡單，但實際上是一個十分困難的課題。這也許是本世紀人類所從事的各種科學研究中，最富有挑戰性與創造性的一個領域。人工智能的發展已經走過了六十多年的歷程，人工智能取得了舉世矚目的發展。現在，人工智能技術已被譽為當代三大尖端技術之一，但仍有許多問題等待我們去探索。