Entwicklung von Spielstrategien mit koevolutionären Ameisenalgorithmen

Page 2

Kapitel 1

Einleitung

1.1 Aufgabenstellung

Unter dem Begriff naturanaloge Optimierungsverfahren fasst man verschiedene (Meta-)Heuristiken ¹ zur L¨ osung von Optimierungsaufgaben zusammen, die aus der Biologie bekannten Mechanismen nachempfunden sind. Bekannte Beispiele sind z.B.:

• Genetische Algorithmen ([12])

• Neuronale Netze ([13])

• Simulated Annealing ([21])

• Ameisenalgorithmen

• Koevolution¨ arer Wettbewerb (competetive coevolution)

Gegenstand der vorliegenden Arbeit ist eine Kombination der beiden letztgenannten Verfahren, was zum derzeitigen Wissensstand ein Novum darzustellen scheint.

In den n¨ achsten beiden Abschnitten werden diese beiden Heuristiken kurz vorgestellt, bevor ein solches Verfahren zur Entwicklung von Spielstrategien f¨ ur Nim (Kapitel 2) bzw. Tic-Tac-Toe (Kapitel 3) beschrieben wird.

1.2 Schwarmintelligenz mit Ameisenalgorithmen

Mit sog. Ameisenalgorithmen versucht man den Mechanismus der in der freien Natur oft zu beobachtenden ” Ameisenstraßen“ zur L¨ osung von Optimierungsaufgaben nachzuahmen (vgl. auch [7], [9]): dieses Ph¨ anomen entsteht dadurch, dass einzelne Ameisen auf der Nahrungssuche einen Duftstoff (sog. Pheromon) ausscheiden, der andere Ameisen anzieht. Gibt es zwischen Nest und Futterquelle mehrere m¨ ogliche Wege, so wird mit der Zeit auf dem k¨ urzesten Pfad eine h¨ ohere Pheromonkonzentration als auf den anderen vorherrschen, so dass

¹ zum Begriff der Heuristik siehe [15], zum Begriff der Meta-Heuristik siehe [8]

Page 6

Kapitel 2

Nim-21

2.1 Beschreibung des Spiels

Bei dem Spiel Nim liegen zu Beginn k ^max = 21 Streichh¨ olzer ¹ auf einem Tisch, jeder der beiden Spieler muß abwechselnd ein bis drei Streichh¨ olzer nehmen, wobei er auf seinen Zug nicht verzichten darf. Der Spieler, der das letzte Streichholz nimmt, hat verloren.

Das Spiel ist nicht fair, denn — wie im ¨ ubern¨ achsten Abschnitt noch gezeigt

wird — der Spieler mit dem ersten Zug hat bei optimaler Spielweise seines Gegners keine M¨ oglichkeit zu gewinnen.

F¨ ur unsere Zwecke zeichnet sich dieses Spiel durch folgende Vorteile aus:

• Die Regeln sind leicht verst¨ andlich

• Die optimale Strategie ist bekannt und ohne weiteres nachvollziehbar, so dass wir die Ergebnisse neuer L¨ osungsverfahren gut beurteilen k¨ onnen

• Aufgrund der begrenzten Anzahl an m¨ oglichen Spielsituationen und sich daraus ergebenden Z¨ ugen scheint Nim-21 ohne weiteres mit einem Amei-senalgorithmuses modellierbar

• Die Kodierung der einzelnen Spielsituationen ist trivial, es gibt keine symmetrischen F¨ alle oder ¨ ahnliches zu beachten

2.2 Notation:

Im weiteren werden wir die Anzahl der noch auf dem Tisch liegenden Streichh¨ olzer als Spielsituation k auffassen: k ∈ {0, . . . , 21}.

¹ Es gibt auch Beschreibungen von Nim, die von anderen Werten f¨ ur k ^max ausgehen, etwa k ^max = 15 oder k ^max = 27. Wir beschr¨ anken uns im weiteren auf die Variante mit 21 Streichh¨ olzer, wobei das weitere Vorgehen prinzipiell auch mit anderen Werten f¨ ur k ^max m¨ oglich w¨ are. Um Verwechslungen auszuschließen, bezeichnen wir das Spiel im weiteren deshalb mit Nim-21. Weitere Varianten von Nim werden noch in Abschnitt 2.9 (Seite 20) kurz besprochen

Page 7

Als Strategie eines Spielers i ∈ {1, 2} bezeichnen wir eine Funktion s i (k), die angibt, wieviele H¨ olzer der betreffende Spieler bei vorliegen der Situation k vom Tisch nimmt. Es gilt also s i (k) ∈ {1, 2, 3} mit der Einschr¨ ankung s i (k) ≤ k (es kann sich keine negative Anzahl von Streichh¨ olzern im Spiel befinden). Spieler 1 sei immer der Spieler, der den ersten Zug macht.

2.3 Optimale Strategie

Die optimale Strategie des zweiten Spielers lautet wie folgt:

s ^∗ 2 (k) =

Hierbei sei u ∈ {1, 2, 3} eine ganzzahlige Zufallsvariable mit beliebiger Verteilung (etwa: Gleichverteilung).

Der Spieler w¨ ahlt gem¨ aß dieser Strategie seinen Zug immer so, dass m¨ oglichst einer der Zust¨ ande k = 4 · n + 1 eintritt (n ∈ {0, 1, 2, 3, 4, 5}):

K ^∗ = {1, 5, 9, 13, 17, 21} (2.2)

Um die Optimalit¨ at dieser Strategie einzusehen, betrachten wir zun¨ achst den Fall, dass sich noch k = 5 = 4 · 1 + 1 (also n = 1) Streichh¨ olzer auf dem Tisch befinden und Spieler 1 an der Reihe ist: egal welche Wahl er trifft, wir k¨ onnen unsere Wahl stets so treffen, dass nur das letzte Streichholz ¨ ubrig bleibt, womit der Gegner verloren h¨ atte: nimmt er nur eines, so nehmen wir drei, nimmt er zwei, so nehmen wir ebenfalls zwei, nimmt er drei, so nehmen wir nur ein Streichholz. Ist unser Gegner also bei k = 5 am Zug, so hat er praktisch bereits verloren.

Betrachten wir den n¨ achsten Zustand k = 9 = 4 · 2 + 1 (n = 2): sieht sich der Gegner dieser Spielsituation gegen¨ uber, so k¨ onnen wir unseren darauffolgenden Zug so gestalten, dass nur noch 5 H¨ olzer ¨ ubrig bleiben, womit wir —

wie im vorangegangenen Absatz gezeigt — als Sieger aus der Partie hervorgehen.

Analog laufen die ¨ Uberlegungen zu n = 3 (13 Streichh¨ olzer), n = 4 (17 Streichh¨ olzer) und schließlich n = 5 (21 Streichh¨ olzer), was aber dem Aus-gangszustand k ^max entspricht — hat der Gegner den ersten Zug, so ist unsere Strategie optimal (der Fall II in Gleichung 2.1 mit der randomisierten Entscheidung tritt ¨ uberhaupt nicht auf), wir k¨ onnen nicht verlieren, unabh¨ angig von der Entscheidungen des Gegners: das Spiel ist nicht fair.

Sind wir in der ungl¨ ucklichen Lage, das Spiel er¨ offnen zu m¨ ussen, so kann der Fall II durchaus eintreten — wir haben nur im Fall eines Fehlers (also einer Entscheidung, die von der optimalen Strategie abweicht) unseres Gegners eine Chance zu gewinnen. K¨ onnen wir durch einen Zug nicht erreichen, dass danach noch k ∈ K ^∗ Streichh¨ olzer auf dem Tisch verbleiben, so randomisieren wir unsere Entscheidung, wobei wir aber m¨ oglichst nicht das letzte Streichholz vom Tisch nehmen.

Page 8

2.4 Umsetzung

2.4.1 Pheromonmatrizen

Da wir die Idee des koevolution¨ aren Wettbewerbs anwenden wollen, ben¨ otigen wir zwei Populationen A und B mit jeweils m Ameisen ² : |A| = |B| = m. Jede uber eine eigene Pheromonmatrix: τ ^A und τ ^B , wodieser Populationen verf¨ ugt ¨

bei die Ameisen aus Population A keinen Zugriff auf τ ^B haben und umgekehrt.

W¨ ahrend des Spiels kann ein Spieler (eine Ameise) mit k ^max = 21 verschiedenen Spielsituationen k konfrontiert werden ³ : jede dieser Spielsituationen wird in den Pheromonmatrizen durch eine Zeile repr¨ asentiert; zu jeder Situation gibt es bis zu 3 m¨ oglichen Z¨ uge (Anzahl der zu nehmenden Streichh¨ olzer), jeder Zug wird durch eine Spalte repr¨ asentiert: die beiden Pheromonmatrizen haben also jeweils 21 × 3 Komponenten.

Weiter seien die einzelnen Elemente einer Matrix τ i kl ∈ [0, 1] zeilenweise auf den Wert 1 normiert:

^! τ i k1 + τ i k2 + τ ⁱ = 1 k ∈ {1, . . . , k ^max }, i ∈ {A, B} (2.3) k3

2.4.2 Strategie einer Ameise

Vor Beginn eines Turniers ⁴ erzeugt jede Ameise aus den beiden Populationen unter Verwendung der jeweiligen Pheromonmatrix eine Strategie, welche f¨ ur alle Partien, die die Ameise im bevorstehenden Turnier zu bestreiten hat, verwendet wird. Die Strategie s i u der u-ten Ameise aus Population i gibt f¨ ur jeden m¨ oglichen Zustand s eine zul¨ assige Entscheidung an und wird unter Verwendung einer [0, 1]-verteilten Zufallsvariable q wie folgt berechnet:

wobei L ∈ N (k) zuf¨ allig gem¨ aß folgender Wahrscheinlichkeiten bestimmt wird:

Hierbei sei N (k) die Menge der zul¨ assigen Z¨ uge in einer Spielsituation k:

N (k) ∈ {1, . . . , min{k, 3}} (2.6)

Es soll also verhindert werden, dass eine Entscheidung besagt, es seinen mehr Streichh¨ olzer zu nehmen als noch im Spiel sind.

² unterschiedliche Populationsst¨ arken k¨ onnten z.B. dann Sinn machen, wenn unterschiedliche Anpassungsgeschwindigkeit modelliert werden sollen; dieser Fall wird im weiteren aber nicht betrachtet

³ den Fall k = 0 brauchen wir nicht zu betrachten, denn hier ist das Spiel schon entschieden, es ist keine Entscheidung mehr zu treffen (Terminalzustand)

⁴ mit Turnier sei im weiteren eine Zahl von m · m Einzelspielen (Duelle) bezeichnet: jede Ameise aus Population A tritt gegen jede aus Population B an

Page 9

Der Parameter q 0 , typischerweise etwa auf 0.1 gesetzt, steuerte das Explorationsverhalten des Algorithmuses. Je h¨ oher sein Wert ist, desto h¨ aufiger wird Fall I in Formel 2.4 eintreten, es wird also gerade die Entscheidung getroffen, f¨ ur die der Pheromonwert in Zeile k sein Maximum annimmt, der L¨ osungsraum wird nicht weiter erforscht.

2.4.3 Pheromon-Update

Nach jedem Turnier f¨ uhren wir entsprechend der Ergebnissen und Z¨ ugen der einzelnen Partien Updates auf den beiden Pheromonmatrizen durch: hierzu werden w¨ ahrend des Turniers folgende Ergebnisse gespeichert (i, j ∈ {A, B}, i = j, u, v ∈ {1, . . . , m}):

• Die Menge der Spielsituationen z i uv , in denen Ameise u aus Population i im

Spiel gegen Ameise v aus der gegnerischen Population einen Zug machen mußte: z i uv ⊂ {1, . . . , k ^max } (2.7)

Zur Veranschaulichung betrachten wir die Spielpartie zwischen den beiden Ameisen u = 1 aus Population A und v = 2 aus Population B in Tabelle 2.1; die Mengen z ^A 12 und z ^B 21 w¨ urden also wie folgt aussehen:

Tabelle 2.1: Beispiel einer Spielpartie zwischen zwei Ameisen

• Die Menge b i u der von Ameise u aus Population i besiegten Gegner aus Population j: b i u ⊆ {1, . . . , m} (2.8)

• Die Menge der gegnerischen Ameisen d i u , gegen die Ameise u aus Population i verloren hat: d i u ⊆ {1, . . . , m} (2.9)

Im weiteren wird uns nur die M¨ achtigkeit |d i k | dieser Menge interessieren.

Page 11

beiden anderen Duellen ebenfalls unterlegen ist. Entsprechend ergeben sich die weiteren Werte wie folgt:

α ^A 2 =

F¨ ur jeden von Ameise u aus Population i besiegten Gegner v ∈ b u i aus

Population j wird f¨ ur alle in dieser Partie aufgetretenen Spielsituationen z i

uv

folgender Update auf die Pheromon-Matrix τ ⁱ vorgenommen:

Hierbei ist c ∈ R + ein noch festzulegender Parameter ⁵ . Die Division durch die Anzahl der Spielsituationen |z i
gegen¨ uber k¨ urzeren

¨ ubervorteilt werden: ohne diesen Term w¨ urde eine Zugfolge z.B. mit der L¨ ange 5 ungerechtfertigerweise mehr Pheromon in die Matrix updaten d¨ urfen als eine der L¨ ange 4. Abschließend normieren wir noch die einzelnen Zeilen von τ ⁱ , so dass Bedingung 2.3 erf¨ ullt ist:

Bedingt durch diese Normierung k¨ onnen wir auf einen Schritt, in dem Pheromon an bestimmten Stellen der Matrix verdunstet (wie z.B. in [11]) oder von den Ameisen gefressen wird, verzichten.

2.4.4 Konvergenz der Pheromon-Matrix

Bei der praktischen Erprobung des Algorithmuses sind wir nat¨ urlich in erster Linie daran interessiert herauszufinden, ob die Ameisen die optimale Strategie s ^∗ (k) (vgl. Formel 2.1) finden. Jede Zeile k ∈ K mit

(k − 1) mod 4 = 0 (2.14)

sollte in Spalte s = s ^∗ (k) den h¨ ochsten Wert haben, welcher 1.0 sehr nahe ist, etwa τ i ks = 1 − ε 1 , wobei ε 1 eine sehr kleine, noch genauer zu bestimmende positive Zahl reelle Zahl ist. In den beiden verbleibenden Spalten ν 1 und ν ² (ν 1 , ν 2 ∈ {1, 2, 3}, ν 1 = s , ν 2 = s , ν 1 = ν 2 ) muß der Wert dann ann¨ ahernd 0.0 sein, also τ i kν1 = ε 2 und τ i kν2 = ε 3 . Wir bezeichnen die Zeile k der Pheromon-Matrix τ ⁱ als konvergiert, wenn gilt:

ε ≥ max{ε 2 , ε 3 } ˆ (2.15)

Die Konstante ˆ ε sei hierbei eine als Parameter fest vorgegebene sehr kleine Zahl, etwa ˆ ε = 0.01.

⁵ Der Parameter c entspricht in seiner Funktion damit in etwa dem ρ im herk¨ ommlichen Ameisenalgorithmus lt. [11] zur Steuerung des Pheromon-Updates

Page 12

2.4.5 Ablauf des Algorithmus

Insgesamt betrachtet l¨ aßt sich der Algorithmus im Pseudo-Code wie in Abbildung 2.1 darstellen. In Abbildung 2.2 sind die einzelnen Parameter zur Konfiguration des Algorithmuses noch einmal zusammengefaßt.

Abbildung 2.2: die verschiedenen Parameter des Algorithmus im ¨ Uberblick

2.5 Implementierung in Java

Der in diesem Kapitel beschriebene Algorithmus wurde mittels Java umgesetzt. Ausschlaggebend war hierf¨ ur im wesentlichen, dass die Anbindung einer kleinen graphischen Benutzeroberfl¨ ache zur Visualisierung der Pheromon-Matrizen angestrebt wurde, was sich mittels der Java-Standard-Bibliothek f¨ ur graphische Benutzeroberfl¨ achen — Swing — besonders einfach verwirklichen l¨ aßt. F¨ ur sehr rechenintensive Anwendungen mag die Performanz von Java vielleicht zu schwach sein, beim vorliegenden Fall mit den recht klein dimensionierten Pheromon-Matrizen (21 × 3) war dies aber kein Problem. Im Anhang A ab Seite 33 wird der Aufbau und die Bedienung der Implementierung genauer beschrieben.

2.5.1 Visualisierung

Die Fenster der graphischen Benutzerober߬ ache (siehe Abbildung 2.4) sind vollkommen passiv, dienen also nur der Visualisierung des Zustandes der Pheromon-

Page 17

Eine Population spielt immer mit der optimalen Strategie

Spielen die Ameisen einer Population von der ersten Runde an mit der optimalen Strategie, so finden die Ameisen der gegnerischen Population ¨ uberraschenderweise immer noch die optimale L¨ osung: sie gewinnen (und zwar ausschließlich als Zweitspieler, denn der Erstspieler verliert — wie zu Beginn des Kapitels erkl¨ art — immer gegen die optimale Strategie) zwar nur sehr wenige Einzelspiele, diese Siege werden aber dank der verwendeten Update-Strategie (siehe Abschnitt 2.4.3, Formel 2.11) sehr stark gewichtet.

2.7 Algorithmus mit nur einer Population

Das beschriebene Verfahren kann mit einigen kleinen ¨ Anderungen auch mit nur

einer Ameisen-Population angewendet werden: hierbei spielen dann die Ameisen einer Population untereinander gegeneinander, wobei jede Ameise auch gegen sich selbst spielt, damit wir wieder auf m ² Spiele pro Iteration kommen, die Ergebnisse sind sonst nicht ohne weiteres miteinander vergleichbar.

In Abbildung 2.10 sind die beiden Ans¨ atze miteinander verglichen: Der Al-gorithmus mit einer Population konvergiert schneller.

Page 22

Kapitel 3

Tic-Tac-Toe

3.1 Beschreibung des Spiels

Bei Tic-Tac-Toe setzen die zwei Spieler stets abwechselnd ihre Markierung Kreis“ auf ein quadratisches Spielfeld mit 3 × 3 Feldern; gewon- Kreuz“ und ”

”

nen hat derjenige, der zuerst drei Markierungen in einer vertikalen, horizontalen oder diagonalen Reihe auf dem Spielbrett hat. Das Spiel kann auch unentschieden enden, wenn alle 9 Positionen besetzt sind, aber keiner der Spieler eine Reihe hat. In Abbildung 3.1 ist ein Beispiel f¨ ur ein Spielfeld dargestellt.

3.2 Optimale Strategie

Auch f¨ ur Tic-Tac-Toe existiert eine optimale Strategie: spielen beide Spieler nach dieser, so endet das Spiel stets unentschieden. Leider ist dieser Strategie nicht so einfach wie bei Nim-21 herzuleiten, man kann sie auch nicht als geschlossene Regel formulieren.

Die Herleitung der optimalen Strategie wird anhand des Minimax-Algorithmus durchgef¨ uhrt (siehe auch [14], [15]): ausgehend von einer gegebenen Spielsituation bauen wir einen Entscheidungsbaum f¨ ur alle m¨ oglichen weiteren Zugfolgen.

Page 24

sind die Nachfolgerpfeile stattdessen gegnerische Z¨ uge, so wird er mit dem Minimum aller Nachfolgerknoten bewertet — dieses Vorgehen geht also davon aus, dass der Gegner stets optimal zieht. Da ein Maximum oder Minimum nicht unbedingt eindeutig bestimmt sein muss, gibt es mehr als eine optimale Strategie.

Mit diesem Verfahren k¨ onnen prinzipiell auch anspruchsvollere Spiele wie etwa Schach oder Dame gel¨ ost werden: allerdings w¨ achst der Suchbaum bei diesem Spielen so stark, das er nur teilweise aufgebaut werden kann ³ . Bei Tic-Tac-Toe hingegen ist die Anzahl der m¨ oglichen Z¨ uge so vergleichsweise gering, dass immer problemlos ein vollst¨ andiger Suchbaum aufgebaut werden kann.

Der Minimax-Algorithmus kann durch den Einsatz sog. oberer und unterer Schranken weiter verbessert werden (sog. α-β-Pruning, siehe [14]), was hier aber nicht weiter betrachtet werden soll, da f¨ ur unser Vorgehen die optimale Strategie nur einmal berechnet werden muß.

3.3 Notation

Jede Spielsituation X wird durch die Angabe der Belegung aller 9 Brettpositionen beschrieben:

X ∈ {(x 0 , x 1 , . . . , x 8 )|x i ∈ {0, 1, 2}} (3.1)

Hierbei sind die einzelnen Stellen wir folgt kodiert:

Die Zuordnung der Indices 0 bis 8 erfolgt dabei in Leserichtung (siehe Abbildung 3.3).

Abbildung 3.3: Zuordnung Indices zu den Spielfeldpositionen

Der Zustand aus Abbildung 3.1 wird also wie folgt dargestellt:

Spielst¨ arke des Computers beeinflußt