Hi Luckie,
mir fallen zwei Lösungen ein die wesentlich performanter als dein Ansatz sein müssen.
1.) wärend des Eintragens eines Zuges eines Spielers, musst du ja in die richtige Spalte/Zeile einen Spielerstein ins Game eintragen. Exakt in diesem Moment, also BEIM Eintragen eines Steines ins Brett (egal ob Spielerzug oder ein Machineller Zug) überprüfst du ob dieser Zug zum 4 gewinnt führt. Dies hat nun mehrere Vorteile:
a.) man überprüft nur EINE Farbe=Spieler, statt beide Spieler
b.) man überprüft ausgehend von der aktuell gesetzten Spieleposition nur 3 Richtungen a 4 Steine, du zählst von der aktuellen Position jeweils in alle Richtung die gleichfarbigen Steine zusammen. Sollte in einer der drei Richtungen >= 4 herauskommen so hat der Zug gewonnen. Die Überprüfungsschritte werden dadurch ganz stark eingeschränkt und durch zusätzliche Informationen = aktuelle Veränderunge am Brett, der Suchraum verkleinert.
2.) Das Brett als solches ist immer gleich. Somit lohnt es sich Konvertierungs-matrixen im Speicher einmalig zu berechen. In diesem Array[] atehen alle Reihen mit mehr als 3 Koordinaten in das Brett. Über diese Martix kann man dann direkt alle Gamepositionen abfragen, in EINER Loop.
Zb. eine Verlinkte Liste aller Positionen auf dem Brett, pro Position jeweils ein Zeiger auf Rechts/Unten/RechtsUnten Position. Nun wird eine Liste aller Anfangsknoten zentral verwaltet. Entstehen wird ein Baum den man nur noch durchgehen muß. Bei dieser Iteration hüpft man von Node zu Node und zählt einen Counter so lange hoch wie es KEINEN Farbwechsel gibt. So bald ein anderer Stein in der Node=Game vorkommt wird dieser Counter=1 gesetzt.
Ich habe hier mal aus meiner 4-Gewinnt Komponente den Zug-Setzen-Algo. rauskopiert:
Delphi-Quellcode:
procedure TGame.SetCell(X,Y: Integer; Value: Integer);
var
I,SX,EX,SY,EY: Integer;
Tick: cardinal;
Wins: Boolean;
begin
Assert((Value >= gsOne)
and (Value <= gsTwo));
if Value <> FGrid[X, Y]
then
begin
FGrid[X, Y] := Value;
if Value <> gsEmpty
then
begin
Inc(FMoves);
if goMoveAnimation
in FOptions
then
for I := FHeight -1
downto Y +1
do
begin
SetControlColor(FShape[X, I], FColor[Value]);
Tick := GetTickCount + Cardinal(I) * 10;
while GetTickCount < Tick
do Idle;
SetControlColor(FShape[X, I], FColor[gsEmpty]);
end;
SetControlColor(FShape[X, Y], FColor[Value], FMoves);
if FMoves < FWidth * FHeight
then
begin
// @Luckie: hier wirds überprüft !!
// Grid isn't full
Wins := True;
// test horizontal
SX := X;
while (SX >= 0)
and (FGrid[SX, Y] = Value)
do Dec(SX);
EX := X;
while (EX < FWidth)
and (FGrid[EX, Y] = Value)
do Inc(EX);
Dec(EX, SX);
if EX <= FStonesInLine
then
begin
// test vertical
SY := Y;
while (SY >= 0)
and (FGrid[X, SY] = Value)
do Dec(SY);
EY := Y;
while (EY < FHeight)
and (FGrid[X, EY] = Value)
do Inc(EY);
Dec(EY, SY);
if EY <= FStonesInLine
then
begin
// test diagonal from bottomleft to topright
SX := X;
SY := Y;
while (SX >= 0)
and (SY >= 0)
and (FGrid[SX, SY] = Value)
do
begin
Dec(SX);
Dec(SY);
end;
EX := X;
EY := Y;
while (EX < FWidth)
and (EY < FHeight)
and (FGrid[EX, EY] = Value)
do
begin
Inc(EX);
Inc(EY);
end;
Dec(EX, SX);
if EX <= FStonesInLine
then
begin
// test diagonal
SX := X;
SY := Y;
while (SX >= 0)
and (SY < FHeight)
and (FGrid[SX, SY] = Value)
do
begin
Dec(SX);
Inc(SY);
end;
EX := X;
EY := Y;
while (EX < FWidth)
and (EY >= 0)
and (FGrid[EX, EY] = Value)
do
begin
Inc(EX);
Dec(EY);
end;
Dec(EX, SX);
Wins := EX > FStonesInLine;
end;
end;
end;
if Wins
then
if Value = gsOne
then FAction := gaPlayerOneWins
else FAction := gaPlayerTwoWins;
end else FAction := gaRemis;
// grid full must be a remis
end else
begin
Dec(FMoves);
SetControlColor(FShape[X, Y], FColor[gsEmpty]);
end;
end;
end;
Anbei mal mein angefangenes Projekt. Entpacke es, du installierst die Units NNet.pas und Fourwins.pas als Komponenten. In Fourwins.pas wird eine 4-Gewinnt Komponente installiert, mit Grafischer Komponente + MinMax Algo + Bedienung. Dies Komponente kann nun durch verschiedene Player-Klassen erweitert werden die verschiedene Zug-Such-Strategieen ermöglichen. In NNet.pas findest du ein Neuronales Netz mit dem ich versucht hatte nun einen 4-Gewinnt Neuonal Net Player zu bauen und zu trainieren. Mein Idee dabei war die Netze gegen Menschen, Computer-MinMax-Spieler und anderer NN-Player antreten zu lassen und zu trainieren. Rein theoretisch erhoffte ich mir dadurch ein Neuonales Netz zu trainiert zu bekommen das fast unschlagbar ist.
LEIDER!! bin ich nie so richtig fertig geworden mit dem Ding, und nach 1-2 Wochen Runspielerei verlor ich auch dann die Lust. Ich hoffe du kannst damit was anfangen. Bei Fragen bin ich ja auch noch da
Gruß Hagen