遊戲人工智慧

在這裡，我們逐步學習一些的算法模型，逐步建立更好的智慧型系統，希望大家能夠喜歡。 首先，我們建立狀態表示模型，狀態轉化模型，智慧型評估模型。 例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，觸發獎勵節點。此時小狗肚子餓事件和看見主人事件和叫事件處於激活狀態，這些事件節點之間的聯結將改變，以至於小狗能夠在肚子餓時候沒有食物時候看見主人時候叫。（當然這還需要改進上述系統，只要大家肯動腦，相信沒什麼大問題）。
在這裡，每個節點都是一個抽象的概念，可以由任何模型組成，也就是說它可以由任意模型嵌套組合而成，這樣就可以以最優的嵌套組合（模型本無定式，惟用而化）構成整個智慧型系統，從而模擬智慧型表象。
六、結尾
因為遊戲中智慧型模擬的重點就是建立相應的算法模型，並且想對深入研究遊戲中的人工智慧，就需要不斷實踐，所以在上面的文章中我用了幾乎全部篇幅來講解有關算法，就是希望大家能通過時間深入研究和學習。相信大家通過研究，也可建出漂亮的遊戲智慧型系統。更複雜的人工智慧系統需要建立如下幾個重要部分，環境模型、事物模型、事物與環境的互動接口、（事物與事物互動接口、環境與環境互動接口）、智慧型決策模型、智慧型評估模型，智慧型學習模型。而這裡的每一個部分都牽扯到非常廣的領域，非一時所能敘述清楚，因此就不再細述。