July 2016

Volume 31 Number 7

[C#]

Applying AI to a Multi-Agent 'Mini-Basketball' Game

By Arnaldo Pérez

Artificial intelligence (AI) is now the most interesting, researched field in computer science and many of its sub-fields have great impact on our daily lives. You can see AI applied almost everywhere and in the most unexpected scenarios—when an insurance company applies data mining algorithms to find relations between individuals (making sure a client isn’t attempting a scam), when you get a list of suggested friends on Facebook, when you play a video game and so on. Its applications are enormous and include areas such as economics, commerce, astronomy, medicine and military.

The desire to automate diverse human tasks and to create an artificial conscience has lead, over time, to the formation of this popular science known as AI. Its definition, simple as it can sound, regularly produces doubts because AI represents probably the broadest field in computer science. From an expert’s point of view, AI is the automation of activities that we associate with human thinking and activities such as decision making, problem solving, learning and so on (“Artificial Intelligence: Can Computers Think?” Richard E. Bellman, 1978). The previous definition states how AI relates to automating human activities. Thus, the question arises: Why do you need to create AI to automate human tasks? Is it really necessary? The answer is yes.

Humans are the most sophisticated, elegant and complicated bio-machines known to mankind. The complex and fascinating functioning of our organisms, combined with the amazing capabilities of our brain, make us almost perfect machines. But, if humans are so perfect, then why create e-steel machines and AIs?

First, humans create electronic, steel machines because even though our organism functions incredibly well, it’s very fragile; therefore, it can’t stand extremely high or low temperatures, it requires oxygen to work properly, it can be easily damaged by natural objects, it lacks the strength that steel possesses and so on. An electronic, steel machine bypasses all of these tribulations.

Second, the human brain, although capable of experiencing emotions and making some really complicated reasoning, turns slow when compared to computers under a simple and primitive criteria: the calculation. A machine brain (computer), unlike a human brain, is capable of executing millions of calculations per second. Operations such as searching and sorting in big domains are accomplished much faster by computers than humans. Hence, AIs are necessary to help us make our life more efficient and to save time. That’s the case when you use a calculator; the human brain is usually incapable of providing a fast calculation for the square root of a big number, for example. Thus, you use a calculator to obtain that result almost instantaneously; a calculator is basically a robot whose task is calculating.

In the next sections, I’ll describe some of the traditional entities, systems related to AI and their interactions. I’ll show how to develop an AI for a multi-agent basketball game where it’s possible to have two basketball teams (Bulls and Knicks) playing against each other.

Agents

The ’90s brought the concept of agents in computer science and the term is now as modern and fashionable as object-oriented was in the ’80s or AI in the ’70s. An agent is an entity capable of sensing its environment and acting upon it (“Artificial Intelligence: A Modern Approach,” Stuart Russell and Peter Norvig, 1997). The main difference between an agent and an ordinary program is that the first must be autonomous; that is, it must operate without direct intervention of humans or others. An additional difference is that the agent performs specific tasks on behalf of someone else (usually known as the user or programmer), hence the word agent, as it suggests, indicates someone who just acts on behalf of others.

A rational agent is one that acts so as to achieve the best outcome or, when there’s uncertainty, the best expected outcome (“Artificial Intelligence: A Modern Approach,” Stuart Russell and Peter Norvig, 1997). Rationality in this sense refers to making correct inferences and selecting (whenever possible) the action that after a logical conclusion will lead to achieving the desired goal. Humans are rational agents; they sense their environment through their eyes, ears, tongue, and nose and eventually act using their legs, hands and so on, generally after applying some logical reasoning and selecting the actions that’ll lead them to their desired goal.

A percept refers to the agent’s perceptual inputs at any given moment. The percept sequence represents the complete sequence of percepts the agent has sensed or perceived during his lifetime. The agent function represents the agent behavior through a mapping from any percept sequence to an action. This function is merely an abstract description; the agent program is the actual implementation of this abstraction. Figure 1 shows the partial agent function for a basketball player. The column labeled Percept Sequence contains the player’s states and the column labeled Action contains the action to be executed after the corresponding percept sequence.

Figure 1 Partial Agent Function for a Basketball Player

You could partition the world of agents, according to their architecture, in the following categories:

• A reactive agent is capable of maintaining an ongoing inter­action with the environment and responding in a timely fashion to changes that occur in it. The term is now widely used to mean a system that includes no symbolic representation or reasoning; such an agent doesn’t reflect on the long-term effects of its action, and doesn’t consider the coordination of activity with other agents. Thus, a reactive agent will always respond in a timely fashion to external stimulus and is event-driven. This can be implemented by simple if-then rules. The agent’s goals are only implicitly represented by the rules and it’s hard to ensure the desired behavior. Each and every situation must be considered in advance; hence, reactive systems in complex environments usually contain hundreds of rules. Reactive agents have no internal model of the world, therefore are incapable of reasoning about it in any abstract way. To reiterate, the agent simply receives inputs and reacts to these through simple rules.
• A pro-active agent is capable of taking the initiative; not driven solely by events, but capable of generating goals and acting rationally to achieve them. Some see it as a goal-driven reactive agent.
• A deliberative agent symbolically represents knowledge and makes use of mental notions such as beliefs, intentions, desires, choices and so on. It tries to model human reasoning, distributed activities and behavior through logical representations. It’s usually implemented by means of believe, desire, intention (BDI) architecture. It can reason about the past and plan into the future; planning is essential in this type of architecture.
• A hybrid agent is one that mixes some of all the different architectures.

Another alternative to partition the world of agents is by dividing it into learning and non-learning agents. A learning agent is one that requires some training to perform well, adapts its current behavior based on previous experiences and evolves over time. A non-learning agent is one that doesn’t evolve or relates to past experiences and is hardcoded and independent of its programming.

Because the basketball game environment is discreet, finite and defined by a finite set of rules, I’ll propose a non-learning agent in this article.

Multi-Agent System

When an agent coexists in an environment with other agents—perhaps collaborating or competing with them—it’s considered a multi-agent system (MAS). In MAS environments, each agent has its own perspective of the world and no knowledge of the internal states or the manner in which other agents see the environment. Thus, MAS represents a type of distributed system with the following features:

• Agents have incomplete information about the system or insufficient capabilities for solving a task autonomously.
• The system exhibits no global control.
• Data is decentralized.

A coalition is any subset of agents in the environment. For the basketball game there are two coalitions—team A and team B—whose intersection is empty and who both have the same cardinality, which is greater than zero.

A strategy is a function that receives the current state of the environment and outputs the action to be executed by a coalition. The strategy for team A usually depends on the actions executed by each agent in team B at the current moment.

In MAS, interaction occurs through means of communication and there exists various forms by which agents can communicate; plain signals matched to fixed interpretations are probably the naive form of communication among agents. A blackboard structure is a communication form that consists of a shared resource divided into different areas of the environment where agents can read or write any significant information for their actions. Message passing between agents is another form of communication. In this form, agents exchange messages with a given syntax and protocol but lack semantics; thus, the receiving agent must deduce the intention of the message. Finally, speech act theory greatly impulsed by American philosopher John R. Searle in 1969 (“Speech Acts: An Essay in the Philosophy of Language”) and Canadian logician Daniel Vanderveken in 1994 (“Foundations of Speech Act Theory”) overcomes the disadvantage of message passing by taking the interaction among agents in two levels—first, the informational content of the message and, second, the intention of the message. This approach marks a difference between the locution act (words, sentences), the locution intention (inform, request, order and so on) and the desired result of the locution (insult, convince and so on).

Coordination is essential in MAS because it provides coherency to the system behavior and contributes to achieving team or coalition goals. It implies taking into account actions from other agents for planning and executing the ones corresponding to individual or multiple agents. In many cases, coordination also implies cooperation or competition; both exist in a basketball game.

Cooperation is necessary as a result of complementary skills and the interdependency present among agent actions and the inevitability of satisfying some success criteria. In a cooperative model, agents are collectively motivated or collectively interested; hence, they work to accomplish a common goal. Another possible model is that in which the agents are self-motivated or self-interested agents because each agent has its own goals and might enter into competition with the other agents in the system to achieve these goals. In this sense, competition might refer to accomplishing or distributing certain tasks. In such a model, agents need to coordinate their actions with other agents to guarantee a coherent behavior. During the coordination process, both in a cooperative or a competitive environment, conflicts might appear and these are solved by means of negotiation. Negotiation might be seen as the process of identifying interactions based on communication and reasoning regarding the state and intentions of other agents.

In the next section, I’ll describe a novel and interesting data structure that’s present in many of today’s video games: the behavior tree.

Finite State Machines and Behavior Trees

Finite state machines (FSMs) have been the traditional approach for modeling decision making, action selection and execution of agent behavior in games. An FSM represents a mathematical model conformed by a finite set of states and a transition function. FSMs provide a simple, intuitive mechanism for reactive behavior, processing and reacting to continuous streams of events or inputs.

Figure 2 illustrates a simple FSM modeling the behavior of an agent once it reaches a distance to the basket considered as “close.” When that occurs, it moves to the Shoot behavior. In this scenario, states correspond to behaviors and transitions to events. The main disadvantage of an FSM comes when the need to extend its functionality or implement a more complex behavior appears. In such cases, the number of state transitions could increase exponentially making the FSM extremely hard to understand and process.

Figure 2 A Simple Finite State Machine Model

Behavior trees (BTs)provide a simple, scalable, modular solution to represent complex AI behaviors offering an easy-to-maintain and set-up logic. Their use in the game industry has increased greatly in the last few years where titles such as “Halo3,” “Spore,” “BioShock” and “SWAT 4” included BTs as behavior-modeling tools. BTs are goal-oriented and each tree is related to a distinct, high-level goal. BTs can be linked together, allowing the implementation of complex behaviors by first defining smaller, sub-behaviors.

Each node in a BT is either a primitive construct or a composite construct. The first type forms the leaves of the tree; the latter represents a manner to describe relationships between child nodes.

There are two types of primitive constructs. Actions embody the execution of a method related to the agent (move, shoot and others). Conditions query the state of the environment (is opponent reachable, is move feasible, is close to basket and others).

Figure 3 shows a BT with two children nodes—a condition C and an action A.

Figure 3 A Behavior Tree with Two Children Nodes

There are four types of composite constructs. Selectors pick one of its children to be executed. This selection can be done randomly or using some priority. The value of the selector depends on whether the child node executed was successful (return true) or not.

Sequences impose an ordering in the execution of children nodes. In Figure 3, the red-dotted line indicates the ordering of execution in the sequence tree. For this type of node to be successful, each and every one of its children nodes must be successful, as well.

Finally, Decorators, which are inspired in the programming design pattern, provide a way to simplify the programming process and extend behavior by adding functionality to a node. A Timer Decorator could be a kind of decorator that, as the name suggests, executes its children nodes after certain time intervals. A Counter Decorator, on the other hand, could execute a child node or behavior several times. In Figure 3, the D counter decorator will execute the node Sequence 10 times, as defined.

In the next section, I’ll describe the simplified version of the basketball game considered in this article and the AI proposed for such a game.

A Basketball Game and AI Implementation

Because a basketball game is a big, complicated game that would require a complex FSM or a really big BT, only a simplified version of it that includes some basic strategies for offensive and defensive plays will be considered in this article. In this game, there’ll be two players (A1->blue, B1->green), each with properties Speed and Shooting Accuracy. The first defines how fast or frequent the player reacts to the environment and the latter defines the probability that a player will make a shot once attempted. Initially, players start in the center as shown in Figure 4. The score is 0-0 and the time is 0 seconds. If a player hasn’t scored after 15 seconds, a shot-clock violation is triggered and that player loses possession of the ball. The GUI of the game consists of a Windows Forms application, which you can later consult in order to check any graphical details. The Start button, as expected, starts the game; analogous for the Stop button.

Figure 4 A Basketball Game with AI Implementation

The yellow squares indicate the baskets and the white circle repre­sents the ball. Let’s start analyzing the Court class, which corresponds to the basketball court; it contains the listed fields in Figure 5.

Figure 5 Court Class

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];
  }
...
}

Fields Height and Width are self-explanatory. BallPos indicates the position of the ball on the court. ScoreTeamA and ScoreTeamB indicate the score for each player and _grid is the string matrix containing the logic of the court. If player A1 is on cell (0,0) and is in possession of the ball, then value _grid [0, 0] = A1,B. The same applies for B1, hence, the possible values of any cell on the grid are A1, B1, A1,B and B1,B. Methods, indexers implemented in this class are the following (Indexer provides indexing of elements on the grid; it also updates the position of the ball on the court):

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);
}
}

The IsBall method determines whether a given string contains the ball:

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

The IsEmpty method determines whether a cell on the grid is empty:

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

Finally, the ToWallGrid method returns a PathNode matrix, as shown in Figure 6; it will be used in the Path Finding algorithm to be explained shortly.

Figure 6 ToWallGrid Method

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;
}

In this method, the wallGrid matrix will indicate whether a given cell will be considered as an obstacle or not, as mentioned, before it serves the Path Finding algorithm.

The BehaviorTree class and all of its descendants are structured according to the Figure 7 diagram.

Figure 7 BehaviorTree Class Structure

The code for every BehaviorTree-related class is presented in Figure 8.

Figure 8 Code for Every BehaviorTree Related Class

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();
}
  }

Given the fact that every class is straightforward and the code self-explanatory, no description of them will be provided; you can easily see what the purpose of each class is and how it links to previously explained concepts.

The most significant class in the application is the Player class representing the agent itself and encapsulating its behavior and all of the AI code. This behavior has been divided into offensive and defensive; the first has been modeled through an FSM and the latter has been modeled using a simple BT like the one shown in Figure 3. A Player contains the listed fields shown in Figure 9.

Figure 9 A Player Class Code Field

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 defines the position of the player on the court. Scoring­Basket is the location where he should score on the court. Path is a list of PathNodes used to find the shortest path from one initial point to another considering obstacles on the way and _random is a Random object used to get the probability of making a shot. The remaining fields are self-explanatory.

This class uses the following enums:

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

The Player class is divided into Predicates methods and Action methods. There are three 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;
}

The IsBallLoose method simply determines if the ball is loose on the court; the IsCloseToBasket method determines whether the player is close to his scoring basket:

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 indicates the possibility of reaching one of the opponents on court; the factor variable aids on deciding if an opponent is in a reachable position. Reachable means that the opponent hasn’t passed (while in offensive mode) the player’s column when moving toward his scoring basket.

Before looking at the Actions block code, let’s analyze two methods that are called immediately after an agent executes an action:

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();
}

This method represents the agent’s function; it gets a set of percepts and reacts or decides which action to take looking at the percepts, as shown in Figure 10.

Figure 10 Agent’s Function

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;
}

The GetPercepts method, which relies on several predicates, returns the set of percepts that are eventually used to decide which action to take.

First, the FeasibleMoves method acts as a filter; once the agent has decided a move in a certain direction, it checks the FeasibleMoves list of directions and sees whether the direction the agent is about to make is actually possible; if not then no action is taken. The Move method that includes a call to the FeasibleMoves method is shown in Figure 11.

Figure 11 The Move Method

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;
}

The MoveToBall method moves the player toward the ball in case it’s loose on the court:

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);
}

As shown in Figure 12, the MoveToBasket represents a distinctive method in the application as it’s the only one that includes planning and makes the agent hybrid (reactive and deliberative).

Figure 12 The MovetoBasket Method

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 builds a path from the player’s position up to the basket; if the plan fails or becomes unfeasible, then that path is erased and recalculated again. The PathFinding algorithm is a search algorithm; in this case, an A* algorithm. Path finding algorithms are frequently implemented in AI and are extremely common in games.

As previously mentioned, the defensive behavior is developed using a BT, as shown in Figure 13.

Figure 13 Defensive Behavior Using a Behavior Tree

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;
}

The BlockPath method represents the strategy by which a player tries to block his closest opponent path to the basket. It relies on the Closest method, which uses the Manhattan Distance to find his closest opponent, as shown in Figure 14.

Figure 14 The BlockPath Method

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;
}

Wrapping Up

In this article, I explained how to develop a hybrid agent for a multi-agent basketball game. It’s now up to you to incorporate new functionalities and strengthen the AI proposed. In a future article I’ll address the issue of creating a learning agent for a basketball game; a learning agent will evolve over time and improve its strategies with every new play.

Arnaldo Pérez Castaño is a computer scientist based in Cuba. He’s the author of a series of programming books—“JavaScript Fácil,” “HTML y CSS Fácil,” and “Python Fácil” (Marcombo S.A.)—and writes for VisualStudioMagazine.com and Smashing Magazine. His expertise includes Visual Basic, C#, .NET Framework and artificial intelligence, and he offers his services as a freelancer through nubelo.com. Cinema and music are some of his passions. Contact him at arnaldo.skywalker@gmail.com.

Thanks to the following Microsoft technical expert for reviewing this article: James McCaffrey
Dr. James McCaffrey works for Microsoft Research in Redmond, Wash. He has worked on several Microsoft products including Internet Explorer and Bing. Dr. McCaffrey can be reached at jammc@microsoft.com.

Discuss this article in the MSDN Magazine forum