一直以來，星際争霸等政策遊戲AI都被視為遊戲AI中實作難度最高的。其一，遊戲規則較複雜，包含建造、資源收集、兵種配合、戰鬥微操很多内容；其二，玩家需要運用不同的政策對抗不同敵人，政策很複雜。
星際争霸遊戲畫面
為什麼寫這篇文章
寫此篇文章主要有以下幾點考量。其一，傳統遊戲AI基于規則實作，有的使用狀态機、有的使用行為樹、甚至有些運用搜尋算法來尋找最優的動作，政策遊戲往往綜合運用多種技術，有一定的研究價值；其二，盡管基于規則的傳統AI沒法和人類對抗，但它涉及的程式抽象思想值得研究；其三，我之前寫過幾個AI相關的材料，一個是課程《各類型遊戲人工智能算法》，它主要偏重于不同類型遊戲AI的綜述，另一個課程 《直覺了解AI博弈原理》主要介紹象棋、圍棋、王者榮耀的AI實作，更偏重于強化學習方法的演進，兩者中間還缺乏一個綜合執行個體，而星際争霸機器人UAlbertaBot剛好可以填補這一空白。本文主要參考UAlbertaBot的源碼、Wiki，以及相關的幾篇論文，我們并不去關心程式怎樣安裝和運作，而是關注它的設計和原理。
UAlbertaBot是什麼
UAlbertaBot是一套開源的星際争霸AI，該程式自2010年開始參加各種星際AI的比賽，并且赢得2013年AIIDE星際争霸AI比賽的冠軍。它的作者是David Churchill，紐芬蘭紀念大學的計算機助理教授。UAlbertaBot的開源位址如下：
https://github.com/davechurchill/ualbertabot/
在2018年以前，使用強化學習方法的AI尚未成熟，UAlbertaBot等星際争霸機器人成為遊戲AI競技的代表。盡管在2018年以後強化學習AI展現出很強的能力，但強化學習AI訓練難度大且難以用邏輯表示它的行為，遊戲産業依然廣泛的使用傳統AI。
文章會分如下幾篇
- 架構和規則，宏觀介紹UAlbertaBot的原理
- 建造順序搜尋，介紹使用深度搜尋算法去找到最優建造順序的方法
- 戰鬥模拟評估，介紹模拟隊伍作戰評估能否獲勝的方法
- starterbot，一個最簡單的機器人，從中了解最基礎星際AI的寫法
- 政策制定，政策制定部分的代碼分析
- 建造實作，生産、建造相關系統的代碼分析
- 戰鬥實作，戰鬥相關代碼分析
- 尋路算法，地圖相關代碼的分析
代碼結構
UAlbertaBot的代碼使用C++編寫，代碼架構層次分明，整體如下圖所示。我們可以先有個大概印象，其中CombatCommander負責兵種戰鬥的邏輯、WorkerManager負責勞工的邏輯、ProductionManager負責建造邏輯、StrategyManager負責整體政策，整體還是比較明晰。
代碼層次結構
源碼檔案
程式從main開始運作，沿着UAIBertaBot、GameCommander逐層調用，最後分發到WorkerManager、ProductionManager等子系統，main、UAIBertaBot、GameCommander它們并不包含具體邏輯，僅僅是一層層的往下調用。
頂部的代碼結構
各個子系統負責對應的邏輯實作，它們的主要功能如下。
各個子系統
ProductionManager 生産管理器
- 在程式中，政策管理器（StrategyManager）會負責選擇合适的政策，而針對不同的政策需要生産不同的機關，StrategyManager會生成一個建造目标（build order goal ），包含要生産的内容，由ProductionManager去執行。
- 由于建造單元有依賴關系，也會消耗資源，必須合理地安排生産的順序。ProductionManager會調用StarcraftBuildOrderSearch進行搜尋，找到最合理的建造順序（後續還會詳細介紹搜尋的過程），形成建造清單（build order）
- 按照優先級，建造隊列（build order）裡的機關。
- ProductionManager會調用BuildingManager來實作具體的建造過程，包括配置設定勞工去建造、建造過程中勞工被打死需要重新配置設定勞工、管理建築的狀态（準備建、已配置設定勞工、建造中、建造完成）。
CombatCommander 戰鬥管理器
- 如果敵人來到我方占領的區域，建立防禦隊伍（defense Squad）去防禦。
- 如果存在攻擊機關，按照如下順序進行攻擊，a：已知的敵人基地；b：可見的敵人單元；c：已知的敵人建築；d：進行探索，直到找到攻擊目标。
- CombatCommander會根據需要建立隊伍，如需要防禦時建立防禦隊伍，攻擊時建立攻擊隊伍，配置設定單元到各個隊伍（Squads），并且管理它們。其中Squads子產品會調用CombatSimulation進行戰鬥模拟（後續也會詳細說明），如果預估會勝利，則訓示隊伍去攻擊敵人；如果預估會失敗，則撤退。Squads會調用各種MicroManager進行微觀動作的操控。
- MicroManager是一個基類，派生出MeleeManager（混戰）、RangedManager（範圍攻擊）、DetectorManager（偵查管理器），不同子類會實作一種特定行為的控制。
- 在合适時間，設定一個勞工去偵查，以探索地圖區域。CombatCommander會調用scoutManager，負責偵查邏輯，a：具體邏輯是尋找敵人基地并往敵人基地的方向行進；b：如果在敵人基地内遇到敵方勞工則攻擊它；c：如果敵方勞工反擊，則撤退。
WorkerManager 勞工管理器
- 如果有空閑勞工，配置設定他們去收集礦産
- 為每個提煉廠配置設定3個勞工
- 如果發現新的油礦，重新配置設定勞工去挖礦
- 如果需要建造，配置設定一些勞工去建造
其他系統諸如InformationManager會記錄已發現的敵人資訊，MapGrid和MapTool會實作尋路輔助的功能。
下面又到廣而告之的時間啦，如果你想學習開發遊戲，不妨看一看筆者寫的《Unity3D網絡遊戲實戰》和《百萬線上：大型遊戲服務端開發》，畢竟也是花費多年時間編寫，相信對大家了解遊戲開發技術會有一些幫助。
作者的一系列遊戲技術總結