---

Juli 2016

Band 31, Nummer 7

C# – Arbeiten mit künstlicher Intelligenz bei einem „Mini-Basketball“-Spiel mit mehreren Agents

Von Arnaldo Pérez Pérez | Juli 2016

Künstliche Intelligenz (Artificial Intelligence, AI) ist heute das interessanteste und forschungsintensivste Feld der Informatik, und viele ihrer Teilgebiete haben großen Einfluss auf unseren Alltag. Die Anwendung von AI erfolgt nahezu überall und in den am wenigsten erwartbaren Szenarien – wenn ein Versicherungsunternehmen Algorithmen für Data Mining anwendet, um Beziehungen zwischen Personen zu entdecken (um sicherzustellen, dass ein Kunde nicht in betrügerischer Absicht handelt), wenn Ihnen eine Liste mit Freunden auf Facebook vorgeschlagen wird, wenn Sie ein Videospiel spielen usw. Die Einsatzgebiete sind immens und umfassen Bereiche wie Wirtschaft, Handel, Astronomie, Medizin und Militär.

Der Wunsch, verschiedene menschliche Aufgaben zu automatisieren und ein künstliches Bewusstsein zu erschaffen, hat im Lauf der Zeit zur Ausprägung dieser beliebten Wissenschaft namens AI geführt. Ihre Definition, so einfach sie sich anhört, führt regelmäßig zu Zweifeln, da AI wohl das umfangreichste Gebiet der Informatik darstellt. Aus Expertensicht stellt AI die Automatisierung von Aktivitäten dar, die wir mit dem menschlichen Denken und Aktivitäten wie dem Fällen von Entscheidungen, dem Lösen von Problemen, Lernen usw. assoziieren („Artificial Intelligence: Can Computers Think?“ Richard E. Bellman, 1978). Die vorstehende Definition legt dar, wie sich AI bezogen auf die Automatisierung von menschlichen Aktivitäten verhält. Daher stellt sich die Frage: Warum muss AI erschaffen werden, um menschliche Aufgaben zu automatisieren? Ist das wirklich notwendig? Die Antwort lautet „Ja“.

Menschen sind die höchst entwickelten, elegantesten und komplexesten biologischen Maschinen, die der Menschheit bekannt sind. Die komplexe und faszinierende Funktion unserer Organismen in Kombination mit den erstaunlichen Fähigkeiten unseres Gehirns machen uns zu nahezu perfekten Maschinen. Aber wenn Menschen so perfekt sind, warum ist es dann sinnvoll, elektrische Maschinen aus Stahl und AI-Entitäten zu entwickeln?

Erstens erstellen Menschen elektronische Maschinen aus Stahl, weil unser Organismus trotz seiner ungeheuer guten Funktion sehr fragil ist; er kann daher weder mit extrem hohen noch extrem niedrigen Temperaturen umgehen, er benötigt Sauerstoff für die ordnungsgemäße Funktion, er kann leicht durch natürliche Objekte beschädigt werden, im fehlt die Widerstandskraft, über die Stahl verfügt usw. Eine elektronische Maschine aus Stahl kann all diese Hindernisse umgehen.

Zweitens ist das menschliche Gehirn, trotz seiner Fähigkeit, Emotionen wahrzunehmen und einige wirklich komplexe Überlegungen anzustellen, im Vergleich zu Computern unter dem Blickwinkel eines einfachen und primitiven Kriteriums langsam: der Berechnung. Ein Maschinengehirn (Computer) ist im Gegensatz zu einem menschlichen Gehirn imstande, Millionen Berechnungen pro Sekunde auszuführen. Vorgänge wie das Suchen und Sortieren in großen Domänen werden von Computern sehr viel schneller als von Menschen bewältigt. Daher ist AI erforderlich, um unser Leben effizienter zu gestalten und Zeit zu sparen. Das ist der Fall, wenn Sie einen Taschenrechner benutzen; beispielsweise ist der menschliche Verstand normalerweise außerstande, die Quadratwurzel einer großen Zahl schnell zu berechnen. Sie verwenden daher einen Rechner, um dieses Ergebnis nahezu augenblicklich zu erhalten; ein Rechner ist im Prinzip ein Roboter, dessen Aufgabe Rechnen ist.

In den nächsten Abschnitten beschreibe ich einige der traditionellen Entitäten, Systeme, die mit AI zusammenhängen, und ihre Interaktion. Ich demonstriere die Entwicklung einer AI für ein Basketballspiel mit mehreren Agents, in dem zwei Basketballteams (Bulls und Knicks) gegeneinander spielen können.

Agents

Die 90er haben der Informatik das Konzept der Agents beschert, und der Ausdruck ist heute so modern und hip wie „objektorientiert“ in den 80ern und „AI“ in den 70ern war. Ein Agent ist eine Entität, die zur Wahrnehmung ihrer Umgebung und als Reaktion darauf zum Handeln fähig ist („Künstliche Intelligenz: Ein moderner Ansatz“, Stuart Russell und Peter Norvig, 1997). Der wichtigste Unterschied zwischen einem Agent und einem gewöhnlichen Programm besteht darin, dass der erstgenannte autonom sein muss; das bedeutet, er muss ohne direkte Intervention durch Menschen oder andere tätig werden können. Ein weiterer Unterschied besteht darin, dass der Agent bestimmte Aufgaben im Auftrag eines anderen (normalerweise ist das der Benutzer oder Programmierer) ausführt, daher die Bezeichnung Agent, da sie jemanden bezeichnet, der lediglich im Auftrag anderer handelt.

Ein rationaler Agent ist einer, der so agiert, dass das beste Ergebnis erreicht wird, bzw. das wahrscheinlich beste Ergebnis, wenn es Unsicherheiten gibt („Künstliche Intelligenz: Ein moderner Ansatz“, Stuart Russell und Peter Norvig, 1997). Rationalität bedeutet in diesem Sinn, zu richtigen Folgerungen zu gelangen und (wann immer möglich) die Aktion auszuwählen, die nach einem logischen Schluss zum Erreichen des gewünschten Ziels führt. Menschen sind rationale Agents; sie nehmen ihre Umgebung durch Augen, Ohren, Zunge und Nase wahr und handeln gegebenenfalls unter Verwendung ihrer Beine, Hände usw., im Allgemeinen nach der Anwendung logischer Schlussfolgerungen und der Auswahl der Aktionen, die sie zum gewünschten Ziel führen werden.

Als Perzept wird der wahrgenommene Input des Agents zu jedem beliebigen Zeitpunkt bezeichnet. Die Perzeptfolge stellt die vollständige Abfolge der Perzepte dar, die der Agent während seiner Lebensdauer empfunden oder wahrgenommen hat. Die Agentfunktion stellt das Agentverhalten durch eine Zuordnung einer beliebigen Perzeptfolge zu einer Aktion dar. Diese Funktion ist lediglich eine abstrakte Beschreibung; das Agentprogramm stellt die eigentliche Implementierung dieser Abstraktion dar. Abbildung 1 zeigt einen Teil der Agentfunktion für einen Basketballspieler. Die Spalte mit der Beschriftung „Perzeptfolge“ enthält die Zustände des Spielers, und die Spalte mit der Beschriftung „Aktion“ enthält die nach der entsprechenden Perzeptfolge auszuführende Aktion.

Abbildung 1 Partielle Agentfunktion für einen Basketballspieler

Perzeptfolge	Aktion
(nahe am Ball, ungedeckt)	Werfen
(nahe am Gegner, Gegner wirft)	Blocken
(Gegner verliert Ball)	Steal
(gedeckt, Teamkamerad ungedeckt)	Passen
(Teamkamerad nahe am Korb, Teamkamerad ungedeckt, Teamkamerad guter Slammer, Blickkontakt)	Alley-oop-Pass

Die Welt der Agents lässt sich nach ihrer Architektur in folgende Kategorien aufteilen:

• Ein reaktiver Agent kann eine fortlaufende Interaktion mit der Umgebung aufrecht erhalten und zeitnah auf Änderungen der Umgebung reagieren. Der Ausdruck wird heute zur Bezeichnung eines Systems verwendet, das weder symbolische Darstellung noch Schlussfolgerung umfasst; ein derartiger Agent reflektiert weder die langfristigen Folgen seiner Aktion, noch koordiniert er seine Aktivität mit anderen Agents. In dieser Weise antwortet ein reaktiver Agent immer zeitnah auf äußere Reize und ist ereignisgesteuert. Das kann durch einfache Wenn-Dann-Regeln implementiert werden. Die Ziele des Agents werden nur implizit durch die Regeln repräsentiert, und es ist schwierig, das gewünschte Verhalten sicherzustellen. Jede einzelne Situation muss im Vorhinein abgewogen werden; daher enthalten reaktive Systeme in komplexen Umgebungen normalerweise Hunderte Regeln. Reaktive Agents besitzen kein internes Modell der Welt, sie sind daher unfähig, abstrakte Folgerungen über sie abzuleiten. Die Wiederholung erfolgt einfach dadurch, dass der Agent Eingaben empfängt und auf diese anhand einfacher Regeln reagiert.
• Ein proaktiver Agent ist imstande, die Initiative zu ergreifen; er ist nicht nur durch Ereignisse gesteuert, sondern fähig, Ziele zu generieren und rational zu agieren, um sie zu erreichen. Er wird von manchen als zielgesteuerter reaktiver Agent angesehen.
• Ein absichtsgesteuerter Agent (Deliberative Agent, auch als Intentional Agent bezeichnet) stellt Wissen symbolisch dar und verwendet mentale Auffassungen, wie Vorstellungen, Absichten, Wünsche, Entscheidungen usw. Er versucht, das menschliche Urteilsvermögen, verteilte Aktivitäten und Verhalten mithilfe von logischen Repräsentationen zu modellieren. Er wird normalerweise in Form einer BDI-Architektur (Belief, Desire, Intention – Weltwissen, Ziele, Absichten) implementiert. Er kann Schlussfolgerungen aus der Vergangenheit ableiten und Zukunft planen; Planung ist für diese Art Architektur typisch.
• Ein hybrider Agent stellt eine Mischung einiger aus allen verschiedenen Architekturen dar.

Eine andere Möglichkeit, die Welt der Agents aufzuteilen, besteht darin, sie in lernende und nicht lernende Agents aufzuteilen. Ein lernender Agent ist einer, der ein gewisses Maß an Schulung benötigt, um gut zu funktionieren, der sein aktuelles Verhalten auf der Grundlage früherer Erfahrungen anpasst und sich im Lauf der Zeit entwickelt. Ein nicht lernender Agent ist ein Agent, der sich nicht weiterentwickelt oder auf vergangene Erfahrungen bezieht, der hartcodiert und von seiner Programmierung unabhängig ist.

Da die Basketball-Spielumgebung diskret, endlich und durch eine endliche Menge Regeln definiert ist, schlage ich in diesem Artikel einen nicht lernenden Agent vor.

Multiagentsystem

Wenn ein Agent in einer Umgebung mit anderen Agents koexistiert – in der er möglicherweise mit ihnen zusammenarbeitet oder konkurriert – wird sie als System mit mehreren Agents (Multiagentsystem, MAS) angesehen. In MAS-Umgebungen hat jeder Agent seine eigene Perspektive der Welt und kein Wissen von den internen Zuständen der anderen Agents oder der Weise, in der sie die Umgebung sehen. Daher stellt MAS einen Typ von verteiltem System mit folgenden Features dar:

• Die Agents besitzen unvollständige Informationen über das System oder weisen unzureichende Fähigkeiten auf, um eine Aufgabe autonom zu lösen.
• Das System weist keine globale Steuerung auf.
• Die Daten liegen dezentral vor.

Eine Koalition ist jede beliebige Teilmenge von Agenten innerhalb der Umgebung. Im Fall von Basketball gibt es zwei Koalitionen – Team A und Team B – mit leerer Schnittmenge und der gleichen Kardinalität größer als null für beide.

Eine Strategie ist eine Funktion, die den aktuellen Zustand der Umgebung empfängt und die von einer Koalition auszuführende Aktion ausgibt. Die Strategie für Team A hängt normalerweise von den im aktuellen Augenblick von jedem Agent von Team B ausgeführten Aktionen aus.

In MAS erfolgt Interaktion auf dem Weg der Kommunikation, und den Agents stehen verschiedene Kommunikationsformen offen; einfache Signale, die festen Auslegungen zugeordnet sind, stellen vermutlich die naive Kommunikationsform unter Agents dar. Eine Schwarzes Brett-Struktur ist eine Kommunikationsform, die in einer gemeinsamen Ressource besteht, die in verschiedene Bereiche der Umgebung aufgeteilt ist. Hier können Agents alle signifikanten Informationen für ihre Aktionen schreiben oder lesen. Die Übergabe von Nachrichten zwischen Agents ist eine weitere Form der Kommunikation. Bei dieser Form tauschen Agents Nachrichten mit einer festen Syntax und einem definierten Protokoll aus, jedoch ohne definierte Semantik; der empfangende Agent muss daher die Absicht der Nachricht erschließen. Schließlich überwindet die stark vom amerikanischen Philosophen John R. Searle („Sprechakte: Ein sprachphilosophischer Essay“, 1969) und dem kanadischen Logiker Daniel Vanderveken („Grundlagen der Sprechakttheorie“, 1994) geprägte Sprechakttheorie die Nachteile beim Übergeben von Nachrichten durch Abwicklung der Interaktion zwischen Agents auf zwei Ebenen – erstens der informationelle Gehalt der Nachricht und zweitens die Intention der Nachricht. Dieser Ansatz unterscheidet zwischen dem Ausdrucksakt (Wörter, Sätze), der Ausdrucksabsicht (Information, Bitte, Auftrag usw.) und dem gewünschten Ergebnis des Ausdrucks (Vorwurf, Überzeugung usw.).

Koordination ist in MAS von entscheidender Wichtigkeit, da sie zur Kohärenz des Systemverhaltens und zum Erreichen der Team- oder Koalitionsziele beiträgt. Das impliziert die Berücksichtigung der Aktionen anderer Agents bei der Planung und Ausführung der korrespondieren Aktionen einzelner oder mehrerer Agents. In vielen Fällen impliziert Koordination darüber hinaus Kooperation oder Konkurrenz; in einem Basketballspiel gibt es beides.

Kooperation ist als Ergebnis sich ergänzender Fähigkeiten und der gegenseitigen Abhängigkeit zwischen Agentaktionen und dem unausweichlichen Erfordernis, Erfolgskriterien zu erfüllen, unabdingbar. In einem kooperativen Modell sind Agents kollektiv motiviert oder kollektiv interessiert; daher arbeiten sie auf die Erreichung eines gemeinsamen Ziels hin. In einem anderen möglichen Modell sind die Agents eigenmotiviert oder verfolgen eigene Interessen, da jeder Agent eigene Ziele verfolgt und mit den anderen Agents im System in Konkurrenz treten kann, um diese Ziele zu erreichen. In diesem Sinn kann sich Konkurrenz auf das Erreichen oder Verteilen bestimmter Aufgaben beziehen. In einem derartigen Modell müssen die Agents ihre Aktionen mit anderen Agents koordinieren, um ein kohärentes Verhalten sicherzustellen. Während des Koordinierungsprozesses können sowohl in einer kooperativen als auch in einer auf Konkurrenz basierende Umgebung Konflikte auftreten, die mithilfe von Verhandlung gelöst werden. Verhandlung kann als der Prozess der Identifikation von Interaktionen auf der Grundlage von Kommunikation und Urteilsvermögen hinsichtlich des Zustands und der Absichten anderer Agents aufgefasst werden.

Im nächsten Abschnitt beschreibe ich eine neue und interessante Datenstruktur, die in vielen aktuellen Videospielen verwendet wird: den Verhaltensbaum.

Endliche Automaten und Verhaltensbäume

Endliche Automaten (Finite State Machines, FSMs) sind der herkömmliche Ansatz für das Modellieren von Entscheidungsfindung, Aktionswahl und Aktionsausführung für das Verhalten von Agents in Spielen. Eine FSM stellt ein mathematisches Modell mit einer Übergangsfunktion dar, dem eine endliche Menge von Zuständen entspricht. FSMs bieten einen einfachen, intuitiven Mechanismus für reaktives Verhalten zu, Verarbeitung von und Reaktion auf kontinuierliche Ereignis- oder Eingabedatenströme.

Abbildung 2 zeigt eine einfache FSM, die das Verhalten eines Agents modelliert, sobald eine Entfernung zum Korb erreicht wird, die als „nah“ angesehen wird. Wenn dieser Fall eintritt, wird zum Verhalten „Werfen“ gewechselt. In diesem Szenario korrespondieren Zustände mit Verhalten und Übergänge mit Ereignissen. Der schwerste Nachteil einer FSM zeigt sich, wenn die Notwendigkeit eintritt, ihre Funktionalität zu erweitern oder ein komplexeres Verhalten zu implementieren. In diesen Fällen kann die Anzahl der Statusübergänge exponentiell anwachsen, wodurch die FSM extrem schwer verständlich und handhabbar wird.

Abbildung 2 Einfaches Modell eines endlichen Automaten

Verhaltensbäume (Behavior Trees, BTs) stellen eine einfache, skalierbare, modulare Lösung für das Darstellen von komplexem AI-Verhalten dar und weisen eine leicht zu wartende und zu implementierende Logik auf. Ihre Nutzung in der Spielebranche hat sich in den letzten Jahren stark erhöht, als Titel wie „Halo3“, „Spore“, „BioShock“ und „SWAT 4“ BTs als Tools zur Verhaltensmodellierung beinhalteten. BTs sind zielorientiert, und jeder Baum hängt mit einem eigenen, vergleichsweise abstrakten Ziel zusammen. BTs können miteinander verknüpft werden, was die Implementierung komplexer Verhalten ermöglicht, indem zunächst kleinere Unterverhalten definiert werden.

Jeder Knoten in einem BT ist entweder ein primitives Konstrukt oder ein zusammengesetztes Konstrukt. Der erste Typ bildet die Blätter des Baums; der zweite stellt eine Weise dar, die Beziehungen zwischen untergeordneten Knoten zu beschreiben.

Es gibt zwei Arten von primitiven Konstrukten. Aktionen verkörpern die Ausführung einer auf den Agent bezogenen Methode (Bewegen, Werfen und weitere). Bedingungen fragen den Status der Umgebung ab (ist der Gegner erreichbar, ist die Bewegung ausführbar, ist die Nähe zum Korb gegeben und weitere).

Abbildung 3 zeigt einen BT mit zwei untergeordneten Knoten – einer Bedingung B und einer Aktion A.

Abbildung 3 Verhaltensbaum mit zwei untergeordneten Knoten

Es gibt vier Typen von zusammengesetzten Konstrukten. Mithilfe von Selektoren kann eines seiner untergeordneten Elemente für die Ausführung ausgewählt werden. Diese Auswahl kann frei oder unter Anwendung einer Priorität erfolgen. Der Wert des Selektors hängt davon ab, ob der ausgeführte untergeordnete Knoten erfolgreich (Rückgabewert TRUE) ausgeführt wurde oder nicht.

Die Abfolge implementiert eine Reihenfolge in der Ausführung von untergeordneten Knoten. In Abbildung 3 markiert die rot gepunktete Linie die Ausführungsreihenfolge im Sequenzbaum. Damit diese Art Knoten erfolgreich ausgeführt werden kann, muss jeder seiner untergeordneten Knoten ebenfalls erfolgreich ausgeführt werden.

Schließlich bieten Decorator-Elemente, die vom Programmierentwurfsmuster inspiriert sind, eine Möglichkeit, den Programmierprozess zu vereinfachen und das Verhalten durch Hinzufügen von Funktionalität zu einem Knoten zu erweitern. Ein Zeitgeberdecorator könnte eine Art Decorator sein, die – wie der Name nahelegt – seine untergeordneten Knoten nach bestimmten Zeitintervallen ausführt. Ein Zählerdecorator könnte wiederum einen untergeordneten Knoten oder ein Verhalten mehrfach ausführen. In Abbildung 3 führt der Zählerdecorator D die Knotensequenz 10 mal aus, wie definiert.

Im nächsten Abschnitt beschreibe ich die vereinfachte Version des in diesem Artikel beleuchteten Basketballspiels und die für ein solches Spiel vorgeschlagene AI.

Ein Basketballspiel und seine AI-Implementierung

Da Basketball ein umfangreiches, kompliziertes Spiel ist, das eine komplexe FSM oder einen wirklich großen BT erfordern würde, wird in diesem Artikel nur eine vereinfachte Version untersucht, die einige grundlegende Strategien für offensive und defensive Spielzüge enthält. In diesem Spiel gibt es zwei Spieler (A1 -> blau, B1 -> grün), von denen jeder die Eigenschaften Geschwindigkeit und Treffgenauigkeit aufweist. Die erste definiert, wie schnell oder wie häufig der Spieler auf die Umgebung reagiert, und die zweite definiert die Wahrscheinlichkeit, mit der ein Spieler aus einem Versuch einen Treffer erzielen kann. Anfänglich beginnen Spieler in der Mitte, wie in Abbildung 4 gezeigt. Der Stand ist 0:0, und die Zeit ist 0 Sekunden. Wenn ein Spieler nach 15 Sekunden nicht gepunktet hat, wird ein Wurfuhrverstoß ausgelöst, und der betreffende Spieler verliert den Ballbesitz. Die grafische Benutzeroberfläche des Spiels besteht aus einer Windows Forms-Anwendung, die Sie später zu Rate ziehen können, um grafische Details zu studieren. Die Schaltfläche „Start“ startet – erwartungsgemäß – das Spiel, analog gilt Entsprechendes für die Schaltfläche „Stopp“.

Abbildung 4 Ein Basketballspiel mit AI-Implementierung

Die gelben Quadrate zeigen die Körbe, der weiße Kreis den Ball an. Beginnen wir mit der Analyse der Klasse „Court“, die dem Basketballfeld entspricht; sie enthält die in Abbildung 5 aufgelisteten Felder.

Abbildung 5 Klasse „Court“

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

Die Felder Height und Width sind selbsterklärend. BallPos zeigt die Position des Balls auf dem Spielfeld an. ScoreTeamA und ScoreTeamB geben den Punktestand für jeden Spieler an, und _grid ist die Zeichenfolgenmatrix, die die Logik des Spielfelds enthält. Wenn sich der Spieler A1 auf Zelle (0,0) befindet und im Ballbesitz ist, dann entspricht der Wert „_grid [0, 0] = A1,B“. Das gleiche gilt für B1, daher sind die möglichen Werte jeder Zelle im Raster „A1“, „B1“, „A1,B“ und „B1,B“. Die folgenden Methoden und Indizierer sind in dieser Klasse implementiert (der Indizierer stellt die Indizierung der Elemente auf dem Raster zur Verfügung; er aktualisiert außerdem die Position des Balls auf dem Spielfeld):

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

Die IsBall-Methode bestimmt, ob eine bestimmte Zeichenfolge den Ball enthält:

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

Die IsEmpty-Methode bestimmt, ob eine Zelle im Raster leer ist:

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

Schließlich gibt die ToWallGrid-Methode eine PathNode-Matrix zurück, wie in Abbildung 6 dargestellt; sie wird im Algorithmus zur Wegermittlung verwendet, der in Kürze erklärt wird.

Abbildung 6 Methode „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;
}

In dieser Methode zeigt die wallGrid-Matrix an, ob eine bestimmte Zelle – wie bereits erwähnt – als Hindernis angesehen wird oder nicht, bevor sie dem Wegermittlungsalgorithmus übergeben wird.

Die Klasse „BehaviorTree“ und alle ihre Nachfahren weisen die im Diagramm in Abbildung 7 dargestellte Struktur auf.

Abbildung 7 Struktur der Klasse „BehaviorTree“

Der Code für jede auf BehaviorTree bezogene Klasse ist in Abbildung 8 wiedergegeben.

Abbildung 8 Code für jede auf BehaviorTree bezogene Klasse

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

Angesichts der Tatsache, dass jede Klasse einfach und der Code selbsterklärend ist, gebe ich zu ihnen keine Beschreibung; Sie können den Zweck der einzelnen Klassen und ihre Verbindung mit den zuvor erläuterten Konzepten leicht ersehen.

Die bedeutendste Klasse in der Anwendung ist die Klasse „Player“, die den Agent selbst darstellt und sein Verhalten sowie den gesamten AI-Code verkapselt. Dieses Verhalten wurde in offensiv und defensiv aufgeteilt; das erste wurde mithilfe einer FSM und das zweite in Form eines einfachen BTs modelliert, wie dem in Abbildung 3 dargestellten. Ein Spieler enthält die in Abbildung 9 dargestellten aufgelisteten Felder.

Abbildung 9 Ein Codefeld der Klasse „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“ definiert die Position des Spielers auf dem Feld. „Scoring­Basket“ ist die Position, an der er auf dem Feld punkten soll. „Path“ ist eine Liste der „PathNodes“, die zum Ermitteln des kürzesten Wegs von einem Ausgangspunkt zu einem anderen Punkt unter Berücksichtigung der Hindernisse auf dem Weg verwendet wird, und „_random“ ist ein Zufallsobjekt, das zum Abrufen der Wahrscheinlichkeit für das Ausführen eines Wurfs verwendet wird. Die verbleibenden Felder sind selbsterklärend.

Dieses Klasse verwendet die folgenden Enumerationen:

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

Die Klasse „Player“ ist in Prädikatmethoden und Aktionsmethoden aufgeteilt. Es gibt drei Prädikate:

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

Die IsBallLoose-Methode bestimmt einfach, ob der Ball auf dem Feld frei ist; die IsCloseToBasket-Methode bestimmt, ob der Spieler in der Nähe des zählenden Korbs ist:

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 zeigt die Möglichkeit an, einen der Gegner auf dem Feld zu erreichen; die Variable „factor“ hilft bei der Entscheidung, ob ein Gegner sich in einer erreichbaren Position befindet. Erreichbar bedeutet, dass der Gegner (im offensiven Modus) bei der Bewegung zu seinem zählenden Korb die Spalte des Spielers nicht überquert hat.

Bevor wir uns den Code des Blocks „Actions“ ansehen, wollen wir zwei Methoden analysieren, die unmittelbar nach der Ausführung einer Aktion durch einen Agent aufgerufen werden:

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

Diese Methode stellt die Funktion des Agents dar; sie ruft eine Reihe von Perzepten ab und reagiert darauf oder entscheidet, welche Aktion in Ansehung der Perzepte ergriffen werden soll, wie in Abbildung 10 zu sehen.

Abbildung 10 Funktion des Agents

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

Die GetPercepts-Methode, die auf mehreren Prädikaten aufbaut, gibt die Menge der Perzepte zurück, die gegebenenfalls der Entscheidung über die auszuführende Aktion zugrunde gelegt werden.

Zuerst fungiert die Methode „FeasibleMoves“ als Filter; sobald der Agent eine Entscheidung für eine Bewegung in einer bestimmten Richtung getroffen hat, überprüft sie die Liste „FeasibleMoves“ der Richtungen und überprüft, ob die Richtung, die der Agent einschlagen soll, überhaupt möglich ist; falls nicht, wird keine Aktion ausgeführt. Die Move-Methode, die einen Aufruf der Methode „FeasibleMoves“ enthält, ist in Abbildung 11 dargestellt.

Abbildung 11 Die Methode „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;
}

Die Methode „MoveToBall“ bewegt den Spieler zum Ball hin, falls der frei auf dem Feld ist:

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

Wie in Abbildung 12 zu sehen, stellt „MoveToBasket“ eine unverwechselbare Methode in der Anwendung dar, da es die einzige Methode ist, die Planung involviert und den Agent zu einem hybriden (reaktiven und absichtsgesteuerten) Agent macht.

Abbildung 12 Die Methode „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“ generiert einen Weg von der Position des Spielers hin zum Korb; wenn bei dem Plan ein Fehler auftritt oder er undurchführbar wird, wird dieser Weg gelöscht und erneut berechnet. Der PathFinding-Algorithmus ist ein Suchalgorithmus; in diesem Fall ein A*-Algorithmus. Algorithmen zur Wegermittlung werden häufig in AI implementiert und sind in Spielen außerordentlich gebräuchlich.

Wie zuvor erwähnt, wird das Defensivverhalten in Form eines BTs entwickelt, wie in Abbildung 13 zu sehen.

Abbildung 13 Defensivverhalten unter Verwendung eines Verhaltensbaums

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

Die BlockPath-Methode stellt die Strategie dar, mit der ein Spieler versucht, den Weg seines nächststehenden Gegners zum Korb zu blockieren. Sie beruht auf der Closest-Methode, die Manhattan-Metrik verwendet, um den nächststehenden Gegner zu ermitteln, wie in Abbildung 14 dargestellt.

Abbildung 14 Die Methode „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;
}

Zusammenfassung

In diesem Artikel habe ich erläutert, wie ein hybrider Agent für ein Multiagent-Basketballspiel entwickelt werden kann. Es liegt jetzt an Ihnen, neue Funktionen zu integrieren und die vorgeschlagene AI auszubauen. In einem kommenden Artikel werde ich mich mit dem Erstellen eines lernenden Agents für ein Basketballspiel und den damit verbundenen Schwierigkeiten befassen; ein lernender Agent entwickelt sich im Lauf der Zeit und verbessert seine Strategien mit jedem neuen Spiel.

---

Arnaldo Pérez Castañoist ein auf Kuba lebender Informatiker. Er ist Autor einer Reihe von Büchern zur Programmierung: „JavaScript Fácil“, „HTML y CSS Fácil“ und „Python Fácil“ (Marcombo S.A). Außerdem schreibt er für VisualStudioMagazine.com und Smashing Magazine. Er ist Fachmann für Visual Basic, C#, .NET Framework und künstliche Intelligenz und bietet seine Dienste auf nubelo.com als Freiberufler an. Das Kino und die Musik zählen zu seinen Leidenschaften. Sie erreichen ihn unter arnaldo.skywalker@gmail.com.

Unser Dank gilt dem folgenden technischen Experten bei Microsoft für die Durchsicht dieses Artikels: James McCaffrey
Dr. James McCaffrey ist in Redmond (Washington) für Microsoft Research tätig. Er hat an verschiedenen Microsoft-Produkten mitgearbeitet, unter anderem an Internet Explorer und Bing. Dr. McCaffrey erreichen Sie unter jammc@microsoft.com.