##EasyReadMore##

2009年12月13日 星期日

基於神經網絡的人機對抗人工智能系統 part2








基於神經網絡的人機對抗人工智能系統 part2

文章網址:http://www.playdota.com/forums/2597/22522-20110-31070-32463-32593-32476-30340-20154-26426-23545-25239-20154-24037-26234-33021-31995-32479-65288-29702-35770-65289-a/


第四章 數學算法的實際應用


4.1 確定三大系統的參數和意義
三大系統為巡查系統、控制系統和指令中心。每個系統都有傳入、傳出兩類參數。

4.1.1 巡查系統
巡查系統使用完全工程學方法編寫。
巡查系統的參數有:
1)信號轉化方面
傳入參數:
①內容:己方角色總數量及棋子總數量、每個己方角色當前金錢資源、每個己方棋子當前的實力數據(生命力、戰 鬥力、已學技能、已購買物品),以及所處位置
敵方角色總數量及棋子總數量、每個敵方棋子當前的實力數據(生命力、戰鬥力、已學技能、已購買物品),以及 出現在己方棋子視野中的每個敵方棋子的位置
②類型:視覺信號
③描述:對於人類角色,上述信號都是通過人類的雙眼,以視覺圖像方式傳入大腦。
傳出參數:
①內容:內存中的數據
②類型:實數組
③描述:上述各項信號雖然以視覺圖像表達出來,通過人類的雙眼傳入大腦,但這些信號在電腦內存中都有對應的 內存地址。信號轉化實際上,是直接將這些信號對應的內存中的數據,傳送給指令中心。
2)行為限制方面
傳入參數:
①內容:每個電腦角色通過控制系統下達給棋子的指令
②類型:句柄——發佈指令的電腦角色,句柄——執行指令的棋子,整數——指令本身,句柄——目標單位或目標 地點
③描述:巡查系統檢查電腦角色下達的指令,將其與內置的固定規則進行運算、比較
傳出參數:
①內容:「允許」或「否決」
②類型:布爾值
③描述:如果下達給棋子的指令沒有違反最根本的規則,就允許該指令;反之否決該指令,並給電腦角色一個「警 告」懲罰,讓其重新調整角色。

4.1.2 控制系統
控制系統也使用完全工程學方法編寫。
控制系統的參數有:
傳入參數:
①內容:電腦角色通過指令中心實施評估後,下達的指令
②類型:句柄——發佈指令的電腦角色,句柄——執行指令的棋子,整數——指令本身,句柄——目標單位或目標 地點
③描述:棋子接收到指令後會立刻響應。
傳出參數:
①內容:棋子執行指令的結果
②類型:浮點數——指令完成度
③描述:用於反饋給命令中心,這次下達/響應指令是否成功。

4.1.3 命令中心
命令中心的參數有:
1)知己知彼方面
該功能使用完全工程學方法編寫。
傳入參數:
①內容:經過巡查系統轉化過的各種信號
②類型:實數組
③描述:巡查系統為電腦角色提供知覺
傳出參數:
①內容:己方角色及其控制的棋子的整體實力、敵方角色及其控制的棋子的整體實力
②類型:實數組
③描述:命令中心接收到巡查系統傳來的數據後,經過相關計算,生成敵我雙方目前實力的評估報告(一系列實數 ),儲存於電腦角色的記憶數組中。
2)探索活動區域方面
該功能使用半工程學、半模擬法——前饋網絡編寫。
傳入參數:
①內容:經過巡查系統轉化過的各種信號
②類型:實數組
③描述:傳入的信號主要是己方棋子的位置分佈,和敵方棋子的活動記錄。因為敵方棋子不可見,只有進入己方棋 子的視線內才會被察覺,所以命令中心會根據傳入參數,預測敵人出現的地點。
傳出參數:
①內容:三維坐標,及坐標的重要程度
②類型:實數組
③描述:整個活動範圍是三維的空間,用三個實數變量x、y、z表示一個三維坐標(x,y,z)。傳出的三維 坐標表示目的地,目的地所處的地域不同,重要性也不同。重要性是固定的,但命令中心會根據目的地的重要程度 ,自行決定是否派棋子去探索。
3)提升棋子實力方面
該功能使用半工程學方法、半模擬法編寫。
傳入參數:
①內容:經過巡查系統轉化過的各種信號
②類型:實數組
③描述:傳入的信號主要是跟電腦角色自己有關的數據,為自身當前擁有的金錢資源(用於購買物品),和棋子當 前的實力(為了學習技能)。
傳出參數:
①內容:技能的編號和物品的編號
②類型:整數
③描述:為了實現「有效提升」棋子實力這一目的,需要先掌握電腦角色和棋子當前的數據(一系列實數),然後 輸進一個訓練好的神經網絡系統。神經網絡識別這一系列數據後,將迅速並準確地給出對應的具體實 施方案。
4)實時評估方面
該功能使用模擬法——競爭網絡編寫。
傳入參數:
①內容:經過巡查系統轉化過的各種信號
②類型:實數組
③描述:電腦角色的棋子遇到敵方單個棋子時,需要迅速評估自己棋子和敵方棋子的實力;如果己方數個棋子同時 遇見敵方數個棋子時,不僅需要評估每一個棋子的實力,還得考慮敵我雙方棋子之間,互相配合的能力(換句話講 ,就是計謀)
傳出參數:
①內容:電腦角色對它的棋子發佈的指令
②類型:句柄——發佈指令的電腦角色,句柄——執行指令的棋子,整數——指令本身,句柄——目標單位或目標 地點
③描述:電腦角色經過實時評估後,就會做出決策。決策的內容就是一系列指令,控制棋子做出一系列能夠擊敗敵 方棋子,或保全己方棋子的行動。行動包括直接上前攻擊、迂迴、誘敵深入、埋伏落單棋子、輔助己方棋子,或者 撤退、掩護友方棋子等等。


4.2 三大系統的具體實現思路

4.2.1 巡查系統
1)信號轉化功能
由於各種信息的視覺信號,都與電腦內存中具體的數據相對應,所以,只要將這種對應關係整理出來,列成一個可 查詢的表格,就能實現信號轉化功能。

輸入待轉化信號 → 查詢表格 → 得到輸出結果

2)行為限制功能
違反規則的行為共有下列幾種:

使用作弊工具,非法修改角色的金錢資源 → 非法改變金錢
使用作弊工具,非法修改棋子的實力 → 非法提升實力
以任何方式利用DOTA自身的漏洞 → 利用BUG
利用任何手段,直接偵測到敵方棋子的位置等不可見的數據 → 非法偵察情報
在附近沒有敵方棋子防守的情況下,偷襲敵方建築物 → 非法進攻
一方陣營的角色為它們棋子購買的特殊物品的總數量超標 → 違反物品限制

這些違規行為都可以通過多組數據描述。
一旦一個電腦角色發出的指令,其具體數據通過逐條比較後,與違規行為數據組中的數據整體相似,就可以認定這 個指令違規。

4.2.2 控制系統
為了實現指令的發佈與響應功能,這裡構造一個指令隊列系統。
構造方式如下:
1)系統為每一個電腦角色的棋子分配一個指令隊列
2)每個指令隊列中包含有編號1至編號10,一共10個(總數可變)指令單元
3)每個指令單元均有6項數據,分別是指令單元的指令、指令的目標單位、指令的目標地點、指令的計時器、指 令的描述、指令的描述註解。
4)指令單元每項數據的作用:

數據名稱 描述
指令 表示該棋子需要執行的指令
目標單位 表示該單位需要對誰執行指令
目標地點 表示該單位需要在哪裡執行指令
計時器 表示該單位執行該指令最多花費多長時間
描述 表示該指令的行為描述,影響後續實時評估結果
描述註解 表示其他必要的描述,影響後續實時評估結果
完成度 表示這個指令完成度如何
表 2
5)指令隊列中若存在指令,棋子將按編號從1至指令總數量(最大數量10),依次執行指令單元中 的指令。
6)電腦角色對指令隊列進行的操作,共有如下幾種:
①下達一個立刻執行指令
下達的指令會直接替換編號1的指令單元中的指令,無論棋子剛才在做什麼,現在都會立刻執行新下 達的指令。
②在指定編號的指令單元中下達一個非立刻執行指令,或在指令隊列最後附加一個非立刻執行的指令
這可以讓棋子擁有做出一系列指定動作(即使用計謀)的能力。
③清除指令隊列中所有指令
這可以讓棋子處於原地待命狀態。
④計算指令完成程度
如果指令根本沒被執行,則輸出0,否則輸出完成度數值(百分比)
7)指令隊列原理
發佈指令給事物(電腦角色發佈指令給隊列)——事物接收指令並執行(棋子接收到指令,並執行),這一方式模 擬了人類「思考」——「行動」的過程。

4.2.3 命令中心
1)知己知彼功能
一個角色的整體實力包括其擁有的金錢資源,棋子本身實力(生命力、戰鬥力)和技能、物品對棋子本身實力的提 升。
由於DOTA的設定,一個角色和它控制的棋子自身各種數據一旦確定,就一定會有一個確定的整體 實力數值。
設一個角色金錢資源為M,棋子本身生命力為H,棋子本身戰鬥力為A,棋子已經學習的技能對生命力、戰鬥力的 提升為S、I,棋子已經購買的技能對生命力、戰鬥力的提升為S'、I',整體實力為T。
則會有一個線性函數F,使得T=F(M,H,A,S,I,S',I')。
對於每一個角色(無論敵我),由於它各種數值(除了坐標數值) 雖然會改變,但在一定時間範圍內(數秒到數分鐘)可以保持穩定不突變(就算現在突然改變了,但也再會保持一 定時間,才再次改變),因此在這段穩定期內,可以使用函數F求出整體實力T。
2)探索活動區域功能
①半工程學方面,由於整個活動區域內各項地形數值不會改變(地面不會在這裡凸起一塊,或凹進一塊等),因此 一個地域內的地形的重要性(是否利於防守、是否毫無戰略價值等),在一開始就被設置好了,不會 改變。
所以目標地點所處的地域,重要性也能通過一個可查詢表格實現。

輸入目標地點坐標 → 查詢表格 → 得到輸出結果

而目標地點坐標,可以通過對敵方棋子活動記錄預測(敵人最後出現在哪裡,就嘗試去哪裡探索),或者反向查詢 表格(輸入重要性,得到目標地點)來求出。
②半模擬法方面,由於電腦角色只需要求出自身、敵方每個未露面棋子整體實力,然後通過簡單權重計算,算出棋 子到達未探索的目的地時,萬一遇見敵方棋子時,是否敵得過即可。
所以構建一個只有一個神經元的系統。
神經元有五個輸入,為自身棋子的整體實力,與敵方每個未露面棋子的整體實力的大小比較。如果自身棋子的整體 實力比一個敵方棋子強大,對應的輸入就為1,否則為0.
神經元依次把五個輸入與其對應的權重(電腦角色對於每個敵方角色的實力預估)相乘,並求積的總和。如果最終 激勵值超過神經元的閾值,則去目標地點探索承擔的風險可以接受;否則表示去目標地點探索承擔的風險太大,不 可接受。
3)提升棋子實力功能
提升棋子實力主要通過兩點,技能的(多選一)學習和物品的(多選一)購買。
技能的學習:
技能可以提升棋子的生命力或戰鬥力。
每個棋子每一等級可以學習一個技能(從自身技能庫中五選一),由於一個技能不會同時提升生命力和戰鬥力,因 此需要評估所有類別的技能的各項數據,找出學習哪一個技能後,棋子整體實力提升最明顯。
對於一些棋子的部分技能,存在一些常識性學習規則,這些規則是人類角色通過無數次試驗,得到的常識。如果一 個棋子技能學習部分存在常識性學習規則,技能將優先按照該規則以固定的方式學習技能。
如果一個棋子沒有或只有很少常識性學習規則,那麼就需要使用一個通用技能學習神經網絡,通過該網絡求最優解 。
由於通用技能學習神經網絡需要做到五選一,存在競爭關係,因此需要使用競爭網絡。

構建一個只有輸入層和競爭層的雙層競爭網絡。

輸入層由處理單元構成,處理單元的作用是將輸入的,可以完整描述一個棋子自身實力的所有數據,轉化為一個輸 入模式。對於每一個棋子,輸入模式是通用的,但因為每個技能都不相同,所以競爭單元也不相同。
競爭層由五個競爭單元組成。每個競爭神經單元都與輸入層的處理單元相連接,如果一個競爭單元輸入的加權和最 大,則該競爭單元對應的技能成為優勝者,被棋子學習。
由於技能的複雜性,這個競爭網絡必須由人工監督訓練。
物品的購買:
物品也可以提升棋子的生命力或戰鬥力。
物品總量眾多,而且物品的購買不受棋子種類限制(就是說對於每一個棋子,它能購買的物品都是相同的)。物品 的購買僅僅受限於電腦角色的金錢資源,和棋子所攜帶物品總量(一個棋子最多可以攜帶6個物品) 。
電腦角色在為棋子購買物品時,不可能把每一個物品都買一遍,因此需要評估所有類別的物品的各項數據,找出購 買哪一個物品後,棋子整體實力提升最明顯。
對於一些棋子的部分物品,也存在一些常識性購買規則,這些規則是人類角色通過無數次試驗,得到的常識。如果 一個棋子物品購買部分存在常識性購買規則,物品將優先按照該規則以固定的方式購買。
如果一個棋子沒有或只有很少常識性學習規則,那麼就需要使用一個通用物品購買神經網絡,通過該網絡求最優解 。
由於通用物品購買神經網絡需要做到多選一,存在競爭關係,因此需要使用競爭網絡。

構建一個只有輸入層和競爭層的雙層競爭網絡。

輸入層由處理單元構成,處理單元的作用是將輸入的,可以完整描述一個棋子自身實力的所有數據,轉化為一個輸 入模式。對於每一個棋子,輸入模式都通用,競爭單元也通用的。無論棋子是什麼種類的,只要它的輸入模式與已 知的符合,就可以購買對應的物品。
競爭層由多個競爭單元組成,數量取決與物品總數。每個競爭神經單元都與輸入層的處理單元相連接,如果一個競 爭單元輸入的加權和最大,則該競爭單元對應的物品成為優勝者,被棋子購買。
由於物品的複雜性,這個競爭網絡必須也由人工監督訓練。
4)實時評估功能
發生遭遇戰時,巡查系統會對每個電腦角色進行通告,並為其提供戰況情報與數據。
對敵我雙方臨近戰場棋子整體實力的評估,是通過一個神經元進行的。這個神經元構造與實現「探索活動區域」功 能的神經元相似,只不過目的地坐標被自動設定為戰場。
這個評估是告訴一個電腦角色,加入戰鬥有多大風險,多大的勝算。電腦角色將評估結果於自身的性格值結合,最 後決定是否加入戰鬥。

電腦角色謀略的使用,是靠一個競爭網絡實現的。

這個競爭網絡的處理單元,將戰場的地形、坐標、範圍,以及參與戰鬥的敵我雙方的棋子整體實力等詳細數據,轉 化成一個輸入模式。對於每一個棋子,輸入模式都通用,競爭單元也通用。無論棋子是什麼種類的,只要它的輸入 模式與已知的符合,控制它的電腦角色就會做出相應的一系列動作(即實施謀略)。
競爭層有多個競爭單元組成,數量取決與一個角色可以做出的謀略或配合的總數。對於電腦角色,它們一開始並不 瞭解,也不能識別不同輸入模式對應的行為的意義。所以這個競爭網絡必須由監督人工訓練,由人告訴電腦角色, 什麼樣的行為是迂迴、是誘敵深入或埋伏落單敵方棋子等,以及什麼樣的輸入模式對應什麼樣的行為 ,等等。


第五章 總結
上述全部內容就是一個DOTA人工智能系統的構建理論和實現思路。
理論的核心內容是通過三大系統,即巡查系統、控制系統和命令中心,來實現一個人工智能的完整功 能。
1)巡查系統就像是個裁判,它為電腦角色提供知覺能力,同時每時每刻監督電腦角色的行為,如果發現電腦角色 違規,就會警告該角色並責令改正。
2)控制系統是一個帶有反饋環節的控制手段,它為電腦角色提供對棋子的絕對控制權力,使電腦角色能夠有效地 將思維通過棋子的行為表現出來。
3)命令中心類似於人類的大腦,它為電腦角色提供思維能力,電腦角色通過這個系統產生意識,會對感知環境, 並對對各種複雜狀況做出反應。
整個人工智能實際製作起來的難點,一是理論的建立,二是算法的設計,而算法的設計又依賴於現有 數據的輸入。
理論為實際算法和程序代碼提供思路,反過來實際算法和程序代碼會通過自身的設計、執行來支持理 論的正確性。
編寫一個DOTA人工智能系統雖然是非常費時的工作,但它由於使用了人工神經網絡系統,因此不論是功能方面 、排錯維護方面,還是算法複雜度、實際代碼所需量,都比完全工程學方法編寫的人工智能系統強大 。
目前,整個DOTA AI的程序代碼已經實現了第一大系統巡查系統的「信號轉化」功能,和第二大系統控制系統的全部功能「指令的 發佈/響應與執行結果反饋」。
所有系統中,以第三大系統命令中心「實施評估」功能最為重要。可以說一切其他的智能,都建立在電腦角色正確 識別當前環境、當前棋子實力等數據的基礎上。
要完整、精確地實現第第三大系統的功能,需要以各種數據錄入完畢、各個算法設計完畢、所有神經網絡正確訓練 完畢為前提。
目前整個DOTA AI的製作正在進行的階段,就是數據的錄入。只有將所有必要的數據錄入完畢後,所有依賴於數據完整的後續功 能(算法設計、神經網絡訓練)才有實現的可能。
總體來說,新版人工智能系統編程已經完成了40%,進度快速增長中。這個全新的,與舊版有著本質不同的人工 智能,預計完成時間——2009年年底。


參考文獻
[1]Mat Buckland[美].遊戲編程中的人工智能技術(AI Techniques for Game Programming).清華大學出版社. 2006.5
[2]JASS使用教程




6 則留言:

  1. 在"1.3 神經網路的訓練"裡有提到"監督式學習"與"使用"倒傳遞網路".
    但在part2的介紹裡, 關於類神經網路學習的實作部份似乎是沒有的, 個人以為最接近的描述是"模擬法". 但什麼是"模擬法"呢?

    JASS似乎不支援在遊戲結束時可回存某些參數(類神經網路的權重)至地圖裡. 雖然可以用寫入其他檔案方式保存, 再開啟WE, 改入地圖裡, 不過文中並沒有說是以這種方式來改變類神經網路的權重, 而是用"模擬法". 對於"模擬法", 個人的猜測是自行建立一個模擬環境(在這裡是模擬在War3上跑的Dota)來訓練神經網路, 但所費的工程應該是滿大的(約等於是寫一個遊戲環境, 而且還要很像Dota). 況且監督式學習, 需要不少學習樣本(想像成高手在旁指點). 這也需要人力(而且還要是高手)實際配合, 除非能從現有的rp讀出些什麼數據來, 這就是另一個問題了.
    總之, 會遇到的問題, 需要的工程不少, 但文中都輕描淡寫的帶過了.

    回覆刪除
  2. 如果對RTS的AI有興趣, 不妨來看看.

    下篇是sc1的AI挑戰賽的簡介.
    http://airobot.org/blog/2009/11/16/%E3%80%8A%E6%98%9F%E9%99%85%E4%BA%89%E9%9C%B8%E3%80%8Bai%E6%8C%91%E6%88%98%E8%B5%9B/

    在米國舉辦的AI挑戰賽--
    http://eis.ucsc.edu/StarCraftAICompetition

    所使用的主要api--
    http://code.google.com/p/bwapi/

    還有其他api列在第一個link中.

    回覆刪除
  3. 這三篇文章:基於神經網絡的人機對抗人工智能系統,
    是我轉貼別處的文章,我從這些文章中得到了一些靈感,
    其實我有辦法創造出很像人操作的AI,
    但是要創造出很聰明還會學習的AI,目前無解!
    你介紹的那些網址都是關於星海爭霸的,
    可惜跟魔獸爭霸有差距的!

    回覆刪除
  4. 我的看法是: 以有限狀態機方式(一堆條件判斷與行為執行)在JASS上做AI會比用類神經或是其他機器學習的方法來得恰當. "機器學習", 即使是訓練完成後的架構所需的運算, 個人認為對JASS運算的負擔太重了. 更不要說如何來建立一個訓練環境(這也是我第一篇留言的重點).

    除了sc1成為經典RTS之外, 以C++做的api將ai的運算獨立出sc1主程式外, 可以提供更多的運算效能(不用再透過一層綁手綁腳的script)--我想這就是為什麼會有sc1的ai競技的原因, 很多關於ai的理論終於可以在這經典RTS遊戲上實現了, 甚至是與真人對決, 就像電腦象棋vs人類棋王. 當然, 這對寫war3的ai是沒有幫助的, 運作的環境不同, 也許將來也會有熱血的geek做出類似的api給war3使用吧.

    回覆刪除
  5. 不瞞你說,我很看好星海2的發展。因為星海2的語言類似 c 語言,
    而且官方有保證在 AI 的編寫上,能有更棒的表現!
    所以我會在星海2一推出,馬上開始編寫 星海2 地圖,
    到時候希望能夠有比 SC1 + C++ api 的 AI 更加強大!

    回覆刪除
  6. sc1的c++api與sc2的銀河script是不同層次的作法.
    就運算效能而言: sc2的script似乎還是都得透過vm來執行. 這肯定比c++更貼近機器的執行效率來得低. 所以使用sc1的c++api能實現需要更多複雜運算的ai.
    然而就普及而言: sc1的c++api就像是一種外掛, 要使用還得另外安裝, 並且sc1已經老了, 很少人在玩了. 所以就算用sc1的c++api做出了個ai也只能拿來自娛(或是參加米國的ai競技 XD). 相比之下, 在明日之星的sc2上寫custom game, 可以讓更多玩家用到自己寫的ai(據說地圖還可以賣錢), 這樣的成就感或許更大的吧.
    總之, 看需求來決定環境囉.

    回覆刪除

※怎麼下載?Xuite硬碟MediaFireBadongoSendSpace
※文章可以轉貼嗎?可以,不過要註明出處、標示本站連結。
※載點可以轉貼嗎?不可以,不能盜連。
※建議瀏覽器:Chrome 或 Firefox 或 Opera 或 IE7以上
!請按+1來支持本站!