Künstliche Intelligenz - Programmierung

Künstliche Intelligenz – Programmierung

Author D. Selzer-McKenzie

Spieltheoretische Untersuchung

1 Das Spiel ,Vier gewinnt"

Dies soll eine kurze Einführung in das Spiel ,,Vier gewinnt" werden in dem die Regel vorgestellt und eine für diesen Text eindeutige Nomenklatur eingeführt.

1.1 Die Regeln von ,Vier gewinnt"

„Vier gewinnt" ist ein zwei Personen Spiel, bei dem jeder der Spieler 21 identische Spielsteine bestitz. In der Originalversion haben diese die Farben gelb und rot.

Das Spiel wird auf einem rechteckigen Spielfeld mit sieben Spalten und 6 Zeilen ge­spielt. Die Spielsteine werden von den beiden Spielern abwechselnd in eine der Spalten geworfen.

Wenn ein Spieler einen Spielstein in eine Spalte wirft, fällt dieser in die letzte unbe­setzte Zeile. Sind in einer Spalte alle 6 Zeilen besetzt so kann dort kein Stein mehr hineingeworfen werden. Im weiteren Verlauf nennen wir das werfen eines Steins einen Zug machen.

Im allgemeinen gibt es keine Regeln welche Farbe bzw. welcher Spieler beginnt, der Einfachheit halber werden wir hier davon ausgehen, dass immer der Spieler mit den gelben Steinen starten darf, ähnlich Schach oder Dame bei denen die weißen Steine stets beginnen.

Beide Spieler werden nun im Verlauf des Spiels versuchen vier zusammenhängen­de Spielsteine im Gitter zu positionieren. Dies ist entweder in vertikaler, horizontaler oder diagonaler Position möglich. Der erste Spieler der dies geschafft hat gewinnt das Spiel. Sind alle 42 Spielsteine gespielt und es hat kein Spieler geschafft vier zusamm-hängende Steine zu erreichen, so endet das Spiel unentschieden.

Die nachfolgenden Diagrammen zeigen einige Situationen in denen Gelb gewinnt.

• • •

• • • •

Abbildung 2: Diagramm 1.1.2

•

•

•

•

•

•

•

Abbildung 3: Diagramm 1.1.3

Und nun eine Spielsituation in der das Spiel unentschieden ausgeht.

			•
•	•	•		•	•	•
			•
•	•	•		0	•	•
			•
•	•	•		•	•	•

Abbildung 4: Diagramm 1.1.4

1.2 Nomenklatur

Um es nun einfacher zu machen die verschiedene Spielsituationen und Spielzüge zu beschreiben führen wir für das Spielraster eine Indizierung ein.

Ähnlich wir beim Schach benennen wir die 7 Spalten mit von links nach rechts mit „e bis „g" und die 6 Zeilen mit „1" bis „6". Nach dieser Nomenklatur wäre z.B. das unterste Feld in der Mitte dl.

Ebenso ist es Möglich das Spiel, bzw. die Züge so zu beschreiben. Das Beispiel in Diagramm 2.1 sähe wie folgt aus, wobei die Nummer zu Beginn die Spielrunde angibt:

1.    dl, d2

2.    cl, d3

3.    el, bl

4.    fl, gelb gewinnt.

In gleicher Weise ist es möglich die Gewinngruppe, also die vier Steine welche ei­ne Linie Bilden anzugeben.

Wir verdeutlichen dies wieder an Diagramm 2.1, wo die Gewinngruppe cl,d1,el,f1 ist.

Da es sich bei der Gewinngruppe immer um eine Linie handelt würde es sogar aus­reichen nur Anfangs- und Endpunkt zu nennen.

1.3 Strategische Vorgaben für die Spieler

Vorweg wollen wir einige Verhaltensregeln für die Spieler festlegen, welche zwar lo­gisch sind, doch in eigenen Annahmen im folgenden vorausgesetzt werden.

Für die Spieler sollen Annahmen gelten:

1.    Wenn man gewinnen kann so spielt der Spieler seinen Gewinnzug

2.    Hat der Gegner die Möglichkeit zu gewinnen verhindert man es

3. Bevor man den Gegner gewinnen lässt, gibt man seine eigene Gewinnposition auf

Mit diesen Annahmen soll im Prinzip nur ein unlogisches Verhalten von vorne herein ausgeschlossen werden, um Äste im Baum aszshließen die nie gespielt werden würden. Des weiteren gehen wir davon aus, dass die Spieler keine Fehler machen, also verhin-derbare Gewinnditivationen des Gegners übersehen, oder ihm unbewusst welche zu ermöglichen. Damit ist gewährleistet, dass man von „perfekten" Spielern ausgehen kann und wirklich nur solche Positionen gespielt werden, die auch dann gespielt wer­den wenn man den vollständigen Spielbaum kennen würde.

Es handelt sich hierbei sicher um Einschränkungen gegenüber dem „normalen" Spiel in der Realität, aber Spieltheoretisch macht es keine Unterschied.

2 Spieltheoretische Herangehensweise

In diesem Kapitel wollen wir nach den Vorgaben aus der Vorlesung an das Spiel heran­gehen, also den Spielbaum und die Historienmenge betrachten und die Schwierigkeiten dieser Herangehensweise aufzeigen.

2.1 Probleme der Spieltheorie bei Komplexen Spielen

Da es sich bei „4 Gewinnt" um ein 2 Personen Nullsummenspiel mit vollständiger Information handelt wäre es bei der Analyse, nach unserer Vorlesung, die Rückwärts-induktion zu benutzen. Hierzu wäre aber ein vollständiger Spielbaum nötig, welcher bei diesem Spiel enorm groß wäre.

Diagramm 1.2.1 zeigt die erste Runde also 2 geworfene Steine.

Abbildung 5: Diagramm 1.2.1

Hier sehen wir das nach nur einer Runde bereits 7 • 7 = 49 Äste, also mögliche Er­gebnisse haben. Der Baum würde also sehr groß und für eine vollständige Analyse zu kompliziert.

Eine Möglichkeit ist es den Spielbaum zu vereinfachen, also Nutzlose Züge wegzulas­sen, oder aber auch gewissen Positionen einen Wert zuzuweisen und so nur die y%Tert-vollsten" Züge zu machen. Letzter Methode werden wir in Abschnitt 1.2.3 versuchen, zuvor jedoch betrachten wir den gesamten Spielbaum und versuchen abzuschätzen wie groß er ist, wie viele Spielverläufe es also geben kann.

Versuchen wir nun abzuschätzen wie groß der Spielbaum ist, wie viele Äste wir un­tersuchen müssten:

Wir wollen also eine obere Grenze für die Anzahl der Knoten finden und so heraus­finden wie viele Spielsituationen es gibt.

Eine Möglichkeit ist es über die Kombinatorik an das Problem heranzugehen. Hierzu sollten wir zunächst unterscheiden welche Spielsituationen es geben kann und ob sie zulässig sind oder nicht. Ganz banal ist es man nimmt an, dass es 6 • 7 = 42 Felder also mögliche Positionen gibt, die immer einen von drei Zuständen haben, nämlich gelb, rot oder leer. Daraus könnte man schließen das es 3⁴² = 1, 09419. 10²⁰ Spielsiti-uationen also Knoten gibt. Dies ist natürlich eine sehr grobe Abschätzung da es eine Vielzahl von „illegalen" also unmöglichen Spielsitationen gibt.

Wir müssen also Situationen identifizieren die nicht möglich sind. Es gibt in zwei Möglichkeiten die ausgeschlossen erden müssen, erstens das die roten Steine nach ei­ner Runde nur auf Plätzen liegen die erreicht werden können also z.B nicht wie in Abbildung 6.

Abbildung 6: Diagramm 1.2.2

Hier ist leicht zu sehen das Rot begonnen haben müsste um diese Position zu errei­chen, was wir aber in der Einführung ausgeschlossen haben.

Welche Positionen sind also nach jeder Runde zulässig? Intuitiv ist es klar, was nicht passieren darf eine Zahl, bzw. eine mathematische Formulierung dafür zu finden ist nicht so einfach.

Auch für den anderen Fall, das auftreten mehrerer „Vierer" also Gewinnpositionen nicht ohne weiteres Möglich.

Wir versuchen dennoch eine bessere Abschätzung zu finden, nehmen hierbei aber zumindest in Kauf mehrere Vierer zu bekommen. Diese Grenze versuchen wir über den Spielbaum zu identifizieren, indem wir die Knoten einfach Iterieren.

Im folgenden vernachlässigen wir also, dass das Spiel nach weniger wie 21 Runden also 42 Zügen zu Ende ist.

Wir wissen, dass in den ersten 3 Runden also ersten 6 Zügen jeder Spieler im­mer 7 Möglichkeiten hat, da keine Reihe bis Oben gefüllt sein kann also haben wir 7⁶ = 117.649 Knoten.

Führen wir das weiter haben wir:6⁵ + 6⁴.7+ 6³. 7²+6². 7³+6²7⁴+6-7⁵+7⁶ = 332.738 Mögliche Züge pro erstem Abzweig, also in Summe 7 • 332.738 = 2.328.166. Man er­kennt schnell das man diese Menge auf diese Weise nicht gut Abschätzen kann. Selbst wenn man annimmt, das man immer 7 Möglichkeiten hat pro Zug kommt man auf 7²¹ = 5, 5845641 • 10¹⁷, was gegenüber der gröbsten Abschätzung eine Verbes­serung von nur 1, 088604433 • 10' wäre. Wir stellen also fest, dass man auf diese Weise keine bessere Schranke finden kann. Deshalb greifen wir hier auf die Arbeit von Allis zurück, welche unter Hinzunahme aller „illegaler" Positionen eine Schranke von 7, 1 • 10¹³ möglichen Positionen über einen Computer errechnen lies.

Obiger Versuch zeigt schnell, dass man mit der klassischen mathematischen Herange-hensweise kaum eine Möglichkeit hat solche Spiele zu lösen. Welche anderen Optionen hat man aber um komplexe Spiele zu lösen, ganz klar die Hilfe von Rechner in An­spruch zu nehmen. Aber auch hier stößt man schnell auf Probleme, denn Rechenzeit ist ersten teuer wenn es um so komplexe Berechnungen geht und andererseits wollen wir aus der Erkenntnis natürlich auch einen Nutzen ziehen, also für unser nächstes Spiel einen Vorteil für uns haben. Lange Rechendauer ist aber in jedem Fall kon­traproduktiv da der Gegner nicht ewig auf unseren Zug warten wird bzw. Verdacht

schöpft und nicht gegen uns spielt.

Dies ist in allen Spielen dieser Art, Schach, Dame, Mühle usw.., aber auch in den klassischen Glücksspielen wie Poker etc. ein Problem. Was also tun um besser zu spielen als andere und dennoch schnell und gute Verfahren zu haben.

Die Antwort ist bestimmte Situationen auszuwerten und den Computer oder auch dem Menschen so die Chance geben mit nur wenigen Zügen im voraus besser zu sein.

2.2 Analyse einzelner Spielsituationen

Wie wir gerade gesehen haben ist es nicht möglich das Spiel ,yon Hand" komplett zu analysieren oder „perfekt" zu spielen. Und auch mit Hilfe von Computern ist es sehr schwer den ganzen Spielbaum in einer ,yernünftigen" Zeit durch zurechnen, was die Programmierung als Spiel erschwert. Wir müssen also sowohl für den Menschen als auch den Computer die Spieltiefe, also die Anzahl der Situationen die im voraus mit bedacht werden verringern.

Man betrachtet also an Stelle des ganzen Baumes nur noch wenige Schritte bzw. Knoten im voraus. Deshalb ist es wichtig bestimmten Positionen eine Wertigkeit zu geben, also einen Nutzen zuzuweisen, auch ohne alle weiteren möglichen Knoten zu kennen.

Hierzu zeigen wir das es gerade in Hinblick auf das Ende des Spiels gute und schlechte Positionen gibt und man durchaus eine Taktik finden kann um die Wahrscheinlichkeit des Gewinnens zu erhöhen. Außerdem gehen wir auf das Problem des „Zugzwanges" ein und wie man ihn für sich nutzen kann.

2.2.1 Konkrete Spielsituationen und deren Nutzen

Wir wollen zuerst eine Situation betrachten an der wir sehen können das es gute und schlechte Gewinnmöglichkeiten gibt. Betrachten wir hierzu das Diagramm 1.2.2.

•		•	•	•
•
•
•		•	•	•
•				0

Abbildung 7: Diagramm 1.2.2

Um an diese Stelle des Spiels zu gelangen wurden folgende Spielzüge gespielt:

1.    dl, d2

2.    d3, el

3.    d4, e2

4.    d5, d6

5.    cl, c2

6.    c3, al

7.    c4, a2

8.    c5, c6

9.    e3, a3

10.              a4, a5

11.              e4, a6

12.              e5, e6

Und da eine gerade Anzahl von Steinen gespielt ist, ist der gelbe Spieler an der Reihe den nächsten Zug zu machen.

Wir sehen ganz leicht, dass es sowohl für Gelb als auch für Rot Möglichkeiten gibt zu gewinnen. Gelb gewinnt mit den Positionen b2, b3, b4, b5, f3, f4 und f5, Rot hingegen mit b2, b6, f2 und f6. Und obwohl das Spiel noch nicht beendet ist, wird sollte beide Spieler den strategischen Regeln aus der Einführung folgen, Rot gewinnen

Warum ist das so?

Spielen wir das Spiel doch einfach einmal weiter. Gelb wird nicht in die Spalten b oder f werfen, da Rot gewinnen würde, also bleiben diese Reihen unbesetzt, Rot wiederum spielt ebenfalls nicht in diese Spalten, da er seine Position vernichten würde. Folglich wird Spalte g aufgefüllt. Da diese Reihe aber 6 Zeilen hat ist sie nach eine geraden Anzahl von Zügen ebenfalls und es ergibt sich die Situation in Diagramm 1.2.3. nach den Zügen:

13.     gl, g2

14.     g3, g4

15.     g5, g6

•		•	•	0		•
•
						•
•
•		•	•	0		•
•				•

Abbildung 8: Diagramm 1.2.3

Nun haben wir die Situation, dass Gelb gezwungen ist in die Position bl oder fl zu spielen, und Rot gewinnt. Das Spiel war so gesehen also schon nach den ersten zwölf Runden zu Ende und Gelb hatte verloren. Dies führt nun zur Frage welche Gewinnpo­sitionen sind gut, kommen also zum Tragen und welche nicht, welchen sind also von Nutzen und Erstrebenswert. Ebenso sieht man hier das Phänomen des „Zugzwang", welchen wir später noch genauer untersuchen.

Bevor wir jedoch genauer auf den Nutzen von Gewinnpositionen eingehen wollen wir heraus finden wo Gelb den Fehler gemacht hat und ab wann das Spiel verloren war, bzw. welchen Zug Gelb besser gespielt hätte.

Gehen wir hierzu züruck in Runde 6, und habe Gelb bereits gespielt. Die bisherigen Züge ergeben folgendes Bild:

Schon hier lässt sich die Niederlage nicht mehr abwenden. Wir versetzten uns in die Position von Rot und überlegen kurz.

Abbildung 9: Diagramm 1.2.2

Wo könnte Gelb eine Gewinnposition aufbauen. Schauen wir uns zuerst die horizon­talen Möglichkeiten an. Hier gibt es die Möglichkeiten al-dl, a3-d3, b3-e3, c3-f3, und evtl. höher, aber Gelb benötigt auf jeden Fall die Spalten b oder f zum Gewinnen. In diagonaler Richtung ergibt sich die Möglichkeit, z.B. {a1, b2, c3, d4}, auf jeden Fall benötigt Gelb hierzu ein Feld aus b2 bis b6 oder f2 bis f6. Und in vertikaler Richtung ist natürlich immer etwas Möglich, jedoch für Rot leicht zu verhindern.

Stellt Rot diese Überlegungen an und zählt die verbleibenden Felder kommt er darauf das sich die Situation aus Diagramm 1.2.3 ergibt Gelb also gezwungen ist b2 oder f2 zu spielen, deshalb spielt Rot al. Das Spiel ist also vorbei Gelb verliert.

Wir sehen das Spiel kann bei guten Spielern bereits nach nur sechs Runden ent­schieden sein, aber wo war der Fehler? Wie wir oben gesehen haben ist es schwer den Spielbaum komplett zu untersuchen aber wir geben eine Möglichkeit an ein Einen Sieg in diesem Spiel zu erreichen. Gehen wir in Runde 4. Bis hierin wurde folgendes gespielt:

1.  dl, d2

2.  d3, el

3.  d4, e2

4.  d5, d6

Und haben die Situation in Diagramm 1.2.4

Spielt Gelb nun al anstelle von cl wäre ein Möglicher Spielverlauf: 1. dl, d2

2.    d3, el

3.    d4, e2

4.    d5, d6

5.    al, c1

6.    c2, e3

7.    e4, bl

8.    a2, c3

9.    c4, c5

10.     e5, e6

11.     c6, gl

12.     g2, g3

13.     g4, g5 13. g6, a3

14.     a4, a5

15.     a6, fl

16.     f2, f3

17.     f4, f5

18.     f6, b2

Und Gelb gewinnt mit {a4, b3, c2, d2}. Also bereits in der 4 Runde wir der Grundstein über Sieg und Niederlage gelegt, voraus gesetzt der „menschliche" Faktor, also Fehler, bleiben aussen vor. Zur Verdeutlichung zeigen wir nochmals die Situation in Runde 15 nachdem Gelb gespielt hat in Diagramm 1.2.4.:

			00
•		0				•
•		•		0		•
				00
		..		0		•

Abbildung 11: Diagramm 1.2.4

Welche Erkenntnisse können wir also aus diesem Abschnitt ziehen?

Auch wenn es ,nur eine" Spielsituation ist hat man doch schon zwei wesentliche Dinge sehen können. Zum einen welche Rolle die Spalte b und f spielen. Es war hier zwar konstruiert, aber man erkennt trotzdem das es ohne diese beiden Spalten nicht Mög­lich ist einen Vierer in einer Diagonalen oder Horizontalen zu erreichen. Da es aber im Prinzip bei einem fehlerfreien Spiel nicht Möglich ist einen waagrechten Vierer zu schaffen, ohne den Zugzwang zu Nutzen, also den Gegner zu zwingen einen anderen Vierer zu verhindern, kann diese Möglichkeit ausgeschlossen werden. Der zu verhin­dernde Vierer wäre nämlich ein Horizontaler oder Diagonaler, was uns wieder in die Spalten b und f bringt.

Die Kontrolle oder den Nutzen dieser beider Spalten ist also der Schlüssel zum Ge­winnen.

2.2.2 Gute und schlechte Gewinnmöglichkeiten

Im vorherigen Abschnitt haben wir gesehen, dass es an den letzten beiden Spalten hängt ob man gewinnt oder nicht, jetzt wollen wir untersuchen welche Felder in die­sen Spalten zum Gewinn führen und welche also Gewinnmöglichkeiten also um diese Spalten herum geschaffen werden müssen um am Ende zu gewinnen.

Gewinnen kann man nur wenn der Gegner gezwungen ist einen Stein in das Feld unter dem eigenen Gewinnfeld zu werfen, und wir haben gesehen, dass wenn beide Spieler keine Fehler machen, es meisten dann passiert wenn alle bis auf die zwei Spal­ten bereits gefüllt sind, diese beiden aber leer. Welche Situation ergibt sich folglich. Der Gelb Spieler wird in diesem Fall immer die ungeraden Felder erhalten, der Rote die geraden.

Daraus lässt sich folgern das man nur der Spieler gewinnen kann, welcher seine Ge­winnmöglichkeiten nach diesen Voraussetzungen geschaffen hat, ansonsten wird das Spiel unentschieden enden.

Sollten beide Spieler nach diesen Voraussetzungen gespielt haben, gibt es zwei Mög­lichkeiten, erstens befinden sich die Gewinnmöglichkeiten in der selben Spalte, bzw. sind diese in beiden Spalten in der gleiche Zeile, gewinnt diejenige, welche die niedriger Zeilenzahl hat, was für jeden klar sein sollte. Was aber wenn die Gewinnmöglichkeiten in verscheiden Spalten und verschiedenen Zeilen sind.

Um diesen Fall zu untersuchen greifen wir auf ein Beispiel zurück. Das Spiel sei bis zu der Situation in Diagramm 1.2.5 vorgeschritten.:

		•			•	0
•			•
		O				•
•			0			•
			•		•
•		•			•

Abbildung 12: Diagramm 1.2.5

Beide Spieler haben hier eine für sie gute Gewinnsituation geschaffen, Gelb mit b3, also ungerade, zum Vierer {a4, b3, c2, dl} und Rot mit e2, also gerade, zum Vierer Ic4, d3, e2, f 11. Da eine ungerade Anzahl an Steinen gespielt wurde, bzw. eine unge­rade Zahl an Feldern frei ist, muss Rot als nächste werfen. (Den ersten Stein aus der aktuellen Runde haben wir schon gesetzt, da ein Wurf in die Spalte e für Gelb schon

zur Niederlage führen würde, er also gezwungen ist dort zu werfen) Welche Möglich­keiten ergeben sich für Rot? Er kann nur in b2 oder el werfen. Das Feld b2 bedeutet die sofortige Niederlage, el würde seine Gewinnmöglichkeit zerstören. Dennoch wird er das kleinere Übel wählen und el wählen. Daraufhin wird die Spalte e bis oben gefüllt und Rot ist wieder am Zug.

Es ergibt sich die Situation in Diagramm 1.2.6.

		•			•	•
•			•	•
		•				•
•			•	•		•
			•		•
•		•		•	•

Abbildung 13: Diagramm 1.2.6

Nun muss Rot das Feld b2 wählen, Gelb antwortet mit b3 und wird gewinnen.

Aus diesem Beispiel lässt sich folgendes ableiten. Ist eine Situation gegeben in der die Spieler jeweils für sich gute Gewinnmöglichkeiten geschaffen haben, also Gelb ungerade und Rot gerade, wird GElb immer dann gewinnen wenn diese in unter­schiedlichen Spalten und Zeilen liegen. Aber warum?

Die Antwort ist ganze einfach, sind bis auf zwei Spalten alle gefüllt, darf Gelb immer beginnen und wird die ungeraden Felder haben, weshalb seine Gewinnmöglichkeit gut ist. Da die Gewinnmöglichkeit für Rot in einer anderen Spalte liegt, kann Gelb gefahrlos in der für ihn guten Spalte den ersten Stein werfen. Nun ist die Anzahl der freien Felder immer ungerade und Rot ist an der Reihe. Aber es bleibt ihm nur noch die andere Spalte übrig, da er sonst verlieren würde. Daraus folgt aber, dass im Prinzip nur noch eine gerade Anzahl von Feldern frei ist, nämlich 6 in dieser Spalte. Die zu erreichenden Felder drehen sich also in Bezug auf gerade/ungerade um, die ge­rade Möglichkeit wird nutzlos. Ist diese Spalte bis auf den vorletzten Platz gefüllt ist erneut nur noch eine gerade Anzahl übrig und Gelb ist an der Reihe, das Verhältnis dreht wieder und Rot muss den fatalen Stein ziehen.

Wir sehen das auch hier der Zugzwang eine besondere Rolle spielt und deshalb seine Kontrolle wichtig ist. Und auch wenn wir andere spricht in höheren Zeilen gelegene Möglichkeiten haben ist es die selbe Situation wie in unserem Beispiel, da es nur auf gerade und ungerade Felder ankommt.

Fassen wir nun die beiden letzten Abschnitte zusammen.

Bei fehlerfreiem Spiel führt der Gewinn nur über horizontale und diagonale Vierer, entweder direkt, weil es keine anderen Möglichkeiten mehr gibt, sprich alle bis auf zwei Reihen gefüllt sind, oder weil man über den Zugzwang eine Situation schafft in der der Gegner über eine horizontale oder diagonale Gewinnmöglichkeit verhindert,

dass man den vertikalen Vierer nicht blocken kann.

Dann haben wir gesehen, dass sollte beide Gewinnmöglichkeiten in der selben Spalte oder aber in der beiden Spalten die selben Felder sein, ist nur diejenige Gewinnmög­lichkeit „gut" welche in der Richtigen Zeile liegt, ungerade Zeile für Gelb, gerade für Rot. Es gewinnt dann jene mit der niedrigeren Zeilenzahl.

Es gibt also folgende Möglichkeiten:

1.      Gelb hat eine ungerade Gewinnmöglichkeit, Rot eine gerade Gewinnmöglichkeit Diejenige mit der kleiner Zeilenzahl gewinnt!

2.      Gelb hat eine gerade Gewinnmöglichkeit, Rot eine ungerade Gewinnmöglichkeit Das Spiel endet unentschieden!

3.      Gelb hat eine ungerade Gewinnmöglichkeit, Rot eine gerade Gewinnmöglichkeit Gelb gewinnt!

4.      Gelb hat eine gerade Gewinnmöglichkeit, Rot eine gerade Gewinnmöglichkeit Rot gewinnt!

Liegen die Gewinnmöglichkeiten in unterschiedlichen Spalten, ist die Sache etwas komplizierter, denn es gibt mehrere Möglichkeiten für die Spieler zu gewinnen. Neh­men wir an jeder Spieler hat genau eine Gewinnmöglichkeit in jeweils einer anderen Spalte und kann auch keine weitere schaffen. Man kann die folgenden aussagen treffen:

1.      Gelb hat eine ungerade Gewinnmöglichkeit, Rot eine gerade Gewinnmöglichkeit Gelb gewinnt! Wie oben gesehen.

2.      Gelb hat eine gerade Gewinnmöglichkeit und Rot eine gerade Gewinnmöglich­keit

Rot Gewinnt! Rot kann die gerade Möglichkeit von Gelb verhindern, und selbst gewinnen, da Gelb nur die ungeraden Felder besetzten kann.

3.      Gelb hat eine gerade Gewinnmöglichkeit, Rot hat ein ungerade Gewinnmöglich­keit

Das Spiel endet unentschieden! Es gelten die selben Voraussetzungen als wä­ren die Möglichkeiten in einer Spalte, da erst die des anderen

verhindert wird, bzw. man eher seine eigene aufgibt als den anderen gewinnen zu lassen.

Sollte Rot seine Gewinnmöglichkeit nicht aufgeben, und in die andere Spalte werfen, dann tauschen bei Spieler

gerade und ungerade Felder und Gelb gewinnt.

4.      Gelb hat eine ungerade Gewinnmöglichkeit, Rot eine ungerade Gewinnmöglich­keit

Das endet unentschieden, wenn Die Gewinnmöglichkeit nicht in der ersten Zeile ist.

Gelb beginnt, da es eine gerade Anzahl von freien Feldern gibt, und spielt in eine freie Spalte worauf Rot die

andere wählen wird. Nun wird zunächst Gelb seine Möglichkeit aufgeben und die Spalte wird gefüllt. Im Anschluß

bleibt eine ungerade Zahl an freien Feldern und Rot ist an der Reihe, woraufhin er auch seine Möglichkeit

aufgeben muss.

Natürlich haben wir hier ganz speziell Situationen betrachte und Ergebnisse bekom-men.Man kann diese, indem man an einer Stelle einen anderen Zug macht, ganz einfach ausser Kraft setzen, was wir im Beispiel in Diagramm 1.2.7 zeigen wollen.

•	•			•
			0			•
•	•			•
			•			•
•			0
•				•	•	•

Abbildung 14: Diagramm 1.2.7

Wir befinden uns scheinbar in der Situation das beide Spieler eine ungerade Gewinn­möglichkeit in unterschiedlichen Spalten haben, folglich sollte das Spiel unentschieden enden. Aber wenn man nach obiger Regel weiter spielt erkennt man das Rot sich eine weitere Möglichkeit zu gewinnen schaffen kann, und zwar in einem geraden Feld wie man in Diagramm 1.2.8 sehen kann, und deshalb die obigen Überlegungen hinfällig sind. Das Spiel endet mit Sieg für Rot.

•	•			•
			0		•	•
•	•			•
			•		•	•
•			0
•				•	•	•

Abbildung 15: Diagramm 1.2.8

Aber und darauf kam es uns ja in diesem Abschnitt an, wir können verschiedenen Situationen bestimmten Nutzen zuordnen, auch ohne das ganze Spiel zu kennen. Wir können prinzipiell abschätzen welche Gewinnmöglichkeiten besser sind, und wel­che Möglichkeiten für den Gegner es von vorne herein zu verhindern gilt.

Daraus folgt auch was jeder Spieler wahrscheinlich intuitiv macht und was wir bei je­dem Beispiel hier auch getan haben, und zwar immer mit dl zu beginnen. Wir halten

und somit nämlich immer die Möglichkeit offen eine Gewinnmöglichkeit in der ersten Zeile waagrecht zu haben. Wir machen dies, da wir gesehen haben das es nur über die waagrechten und diagonalen Vierer Gewinnchancen gibt, dazu aber immer die Spalte d benötigt wird, und wir ungerade Möglichkeiten brauchen, also uns die Möglichkeit eines Vierers in der ersten Zeile halte.

Umgekehrt sollte man als roter Spieler immer Gewinnmöglichkeiten für Gelb in der ersten Zeile verhindern da dies die stärksten sind.

2.2.3 Zugzwang und dessen Kontrolle

Wir haben im letzten Abschnitt immer wieder Situationen erzeugt in denen ein Spie­ler gewinnt und dabei stillschweigend das Phänomen des „Zugzwangs" hingenommen, ohne näher darauf einzugehen.

Dies hat den Grund, dass es ohne den Zugzwang nicht möglich ist zu Gewinnen, wie wir gesehen haben, und deshalb wollen wir diesem Thema einen eigenen Abschnitt widmen.

Zunächst einmal was bedeutet Zugzwang.

Damit beschreiben wir eine Situation in der ein Spieler sozusagen gezwungen ist einen bestimmten Zug zu tätigen, sei es weil kein anderes Feld gespielt werden kann wie in Diagramm 1.2.3, oder weil er eine Niederlage abwenden muss, indem er eine Vierer­möglichkeit verhindert, wie in Diagramm 1.2.9 wo Rot nur b1 oder e1 spielen kann um einen möglichen Vierer von Gelb zu verhindern.

Abbildung 16: Diagramm 1.2.9

Mit Hilfe des Zugzwangs lässt sich also spätestens nach 15. Runden eine Gewinnsi­tuation schaffen. Aber wem wir dieser am Ende Nutzen? Wer kontrolliert also den Zugzwang?

Zunächst wollen wir sehen was es bedeutet den zugzwang zu kontrollieren und ge­hen dazu nochmals zu unserem Beispiel aus 1.2.2.1. Wir haben gesehen, das nach der fünften Runde das Spiel schon entschieden ist. Aber warum genau?

In allen Runden danach besetzt Gelb nach und nach die ungeraden Felder und Rot

wird immer in die selbe Spalte Spielen, so ergibt sich für Gelb keine Gewinnmöglich­keit und am Ende wird Gelb entweder b1 oder fl spielen müssen. Rot kontrolliert also den Zuzwang, da Gelb keine Möglichkeit hat die geraden Felder zu spielen. Dies resultiert daraus, das noch eine gerade Anzahl an Feldern übrig ist die nicht zu einem Sieg von Rot führen würden, folglich am Ende die Situation aus Diagramm 1.2.3 übrig bleibt.

Wir können also dann von Kontrolle des Zugzwngs sprechen, wenn ein Spieler die Möglichkeit hat durch eine Strategie, z.B. immer die selbe Spalte zu Spielen wie der andere, alle möglichen Gewinnpositionen zu verhindern, so dass er am Ende seine spielen kann.

Wie kann man also die Kontrolle über den Zugzwang erhalten, und ist Möglich die Kontrolle vom anderen übernehmen?

Wie ist die Situation zu Beginn des Spiels. Intuitiv kann man denken das Rot na­türlich auch hier die Möglichkeit hat immer in die selbe Spalte zu spielen, es würde ihm aber nichts nützen, da Gelb dann in der ersten Zeile einen Vierer bekommt. Wir legen also fest, dass am Anfang kein Zugzwang existiert.

Wie können wir ihn aber schaffen?

Es hängt sicher davon ab welche Gewinnsitiation man schaffen kann. Gelb muss nach obigen Überlegungen eine Gewinnmöglichkeit in einem ungeraden Feld schaffen, und zugleich verhindern, dass Rot eine gerade Gewinnposition in der gleichen Spalte aber in einer kleineren Zeile schafft. Idealer Weise also für Gelb in ersten oder dritten Zeile, und Rot nicht in der Zweiten, und natürlich auch keinen anderen davor.

2.3 Vorige Überlegungen und der Spielbaum

Nun wollen wir mit den nun erworbenen Erkenntnissen versuchen den Spielbaum zu vereinfachen um das Spiel wenigstens im Ansatz mit Hilfe der Spieltheorie zu unter­suchen.

Natürlich werden wir auch so nicht den ganzen Spielbaum analysieren können, aber wir schaffen eine gewisse Spieltiefe, also wir betrachte hier 6 Steine und wollen so versuchen den bestmöglichst eine Strategie hierfür zu zeigen.

Wir gehen davon aus das die Spieler immer Positionen erreichen wollen die zu mög­lichen Vierern gehören oder aber die ihnen die Möglichkeit geben in einem folgenden Zug eine Viererposition zu erreichen.

Zunächst können wir im ersten Zug annehmen, dass Gelb immer dl wählen wird, wir verkürzen ihn also von oben. Damit folgt dann folgender Spielbaum:

Abbildung 17: Diagramm 1.2.10

Nun überlegen wir uns welche Gewinnmöglichkeiten für Gelb denn überhaupt Sinn­voll sind, also welche sind mit dem letzten Stein in ungeraden Feldern in den Zeilen 1 und 3 zu vervollständigen. Nutzen wir zusätzlich noch aus, dass wir alle Ergebnisse in den Spalten a bis e Spiegel oder verschieben können ergeben sich die folgenden. {al, bl, cl, dl}, {a3, b3, c3, e3}, {al, b2, c3, d4},

Für den roten Spieler ist es am besten gerade Gewinnmöglichkeiten zu schaffen, und zwar in der zweiten Zeile. Daraus ergeb sich die folgenden Vierer:

{a2, b2, c2, d2}, {a1, b2, c3, d4} dies sind bis auf Spiegeln und verschieben die einzigen Vierer in den unteren vier Zeilen, {d4, c3, b2, dl} fällt weg da Gelb als erstes dl spielt. Welche Möglichkeiten ergeben sich daraus für Rot. Er wird möglichst schon im ersten Zug verhindern wollen, dass Gelb ein weiteres wichtiges Feld besetzt, also eines der obigen Viererfelder. Das einzige an das er herankommt ist aber al. Das Spielen dort ist aber nicht hinderlich für Gelb, da er gespiegelt auch g1 spielen kann. Also wird Rot ein für sich wichtiges Feld besetzen hier also d2 oder vorbereitende für den nächsten Zug ei. Für Gelb spielt das keine Rolle er wird in der zweiten Runde al spielen um ein weiteres Viererfeld zu bekommen. Rot wird entweder mit versuchen die Tupel {el, e2}, {el, d2}{gl, el}, {gl, d2} zu bekommen Es ergeben sich also folgende Zug Möglichkeiten und und unter weglassen der Äste der Baum aus Diagramm 1.2.11.

1.    dl, {el, d2, gl}

2.    al, {e2, d2, g2}

Welche Möglichkeiten sind nun wieder die besten für Rot?

Im linken Ast hat er zwei Möglichkeiten, entweder er behindert Gelb mit a2, ei oder er versucht seine Gewinnmöglichkeit aufzubauen indem er el spielt. Wir haben hier also folgende Möglichkeiten:

Abbildung 18: Diagramm 1.2.10

1 dl, d2

2. al, {el, a2, c1}

Im Mittleren Ast hat Rot wieder die Möglichkeit Gelb zu behindern, mit a2, cl, oder selbst seine Gewinnmöglichkeit weiter aufzubauen mit e2, oder d2. Das ergibt folgen­de Züge:

1.  dl, el

2.  al, {a2, cl, d2, e2}

Im rechten Ast sehen wir, dass es für den zweiten Spieler eigentlich nicht gut war gl zu spielen, da Gelb mit al geantwortet hat und er zwar versuchen könnte den Vierer {d2, e2, f 2, g2} zu erreichen, aber wir haben gesehen, dass er trotzdem verlieren wür­de, schafft es Gelb auf der anderen Seite eine der obigen Möglichkeiten aufzubauen. Diesen Ast verfolgen wir also nicht mehr weiter, konnten also in der ersten Runde gl schon als Zug mit geringerem Nutzen identifizieren. Es ergibt sich der Baum im Diagramm 1.2.11:

Abbildung 19: Diagramm 1.2.11 Betrachten wir die nächste Runde.

Wir beginnen auch hier beim Linken Ast, also der Historie {d1, d2, al, a2}.

Welche Möglichkeiten hat Gelb?

Positionen seiner Vierer wären bl, cl, a3 und d3, also wird er eine von ihnen Spielen. Rot kann kann bzw. darauf antworten mit cl,bl,el,a3 oder d4.

Im nächsten Ast {dl, d2, al, cl} ist für Gelb nützlich d3 oder c2 zu spielen, Rot kann a2, c2, c3, el, oder d4 spielen jeweils abhängig von der Wahl von Gelb.

Und im dritten Ast {d1, d2, al, el} kann Gelb a2, bl, cl oder d3 und Rot muss bzw. kann mit bl,cl, a2 oder e2 antworten.

Im Ast {dl, el, al, a2} Im Ast {dl, el, al, cl} Im Ast {d1, el, al, e2} Im Ast {dl, el, al, d2} Es ergibt sich der vereinfachte Spielbaum in Diagramm 1.2.12 mit nun nur noch 60 Enden.

Abbildung 20: Diagramm 1.2.12

Wir haben hier natürlich sehr viele intuitive Verhaltensweisen vorausgesetzt, aber immer im Hinterkopf die Ergebnisse aus Abschnitt 1.2.2 gehabt. Dies ist in unseren Augen eine vertretbare Vereinfachung, und wir können nun indem wir verschiedenen Positionen einen Wert geben, in den ersten 6 Zügen durchaus so etwas wie eine „beste" Strategie finden.

Betrachten wir die Historien die bis zum 6. Zug entstanden sind, und bezeichnen ihre Menge mit H6.

H6 = {dl, d2, al, a2, a3, bl}, {dl, d2, al, a2, a3, cl}, {dl, d2, al, a2, a3, el}, {dl, d2, al, a2, bl, cl}, {dl, d2, al, a2, cl, bl}, {dl, d2, al, a2, d3, a3}, {d1, d2, al, a2, d3, bl}.{dl, d2, al, a2, d3, cl}, {dl, d2, al, a2, d3, d4}, {dl, d2, al, cl, d3, a2}, {dl, d2, al, cl, d3, c2}, {dl, d2, al, cl, d3, d4}, {dl, d2, a1, cl, c2, a2}, {dl, d2, al, c1, c2, c3}, {dl, d2, a1, c1, c2, el}, {dl, d2, al, e1, bi, cl}, {dl, d2, al, ei, cl, dl}, {dl, d2, al, ei, a2, a3}, {dl, d2, al, ei, a2, cl}, {dl, d2, al, el, a2, e2}, {dl, d2, al, el, d3, a2}, {dl, d2, al, el, d3, cl}, {dl, d2, al, el, d3, e2}, {dl, el, al, d2, bl, cl}, {dl, el, al, d2, cl, bl}, {dl, el, al, d2, a2, e2}, {dl, el, al, d2, a2, a3}, {dl, el, al, d2, a2, d3}, {dl, el, al, d2, a2, cl}, {dl, el, al, d2, d3, e2}, {d1, el, al, d2, d3, a2}, {dl, el, al, d2, d3, bl}, {dl, e1, al, d2, d3, cl}, {d1, e1, al, d2, d3, d4}, {dl, e1, a1, e2, bi, cl}, {d1, e1, al, e2, cl, bl}, {dl, el, al, e2, a2, a3}, {d1, el, al, e2, a2, d2}, {d1, el, al, e2, a2, cl}, {dl, el, al, e2, d2, a3}, {dl, el, al, e2, d2, d3}, {dl, el, al, e2, d2, e3}, {dl, el, al, cl, bl, a2}, {dl, el, al, ei, bl, b2}, {dl, el, al, cl, bl, c2}, {d1, el, al, cl, bl, d2}, {dl, el, al, cl, c2, bl}, {d1, el, al, cl, b2, d2}, {d1, el, al, cl, b2, e2}, {d1, el, al, cl, a2, c2}, {d1, el, al, cl, a2, d2}, {dl, el, al, cl, a2, e2},

el, al, cl, d2, e2}, {dl, ei, al, cl, d2, g1},             ei, al, a2, bl, ei}, {dl, ei, al, a2, cl, bll,

{dl, el, al, a2, d2, a3}, {dl, el, al, a2, d2, bll, {dl, el, al, a2, d2, d3}

Geben wir uns nun folgende Nutzenfunktion vor, welche hier rein willkürlich ist aber

verdeutlicht wie man vorgehen könnte.

u : H₆ -> R² mit

(x₁, y_i, x₂, y₂, x₃, y₃) 1--> (E 2 • ¹{Ein Viererfeld ist besetzt}(Xi) + 1 ' ¹{Ein gegnerisches Vierfeld ist besetzt}(Xi) + 0

E[² • ¹{Ein Viererfeld ist besetzt}(Yi) +¹ • ¹{Ein gegnerisches Vierfeld ist besetzt}(Yi) + ⁰ '¹{EinsonstigesFeld ist beset;

Dann ergibt sich der Nutzen aus den einzelnen Ästen wie in Diagramm 1.2.13, wobei wir die rechten Äste weggelassen haben, da Rot mit el keinen Nutzen bekommt, und so über 4 nicht hinaus kommt.:

J3

I            I   1                                                                                              1   I

(0,4) (6,4) )6,) _,0,43(64)16 446 51(6,9(                                        0)5,4)(5,3)(6,3)(6 ays ax5 ax5 ^,)(5 ⁴)(e

Abbildung 21: Diagramm 1.2.13

Mit obigen Annahmen wird das Spiel also auf einen Ast mit der Verteilung (6,5) hinauslaufen, wobei wenn wir die Äste verfolgen hier die folgenden Historien in Frage kommen:

{d1, d2, a1, a2, a3, b1}, {dl, d2, a1, cl, d3, a2},      d2, a1, c1, d3, c2}

Weitere Aussagen lassen sich mit dieser Spieltiefe natürlich nicht machen, weshalb wir etwaige besser Züge nicht ausschließen können, ebenso wenig wie man sagen kann das ist die bester oder einzige Eröffnungsvariante für Vier Gewinnt.

Eine mögliche Position nach diesen sechs Zügen könnte z.B. so aussehen wie in Dia-

gramm 1.2.14, hier haben wir die Historie          d2, al, a2, a3, b11 gewählt.

Abbildung 22: Diagramm 1.2.14

Es handelt sich hier um eine starke Vereinfachung aber wir sehen wie man es schaffen

kann das Spiel zu analysieren.

Genau auf solchen Annahmen basieren die meisten Computerspiele zu Vier Gewinnt, man betrachtet nur eine gewisse Tiefe, und vergibt jedem Feld einen Nutzen. Natürlich sind die Einschränkungen nicht so gravieren wie hier beim von der Hand bearbeiten aber es soll ja auch nur ein Versuch sein das Spiel in den Griff zu bekommen.

Wie man es mit dem Computer bearbeiten kann, und welche Lösung gut ist, aber auch wo die Grenzen sind behandeln wir in Teil II dieser Arbeit.

Teil II

Programmierung „4 Gewinnt"

3 Ziel der Programmierung einer Künstlichen Intel­ligenz

Als Ziel haben wir es uns gesetzt eine künstliche Intelligenz (KI) zu programmieren, die es ermöglicht gegen einen Computer zu spielen. Die KI sollte dabei so angelegt sein, dass sie im Schwierigkeitsgrad angepasst werden kann, allerdings auch ein ernst zunehmender Gegner für den menschlichen Spieler ist. Da das Spiel wie bereits darge­legt gelöst ist und für den beginnenden Spieler zu gewinnen, wäre es "langweilig", wenn der Computer perfekt wäre, da ein Spiel gegen ihn dadurch an Reiz verliert, wenn man sich bewusst ist, nur verlieren zu können. Aus diesem Grunde soll er unterschiedlich "klug" eingestellt werden können.

4 MinMax Algorithmus

Für symmetrische Spiele in extensiver Form ist eine Bestimmung von optimalen Stra­tegien durch Elimination durch strikte Dominanz möglich. Auf diesem Prinzip grün­det sich der MinMax Algorithmus.

4.1 Funktionsweise

Im Folgenden sei also nun für Spieler 1 die Nutzenfunktion besser je größer ihr Wert ist, für Spieler 2 daraus folgernd je kleiner ihr Wert ist. Wobei im Moment nur die Möglichkeiten -1 Für Sieg von Spieler 2, 0 für ein Unentschieden sowie +1 für einen Sieg von Spieler 1 gegeben ist.

Der Ausgang eines Spielfeldes lässt sich bestimmen indem der Spielbaum unterhalb der Aktuellen Situation aufgestellt wird und nun von unten nach oben die Bewertun­gen wie Eliminiert werden. Ist An einem Teilbaum der Tiefe 1 also nun Spieler 1 am Zug so wird er die Beste Möglichkeit für sich wählen. Man kann also dem Knoten über der Entscheidung den Wert dieser Besten Möglichkeit zuordnen und den Teilbaum eliminieren. Für Spieler 2 ist diese Elimination mit dem geringsten wert analog. Zum veranschaulichen dieses Algorithmus sei ein Spiel S' = (M, E n Z, P, u) gegen durch abwechselndes ziehen von Spieler 1 und Spieler 2 gegeben sowie durch folgen­den Spielbaum:

5.1 Verfeinerung der Nutzenfunktion

Die Verfeinerung der Nutzenfunktion basiert nun auf grundlegenden Verhaltensmus­tern die wir bereits als Optimal dargestellt haben im ersten Teil.

Wir bewerten nun jedes Spielfeld aus der Historie wie folgt:

Ziel des Spieles ist es eine Reihe aus 4 eigenen Steinen aufzubauen. Für diese Reihe gibt es nur eine Begrenzte Anzahl von Möglichkeiten (69 Blöcke). Wir bewerten nun alle diese Möglichkeiten und geben ihren Anteil an die Nutzenfunktion wieder. Ist ein Block besetzt mit einem Stein von Spieler 1 so erhält gibt der Block einen Anteil von 10 an die Nutzenfunktion, Ist ein Block besetzt mit 2 Steinen von Spieler 1 so gibt er einen Anteil von 100 an die Nutzenfunktion. Bei 3 Steinen ist der Anteil 10.000.

Hat ein Block 4 Steine so ist das Spiel gewonnen und der Anteil ist 100000000. Die Anteile für Steine von Spieler 2 sind jeweils negativ. Des weiteren kann ein Block keinen Anteil liefern wenn schon Steine von beiden Spielern in ihm liegen.

Diese Werte können natürlich variiert werden.

Der Wert für einen Vierer sollte sehr groß gewählt werden, damit ein Sieg unbedingt das Erstrebenswerte bleibt, es darf also nicht möglich sein mit Ansammlung von an­deren Möglichkeiten mehr Punkte zu machen als mit dem eigentlichen Gewinn des Spiels. Die Verfeinerung der Nutzenfunktion soll also nicht die Gewinnsituationen verändern.

Mit dieser einfachen Nutzenfunktionsverfeinerung ist nun schon eine bessere Unter­scheidung der Spielmöglichkeiten gegeben, auch wenn noch kein Sieg innerhalb der Tiefe der Suche auftritt.

Weitere Verfeinerungen wären möglich für bekannt "gute Positionen", wie zum Bei­spiel Zwickmühlen bei denen bereits 2 Dreier existieren, deren offenes Feld (mögliches Gewin Eine andere mögliche Veränderung wäre es Dreier nach der Höhe zu bewerten, usw.

5.2 Beschreibung des Alpha-Beta Cuts in Pseudocode

Zur vorherigen Erklärung sollen zuerst einige Konventionen für den Pseudocode er­läutert werden.

Allgemein ist die Syntax vollkommen frei, er muss nur vom Menschen verstanden wer­den. Eine Funktion wird aufgerufen auf dem Aktuellen Spielfeld bzw. der aktuellen Position im Spielbaum.

Mit S = {s_i, ... s_k} soll die Menge der Wahlmöglichkeiten an auf dem Aktuellen Spielfeld bezeichnet werden (endlich und insbesondere abzählbar).

Außerdem soll für ein s E S s. funktion definiert werden. es Bezeichnet die Funktion Aufgerufen auf eine Simulation von s.

Zuerst soll allerdings noch die Funktion max(n)und min(n) definiert werden. Sie sind, wie danach die Funktionen abmin, abmax (für Alpha-Beta) rekursiv definiert: max(0) = min(0) = wert()

max(n) = max{s. min(n — 1)1s E S}

max(n) = min{s. max(n — 1)1s E S}

Pseudocode abmax(n, a, 0) =

if (n = 0) return wert ()

:= 1;

while(i <= n){

w := s_i. abmin(n — 1, a, ,ß);

if(w >= _/3) return _/3;

if(w > a) a := w;

+ +;

}

return a;

Analog ist definiert:

Pseudocode abmin(n, a, 0) =

if (n = 0) return wert()

i := 1;

while(i <= n){

w := s_i. abmax(n — 1, a, _/3);

if(w <= a) return a;

if(w < 0) ß := w;

+ +;

}

return _/3;

5.3 Korrektheit des Algorithmus

Mit der Definition wird nun ein Algorithmus gegeben der effizienter rechnen kann, da einige Rechenschritte wegfallen, wenn der Bedingte Befehl 1 ausgeführt wird also ein Cut ausgeführt wird.

Diese Vorgehensweise ist also nur von Nutzen, wenn unter gewissen Voraussetzungen die Werte der Funktionen abmin und abmax mit den klassischen min und max über­einstimmen.

Hierzu erst ein Lemma über den Wert von abmin und abmax

5.3.1 Lemma

Sei n > 0, a, 0 E IR, a < )3

  {a            für max(n) < a

abmax(n, a, _/3) = max(n) für a < max(n) < _/3

/³           für 0 < max(n)

  {a           für min(n) < a

abmin(n, a, _/3) = min(n) für a < min(n) < _/3

für _/3 < min(n)

Beweis: Das Lemma soll bewiesen werden durch Induktion nach n. Dabei werden aufgrund der Symmetrie nur die Schritte für die Maximumsfunktion dargelegt. Der Induktionsanfang ist gegeben per Definition von Max(0) die ebenfalls den

Wert des Aktuellen Spielfeldes darstellt. Sei nun also die Aussage gegeben für < n

1.max(n) > _/3 Es gilt max(n) = max{s. min(n — 1)1s E S} Sei nun also 1 < 1 < k,1 minimal mit s_l. min(n — 1) = max(n)

Nun ist s_i.min(n — 1) > ß s_i. abmin(n — 1, a, ß) = ßVa

Bei der Überprüfung von 1-ten Schritt der Schleife ist also w = s_l. abmin(n-1, a, ß) = und es wird als Wert für abmax(n, ce, _/3) zurückgegeben.

2.max(n) < a max(n) = max{s. min(n — 1)1s E S} ~Vlk:s_i.min(n-1)

< < k : s_i. abmin(n — 1) ¹1 = w

Keiner der Bedingten Befehle wird ausgeführt. wird unverändert am Ende zurückgegeben.

sonst Es gilt: a < max(n) <

V1 s_i. min(n — 1) <ß

Sei 1 < 1 < k, 1 minimal mit s_l. min(n — 1) = max(n) =V1 < i < 1 : s_i. min(n — 1) E [—co, max(n)[

> V1 < i < 1 : s_i. abmin(n — 1) E [ce, max(n)[ 1-ten Durchgang ist a < s_l. min(n — 1)

i.v.

>a< s_t. min(n — 1) <                    abmin(n — 1, a, 0) = s_k. min(n — 1)

Nun wird der Bedingte Befehl 2 ausgeführt und von nun an ist a

s_l. abmin(n — 1, a, 0) = s_t. min(n — 1) = max(n)

V/ < i < k : s_i. min(n — 1) < a = s_l. min(n — 1) = s_i. abmin(n — 1, a, _/3) =

aha

kein weiterer bedingter Befehl wird ausführt.

keine weitere Änderung von a

max(n) wird zurückgeben.

5.3.2 Korollar

n > 0

abmax(n, —oo, oo) = max(n) abmin(n, —oo, oo) = min(n)

5.3.3 Korollar

Wenn gilt dass für die Funktion wert() immer gilt: a < wert() < ß

abmax(n, —oo, oo) = max(n) abmin(n, —oo, oo) = min(n)

Beweis: Da a < wert() < ß =a < max(n) < ß Für min analog.

6 Implementierung

Für die Implementierung des Algorithmus haben wir PHP (PHP: Hypertext Prepro-cessor) gewählt.

Dabei muss beachtet werden dass noch einige Änderungen notwendig sind, um einen spielenden Computer zu erschaffen. Er muss nicht nur seine jetzige Situation mit ei­ner gewissen Tiefe n bewerten, sondern er Bewertet die Situation seines Gegners mit einer Tiefe n — 1 und wählt dann die Möglichkeit aus die am Besten ist.

Ergeben mehrere Strategien den besten Wert soll der Zufall entscheiden, dadurch ent­steht eine weiter gewisse Dynamik im Spiel des Computers.

Die graphische Oberfläche ist sehr schlicht gehalten und soll dennoch eine intuitive Bedienung des Spiels ermöglichen.

Als erstes wird ein Schwierigkeitsgrad gewählt (er legt die Tiefe n des Alpha-Beta-Cut Algorithmus fest). Anschließend tätigt der Spieler seinen ersten Zug, der Computer zieht automatisch das für ihn optimale Feld.

Vier gewinnt (Schwierigkeit: 4)

neues spie]

Dewertuneen einblenden

Bereehnuri dauerte 0.134 SLkundcn.

Rudi

Als zusätzliche Information kann die vom Computer getätigte Bewertung der 7 mög­lichen Züge eingeblendet werden. Dies ist insbesondere dann von Interesse, wenn man der Meinung ist, dass der Computer gerade einen Fehler getan hat oder sich anders verhalten hat als bei einem vorherigen Spiel in der selben Situation, dies ist dann ein Grund des Zufallsgenerators bei Gleichwertigen besten Möglichkeiten.

Vier gewinnt (Schwierigkeit: 3 )

Bewertung für A= -10

nues 5p                                     Bewertung für B -20

Bewertung für C = 10400

Berechnung dauerte 0.0    .cricun _{Bewertung für]) 130}

Runde 113                                Bewertung für E = 20320

E  FFPLEF Brwvirctin für P 104450 1-77PPET Bewertung für G = 518.80

E  FF

E  FFBBF^-1^—

E n^—BREI^—

BEF

6.1 Bekannte Fehler

In niedrigen Schwierigkeitsstufen kann es dazu kommen, dass ein Computer sich nicht " Intelligent" verhält. Das hat damit zu tun dass er das Spiel falsch bewertet, da er nicht weit genug vorhersehen kann (die Tiefe der Suche ist zu gering). So kann er auf Stufe 1 nicht sehen was der Gegner tun könnte, da er nur den Wert des Spielfeldes direkt nach dem Zug bewertet. Selbst auf Stufe 2 kann er nur einen Sieg seines Geg­ners verhindern, wenn dieser den Sieg nur mit einer einzigen Position erreichen kann. Eines dieser Typischen Spielverläufe ist das "Aufsetzen" auf die Spielersteine. Die Er­klärung hierfür ist einfach: Der Computer bewertet die Unterbunden möglichen Vierer nach oben und den eigenen Aufbau eines möglichen Vierers höher als eine frühzeitige Verhinderung eines Waagerechten Vierers seines Gegners.

Vier gewinnt (Schwierigkeit: 1

Ecue

Dcwerouumci Aluadsa

Bereehniang dauerte 0.00 t Sekunden.

»^-kii3 ^-de 6

E   PPPPEP

ü   r•••rr

met eyrite

Ein weiteres "Problem" ist die "Verwandlungsschwäche" in höheren Schwierigkeitsgra­den. Dabei handelt es sich um das Phänomen, dass der Computer keinen Vierer setzt, auch wenn er es könnte. Auch dies hat eine einfache Erklärung. Er Bewertet mit einem recht weiten Blick in die "Zukunft" (z.b. 6 Züge). Wenn er nun neben dem soforti­gen Gewinn eine weiter Möglichkeit des Sieges sieht (und diese eventuell aufgrund der Weiteren Bewertungskriterien eine noch höhere Bewertung aufweist) kann (oder muss) er diese Möglichkeit wählen. Dies mag dem Spieler seltsam erscheinen, es kann aber keinen Sieg des Computers verhindern, nur hinauszögern, aus diesem Grund ist dies auch nicht als eigentlicher Fehler zu bewerten, nur als "Charakterschwäche" da dies für den Menschlichen Spieler arrogant wirken könnte.

6.1.1 Zeitaufwand

Um zu verdeutlichen, wie lange die Auswahl der optimalen Position dauert (je nach Schwierigkeitsgrad) wurde eine Alternative Spielform implementiert. Die Auswahl der Position funktioniert mit der selben Funktion, allerdings werden beide Spieler vom Computer gesteuert, gemessen wird die durchschnittliche Dauer pro Zug ab Schwierigkeitsstufe 4 (bei geringerer Stufe waren die Werte nicht auswertbar). Die

Tabelle 1: Zeiteinschätzung

Schwierigkeitstufe	Zugdauer in sec
4	0,117
5	0,567
6	1,61
7	9,73
8	43,2

Erhöhung der Schwierigkeit vervielfacht sich die Rechenzeit. Eine Schwierigkeit höher als 7 oder 8 würde aufgrund der Langen Wartezeiten keine Freude mehr bereiten. Bei der benötigten Zeit ist außerdem interessant, dass die Berechnung von 2 auf den ersten Blick völlig äquivalent en Spielfelder (z.b. Spiegelverkehrt) unterschiedlich lange dauern können. Dies ist rührt daher, dass für die Verkürzung der Rechenzeit die Cuts sehr wichtig sind, und diese sind abhängig von der Reihenfolge der Positionen zur Simulation. Da in der Implementierung diese Reihenfolge fest ist (von links nach rechts) kann eine Spiegelung des Spielfeldes Auswirkung haben auf die Rechenzeit.