Autor Beitrag
Hidden
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 2242
Erhaltene Danke: 55

Win10
VS Code, Delphi 2010 Prof.
BeitragVerfasst: Di 13.05.08 09:34 
Hi,

Bei meinem Schachprogramm stehe ich vor der Wahl: Schleifen oder Rekursion. Mit gotos wären nämlich auch Schleifen denkbar. Arbeitet ein Analysealgorithmus schneller mit Schleifen oder rekursivem Aufruf?

mfG,

_________________
Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)
BenBE
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: Di 13.05.08 09:40 
Kommt darauf an, wie man die Schleife realisiert. Mit Schleifen und einer Sorted Queue kann man nämlich doppelte Analysen ausschließen und damit die durchzuführenden Prüfungen mitunter stark reduzieren ...

Rekursion hat zudem den Nachteil, mehr Arbeitsspeicher zu belegen, wo oftmals zu wenig eh schon da ist ...

_________________
Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
Hidden Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 2242
Erhaltene Danke: 55

Win10
VS Code, Delphi 2010 Prof.
BeitragVerfasst: Di 13.05.08 10:12 
Hi,

Doppelanalysen werden durch eine Hashtabelle sofort gekillt. Beim rekursiven Ansatz war die global.

Das häufigere Reservieren von Arbeitsspeicher(bei jeder Rekursion einmal für Alpha, Beta und die verbleibende Suchtiefe, wenn dir das sagt) war auch mein Knackpunkt.

Um wieviel wäre so eine Schleife denn erfahrungsgemäß schneller?

mfG,

_________________
Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)
alzaimar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: Mi 14.05.08 08:06 
Nimmt sich (bei Quicksort) nicht viel.
Post #23: www.delphipraxis.net...terativ&start=15

Ich würde erstmal die NegaMax und NegaScout-Algorithmen vergleichen, und dann das A/B-Pruning (Killerheuristik?), die Zugvorsortierung und die Stellungsbewertung optimieren, anschließend dynamische Vorschautiefen und Mustererkennung sowie eine Stellungsdatenbank implementieren.

Wenn das Programm dann zufriedenstellend spielt, kann man sich überlegen, ob man das nocht iterativ hinbekommt. Aber ob das dann wirklich merklich schneller wird, bezweifle ich.

_________________
Na denn, dann. Bis dann, denn.
j.klugmann
Ehemaliges Mitglied
Erhaltene Danke: 1



BeitragVerfasst: Mi 14.05.08 08:11 
Also mir wära es mit gotos viel zu unübersichtlich.

user profile iconBenBE
Zitat:
Kommt darauf an, wie man die Schleife realisiert. Mit Schleifen und einer Sorted Queue kann man nämlich doppelte Analysen ausschließen und damit die durchzuführenden Prüfungen mitunter stark reduzieren ...

Das kan ich auch so sagen.Kann man empfehlen.

Jetzt muss man Vortteile und Nachteile gegenrechnen.

MVRFUAG j.klugmann
Hidden Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 2242
Erhaltene Danke: 55

Win10
VS Code, Delphi 2010 Prof.
BeitragVerfasst: Mi 14.05.08 08:51 
Hi,

Danke für die Antworten :D

Ich habe nicht die NegaMAX, sondern die MiniMAX-Variante verwendet. Es lohnt sich nämlich, für Max und Min getrennte Hashtabellen zu nehmen. Und bei NegaMax jedes Mal drauf zu checken, ob es jetzt Min oder Max ist tut bei den vielen Aufrufen doch nochmal ein bisschen weh...

ausblenden volle Höhe Hier mein PseudoCode, erstmal noch ohne Hashtabellen:
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:
Maxi:  //Rekursion; Mini und Maxi werden abwechselnd aufgerufen
  ErzeugeZuege;
  Tiefe--;  //tiefer in den Suchbaum
  if Tiefe = 1 then begin
LastMaxi:  //letzter Durchlauf, da Tiefe 1 -> In den Blättern Laufzeit sparen!
    Fuere Zug aus;
    Wert := Alter Wert + Änderung(geschlagene Fig, ...);
    Mache Zug Rückgängig;
    if Wert > BesterWert[Tiefe]
      BesterWert[Tiefe] := Wert;
    Nächster Zug;
    if Letzter Zug
      Goto ContinueMini;  //Zurück zur alten Tiefe und dort den nächsten Zug
    Goto LastMaxi;  //Wenn nicht letzter Zug, nächsten Tiefe1-Zug betrachten
  end;
ContinueMaxi:
  Tiefe++;  //Zurück zur alten Tiefe
  Mache Zug Rückgängig;
  Nächster Zug;
  if Letzter Zug then begin
    BesterWert[Tiefe] := BesterWert[Pred(Tiefe)];  //Wert = bester FolgeZug
    if Tiefe = SollTiefe
      Exit;  //Fertig
    Goto ContinueMini;  //Zurück zur alten Tiefe und dort den nächsten Zug
  end;  //Wenn nicht letzter Zug, Rekursion -> Mini
Mini:
  ErzeugeZuege;
  Tiefe--;  //tiefer in den Suchbaum
  if Tiefe = 1 then begin
LastMini:  //letzter Durchlauf, da Tiefe 1 -> In den Blättern Laufzeit sparen!
    Fuere Zug aus;
    Wert := Alter Wert + Änderung(geschlagene Fig, ...);
    Mache Zug Rückgängig;
    if Wert < BesterWert[Tiefe]
      BesterWert[Tiefe] := Wert;  //Es soll ja minimiert werden..
    Nächster Zug;
    if Letzter Zug
      Goto ContinueMaxi;  //Zurück zur alten Tiefe und dort den nächsten Zug
    Goto LastMini;  //Wenn nicht letzter Zug, nächsten Tiefe1-Zug betrachten
  end;
ContinueMini:
  Tiefe++;  //Zurück zur alten Tiefe
  Mache Zug Rückgängig;
  Nächster Zug;
  if Letzter Zug then begin
    BesterWert[Tiefe] := BesterWert[Pred(Tiefe)];  //Wert = bester FolgeZug
    if Tiefe = SollTiefe
      Exit;  //Fertig
    Goto ContinueMaxi;  //Zurück zur alten Tiefe und dort den nächsten Zug
  end;
  Goto Maxi;  //Wenn nicht letzter Zug, Rekursion -> Maxi


Edit: Wie ihr vielleicht gemerkt habt, püfe ich auf Tiefe 1, nicht auf Tiefe 0. Dadurch spare ich mir in den Blättern diese Prüfung.

mfG,

_________________
Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)