遊戲人工智慧

在這裡,我們逐步學習一些的算法模型,逐步建立更好的智慧型系統,希望大家能夠喜歡。 首先,我們建立狀態表示模型,狀態轉化模型,智慧型評估模型。 例2:黑白棋的人工智慧。

遊戲人工智慧理論
一、人工智慧慨述
提到人工智慧,就不能不說說我非常景仰的人工智慧之父圖靈。他相信如果模擬人類大腦的思維就可以做出一台可以思考的機器,他於1950寫文章提出了著名的“圖靈測試”,測試是讓人類考官通過鍵盤向一個人和一個機器發問,這個考官不知道他現在問的是人還是機器。如果在經過一定時間的提問以後,這位人類考官不能確定誰是人誰是機器,那這個機器就有智力了。這個測試在我們想起來十分簡單,可是偉大的思想就源於這種簡單的事物之中。
然而,圖靈的測試也只說明了事物具有了智慧型的表象,何可謂智慧型的本質呢,可能當今世上誰也說不清楚。浩浩星空茫茫幻化演變,何可謂智,何可謂能,本就是空。只是以我們人類的認識和想像,無中生有罷了。所以我們談的智慧型只能局限於我們人類的認知和想像,拋開了主觀,也就只剩客觀存在而已。
也正因為我上面的觀點,在此我僅講一些簡單的實用的模型,使我們的程式具有一定的智慧型表象,但絕非智慧型的本質。希望大家能通過不斷的實踐進行學習,如果能對大家有些許幫助,就已心滿意足。
在這裡先說一句非常重要的話,如果你無法用語言描述一個事物,那么你就很難更深入的研究它。在我們電腦程式中,如何為事物建立模型是非常非常重要的,好的模型一旦建立,就已成功一半了。
在這裡,我們逐步學習一些的算法模型,逐步建立更好的智慧型系統,希望大家能夠喜歡。
二、狀態空間法
將問題轉換到對應狀態空間,然後以狀態空間的分析方法分析問題,是解決簡單問題常用的有效方法。在一個大的遊戲智慧型系統中,局部的智慧型表象模擬通常都是採用這種簡單而行之有效的方法。
例1:4個人晚上過橋,一個手電筒,最多2人同過,單獨過橋需要時間分別為10、5、2、1分鐘,2人同過,按慢的人算時間,問最少多長時間?
首先,我們建立狀態表示模型,狀態轉化模型,智慧型評估模型。
狀態表示模型即能表示任一時刻(或時段)的狀態(最好和實際狀態是一一映射方式)。狀態通常由一些狀態參數或規則表示。比如模型R :
Time:已用時間
PersonState[4]:4個人的狀態,0表示未過橋,1表示已過橋
PersonWalkTime[4]:4個人的走路時間
LightState:手電筒狀態,0表示未過橋,1表示已過橋
狀態轉化模型:由一狀態如何轉化到下一狀態。比如模型T:加最簡單限制,if(LightState==0) 可兩人過橋,否則只許一人過橋,並且所有狀態發生相應變化。採用廣度搜尋方式進行所有可能的狀態轉化。
智慧型評估模型:和智慧型表象相關的評估模型,可嵌套組合子模型。
模型E:Time越小越優。
在這個系統建立好後,我們很容易通過廣度搜尋來找到最佳過河方案。若是把相應數據輸入電腦,而電腦可以得出過橋方式,那么我們就可認為在一定程度這個系統具有了智慧型的表象(想像著我們不知道其內部如果工作)。當然模型定義的越好,系統的性能也越好。
因為上面算法使用的是廣度搜尋,為此我們可加入一些改進,使其速度更快。
改進1:我們儘量使走的慢的人過橋次數少一些,因此我們在每次返回一攜帶手電筒的人時,都選擇走的快的,這樣的話,我們的搜尋就顯的更智慧型了一些,速度也會快很多了。這種算法也就是A算法(即每次搜尋,選取最可能達到最優的情況搜尋,這裡就需要一個局部評估模組)。
改進2:我們在開始階段定義一個Time數值,若出現搜尋過程中Time已超過此數值的,其下搜尋不再進行。若出現搜尋結果小於Time的,我們更新Time,並繼續搜尋。運用這種方法,我們將省去很多無用的搜尋。這種方法稱為alpha-beta剪枝技術。
三、棋類遊戲算法
由於棋類遊戲就是一種智力遊戲,被研究的也較為深入,所以在這裡我們舉一個簡單的黑白棋的人工智慧的實現(因為黑白棋比較簡單,對初學者來說很容易上手,所以比較適宜做教材)。在這裡仍然採用了狀態空間法。
例2:黑白棋的人工智慧。黑白棋,又叫反棋、奧賽羅棋等,在西方很流行。黑白棋的棋盤是一個有8*8方格的棋盤。下棋時將棋下在空格中間,而不是像圍棋一樣下在交叉點上。開始時在棋盤正中有一白一黑四個棋子交叉放置,黑棋總是先下子。下子的方法是:把自己顏色的棋子放在棋盤的空格上,而當自己放下的棋子在橫、豎、斜八個方向內有一個自己的棋子,則被夾在中間的全部會成為自己的棋子。並且,只有在可以翻轉棋子的地方才可以下子。最後棋盤全部占滿,子多者為勝。
此主題相關圖片如下:
圖1
下面建立模型。
狀態表示模型:模型R:board[8][8],=BLACK 表示黑棋,=WHITE 表示白棋,=EMPTY 表示空,turn=1 表示電腦走棋,turn=0 表示玩家走棋,mode=0 表示電腦走黑棋。
狀態轉化模型T:即先判斷可以落棋的地方(是否為空,並且可以翻轉棋子),然後落棋後改變board[m][n],turn。
智慧型評估模型E:吃子越多越好。
這樣我們就建立了一個有低級智慧型表象的系統。為改進這個系統,我們來學習一些常用的技巧和算法。
戰略點權值表:經過多次下棋,我們就可以知道棋盤的四個角是永遠不能被吃掉的,所以這四個點是戰略要地。同樣,我們可以得出另一些重要的戰略點。我們把這些點賦一個較大的權重,這樣,我們可得到一個權重表(對應棋盤)。當然這個表可使用一些參數,並且可隨過程改變而改變,越靈活的格式(如果你能收的住)將產生越好的智慧型表象。局勢評估模組:對敵我雙方的總體或局部兵力分布得出一個較為合理的分析結果,有了這個模組,才能更好的把握戰局。
博弈樹算法:也是一種狀態搜尋算法,但每個狀態節點上都有一個評估。我們記敵我評估函式為 E(state)、M(state):
此主題相關圖片如下:
圖2
如圖在node0時候,電腦走棋有3種選擇,在每種選擇後,玩家又有三種選擇。簡單記評估值為 F(node)= M(node)-E(mode)。設 node20 評估值為F(node20) = M(node20) - E(node20)。node21 評估值為F(node21) = M(node21) - E(node21)。node22 評估值為F(node22) = M(node22) -E(node22) 。那么電腦在選擇node10後,認為玩家會選擇E(node)大而M(node)小的那個,所以電腦選擇node10的所取得的優勢應該是MIN( F(node2i) )。
所以遍歷 node10,node11,node12,電腦就可以得到其能獲得的最大優勢是MAX(MIN(F(node2i)))。當然此博弈樹可以加大樹的深度,並且可用A算法和alpha-beta算法改進。具體算法不再詳述,有興趣者可以自己研究。
四、遺傳算法
上述的幾種算法雖然可以模擬出比較好的智慧型表象,但遺憾的是沒有學習功能。而學習功能相對於智慧型生物是一個非常重要的功能。因此,我們簡單介紹一下遺傳算法,並舉一個具體的例子。
生物的進化是一個奇妙的最佳化過程,它通過選擇淘汰,突然變異,基因遺傳等規律產生適應環境變化的優良物種。遺傳算法是根據生物進化思想而啟發得出的一種全局最佳化算法。
遺傳算法簡介:對問題產生一個描述,對待解決問題進行編碼。隨機初始化群體X(0)=(x1, x2, … xn)。對當前群體X(t)中每個個體xi計算其適應度F(xi),適應度表示了該個體的性能好壞。套用選擇運算元產生優良種群goodX(t)。對goodX(t)套用遺傳運算元,產生新一代群體X(t+1)。t:=t+1;如果不滿足終止條件繼續(3)。選擇運算元:選擇運算元從群體中按某一機率成對選擇個體,某個體xi被選擇的機率Pi與其適應度值成正比。最通常的實現方法是輪盤賭模型。
例3:同樣看黑白棋,我們採用自學習的方法來模擬智慧型的實現。棋盤狀態採用 敵方=-1、空=0、我方=1。棋盤大小為64,我們對每一個格子用5*5的局部棋子來評價其戰略重要性。採用線性方式Important[node]=∑Wi*state[ i]。這樣我們就得到一個W[64][25]的表,對於每一種棋盤局勢它總能判斷出戰略重要性最大的點(姑且不論對與否)。這種編碼方式考慮了棋盤全局位置特性與局部局勢特性,大家可自行改進。
選取種群大小為30,隨機生成30個Wi[64][25]。
初始訓練階段:對每一個Wi[64][25],讓其判斷一些特定的戰略點,判斷力好的適應度大。後期訓練階段:和人對下,贏的多的適應度大。選擇適應度大的10個為產生優良種群goodX(t)。對goodX(t)套用遺傳運算元,產生新一代群體X(t+1)(30個個體)。交叉遺傳,可選取father[0-32][25]和mother的[32-64][25]產生新的個體。變異遺傳,對father[64]25]中的數值產生一些隨機變化從而生成新個體。t=t+1;如果不滿足終止條件繼續(3)。
採用這種方式,我們可以使程式自己學習,從而模擬智慧型。遺傳算法的主體就是對問題編碼,然後通過進化方式進化出優秀(相對於適應度)的種群,編碼方式由具體問題決定,進化方式影響進化範圍和速度。通過這種方式的學習,模型一般都能得到此編碼方式下的最優編碼,從而具有超越人為編碼的性能。有興趣的讀者可以自行深入研究。
五、語意網路模型
學會了以上算法,但一般只能進行小規模模型的智慧型模擬。下面我再給出一個語意網路模型,用來構建整體的模型,結合上面的算法,就可以作出漂亮的中等規模的智慧型系統。
例4:一個小型的帶時限的語意網路模型。網路由節點及連線節點的線組成,為簡單化,每個節點性質相同。節點:受到刺激後可被激活,激活後又可刺激鄰接節點。激活度由一個刺激度的函式決定。節點有門限,只有刺激度超過此門限時節點才可被激活或抑制。節點有一個受激快取,用來記錄短期內受到的刺激。有一個激活快取,用於控制激活時間段。
門限:GateT(激活)、GateN(抑制)。
受激快取:FMemory記錄受激大小,衰減度,受激時刻。
激活快取:BMemory記錄激活度大小,衰減度,激活時刻。
激活函式:Active 計算激活度,可由節點自定義。
連線節點的線:傳遞刺激並可調節刺激大小。
Wi:權值,表示相應的支持度(>0,越大表示越支持)或抑制度(D ,對應網路模型如下:
此主題相關圖片如下:
圖3
假設情景:A激活,1秒後B激活,2秒後C激活。A激活:D受激 Active(A) * W1 Gate(D),被激活,記入激活快取。這樣就可以表示短時間內事物受A、B、C事件刺激,將產生D時間。
如果 A^B->D成立, A^B^C->D不成立,D->H,A^B^C^E->D成立。
A發生,Active(A)*WaGateT(D),D激活 Active(D)*Wd>GataT(H),H激活。記入D和H的快取。
C發生,Active(C)*Wc + NowActive(FMemory)吃食。
特定獎勵節點:吃食。
隨機動作: 叫、跑、打滾。
那么當小狗肚子餓時,如果沒有食物,它可以選隨機動作,如果它選擇了跑或打滾,沒有食物。如果它選擇了叫,而剛好主人在主人就餵食,那么觸發規則1,觸發獎勵節點。此時小狗肚子餓事件和看見主人事件和叫事件處於激活狀態,這些事件節點之間的聯結將改變,以至於小狗能夠在肚子餓時候沒有食物時候看見主人時候叫。(當然這還需要改進上述系統,只要大家肯動腦,相信沒什麼大問題)。
在這裡,每個節點都是一個抽象的概念,可以由任何模型組成,也就是說它可以由任意模型嵌套組合而成,這樣就可以以最優的嵌套組合(模型本無定式,惟用而化)構成整個智慧型系統,從而模擬智慧型表象。
六、結尾
因為遊戲中智慧型模擬的重點就是建立相應的算法模型,並且想對深入研究遊戲中的人工智慧,就需要不斷實踐,所以在上面的文章中我用了幾乎全部篇幅來講解有關算法,就是希望大家能通過時間深入研究和學習。相信大家通過研究,也可建出漂亮的遊戲智慧型系統。更複雜的人工智慧系統需要建立如下幾個重要部分,環境模型、事物模型、事物與環境的互動接口、(事物與事物互動接口、環境與環境互動接口)、智慧型決策模型、智慧型評估模型,智慧型學習模型。而這裡的每一個部分都牽扯到非常廣的領域,非一時所能敘述清楚,因此就不再細述。

相關詞條

相關搜尋

熱門詞條

聯絡我們