Lade Inhalt...

Genetische Algorithmen in der Praxis

Bachelorarbeit 2009 63 Seiten

Informatik - Programmierung

Leseprobe

Inhaltsverzeichnis

1 Einleitung
1.1 Motivation
1.2 Begriffsklärung, theoretisches Fundament

2 Objekt der Optimierung
2.1 Das Spiel „Qubic“
2.1.1 Spieltheoretische Begründung
2.1.2 Berechenbares Nash-Gleichgewicht
2.1.3 Min-Max-Algorithmus
2.1.4 Stellungsbewertung

3 Programmierung des Spiels
3.1 Allgemeiner Aufbau einer Brettspielsimulation
3.2 Stellungsbewertung

4 Messen der Spielstärke
4.1 Standardspieler
4.1.1 Totale Ordnung für Standardspieler
4.2 Elo-Punktesystem
4.3 Zuordnung der Spielstärke zur Suchtiefe
4.3.1 Spieler mit Spielstärken in Hunderterschritten
4.3.2 Spieler mit dazwischenliegenden Spielstärken
4.4 Ressourcenverbrauch und weitere Erkenntnisse

5 Anwendung genetischer Algorithmen
5.1 Chromosom als Gewichtsvektor
5.1.1 Qubic-Gewinnlinien
5.1.2 Skalarproduktes von Matrizen
5.1.3 Chromosomenmatrix
5.2 Genetische Operatoren
5.2.1 Mögliche Arten der Fortpflanzung
5.2.2 Die verwendeten Methoden

6 Drei Versuchsreihen
6.1 Generationszyklen mit beschränkten Chromosomen
6.1.1 Entwicklung der Spielstärken
6.1.2 Entwicklung der Chromosomen
6.1.3 Hoher S elektionsdruck
6.2 Generationszyklen mit freien Chromosomen
6.3 Kontinuierliche Verbesserung mit freien Chromosomen

7 Schlussbemerkungen
7.1 Kontinuierliche Verbesserung schlägt Generationenmodell
7.2 Unerwartete Verteilung der Werte innerhalb der „guten“ Chromosomen

Literaturverzeichnis

Abbildungsverzeichnis

Tabellenverzeichnis

Abkürzungsverzeichnis

1 Einleitung

1.1 Motivation

In dieser zweiten Bachelorarbeit soll das theoretische Wissen, das in der ersten Arbeit (Schölnast, 2009) aufbereitet worden ist, in der Praxis erprobt werden.

1.2 Begriffsklärung, theoretisches Fundament

In (Schölnast, 2009) wurden die Begriffe „genetische Algorithmen“ „Evolutionsstrategien“ und „genetische Programmierung“ bereits ausführlich behandelt, dennoch sollen hier in der gebotenen Kürze die wesentlichen Merkmale dieser Fachgebiete skizziert werden.

Genetische Algorithmen (GA)

Genetische Algorithmen sind Verfahren, die zur Lösung von Such- und Optimierungs­problemen dienen. Der Erfolg der Genetischen Algorithmen liegt in der Nachahmung der biologischen Evolution, die selbst ein fortwährender Optimierungsprozess ist. Zu diesem Zweck bedient sich der Genetische Algorithmus der Evolutionsmechanismen

- Genetische Variation

Erzeugung neuer Erbsubstanz durch Rekombination und Mutation

- Selektion

Eliminierung oder Weitergabe der Erbsubstanz

- Zufälle

Die Individuen einer Population befinden sich ständig in einem Kampf ums Dasein. Träger vorteilhafter Merkmale überleben mit höherer Wahrscheinlichkeit (survival of the fittest) und können somit ihre Anlagen an die nächste Generation weitergeben. Folglich besitzt die Folgegeneration die Gene der “besseren “ Eltern. Diese Idee nutzt der Genetische Algorithmus, indem er mit einer Population von Individuen, welche je eine mögliche Lösung des Problems repräsentieren, arbeitet.

(Czogalla, 2005)

Vorbild dieser Methode ist, wie oben von Fr. Czogalla bereits erwähnt, die natürliche Evolution. Dabei wird vor allem auf die folgenden Gesichtspunkte der Evolution Bezug genommen:

- Individuen existieren nicht für sich alleine, sondern sind Teil einer Population, bestehend aus mehreren ähnlichen aber nicht gleichen Individuen derselben Art.
- Jedes einzelne Individuum zeigt gegenüber seiner Umwelt ein Verhalten, das für dieses Individuum typisch ist. (Phänotyp)
- Dieses Verhalten wird geprägt von internen Merkmalen, die dieses Individuum bei seiner Erzeugung geerbt hat. (Genotyp)
- Die Struktur dieser internen Merkmale ist für alle Individuen einer Art gleich. Diese internen Merkmale werden als genetischer Code, Chromosomen oder Gene bezeichnet.
- Die Individuen können aufgrund ihres genetisch vorprogrammierten Verhaltens mit verschiedenen Umwelteinflüssen besser oder schlechter fertig werden. Davon, wie gut diese Fähigkeiten ausgeprägt sind, hängt es ab wie lange ein bestimmtes Individuum überlebt, und davon wiederum hängt ab, ob bzw. wie häufig sich dieses Individuum fortpflanzen kann.
- Individuen, die sich innerhalb ihrer Population besser behaupten als andere, werden also mehr Nachkommen in die Welt setzen. Daraus folgt, dass jedes Individuum der nächsten Generation mit größerer Wahrscheinlichkeit sein Erbgut von fitten Eltern geerbt hat als von Eltern, die kaum in der Lage waren mit den Umweltbedingungen fertig zu werden.

Diese Punkte gelten sowohl für die natürliche Evolution als auch - mit gewissen Anpassungen - für die genetischen Algorithmen. Daher kann allein aus diesen Merkmalen der Evolution das Grundgerüst der genetischen Algorithmen abgeleitet werden:

1. Urzeugung: Erzeuge eine Gruppe von Individuen, die den Startpunkt des Evolutions­zyklus darstellen (Generation 1). Dieser Schritt entspricht in der Natur dem Abschnitt vom Entstehen der ersten Lebensformen bis hin zu einem Punkt, ab dem die Vorgänge der Evolution beobachtet werden sollen, also bis zu einer Population, die man als Startpunkt ansehen kann. Als Beispiel kann eine Gruppe von Tieren (z.B. Hunde) angenommen werden, die gemeinsam in einer Umgebung ausgesetzt werden, in der es bis dahin keine anderen Individuen dieser Art vorhanden waren (z.B. Australien).
2. Fitness: Die Individuen der Generation 1 werden dem Druck der Umweltbedingungen ausgesetzt. Je nachdem wie gut sie sich dabei behaupten wird ihnen eine niedrige oder eine hohe Fitness zugebilligt.
3. Selektion: Die Höhe seiner Fitness entscheidet darüber, mit welcher Wahrscheinlich­keit sich ein Individuum fortpflanzen kann. Dabei ist nicht nur die eigene Fitness ausschlaggebend, sondern vielmehr der Unterschied zwischen der eigenen Fitness und der Fitness der anderen Individuen.
4. Fortpflanzung: In der Natur kommen zwei grundlegende Arten der Fortpflanzung vor: Geschlechtliche und ungeschlechtliche. Bei der geschlechtlichen Fortpflanzung vereinen zwei Elternteile ihr Erbgut um daraus das Erbgut eines neuen Individuums zu erzeugen. Bei der ungeschlechtlichen Fortpflanzung entsteht das neue Individuum aus dem Erbgut von nur einem Vorfahren. Auf die Einzelheiten dieser Vorgänge wird an späterer Stelle genauer eingegangen.
5. Wiederholung: Die Individuen der neuen Generation müssen sich wieder ihrer Umwelt stellen, das heißt, auch ihnen wird eine Fitness zugeordnet, die wiederum ausschlaggebend bei der Selektion ist, und daher über die Zusammensetzung der darauffolgenden Generation entscheidet. Die Schritte 2 bis 4 werden also in einem fortwährenden Zyklus durchlaufen.
6. Ende: Die Natur kennt kein Ende der Evolution. Daraus folgt, dass die genetischen Algorithmen aus sich heraus keine Ende-Bedingung kennen. Insbesondere heißt das aber auch, dass es kein Kriterium gibt, anhand dessen man erkennen kann, dass das endgültige Optimum erreicht worden ist. Es gibt nicht einmal eine Garantie dafür, dass dieses Optimum jemals erreicht werden kann.

Schlimmer noch: Nicht einmal die Existenz eines globalen Optimums kann vorausgesetzt werden, da Fälle denkbar sind, wo zu jeder möglichen Ausprägung der genetischen Ausstattung ein Individuum mit einer anderen Ausstattung gefunden werden kann, das besser abschneidet als das erste.

Insbesondere in dem in dieser Arbeit beschriebenen Beispiel eines Brettspiel­programmes ist es sogar ausgesprochen unwahrscheinlich, dass man ein Individuum finden kann, das gegen alle anderen Individuen gewinnen kann. Wahrscheinlicher ist, dass es geschlossene Ketten von Individuen gibt, wobei Individuum A immer gegen B gewinnt, B immer gegen C und C schließlich immer gegen A.

Dieses Manko lässt sich aber durch eine andere Zielsetzung vermeiden: Anstatt nach einem Individuum zu suchen, das gegen alle anderen Individuen siegreich ist, könnte man nach jenem Individuum suchen, das gegen den größten Anteil von Gegnern siegreich ist (relativer Vergleich). Alternativ könnte man nach Individuen suchen, die beim Spiel gegen eine Reihe von vordefinierten Gegnern mit vordefinierten Stärken die höchste Punktezahl erreichen (absoluter Vergleich).

Sowohl der relative als auch der absolute Vergleich sind Gegenstand dieser Arbeit und werden an späterer Stelle genauer betrachtet.

In der Praxis wird man den Evolutionsprozess abbrechen, wenn eine der folgenden Bedingungen eintritt:

- Die Fitness des besten Individuums hat einen zu Beginn festgelegten Schwellenwert überschritten.
- Über mehrere Generationen stagniert die Fitness der Population.
- Eine zuvor festgelegte Zeitspanne (entweder Echtzeit oder Anzahl von Generationen) ist abgelaufen.

Auf weitere Aspekte der genetischen Algorithmen wird an späterer Stelle genauer eingegangen.

Evolutionsstrategien (ES)

Die Begriff „Evolutionsstrategie“ wird heute meist als Synonym für „Genetischer Algorithmus“ verwendet. Gelegentlich werden ES auch als Teilgebiet der GA angesehen. Historisch betrachtet sind das jedoch zwei zwar sehr ähnliche, aber dennoch unabhängig voneinander in Europa (ES) und USA (GA) entstandene Optimierungsmethoden.

Der augenfälligste Unterschied zwischen der GA zu den ES besteht darin, daß die Anhänger der GA die Chromosomen einer Population in der Regel als binäre Vektoren codieren. Dies ist verblüffend, denn die Evolutionsstrategen benutzen, wie wir gesehen haben, die kompakteste aller möglichen Codierungen: reelle Zahlen.

(Schöneburg, Heinzmann, & Sven, 1994)

Dieser Unterscheid, der auf den ersten Blick wie ein unwichtiges Detail wirkt, hat weitreichende Auswirkungen auf die Implementierung, und führte zu einer jahrzehntelangen Aufspaltung in zwei Lager. Mittlerweile wird das eine als ein Aspekt des anderen gesehen, und der Begriff „genetische Algorithmen“ hat sich als Oberbegriff der beiden nun vereinten Strömungen durchgesetzt. In diesem Sinne wird auch in dieser Arbeit der Begriff „genetische Algorithmen“ in den Titel gesetzt, obwohl die hier beschriebene Optimierungsmaßnahme nach ursprünglicher Definition eine Evolutionsstrategie ist, denn die zu optimierenden Parameter liegen als rationale Zahlen vor, deren Art der maschineninternen Repräsentation (als binärer Vektor) für den Optimierungsvorgang nicht relevant ist.

Genetische Programmierung

Bei der Verwendung genetischer Algorithmen wird in der Planungsphase eine Menge von Parametern definiert, die dann das Objekt der Optimierung darstellen. Die Programme, die für diese Optimierung eingesetzt werden, werden mit Hilfe konventioneller Methoden entwickelt. Sie sind also nur das Werkzeug für die Optimierung, ohne selbst der Optimierung unterworfen zu sein.

Im Gegensatz dazu wird bei der genetischen Programmierung eine Menge von Computer­programmen, in Form einer geeigneten Repräsentation, dem zyklischen Optimierungsprozess unterworfen. Die Programme können dabei durch ihren Quellcode oder sogar durch den ausführbaren Maschinencode repräsentiert sein. Häufiger werden Programme aber als Bäume dargestellt, wobei jeder Baum die hierarchische Struktur von Funktionsaufrufen des jeweiligen Programms abbildet. Konstante Werte, aber auch Inputgrößen, bilden dabei, ebenso wie parameterlose Funktionen, die Blätter des Baumes (vgl.(Schölnast, 2009)).

Der Vorteil der genetischen Programmierung liegt ganz sicher darin, dass die Entscheidung, welche Parameter für die Optimierung heranzuziehen sind, nicht mehr in der Vorbereitungsphase vom Entwickler getroffen werden muss, sondern dass diese Festlegung selbst ein Teil des Optimierungsvorganges ist.

Aber auch der Nachteil liegt auf der Hand: Tausende, möglicherweise sogar Millionen Programm-Bäume, die bei diesem Prozess entstehen, müssen in lauffähige Programme umgewandelt werden, und diese Programme müssen dann auch durchgeführt werden. Um dies in der Praxis durchführen zu können, müssen Maßnahmen getroffen werden um unverhältnismäßig aufgeblähte Programme zu vermeiden, und um Programme, die sich in Endlosschleifen verfangen, von Programmen zu unterscheiden, die einfach nur langsam sind. Es muss auch die nötige Hardware vorhanden sein, um diese riesige Menge an Programmen in vielen Durchläufen zu bewerten. Denn wie später noch gezeigt wird, ist die Bewertung der Optimierungsobjekte ein zentraler Bestandteil aller Methoden, die an die natürliche Evolution angelehnt sind.

2 Objekt der Optimierung

2.1 Das Spiel „Qubic“

Die Wahl des Objekts, das der Optimierung unterzogen werden sollte, fiel auf das 3D- Brettspiel „Qubic“. Dieses Spiel ist eine Variante des bekannten Kinderspiels „Tic-Tac-Toe“.

Tic-Tac-Toe wird auf einem Raster gespielt, das die Spielebene in 9 Quadrate unterteilt, die in drei Reihen zu je drei Spalten angeordnet sind. Die beiden Spieler ziehen abwechselnd, indem sie ihre jeweiligen Symbole (traditionellerweise X und O) in eines der noch freien Quadrate setzen. Jener Spieler, der mit seinen Symbolen als erster eine Dreierlinie bilden kann, hat das Spiel gewonnen. Dabei gelten die drei waagrechten Zeilen, die drei senkrechten Spalten, aber auch die beiden Diagonalen als gewinnfähige Linien.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1 Tic-Tac-Toe

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2 Senkrecht stehende zweidimensionale Tic-Tac-Toe-Variante (Vier Gewinnt)

Qubic erweitert dieses Konzept auf einen 4x4x4-Würfel. Auf einem Grundbrett sind 16 Stäbe angebracht, wobei diese Stäbe ein quadratisches 4x4-Raster bilden. Anstelle von Symbolen oder Chips setzen die beiden Spieler abwechselnd Kugeln auf die Stäbe. Jede Kugel hat ein Loch um sie damit auf einen Stab setzen zu können. Auf einem Stab können bis zu vier Kugeln aufgefädelt werden. Die Kugeln der beiden Spieler unterscheiden sich in ihrer Farbe.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3 Qubic ist eine dreidimensionale Tic-Tac-Toe-Variante

Ziel ist es, als erster vier Kugeln der eigenen Farbe in einer Reihe anzu¬ordnen, wobei natürlich auch alle Flächen- und Raumdiagonalen zu den gewinnfähigen Linien zählen. Insgesamt durch-ziehen 76 solcher Linien den Spielraum.

Von Tic-Tac-Toe leiten sich eine Vielzahl verschiedener Spiele ab, die unter­schiedliche Aspekte des Spiels variieren. So gibt es beispielsweise auch eine 4x4- Variante die ebenfalls mit Stiften auf einem Blatt Papier gespielt wird. Sehr beliebt ist auch das Spiel „Vier gewinnt“, das mit roten und gelben Chips in einem senkrecht stehenden Raster gespielt wird (siehe Abbildung 2). Neben der Größe des Spielfeldes besteht der wesentlichste Unterschied zum 4x4-Tic-Tac-Toe darin, dass bei dem senkrecht stehenden Vier­Gewinnt die Spielsteine der Schwerkraft folgend nach unten fallen.

2.1.1 Spieltheoretische Begründung

Endlich

Qubic ist, wie alle Tic-Tac-Toe-Variationen, ein endliches Spiel: Das Spielfeld ist räumlich begrenzt und pro Zug verringert sich die Anzahl der noch freien Plätze. Damit ist sichergestellt, dass das Spiel nach endlich vielen Zügen zu Ende ist. Im Fall des originalen Tic-Tac-Toe sind das neun Züge, bei Qubic erreicht man spätestens nach dem 64. Zug das Ende des Spiels.

Andere Spiele wie z.B. Dame, Mühle oder Schach haben diese Eigenschaft nicht automatisch. Erst durch Einfuhren spezieller Regeln, deren einziger Zweck es ist unendlich lange Spiele zu verhindern (Remis bzw. Patt), können auch diese Spiele zu endlichen Spielen gemacht werden.

Zwei-Personen-Spiel

Solange spielende Computer außer Acht gelassen werden, liegt die Definition dieses Begriffs auf der Hand: Genau zwei Personen nehmen an dem Spiel teil. Solitär, Skat und Fußball gehören nicht zu dieser Gruppe von Spielen.

Zieht man in die Definition spielende Computer bzw. Programme mit ein, hängt es davon ab, ob man dem Computer den Status einer Person zubilligt. Aus Sicht des Programmentwicklers ist dies durchaus sinnvoll, daher wird in dieser Arbeit auch dieser Standpunkt eingenommen.

Wenn man jedoch einen Schachcomputer nicht als Person, sondern als „Spiel-Zeug“ ansieht, muss man das Spiel eines Menschen gegen diesen Computer in die Reihe der Solitärspiele, also der Ein-Personen-Spiele einordnen.

Nullsummenspiel

Dieser Begriff aus der Spieltheorie kann bei oberflächlicher Betrachtung missverstanden werden. Dieser Ausdruck wird nämlich in den Medien häufig falsch verwendet. Man bezeichnet damit gerne Situationen, in denen mehrere Entscheidungsmöglichkeiten offen stehen, von denen jedoch alle weder eine Verbesserung noch eine Verschlechterung der Ausgangslage versprechen.

Tatsächlich ist damit aber gemeint, dass die Summe aller Gewinne, die alle Spieler gemeinsam, also in Summe, erzielen, null ist. Das heißt jedoch keineswegs, dass das auch für die Gewinne der einzelnen Spiele gelten muss. Es heißt nur, dass die Beträge, die in Summe an die Gewinner ausbezahlt werden, genau jenen entsprechen, die die Verlierer in Summe als Verlust zu verbuchen haben. Dabei muss aber nicht notwendigerweise wirklich Geld fließen. Auch der Hinzugewinn von Punkten gilt im Sinn dieser Definition als Gewinn.

Solitärspiele sind in der Regel niemals Nullsummenspiele. Ein Beispiel dafür ist Lotto: Ein Spieler setzt einen Betrag und kann entweder diesen Einsatz verlieren oder einen Geldgewinn erlangen. Dieses Beispiel zeigt aber auch, dass jedes Nicht-Nullsummenspiel durch Hinzufügen eines weiteren Spielteilnehmers (in diesem Fall der Lotto-Toto-Gesellschaft) zu einem Nullsummenspiel gemacht werden kann. Die Aufgabe dieses zusätzlichen Spielers, der selbst keinen Zug machen darf, besteht nur darin, durch seine Einnahmen oder Ausgaben die Gesamtgewinnsumme aller Spieler auf null zu halten.

Zweipersonen-Nullsummenspiele haben die trivial erscheinende, aber sehr wichtige Eigenschaft, dass solche Spiele immer entweder damit enden dass entweder niemand gewinnt und niemand verliert (Unentschieden), oder dass genau eine Person gewinnt und die andere Person verliert.

Spiel mit vollständiger Information

In Spielen mit vollständiger Information hat jeder Spielteilnehmer zu jedem Zeitpunkt alle Informationen, die nötig sind, um den gesamten zukünftigen Spielverlauf zu analysieren. Man kennt also alle eigenen Zugmöglichkeiten und man kennt ebenso alle Zugmöglichkeiten des Gegners.

Spiele mit Zufallselementen wie z.B. Scrabble oder Mensch-ärgere-dich-nicht fallen nicht in diese Kategorie, weil dabei nicht bekannt ist, welche Möglichkeiten man selbst in zwei oder drei Zügen hat.

Spiele mit verdeckten Elementen, worunter fast alle Kartenspiele fallen, fallen ebenfalls nicht in diese Klasse, weil dabei unbekannt ist, welche Möglichkeiten der Gegner hat auf den eigenen Zug zu antworten.

Die klassischen Brettspiele, wie beispielsweise Schach, Halma oder Go, sind hingegen Spiele mit vollständiger Information, ebenso wie Tic-Tac-Toe mit all seinen Varianten, darunter auch Qubic.

2.1.2 Berechenbares Nash-Gleichgewicht

Schon lange bevor John Forbes Nash mit dem nach ihm benannten Nash-Gleichgewicht die Spieltheorie für die Welt der Wirtschaft interessant gemacht hat, bewies Ernest Zermelo 1912, dass für Spiele, auf die die vier oben beschriebenen Kriterien zutreffen, ein solches Gleichgewicht nicht nur existiert, sondern auch in jedem Fall in endlicher Zeit mit einem einfachen Algorithmus berechnet werden kann. John von Neumann bewies 1928, dass für die Existenz dieses Gleichgewichts (nicht aber für seine Berechenbarkeit) sogar nur die beiden Bedingungen Zweipersonenspiel und Nullsummenspiel ausreichend sind.

Was heißt das?

Vorausgesetzt wird, dass alle Spielteilnehmer die Maximierung des eigenen Gewinns anstreben und sonst keine anderen Ziele verfolgen. Dabei stehen jedem Spieler verschiedene Strategien zur Verfügung. Wenn jeder Spieler unter Berücksichtigung der Tatsache, dass seine Gegner jeweils für sich selbst dasselbe tun, aus seinen Strategien jene wählt, die unter diesen Bedingungen den höchsten Gewinn (oder zumindest den kleinsten Verlust) verspricht, oder wenn er seine Strategien aufgrund dieser Überlegungen mit verschiedenen Gewichten versieht, und dann per Zufall zwischen diesen Strategien wählt, dann wird ein Zustand erreicht, wo kein Spieler durch Verändern seiner Vorgehensweise seinen Vorteil vergrößern bzw. seinen Nachteil verkleinern kann. Eine solche Veränderung des Zustands hin zum eigenen Vorteil könnte nur durch Aktionen des Gegners erfolgen, der daran aber kein Interesse hat, und dies folglich nicht tun wird.

Diesen Gleichgewichts-Zustand, bei dem jeder Spieler unter Bedachtnahme aller Möglichkeiten seiner Gegner nichts mehr tun kann um den eigenen Status zu verbessern, hat Nash in seiner mit dem Nobelpreis für Wirtschaftswissenschaften ausgezeichneten nur 27

Seiten umfassenden Doktorarbeit „Non-Cooperative Games“ ausführlich beschrieben. (Nash, 1950)

Die Lage dieses Nash-Gleichgewichts, also die Werte der Gewinnhöhen der optimal spielenden Spieler, ist eine Eigenschaft des jeweiligen Spiels und ist nur von seinen Regeln abhängig, nicht jedoch von den Strategien der Spieler. Im Gegenteil: Durch das Gleichgewicht sind die optimalen Strategien aller Spieler bereits vorbestimmt.

Im vergleichsweise einfachen Szenario der endlichen Zweipersonen-Nullsummenspiele mit vollständiger Information kann dieses Gleichgewicht nur einen der folgenden drei folgenden Werte annehmen:

- Der Spieler, der das Spiel eröffnet, gewinnt.
- Der Spieler, der das Spiel eröffnet, verliert.
- Das Spiel endet unentschieden.

Darüber hinaus gibt es für diese Gruppe von Spielen einen einfachen Algorithmus mit dem dieses Gleichgewicht gefunden werden kann:

2.1.3 Min-Max-Algorithmus

Für die Ermittlung des Nash-Gleichgewichtes wird die Ausgangsstellung als Startpunkt verwendet. Also jene Stellung, bei welcher noch keiner der Spieler einen Zug getätigt hat. Dieser Algorithmus eignet sich jedoch auch, um im laufenden Spiel herauszufinden, welchen Zug der ziehende Spieler wählen soll.

Ausgehend von der Startstellung werden in einem Baumdiagramm alle Stellungen, die durch einen Zug erreicht werden könnten, als Kinder des Wurzelknotens (der Startstellung) eingetragen. Von jedem dieser Knoten werden jeweils alle Stellungen wiederum als Kinder des gerade betrachteten Knotens dargestellt, die nun der Gegner mit einem Zug erreichen kann. In der nächsten Ebene werden dann die Stellungen eingetragen, die den eigenen Antwortmöglichkeiten entsprechen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4 Zugbaum

Abbildung 4 stellt einen solchen Zugbaum dar: Die Wurzel des Baumes ist die jeweilige Inputstellung. Am Beginn des Spiels natürlich die Ausgangsstellung, im Fall von Qubic wäre das ein leeres Brett.

Die von der Wurzel (Ebene 0) ausgehenden rot eingefärbten Kanten stellen die möglichen Züge dar, aus denen jener Spieler wählen kann, der am Zug ist und daher diesen Baum analysiert. Diese Kanten enden an Knoten der Ebene 1. Das sind die Stellungen, die der ziehende Spieler mit seinen Zügen erreichen kann. Gleichzeitig sind das auch die Wurzeln jener Bäume, die der gegnerische Spieler an diesen Stellen errichten würde. Dem Gegner stehen, ausgehend von diesen Stellungen, jeweils die grün eingefärbten Kanten als Züge zur Verfügung. Damit werden die Stellungen der Ebene 2 erreicht. Von dort zieht wieder der erste Spieler entlang einer der roten Kanten, und so weiter, bis eine Stellung erreicht wird, die für einen der beiden Spieler den Sieg (und damit für den anderen die Niederlage) bedeutet, oder bis eine Stellung erreicht ist, die als unentschieden zu bewerten ist.

Da es sich um ein endliches Spiel handelt, ist auch dieser Zugbaum endlich. Das heißt aber nicht, dass er deswegen überschaubar ist. Im Fall von Qubic hat in der Anfangsphase jeder Spieler 16 verschiedene Möglichkeiten seinen Stein zu setzen. Später, wenn einzelne Stäbe mit je vier Kugeln bereits voll besetzt sind, nimmt diese Anzahl ab. Im Mittel hat jeder Spieler pro Zug ungefähr 14 Möglichkeiten. Das heißt, dass die Anzahl der Knoten im Zugbaum von Ebene zu Ebene jeweils um den Faktor 14 wächst. Der ganze Baum beinhaltet damit also etwa 1464, also rund 2,2*1073 Knoten. Diese Zahl ist zwar - wie versprochen - endlich, aber dennoch unerreichbar groß.

Würde man den ganzen Planeten Erde vollständig mit einer 10 km dicken Schicht aus Computern der gegenwärtigen Technologie überziehen, und hätte man diese Computer seit Beginn des Universums gemeinsam am Aufbau des Qubic-Zugbaums arbeiten lassen, dann hätten diese Computer bis heute gerade einmal die ersten 40 Ebenen des Baums aufgebaut. Um den ganzen Baum aufzubauen, wäre für diese Menge von Computern ungefähr das 1030­fache des Alters des Universums von Nöten.

Verschiedene Überlegungen, wie z.B. die Erkennung gleicher Stellungen, die durch unterschiedliche Zugfolgen erzeugt wurden, Stellungen, die durch Drehung oder Spiegelung ineinander überführbar sind, oder das sogenannte Alpha-Beta-Stutzen[1], lassen den Aufwand wieder drastisch schrumpfen.

Gleiche Stellungen

Das Erkennen gleicher Stellungen ist mit einigem Aufwand verbunden, der erst durch den dadurch erzielten Zeitgewinn gerechtfertigt werden muss. Das ist nur für die ersten Züge des Spiels der Fall, weil beinahe jeder Zug einen Symmetriebruch hervorruft, und einmal gebrochene Symmetrien nur selten wiederhergestellt werden.

Beispielsweise gibt es für den allerersten Zug 16 Möglichkeiten, die aber nur drei verschiedene Stellungen ergeben, wenn man Stellungen, die durch Spiegelung oder Drehung ineinander überführen kann, als gleich ansieht. Zwei dieser drei Stellungen führen durch den zweiten Zug zu jeweils 10 unterscheidbaren Stellungen, während alle 16 Folgestellungen, die aus der dritten Stellung hervorgehen, voneinander unterscheidbar sind, also nicht in eine der anderen Stellungen überführt werden können. Das heißt: Für den ersten Zug lässt sich damit eine Beschleunigung um den Faktor 16/3 = 5,33 erreichen. Beim zweiten Zug beträgt dieser Faktor im Mittel nur noch (16/10 + 16/10 + 16/16) / 3 = 1,2. Dieser Faktor nähert sich für weitere Züge so schnell dem Wert 1,0, dass schon nach dem dritten oder vierten Zug der Aufwand für das Suchen gleicher Stellungen größer wird als der damit verbundene Zeitgewinn.

Alpha-Beta-Stutzen

Das Alpha-Beta-Stutzen ist dann am effizientesten, wenn man zuerst jene Äste des Zugbaums analysiert, die am ehesten versprechen jenen Spielpfad zu enthalten, dem das Spiel tatsächlich folgen wird. Das wiederum kann man abschätzen, indem man in einer Vorbewertung bereits alle Stellungen der ersten Ebene des Zugsbaums mit dem Stellungsbewerter (siehe Abschnitt 2.1.4) bewertet, und dann mit dem Aufbau des Baumes bei jener Stellung beginnt, die den besten Wert hat.

Wenn nämlich der Stellungsbewerter wirklich plausible Werte für die einzelnen Stellungen liefert, dann sorgt das Aufbauen des Zugbaumes samt Bewerten der darunterliegenden Stellungen für Werte, die in der Nähe der Vorbewertungen liegen. Das wiederum führt dazu, dass man beim Aufbauen und Bewerten des nächsten Astes möglicherweise schon bald erkennt, dass dieser Ast ab bestimmten Knoten nicht weiter untersucht werden muss.

Besonders bei den Ästen, die in der Vorbewertungsrunde schlechte Werte bekommen haben, wird man recht schnell zu Knoten im Baum kommen, wo man die dort befindlichen Teilbäume abschneiden kann.

Die Effizienz des Alpha-Beta-Stutzens hängt also stark von der Qualität des Stellungsbewerters ab und drückt sich dadurch aus, dass die Anzahl der zu bewertenden Knoten pro Ebene nicht um den Faktor 14, sondern um einen kleineren Faktor zunimmt. Doch selbst wenn man den Faktor von 14 auf 7 halbieren würde, was durchaus im realisierbaren Bereich liegt, wären statt der oben erwähnten 2,2* 1073 Knoten noch immer 1,2*1054 Knoten zu untersuchen. Anstatt also für die vollständige Analyse des Spieles eine Zeitspanne in der Größenordnung des 1030-fachen Alters des Universums aufwenden zu müssen, würde das 10­fache Alter genügen.

Bereits vollständig analysierte Spiele

Trotz der oben beschriebenen Verfahren konnte bisher nur bei einigen wenigen einfachen Spielen tatsächlich eine vollständige Analyse des Zugbaumes, und damit eine exakte Ermittlung des Nash-Gleichgewichts erreicht werden.

Für Tic-Tac-Toe und viele seiner Abkömmlinge wurde dieses Gleichgewicht bereits berechnet (Tic-Tac-Toe endet immer unentschieden wenn beide Spieler optimal spielen). Für die meisten anderen Spiele, darunter nicht nur Schach, sondern auch Qubic, war diese Berechnung aufgrund des hohen Aufwandes bisher nicht möglich. Dies ist ein weiteres Argument, das, gemeinsam mit den sehr einfachen Regeln, zur Wahl von Qubic als Studienobjekt geführt hat.

2.1.4 Stellungsbewertung

Die Bewertung der Stellungen erfolgt bottom-up, also von den Blättern ausgehend. Die Werte der Blätter sind bekannt, und können +1 (für eine Stellung, die den Sieg des anziehenden Spieles bedeutet), -1 (für eine Verlust-Stellung) und 0 (Unentschieden) sein.

Der Wert des darüber liegenden Knotens ist das Maximum oder das Minimum seiner Kind­Knoten. Das Maximum wird genommen wenn der anziehende Gegner an dieser Stellung am Zug ist, denn er wird versuchen, den bestmöglichen Zug zu wählen. Wenn der Gegner am Zug ist, wird dieser jedoch seinen Vorteil erhöhen wollen, was bei Zweipersonen­Nullsummenspielen aber genau die schlechtmöglichste Wahl für den ersten Spieler ist. Daher wird in diesem Fall das Minimum gewählt.

Weiter oben liegende Knoten werden nach demselben Schema bewertet, bis man die Wurzel erreicht. Hier ist dann zu unterscheiden, ob man am Wert des Nash-Gleichgewichts interessiert ist, oder ob man einen Zug machen will: Der Wert des Nash-Gleichgewichts ist identisch mit dem Wert der Wurzelstellung des Spiels. Will man einen Zug machen, ist der Wert der Wurzel völlig uninteressant. Wichtig sind nur die Werte der Stellungen, die man von der Wurzel aus erreichen kann, den man wird unter diesen Stellungen jene Stellung nehmen, die den größten Wert hat. Falls mehrere denselben maximalen Wert haben, kann man per Zufall zwischen ihnen wählen.

Begrenzung auf n Ebenen

Diese exakte Methode scheitert aber in der Praxis an den zu langen Zeiten, die für das Aufbauen eines vollständigen Zugbaumes notwendig sind. Daher wird der Baum nur bis zu einer bestimmten Tiefe aufgebaut. Die Knoten der untersten Ebene müssen nun mit Werten belegt werden, die möglichst gut die Wahrscheinlichkeit widerspiegeln, von dieser Stellung aus einen Sieg (positives Vorzeichen) oder eine Niederlage (negatives Vorzeichen) zu erreichen. Die Bewertung der höheren Ebenen erfolgt dann wieder nach dem Min-Max- Algorithmus.

Abbildung 5 illustriert diese Vorgehensweise:

- Ausgehend von der Stellung, bei der der Spieler A am Zug ist, werden die Ebenen 1 und 2 des Zugbaumes erzeugt.
- Die Stellungen der Ebene 2 werden bewertet (diese Bewertung stellt den eigentlichen Inhalt dieser Arbeit dar).
- Da von Ebene 1 zu Ebene 2 der Gegner zieht, erhalten die Knoten der Ebene 1 den Minimumswert ihrer Kinder.
- Der Knoten darüber (Ebene 0 = Wurzel) würde den Maximumswert aller Knoten der Ebene 1 erhalten. Die Bewertung der Wurzel ist aber nicht notwendig. Stattdessen wird der Spieler A nun jenen Zug wählen, der zum höchstbewerteten Knoten der Ebene 1 führt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5 Zugbaum mit Bewertungen

3 Programmierung des Spiels

3.1 Allgemeiner Aufbau einer Brettspielsimulation

Ein Programm, welches den Spieler eines Brettspieles simuliert, beinhaltet immer folgende Komponenten:

- Initialisierung: Beim Start des Programms müssen Vorbereitungen getroffen werden, die den reibungslosen Ablauf des Programms ermöglichen.

- Benutzerinterface: Das Programm muss Eingaben seines Gegners entgegennehmen und ihm seine Reaktionen mitteilen. Üblicherweise ist der Gegner des Programms ein Mensch, aber auch das Spiel gegen andere Programme sollte unter Umständen möglich sein.
- Sieg/Niederlage-Erkennung: Das Programm muss in der Lage sein, Stellungen, die das Ende des Spiels bedeuten, zu erkennen. Im Fall von Qubic muss diese Routine erkennen können, ob sich auf einer der 76 Gewinnlinien 4 Kugeln derselben Farbe befinden, bzw. ob bereits alle 64 Plätze mit Kugeln besetzt sind (letzteres kennzeichnet einen unentschiedenen Spielausgang)
- Zuggenerator: Es ist notwendig, ausgehend von einer Inputstellung alle Stellungen erzeugen zu können, die der an dieser Stelle am Zug befindliche Spieler erreichen kann.
- Stellungsbewertung: Dieser Programmteil bekommt eine Stellung als Input und liefert eine Zahl zurück, die den Wert dieser Stellung darstellt. Die Werte müssen folgende Bedingungen erfüllen:
- Je größer der Wert, desto größer ist die Wahrscheinlichkeit, dass der Spieler, der vom Programm simuliert wird, bei Erreichen dieser Stellung gewinnen wird.
- Je kleiner der Wert ist, desto eher wird das Spiel mit einem Sieg des Gegners, also mit der eigenen Niederlage, enden, falls diese Stellung im Spielverlauf tatsächlich erreicht wird.
- Werte, die nahe bei null liegen, sagen aus, dass entweder unklar ist, wer ab dieser Stellung siegen wird, oder dass der wahrscheinlichste Endzustand ein Unentschieden ist.

Mit Ausnahme der Stellungsbewertung kann für jeden Programmteil mit den klassischen Methoden der SW-Entwicklung zuverlässiger Code designed und implementiert werden. Für die Stellungsbewertung liegt jedoch auf den ersten Blick kein einfaches Konzept auf dem Tisch.

3.2 Stellungsbewertung

Da, wie oben erwähnt, sich sehr einfach für anderen Teile des Programms klare Vorgaben finden lassen, die ebenso einfach umgesetzt werden können, besteht kein Bedarf, sich über die Optimierung dieser Programmteile Gedanken zu machen, die über simple Performance- und Speicherplatz-Vorgaben hinausgehen. Anders formuliert: Die Spielstärke des Programms lässt sich nicht verbessern, indem man etwas am Zuggenerator oder am Benutzerinterface verändert.

Der Schlüssel zum Erfolg liegt beim Stellungsbewerter, und es gibt drei grundlegende Konzepte, wie dieser Programmteil in Angriff genommen werden kann:

Das Problem ignorieren und bewusst auf seine Lösung verzichten Man benutzt die Gewinn/Niederlage-Erkennung um absolut sichere Gewinn- und Verluststellungen mit +1 bzw. -1 zu bewerten, und weist allen anderen Stellungen den Wert 0 zu. Das ist natürlich nicht die optimale Strategie, entspricht aber genau der Vorgehensweise, die man verwenden würde, wenn man den Zugbaum vollständig aufbauen würde.

Je mehr Ebenen man aufbaut, desto eher wird man mit dieser Methode Zugfolgen erkennen können, die zu Sieg oder Niederlage führen. Vor allem kann man sich bei dieser Methode sicher sein, dass Stellungen, die den Wert +1 haben, garantiert zu einem Sieg führen, und dass -1 eine garantierte Niederlage bedeutet.

Diese Methode wird in dieser Arbeit verwendet, um Standardspieler zu erzeugen, deren Spielstärke durch Einstellen einer bestimmten Suchtiefe (maximale Tiefe des Zugbaums) exakt festgelegt werden kann. Diese Standardspieler bilden zusammen eine Messskala, um daran die Stärke der „genetischen Spieler“ zu messen.

Parameter für die Bewertungsfunktion finden und optimieren

Die Stellung, die als Input vorliegt, muss analysiert werden. Es müssen aus dieser Stellung Zählwerte ermittelt werden, die möglichst gut wiederspiegeln, ob die Stellung für den vom Computer simulierten Spieler von Vorteil oder von Nachteil ist.

Bei einem Schachprogramm könnte man beispielsweise die eigenen und die gegnerischen Figuren zählen, man würde vielleicht zusätzlich zählen, wie viele Figuren von anderen bedroht oder geschützt werden. Im Fall von Qubic wird man stattdessen die Linien zählen, die mit Kugeln von nur einer Farbe besetzt sind, und dabei auch die Anzahl dieser Kugeln berücksichtigen.

[...]


[1] Das Alpha-Beta-Stutzen lässt sich am besten anhand eines Beispiels erklären. Siehe Abbildung 5; lesen Sie aber bitte zuvor noch den Abschnitt 2.1.4 Stellungsbewertung: Nehmen wir an, die beiden Teilbäume, deren Wurzeln der linke und der mittlere Knoten der Ebene 1 sind, wären schon bewertet worden (mit -2 und +6). Als nächstes wird vom rechten Teilbaum in der untersten Ebene der linke Knoten mit -5 bewertet. Es ist somit klar, dass der Wert des Elternknoten den Wert -5 oder einen noch kleineren Wert erhalten wird, denn dieser Knoten erhält den Minimumswert seiner Kinder. Auf der Ebene dieses Elternknotens gibt es aber einen Knoten mit einem höheren Wert (nämlich +6). Da nach den Knoten dieser Ebene das Maximum ausgewählt wird, steht fest, dass dieser Teilbaum nichts zum Wert des darüberliegenden Knotens mehr beitragen kann. Daher kann man diesen Ast stutzen, also diesen Teilbaum ignorieren.

Details

Seiten
63
Jahr
2009
ISBN (eBook)
9783640594887
ISBN (Buch)
9783640594740
Dateigröße
3.3 MB
Sprache
Deutsch
Katalognummer
v148855
Institution / Hochschule
Fachhochschule Technikum Wien – Informations- und Kommunikationssysteme
Note
1
Schlagworte
Genetische Algorithmen Evolutionsstrategien praktische Anwendung Vergleich Mutation Crossover

Autor

Teilen

Zurück

Titel: Genetische Algorithmen in der Praxis