Gomoku (5 Gewinnt) - Beta Version

[I-love-Delphi-4-ever]

<edit>

ACHTUNG: NEUE VERSION MIT STRATEGISCHER AUSRICHTUNG

</edit>

*******************************************

Da ich gerade Urlaub habe, habe ich gedacht
dass ich Just-4-Fun einfach mal ein Spiel mit
Delphi programmiere, einfach weil ich lust auf's
programmieren hatte.

So, dass Spiel ist Freeware, ich habe es einfach
mal in den Anhang gepackt, damit ihr es testen
könnt.

WICHTIGER HINWEIS: Das Spiel ist noch lange
nicht fertig!! Es kommt auf jeden Fall noch
eine strategische Komponente rein und noch ein
paar andere verbesserungen. Es ist zwar schon
"spielbar", aber die programmierung ist noch
lange nicht abgeschlossen.

MEINE BITTE: Falls ihr Fehler findet oder
euch verbesserungen einfallen, schreibt sie
hier rein, damit ich das Programm anpassen kann.
Bin für alles offen!

***********************************************
Beschreibung: Spiel
Versionsnummer: 1.1 (Beta) - Release: 20.04.06
Läuft unter Windoof und man braucht nix außer ne Maus
Größe: 622 KB
***********************************************

Screenshot:

http://free.pages.at/load2/sonstiges/screenshot.jpg

[igel457]

Nettes Spiel, ich verliere nur immer...
Kannst du nicht noch verschiedene KI-Stufen machen?

Aber weiter so...

[Sascha L]

Sieht schon gut aus.

Kann es sein, dass der PC immer auf gleiche Weise seine Steine verteilt, wenn man ihm nicht in die Quere kommt?

Wieso wird das Fenster maximiert?? Das sieht blöd aus, das der Bereich des Spiels wesentlich kleiner ist. Wenn man das fenster auf normale Größe bringt, dann kann man das Spiel nicht mehr spielen, weil man dein Fenster nicht Resizen kann

[I-love-Delphi-4-ever]

Zitat von Sascha L:

Sieht schon gut aus.

Kann es sein, dass der PC immer auf gleiche Weise seine Steine verteilt, wenn man ihm nicht in die Quere kommt?

Wieso wird das Fenster maximiert?? Das sieht blöd aus, das der Bereich des Spiels wesentlich kleiner ist. Wenn man das fenster auf normale Größe bringt, dann kann man das Spiel nicht mehr spielen, weil man dein Fenster nicht Resizen kann :(

Also dass der PC immer in der gleichen weise seine Steine setzt,
dass hast du gut beobachtet. Wie gesagt, es fehlt noch die strategische
Komponente... Auf eine zufallsgenerator habe ich bisher verzichtet,
da ich ja eine strategiekomponente geplant habe... sollte aber dennoch
zumindest den eröffnungszug mit zufallsgenerator setzen lassen...

Das mit dem maximiert-zustand werde ich gleich mal verbessern.

PS: Könntest du einen Screenshot posten, wie das Spiel bei dir aussieht, ich hab leider nur nen 768*1024-Röhrenmonitor und da passt alles... So kann ich mir ein besseres Bild davon machen wie das Spiel auf anderen Monitoren wirkt und entsprechend anpassen. Resize werde ich natürlich noch freigeben.

Danke im Voraus.

[alzaimar]

Nicht schlecht. (4x gewonnen, 2x gepennt = verloren). Spielt wirklich gut.

Falls Du das mit Backtracking machst, erlaube bitte eine höhere Suchtiefe. Falls Du bisher nur Heuristiken (Mustererkennung, offene 3er etc.) eingebaut hast, würde ich das mit einer Minimax-Strategie kombinieren (hechel), DAS Teil würde dann echt Spass machen.

Die Kommentare sind nett, aber wenn, dann musst Du erstens alle Rechtschreibfehler verbessern und zweitens viel mehr Sprüche implementieren, weil es sonst sehrt schnell langweilig wird.

Vorschläge: Speedgame: Pro Zug max 5 Sek. Wer nicht zieht, setzt eben aus!

[I-love-Delphi-4-ever]

Zitat von alzaimar:

Nicht schlecht. (4x gewonnen, 2x gepennt = verloren). Spielt wirklich gut. :thumb:

Falls Du das mit Backtracking machst, erlaube bitte eine höhere Suchtiefe. Falls Du bisher nur Heuristiken (Mustererkennung, offene 3er etc.) eingebaut hast, würde ich das mit einer Minimax-Strategie kombinieren (hechel), DAS Teil würde dann echt Spass machen.

Die Kommentare sind nett, aber wenn, dann musst Du erstens alle Rechtschreibfehler verbessern und zweitens viel mehr Sprüche implementieren, weil es sonst sehrt schnell langweilig wird.

Vorschläge: Speedgame: Pro Zug max 5 Sek. Wer nicht zieht, setzt eben aus!

Zuerst mal danke für's Testen!

Also, wie schon im eingangsposting gesagt, strategie ist noch in
entwicklung, die hochgeladene Version arbeitet noch nach
Mustererkennung, wobei darauf geachtet wird, dass jeder Zug
sinnvoll ist (züge werden nur gesetzt wenn eine 5er Reihe
daraus entstehen kann [zumindest *sollte* dass Programm so
arbeiten]).
Was ich geplant habe ist eine Mischung aus strategie und Mustererkennung. Zuerst wird das Programm
strategische züge setzen, sobald dann gute Muster erkennbar sind
(offene 3er etc.) wird auf die Mustererkennung umgeschaltet.
Ich vermute dass ist das gleiche was du mit Minimax-Strategie
gemeint hast;-)

Die Idee mit dem Speedgame find ich genial! Werde dass auf jeden
Fall in die nächste Version gleich mal einbauen.

Werde auch mehr Sprüche einbauen... Muss mal im Netz schauen,
da gibt es bestimmt irgendwo ne Datenbank für Sprüche, so dass
ich für jede Situation dann 10 Sprüche habe, die ich dann per
Zufallsgenerator einwerfen kann.

Rechtschreibfehler werd ich natürlich noch korregieren, danke
für den Hinweis:-)

[alzaimar]

Minimax ist nichts anderes als eine rekursive Suche nach dem besten Zug. Der Suchbaum wächst exponentiell mit jedem Halbzug, was natürlich etwas blöd ist. Hier greift dann noch das sog. 'Alpha-Beta-Pruning' (sollte im Wiki zu finden sein). Das schnippelt (engl: to prune: Baum beschneiden) nun den Suchbaum so, das anstatt der x^n Knoten (x=Mögliche Züge, n=Suchtiefe) nur noch log (x^n) übrig bleiben. Also kann man wesentlich tiefer blicken.
Die Minimax/Alpha-Beta-Strategie arbeitet besser, wenn die zu analysierenden Züge so sortiert werden, das vermutliche 'Killerzüge' zuerst ausgeführt werden. Denn dann ist die Wahrscheinlichkeit größer, die restlichen Züge nicht mehr auswerten zu müssen, da diese nie besser werden können. Sie zu implementieren, ist eine Sache von ca. 5 Zeilen, wenn man schon die rekursive Suche hat.

Um eine rekursive Suchstrategie zu implementieren, benötigst Du dann noch eine Stellungsfunktion. Dazu kann man z.B. die Anzahl der offenen 2er,3er oder sonstwelche Muster nehmen, und diese Anzahlen mit Konstanten multiplizieren, um so zu einer Zahl zu kommen, die umso höher ist, je besser die Stellung aus Sicht des Computers ist: Eine Stellung, in der der Mensch gut dasteht, ist hingegen <0.

F(Stellung) = C1*Anzahl(2er) + C2*Anzahl(3er) + C3*Anzahl(4er mit einem offenen Ende)....

Diese Konstanten zu finden ist das eigentlich Schwierige: Vielleicht ist die Multiplikation hier auch blöd, denn wer 2 offene 3er hat, ist nicht etwa doppelt so gut, sondern hat schlicht und ergreifend *gewonnen*.

Um den besten Zug zu finden, muss ich den nehmen,
der meine Stellung maximiert. (Suchtiefe = 0)
Oder den, auf den Du die schlechteste Antwort hast. (Suchtiefe = 1)
Oder den, auf den dein bester Zug mich wieder am Besten dastehen lässt. (Suchtiefe = 2)
....

Nur so, als Denkanstoß: Die Konstanten, mit denen Du deine Stellungseigenschaften multiplizierst, können als 'Genome' angesehen werden. Du kannst nun zwei Programmversionen gegeneinander spielen lassen, wobei eine Version eben zufällig andere Konstanten verwendet (Mutation). Der Gewinner überlebt ('Survival of the fittest') ist dann sozusagen der Vatta (oda die Mutta) für weitere Generationen, die eine andere Konstante verändern. So verbessert sich dein Programm.

Ja, ja, die 'Nullsummenspiele mit vollständiger Information', die sind schon was
[edit] Alpha-Beta-Strategie wieder aus dem Hirnbackup gezogen[/edit]

[xZise]

Geil ^^
1 : 1

Soll dass vier gewinnt ähneln? Wenn ja, wie wäre es, wenn die "Steine" nach unten fallen?
Oder noch ein extra Mode

Also ich kann sagen:

TOP ^^ Zwar das erste mal gelost, aber was solls

[I-love-Delphi-4-ever]

Zitat von alzaimar:

Minimax ist nichts anderes als eine rekursive Suche nach dem besten Zug. Der Suchbaum wächst exponentiell mit jedem Halbzug, was natürlich etwas blöd ist. Hier greift dann noch das sog. 'Alpha-Beta-Pruning' (sollte im Wiki zu finden sein). Das schnippelt (engl: to prune: Baum beschneiden) nun den Suchbaum so, das anstatt der x^n Knoten (x=Mögliche Züge, n=Suchtiefe) nur noch log (x^n) übrig bleiben. Also kann man wesentlich tiefer blicken.
Die Minimax/Alpha-Beta-Strategie arbeitet besser, wenn die zu analysierenden Züge so sortiert werden, das vermutliche 'Killerzüge' zuerst ausgeführt werden. Denn dann ist die Wahrscheinlichkeit größer, die restlichen Züge nicht mehr auswerten zu müssen, da diese nie besser werden können. Sie zu implementieren, ist eine Sache von ca. 5 Zeilen, wenn man schon die rekursive Suche hat.

Um eine rekursive Suchstrategie zu implementieren, benötigst Du dann noch eine Stellungsfunktion. Dazu kann man z.B. die Anzahl der offenen 2er,3er oder sonstwelche Muster nehmen, und diese Anzahlen mit Konstanten multiplizieren, um so zu einer Zahl zu kommen, die umso höher ist, je besser die Stellung aus Sicht des Computers ist: Eine Stellung, in der der Mensch gut dasteht, ist hingegen <0.

F(Stellung) = C1*Anzahl(2er) + C2*Anzahl(3er) + C3*Anzahl(4er mit einem offenen Ende)....

Diese Konstanten zu finden ist das eigentlich Schwierige: Vielleicht ist die Multiplikation hier auch blöd, denn wer 2 offene 3er hat, ist nicht etwa doppelt so gut, sondern hat schlicht und ergreifend *gewonnen*.

Um den besten Zug zu finden, muss ich den nehmen,
der meine Stellung maximiert. (Suchtiefe = 0)
Oder den, auf den Du die schlechteste Antwort hast. (Suchtiefe = 1)
Oder den, auf den dein bester Zug mich wieder am Besten dastehen lässt. (Suchtiefe = 2)
....

Nur so, als Denkanstoß: Die Konstanten, mit denen Du deine Stellungseigenschaften multiplizierst, können als 'Genome' angesehen werden. Du kannst nun zwei Programmversionen gegeneinander spielen lassen, wobei eine Version eben zufällig andere Konstanten verwendet (Mutation). Der Gewinner überlebt ('Survival of the fittest') ist dann sozusagen der Vatta (oda die Mutta) für weitere Generationen, die eine andere Konstante verändern. So verbessert sich dein Programm.

Ja, ja, die 'Nullsummenspiele mit vollständiger Information', die sind schon was :mrgreen:
[edit] Alpha-Beta-Strategie wieder aus dem Hirnbackup gezogen[/edit]

Der begriff der "Minimax"-Therorie ist mir neu, ich werde mich bei
nächster Gelegenheit in dieses Thema mal einlesen...

Ich glaube aber das Prinzip das du vorgeschlagen hast, ist das gleiche
an dem ich zur Zeit arbeite und das ich mit "Strategie" beschrieben
habe. Und zwar habe ich vor dass der Computer die "möglichen Züge"
speichert (anstatt sie auszuführen) und anschliessend die, deren
*gedachte* 5er-linie sich überschneidet mit einem höhren faktor
zu bewerten. Schon jetzt werden die Züge die weiter Innen liegen mit
einem Faktor aufgewertet (dadurch erreiche ich dass sich der Computer immer auf das Zentrum konzentriert da es hier mehr Möglichkeiten zu "Zwickmühlen" gibt -> die Linien überschneiden sich schon fast zwangsläufig). Diese zwei faktoren bestimmen dann welche
wertigkeit ein zug hat, der beste zug wird ausgeführt.
Dabei werden die Züge die zu einem offenen 3er oder einem offenen 4er oder gar zu einem 5er (direkter Gewinn) führen natürlich höher bewertet. Also im Prinzip das gleiche was du vorschlägst - oder?

[alzaimar]

Das Minimax-Verfahren findet rekursiv den Zug, der die gegnerischen Vorteile MINImiert und die eigenen Vorteile MAXimiert. Der Beste (MAX) eigene Zug ist dabei der, der den schwächsten (MIN) gegenerischen Zug zulässt.

Deine Zugbewertung ist eine 'Heuristik' ohne Rekursion, quasi eine Mustererkennung. Du versuchst, bestimmte Muster zu erzwingen (Zwickmühlen) und Linienüberkreuzungen: Eine sehr gute Idee, die Dein Spiel schon mal recht stark macht. Es könnte reichen, mit dieser Funktion eine MiniMax-Strategie aufzubauen:

Hier mal ein Pseudocode für eine einfache rekursive Suche mit Minimax (aus dem Gedächtnis)

Delphi-Quellcode:

Function FindeBestenZug (Level : Integer; Spieler, Gegner : TSpieler: Brett : TSpielfeld) : Integer;
Begin
  L := ErzeugeListeAllerZüge;
  MaxS := -999999;
  Foreach Z in L Do Begin
    MakeTheMove (Brett, Spieler, Gegner, Z);                                           // Zug ausführen
    If Level = MaxZugTiefe Then
      S := BewerteStellung (Brett, Spieler, Gegner)              // Je höher der Wert, desto besser ist
    Else                                                              // die Stellung für den 'Spieler'
      S := -FindeBestenZug (Level + 1, Gegner, Spieler, Brett);     // Und dann besten Gegnerzug finden
// Hier wird der beste Gegnerzug geliefert. Wir wollen aber den Zug, der S minimiert! Deshalb das MINUS
    UndoMove  (Brett, Spieler, Gegner, Z);                                     // Zug rückgängig machen
    If S > MaxS Then Begin                 // Ist der Zug besser als alle bisherigen in diesem Versuch?
      MaxS := S;                                                                             // Merken!
      MaxZ := Z;                                               // MaxZ in Stufe 0 ist der gesuchte Zug!
    End;
  End;
 Result := MaxS; 
End;

Wie Du siehst, wird bei Zugtiefe 0 genau der Zug ermittelt, bei dem die Stellung dann am Besten ist.
Bei Zugtiefe 1 wird für jeden der möglichen Züge die Anwort des Gegners ermittelt. Gewonnen hat der Zug, bei dem die Antwort des Gegners am Schlechtesten ist. Es ist interessant, das Verhalten bei verschiedenen Werten für 'MaxZugTiefe' zu analysieren. Das Problem, was Du haben wirst ist die Liste L der möglichen Züge. Denn es gibt anfangs ja 361 davon. Danach immer noch 324 etc. Das ist zu viel!

Des weiteren spielt der sog. Horizonteffekt eine entscheidende Rolle. Nehmen wir an, durch einen perfiden Zug wird der Computer in 6 Zügen gewinnen. Wenn die Suchtiefe auf 5 eingestellt ist, würde der Computer diesen Zug einfach übersehen, weil während der Analyse die Win-Situation unentdeckt bleibt. Deshalb ist eine gute Stellungsfunktion entscheidend, die auch strategische Muster (offene 4er, doppelte 3er, Zwickmühlen etc.) korrekt bewertet und strategische Vorteile besser darstellt. Dadurch wird der Horizonteffekt zwar nicht vollständig vermieden, hier jedoch mit Sicherheit fast bedeutungslos: Eine Stellung, die 'gleich' gewonnen wird, ist leicht zu erkennen.

Ich bin mir sicher, das Du bald ein Programm hast, an dem wir uns alle die Zähne ausbeißen werden.