Künstliche Intelligenz zur Verbesserung der Spiellogik

Wie soll das gehen?

Wann macht ein Spiel Spaß?

• Gute Ziele– Es muss für den Spieler ein Ziel existieren auf das er

zuarbeiten kann. • echte Entscheidungen• Keine Langeweile

– Es darf nicht passieren, dass der Spieler einen großen Anteil der Runden mit Warten verbringt.

• Leicht zu verstehen, schwer zu meistern• Absehbares Ende

– Multiplayerpartien sollten höchstens 2 Stunden dauern

Wie kann man Spielspaß messen?

• Gar nicht • Durch Massen an Beta-Testern

• Indem man Simulationen durchführt, die zu erwartendes Spielerverhalten emulieren

Was für Simulationen?

• Man nehme mehrere Künstliche Intelligenzen und lasse sie gegeneinander antreten.

• Diese Künstlichen Intelligenzen lernen und optimieren sich gegenseitig.

• Ihr Spielverhalten kann analysiert werden, wie das von Beta-Testern.

• Kein Mehraufwand: Eine KI brauchen wir für das Spiel sowieso.

• Prämisse: Die KI funktioniert ähnlich wie Spieler.

Blick von der anderen Seite:Wie funktioniert eine gute KI

• Atlantis ist von den Anforderungen her ähnlich zu Civilization von Sid Meier

• Deren KI funktioniert auf der Basis von Beratern• Jeder Berater behält einen bestimmten

Spielaspekt im Auge und macht Vorschläge, die optimal zu diesem Aspekt passen (sollen)

• Ein übergeordnetes Strategiemodul entscheidet, welchem Berater in welcher Situation Folge geleistet wird.

Berater

• Jeder Berater berechnet Züge, die seinem Ziel dienlich sind.

• Dabei bewertet er sich auch selbst, wie dringlich seine Vorschläge sind. – Beispiel: Eine militärische Einheit in einer unbefestigten Stadt zu

produzieren ist wichtiger, als in einer bereits befestigten.

• Vorteil: Taktisches Vorgehen ist meist recht übersichtlich und es können optimale Lösungen gefunden werden, ohne großen Berechnungsaufwand

• Nachteil: Jeder Berater hat nur seine eigenen Ziele im Auge, evtl. Synergien zu anderen Zielen fallen weg

Berater (Techniken)

• Die wichtigsten Techniken dabei sind:– Baulisten mit Gewinn-Verlustrechnung– Rollen für Einheiten– Taktische Analyse mit Alpha-Beta-

Suchbäumen

Baulisten

• Liste der dem Ziel förderlicher Gebäude, Einheiten, Gegenstände

• Der „Gewinn“, also der zu erwartende Nutzen, wird heuristisch bestimmt

• Der „Verlust“, also die zu erwartenden Kosten, werden ebenfalls bestimmt

• Die Heuristik sollte für alle Einrichtungen vergleichbar sein

• Gesucht ist die Aktion(en) deren Gewinn maximal ist und deren Verlust das erlaubte Budget nicht überschreitet

• Vorgeschlagene Methode: Greedyalgorithmus

Rollen

• Einheiten nehmen Rollen ein, um Ziele langfristig voranzutreiben

• Wichtig für Aufgaben, die länger als einen Zug dauern und/oder die einen hohen Spezialisierungsgrad erfordern

• Einheiten mit einer Rolle folgen vorgefertigten Handlungsmustern (Scouten, search&destroy, Strassen bauen, Gebäude bauen, etc. )

• Die Handlungsmuster sollten möglichst wenig komplex sein und ein klar definiertes Ziel haben

• Vorgeschlagene Methode: Skripte

Taktische Kriegsführung

• Militärische Rollen sind oft sehr komplex, da es viele Parameter zu beachten gilt– Gelände– Position der eigenen Truppen– Position der gegnerischen Truppen– Versorgung– Position schützenswerter Einrichtungen– Etc.

• Zusätzlich geht man davon aus, dass der Gegner ebenfalls versucht intelligente Züge zu finden

• Vorgeschlagene Methode: Alpha-Beta-Suchbäume (mit Pruning)

Ressourcenverteilungsproblem

• Gegeben: Eine Budgetschlüssel A und eine Gewinntafel B

• A gibt an zu welchen Anteilen Ressourcen in welche Ziele gesteckt werden (die Strategie)

• B gibt an, welche Ressourcen von wem benötigt werden um diese Ziele zu erreichen (die Beratervorschläge)

• Problem: – Wie kann der Budgetschlüssel fair verwirklicht

werden?

Ressourcenverteilungsproblem (Forts. )

• (fiktives) Beispiel: Wirtschaft und Militär sollen je 50 % der Ressourcen pro Runde bekommen. Das Einkommen beträgt 4 Holz und 5 Eisen. – Wer bekommt das „übrige“ Eisen?– Eine Windmühle kostet 3 Holz. Wann soll die gebaut

werden?– Ein Schwertmann kostet 4 Eisen. Wirtschaft will

dagegen hauptsächlich Windmühlen bauen. Was nun?

– Wirtschaft will eine Schmiede bauen (20 Holz, 30 Eisen). Geht das und wenn ja wie?

– Wie kann das berechnet werden ohne ein NP-vollständiges Knapsack-Problem zu lösen?

Grundlegende Ziele für gute Berater

• Schnelle oder zumindest skalierbare Rechenzeit• Eindeutige Zielstellung• Lieber zu viele als zu wenige

– Wenn ein Berater zwischen zwei Unterzielen hin- und hergerissen wirkt, dann lieber zwei Berater daraus machen

– Wenn ihr 2 Methoden habt ein Ziel zu verwirklichen, dann implementiert einfach beide

• Keine „Verschwendung“• Schnell anpassbar auf Spiellogikänderungen

Grundlegende Ziele für gute Rollen

• Haben ein klar definiertes Ziel, dem sie auch in der Bauliste zugeordnet sind.

• Kurze Berechnungszeit• Beenden sich selbst, wenn der Auftrag

beendet ist• Die Einheiten nehmen ihre Umwelt war

und reagieren darauf• Reagieren auf Gefahrensituationen mit

Rückzug

Ablauf

Spielspass

Genetische Algorithmen

Taktiken/Berater

Spiellogiksoll optimiert werden auf

Virtuelle Beta-Tester (lernt = optimiert sich selbst, um zu gewinnen)

Strategie

Spielstärke

werden optimiert auf

wird optimiert von

werden optimiert auf

Verteilt Ressourcen auf

wird optimiertdurch

benutzt

Genetische Algorithmen

• Sind bekannt dafür sich an spezielle Situationen anzupassen und gute Strategien zu finden.

• Entwickeln sich, man kann also so eine Art Lernkurve beobachten.

• Neigen dazu Systeme auszunutzen, sind daher gut dazu geeignet Schwachstellen zu finden.

Genetische Algorithmen (Funktionsweise)

• Eine Anfangspopulation wird ausgewählt (meist zufällig)

• Die Fitness der Individuen wird gemessen• Individuen mit hoher Fitness dürfen sich

fortpflanzen• Dies geschieht durch:

– Mutation (zufällige Veränderung)– Rekombination (2 Individuen werden gemischt)

• Der Kreis beginnt von vorne mit den Kindern der Elite

Fitnessfunktion

• Bestimmt die Richtung der Evolution• Daher sehr wichtig• Traditionell: möglichst hohe Punktzahl im Spiel

erreichen • Alternativ: Ranking

– Jeder gegen jeden, die Gewinner kommen weiter• Andere Alternative: Koevolution mit Konkurrenz

– Eine Gruppe erhält das Ziel möglichst viele Punkte zu sammeln

– Die andere Gruppe erhält das Ziel, das der andere möglichst wenig Punkte bekommt

Auswahl geeigneter Kandidaten

• Es gilt: Eliten fördern, ohne die „Artenvielfalt“ einzuschränken

• Oft benutzt wird das Tournament-Verfahren, bei dem zufällig ausgewählt wird, nur dass gute Kandidaten größere Chancen haben

A C

1/6 = 17%

3/6 = 50%

B

2/6 = 33%

• Beispiel für– A hat Fitness 3– B hat Fitness 1– C hat Fitness 2

Fortpflanzung

• Mutation:– Ein einzelner Wert wird zufällig verändert

• Rekombination:– 2 Individuen tauschen Chromosomen aus– Dies geschieht normalerweise in Blöcken– Werte werden kombiniert (Durchschnitt), oder vom

einen oder anderen Elternteil übernommen

Allgemeine Regeln für „Chromosomen“

• Sie sollten möglichst (mathematisch) unabhängig voneinander sein

• Jedes Chromosom sollte regelmäßig benutzt werden

• Jedes Chromosom sollte potenziell wichtig sein• Chromosomen sollten stetig sein,

– d.h. wenn der Wert A den Effekt a hat und Wert B den Effekt b, dann sollte ein Wert zwischen A und B in den meisten Fällen einen Effekt zwischen a und b haben.

Mehr zu Genetischen Algorithmen

• Mathematisch: Durchsucht einen Ergebnisraum mit stochastischen Mitteln nach lokalen Maxima.

• Der Raum ist i. A. sehr hochdimensional (= viele Chromosomen)

• Wenn die optimale Antwort A mit a Dimensionen auf einen Input B mit b Möglichkeiten gesucht wird, enthält der Suchraum a*b Dimensionen.

• Achtung! Bei B zählt jede Möglichkeit – bei einer 100x100 Karte mit je 4 Geländearten und

einer 2-dimensionalen Antwort sind das 80 000 Dimensionen

Beispiel: Ausweichen bei Asteroids

• Der Algorithmus soll fliegenden Asteroiden ausweichen:

• Input: – Aktuelle Drehrichtung des Schiffs (8 Möglichkeiten)– Richtung des nächsten Asteroiden (in Grad)– Geschwindigkeit des nächsten Asteroiden

(in 10 Stufen)• Output:

– Drehrichtung und Schub• Ergibt 57 600 Chromosomen/Dimensionen, von

denen die meisten nie benutzt werden• Sogar 207 360 000 Chromosomen, falls auch

der zweitnächste Asteroid betrachtet wird.

Besseres Ausweichen bei Asteroids

• Input: Nur die Richtung aus der der nächste Asteroid kommt. – 8 Richtungen aus Sicht des Raumschiffs

• Mögliche Reaktionen: Drehen, Schub– Drehen: -1: links, 0: nicht drehen, 1: rechts– Schub: -1: rückwärts, 0: kein Schub, 1: Schub

• Insgesamt 16 Dimensionen

vorn

Schub

vorn

Drehen

vornrechts Schub

vornrechts Drehen

rechts Schub

rechts Drehen

hintenrechts Schub

etc.

-1 1 -1 -1 -1 1 0

Reduktion der Dimensionalität

• Input vereinfachen– Unwichtiges weglassen– Abgeleitete Werte benutzen– Zustände benutzen, die durch Bewertung der Inputs

erreicht werden– In der Literatur wird der Input oft komplett

weggelassen und kommt nur indirekt in der Fitnessfunktion vor

• Output vereinfachen– Statt konkreter Befehle Ziele formulieren.

(wie bei Beratern)– Übersichtliche Probleme vorher lösen.

Zustände als vereinfachte Inputs

• Anstatt immer allen Input zu betrachten, werden Zustände definiert, die vom Input abhängen

• Es gibt dann n Zustände, sowie eine vom Input abhängende Zustandsänderungsfunktion

• Beispiel: Der Algorithmus soll sich je nach Temperatur anders verhalten. Also wird den Zuständen jeweils eine Zahl zugeordnet:– Zustand 1: -5– Zustand 2: 15

• Der Zustand, der näher dran liegt gewinnt• Vorteil: Die Anzahl der Chromosomen explodiert nicht

mehr und die Reaktionen entwickeln sich schneller. • Nachteil: Es werden nicht mehr alle Spezialfälle

abgefangen.

Was kann ich mir unter den Zuständen vorstellen?

• Zustände sind veränderte Strategien, die auf verschiedene Gegebenheiten reagieren.

• Beim Schach: Eröffnung, Mittelspiel, Endspiel. • Bei Strategiespielen: Aufbau, Forschung,

Militärisches Rüsten, Angriff, Verteidigung, …• Gute Inputs sind also Zeit, freie Ressourcen,

Kriegszustand, Einheiten des Gegners, Position in der Rangliste, Bedrohungsgrad, …

Zustandsänderungsfunktion

• Die Funktion wird komplexer, je mehr verschiedene Inputarten betrachtet werden müssen.

• Was bedeutet „näher dran liegen“ bei vielen Parametern?

• Gibt es Konstellationen, in denen Zustände gar nicht mehr, oder nur höchst selten erreicht werden?

• Sollten Zustandsänderungen forciert, oder vermieden werden?

• Sollte man eine bestimmte Reihenfolge festlegen, wie bei Automaten?

• Wie viel Freiraum lasse ich dem genetischen Algorithmus?

Wie sieht nun das Genom aus?

• Man schreibe eine KI und lasse alle Parameter, die nicht logisch abgeleitet werden können, von einem genetischen Algorithmus bestimmen

• Das Genom enthält also– n Strategien für n Zustände– Jede Strategie enthält pro Berater eine

Ressourcenverteilung– Die Parameter der Zustandswechselfunktion– Globale Parameter für taktisches Verhalten, etc.

Literatur

• Allgemein:– http://www.atlantis.yafclan.de - das Wiki für Atlantis– http://www.jesperjuul.net/text/gameplayerworld/ -

Was ist ein Spiel…– http://c-evo.org/text.html und http://www.freeciv.org/

sind frei verfügbare Spiele und recht ähnlich zu Atlantis (von der KI her)

– http://www.gamasutra.com/ für alles zum Thema Spieleentwicklung

– Wikipedia – zu allen Themen (englisch und deutsch)– www.google.de – mit filetype:ppt für Einführungen,

filetype:pdf für wissenschaftliche Paper– www.citeseer.edu – für wissenschaftliches

Mehr Literatur

• Genetische Algorithmen (genetic algorithm)– http://www-personal.umich.edu/~axe/

research/Evolving.pdf – Für die grundlegende Idee – http://www.cs.vu.nl/~gusz/ecbook/slides/

Genetic_Algorithms.ppt – Gute Einführung

• Alpha-Beta Search– http://www.cis.upenn.edu/~matuszek/cit594-2003/

Lectures/38-alpha-beta.ppt - Gute Einführung

Noch mehr Literatur

• Programmieren– Die Coding Standards des Atlantis Projekts– „C++ für Dummies“– JNI – Java Native Interface– „The Pragmatic Programmer. From

Journeyman to Master. “ Von A. Hunt, D. Thomas, W. Cunningham

– http://www.pragmaticprogrammer.com/ - Diverse der Artikel dort (nicht die mit Ruby)

– Bücher von Tom DeMarco – Für Teamleiter