# Puppet Search

> [Puppet Search: Enhancing Scripted Behavior by Look-Ahead Search with Applications to Real-Time Strategy Games](https://pdfs.semanticscholar.org/3902/521ee719f296423c33e79f99949af1c7445b.pdf)

实时策略游戏已经被证明非常适合标准的对抗树搜索技术。最近，出现了几种解决它们复杂性的方法，它们使用游戏状态或移动抽象，或者两者兼有。不幸的是，支持性实验要么局限于更简单的即时战略环境(μRTS，SparCraft)，要么缺乏对最先进的游戏代理的测试。

在这里，我们提出了Puppet Search，一种基于脚本的新的对抗性搜索框架，可以将选择点暴露给前瞻搜索程序。为其选择点选择script和decision的组合表示接下来要应用的动作。这种移动可以在实际游戏中执行，从而让脚本运行，或者在游戏状态的抽象表示中执行，该抽象表示可以被敌对搜索算法使用。Puppet Search返回代理在特定时间内要执行的脚本和选项的主要变化。我们在一个完整的星际争霸机器人中实现了这个算法。实验表明，它与2014年亚投行星际争霸赛中最先进的机器人对战时使用的所有独立脚本都匹配或优于它们。

## 方法

### Puppet ABCD Search

算法1展示了基于ABCD(考虑持续时间的[α-β搜索](https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning))搜索的一个变种，它本身是α-β搜索对同时和持续动作的适应。为了减少求解多步同时移动游戏的计算复杂性，ABCD搜索基于移动序列化策略实现近似，其指定下一个（第3行）和之后的对手的玩家。他们所讨论的策略包括以1-2-2-1的方式随机，交替和交替，以平衡第一或第二玩家的优势。

为了适应我们假设的同步移动游戏的Puppet Search搜索框架，我们修改了ABCD搜索，它考虑了Puppet移动序列，并考虑到在任何时间点两个玩家都执行Puppet 移动。第9行，最大搜索深度假设为偶数，这允许两个玩家选择一个Puppet 向前移动。在第4行，生成当前玩家的移动。它们包含选择点决策以及移动它的玩家。之后，如果从上一个递归调用(第5行)没有传递任何移动，当前玩家的 $$m\_{2}$$ 将被传递到下一个PUPPETABCD调用在第6行。否则，两个玩家的动作都将应用到状态(第9行)。应用移动的确切机制是特定于域的。我们稍后将给出一个特定于RTS游戏的示例（算法2）。

![](https://2281160879-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LaNHyhKoX7GdL4Ytevq%2F-Lbb7XqaQAPPtrsl7lzc%2F-LbbFo23lS0xJ3oF5n9j%2Fimage.png?alt=media\&token=7e10b146-fb55-4f80-adec-2d70b8a4bcf1)

### Puppet Search in RTS Games

本节描述了在星际争霸游戏代理中上层搜索的实现。星际争霸是一种大众游戏，玩家可以同时向他们控制的所有个人游戏单元发出动作，每秒几次。此外，有些动作并不是偶然的——它们需要一些时间来完成，它们的效果有时是随机的，只有游戏状态的局部视图可供玩家使用。最后，游戏区域的大小、可用单元的数量以及在任何给定时间可能采取的行动的数量都比大多数棋盘游戏大几个数量级。

我们的实现通过调整标准人工智能算法来解决其中的一些问题，例如在同步移动设置中序列化移动，或者忽略一些最终的问题，例如通过假设确定的动作效果和完美的信息。此外，由于软件限制，例如在搜索过程中无法使用引擎来转发世界，以及没有合适的模拟程序，必须进行一些简化。

#### Concurrent Actions and Script Combinations

星际争霸2的很多动作是同时进行的，为了使其符合“Puppet Search”框架，我们可以组合所有这些脚本并定义单个选择点，其可用（并发）Puppet 移动是由各个脚本的puppet 移动的向量组成。例如，一个并发的puppet 移动可能是低级puppet 移动的一对，例如“在选择单元组A的脚本的选项2和选项组B的选择点上选项3”，这可能意味着“现在A主攻基地的并且B建立一个二级基地，当游戏达到第7000帧时。

在另一个场景中，我们可以访问多个脚本来实现不同的完整游戏策略。例如，我们可以将所有参与最近星际争霸人工智能竞赛的程序视为脚本，并尝试将它们结合到一个基于超级搜索理念的星际争霸玩家中，方法是识别各个策略中的弱点，提出适当的选择点，然后在顶部添加一个选择点，让人工智能系统可以选择在给定的帧之外或者在某些游戏事件发生之前继续执行其中一个脚本。

#### State Representation and Move Execution

为了实现模拟前向得到得到未来的结果，我们使用Build Order Search System（BOSS）前向经济和SparCraft前向战斗。因为同时推进经济、团队和战斗既棘手又计算成本高，所以我们决定用游戏时间最长的动作来决定速度:推进经济，如算法2所示。

每次我们需要应用移动时，脚本都会运行，并返回要构建的有序建筑物列表（第3,4行）。在第8行，状态被转发，直到满足列表中下一个建筑的先决条件(资源和其他建筑)。然后，该建筑被添加到BOSS 建造队列(第9行)，以便下次经济受到保护时，其建设将开始。然后，在第10行，小队移动和战斗被转发到相同数量的帧外。然后将查询脚本以检查它们是否已经到达未定的选择点，在这种情况下转发停止。这个循环一直持续到构建列表变空、游戏结束或者达到给定的帧限制。为简单起见，我们在第2行将该帧限制显示为常数。

![](https://2281160879-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LaNHyhKoX7GdL4Ytevq%2F-Lbb7XqaQAPPtrsl7lzc%2F-LbbPckvwM1WgpZ6scHw%2Fimage.png?alt=media\&token=c032854c-2e1c-4d1b-b009-351dc926c14b)

#### Search

由于具有用于转发单位移动和战斗的不完美模型，我们决定不反对使用MCTS，其将在playout阶段严重依赖它。 我们选择使用修改后的Alpha-Beta搜索。

#### State Evaluation

我们评估了一些方法，第一个是星际争霸根据建造它所需要的资源给每个单位分配的分数，为了我们的目的，这个分数高估了建筑物。第二个是LTD2(“生命时间-伤害-2”)，这是一个单位在其一生中所能造成的平均伤害的量度，它根本不重视非攻击性单位和建筑，甚至对于战斗单位来说，它也不考虑范围或速度等属性，或者隐形等特殊能力。为了尝试手工构建一个评估函数来解决这些不足，我们决定使用一个基于anchester’s attrition laws的模型。它自动训练单位的评估功能，调整到每个对手。它仍然只考虑战斗单位，所以下一步显而易见的是使用一个函数来评估整个游戏状态，如(埃里克森和布鲁2014)所述。

#### Hash Tables

因为移动执行的成本很高，所以我们使用散列表来存储状态，通过散列用于到达该状态的移动序列来索引。它的工作原理类似于基于Zobrist散列的换位表(Zobrist 1970)，但是由于状态太大且代价太高，所以我们改为散列从根到当前状态的移动顺序。

## 实验

实验使用12个VirtualBox虚拟机（VM）进行，每个虚拟机配备2个运行速度为2.5GHz的IntelXeon E5420 CPU核心和2GB RAM。客户操作系统是Microsoft Windows XPSP3。The StarCraft AI Tournament Manager用来协调比赛。默认的锦标赛超时策略已被更改，允许我们的机器人在构建队列每2000帧用完时花费6秒的搜索时间。

![](https://2281160879-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LaNHyhKoX7GdL4Ytevq%2F-Lbejs3ldFv3nRFGKkdY%2F-Lbf9lXRo5TEaCUBY-dB%2Fimage.png?alt=media\&token=60ee67d6-a83c-4f5c-a93f-00a8e7379666)

![](https://2281160879-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LaNHyhKoX7GdL4Ytevq%2F-Lbejs3ldFv3nRFGKkdY%2F-Lbf9nDL0f2dhdtuPS2_%2Fimage.png?alt=media\&token=5b4be972-38ed-4cf3-9661-48cf0a87d4ba)

![](https://2281160879-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LaNHyhKoX7GdL4Ytevq%2F-Lbejs3ldFv3nRFGKkdY%2F-Lbf9pUhK1HIeEfi7iHp%2Fimage.png?alt=media\&token=b65fb4fe-85a4-49fb-90ed-87162173afd4)

![](https://2281160879-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LaNHyhKoX7GdL4Ytevq%2F-Lbejs3ldFv3nRFGKkdY%2F-Lbf9quhyNBfDJQAJwdi%2Fimage.png?alt=media\&token=be1db508-301a-42f3-a2fb-697c25971fc5)