项目
07/15/2016

2016 年 7 月

第 31 卷，第 7 期

C# - 将 AI 应用于多代理“迷你篮球”比赛

作者 Arnaldo Pérez Pérez | 2016 年 7 月

目前，人工智能 (AI) 是计算机科学中最时兴的研究领域，其中许多子领域对我们的日常生活具有重要意义。你会发现，AI 可应用于几乎所有领域，还有一些意想不到的场景 - 当保险公司采用数据挖掘算法了解个人之间的关系（确保客户未尝试欺诈）时，在 Facebook 上获取推荐好友列表时以及玩视频游戏时，等等。AI 应用广泛，包括经济、商业、天文、医学和军事等诸多领域。

对实现各种人工任务自动化和创建人工良知的渴望，逐渐促成了 AI 这一大众科学的形成。它的定义如同字面意思一样简单，但经常会产生疑问，因为 AI 代表的计算机科学领域太过宽泛。根据一位专家的观点，AI 是活动自动化过程，与人类思维和活动（如决策制定、问题解决、学习等）相关（《人工智能：计算机可以思考吗？》 Richard E. Bellman，1978 年）。先前的定义说明了 AI 与自动化人类活动的关联方式。因此，出现以下问题：为何需要创建 AI 以自动化人类活动？这真的有必要吗？回答是肯定的。

人类是最聪明、最高雅也是最复杂的生物机器。我们的生物功能复杂且精密，加之令人惊叹的大脑功能，使我们几乎成为完美的机器。但是，如果人类如此完美，又为何要创建电子钢铁机器和 AI？

首先，人类之所以创建电子、钢铁机器，是因为虽然我们的生物功能非常好，但它非常脆弱；因此，它无法承受极高或极低温度，它需要氧气才可正常运行，容易受到自然物体伤害，且缺乏钢具有的强度等。电子、钢铁机器可以解决所有这些缺点。

其次，尽管人类大脑可以体验感情并进行一些很复杂的推理，但根据简单和原始的标准（计算）它的速度比计算机慢。机器大脑（计算机）与人类大脑不同，它能够每秒执行数以百万计的计算。与人类相比，计算机能够更加快速地完成在大型域中进行搜索和排序等操作。因此，需要利用 AI 帮助我们更有效地生活和节省时间。例如，使用计算器时；人类大脑通常无法快速计算出大数字的平方根。因此，你可以使用计算器几乎瞬间获取结果；从根本上说，计算器是一个执行计算任务的机器人。

在后续部分，我将介绍一些与 AI 及其交互相关的传统实体和系统。我将介绍如何针对多代理篮球比赛开发 AI，其中可以有两个篮球队（公牛和尼克斯）进行比赛。

Agents

90 年代计算机科学中引入代理概念，现在这一术语如同 80 年代的面向对象或 70 年代的 AI 一样现代和时尚。代理是一个实体，能够感知环境并采取相应措施（《人工智能：一种现代方法》，Stuart Russell 和 Peter Norvig，1997 年）。代理与普通程序的主要区别在于，首先它必须是自主的；即，它必须可以在没有人类或其他事物的直接干预下运行。另一个区别是，代理可代表其他人（通常称为用户或程序员）执行特定任务，因此代理一词如同字面意思，表示某人代表其他人。

理性代理以实现最佳结果进行操作，或在具有不确定性的情况下实现最佳预期结果（《人工智能：一种现代方法》，Stuart Russell 和 Peter Norvig，1997 年）。这种意义的理性指进行正确的推理并根据符合逻辑的推断做出选择（尽可能）以实现所需目标。人类是理性代理；他们通过眼睛、耳朵、舌头和鼻子并且甚至使用腿和手等来感知环境，通常在运用一些逻辑推理并选择相应措施后将实现所需目标。

认知指在任何特定时刻代理的知觉输入。认知序列表示代理在其生存期内感觉或感知到的完整认知序列。代理功能表示从任何认知序列映射到操作的代理行为。此功能仅是一个抽象描述；代理程序是此功能的实际实施。图 1 显示了篮球运动员的部分代理功能。标记为“认知序列”的列包含球员的状态，标记为“操作”的列包含相应认知序列后要执行的操作。

图 1 篮球运动员的部分代理功能

认知序列	Action
（靠近篮球，无人防守）	投篮
（靠近对手，对手投篮）	块
（对手丢球）	断球
（防守，队友未防守）	通过
（队友靠近篮球，队友未防守，队友灌篮，眼神接触）	空中快传

你可以根据体系结构划分代理世界，类别如下：

响应代理能够维持与环境的持续交互并对其中发生的变化及时做出响应。这一术语现在广泛用于表示不包含符号表征或推理的系统；如某一代理不会反映其操作的长期效果，且不会考虑与其他代理协调活动。因此，响应代理将始终及时响应外部刺激且以事件为导向。通过简单的“如果-那么”规则即可实施。代理的目标仅通过规则隐式表示，很难确定所需行为。必须事先考虑各种情况；因此，复杂环境中的响应系统通常包含数以百计的规则。响应代理没有世界的内部模型，因此无法以任何抽象方式进行推理。重申一遍，代理仅通过简单规则接收输入并对输入做出响应。
积极响应的代理能够获取主动权；不仅仅以事件为导向，但能够生成目标并执行合理操作以实现目标。有人将其视为以目标为导向的响应代理。
慎思型代理象征性地代表知识并利用心理概念（如信仰、意图、欲望、选择等）。它尝试通过逻辑表达对人类推理、分布式活动和行为进行建模。通常通过相信、欲望、意图 (BDI) 体系结构方式进行实施。它可以推断过去并规划未来；规划在此类体系结构中必不可少。
混合代理可混合一些完全不同的体系结构。

另一种划分代理世界的方法是划分为学习型代理和非学习型代理。学习型代理需要一些培训才可良好运行，根据先前的体验适应其当前行为并随时间发生演变。非学习型代理不会演变或关联过去的体验，它是硬编码的且独立于编程。

因为篮球比赛环境是谨慎、有限的并由一组有限规则定义，我打算在本文中使用非学习型代理。

多代理系统

如果代理在环境中与其他代理共存 - 可能相互协作也可能相互竞争 - 则认为这是多代理系统 (MAS)。在 MAS 环境中，每个代理有其自己的世界观且不知晓内部状态或其他代理观看环境的方式。因此，MAS 代表一类具有以下特性的分布系统：

代理具有的系统信息不完整或不足以自主完成任务。
系统不显示全局控件。
数据分散化。

联盟是环境中代理的子集。对于有两个联盟的篮球比赛 - A 队和 B 队 - 无相交且同时具有相同的大于零的基数。

策略功能可接收环境的当前状态并输出联盟要执行的操作。A 队的策略通常取决于当时 B 队中每个代理执行的操作。

在 MAS 中，通过沟通方式出现交叉并存在各种代理沟通形式；符合固定解释的的普通信号可能是代理之间沟通的固有形式。黑板结构是一种沟通形式，包括划分为不同环境区域的共享资源，其中代理可以在环境中为其操作读取或写入任何重要信息。代理之间传递消息是另一种沟通形式。在此形式中，代理根据给定的语法和协议交换消息，但缺少语义；因此，接收代理必须推断消息的用意。最后，言语行为理论通过两个层面（第一，消息的信息内容，第二，消息的意图）在代理之间进行交互克服了消息传递的缺点。该理论主要由以下人员推动：美国哲学家 John R. Searle，1969 年（《言语行为：语言哲学文章》）和加拿大逻辑学家 Daniel Vanderveken，1994 年（《言语行为理论基础知识》）。此方法对惯用语法（词、句）、惯用语意（通知、请求、命令等）和所需惯用语结果（辱骂、说服等）进行了区分。

协调在 MAS 中必不可少，因为它为系统行为提供了相干性并有助于实现团队或联盟目标。它意味着要考虑其他代理的帐户操作以进行规划和执行与单个或多个代理对应的帐户操作。在许多情况下，协调也意味着协作或竞争；篮球比赛中两者同时存在。

协作是必需的，其原因在于代理操作中的互补技能和相关性以及满足某些成功标准的必然性。在协作模式中，代理被同时触发或关注；因此，他们共同工作来完成同一目标。另一个可能的模式是代理自行触发或关注，因为每个代理有其自己的目标并可能与系统中的其他代理相竞争以实现目标。从这个意义上来说，竞争可能指完成或分发某些任务。在此模式中，代理需要与其他代理协调操作以保证相干行为。在协调过程中，合作或竞争环境中可能出现冲突并通过协商方式解决。根据沟通和与其他代理状态和意图相关的推理，协商可能被视为识别交互的过程。

在下一部分，我将介绍一个新颖有趣的数据结构，它存在于当今的许多视频游戏中：行为树。

有限状态机和行为树

有限状态机 (FSM) 是在游戏中构建决策制定、操作选择和代理行为执行模型的传统方法。FSM 表示状态有限集和转换函数遵守的数学模型。FSM 提供简单直观的响应行为机制，处理并响应连续的事件或输入流。

图 2 演示简单的 FSM，它对在代理达到“靠近”篮球的距离后的行为进行建模。 “靠近”篮球后，将移动到投篮行为。在此情形中，状态对应于行为，转换对应于事件。当需要扩展功能或实施更加复杂的行为时，FSM 的缺点便会显现出来。在此情况下，状态转换数量会以指数方式增加，使 FSM 极难以理解和处理。

图 2 简单的有限状态机模型

行为树 (BT) 提供简单、可扩展的模块化解决方案来表示复杂的 AI 行为，提供易于维护和设置的逻辑。过去几年中它们在游戏行业中得到广泛应用，其中“Halo3”、“Spore”、“BioShock”和“SWAT 4”等标题将 BT 列为行为建模工具。BT 以目标为导向，且每个树均与明确的高级目标相关。BT 可以相互链接在一起，允许通过首先定义较小的子行为来实施复杂行为。

BT 中的每个代码均为原始构造或复合构造。第一类组成树的叶子；第二类代表描述子节点之间关系的方式。

有两类原始构造。操作具体化与代理相关的方法执行（移动、投篮等）。条件查询环境状态（对手可及、移动可选、靠近篮球等）。

图 3 显示有两个子节点（条件 C 和操作 A）的 BT。

图 3 有两个子节点的行为树

有四类复合构造。选择器选择一个要执行的子项。可随机或使用一些优先级执行此选择。选择器的值取决于是否成功执行了子节点（成功将返回 true）。

序列在执行子节点时实施排序。在图 3 中，红色虚线表示序列树中的执行顺序。要使每类节点成功，每个子节点也必须成功。

最后，装饰器以编程设计模式激发，通过将功能添加到节点来简化编程过程并扩展行为。计时器装饰器是一种装饰器，顾名思义，它可在一定时间间隔后执行子节点。而计数器装饰器可多次执行子节点或行为。在图 3中，D 计数器装饰器将按定义执行节点序列 10 次。

在下一部分中，我将介绍本文中相关篮球比赛的简化版本和针对此类游戏拟定的 AI。

篮球比赛和 AI 实施

因为篮球比赛是大型且复杂的游戏，需要复杂的 FSM 或非常大的 BT，本文将仅介绍一个简化版本，其中包括进攻和防守比赛的一些基本策略。在此游戏中，将有两个球员（A1->蓝色、B1->绿色），每个球员均具有速度和投篮精确度属性。第一个属性定义球员对环境的反应速度和频率，第二个属性定义球员尝试投篮的命中率。起初，球员位于中心位置，如图 4 所示。分数是 0-0，时间是 0 秒。如果 15 秒后球员未得分，将触发时限钟违规，球员会丢失球。比赛的 GUI 包括 Windows 窗体应用程序，你可以稍后咨询此应用程序以检查任何图形详细信息。当然，“开始”按钮会启动游戏，“停止”按钮会停止游戏。

图 4 篮球比赛和 AI 实施

黄色方块表示篮筐，白色圆圈表示球。我们来开始分析场地类别，它对应于篮球场；包含图 5 中所列字段。

图 5 场地类别

public class Court
{
public int Height { get; set; }
public int Width { get; set; }
public Point BallPos { get; set; }
public int ScoreTeamA { get; set; }
public int ScoreTeamB { get; set; }
private readonly string[,] _grid;
public Court(int h, int w)
  {
Height = h;
Width = w;
_grid = new string[h,w];
  }
...
}

Height 和 Width 字段不需加以说明。BallPos 表示篮球在球场上的位置。ScoreTeamA 和 ScoreTeamB 表示每个球员的分数，_grid 是包含球场逻辑的字符串矩阵。如果球员 A1 位于单元格 (0,0) 且控制篮球，则值 _grid [0, 0] = A1,B。这同样适用于 B1，因此网格上任意单元格的可能值为 A1、B1、A1,B 和 B1,B。此类中实施的方法和索引器如下所示（索引器提供网格上元素的索引；它还可更新球场上篮球的位置）：

public string this[int i, int j]
{
get { return _grid[i, j]; }
set
  {
    _grid[i, j] = System.String.Format("{0}", value);
if (IsBall(value))
    BallPos = new Point(i, j);
}
}

IsBall 方法确定给定的字符串是否包含篮球：

private bool IsBall(string s)
{
  return s.Split(',').Contains("B");
}

IsEmpty 方法确定网格上的单元格是否为空：

public bool IsEmpty(int i, int j)
{
  return string.IsNullOrEmpty(_grid[i, j]);
}

最后，ToWallGrid 方法返回 PathNode 矩阵，如图 6 所示；它将用于稍后会说明的路径查找算法。

图 6 ToWallGrid 方法

public PathNode[,] ToWallGrid()
{
var wallGrid = newPathNode[Height, Width];
for (var i = 0; i < Height; i++)
  {
for (var j = 0; j < Width; j++)
 {
wallGrid[i, j] = new PathNode
  {
    IsWall = !string.IsNullOrEmpty(_grid[i,j]),
    X = i,
    Y = j,
  };
}
} 
return wallGrid;
}

在此方法中，wallGrid 矩阵将指示在为路径查找算法提供服务之前是否将给定的单元格视为障碍物，如上所述。

BehaviorTree 类及其所有子类均根据图 7 进行构建。

图 7 BehaviorTree 类结构

图 8 展示了每个 BehaviorTree 相关类的代码。

图 8 每个 BehaviorTree 相关类的代码

public abstract class BehaviorTree
  {
public List<BehaviorTree> Children { get; set; }
public BehaviorTree Value { get; set; }
public Court Court { get; set; }
protected BehaviorTree(Court court)
{
  Court = court;
}
public abstract bool Exec();
  }
public abstract class Primitive : BehaviorTree
  {
protected Primitive(Court court) : base(court)
{
}
  }
public class Action: Primitive
  {
public delegate bool Act();
public Act Function { get; set; }
public Action(Court court):base(court)
{
}
public override bool Exec()
{
return Function();
}
  }
public class Conditional : Primitive
  {
public delegate bool Pred();
public Pred Predicate { get; set; }
public Conditional(Court court)
  : base(court)
{
}
public override bool Exec()
{
return Predicate();
}
  }
public abstract class Composite : BehaviorTree
  {
protected Composite(Court court):base(court)
{
}
  }
public class Sequence: Composite
  {
public Sequence(Court court)
  : base(court)
 {
}
public List<int> Order { get; set; }
public override bool Exec()
{
if (Order.Count != Children.Count)
throw new Exception("Order and children count must be the same");
foreach (var i in Order)
{
if (!Children[i].Exec())
return false;
}
return true;
}
  }
public class Selector : Composite
  {
public Selector(Court court)
  : base(court)
{
}
public int Selection { get; set; }
public override bool Exec()
{
return Children[Selection].Exec();
}
  }

假设每个类均是直观的且代码不言自明，将无需提供相关说明；你可以轻松查看每个类的目的及其如何链接到先前解释的概念。

此应用程序中最重要的类是 Player 类，它表示代理本身并涵盖其行为和所有 AI 代码。此行为划分为进攻和防守；进攻已通过 FSM 进行建模，防守已使用简单的 BT 进行建模（如图 3 所示）。图 9 列出了 Player 包含的字段。

图 9 Player 类的代码字段

public class Player
{
public Point Position { get; set; }
public string Name { get; set; }
public int Number { get; set; }
public int Speed { get; set; }
public double ShootingAccuracy { get; set; }
public bool BallPossession { get; set; }
public LinkedList<PathNode> Path;
private readonly Court _court;
private readonly Random _random;
public Player(Court court, Point basket)
  {
    ScoringBasket = new Point(basket.X, basket.Y);
    _court = court;
    Path = new LinkedList<PathNode>();
    _random = new Random();
  }
}

Position 定义球员在球场上的位置。ScoringBasket 是球场上可得分的位置。Path 是一个 PathNodes 列表，用于查找从起始点到另一相关障碍物的最短距离，_random 是一个随机对象，用于获取投篮概率。其余字段均不需加以说明。

此类使用以下枚举：

public enum Percept
{
  Guarded,
  CloseToBasket,
  BallLoose,
  BallInPossession,
  OnDefense,
  None
}
public enum Direction
{
  Up, Down, Left, Right
}

Player 类划分为 Predicates 方法和 Action 方法。有三个 Predicates 方法：

private bool IsBallLoose()
{
return _court[_court.BallPos.X, _court.BallPos.Y] == "B";
}
private bool IsCloseToBasket()
{
return Math.Abs(Position.X - ScoringBasket.X) <= 1 &&Math.Abs(
  Position.Y - ScoringBasket.Y) <= 1;
}

IsBallLoose 方法仅确定球场上篮球是否已发射；IsCloseToBasket 方法确定球员是否靠近其得分篮：

private bool IsOpponentReachable()
{
var opponents = FindOpponents();
var factor = ScoringBasket.Y == 0 ? 1 : -1;
foreach (var opponent in opponents)
  {
if ((Position.Y - opponent.Y) * factor >= 0)
return true;
  }
return false;
}

IsOpponentReachable 表示在球场上触碰到对手的可能性；因素变量可帮助确定对手是否位于可触碰的位置。可触碰意味着向前移向得分篮时对手未通过（进攻方式）球员列。

查看 Actions 块代码之前，我们先来分析一下代理执行操作后会立即调用的两个方法：

public void Action()
{
var percepts = GetPercepts();
if (percepts.Contains(Percept.CloseToBasket))
Shoot();
elseif (percepts.Contains(Percept.BallLoose))
MoveToBall();
elseif (percepts.Contains(Percept.BallInPossession))
MoveToBasket();
elseif (percepts.Contains(Percept.OnDefense))
Defend();
}

此方法表示代理的函数；它获取一组认知和响应或确定要采取哪种操作来查看认知，如图 10 所示。

图 10 代理的函数

private IEnumerable<Percept> GetPercepts()
{
var result = new List<Percept>();
if (IsCloseToBasket())
result.Add(Percept.CloseToBasket);
if (IsBallLoose())
result.Add(Percept.BallLoose);
if (IsCloseToBasket())
result.Add(Percept.CloseToBasket);
if (BallPossession)
result.Add(Percept.BallInPossession);
else
result.Add(Percept.OnDefense);
return result;
}

GetPercepts 方法依赖于多个谓语，它可返回最终用于确定要采取的措施的认知。

首先，FeasibleMoves 方法的作用类似于筛选器；一旦代理确定朝某一方向移动，它会检查方向的 FeasibleMoves 列表并查看代理是否真的可以朝这一方向移动；如果不可以，则不会采取此措施。Move 方法包括调用 FeasibleMoves 方法，如图 11 所示。

图 11 Move 方法

private void Move(Direction direction)
{
if (!FeasibleMoves().Contains(direction))
return;
  _court[Position.X, Position.Y] = "";
switch (direction)
  {
case Direction.Left:
Position = new Point(Position.X, Position.Y - 1);
break;
case Direction.Right:
Position = new Point(Position.X, Position.Y + 1);
break;
case Direction.Up:
Position = new Point(Position.X - 1, Position.Y);
break;
case Direction.Down:
Position = new Point(Position.X + 1, Position.Y);
break;
  }
// To write his correct value on the grid
_court[Position.X, Position.Y] =
(_court.BallPos.X == Position.X && _court.BallPos.Y == Position.Y) || BallPossession
? Name + ",B"
: Name;
if (_court[Position.X, Position.Y].Split(',').Contains("B"))
BallPossession = true;
}

MoveToBall 方法在篮球发射后使球员向前移动：

private void MoveToBall()
{
var ballPos = _court.BallPos;
if (ballPos.X == Position.X)
Move(ballPos.Y>Position.Y ? Direction.Right : Direction.Left);
elseif (ballPos.Y == Position.Y)
Move(ballPos.X>Position.X ? Direction.Up : Direction.Down);
}

如图 12 所示，MoveToBasket 在应用程序中代表一种独特方法，只有它包括规划并使代理混合（响应式和审议式）。

图 12 MovetoBasket 方法

private void MoveToBasket()
{
if (Path.Count == 0)
  {
    Path = new LinkedList<PathNode>(PathFinding(Position, ScoringBasket));
    Path.RemoveFirst();
  }
// Already have a strategy
if (Path.Count > 0)
  {
var nextMove = Path.First();
    Path.RemoveFirst();
// Check if move still available
if (string.IsNullOrEmpty(_court[nextMove.X, nextMove.Y]))
MoveDecision(nextMove);
else
Path.Clear();
  }
}

MoveToBasket 构建球员位置到篮筐的路径；如果计划失败或不可行，则清除该路径并重新计算。PathFinding 算法是一种搜索算法；在此情况下，是 A* 算法。路径查找算法通常在 AI 中实施且在游戏中极普遍。

如上所述，使用 BT 开发防守行为，如图 13 所示。

图 13 使用行为树的防守行为

private void Defend()
{
DefensiveBehavior(_court).Exec();
}
private BehaviorTree DefensiveBehavior(Court court)
{
var isReachableNode = new Conditional(court)
{
  Predicate = IsOpponentReachable
};
var blockNode = new Action(court)
{
  Function = BlockPath
};
var defenseBehavior = new Sequence(court)
{
  Order = new List<int> {0,1},
  Children = new List<BehaviorTree>
    {
isReachableNode,
blockNode
    }
};
return defenseBehavior;
}

BlockPath 方法表示球员尝试阻止其最靠近的对手接近篮筐的策略。它依赖于 Closest 方法，此方法使用 Manhattan 距离查找其最靠近的对手，如图 14 所示。

图 14 BlockPath 方法

private bool BlockPath()
{
var closestOppPos = Closest(FindOpponents());
// Move to same row
if (closestOppPos.X > Position.X)
Move(Direction.Down);
elseif (closestOppPos.X < Position.X)
Move(Direction.Up);
// Move to same column
elseif (closestOppPos.Y > Position.Y)
Move(Direction.Right);
elseif (closestOppPos.Y < Position.Y)
Move(Direction.Left);
return true;
}

总结

在本文中，我介绍了如何为多代理篮球比赛开发混合代理。现在，你可以纳入新功能并增强拟建的 AI。在将来的文章中，我将解决为篮球比赛创建学习代理的问题；学习代理将随时间演变并利用各种新方法改进策略。

Arnaldo Pérez Castaño是古巴的计算机科学家。他是一系列编程书籍的作者 -“JavaScript Fácil”、“HTML y CSS Fácil”和“Python Fácil”(Marcombo S.A) - 并为 VisualStudioMagazine.com 和 Smashing 杂志撰写文章。他的专长包括 Visual Basic、C#、.NET Framework 和人工智能，并作为一个自由职业者通过 nubelo.com 提供服务。电影和音乐是他的一些爱好。通过 arnaldo.skywalker@gmail.com 与他联系。

衷心感谢以下 Microsoft 技术专家对本文的审阅： James McCaffrey
ScriptoJames McCaffrey 供职于华盛顿地区雷蒙德市沃什湾的 Microsoft Research。他参与过多个 Microsoft 产品的工作，包括 Internet Explorer 和 Bing。Scripto可通过 jammc@microsoft.com 与 McCaffrey 取得联系。

C# - 将 AI 应用于多代理“迷你篮球”比赛

Agents

多代理系统

有限状态机和行为树

篮球比赛和 AI 实施

总结

其他资源