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 liegt kann 5 Werte annehmen zwischen (einschließlich) der "fast nur eigenen 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 nocheinmal (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.
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.
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.
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"
stellt grundlegende Funktionen des Viergewinntspielfeldes bereit, während die
Datei "SchlauesSpielfeld" tspielfeld
um Stellungsbewertungsfunktionen einschließlich der Methode "hat Spieler
gewonnen?" erweitert, die Methode zur Ermittlung des besten Zuges hinzufügt und
die Schnittstelle Threads implementiert, um gleichzeitige Vorausberechnungen zu
ermöglichen.
Die Datei "kreise.html" ist ein Beispiel, wie das
Applet in eine Homepage eingebunden werden kann. Wenn jemand das tut, freue ich
mich, wenn er mir eine Mail schreibt.