Vier gewinnt

[fliegermichl]

Ich hatte in diesem Thread ein Vier Gewinnt Spiel vorgestellt.
Dort hatte jedes Spielfeld anhand der Gewinnmöglichkeiten an diesem Feld einen Wert zugewiesen bekommen.
Die Bewertungsfunktion für den MiniMax Algorithmus (Bewerten) hat einfach die Werte der Felder, die mit der jeweiligen Farbe besetzt waren, zusammen addiert.

Das hat schon einigermassen geklappt.
Allerdings wurde z.B. nicht berücksichtigt, dass wenn schon 3 Steine beieinander waren, ein vierter das Spiel entscheiden würde.

Bei der Suche nach einer besseren Bewertungsfunktion bin ich auf diese Seite gestoßen und habe da mal den C Quellcode nach Pascal übersetzt.
Er funktioniert auch sehr gut. Ich verstehe nur nicht wie?

Gemeint ist die Funktion scoreBoard, welche auch gleichzeitig ermittelt, ob ein Spieler gewonnen hat.

[Zvoni]

Ist das jetzt ein "klassisches" 4-Gewinnt, oder ein echtes Score 4?
"klassiches" 4 Gewinnt ist nämlich 2D, aber "Score 4" sehe ich immer nur als 3D.
Das 2D "4 Gewinnt" heisst nämlich "Connect 4".

Ich hab mal in den C-Code geschaut.
Find ich unnötig kompliziert, permanent den Score über das gesamte Brett zu berechnen.

Begründung:
Das Spielbrett hat eine finite Grösse (6 hoch, 7 breit), heisst: Es gibt auch eine finite Anzahl möglicher Gewinn-Kombinationen.
Hätte mir die möglichen Gewinn-"Koordinaten" als separate Struktur (Array, Liste, was auch immer) gespeichert, und jedes mal wenn ein neuer Stein gesetzt wird, einfach dort reingeschaut, statt jedesmal durch das ganze Brett zu laufen.

Im Prinzip sowas wie ein Reverse Lookup:
Für jedes Feld auf dem Brett hälst du eine Struktur vor, in WELCHEM es als Gewinn-Möglichkeit vorkommt, und dann rennst du auch nur durch diese Felder.

Beispiel
y=Höhe
x=Breite
[0,0] sei links unten

Das Feld [0,1] ist in 4 Gewinn-Möglichkeiten ein "Mitglied":
[0,0],[0,1],[0,2],[0,3] --> waagrecht, ab ganz links
[0,1],[0,2],[0,3],[0,4] --> waagrecht, ab 2. Spalte
[0,1],[1,1],[2,1],[3,1] --> senkrecht 2. Spalte
[0,1],[1,2],[2,3],[3,4] --> Diagonal nach rechts oben

Heisst: Fällt ein Stein auf [0,1], rennst du eben nicht durch alle Felder, sondern nur durch diese 16

würde übrigens das Spielfeld nicht als 2D-Array speichern sondern als 1D. Koordinaten-Berechnung ist dann einfach mit DIV bzw. MOD.
Beispiel:
Felder 0 bis 6 sind die unterste Reihe, 7 bis 13 die zweite usw.
In meinem Beispiel oben wäre das dann wie folgt:
Feld "0" ist das ganz links unten
Das Feld "1" (unterste Reihe, 2. von links) hätte als Gewinn-Möglichkeit dann
0,1,2,3 -- waagrecht
1,2,3,4 -- waagrecht
1,8,15,22 -- senkrecht
1,9,17,25 -- Diagonal links unten nach rechts oben

Das Feld "6" (ganz rechts unten) hat "nur" 3 Gewinnreihen:
3,4,5,6 --waagrecht
6,13,20,27 --senkrecht
6,12,18,24 -- Diagonal von Links oben nach rechts unten

Feld "3" (unterste Reihe Mitte) hat 7 GewinnReihen
0,1,2,3 --waagrecht
1,2,3,4 --waagrecht
2,3,4,5--waagrecht
3,4,5,6 --waagrecht
3,10,17,24 --senkrecht
3,9,15,21 -- Diagonal von Links oben nach rechts unten
3,11,19,27 -- Diagonal von Links unten nach rechts oben

Und in diesen "Gewinn-Strukturen" speicherst du eben nur die Indizes der Gewinn Felder.
Hätte wahrscheinlich nen Record mit dynamischem Array gemacht

Code: Alles auswählen

Type
  TFeld = Record
     FeldIndex:Integer;
     GewinnReihen: Array Of Array[0..3] Of Integer;
  End;
  
 Var SpielFeld:Array[0..41] Of TFeld;
 //Initialisiere alles ...blabla

Da die Gewinn-Reihen "statisch" sind, würde ich die in einer kleine Datenbank, INI-File, Datei, Socken-Schublade, was auch immer, permanent vorhalten

[fliegermichl]

Zunächst einmal vielen Dank für deine Ausführungen.
Mir geht es aber in erster Linie darum, zu verstehen, wie die Bewertungsfunktion scoreBoard zu ihren Ergebnissen kommt.
Sie berücksichtigt dabei nämlich auch "Angriffe" vom Gegner mit ziemlich wirksamer Abwehr.

[Zvoni]

Zunächst einmal vielen Dank für deine Ausführungen.
Mir geht es aber in erster Linie darum, zu verstehen, wie die Bewertungsfunktion scoreBoard zu ihren Ergebnissen kommt.
Sie berücksichtigt dabei nämlich auch "Angriffe" vom Gegner mit ziemlich wirksamer Abwehr.

Also wenn ich es richtig verstanden habe, speichert er die „Konter“ in counters, und nutzt diese für eine schnelle Entscheidung.
Nach dem Motto: Wenn gelb in der untersten Reihe in der Mitte ist, braucht er für Orange die unterste Reihe erst gar nicht zu prüfen, weil orange da nie gewinnen kann.

Mag mich aber auch irren. Bin aus dem Code auch nicht schlau geworden.
Außerdem gibts ne Funktion „inside“ die nie aufgerufen wird!?!??!

[corpsman]

Komisch,
wenn man das Spiel gewinnt, dann passiert nichts ...

Laut Source sollte da eine Meldung kommen.

Auch musste ich Ausdrücke wie

Code: Alles auswählen

 score -= scores[y][x - 3];                      

zu

Code: Alles auswählen

 score := score - scores[y][x - 3];       

umschreiben, du hast da wohl eine Einstellung Aktive die nicht by Default aktiv ist ..

by the way das repo ist witzig, ggf portiere ich das nach FPC und wir schaun mal wie wir mit FPC in seinen Benchmarks so abschneiden

[fliegermichl]

Komisch,
wenn man das Spiel gewinnt, dann passiert nichts ...

Laut Source sollte da eine Meldung kommen.

Doch, in dem Memo rechts erscheint dann, "Du hast gewonnen"

Auch musste ich Ausdrücke wie

Code: Alles auswählen

 score -= scores[y][x - 3];                      

zu

Code: Alles auswählen

 score := score - scores[y][x - 3];       

umschreiben, du hast da wohl eine Einstellung Aktive die nicht by Default aktiv ist ..

Ich habe unter Projekteinstellungen -> Compilereinstellungen -> Parsen -> Syntaxeinstellungen die Option "C-artige Operatoren" aktiv. Das ist aber per default eingestellt.

by the way das repo ist witzig, ggf portiere ich das nach FPC und wir schaun mal wie wir mit FPC in seinen Benchmarks so abschneiden

Ja, das könnte man mal machen.

[fliegermichl]

...
Außerdem gibts ne Funktion „inside“ die nie aufgerufen wird!?!??!

Die hatte ich aus dem C Code übernommen, wird aber hier nicht gebraucht, da man keinen Stein ausserhalb des Spieles einwerfen kann.

[corpsman]

Weil es nicht mehr wirklich zu diesem Thread gehört hab ich mal einen Follow up gestartet siehe hier