劉英杰

（白城師范學(xué)院 計(jì)算機(jī)科學(xué)學(xué)院 吉林 白城 137000）

引言

隨著計(jì)算機(jī)技術(shù)的快速發(fā)展，對(duì)游戲軟件的設(shè)計(jì)也提出更高的要求。以人工智能技術(shù)為典型代表，是近年來(lái)游戲軟件開發(fā)應(yīng)用的主要技術(shù)之一，能夠滿足實(shí)時(shí)特性要求，為游戲玩家?guī)?lái)更豐富的體驗(yàn)[1-3]。

1 游戲樹

本文我們將討論雙人對(duì)弈，一方稱為選手，另一方稱為對(duì)手。兩人輪流走棋，局面不斷地變化。用節(jié)點(diǎn)代表局面，節(jié)點(diǎn)與節(jié)點(diǎn)之間的連線表示從一個(gè)局面到另一個(gè)局面的走步，選手處于某一局面時(shí)，他將有若干個(gè)局面供選擇，使他走到下一個(gè)局面。同理，對(duì)手處于一個(gè)局面時(shí)，也將有若干個(gè)局面供選擇，使他走到下一步。

于是，雙人對(duì)交過(guò)程就可用樹表示：

此樹停止在所謂靜態(tài)局面(Quiet Βoard)上，在靜態(tài)局面上，由靜態(tài)計(jì)分函數(shù)給出靜態(tài)值(static-value)。

顯然，靜態(tài)局面的父節(jié)點(diǎn)，如果是選手的局面，則選手必選擇有最大分?jǐn)?shù)的靜態(tài)局面做為自己下一步的走法。如果是對(duì)手的局面，則對(duì)手必選擇有最小分?jǐn)?shù)的靜態(tài)局面做為自己下一步的走法。

因此，在游戲樹上，選手是極大化者，對(duì)手是極小化者，游戲過(guò)程就是一個(gè)極大極小搜索過(guò)程。

例如，有一個(gè)選手處于如下一個(gè)局面：

顯然，選手將選擇最左邊的路走下去，這樣他就能取得最大可能的分值2。雖然最右邊的路有最大分值8，但是，如果對(duì)手不失誤的話，選手將不會(huì)拿到這個(gè)分值。

2 α-β剪枝技術(shù)

在游戲樹上，對(duì)屬于選手的節(jié)點(diǎn)，則選手對(duì)此節(jié)點(diǎn)下面的所有子節(jié)點(diǎn)，選擇有最大值的節(jié)點(diǎn)，從而確定出本節(jié)點(diǎn)的α值。

對(duì)屬于對(duì)手的節(jié)點(diǎn)，則對(duì)手對(duì)此節(jié)點(diǎn)下面的所有子節(jié)點(diǎn)，選擇有最小值的節(jié)點(diǎn)，從而確定出本節(jié)點(diǎn)的β值。

選手(或?qū)κ?在某節(jié)點(diǎn)處，確定該節(jié)點(diǎn)的α值(或β值)時(shí)，是從該節(jié)點(diǎn)下面所有子節(jié)點(diǎn)中，從左到右逐次取max(或取min)而做到的。

亦即，設(shè)選手在節(jié)點(diǎn)N處，有m個(gè)子節(jié)點(diǎn)，從左到右排列為N1，…，Nm。設(shè)Ni處的β值為βi(i＝1，…，m)，于是，確定N處α值的過(guò)程如下：

(1)N處α值，暫定為β1

(2)看β2

若β2≤α，則α值仍暫定為β1；

若β2＞α，則α值暫定為β2。

看β3，

若β3≤α，則α值仍不變；

若β3:＞α，則α值暫定為β3。

……

看βm，

若βm≤α，則α值就確定為上面得到的α值;

若βm＞α，則α值就確定為βm。

同理，某節(jié)點(diǎn)處的β值的確定過(guò)程同上。

但是，選手在N處通過(guò)逐次取“最大”確定α值時(shí)，每得到一個(gè)暫時(shí)的α’，如果α’≥β(其中β是N的父節(jié)點(diǎn)由對(duì)手確定的β值)，則N處確定為α’的子節(jié)點(diǎn)右邊所有的子節(jié)點(diǎn)，都不再有繼續(xù)考慮的必要，可以剪去，這稱為β剪枝。

同理，對(duì)手在某節(jié)點(diǎn)處確定β值時(shí)，也要不斷地和其父節(jié)點(diǎn)所確定的值比較，以確定是否α剪枝。

我們將把這一技術(shù)，運(yùn)用于我們下面的設(shè)計(jì)中。

3 博奕函數(shù)的LISP程序設(shè)計(jì)

學(xué)習(xí)是人類和某些高級(jí)動(dòng)物所具有的重要智能行為。學(xué)習(xí)使人們能夠不斷地吸收新的知識(shí)，總結(jié)自己的經(jīng)驗(yàn)，改正錯(cuò)誤，提高自己解決問(wèn)題的能力。使計(jì)算機(jī)系統(tǒng)具有學(xué)習(xí)能力是機(jī)器學(xué)習(xí)的重要目的之一。1956年Samuel研制的跳棋程序首次使計(jì)算機(jī)具備了學(xué)習(xí)能力，這個(gè)程序可以在與對(duì)手不斷的對(duì)奕中總結(jié)經(jīng)驗(yàn)，提高自己的技能。1959年這個(gè)程序戰(zhàn)勝了設(shè)計(jì)者本人，1962年這個(gè)程序戰(zhàn)勝了美國(guó)一個(gè)州的冠軍。機(jī)器學(xué)習(xí)的另外一個(gè)著名系統(tǒng)是Langley的發(fā)現(xiàn)系統(tǒng) BACON，這能根據(jù)現(xiàn)有的數(shù)據(jù)，用83條產(chǎn)生規(guī)則重新發(fā)現(xiàn)許多著名的物理定律，如理想氣體定律、行星運(yùn)動(dòng)定律及歐姆定律，等等[4-5]。

4 結(jié)論

本文利用LISP程序設(shè)計(jì)闡述了人機(jī)對(duì)弈的過(guò)程，人工智能領(lǐng)域看似簡(jiǎn)單，但實(shí)際上是一個(gè)十分困難的課題。這也許是本世紀(jì)人類所從事的各種科學(xué)研究中，最富有挑戰(zhàn)性與創(chuàng)造性的一個(gè)領(lǐng)域。人工智能的發(fā)展已經(jīng)走過(guò)了六十多年的歷程，人工智能取得了舉世矚目的發(fā)展?，F(xiàn)在，人工智能技術(shù)已被譽(yù)為當(dāng)代三大尖端技術(shù)之一，但仍有許多問(wèn)題等待我們?nèi)ヌ剿鳌?/p>