Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Schleife vs. Rekursion: Geschwindigkeitsvorteil?
Hidden - Di 13.05.08 09:34
Titel: Schleife vs. Rekursion: Geschwindigkeitsvorteil?
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,
BenBE - 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 ...
Hidden - 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,
alzaimar - Mi 14.05.08 08:06
Nimmt sich (bei Quicksort) nicht viel.
Post #23:
http://www.delphipraxis.net/topic70640.html&postdays=0&postorder=asc&highlight=quicksort+iterativ&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.
Delete - 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 - 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...
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,
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 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!