Sieger-Prüfung "Vier gewinnt"

[negaH]

Es gäbe noch eine effizientere Lösung:

Delphi-Quellcode:

type
  TPlayer = -1..+1;

  PGamePos = ^TGamePos;
  TGamePos = packed record
    Stone: Integer;
    Link: array[0..7] of PGamePos;
  end;

function Move(X: Integer; Player: TPlayer): Boolean;
var
  Pos,Next: PGamePos;
  I,Count: Integer;
begin
  Pos := @Game[0, X];  // Y,X Koordinaten, Y = 0 = oberste Zeile im Game
  while (Pos.Stone = 0) and (Pos.Link[1] <> nil) and (Pos.Link[1].Stone = 0) do Pos := Pos.Link[1];
  Pos.Stone := Player;
  Count := 1;
  for I := 1 to 7 do
  begin
    Next := Pos.Link[I];
    if Next <> nil then
      if Next.Stone = -Player then 
      begin // A)
        Pos.Link[I] := nil;
        if Odd(I) then Next.Link[I -1] := nil
          else Next.Link[I +1] := nil;
      end else
        if Next.Stone = Player then
        begin
          if not Odd(I) then Count := 1;  
          repeat 
            Inc(Count);
            if Count >= StoneInRow then
            begin 
              Result := True;
              Exit;
            end;
            Next := Next.Link[I];
          until (Next = nil) or (Next.Stone <> Player);
        end;  
  end;
  Result := False;
end;

(* Link-Positionen sind nun:
x       x        x        
  6     1      3 

      7 0 2    
x 4   5 x 4    5 x
      3 1 6    
    
  2     0      7
x       x        x  

*)

Obige Methode hat mehrere Neuerungen:

1.) nachdem ein Spielerstein eingefügt wurde werden in allen Richtungen die Verlinkungen auf NIL gesetzt deren Game-Positionen durch Steine des Gegners belegt sind. Dies geschiet im Source bei A). Somit werden nach jedem setzen eines Steines immer mehr Zellen im Game immer weniger Verlinkungen zu ihren Nachbarzellen besitzen. Dies beschleunigt dann die Suche in diese Richtungen. Somit sucht obiger Algo. nur in Richtungen in denen entweder ein Stein des aktuelle Spielers sitzt oder aber noch kein Stein gesetzt wurde.

2.) die Richtungen = Linkpositionen wurden geändert so daß immer zu einer Geradzahligen Richtung die +1 Richtung die Gegenrichtung der Verlinkung darstellt.

Also TGamePos.Link[0] nach Oben, TGamePos.Link[1] nach Unten, TGamePos.Link[4] nach Rechts, TGamePos.Link[5] nach Links.

Somit ist:

P.Link[0].Link[0 +1] = P
P.Link[1].Link[1 -1] = P
P.Link[2].Link[2 +1] = P
P.Link[3].Link[3 -1] = P
P.Link[4].Link[4 +1] = P
P.Link[5].Link[5 -1] = P
P.Link[6].Link[6 +1] = P
P.Link[7].Link[7 -1] = P

3.) wir beginnen unsere Suche erst mit dem Link[1] nach Unten. Den Link[0] nach oben können wir komplett aussparen da ja dort alle LEER sein muß. Auch dies beschleunigt die Suche.

Gruß Hagen