Inhaltsverzeichnis 1. Kooperation

Kooperation mehrerer Computergegner
Inhaltsverzeichnis
Alexander Altmayer
Inhaltsverzeichnis
1. Kooperation - wozu?
2
2. Einleitung
3
3. Gruppenstrukturen
3
4. Nachrichten
4
5. Aufgabenbestimmung
6
5.1 Contract Net Protocol
7
6. Aufgabenausführung
11
7. Kooperation mehrerer Gegnergruppen
12
8. Zusammenfassung und Ausblick
13
9. Quellenangaben
14
1
Kooperation mehrerer Computergegner
1.
Kooperation - wozu?
Alexander Altmayer
Kooperation - wozu?
Der Grund, Teamfähigkeit in Computerspielen einzusetzen und zu verbessern, ist wohl derselbe wie der,
die Gegner-KI im Allgemeinen zu verbessern:
- die Gegner sollten schwieriger werden, ohne "unfaire" Mittel einzusetzen, wie z.B. immer zu treffen
- das bedeutet oft, Modelle und Vorgehensweisen herzunehmen, wie sie in der Natur bzw. beim Menschen vorzufinden sind; dadurch wirkt Verhalten "natürlicher"
Manchmal ist es nicht nötig, explizit eine Team-KI zu programmieren. Dadurch, dass die Individuen selbst
das Beste für sich wollen, helfen sie auch meistens der gesamten Gruppe.
Wenn jedoch Mechanismen eingebaut werden, die eine richtige Zusammenarbeit ermöglichen, dann kann
der Erfolg drastisch erhöht werden. Manche Ziele lassen sich auch nicht alleine lösen. Ein Stein, der zu
schwer ist, ihn alleine zu tragen, kann zu zweit vielleicht schon wieder weggetragen werden. Eine neue
Position einzunehmen, wenn ein Spieler der eigenen Gruppe in der Schusslinie steht, ist dabei nur eine
Kleinigkeit.
Man könnte aber auch die Vorgehensweise der Agenten derart anpassen, dass sie ihre Schritte im Voraus
sozusagen absprechen. Mögliche Szenarien wären Bots, die ihren Gegner ins Kreuzfeuer nehmen, d.h.
zusammen die richtigen Positionen einnehmen. Oder bei Weltraumsimulationen (Wing Commander[1]):
zwei Schiffe teilen sich die Aufgabe, den Spieler zu eliminieren - ein Schiff fliegt vor dem Spieler her und
weicht immer aus, das andere schiesst ihn von hinten ab. Bei Fussballspielen würden dann z.B. die Spieler
vorher abgesprochene Spielzüge durchführen.
Ausserdem ist es sicher für jeden Spieler nervig, wenn die computergesteuerten Mitspieler in seinem Team
völlig dumme Aktionen durchführen, anstatt sich weitgehend intelligent und autonom zu verhalten, dabei
aber immer kontrollierbar bleiben. Nicht nur Gegner, auch eigene Gruppe muss intelligent sein!
Berechenbare Gegner und Gruppen lassen ein Spiel schnell zu einfach und somit langweilig werden.
Für die Kooperation mehrerer Computergegner sind also folgende Aspekte am interessantesten:
- Informationsaustausch / Nachrichtenaustausch
- Aufgabenbestimmung / Aufgabenausführung
- Gruppenhierarchie
2
Kooperation mehrerer Computergegner
Einleitung
Alexander Altmayer
2. Einleitung
Kooperation ist die Zusammenarbeit mehrerer Individuen oder Gruppen unter einem gemeinsamen Ziel.
Wie sieht es damit in Spielen aus?
Wenn Kooperation in Spielen vorhanden ist, so wird diese meist nach der eigentlichen KI eines Agenten
hinzuprogrammiert und so sollte es auch sein. Die Kooperation wird an die schon existierenden Verhaltensweisen angehängt, denn im Normalfall ist der eigene Erfolg oder eigenes Wohlergehen wichtiger als das der
Gruppe. Das zeigt sich vor allem daran, dass ein sehr wichtiges Ziel eines Agenten wohl sein sollte, zu
überleben. Dies kann durch Persönlichkeit wieder angepasst werden, sodass es Agenten gibt, die für die
Erledigung der Aufgabe die eigenen Bedürfnisse nach hinten zu stellen.
Hat ein Agent dennoch keine wichtige Aufgabe zu erledigen, dann könnte er bei den anderen nachfragen,
ob sie eine Aufgabe für ihn haben, die dann eben wichtiger sein sollte als das aktuelle Ziel. Umgekehrt
könnten auch Agenten, die gerade eine Aufgabe erledigen wollen, andere Agenten um Hilfe zur Erledigung
der Aufgabe bitten. Agenten, die man nach Aufgaben fragt, könnten auch immer gerade für diese Aufgabe
da sein; d.h. sie sind immer die Lenker und Denker, die bestimmen, was getan werden soll.
Hierbei ist interessant, wie man die Prioritäten für die Aufgaben vergibt. Der Prioritätswert kann meist nicht
konstant sein (ein einfacher Integerwert), denn die Bewertung einer Aktion bzw. eines Ziels hängst von
vielen Parametern ab. Es drängt sich schnell die Frage einer Bewertungsfunktion auf (mit gewichteten
Prioritäten). Problematisch dabei ist dabei die "subjektive" Abarbeitung der Funktion. Sie lässt die Zustände der anderen Gruppenmitglieder ausser acht, setzt man voraus, dass ein Agent nicht alles über die anderen weiss.
Wie schon angesprochen muss man, um Kooperation zu realisieren, festlegen, wer die nächste Aufgabe
nun letztendlich bestimmt. Es gibt verschiedene soziale Strukturen, die man dafür einsetzen kann.
3. Gr uppenstrukturen
1.) hierarchisch
In einem hierarchischen System existiert eine Ordnung bezüglich der Befehlsgewalt. Individuen, die höher
in der Ordnung stehen, bestimmen, was Individuen tun sollen, die in der Ordnung unter ihnen stehen. Die
Struktur kann beliebig viele Ebenen beinhalten. D.h. Untergebene können ihrerseits wieder Anweisungen
an andere geben, die in der Hierarchie unter ihnen stehen. Es kann aber auch für ein Spiel genügen, wenn
ein Individuum an der Spitze ist und alle anderen auf einer einzigen Ebene darunter.
2.) autonom / dynamisch
Hier gibt es keine Ordnung bezüglich der Befehlsgewalt. Jeder hätte prinzipiell das gleiche Recht, Aufgaben
zu verteilen. Allerdings geht das schief, wenn nicht irgendwann bestimmt wird, wer die Aufgaben festlegt.
Bei zwei Agenten, die zufällig ihre Aufgaben festlegen, wäre die Wahrscheinlichkeit sehr hoch, dass sie nicht
dieselbe Aufgabe wählen. So käme selten Kooperation zustande, wenn die Ziele nicht dieselben sind. Vor
allem wäre auch nicht abgesprochen, wie die Aufgabe zu lösen ist (auh im Hinblick auf Spezialisierung und
Aufgabenteilung). Ist einmal ein übergeordneter Agent bestimmt, so kann Kooperation stattfinden, da nun
alles abgesprochen ist .
In beiden Fällen müssen die Individuen miteinander kommunizieren: Die Höhergestellten propagieren z.B.
die anstehenden Aufgaben oder Agenten signalisieren, dass sie eine neue Aufgabe erwarten.
3
Kooperation mehrerer Computergegner
Nachrichten
Alexander Altmayer
4. Nachrichten
Wie wir gesehen haben, benötigt Kommunikation eine Form von Nachrichten oder Anfragen.
Anfragen geschehen üblicherweise durch den Austausch von Nachrichten. Nachrichten können aber auch
nur reinen Datenaustausch beinhalten ohne auf das Aufgabenmanagment abzuzielen. Als Beispiel: in vielen
Spielen hat der Computergegner den totalen Überblick. Er weiss, wo der Spieler bzw. seine Einheiten
stehen. Das ist unfair und nicht besonders realistisch. Besser wäre es, wenn Agenten/Bots den anderen
Agenten weitergeben, dass ein Gegner gesichtet wurde. Die Agenten können aufgrund dieses neu erhaltenen Wissens entsprechend reagieren.
Im Wesentlichen besteht eine Nachricht mindestens aus folgenden Merkmalen, um sinnvoll zu sein:
- Name: dieser bestimmt eindeutig die Nachricht, hier wird auch der Typ der Nachricht codiert, z.B.
Data_Request Data_Enemy_Seen oder Task_Announcement
- Sender
- Empfänger
- evtl. Zeit, wann die Nachricht gesendet wurde
- sonstige Menge an Daten/Objekten, abhängig von der Nachricht z..B. Deadline
Es gibt verschiedene Arten, wie Agenten den Nachrichtenaustausch realisieren könnten [3]:
1.) Prozeduraufruf (synchron):
Eine sehr einfache Möglichkeit. Agenten rufen sich gegenseitig auf (mit Prozeduraufruf im Programm vergleichbar). Der Kontrollfluss ist leicht nachzuverfolgen, allerdings muss ein Agent auf die Rückantwort eines
anderen warten, was dazu führt, dass er währenddessen nichts tun kann. Bei schnellen Antwortzeiten (v.a.
wenn die Agenten auf demselben Server sind) kann diese Methode dennoch angewandt werden.
2.) Callback Methode (asynchron):
Auch hier sendet ein Agent eine Nachricht an eine andere ab. Anstatt auf eine Rückantwort zu warten,
nachdem die Nachricht verschickt wurde, kann er mit ihrer Arbeit fortfahren. Erst, wenn die Rückantwort
eintrifft, muss den Agenten unterbrechen, was er gerade getan hat und die Nachricht behandeln. Der
Programmablauf kann schlecht verfolgt werden, aber die Agenten können mit ihrer Arbeit fortfahren, nachdem sie Nachrichten abgeschickt haben.
3.) Mailbox:
Diese Methode kann man in ihrem Ablauf und ihrer Vorgehensweise zwischen den beiden vorherigen
einordnen. Agent A sendet eine Nachricht an Agent B. B behandelt die Nachricht und legt das Ergebnis in
eine Mailbox der Agent A ab.
Der Empfänger (B) wird zwar unterbrochen, aber in der Realität ist es oft genauso - man hört die Kanäle
ab, erhält alle Nachrichten, kann aber nach deren erhalten sofort wieder zu seiner vorherigen Tätigkeit
zurückkehren; die Nachricht wurde ignoriert, weil sie im Moment unwichtig ist. Dies kann man z.B. anwenden wenn der Agent gerade mit einem Gegner in einen Kampf verwickelt ist und somit bestimmte Nachrichten für ihn derzeit nicht wichtig sind. Sowohl Callback als auch Mailbox würde man eher bei verteilten
Systemen bzw. Agenten verwenden. Je nach Situation könnte man sich überlegen, ein erweitertes MailboxSystem (Bild 1) aufzubauen, in dem Nachrichten wie auch Antworten zunächst in eine Mailbox aufgenommen werden und dann periodisch bearbeitet werden. Dann kann man auch sehr genau steuern, wann
Nachrichten verarbeitet werden.
Um eine einfache Verhaltensweise eines Agenten zu implementieren, legt man für jeden eine Zustandsmaschine zugrunde. Diese beinhaltet im Grunde alle spielrelevanten Daten für den Agenten. Für die KI
4
Kooperation mehrerer Computergegner
Nachrichten
Alexander Altmayer
Mailbox
Mailbox
Bild 1 : erweitertes
Mailbox-System
Agent B
Agent A
selbst ist das aktuelle Ziel von grösster Bedeutung, denn abhängig vom Ziel reagiert der Agent auf eingehende Informationen unterschiedlich. Fügt man nun noch ein Nachrichtensystem hinzu, lässt sich schon
ein erster Ansatz von Kooperation realisieren. Der Ablauf würde dann ungefähr so aussehen (siehe auch
Bild 2):
1. Eingabe (visuell, Audio...) + ankommende Nachrichten
2. Auswahl des eigenen Ziels
3. Senden eigener Nachrichten und Befehle
Wissen über die Welt
(auch über sich selbst)
1. Update
1. Update
2. Auswahl
der Aktion
audiovisueller Input
Nachrichten
vorgegebene
Verhaltensweisen
3. eigene
Nachrichten
Output
Bild 2 : grober Ablauf
eines ersten
KI-Ansatzes
oder als Pseudocode (zur Verdeutlichung der Bedeutung des Zustands):
case state of
idle: begin
messages:=get_messages();
if enemy_visible() then
begin
state:=attack; //Zustandswechsel
goto end_st; // Abbruch, da neuer Zustand gefunden
end;
if in_messages(enemy_spotted,messages)
begin
state:=run_to_position; goto end_st;
end;
end_st: (...)
end; break;
run_to_postion: (...)
attack: (...)
retreat: (...)
Bemerkungen: die Reihenfolge der if-Statements bestimmt die Priorität der Ereignisse. Im obigen Beispiel
wäre das Sichten eines Gegners (enemy_visible) immer das wichtigste Ereignis im Zustand idle. Mögliche
Lösung: Bewertungsfunktion. Ausserdem muss meist nicht nur die Zielzustands-Variable gesetzt werden,
sondern auch bestimmte andere Variablen. Beispielsweise müsste man beim Wechsel zu run_to_postion
die (neue) Zielposition auch noch setzen.
5
Kooperation mehrerer Computergegner
Aufgabenbestimmung
Alexander Altmayer
5. Aufgabenbestimmung
Systeme, wie sie vorher beschrieben wurden, können aber zu reaktiv sein. Beispiel: ein Bot, der sofort zum
Gegner bewegt, wenn ein Verbündeter ihn darüber informiert, dass er einen Gegner gesichtet hat ("Enemy
spotted"). Zudem sind sie nicht sehr flexibel, da sie meist fest im Quellcode verankert sind. Änderungen der
Aktionsausführung (meistens durch ein if-then-else - Statement realisiert) führen oft zu einer aufwendigen
Umstrukturierung des Quellcodes. Durch Verwendung eines regelbasierten Systems ist es nicht nur möglich, die tatsächliche Ausführung des Ziels online zu berechnen, sondern auch in abgeänderter Form zur
Absprache, welche Aufgaben erledigt werden sollen. Ein Problem ist die benötigte Rechenzeit von Systemen oder welchen die sozusagen die einzelne Abfolge der Aktionen berechnen (ein „Planer“). In einem 3DShooter wäre ein komplizierter Planer eher Fehl am Platze (Rechenzeit), bei rundenbasierten Strategiespielen dürfte dieser Weg wieder interessant werden.
Beispiele, wo einfache Regeln angewandt werden könnten:
Bots: ich brauche gerade jemanden, der am besten nichts zu tun hat und spezielle Fähigkeiten besitzt.
Oder: ich bin schwer verwundet, ich brauche einen Arzt, der wiederum von ein paar Leuten beschützt
werden soll.
Oder Fussballspiel: ich ziehe all die Mitspieler als Anspielmöglichkeit in Betracht, die nicht zu weit von mir
entfernt sind.
Regelbasierte Systeme müssen übrigens nicht unbedingt besonders komplex sein, was Rechenzeit spart
und die Implementierung vereinfacht. Bei der Überprüfung eines Agenten, ob er für die Aufgabe ausgewählt
wird, genügt es, die Bedingungen und ihre Werte mit den Attributen des zu überprüfenden Agenten zu
vergleichen. Stimmen diese nicht überein, so wird der Agent nicht in die Auswahlliste aufgenommen.
Um es an einem exakteren Beispiel festzumachen: Ein Bot möchte in einen Raum eine Granate werfen (weil
sich dort ein Gegner aufhält), er hat aber keine Granate. Deshalb kann er bei den anderen nachfragen, ob
sie das nicht für ihn erledigen. Wie eine entsprechende Nachricht aussähe wird im folgenden Kapitel ersichtlich.
Nicht ganz einfach ist es auch, festzulegen, wer die Aufgaben verteilen darf. Hat z.B. einer von Anfang an
immer das Kommando, so muss man, wenn dieser aus dem Spiel ausscheidet, wieder einen neuen Kommandeur bestimmen.
Das Contract Net Protocol, das im Folgenden vorgestellt wird, bietet eine einfache Möglichkeit Anfragen
und Probleme dieser Art zu lösen.
6
Kooperation mehrerer Computergegner
Contract Net Protocol
Alexander Altmayer
5.1 Contract Net Protocol
Das Contract Net Protocol [4] ist ein Distributed Net Solver. Verteilt bedeutet, dass sowohl Daten als auch
Kontrolle völlig getrennt voneinander liegen und verarbeitet werden; es gibt weder globale Daten noch
globale Kontrolle, die Individuen sind autonom. Die Individuen sind schwach miteinander verbunden; sie
verwenden die meiste Rechenzeit mehr zur Ausführung und Berechnung als zum Nachrichtenaustausch.
Das Contract Net Protocol bietet effizienten Nachrichtrenaustausch und Aufgabenteilung. Das Protokoll
und eine einheitliche Sprache, die jedes Individuum besitzt, legt die Bedeutung und die Verarbeitungsweise
einer Nachricht fest.
Beispiele, wo das Contract Net oder eine Art davon angewandt wird ist ein ehemaliges Uni-Praktikum,
Pengi2 oder ein Distributed Sensor Network zur Verkehrsüberwachung.
Ablauf des Contract im Wesentlichen:
- es existieren Manager (vergibt Aufträge) und Unterschreibende (erfüllen Aufträge)
- Aufträge ausschreiben (als Manager als Nachricht verbreiten)
- Ausgeschriebene Verträge evaluieren (aus der Sicht eines Unterschreibenden)
- für den interessantesten Vertrag dem Manager ein Angebot machen
- Manager wählen die besten Angebote/Agenten aus, setzen den Vertrag fest
Hierarchien entstehen dadurch, dass Unterschreibende Unterverträge mit anderen Agenten aushandeln
- Auswahl eines bereitstehenden Vertrages/Auftrages
Beispiel einer Task Announcement (Ausschreibung eines Auftrags)
To: * (broadcast message)
From: 25
Type: Task Announcement
Contract: 22-3-1
Task Abstraction: Object Position X27 Y33
Eligibility: Must-Have Sensor, Must-Be Scout
Bid Specification: Position, Object Type
Expiration Time: Jan 28 2001 20:00
1.) Manager und Unterschreibender
In einem Vertrag übernehmen die Agenten entweder die Rolle eines Managers, also des Aufraggebenden
oder des Unterschreibenden. Der Manager kümmert sich hauptsächlich um die Vertragsaushandlung und
überwacht dessen Ausführung. Der Unterschreibende führt einen Auftrag aus. Die Verteilung der Rollen
kann sich dynamisch verändern. Ein Agent kann auch gleichzeitig Manager und Ausführender in verschiedenen Verträgen sein.
2.) Task announcements
Ein Agent schreibt Verträge aus, indem es eine entsprechende Nachricht an alle oder nur bestimmte andere
Agenten sendet. Er ist dann der Manager des Vertrags.
Zunächst besitzt ein Angebot alle elementaren Felder einer Nachricht d.h. Absender und Empfänger.
7
Kooperation mehrerer Computergegner
Contract Net Protocol
Alexander Altmayer
Eine Auftragsausschreibung hat zudem vier Hauptfelder:
- Aufgabenbeschreibung: eine kurze abstrakte Beschreibung der Aufgabe, die ausgeführt werden soll
- Qualifizierungsangabe: Kriterien, die ein Agent erfüllen muss, um an der Aufgabe teilnehmen zu können,
also um ein Angebot zur Teilnahme anzukündigen. Man kann dies als Erweiterung des Empfängerfeldes
sehen: die Anzahl der möglichen Agenten, die auf die Ausschreibung antworten, wird dadurch weiter
eingeschränkt.
- Angebotsspezifikation: gibt an, welche Informationen ein Agent übermitteln muss, wenn er ein Angebot
als Antwort auf eine Ausschreibung sendet. Sie hilft bei der Auswahl der besten Angebote bzw. Agenten.
- Ablaufdatum: die Deadline für ankommende Angebote.
3.) Ausschreibungen verarbeiten und Angebote senden
Kommen bei einem Agenten Ausschreibungen an, so wird überprüft, ob die Eigenschaften den Anforderungen der Aufgabe entsprechen (Qualifizierungsangabe). Dann wird die Ausschreibung in die Liste der
schon vorhandenen einsortiert. Ein Agent, der gerade nichts zu tun hat, kann neu ankommenden Ausschreibungen direkt ein Angebot folgen lassen oder warten, ob noch weitere ankommen. Für die interessanteste
Aufgabe wird dem Manager dann ein Angebot für den Auftrag gemacht. Evtl. gibt der Anbieter dann noch
an, welche weiteren Informationen er für die Ausführung der Aufgabe noch brauchen könnte (z.B. die
Methode zur Aufgabenausführung).
4.) Verarbeitung der Angebote
Ankommende Angebote werden vom Manager ebenfalls in einer sortierten Liste gespeichert. Manager
können ebenfalls eine gewisse Zeit warten, bis mehrere Angebote angekommen sind und dann die besten
auswählen oder Verträge gleich festsetzen. Sind keine Angebote nach einer gewissen Zeit vorhanden, dann
könnte der Manager versuchen, eine andere Ausschreibung zu machen.
5.) Ausführung des Tasks
Sobald ein Agent nichts zu tun hat, wird die erste Vertrag/Aufgabe ausgewählt, die in der Liste der zugeteilten Verträge steht (Bereit-Liste, siehe Bild 3). Wurde die Vertrag ausgeführt, so wird sie in den BeendetStatus überführt, wartet ein Agent auf bestimmte Ereignisse oder Informationen, dann wird die Aufgabe in
die Wartend-Liste transferiert. Wenn die Ereignisse eintreten, dann wird sie wieder in die Bereit-Liste
aufgenommen.
Während der Ausführung einer Aufgabe werden Berichte an den Manager geschickt oder nach Aufgabenbeendigung Endberichte. Mit Hilfe dieser kann ein Manager unter anderem entscheiden, ob eine Aufgabe
weitergeführt werden soll.
8
Kooperation mehrerer Computergegner
Alexander Altmayer
Contract Net Protocol
In
Receive Award
Receive report
Ready
Wait for Task
Processor
Obtain Task Processor
Executing
Generate
subcontract
Wait for report
Complete
Contract
Terminated
Announced
Suspended
Make award
Bild 3: Ein Contract
Processor
Out
und sonst...
Verträge sind nicht verdrängbar (im Contract-Prozessor). Dies könnte man ändern, damit wichtige
Aufgaben ohne Verzögerung ausgeführt werden.
Hat ein Agent nichts zu tun, wäre es möglich, Bereit-Nachrichten an andere Agenten zu schicken. Diese
suchen dann angemessene Aufgaben aus den schon vorhandenen Ausschreibungen heraus und teilen sie
den Anbietern direkt zu.
Managern kann es sehr leicht passieren, dass sie für eine lange Zeit keine Angebote für ihre Ausschreibungen bekommen. Gründe dafür sind:
- alle Agenten sind beschäftigt
- die Aufgabe wird zu schlecht bewertet
- der Agent darf die Aufgabe nicht ausführen (Qualifizierungsangaben)
Um dies zu vermeiden, schickt ein Agent dem Manager sofort eine Nachricht, in der steht, warum er kein
Angebot machen möchte (z.B. "BUSY"). Oder Der Manager kann die Anforderungen lockern.
Direkte Aufgabenzuteilungen reduzieren Rechenzeit (diese können aber auch wieder begründet abgewiesen werden)
Wendet man nun das Contract Net auf das vorher erwähnte Beispiel an, so würde eine Nachricht vielleicht
so aussehen:
Nachrichtentyp: Aufgabenanfrage
An: alle
Von : Agent X
Empfänger muss haben: Granate, Zugang zu Raum bzw. davor
Aufgabendaten: Raum bei Position x,y,z
9
Kooperation mehrerer Computergegner
Contract Net Protocol
Alexander Altmayer
Pengi 2 - Ein Contract Net Beispiel
Das Beispiel soll die Anwendung des Contract Net an einem konkreten Fall zeigen. Pengi 2[5] ist ein
einfaches Spiel und eine Modifikation von Pengo[5]. In einem Uni-Praktikum wurde es in LISP implementiert. Das zweidimensionale, quadratische Spielfeld besteht aus gleich grossen Feldern, auf denen sich
Pinguine und Bienen bewegen (Bild 4). Zudem befinden sich auf dem Spielfeld mehrere Blöcke, die verschoben werden können. Die Pinguine versuchen, bestimmte Blöcke zusammenzuschieben. Die Bienen
versuchen, die Pinguine zu töten. Dies können sie tun, indem sie Blöcke auf Pinguine zu schiessen (das
können auch die Pinguine mit Bienen tun). Oder die Bienen hindern die Pinguine an Bewegungsmöglichkeiten,
wodurch die Pinguine ebenfalls sterben. Das Hindern an der Bewegung eignet sich ideal für die Kooperation - die Bienen können so versuchen, Pinguine einzukreisen.
Im Grossen und Ganzen richtet sich das System nach dem Ablauf des Contract Net Protocol:
- Überleben (ankommende Eisblöcke)
- hat man gerade keine Aufgabe und sichtet einen Pinguin, so wird es als Aufgabe ausgeschrieben, diesen
Pinguin einzukreisen; die Biene, die den Pinguin gesichtet hat, ist somit Manager
- eingehende Aufgaben werden nach der Distanz von der eigenen Position zur Position des Pinguins der
eingehenden Aufgabe sortiert; nähere Pinguine sind interessanter, da schneller erreichbar
- eingehende Angebote werden nach der Distanz von der eigenen Position zur Position des Anbieters
sortiert; Bienen, die näher an mir dran sind, können mir schneller helfen
- liegen keine Aufgaben vor und wurde kein Pinguin gesichtet, so führt man einen Zug in eine Zufallsrichtung aus.
Bild 4:
Ein PengiSpielfeld
Probleme des Contract Net Protocols:
Das Contract Net ist eher für Spiele mit wenigen Agenten geeignet (Rechenzeit kann dennoch recht hoch
werden).
Verträge werden evtl. schnell wieder aufgelöst, weil viel Unvorhergesehenes passieren kann (in einem
Szenario, indem es wichtig ist, dass eine Aufgabe von drei Agenten ausgeführt wird, löst sich der ganze
Vertrag leicht auf, wenn einer der Agenten ausfällt).
10
Kooperation mehrerer Computergegner
Aufgabenausführung
Alexander Altmayer
6. Aufgabenausführung
Nachdem ein adäquates Ziel bzw. Aufgabe gewählt wurde, muss dieses Ziel auch noch ausgeführt
werden.
Die eigentliche Ausführung des Tasks ist so gesehen eine Black Box, die Agenten können nur auf der
Basis dessen, was sie wissen, ihre momentanen Aktionen ausführen.
So könnte es sein, dass ein Teil des Teams eine Aufgabe nicht erledigen kann, weil durch die Ausführung eines Plans durch ein anderen Gruppenteil die Aufgabe nicht mehr ausgeführt werden kann.
Eine Vorausplanung ist nur bedingt oder kaum sinnvoll. Die Umgebungen sind bei Spielen in der
Regel so dynamisch, dass Voraussetzungen für bestimmte Aktionen verlorengehen. Meist sind die
Spiele und ihre Welt auf wenige Ziele und Bedingungen eingeschränkt, wodurch die Durchführung
der Aufgaben zum grössten Teil bekannt ist. Die Ausführung von vordefinierten Methoden reicht oft
aus und führt zu guten Ergebnissen. Man könnte sich überlegen, die Aufgabenausführung, die Methode sozusagen auszutauschen, wenn das Resultat nicht besonders gut war.
Lösungsmöglichkeiten: der derzeitige Chef sagt z.B. bei einem Shooter, wer welchen Feind übernimmt, wo die anderen in Position gehen. Sind dann die Befehle zu ungenau, gehen die Agenten nach
eigenem Gutdünken vor. Wenn sich die Bots einer Gegnergruppe annähern, dann nehmen die Bots
automatisch die besten Positionen ein. Falls eine Position schon von einem anderen Gruppenmitglied
besetzt ist oder er in der Schusslinie steht, dann nimmt der Bot die nächstbeste Position ein (Bild 5).
Bild 5: Bot 1 steht
in der Schusslinie
von Bot 3 - Bot 3
muss sich einen
neuen Platz
suchen
Andere einfache Möglichkeiten koordinierter Aktion wäre bei einem Strategiespiel z.B., wenn ein
Bogenschütze von Nahkampfeinheiten beschützt werden oder dass sich Einheiten nach ihrer Aufgabe anordnen (bei Age of Empires II [9] gibt es auch Formationen - die Einheiten selbst kooperieren
jedoch nicht miteinander). Oder die Kavallerie startet einen schnellen Angriff, zieht sich zurück und
danach greifen die Schwertkämpfer ein. Man spricht bei solchen Vorgenhensweisen von Spezialisierung und Aufgabenteilung.
Allgemein ist die Implementierung von Kooperation in einer Spiele-KI bei autonomen Systemen
weitaus komplexer als bei einer relativ festen Kommandostruktur. Der Programmierer hat bei festen
Kommandostrukturen selbst mehr Kontrolle über den Aktionsablauf. Was getan wird und wer es
bestimmt, wird dadurch einfach klarer.
11
Kooperation mehrerer Computergegner
Kooperation zwischen mehreren Gruppen
Alexander Altmayer
7. Kooperation zwischen mehreren Gruppen
Kooperation kann man auch eine Ebene über einzelnen Agenten ansetzen. Gerade bei Strategiespielen steckt hinter den Computergegnern ja ein virtueller Spieler, der selbst nicht auf dem Spielfeld
präsent ist (eine bestimmte Zivilisation, ein Staat, eine Gruppierung etc.). Die Einheiten befehligt er
allein, die Steuerung geschieht auf globaler Ebene. Die Einheiten selbst könnten aber auch zu einem
gewissen Grade autonom und kooperierend agieren (bisher in wenigen Spielen gut verwirklicht).
Damit würde sich vor allem ein menschlicher Spieler nicht mehr um alles kümmern müssen. Hierbei
muss der Spieler immer noch immer in alle Aktionen eingreifen können, so dass gänzlich ungewollte
Verhalten verhindert werden. Bei (Echtzeit-)Strategie würde man das etwa so umsetzen, dass man
Einheiten bestimmte Verhaltensmuster vorgeben kann (z.B. schneller Angriff, dann zurückziehen,
wie in Dark Reign [7], Bild 6). Alle Einheiten, die dasselbe Verhaltensmuster haben, würden sich
dann gruppieren und gemeinsam agieren (z.B. bei dem vorhin genannten Verhaltensmuster Aussuchen eines gemeinsamen Angriffsziels).
Bei Rollenspielen in der Art von Baldur's Gate [8] wäre es sowieso sinnvoll, sich selbst um alle
Aktionen der Charaktere zu kümmern - man kann die Zeit ja anhalten. Bei manchen Botspielen kann
man jetzt schon einige Befehle an diese erteilen. So ruft man etwa um Hilfe oder schickt Bots zurück
zur Basis. Aber auch die Computergegner untereinander würden durch gewisse Kooperation viel
besser werden. Bei Strategiespielen wie Age of Empires 2 [9] oder Starcraft [10] gibt es zwar Bündnisse, aber sie beschränken sich eigentlich auf einen Nicht-Angriffspakt. Haben die Gegner jeweils
eine gewisse Menge an Einheiten rekrutiert, werden diese auf den Gegner losgehetzt. Wenn zwei
Gegner einen Spieler gleichzeitig angreifen, dann ist das Zufall. Stattdessen könnten die Computergegner ihre Angriffe koordinieren, d.h. zumindest der Zeitpunkt des Angriffs. Oder sie sprechen ab,
welche Einheiten gebaut werden. Wenn einem Spieler für einen Angriff Lufteinheiten fehlen, dann
fordert er sie bei seinem Partner an.
Skripte, vorberechnete Verhaltensweisen z.B. für bestimmte Karten sind nicht unbedingt schlecht.
Solange die Verhaltensweisen der Gegner intelligent aussehen, ist dies eine elegante Methode, um oft
recht gute Resultate zu erzielen.
Die KI in Civilization [11] ist ebenfalls skriptgesteuert und funktioniert recht gut. Zivilisationen
schliessen Bündnisse miteinander, wenn der Spieler zu stark wird und tauschen Technologien aus.
Bild 6:
Dark Reign 2
12
Kooperation mehrerer Computergegner
Alexander Altmayer
8. Zusammenfassung und Ausblick
Kooperation in Computerspielen existiert noch nicht lange. Dementsprechend simpel sind die Implementierungen oder es sind gar keine vorhanden. Das liegt sicherlich auch daran, dass die Entwickler
zunächst Wert auf die Grafik legen und andere Teile der KI, wie etwa Wegeplanung - diese machen
schon einen grossen Teil der Rechenzeit aus. Allerdings ist das kein grosses Argument, wenn man
bedenkt, dass Kooperation mit recht einfachen Mitteln, wie etwa dem Contract Net Protocol, zu realisieren sind. Der Rechenaufwand ist gering, da keine Suchalgorithmen verwendet werden, höchstens
eine Sortierfunktion. Ein wichtiger Teil von Kooperation ist, dass die Individuen das gleiche Ziel haben.
In den meisten Spielen ist dies dadurch verwirklicht, dass die Computergegner zufällig den gleichen
Gegner haben. Bedingte Zusammenschlüsse wie der von schwächeren Gruppierungen gegen die starke
findet man eher selten. Zusätzlich zum gleichen Ziel (gleicher Gegner) müssen noch die Aufgaben
festgelegt werden. Entweder alle versuchen, mit den gleichen Mitteln zum Ziel zu kommen oder die
Aufgaben werden aufgeteilt - bei spezialisierten Einheiten ist dies besonders zu empfehlen. Schliesslich
müssen Ziele und Aufgaben miteinander abgesprochen werden. Dazu wird ein Nachrichtensystem verwendet. Behält man diese Punkte bei der Programmierung seiner Spiele-KI im Hinterkopf, kann ziemlich einfach gute Resultate zustande kommen.
13
Kooperation mehrerer Computergegner
Quellenangaben
Alexander Altmayer
9. Quellenangaben
Kapitel 1 Kooperation - wozu?
[1] http://www.wingcommander.com
Kapitel 4 Nachrichten
[2] Agents talking to Agents, Todd Sundsted, http://www.javaworld.com/javaworld/jw-09-1998/jw-09howto.html
[3] Game Progamming Gems, edited by Mark A. DeLoura, Charles River Media
Kapitel 5 Aufgabenbestimmung und Kapitel 5.1 Contract Net Protocol
[4] The Contract Net Protocol, R. G. Smith, IEEE Transaction on Computers 29(12) S1104-1113, veröffentlicht 1980
[5] Pengo, Pengi 2, http://www.classicgaming.com/vault/roms/arcaderoms.Pengo8623.shtml
Kapitel 6 Aufgabenausführung
[6] „Terrain Reasoning for 3D Action Games“, William van der Sterren, .pdf von http://cgf-ai.com
Kapitel 7 Kooperation mehrerer Gruppen
[7] http://www.activision.com/games/dr2/index2.asp
[8] http://www.interplay.com/bgate2/
[9] http://www.ageofempires2.de/
[10] http://www.starcraft.org/
[11] http://www.civfanatics.com/
14