[Delphi] hulp bij bouwen/doorlopen van een tree

[wizl]

Ik ben bezig een spelletje in Delphi uit te werken. Het spel heet Kat & Muis en wordt gespeeld op een dambord. Op het bord staan 4 zwarte stenen (de katten), en 1 witte steen (de muis). De muis moet naar de overkant zien door te breken. Als de muis wordt ingesloten door de katten heeft de muis verloren!

Om de computer (de katten) een zet te kunnen laten bepalen wil ik steeds alle mogelijke zetten doorlopen in een tree. De lange paden zijn gunstig voor de kat, de korte paden zijn gunstig voor de muis. (althans dat heb ik bedacht)

Ik heb de volgende recursieve functie in elkaar gedraaid die de tree zou moeten opbouwen. De inbounds functie kan bepalen of een volgende zet een geldige positie oplevert. Waar ik nu tegen aanloop is dat de recursieve functie maar blijft lopen als ik hem niet 'begrens' met een level. Ik denk dat dat komt omdat op een gegeven moment de muis geen zetten meer kan doen, maar de kat daarna weer een zet doet zodat de muis weer een vrije mogelijkheid heeft en zo tot in lengte van dagen (of in ieder geval tot de stack overflow ). Daarbij heb ik dadelijk wel een boompje, maar wat moet ik doen om de boom weer van te kunnen doorlopen? Daar heb ik nu volgens mij geen voorzieningen voor!

Op een bord van 8x8 heb ik 32 zwarte vakjes. Dat zijn de enige vakjes waar stenen op kunnen staan.
Welk vakje bezet is door welke steen houd ik bij in Board: Array of TSteen ;

Delphi:

type
  TSteen = (sGeen, sKat, sMuis );

  TGameBoard = class
  private
    NowPlaying: TSteen; // de soort speler (kat of muis) dat aan de beurt is
    Size: Integer; // de grootte van het bord
    MoveCount: integer;
    Moves: array[0..64] of record
      FromCol : integer;
      FromRow : integer;
      ToCol   : integer;
      ToRow   : integer;
    end;
  public
    Board: Array of TSteen ;
    function ToPos(Col, Row: Integer ): Integer ; // functie die de column en rij van een vak omrekent naar het vaknummer
    procedure SetupNewBoard ;
    procedure Write( Col, Row: Integer; Steen: TSteen);
    function Read( Col, Row: Integer ): TSteen;
    procedure DoMove( ColFrom, RowFrom, ColTo, RowTo: Integer );
    procedure _DoMove( PosFrom, PosTo: Integer );
    procedure UndoMove;
    function CheckMove( ColFrom, RowFrom, ColTo, RowTo: Integer ): Boolean;
    function LegalMoves(ACol, ARow: integer): Boolean;
    function Inbounds(ACol, ARow: integer): Boolean;
    constructor Create;
  end;

   TNode = class
     Board: TGameBoard;
     Level: integer;
     LastMove: TPoint;
     procedure Assign(Node: TNode);
  end;

function TfMain.Search(Node: TNode): integer;
var
  Foo: TNode;
  Value, Temp: integer;
  i, j: integer;
begin
  if Node.Level mod 2 = 1 then begin
    Node.Board.NowPlaying := sKat;
  end else begin
    Node.Board.NowPlaying := sMuis;
  end;
  for i := 0 to Pred(Node.Board.Size) do
    for j := 0 to Pred(Node.Board.Size) do
      if Odd(i+j) and (Node.Board.Board[Node.Board.ToPos(i, j)] = Node.Board.NowPlaying) then
        Node.Board.LegalMoves(i, j); // genereer een lijst van legal moves voor deze steen

  if Node.Board.MoveCount > 0 then begin
    for i := 0 to Node.Board.MoveCount do begin
        Foo := TNode.Create; // een nieuwe child creeren
        Foo.Assign(Node);
        Inc(Foo.Level);
        Foo.Board.DoMove(Node.Board.Moves[i].FromCol, Node.Board.Moves[i].FromRow, Node.Board.Moves[i].ToCol, Node.Board.Moves[i].ToRow);  // de move uitvoeren op de nieuwe node

        Foo.LastMove.x := Node.Board.Moves[i].FromCol;
        Foo.LastMove.y := Node.Board.Moves[i].FromRow;
        // anders stapt ie heen en weer
       if (Node.LastMove.x <> Node.Board.Moves[i].ToCol) and (Node.LastMove.y <> Node.Board.Moves[i].ToRow) and (Node.Level < 20) then
          Search(Foo);
    end;
end;

[ Voor 7% gewijzigd door wizl op 03-04-2005 19:34 ]

[Creepy]

Klinkt alsof je een minimax / alfabeta algoritme wilt gaan implementeren?

Daarnaast kan je tijdens het genereren van de zetten controleren of er een eindstand
(muist aan de overkant of ingesloten) is bereikt en op dat moment stoppen met het doorlopen.

[wizl]

Creepy schreef op zondag 03 april 2005 @ 19:07:
Klinkt alsof je een minimax / alfabeta algoritme wilt gaan implementeren?

Daarnaast kan je tijdens het genereren van de zetten controleren of er een eindstand
(muist aan de overkant of ingesloten) is bereikt en op dat moment stoppen met het doorlopen.

Precies, al de pagina's die er over gaan hebben het over dat minimax / alfabeta. Maar daarvoor moet ik dus een soort score bijhouden om te bepalen welke volgende zet de beste is. Wat niet duidelijk wordt uit de voorbeelden die ik heb gevonden aan de hand waarvan ik die score moet bepalen. Ik dacht dus, laat ik de levels maar gaan tellen Mijn probleem is dat ik niet helemaal begrijp hoe ik mijn boom moet opbouwen, zodat ik de boom later ook nog kan doorlopen om evt. nog een score te bepalen . . .

[Creepy]

De levels is alleen om je algoritme qua tijd te kunnen beperken en eventueel een "moeilijkheidsgraad" (hoeveel zetten "denkt" de CPU vooruit).

De score's gebruik je om te kijken welk pad je in de boom gaat nemen. Op het moment dat je een zet doet en in je boom zet kan je ook meteen de score van het bord op dat moment bepalen. De score werkt overigens twee kanten op. een negatief getal wil zeggen dat de ene speler er beter voor staat, en een positief getal wil zeggen dat de andere speler er beter voor staat. -MAX en +MAX zijn ook meteen de scores die je geeft als er een eindsituatie bereikt is.

Hoe je de score bepaalt is helemaal afhankelijk van het type spel

Hou vervolgens in je recursieve functie de hoogste score bij, en de eerste zet die daar bij hoort. Dan weet je welke zet je moet gaan doen aan het einde van je functie.

Ik zie overigens dat je aan de hand van je level bepaalt wie er aan de beurt is. Als je dit als parameter meegeeft aan je functie kan je de CPU ook als muis laten spelen.

[ Voor 10% gewijzigd door Creepy op 03-04-2005 23:08 ]

[wizl]

Thanx, ga ik daar vanavond eens mee aan de slag