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 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
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 := 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);
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);
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);
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
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);
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);
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);
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.
