Autor |
Beitrag |
Hidden
      
Beiträge: 2242
Erhaltene Danke: 55
Win10
VS Code, Delphi 2010 Prof.
|
Verfasst: 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
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: 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 
      
Beiträge: 2242
Erhaltene Danke: 55
Win10
VS Code, Delphi 2010 Prof.
|
Verfasst: 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
      
Beiträge: 2889
Erhaltene Danke: 13
W2000, XP
D6E, BDS2006A, DevExpress
|
Verfasst: 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
|
Verfasst: Mi 14.05.08 08:11
Also mir wära es mit gotos viel zu unübersichtlich.
BenBE 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 
      
Beiträge: 2242
Erhaltene Danke: 55
Win10
VS Code, Delphi 2010 Prof.
|
Verfasst: Mi 14.05.08 08:51
Hi,
Danke für die Antworten
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...
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: ErzeugeZuege; Tiefe--; if Tiefe = 1 then begin LastMaxi: 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; Goto LastMaxi; end; ContinueMaxi: Tiefe++; Mache Zug Rückgängig; Nächster Zug; if Letzter Zug then begin BesterWert[Tiefe] := BesterWert[Pred(Tiefe)]; if Tiefe = SollTiefe Exit; Goto ContinueMini; end; Mini: ErzeugeZuege; Tiefe--; if Tiefe = 1 then begin LastMini: 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 ContinueMaxi; Goto LastMini; end; ContinueMini: Tiefe++; Mache Zug Rückgängig; Nächster Zug; if Letzter Zug then begin BesterWert[Tiefe] := BesterWert[Pred(Tiefe)]; if Tiefe = SollTiefe Exit; Goto ContinueMaxi; end; Goto 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)
|
|
|