Entwickler-Ecke :: Thema anzeigen - Minimax Algorithmus Speicherproblem

Akyben - Mo 30.11.09 14:52
Titel: Minimax Algorithmus Speicherproblem

Hallo Delphi Gemeinde,

ich habe ein Problem mit meinen Minimax Algorithmus. Beim erstellen der Zugmoeglichkeiten werden bei einer Suchtiefe von 9 500 MB Arbeitsspeicher belegt. Ich habe noch nicht soviel Ahnung von dynamischer Programmierung und habe es erstmal so geloest. Ich denke das der Fehler bei der Zuglistengenerierung liegt "New(Eintrag); und Eintrag^ := Copy(spielbrett);". Da ich ja nur den die Liste freigebe, aber nicht die Adressen der Eintraege.

Die Hauptfunktion von meines Minimax Algorithmus

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:

function TForm1.GetMinMaxZug(Spielbrett: TSpielbrett; Farbe : integer): Grundspielbrett;
var Zugliste: TList;
    Knoten: ^Grundspielbrett;
    Knotennr: integer;
begin
  Zugliste := Zuglisten_generator(spielbrett.spielbrett,spielbrett.Breite,spielbrett.Hoehe,Farbe);
  if Zugliste.Count = 0 then  //keine Zuege moeglich
    begin
      result := Spielbrett.spielbrett;
    end;
  Knotennr := Max_Zug(spielbrett.spielbrett,spielbrett.Breite,
              spielbrett.Hoehe,Farbe,0,Standard_Suchtiefe);
  if Knotennr in [0..Zugliste.Count] then
    begin
      Knoten := Zugliste.Items[knotennr];
      result := Knoten^;
    end
  else
    begin
      result := Spielbrett.spielbrett;
    end;
  Zugliste.Free;
end;

Der Max Teil

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:

function TForm1.Max_Zug(Spielbrett: Grundspielbrett; Breite, Hoehe, Farbe, tiefe, suchtiefe: Integer): integer;
var beste_knotennr: integer;
    bester_wert: integer;
    wert: integer;
    I: integer;
    naechstes_Spielbrett: ^Grundspielbrett;
    Zugliste: TList;
    Eintrag: ^Grundspielbrett;
    Gegnerfarbe : integer;
begin
  if Siegbedingung(Spielbrett, Breite, Hoehe, Farbe) then
    begin
      result := -INFINITY;
      exit;
    end;
  if (tiefe = suchtiefe) then
    begin
      result := Eval_Spielbrett(Spielbrett,Farbe);
      exit;
    end
  else
    begin
      Gegnerfarbe := (SCHWARZ + WEISS) - Farbe;
      //Zugliste generieren
      Zugliste := TList.Create;
      for I := breite to (Hoehe * Breite - 1) - Breite do
        begin
          if spielbrett[i] = Farbe then
            begin
              if spielbrett[i + breite*Farbe] = LEER  then  //moglicher Zug
                begin
                  New(Eintrag);
                  Eintrag^ := Copy(spielbrett);
                  Eintrag^[i + (breite) * Farbe] := FARBE;
                  Eintrag^[i] := LEER;
                  Zugliste.Add(Eintrag);
                end;
              if spielbrett[i + (breite-1)*Farbe] = Gegnerfarbe then  //moglicher Zug
                begin
                  New(Eintrag);
                  Eintrag^ := Copy(spielbrett);
                  Eintrag^[i + (breite-1) * Farbe] := FARBE;
                  Eintrag^[i] := LEER;
                  Zugliste.Add(Eintrag);
                end;
              if spielbrett[i + (breite+1)*Farbe] = Gegnerfarbe then   //moglicher Zug
                begin
                  New(Eintrag);
                  Eintrag^ := Copy(spielbrett);
                  Eintrag^[i + (breite+1) * Farbe] := FARBE;
                  Eintrag^[i] := LEER;
                  Zugliste.Add(Eintrag);
                end;
            end;
        end;
      bester_wert := -INFINITY;
      beste_knotennr := 0;
      for I := 0 to Zugliste.Count - 1 do
        begin
          naechstes_Spielbrett := Zugliste.Items[i];
          wert := Min_Zug(naechstes_Spielbrett^,
                  Breite , Hoehe, -Farbe, tiefe+1, suchtiefe);
          if Wert > bester_Wert then
            begin
              bester_Wert := Wert;
              beste_knotennr:= i;
            end;
        end;
      Zugliste.Free;
      if tiefe = 0 then
        begin
          result := beste_Knotennr;
          exit;
        end
      else
        begin
          result := bester_Wert;
          exit;
        end;
    end;
end;

Der Min Teil

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:

function TForm1.Min_Zug(Spielbrett: Grundspielbrett; Breite, Hoehe, Farbe, tiefe, suchtiefe: Integer): integer;
var beste_knotennr: integer;
    bester_wert: integer;
    wert: integer;
    I: integer;
    naechstes_Spielbrett: ^Grundspielbrett;
    Zugliste: TList;
    Eintrag: ^Grundspielbrett;
    Gegnerfarbe : integer;
begin
  if Siegbedingung(Spielbrett, Breite, Hoehe, Farbe) then
    begin
      result := INFINITY;
      exit;
    end;
  if (tiefe = suchtiefe) then
    begin
      result := Eval_Spielbrett(Spielbrett,Farbe);
      exit;
    end
  else
    begin
      Gegnerfarbe := (SCHWARZ + WEISS) - Farbe;
      Zugliste := TList.Create;
      for I := breite to (Hoehe * Breite - 1) - Breite do
        begin
          if spielbrett[i] = Farbe then
            begin
              if spielbrett[i + breite*Farbe] = LEER  then
                begin
                  New(Eintrag);
                  Eintrag^ := Copy(spielbrett);
                  Eintrag^[i + (breite) * Farbe] := FARBE;
                  Eintrag^[i] := LEER;
                  Zugliste.Add(Eintrag);
                  //Dispose(Eintrag);
                end;
              if spielbrett[i + (breite-1)*Farbe] = Gegnerfarbe then
                begin
                  New(Eintrag);
                  Eintrag^ := Copy(spielbrett);
                  Eintrag^[i + (breite-1) * Farbe] := FARBE;
                  Eintrag^[i] := LEER;
                  Zugliste.Add(Eintrag);
                  //Dispose(Eintrag);
                end;
              if spielbrett[i + (breite+1)*Farbe] = Gegnerfarbe then

                begin
                  New(Eintrag);
                  Eintrag^ := Copy(spielbrett);
                  Eintrag^[i + (breite+1) * Farbe] := FARBE;
                  Eintrag^[i] := LEER;
                  Zugliste.Add(Eintrag);
                  //Dispose(Eintrag);
                end;
            end;
        end;
      bester_wert := INFINITY;
      beste_knotennr := 0;
      for I := 0 to Zugliste.Count - 1 do
        begin
          naechstes_Spielbrett := Zugliste.Items[i];
          wert := Max_Zug(naechstes_Spielbrett^,
                  Breite , Hoehe, -Farbe, tiefe+1, suchtiefe);
          if Wert < bester_Wert then
            begin
              bester_Wert := Wert;
              beste_knotennr:= i;
            end;
        end;
      Zugliste.Free;
      if tiefe = 0 then
        begin
          result := beste_Knotennr;
          exit;
        end
      else
        begin
          result := bester_Wert;
          exit;
        end;
    end;
end;

---Moderiert von Narses: Beiträge zusammengefasst---

So ich habe nun die Listen mit folgender Procedur freigegeben und mein programm hat nun nur noch 4mb.

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

Procedure TForm1.Zugliste_Freigeben(var Zugliste: TList);
var Eintrag: ^Grundspielbrett;
    i: integer;
begin
  for I := 0 to Zugliste.Count - 1 do
    begin
      Eintrag := Zugliste.Items[i];
      Dispose(Eintrag);
    end;
  Zugliste.Free;
end;

Falls jemanden eine irgendwie eine unsauere Programmierung auffallen sollte, dann kann koennt ihr noch antworten.

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!