Hi,

Es geht mal wieder um mein Schachprogramm

Wer sich tiefer für den grundlegenden Algorithmus interessiert, für den bietet Wikipedia etwas.

Kurzform: Die Alpha-Beta-Suche arbeitet mit einer Toleranzschwelle(alpha, beta) für beide Seiten. Außerhalb des gebildeten Fensters können Zugvarianten effektiv aussortiert werden.

Das aß-Fenster muss dazu möglichst schnell kleiner werden, daher werden Züge mit großem Schadenspotential zuerst betrachtet("..schlägt Dame" vor "..schlägt Bauer").

Das gleiche gilt für die schlagende Figur, da die geschlagene im Normalfall gedeckt sein sollte("Dame schlägt.." vor "Bauer schlägt..").

Nun habe ch mir in Bezug auf den Sortieralgorithmus folgendes gedacht: Diesen halte ich doch für sehr zeitraubend und würde ihn gerne weglassen, indem ich die Züge in getrennte Listen(Array[Tiefe, Koenig..LeerTyp{geschlagene Fig}, Koenig..Bauer{schlagende Fig}] of Array of TZug) eintrage, womit sie bereits sortiert wären.

Und hier ist der Punkt erreicht, an dem ich mich mangels Wissen auf dem Laufzeitbereich verschiedener Ansätze für kein Konzept entscheiden kann:

Entweder ich mache es wie o.e., oder:
Damit keine Zeit zum reservieren von Speicher verlorengeht, wären diese Arrays sowieso Fix. Somit könnte ich mir auch gleich verschiedene Einsprungpunkte speichern und ein Riesenarray of TZug machen.

Vorteilhaft daran wäre, dass dann nicht jeder einzelne Zugstapel überlaufen könnte, sondern nur quasi der letzte Stapel, die andern laufen in einen anderen Stapel über und überschreiben dort andere Züge(beim Zugstapelüberlauf steigt MiniMAX, z.B., mit halt; aus. Somit wäre das Überschreiben anderer Züge sicherlich vorzuziehen).

Auch stellt sich mir die Frage, ob ich dann nicht lieber ein dynamisches Array verwende und es bei Überlauf vergrößere. Ist das langsamer(ich gehe mal davon aus...)?

mfG,

Normalerweise würde ich die Züge ausführen, die Stellung bewerten, den Zug wieder zurücknehmen und anschließend nach der Bewertungs sortieren. Das ist zwar scheinbar langsam, aber das Du deinen Suchbaum exponentiell (also von X^N auf Log(...) reduzierst).

Hi,

Das ist der klassische MiniMAX-Algorithmus(mit dem Unterschied, dass die Sortierung nach der Bewertung eigentlich überflüssig ist, da nimmt man einfach den besten).

Alpha-Beta ist eine Optimierung des MiniMAX. Er basiert auf folgendem Prinzip: Angenommen, du hast mehrere Taschen, die Gegenstände unterschiedlichen Wertes enthalten. Du wählst die Tasche, dein Gegner allerdings wählt aus dieser Tasche den Gegenstand, den du bekommst.

Nun könntest du für jeden Gegenstand in jeder Tasche den Wert bestimmen und jeweils der Tasche den geringsten Wert in ihr zuordnen. Wenn du allerdings den Wert der ersten Tasche auf 5 bestimmt hast und nun in der zweiten Tasche einen Gegenstand des Wertes 3 findest, kannst du hier schon abbrechen: Egal, was du noch findest, sie ist auf jeden Fall schlechter als die erste.

Wie aus dem Beispiel hervorgeht, bearbeitet MiniMAX überflüssige Situationen. Alpha und Beta sind die schlechtesten Werte, die für beide Spieler erreichbar sind; außerhalb des Alpha-Beta-Fensters kann die Bewertung abgebrochen werden.

Um nun möglichst viele Cutoffs zu erzielen, muss das Fenster möglichst schnell verkleinert werden. Dazu werden(vor der Bewertung) vielversprechende Schlagzüge nach oben sortiert.

Und genau darum geht es: Ich will keinen Sortieralgorithmus über die Zugliste laufen lassen. Ist es nun günstiger, ein Riesenarray of TZug mit Einsprungspunkten für die verschiedenen "Vielversprechend-Züge" zu definieren, oder sollte ich lieber ein verschachteltes Array[Tiefe, GeschlageneFig, SchlagendeFig] of Array of TZug nehmen?

Der Zugriff würde wie folgt erfolgen:


Edit: Tiefe * PlatzproTiefe würde ich natürlich in einer Variable abspeichern, das wäre jedes Mal gleich.

Mich interessiert jetzt nur, was schneller ist.

mfG,

Hidden hat folgendes geschrieben:

Das ist der klassische MiniMAX-Algorithmus(mit dem Unterschied, dass die Sortierung nach der Bewertung eigentlich überflüssig ist, da nimmt man einfach den besten).

Wenn das so einfach wäre, bräuchtest Du kein Minimax /A-B-Pruning. Du hast eine (mehr oder minder) generische Stellungsfunktion, nach der Du die Züge vorsortierst. Dann ist die Wahrscheinlichkeit größer, das Du dein Fenster verkleinern kannst. Übrigens ist es dem MiniMax-Algorithmus egal, in welcher Reihenfolge die Zugkandidaten ausgeführt werden, dem A/B aber nicht. Der heißt nicht umsonst 'Alpha-Beta-Pruning', wobei 'to prune' das Ausdünnen von Baumkronen bezeichnet.[/quote]
Deine Sortierung nach Schlagmöglichkeit mag schneller sein, aber erstens schlägt man beim Schach nicht nur, und zweitens ist ein schlagender Zug nicht immer die richtige Wahl. Die Stellungsfunktion, wenn sie denn gut ist, bewertet sowohl die Anzahl der Spielsteine (und damit indirekt die Schlagzüge), als auch andere Kriterien, wie Stellung, Deckung etc., wird also den Suchbaum effektiver beschneiden, braucht dafür pro Zug etwas mehr Zeit.

Ich würde mal stark annehmen, das die allgemeinere Variante (über die Stellungsfunktion) schneller ist, weil sie den Suchbaum effektiver beschränkt. Sie ist in der Ausführung pro Zugtiefe natürlich langsamer, dafür eben effektiver in der Beschneidung. Wenn deine Engine ('KI') aber vorzugsweise Steine schlägt, dann wird dein Verfahren natürlich schneller sein.

Letztendlich musst Du beide Varianten implementieren und gegeneinander spielen lassen.

Hi,

Eine Bewertung mit reduzierter Suchtiefe und nachfolgender Neusuche ist eine gute Idee(wird ja beim Nullmove-Prunning schon so gemacht.

Nur wäre es auch dort ja wieder zeitsparend, wenn bei der reduzierten Suchtiefe die Züge vorsortiert wären. Letztendlich kommst du also immer bei Tiefe 1 an, was ja im Prinzip meinem Konzept entspricht: Sortierung nach Wert der geschlagenen Figur ist Bewertung bei Tiefe 1 .

Nun könnte man einfach die Sortierung ab Tiefe 3 oder so weglassen, gerade dort befinden sich ja aber viele Knoten .

Angenommen ich schalte dein Prinzip vor. irgendwann lande ich bei Tiefe 1 und muss nach meinem bisherigen Konzept arbeiten: Auf Tiefe 1 muss ich die Züge nichtmehr sortieren, wenn ich direkt in getrennte Listen eintrage.

Da die Listen, damit ich keinen Speicher reservieren muss, statisch sind, kann ich auch gleich eine lange Liste nehmen. Mit verschiedenen Einsprungspunkten(ab Index 50 Königszüge...) kommt es aufs selbe heraus. Welche Variante braucht denn nun mehr Zeit, viele Listen oder lange Liste?

mfG,

*push*

Mein letzter Post ist wohl nicht angekommen. Schade.

Die Vorbewertung zum Sortieren wird *ohne* Zugtiefe gemacht. Es soll ja nur die Wahrscheinlichkeit, das A/B greift, erhöht werden. Daher würde ich das einfach so implementieren. Es reicht ja schon für's Erste, wenn die Stellungsfunktion nur die Spielsteine zählt und die Differenz (klar 1=Bauer, 3=Läufer, 5=Turm usw) liefert, dann hast du genau deine Sortierung nach Schlagen. Später verfeinerst Du die Funktion dann noch, weil man beim Schach ja nicht nur schlägt.

Du machst also sowas:



edit: Deine Bedenken bezüglich des Sortierens kannst du durch Einsatz von RadixSort eliminieren, denn Du weisst genau, das der Sortierschlüssel z.B. im Bereich -32767 .. 32767 ist. Damit ist RadixSort mit O(n) möglich. Du kannst das natürlich noch weiter optimieren, in dem Du schon während der Generierung der Zugliste die Züge bewertest und über eine Skiplist einfügst, wobei ich glaube, das Radixsort schneller ist.

Ob man ohne Sortierung auskommt, weiss ich nicht. Ich hab mich vor einiger Zeit mal über Wiki in eine ziemlich gute Website gehangelt. Da hat ein Schachprogrammierer seine Tricks verraten... Wenn ich nur wüsste, wo das ist.

Die Killer-Heuristik wäre auch noch was en.wikipedia.org/wiki/Killer_heuristic

Hi,

Edit habe ich mal dick gedruckt

Erstmal: Mir ist vor kurzem klargeworden, dass Laufzeit von Zugsortierung und -erzeugung von niedrieger Priorität sind, da bekanntlich der Großteil der Knoten Blätter sind. In Blättern wird nur bewertet, in allen anderen Knoten Züge erzeugt.

Somit wird der Bewertungsmechanismus 50^Tiefe mal aufgerufen, der Zugerzeugungsmechanismus nur 50^Tiefe-1 + 50^Tiefe-2 + ... + 50² + 50 Mal, was näherungsweise 1/50 Mal so oft wie der Bewertungsmechanismus ist(50 ist eigentlich jeweils durch die mögliche Anzahl an Zügen in der jeweiligen Stellung zu ersetzen). Somit liegt dort mehr Optimierungspotential.

Z.B. hatte ich mir extra eine Schöne Zugkarte(Array[A1..H8, Richtungen]) überlegt, mit deren Hilfe sich das Erzeugen der Züge auf die neu entstandenen Zugmöglichkeiten beschränkt. MiniMAX z.B. erzeugt immer alle Möglichkeiten neu, was ich für sehr ineffektiv hielt. Da dies allerdings überraschend selten aufgerufen wird(immer in aß, wenn tiefe > 0; trotzdem nur 1/50 Mal so oft wie die Bewertungsfunktion), steckt man den für diese Tabelle nötigen Speicher wohl doch besser in Hashsize(drei Tage darüber nachgedacht und dann so was -.-)

Nach kurzer Suche zum von dir angesprochenen Verfahren ist mir in einem Thema dazu dieses Zitat von dir ins Auge gefallen, meintest du Counting Sort?

www.delphi-forum.de/...;highlight=radixsort

Zitat:

Ist der Wertebereich bekannt, geht es auch mit 'Counting Sort', das gänzlich ohne Vergleiche auskommt, und im Einzelfall noch schneller sein dürfte. Leider ist der Speicherbedarf proportional zum Wertebereich. Wenn also ein Array mit Zahlen zwischen -maxint und maxint zu sortieren ist, benötigt aber ein Array mit 'nur' 2^23 Elementen.

mfG,

Counting Sort geht auch, würde aber hier vermutlich nicht gut genug sein. Schau doch mal in der Literatur (a.k.a. Internet) was so zum Sortieren benutzt wird. würde mich mal interessieren.

Im Übrigen ist deine Überlegung total falsch (Sortieren ist zweitrangig). Wenn Du durch das Sortieren doch deine Blattanzahl eindampfen kannst (um EXPONENTEN!!! nicht um ein paar Prozent), dann würde ich mir das mal reinziehen. Letztendlich ist das aber alles 'learning by doing', weil man 1000x darüber diskutieren kann, aber letztendlich nur die praktische Anwendung zeigt, was nun besser ist.

[OT] ich habe z.B. ein Stringmatching-Verfahren, das die Anzahl der Vergleiche ggü. dem besten Suchverfahren mal eben HALBIERT! Nur ist es unter dem Strich bei mir (und fpr meinen Einsatzbereich) echt langsamer, weil der Overheader größer ist. Probieren geht über Studieren[/OT]

alzaimar hat folgendes geschrieben:

Im Übrigen ist deine Überlegung total falsch (Sortieren ist zweitrangig). Wenn Du durch das Sortieren doch deine Blattanzahl eindampfen kannst (um EXPONENTEN!!! nicht um ein paar Prozent), dann würde ich mir das mal reinziehen.

Ups da fehlte wohl ein Satzteil
Eigentlich sollte es heißen die Laufzeit dieser Prozesse ist zweitrangig.