本文内容紧张结合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网络游戏实战》是一本很好的书本，作者花费很多韶光编写的呢，教你从零开始开拓一款多人对战游戏，很有特色。网上其他资料大多教怎么做单机游戏，而这本书会解释制作网络游戏的方法，很值得阅读。
