Kurzfassung

Genetische Algorithmen und Evolutionsstrategien sind heuristische Optimierungsmethoden, die ihr Vorbild in der natürlichen Evolution haben. In dieser Arbeit wird diese Methode benutzt, um die Parameter des Stellenbewertungsmoduls des Brettspielprogramms „Qubic“ (eine dreidimensionale Variante von Tic-Tac-Toe) zu optimieren. Es werden insgesamt 28 Parameter definiert, die zusammen das Chromosom eines Spielers bilden. In verschiedenen Versuchsreihen müssen die Spieler durch das Spiel gegen genormte Standardspieler ihre absolute Spielstärke unter Beweis stellen. In einer dieser Reihen wird auch eine relative Spielstärke durch direkten Vergleich der Spieler untereinander ermittelt. Nachkommen werden entweder durch Mutation des Genoms eines Spielers, oder durch Zusammenfügen von Teilen der Gene zweier Elternteile („Crossover“) erzeugt. Diese Nachkommen nehmen entweder als eine neue Generation am Selektionsprozess teil, oder ersetzen innerhalb der Population den jeweils zu diesem Zeitpunkt schlechtesten Spieler. Je nach Versuchsreihe entscheidet die absolute oder die relative Spielstärke darüber, mit welcher Wahrscheinlichkeit jedes Individuum seine Gene an Nachkommen weitergeben darf. Die Methode, strikt voneinander getrennte Generationen zu verwenden, wird mit einem kontinuierlichen Austausch von Individuen verglichen. Dabei schneidet die kontinuierliche Verbesserung überraschend gut ab, was das Entwicklungstempo der Population betrifft. Bestimmte Überlegungen legen nahe, dass die Chromosomen guter Spieler eine gewisse Struktur aufweisen müssen. Durch den Vergleich einer Versuchsreihe, die ausschließlich solche strukturierten Chromosomen verwendet, mit einer Reihe, die sich nicht an diese Vorgaben halten muss, kann gezeigt werden, dass die Chromosomen guter Spieler tatsächlich einige Eigenschaften aufwiesen die erwartet wurden. Einige andere Ergebnisse sind aber überraschend.

Schlagwörter: Genetische Algorithmen, Evolutionsstrategien, praktische Anwendung, Vergleich, Mutation, Crossover

Abstract

Genetic Algorithms and Evolutionary Strategies are methods of heuristic optimization, modeled upon natural evolution. This method was used in this work to optimize the parameters of the position-rating module of the board game “qubic”, a tridimensional version of tic-tac-toe. 28 parameters have been defined, which together make up the chromosome of a player. In various test series the players must proof their absolute playing ability by playing against standardized players. In one of these series also a relative playing strength is calculated by direct comparison of the players against each other. Offspring are generated either by mutation of the genome of one player, or by assembly of parts of the genes of two parents (“crossover”). These offspring will either form a new generation in the selection process, or replace the current worst player within the same population. Depending on the test series, the absolute or relative playing strength of each individual determines the likelihood of passing its genes to offspring. The method of using strictly separated generations is compared against a continuous exchange of individuals. It comes out, that the continuous improvement surprisingly performs much better, concerning the pace of development.

Certain considerations suggest that good players should exhibit a certain structure within their chromosomes. By comparing two test series, one of them using those constraints, the other using unstructured chromosomes, it can be shown that the chromosomes of good players really show some of the expected characteristics. Some other results are, however, surprising.

Keywords: genetic algorithms, evolutionary strategies, implementation, comparison, mutation, crossover

Danksagung

Ich danke FH-Prof. Peter Balog für die Zusage, die Rechner in den EDV-Sälen des Technikums Wien für die Durchführung der sehr rechenintensiven Programme, die für diese Bachelorarbeit entwickelt wurden, benützen zu dürfen.

Dass ich von dieser Zusage gar keinen Gebrauch machen musste, verdanke ich meinem Betreuer, Dr. Göschka, der mir für die Dauer von zwei Monaten einen brandneuen Rechner an der TU-Wien, der mit 8 CPUs bestückt ist, exklusiv zur Verfügung gestellt hat. Durch diesen Rechner ist die praktische Arbeit wesentlich vereinfacht worden. - Herzlichen Dank! Der größte Dank gebührt aber meiner Frau Doris, die mich während meines ganzen Studiums auf jede nur denkbare Weise unterstützt hat, und auch während meiner Arbeit an diesem Dokument viel Geduld mit mir bewiesen hat.

Inhaltsverzeichnis

1  Einleitung  1

1.1  Motivation  1

1.2  Begriffsklärung, theoretisches Fundament  1

2  Objekt der Optimierung  4

2.1  Das Spiel „Qubic“  4

2.1.1  Spieltheoretische Begründung  6

2.1.2  Berechenbares Nash-Gleichgewicht  7

2.1.3  Min-Max-Algorithmus  8

2.1.4  Stellungsbewertung  11

3  Programmierung des Spiels  12

3.1  Allgemeiner Aufbau einer Brettspielsimulation  12

3.2  Stellungsbewertung  13

4  Messen der Spielstärke  15

4.1  Standardspieler  15

4.1.1  Totale Ordnung für Standardspieler  16

4.2  Elo-Punktesystem  17

4.3  Zuordnung der Spielstärke zur Suchtiefe  18

4.3.1  Spieler mit Spielstärken in Hunderterschritten  19

4.3.2  Spieler mit dazwischenliegenden Spielstärken  21

4.4  Ressourcenverbrauch und weitere Erkenntnisse  23

5  Anwendung genetischer Algorithmen  25

5.1  Chromosom als Gewichtsvektor  25

5.1.1  Qubic-Gewinnlinien.  26

5.1.2  Skalarproduktes von Matrizen  29

5.1.3  Chromosomenmatrix  30

5.2  Genetische Operatoren  31

5.2.1  Mögliche Arten der Fortpflanzung  31

5.2.2  Die verwendeten Methoden  32

6  Drei Versuchsreihen  36

6.1  Generationszyklen mit beschränkten Chromosomen  36

6.1.1  Entwicklung der Spielstärken  36

6.1.2  Entwicklung der Chromosomen  39

6  1 3 Hoher Selektionsdruck  42

6.2  Generationszyklen mit freien Chromosomen  43

6.3  Kontinuierliche Verbesserung mit freien Chromosomen  48

7  Schlussbemerkungen  54

7.1  Kontinuierliche Verbesserung schlägt Generationenmodell  54

7.2  Unerwartete Verteilung der Werte innerhalb der „guten“ Chromosomen  55

  Literaturverzeichnis  56

  Abbildungsverzeichnis  56

Tabellenverzeichnis   57

  Abkürzungsverzeichnis  57

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 Optimierungsproblemen 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

• 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

1

ü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 Evolutionszyklus 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 Wahrscheinlichkeit 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 Brettspielprogrammes ist es sogar ausgesprochen unwahrscheinlich, dass man ein Individuum finden kann, das gegen alle anderen Individuen gewinnen kann. Wahrscheinlicher ist,

2

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

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.

3

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 Computerprogrammen, 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.

4

Abbildung 1 Tic-Tac-Toe

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

5

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 Einführen 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.

6

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

7