Der Computer probiert alle Züge bis zu einer bestimmen Zuganzahl aus, die vom Level bestimmt wird. Auf Level 1, probiert er zwei Steinwürfe aus, einen für sich und einen für den Gegner. Auf Level 2 probiert er 4 Steinwürfe aus, auf Level 3, 6 und ab Level 3 immer einen mehr.
Für jede Stellung, die sich daraus ergibt, führt er eine Bewertung durch und wählt dann den Zug, der am Ende die beste Bewertung ergibt. Dabei führt er für die Züge des Gegners die gleiche Methode durch. Auf diese Weise rechnet er immer mit dem (nach dieser Methode ermittelten) besten Zug des Gegners, um den eigenen besten Zug zu bestimmen.
Wie bewertet der Computer eine Stellung?
Er zählt für jeden Stein seiner Farbe, wie viele Möglichkeiten es noch gibt, 4 in eine Reihe zu bekommen. Auf einem ansonsten leeren Spielfeld mit einem Stein unten links ergibt sich eine Bewertung von 3, weil es 3 Möglichkeiten gibt, von diesem Stein aus 4 in eine Reihe zu bekommen: nach oben, nach rechts-oben und nach rechts.
Diese Zählung wird für den Computer und den Gegnger vorgenommen. Aus diesen beiden Zählungen wird eine Stellungsbewertung berechnet, wobei das Zählergebnis des Gegners anders gewichtet werden kann als das eigene. Die Gewichtung wird durch die Angriffslust des Computers bestimmt. Bei extremer Angriffslust, spielt die Zählung des Gegngers nur lexikografisch eine Rolle, d.h. wenn zwei Züge nach der Zählung der eigenen Steine die gleiche Zahl ergeben, wird der Zug bevorzugt, der bei dem Gegner eine schlechteres Zählergebnis hat.
Die Angriffslust (=Strategie) des Computers wird per Zufall für ein Spiel gewählt. Sie kann 5 Werte annehmen zwischen der „fast nur eigene Chancen ausbauen“-Strategie bis zu „in erster Linie die Chancen des Gegner minimieren“. Dabei wählt der Computer in einem Level eine Strategie, mit der er einmal verloren hat, nicht noch einmal (wenn möglich).
Der Fall des Gewinns wird bewertet mit einer Zahl, die größer ist als alle Bewertungen, die nach dem obigen Schema gewonnen werden. Verlieren wird mit einer negativen Zahl bewertet.
Zur Geschwindigkeitsverbesserung wird der Alpha-Beta-Abbruch-Algorithmus verwendet. Die Idee dabei ist folgende: Der Gegner wird immer den Zug auswählen, der für den Computer der schlechteste ist. Deswegen brauchen nicht alle eigenen Züge berechnet zu werden, wenn der Gegner durch einen anderen vorhergehenden Zug (d.h. in einem anderen Zweig) die Möglichkeit hat, sich besser zu stellen als durch den grade analysierten. Alle anderen Züge im aktuellen Zweig brauchen nicht analysiert zu werden, weil es für den Gegner eine Möglichkeit gibt, den Computer schlechter zu stellen als in einem anderen Zweig.
Der andere Zweig wird also vom Computer bevorzugt, ohne alle Züge im aktuellen Zweig durchprobieren und bewerten zu müssen.
Dieser Algorithmus ist rein logisch, d.h. er schränkt die Ergebnis-Menge nicht ein, sondern verringert lediglich die Anzahl der notwendigen Operationen um exakt das das selbe Ergebnis wie bei der vollständigen Suche zu erzielen. Vielen Dank an Marc Becker, der mir diesen Algorithmus erklärt hat.
Verbesserungsmöglichkeiten
Geschwindigkeit
Um die Geschwindigkeit zu verbessern, rechnet der Computer schon während der Gegner noch überlegt. Dazu werden 7 Spielfelder erzeugt, dabei enthält jedes Spielfeld einen möglichen Zug des Gegners. Dann wird die Berechnung gleichzeitig für alle 7 Spielfelder gestartet. Hat der Gegner seinen Zug gemacht, so werden die Berechnungen gestoppt, die für einen anderen Zug des Gegners gestartet wurden und gewartet bis die Berechnung für den Zug, den der Gegner tatsächlich gemacht hat, abgeschlossen ist. Leider bringt das nicht sehr viel, denn die Voraus-Berechnungen müssen sich die Leistung des Prozessors teilen, sie kommen also nur mit ca. einem Siebtel der Geschwindigkeit einer einzelnen Berechnung voran. Bei Zuggeschwindigkeiten des Menschen zwischen 5 und 15 Sekunden pro Zug ergibt sich eine Zeitersparnis von 5/7 bis 15/7 also von 0,7 bis 2 Sekunden. Bei ca. 60 Sekunden Berechnung auf Level 5 ist das nicht mehr als ein Tropfen auf den heißen Stein 🙁 Leider habe ich die Beobachtung der menschlichen Zuggeschwindigkeit erst gemacht, nachdem ich das „auf Gegnerzeit rechnen“ schon programmiert hatte 🙁
Eventuell könnte es sich lohnen, die Routinen, die während der Berechnung gebraucht werden, auf Geschwindigkeit zu optimieren. Das habe ich mit mäßigem Erfolg und nicht besonderer Anstrengung versucht. In dem Quellcode sind beide (die „langsameren“ und die „schnelleren“) Routinen noch enthalten, die neuen haben das Anhängsel „schnell“. Wer Lust hat, hier was zu verbessern, gerne!
Eine andere Möglichkeit, das Spiel in höheren Levels erträglicher zu machen,
wäre, eine Eröffnungsbibliothek einzubauen. Wenn die Eröffnungsbibliothek abgearbeitet ist, geht es allerdings nicht schneller als bisher.
Denkbar wäre auch, den Computer „intelligenter“ zu machen, d.h. Vorausberechnungen abzubrechen, bevor die vorgegebene Berechnungstiefe erreicht ist, wenn irgendwie „absehbar“ ist, dass dieser Berechungszweig nicht in Frage kommt. Allerdings wird auf diese Weise dem Computer „kreatives Potential“ genommen, er kann keine Züge mehr machen, die auf den ersten Blick schlecht aussehen (= absehbar nicht in Frage kommen), sich aber nach einigen Zügen als Vorteilhaft erweisen. Alle Schachprogramme müssen mit solchen „Heuristik“ genannten Methoden arbeiten, weil dort die Anzahl der Möglichkeiten nach nur wenigen Zügen so groß ist, dass in akzeptabler Zeit nicht alle Züge bewertet werden können. Zur Entwicklung guter Heuristiken ist viel Spielerfahrung notwendig. Vielleicht hat jemand Lust, da heran zu gehen? – Ich werde mich (zumindest in absehbarer Zeit) nicht darum kümmern, weil das vorliegende Spiel sozusagen für mich der Test sein sollte, wie gut ein Computer ohne Heuristik, d.h. ohne eingebauter Spielerfahrung, spielen kann. Das Ergebnis ist: Es geht schon ziemlich gut, aber gegen einen Menschen, ist der Computer (ohne Heuristik) langsam und schlagbar.
Spielstärke
Die erste Version dieses Programms wertete nur die Güte der eigenen Stellung, unabhängig von der Stellung des Gegners. Die aktuelle Version benutzt die Bewertung der Stellung des Gegners mit je nach Angriffslust (=Strategie) unterschiedlichem Gewicht. Dadurch konnte die Spielstärke des Computers erheblich verbessert werden.
Nicht implementiert ist: Evtl. ist das Gewicht, das der gegnerischen Stellungsbewertung zu gemessen werden sollte, abhängig von der Spielphase und von der Spielstärke des Gegners.
Eine andere Möglichkeit, die Spielstärke zu verbessern, könnte darin liegen, nicht nur den besten Gegnerzug zu berücksichtigen, sondern die Verteilung der Bewertungen des Gegners mit einzubeziehen. Auch denkbar wäre ein Mechanismus, der für den gegnerischen Zug einen anderen Algorithmus verwendet als für den Computerzug.
Eine weitere Möglichkeit liegt darin, bestimmte Konstellationen (z.B. „Fallen“, die innerhalb der Vorausberechnungstiefe nicht erkannt werden können) mit bestimmten Bewertungen zu versehen. Vermutlich ist dies die am meisten Erfolg versprechende Methode, weil so systematische Schwächen verringert werden können. Allderdings werden so immer nur einzelne „Fallen“ dem Computer beigebracht. Außerdem erfordert das wie bei Heuristiken Spielerfahrung, weshalb ich in absehbarer Zeit nicht plane, solches zu implementieren.
Eine einfachere Möglichkeit, die Spielstärke zu verbessern, könnte darin liegen, nicht nur die Anzahl möglicher Viererreihen zu zählen, sondern auch zu berücksichtigen, aus wie vielen Steinen die Viererreihe schon besteht. Bisher wertet der Computer zwei mögliche Viererreihen, die bereits aus einem, zwei oder drei Steinen bestehen, gleich. Vermutlich wird dadurch das Spiel des Computers aggresiver, aber evtl. auch weniger strategisch, also kurzfristiger ausgerichtet, weil der Fertigbau von 3 Steinen in einer Reihe wichtiger wird –
evtl. wichtiger als der Bau neuer Möglichkeiten. – Ich kann kaum schätzen,
ob das Spiel dadurch besser wird oder nicht, es liegt vermutlich auch an der Gewichtung gegenüber mehr Möglichkeiten. Diese Verbesserungsmöglichkeit plane ich, in grundsätzlich absehbarer Zeit zu programmieren.
Quellcode
Den Java-Quellcode gibt es als ZIP-Datei hier.
Er kann beliebig verteilt, benutzt und verändert werden, solange mein Name mit
weitergegeben wird. Ich meinerseits benutze die modifizierte Klasse MassageBox
von Jack Harich, um Meldungen (z.B. Spieler mit der Farbe X hat gewonnen“)
auszugeben.
Die Hauptdatei heißt „kreise.java“, sie implementiert die grafische Benutzerschnittstelle. Die Datei „tspielfeld.java“ stellt grundlegende Funktionen des Viergewinntspielfeldes bereit, während die Datei „SchlauesSpielfeld.java“ um Stellungsbewertungsfunktionen einschließlich der Methode „hat Spieler gewonnen?“ erweitert, die Methode zur Ermittlung des besten Zuges hinzufügt und
die Schnittstelle für Threads implementiert, um gleichzeitige Vorausberechnungen zu
ermöglichen.
Hier habe ich eine kurze Anleitung geschrieben, wie man dieses kleine Viergewinnt-Spiel auf seine eigene Seite einbindet.
Ideen? Anregungen? Lobgesänge?
Einfach einen Kommentar hinterlassen.