星際争霸中，玩家需要按照合理的順序去建造單元，以盡快形成所需的戰鬥力。不過，找到最優的建造順序并不簡單，需要做權衡。例如，玩家可以先建造一些勞工，讓勞工去采集資源，勞工越多收集資源的速度就越快，進而盡快達成建造的條件，然而建造勞工也需要消耗時間，太多勞工也是浪費，是以需要找出一個合理的建造方法。
本文内容主要結合UAlbertaBot的代碼和相關的論文《Build-order Optimization in StarCraft》進行分析，論文位址如下：
https://www.aaai.org/ocs/index.php/AIIDE/AIIDE11/paper/viewFile/4078/4407
星際争霸遊戲中，勞工在采集礦石
建造目标的産生
UAlbertaBot的政策管理器（StrategyManager）會根據目前局勢去選擇一種政策（具體方法後續再探讨，這裡先關注建設相關），每種政策包含該政策下需要有哪些單元。
例如，如果AI選擇神族（protoss），政策管理器有可能産生一個叫ZealotRush的政策，這個政策對應以下的建造目标，包含一些Probe（勞工）、Pylon（水晶塔）、Gateway（兵營）和Zealot（狂熱者，一種攻擊機關）。
["Probe", "Probe", "Probe", "Probe", "Pylon", "Probe", "Gateway", "Gateway", "Probe", "Probe", "Zealot", "Pylon", "Zealot", "Zealot", "Probe", "Zealot", "Zealot", "Probe", "Pylon", "Zealot", "Gateway", "Probe", "Pylon", "Probe", "Zealot", "Probe", "Zealot", "Zealot", "Zealot", "Zealot", "Pylon", "Probe", "Zealot", "Zealot", "Zealot" ]},
Probe相當于勞工
當AI選擇的政策有變更、或者玩家某些單元被殲滅時，就需要更建立造順序。而ProductionManager便會根據StrategyManager的建造目前去建設。源碼中，上層通過如下接口給ProductionManager設定建設目标。
void ProductionManager::setBuildOrder(const BuildOrder & buildOrder); 再通過performBuildOrderSearch方法做深度搜尋，最終獲得最優建造順序。
ProductionManager::performBuildOrderSearch() 對遊戲的抽象
程式将遊戲的建造部分抽象成“遊戲狀态”和“動作”，并使用搜尋算法來計算最優解。
狀态
對于遊戲狀态，抽象成 S=(t,R,P,I) ，各含義如下：
- t是一個數值，代表遊戲的時間（幀數）
- R是一個向量，代表各種資源占用情況，例如目前遊戲有3個兵工廠，其中兩個是可用的，另一個進行生産，一分鐘後才變為可用
- P是一個向量，存放已經安排但尚未執行的動作，例如正在建造補給站，還需30秒才能建完
- I是一個向量，訓示勞工的狀态。例如有8個勞工正在挖晶體礦（mineral），另有3個正在收集油礦（gas）
通過抽象，程式便能夠使用較為簡單的數值來表達遊戲狀态，雖然這樣的表達簡化了很多内容，卻也降低了計算量，遊戲AI程式的運作速度不能太慢，才能夠做到實時操控
動作
- 對于建造有關的操作，使用 a=(δ,r,b,c,p) 來抽象，各個符号的含義如下
- δ 是一個數值，代表動作的持續時間（幀數），例如建一個士兵需要10秒
- r、b、c代表執行該動作的各種先決條件，其中 r 指required（需要建好哪些東西），b指borrowed（需要借用哪些資源），c指consumed（需要消耗的資源）。
- p指執行該動作後會産生的東西
舉例來說，對于“生産一個神族的龍騎兵”（Produce Protoss Dragoon）這麼一個動作，而言
- 生産總共需要600幀，是以δ = 600
- 必須先有建有控制核（Cybernetics-Core）才能建造，是以r = {Cybernetics-Core}
- 建造過程中需使用兵營，“借用”兵營的生産力一小段時間，是以b = {Gateway}
- 建造它需要消耗125個晶體礦，50個鈾礦，還算2個人口，是以c = {125 minerals, 50 gas, 2 supply}
- 動作執行完畢會産生一個龍騎士，是以p = {1 Dragoon}
玩法的抽象
在實際的遊戲中，建造過程和收集資源的過程都較難用數學去表達，因為建造和收集過程中，需要派遣勞工，讓勞工走到目的地，然後建造或收集，對于收集，勞工還需要把礦物拿回基地，這個過程會涉及資源的位置、地圖尋路，比較複雜。是以，做了一些适當的簡化，如下所示。
- 對于晶體礦收集，固定設定為每個勞工每幀收集0.045個
- 對于油礦收集，固定設定為每個勞工每幀收集0.07個
- 對于每個建築，預設加上4秒的建造時間，以模拟勞工走路花費的時間
狀态轉換
對于遊戲的狀态轉換，做出如下三種抽象：
- S′←Sim(S,δ) ，模拟從狀态S開始，沒有操作的經過δ時間，最後變為S'狀态
- δ←When(S,R) ，目前狀态為S，它需要R資源，該抽象計算出達成該資源所需的時間δ，例如有3個勞工在收集礦石，它需要多少時間才滿足建一個兵營
- S′←Do(S,a) ，目前狀态為S，且執行動作a的條件已滿足，執行動作a，使狀态變為S'
綜合起來即可得到狀态轉換函數 S′=Do(Sim(S,When(S,a)),a)，既想執行動作a，先計算滿足條件所需的時間，然後等待條件滿足，最後執行。
搜尋算法
在做好抽象定義之後，即可從目前遊戲狀态（S）開始，找出達成建造目标（G）的方法，具體是通過深度優先搜尋（depth-first recursive search），遞歸周遊目前狀态下可能的發生的動作，具體算法如下：
- 2-4行：其中的TimeElapsed是為算法效率考慮，限制它執行的時間，以适應遊戲的實時性；
- 9-17行：遞歸搜尋的過程，周遊S下可能執行的動作（while S has more children do），針對該動作形成的新局面S'，遞歸調用（ DFBB(S') ）。其中h←eval(S')是啟發式評估的過程，目的是加快搜尋速度，隻對S'+h<b的狀态去做深度搜尋，忽略其他，這裡就展現了算法名字裡的Branch&Bound（分支界限）。其中的b是作為一個判斷的界限，它綜合兩層計算，其一，星際争霸的科技樹發展是有規律的，如果與預知的經驗相去甚遠，就不再進行搜尋；其二，根據所需的資源消耗來做條件，如果場面的資源不夠，說明難以執行到理想情況，無需繼續搜尋。
- 5-7行：當周遊到目标局面G，即傳回最優的動作序列bestSolution。
這麼做法還有個問題，實際遊戲是多個動作并行處理，不過要做到并行處理動作的計算量很大，算法中采用串行來模拟并行，公式如下所示，即将a和b動作的并行視為有順序的執行。
Do(S,a+b)=Do(Do(S,a),b)
UAlbertaBot将以上算法封裝成一個成為BOSS的子系統，上層可以直接調用，輸入目前局勢和目标，它會傳回搜尋到的動作序列。
文章會分如下幾篇
- 架構和規則，宏觀介紹UAlbertaBot的原理
- 建造順序搜尋，介紹使用深度搜尋算法去找到最優建造順序的方法
- 戰鬥模拟評估，介紹模拟隊伍作戰評估能否獲勝的方法
- starterbot，一個最簡單的機器人，從中了解最基礎星際AI的寫法
- 政策制定，政策制定部分的代碼分析
- 建造實作，生産、建造相關系統的代碼分析
- 戰鬥實作，戰鬥相關代碼分析
- 尋路算法，地圖相關代碼的分析
下面又到廣而告之的時間啦，《Unity3D網絡遊戲實戰》是一本很好的書籍，作者花費很多時間編寫的呢，教你從零開始開發一款多人對戰遊戲，很有特色。網上其他資料大多教怎麼做單機遊戲，而這本書會說明制作網絡遊戲的方法，很值得閱讀。