即時戰略遊戲（比如 WAR3）的 AI 是怎樣實現的？

11-26

用的是什麼演算法？遺傳演算法？模擬退火演算法？這東西寫起來有多複雜？

國內真正做過遊戲AI的很少，說概念的人很多，所以看了半天離實際編碼還是很遠，不知道該怎麼入手，因為國內遊戲主要以MMO和卡牌為主，RTS比較少，體育競技類遊戲更少，沒幾個真正寫過強AI代碼的。而從AI的難度上來看，是：MMO &< FPS &< RTS &< 體育競技。作為實際開發過AI的人，拿一份五年前的代碼，以最難的體育競技類遊戲為例，來科普一下，什麼叫做遊戲團隊策略，什麼叫做分層狀態機？具體該如何落地到代碼？如果你能實現體育競技的AI，那即時戰略只是小事一樁。

硬派遊戲AI，不是虛無縹緲的神經網路，用神經網路其實是一個黑洞，把問題一腳踢給計算機，認為我只要訓練它，它就能解決一切問題的懶人想法。更不是遺傳演算法和模糊邏輯，你想想以前8位機，16位機上就能有比較激烈對抗的足球遊戲、籃球遊戲，那麼差的處理器能做這些計算么？

硬派遊戲AI，就是狀態機和行為樹。狀態機是基本功，行為樹可選（早年AI沒行為樹這東西，大家都是hard code的）。大部分人說到這裡也就沒了，各位讀完還是無法寫代碼。因為沒有把最核心的三個問題講清楚，即：分層狀態機、決策支持系統、以及團隊角色分配。下面分類介紹：

何為分層狀態機？

每個人物身上，有三層狀態機：基礎層狀態機、行為層狀態機、角色層狀態機。每一層狀態機解決一個層次的複雜度，並對上層提供介面，上層狀態機通過設置下層狀態機的目標實現更複雜的邏輯。

基礎狀態機：直接控制角色動畫、提供基礎動作實現，為上層提供支持。
行為狀態機：分解動作，躲避跑、直線移動、原地站立、要球、傳球、射球、追球、打人、跳。
角色狀態機：實現更複雜的邏輯，比如防射求、籃板等都是由N次直線運動+跳躍或者打人完成。

每一層狀態機都是通過為下一層狀態機設定目標來實現控制（目標設定後，下層狀態機將自動工作，上層不用關心動畫到底播到哪了，現在到底是跑是跳），從而為上層提供更加高級擬人化的行為，所有狀態機固定頻率更新（如每秒10次），用於判斷狀態變遷和檢查底層目標完成情況。最高層的角色狀態機的工作由團隊AI來掌控，即角色分配的工作。而行為狀態機以上的狀態抉擇，比如回防，到底是跑到哪一點，射球，到底在哪裡起跳，路徑是怎樣的，則由決策支持系統提供支持。

何為決策支持系統？

狀態機為角色的大腦，而決策支持系統是眼睛和耳朵，常見的工具有勢力圖（Influence Map）和白板（相當於不同角色間喊話），其中勢力圖比較常用，籃球遊戲AI勢力圖可以用下面幾張圖表示：

勢力圖1：於防守籃板距離的map，每格分值為最遠距離減去該格到籃板所在格子的距離

勢力圖2：進攻籃板距離的map，每個分值為最遠距離減去該格到籃板距離，籃板後為0

勢力圖3：同敵人距離，每個敵人有影響範圍，範圍內，離敵人越近分越低，範圍重疊選低的。

勢力圖4：同所有隊友目標位置距離map，打分方法類似上圖。

勢力圖5：與每個隊友目標位置距離的map，標識單個隊友目標位置距離的map。

勢力圖6：現實傳球可行性的map，分數越高，越容易把球傳到該格子上。

勢力圖7：容易把球傳出的位置map，越容易直接傳球給隊友的區域分數越高。

勢力圖8：綜合map，把以上map按一定加權求和。球員有合法目標區域，便於實現內線遊走和外線遊走。

每個球員性格不同，權值也不同，有保守的球員，有喜歡冒險的球員，權值不同而已。這些勢力圖都是為了給上面的三層狀態機和團隊狀態機提供決策支持的。

何為團隊角色分配？

每一層狀態機為下一層設定一個目標，讓下層自動工作，頂層角色層的目標則由最高層的團隊ai進行戰術指導。

團隊狀態機跟據當前的遊戲情況確定當前首要目標（進攻或者防守），又根據當前的勢力圖等信息，確定進攻或者防守的具體戰略（比如中路突破、盤路包抄、下底傳中等），最終為當前己方的所有角色分配一個新的任務，即設定角色層狀態機的新目標，確定他是做主攻還是做助攻，還是聯防還是策應。具體該怎麼聯防，怎麼策應，那就是角色層狀態機的事情了。

話題總結

其實團隊AI沒那麼玄乎，任何問題就是一個編程的建模問題，而最複雜的體育競技類遊戲的AI策略，上文已經給出模型，相信各位略加修改即可使用。寫狀態機是遊戲AI的硬功夫，如果狀態機邏輯經常改變或者項目規模大了以後可以考慮引入決策樹來控制狀態機，程序提供一系列介面，然後用可視化的編輯器進行更改，感興趣的人可以參考決策樹相關文章。

概率統計

如果上面這些邏輯都實現了，這時候才可以輔助與概率統計來讓角色具備學習特性，比如統計某個策略對對手的成敗情況，用來支撐下一次決策，這樣能夠逐步發現對手的弱點，還可以統計所有用戶的大數據，來確定某種情況下，選擇什麼策略，能夠對付60%的用戶。

神經網路

在上面所有邏輯都實現了，你調試好了，玩著比較順暢的時候，再在團隊角色分配處嘗試使用神經網路或者模糊邏輯，同樣是學習大數據，來引入一些不可控的人性化的成分，讓遊戲更加有意思。（EA的 FIFA 20XX號稱引入神經網路，Call of Duty的AI也號稱引入了神經網路和學習機制）。確實能讓遊戲更有趣一點，但是僅僅有趣了一點而已。

自己可以打開地圖的jass腳本去看的，星際里也有script可以看。

War3時代，底層尋路是地圖分Tile之後的A *尋路，上層邏輯估計就是FSM有限狀態機，經過這些年發展，現在遊戲里尋路還是基於導航網格（NavigationMesh）的A*，上層AI很多是Behavior Tree來實現的。

遊戲和工程的AI目標完全不同的，遊戲的AI是看起來聰明、表現多樣；工程上我熟悉的多是為了解決組合爆炸問題，通過AI演算法求解。但工程上的AI演算法也有各種限制，例如遺傳演算法的過度收斂、收斂到局部解、神經網路的權重訓練出來人不可理解、多少個神經節點能解決特定問題的沒有定義，等等等等還有大量問題，這些對於遊戲開發這種需要控制開發周期和確定性結果的工程設計都不利啊！所以遊戲這種密集開發的軟體工程，一是AI不需要這麼複雜的演算法就能實現，二是AI演算法很多不穩定和難理解控制並不適合遊戲快速迭代開發。

順帶一提，遊戲中的AI系統底層A*是圖演算法，上層Behavior Tree只是個框架，方便邏輯書寫的。當然這個世界上也有各種嘗試把學院派AI應用在遊戲的項目，例如bwapi -

An API for interacting with Starcraft: Broodwar (1.16.1)，每年還有AI比賽遊戲界「深藍」伯克利的《星際爭霸》AI「主宰」這是篇伯克利AI的報道，自己當年畢設就通過這平台搞了個星際微操的遺傳神經網路玩了玩，滿好玩的。

ps：個人感覺很多遊戲里的操作集是有限的，遊戲AI在工程意義上去擬真玩家是可解的，某種意義上遊戲AI是可以率先通過工程手段通過圖靈測試。More human than human: AI game bots pass Turing Test

War3的AI沒有必要使用你提及的演算法，或者說，根本無法使用。
有相關經驗表明，遊戲的AI如果採用神經網路等演算法，會傻得出奇。
使用學院派演算法的AI總會做出匪夷所思的動作，讓人無法理解，遊戲性盡失。

其主要原因在於遺傳演算法、模擬退火演算法、神經網路演算法、各種分類演算法等等，都是高度概括化的，旨在找到局部最優解/或者找到全局關係。但是我們的AI實際不需要最優解和全局關係，一是你的電腦沒那麼叼，這麼複雜的情況，如果真的高度概括出來了，其複雜程度是很高的，你的電腦也帶不動，其次是演算法在訓練過程中收斂也會很慢，因為樣本太過複雜，所以也許要花上很久（幾年？猜的）來收斂，如果我們降低收斂精度要求來使速度加快，AI就會變得非常傻，做遊戲明顯不能這樣。即使上述問題都被解決了，還有個問題就是，電腦得到了最優解和最優數學模型，你作為玩家就沒有勝利的希望了，這遊戲給誰玩？
即使設計公司神經病般的決定如此設計，每當你的遊戲有更新，兵種變化，數據變化，整個演算法就要重新訓練，玩家需要重新下載AI的全部內容，對用戶的體驗和公司的工作效率都有損害。

戰略類遊戲的AI，還是有限狀態機。
根據不同情況分類做不一樣的事情，全都設計好，設計的盡量詳細，就OK了。

關於其複雜度：
這類AI的程序體往往超乎想像的長，當然具體長度和遊戲本身的設計也有一定關係，和遊戲其它部分代碼的設計優化程度也有關係，但是即使在較優環境中，其AI長度也是很長的。具體原因就在於其事無巨細的分類了所有情況，規定了AI在不同時間不同情況所做的不同事情，作為一個戰略類遊戲，尤其是即時戰略類遊戲，這是十分複雜的，情況十分多，因此程序本身也會相當的長。

但是他運行速度又快！又像人類在玩！又給了玩家勝利的可能！又容易設計和更改！
何樂而不為呢？

瀉藥。
當然是狀態機，樓上幾位已經說得很好了。
我能補充的是：
1. 類似遺傳演算法這種AI演算法都是計算量極大、需要等幾小時、幾天、幾個月才能出結果的演算法，而遊戲的AI必須在一個tick內迅速作出決定;
2. 重量級的AI演算法是解決不知道答案的問題用的。對於已知答案的問題，當然直接給答案就好；
3. 遊戲中的AI有兩個目標：更像人/更有趣。為了讓他更像人，直接採用預定的策略就可以；為了更有趣，加入一些隨機因素就成。

我來賣個萌呵呵

有限狀態機幾乎是2005年以前所有遊戲的ai解決方案

但是即使是有限狀態機，在刻畫複雜的遊戲場景時，也會陷入冗長的代碼鏈之中而喪失代碼可讀性
所以 behavior tree（行為樹）出現了
本質上說，behavior tree的原理並不比有限狀態機高明多少
但是behavior tree可以大大簡化ai控制流程，使解決方案更加清晰

一個用有限狀態機寫的ai控制，用behavior tree大概只需要1/3的代碼，並且可讀性更強

要了解behavior tree，請查看cry engine 相關資料，
或者havok的行為樹資料更加翔實
同時也有一個基於c#的實現，叫做tree sharp ，可以搜下

贊同樓上所有答案。

傳統即時戰略 [1] 的AI其實可以分為兩個部分，一個是資源管理AI，一個是戰爭AI。

資源管理AI就是決定建築、科技樹、建兵的AI。
資源管理AI一般採用的是規則式AI。
規則式AI簡單來說，就是一大堆if－else語句。
它有兩個主要的部分，一個是工作記憶，另一個是規則記憶。[2]
工作記憶儲存已知的遊戲世界信息，這部分是動態的。
規則記憶儲存設遊戲計師設計的的規則。
正如 @五八所說，規則都是pre－scripted的。
而當工作記憶符合規則記憶的某一條規則時，相應的行動就會被觸發。

這樣做的好處是，遊戲設計師擁有完全的掌控權。
而它的壞處也是十分明顯的——因為是pre－scripted，所以整個規則是靜止的。
但是畢竟在即時戰略中，「正確合理」的發展方式就那麼幾套方案，所以規則式AI帶來的好處多於壞處。

當然，規則式AI也有一些手段來動態學習。
例如給規則的觸發條件並不是一些具體的「錢多少、兵多少」，而是權重。
每次分析時，根據上一次觸發的結果的好壞來調整所有規則的權重，然後選出權重最高的規則，觸發相應行為。［3］
然而動態有時會帶來不確定性，所以採取與否，需要看遊戲的設計來決定。

戰爭AI其實可以分為兩層［4］，一層是將軍AI，一層是士兵AI。
將軍AI的工作是分析遊戲世界，然後告訴所有士兵AI 「去哪裡，做什麼」。
士兵AI的工作是分析自己附近的遊戲世界，然後決定相應的行為。

在將軍AI分析遊戲世界時，有可能會採用Planner［8］、Utility－Based AI或者Neural Network［11］等能夠帶來不確定性的AI演算法。
我對Planner不熟悉，就不多說了，大家可以看看［8］鏈接。
Utility－Based AI是指一套打分系統，根據遊戲世界的信息對行為庫［5］打分，然後選出或者組合出［6］一套行為［12］。
Neural Network是指幾層神經元，例如經典的三層網路——輸入層、隱藏層、輸出層，世界信息通過輸入層輸入Neural Network系統，然後輸出層輸出一個結果［7］。

上面提到的這些演算法有一個共同的好處，能夠根據遊戲世界的變化帶來不確定性。
因為即時戰略中的戰爭部分是最難預測的，玩家可以有無窮無盡的戰術變化，所以將軍AI需要更加動態來產生更加動態的戰術。
然而，這些演算法，特別是Nerual Network，它們產生的結果的過程是「黑箱的」——即使是我設計的將軍AI，我也不知道它是怎麼工作的...遊戲設計師可以說失去了掌控權。
不過，有研究表明，神經質AI在即時戰略中表現最好［9］....或許，這也是算是「出其不意」吧...

相反地，士兵AI需要比將軍AI更加靜態。
如果你把士兵拉到敵人旁邊，他卻在那邊Idle的話...
所以樓上都有提到的有限狀態機、行為樹等更加靜態的演算法［10］會更合適，因為遊戲設計師可以設計好士兵的行動規則。
例如弓箭手在距離敵人大於XX米的情況下射箭，距離小於X米的時候肉搏，士氣低於XX的時候走佬。
如果用Neural Network來實現這些設計的話就會哭笑不得...對的，我就用過Neural Network設計過士兵AI，是我們大學的神經網路的作業...

除了上面的提到的演算法，還有另外一些提高遊戲性的演算法可以採用。
模糊邏輯，Fuzzy Logic，讓遊戲世界的信息模糊化，帶來合理的不確定性。
勢力圖，Influence Map，讓遊戲世界的信息可視化或者是規範化，有助於將軍AI分析。
隨機，Randomization，在適當的時候做出適當的隨機選擇［13］。

注釋或資料來源：
［1］我個人喜歡劃分《星際》《紅警》《帝國》等遊戲為「傳統即時戰略」，通常都有資源管理和戰爭兩部分組成。區別於塔防、即時戰術等即時的策略遊戲。
［2］［3］資料來源：《遊戲開發中的人工智慧》第十一章，規則式AI。
［4］也可以是多層，視乎需求而定。
［5］行為庫指的是一個很多單元行為的集合。一個例子就是行為樹裡面的「行為」。
［6］單元行為如果設計得好、相互沒有依賴關係得話，它們之間可以相互組合。
［7］「結果」可以是一個行為的代號，也可以是一個權重。
［8］Planner資料來源：http://intrinsicalgorithm.com/IAonAI/2012/11/ai-architectures-a-culinary-guide-gdmag-article/
［9］資料來源：Solidot | "神經質"AI在即時戰略遊戲中表現最突出
［10］如 @Freelancer 所說，稱之為框架會更加合適。
［11］Flanking Total War』s AI: 11 Tricks to Conquer for Your Game 提到《全面戰爭》有用到Neural Network，但是我對文章的說的「Neural Network用在士兵AI上」表示懷疑，我猜測是用在將軍AI上的。
［12］一個利用Utility－Based AI的成功例子 http://christophermpark.blogspot.sg/2009/06/designing-emergent-ai-part-1.html
［13］感謝 @HARDCOREGAME 提醒

遊戲的AI只有一個目的，那就是讓玩家玩的爽。
模擬退火，神經網路這些演算法不能達成這唯一的要求，所以遊戲中一般不會採用。

現在業界用的最多的是行為樹，可以簡單理解為加強版的狀態機。

1 請從角色體驗和遊戲類型考慮AI的複雜度
2 有限狀態機適應大多數系統
3 BT可以有效解決分支邏輯的體驗表達
4 尋路和群組可能會涉及到A*的演算法深入但還是有替代方案
5 基於目標的AI是一個業界嘗試的新思路
6 請製作讓玩家覺得有趣「聰明的」AI 不是搞科研

印象里有個遊戲能多少體現AI是怎樣工作的。《裝甲核心V：審判日》，裡面有個僚機系統，本身是啥也不會幹的，需要你自己定義他各類狀況下的行為。當然了，裡面是用各種已經定義好的模塊來實現，並不是最底層的機制，但是還是能很清晰的體現狀態機和行為樹的。圖之後補上。
不是程序員，只是個玩家，說的不對的請指點我修改。

war3里是不可能使用類似「遺傳，模擬退火」等學院派演算法的，主要還是有限狀態機，消息機制，控制行為，群狀態控制等，具體到策略上的規則依然是人為設定好的。
黎清水推薦的書是遊戲ai編程里最經典的教程，你可以去大概翻翻前幾章便可以對遊戲的ai設計有個基本大致的認識。

推薦一本書遊戲編程中的人工智慧技術 (豆瓣)，非常好的解釋了題主的問題，而且有C++源碼。其實上面說的都對，有限狀態機，遺傳演算法，神經網路編程遊戲AI，在這本書中都有提及。只不過實際應用中有限狀態機應該是主流吧。

war3的AI我沒寫過，別的即時戰略遊戲的AI我倒是分析過。舉個例子，神話時代、帝國時代3、國家的崛起的AI都差不多，前半截出農民分配礦工去不同資源上都是設定好的，幾分幾秒造哪種建築出什麼兵種都是設計好的。然後都是照方抓藥，人類來什麼兵AI就派某種兵來頂，發生什麼狀況就會觸發什麼預案，都是設計好的。所謂自我學習的AI也只不過是把某情況觸發某預案的閾值變數變化了，不會出現特別複雜的「算」法，沒什麼可算的，都是條件觸發罷了。國家的崛起的AI不過是一堆幾kb的C++語言文件。至於微操方面的AI也是如此，一堆條件觸發罷了。

我war3作圖五年，題主問的那些演算法一個都不清楚——那時候才初三好嗎－－＃
做AI其實得票第一的那位已經說得很好了：暴雪也好，你也好，造個AI是陪人玩的，不是把人虐的滿地找牙……事實上，暴雪內置的AI編輯器也十分簡單，界面基本上分為兩部分：

獲取資源進行發展的部分

——設計一個混合的發展樹（裡邊有建築科技小兵，包括分礦、第1/2/3英雄等）
——根據發展樹逐一建造資源能夠提供的東西
——＊這弊端很明顯，暴雪官方的AI永遠是一個模樣，並沒有多樣的戰術
——＊＊AMAI可以有各種奇怪的戰術，比如 Tower Rush 吹風流骷髏海等等……

消耗資源進行對戰的部分

——設計一個進攻樹（裡邊包含野點（低中高級）和敵人基地），進攻樹可以重複
——設計一些小分隊陣容，比如一個近戰陣容可以包括大G狼騎等等，一般還要加上英雄，每次貌似隨機出一隊人去進攻
——交戰時，既能自己釋放就不用說了；血少的會往後撤退，誰打自己的英雄友軍就打誰，這是臨場戰略
——＊實際上，這樣的AI還是不夠智能，至少戰術上從來不顧及玩家。比如你的AI盟友總是笑呵呵的打個嘆號，然後等都不等你就出征了……

仔細想想對戰大體不就是這麼兩件事么：找資源和耗資源。這兩個處理好就可以應付大部分情況。
除此之外，還有一些雜項設置，比如根據攻擊護甲類型自動選目標優先攻打，優先幹掉敵方英雄……

如果要研究代碼肯定讓樓主失望了，但要做個戰略AI大概就是這些相對簡單的步驟，這通常已經能取悅大部分玩家。
如果真的能做出那種戰無不勝的AI，那麼說到暴雪時大家一定不會認為這是個偉大的遊戲公司，他早就有更賺錢的生意了，給國防部寫寫代碼分分鐘雄起好么。

遺傳演算法？模擬退火演算法？如果真的我們要在所有遊戲中這樣實現遊戲ai，那麼我們數學系的學生就業就不會那麼困難了。
前面已經把這個問題答得很透徹了，有限狀態機是最「經濟」的解決方法。隨之而來的行為樹規範了這種方法。這些方面我也不專精，所以就不再贅述。
我只想提一下以前初中的時候很無聊做魔獸地圖的時候，有一項就是添加ai。其實魔獸地圖編輯器的ai腳本基本上不需要創作者多少編程知識和數學知識，你只需要把什麼時候怎麼做告訴計算機就好了。
所以遊戲ai的難度在於，人要實現預知大體上的所有可能性。

有人用強化學習來寫星際AI，鏈接：Berkeley Overmind

那種演算法實際上性能很差。現在通常都用概率網路。

打開war3編輯器可以看看。
War3 的 AI 應該是多方面相互結合而成的。

首先是單體AI，移動；巡邏；攻擊；逃跑；站定；跟隨；建造；這個從單位命令上可以推測出來。
一般AI：拾取物品，購買物品，受傷忽略，去掉受傷單位，組隊逃跑，英雄逃跑，單位逃跑，聰明的火炮等等。
英雄：升級技能。
建築：按找某種模式建造建築。
攻擊：優先攻擊哪些單位。

有了這些東西，就可以利用腳本作出各種豐富的AI了。

從編輯器提供的功能上來分析，並沒有使用什麼高深的方法。

和電腦對戰，電腦有一個非常愚蠢的設定，你攻擊建造的建築，它會取消，然後又迅速建造，你再攻擊，它再取消，如此循環。可見AI的設定並不聰明。

不過對於遊戲而言，已經足夠了，因為兩個玩家之間對戰，並不需要多麼聰明的AI支持，靠的是玩家之間的操控能力。

只有我一個人覺得是人肉寫if else的嗎。。。

Reinforcement learning應該是終極解決之道啊

簡單提一提：

紅警2/尤里的復仇里的AI：

【第一章】AI基本教程——AI(MD).ini結構及原理簡析

AI(MD).ini（以下簡稱AI），和其他的ini文件一樣，控制著電腦玩家的行為。AI是從地圖文件中派生出來的，因此
可以將其複製粘貼到地圖文件的後面用FinalAlert2打開並編輯。當然，本章主要提供給希望學習手工編輯的Modder們。

§1.1 AI的結構

每一條有效的AI規則由四個部分組成：AI觸發（AITrigger）、作戰小隊（Team）、特遣部隊（TaskForce）和腳本（Script）。

* 這四個部分中，只有AI觸發是不需要註冊的，其餘都需要註冊。

這四個部分的關係為：

　　　　　　　　　↗特遣部隊1
　　　　作戰小隊1
　　　↗　　　　　↘腳本1
AI觸發
　　　↘　　　　　↗特遣部隊2
　　　　作戰小隊2
　　　　　　　　　↘腳本2

來源：

紅色警戒2尤里復仇修改入門視頻教程 2016年版

|--基礎教程包

|--4.ai教程.txt

作者：LH_Mouse

修改時間：?2016?年?2?月?10?日，??19:38:39

參考網站：http://bbs.ra2diy.com