Die allgemeine Vorsortierung der Züge gemäß Plausibilitätsgesichtspunkten erfolgt in Methoden generiereZuege (allgemeine Suche) bzw. generiereQSZuege (Ruhesuche). Grundsätzlich geht es hier natürlich ebenfalls darum, dafür zu sorgen, dass potenzielle Cutoff-Verursacher in der Liste ganz vorne stehen. Die Zugsortierung basiert vornehmlich auf statischen (i. S. v.: keine volle rekursive Suche involvierenden) Kriterien wie beispielsweise die Präferierung von Bauernumwandlungen, LVA-MVV (least valuable aggressor – most valuable victim, d. h.: Erfolg versprechende Schlagfälle werden bevorzugt) oder eine weiter verfeinerte Statische Evaluation von Abtauschsequenzen (SEE – in der jedoch selbst bereits wieder „gesucht“ wird).
Hauptanforderungen sind hier natürlich:
- Möglichst hohe Erfolgsquote – zu messen daran, wie die Cutoff-Züge gerankt werden bzw. (mittelbar) die Anzahl der im Rahmen der rekursiven Suche zu betrachtenden Knoten, wobei hier natürlich auch die Performanz der übrigen Heuristiken, Techniken & Strategien hineinspielt – Frage beispielsweise: Wie nahe sind wir am theoretischen Optimum der Minimalanzahl zu betrachtenden Knoten bei voller Suche mit Tiefe d?
- Effizienz des Sortierverfahrens: Sowohl die zur Anwendung gelangenden Kriterien (LVV-MVV, SEE etc.) als auch der Sortieralgorithmus selbst sollten möglichst effizient implementierbar sein, da es sich bei der Zuggenerierung um die zeitkritische Operation der rekursiven Suche schlechthin handelt; folglich erscheint es beispielsweise wenig ratsam, sich eines allgemeinen Sortierverfahrens mit Zeitkomplexität O(nlogn) zu bedienen – zumindest, insofern auch auf elementarerem Wege quasi-optimale Zugsortierungen erzielbar sind.
Unterscheidend zwischen Standardsuche und Ruhesuche (QS) implementiert Fischerle die Zugsortierung in einschlägigenn Methoden generiereZuege bzw. generiereQSZuege. Nachfolgend eine genauere Beschreibung der zugrunde gelegten Konzepte sowie der Implementierungstechnik. Soweit beurteilbar, ergibt diese Implementierung Ergebnisse, die bereits recht nahe am möglichen Optimum liegen.
Konzeptuelle Beschreibung
Im Rahmen der Non-QS-Suche verwendet Fischerle derzeit folgendes Verfahren. Angenommen, der König steht nicht im Schach – die Sortierreihenfolge ist:
1. Bauernumwandlungen: schlagende vor nicht schlagenden.
2. Als vorteilhaft eingestufte schlagende Bauernschlagzüge.
3. Als vorteilhaft eingestufte Leichtfigurenschlagzüge.
4. Als vorteilhaft eingestufte Turmschlagzüge.
5. Als vorteilhaft eingestufte Damenschlagzüge.
6. Königsschlagzüge (stets als vorteilhaft eingestuft, da Zielfeld nicht gegnerbeherrscht sein darf).
7. Alle EP-Schlagzüge von Bauern.
8. Alle als neutral eingestuften Schlagzüge (Reihenfolge entsprechend Anordnung der Schritte 2. bis 5.)
9. Rochaden.
10. Nicht schlagende Figurenzüge (ohne König und Bauern).
11. Doppelschritte von Bauern.
12. Einzelschritte von Bauern.
13. Nicht schlagende Königszüge.
14. Alle als nachteilig eingestuften Schlagzüge (Reihenfolge entsprechend Anordnung der Schritte 2. bis 5.).
Die hiermit verbundene Realisierung des LVA-MVV-Paradigmas ist augenfällig; eine verfeinerte statische Abtauschevaluation (SEE) findet hingegen derzeit nicht statt.
Wir wollen nun wie in der Literatur vorgeschlagen verfahren und die Priorisierung gemäß vorstehender Reihenfolge in möglichst geeigneter Weise mit den in den vorangegangenen drei Abschnitten beschriebenen Priorisierungen verzahnen. In diesem Zusammenhang sehen wir die in den Schritte 1 bis einschließlich 8 (neutral eingestufte Schlagzüge) als zu präferieren an und stellen der rekursiven Suche den entsprechenden Zugindex als zusätzliche Information zur Verfügung. Die rekursive Suche betrachtet nun die Züge in folgender Reihenfolge:
1. Zug gemäß Transpositionstafel-Heuristik (falls existent).
2. Zug gemäß Killerzug-Heuristik (falls existent).
3. Gemäß Zugsortierung zu präferierende Züge.
4. Züge gemäß History-Heuristik (falls existent).
5. Die übrigen Züge gemäß Zugsortierung.
Hierbei stellen geeignete Tests sicher, dass wir jeden Zug (maximal) ein Mal suchen.
Für den Fall, dass sich der König der am Zuge befindlichen Partie im Schach befindet, werden alleine die das Schachgebot beseitigenden Züge betrachtet – obige Präferierungsreihenfolge kommt dann sinngemäß für das reduzierte Inventar an Zugkandidaten zum Einsatz.
Im Rahmen der Zuggenerierung für die QS vereinfacht sich die Kategorisierung – in Stichpunkten:
- als nachteilig können Züge alleine im Rahmen der Beseitigung eines Schachgebots eingestuft;
- alle übrigen, also kein Schach beseitigenden Schlagzüge sind hier als vorteilhaft eingestuft, da die QS ja definitionsgemäß nur Erfolg versprechende Schlagoptionen verfolgt, insofern diese kein Schach beseitigen;
- eine Ausnahme bilden Bauernumwandlungszüge: hier unterscheiden wir zwischen vorteilhaften vs. neutralen Zügen – als neutral eingestuft werden diejenigen, bei denen die neu geborene Figur anscheinend einsteht.
Im Rahmen der QS-Suche werden hingegen keine zu präferierenden Züge unterschieden – genauso wenig, wie die obigen Transpositionstafel-, Killerzug- und History-Heuristiken hier Anwendung finden. Betreffend die Zugkandidaten-Priorisierung greift folglich alleine die vorstehend skizzierte rudimentäre Zugsortierung, wie sie in Methode generiereQSZuege realisiert wird.
Implementierungstechnik
Betreffend die technische Umsetzung des obigen Verfahrens gilt nun:
- Die Einstufung der Schlagzüge in eine der Kategorien „vorteilhaft“, „neutral“ und „negativ“ geschieht im Wesentlichen mit Blick auf zwei Kriterien: (a) Differenz des Materialwerts schlagende vs. geschlagene Figur; (b) sog. Feldbeherrschungsdifferenz schlagende Partei vs. geschlagen werdende, wobei sowohl die unmittelbaren als auch die verdeckten Feldeinwirkungen („RW“ – Röntgenwirkungen) berücksichtigt werden (abweichende Regelung für den König als Schlagfigur). Diese beiden Kriterien wurden so definiert, dass sie auf der Basis der zur Verfügung stehenden Brettrepräsentation effizient operationalisierbar sind.
- Die Diskriminierung zwischen umwandelnden und nicht umwandelnden Bauernzügen kann ebenfalls effizient bewerkstelligt werden.
- → hier nun zentral: Im Rahmen des Durchlaufs der obigen Schritte erfolgt nun die Sortierung der Zugkandidaten im Fluge, d. h. formal gesprochen auf der Grundlage eines Bucket-Sort-Verfahrens; eine explizite A-Posteriori-Sortierung mit einem Standardalgorithmus erübrigt sich hiermit – einzig notwendig ist die temporäre Zwischenspeicherung der als neutral bzw. nachteilig eingestuften Züge in eigenen Datenstrukturen („Buckets“) nebst anschließender Einreihung in die allgemeine Zugliste (Schritte 8 und 14).
Exemplarisch soll hier noch die Definition der Kriterien zur Kategorisierung der Schlagzüge von Türmen gegeben werden – diese Züge werden eingestuft als
- vorteilhaft g. d. w. (A) entweder keine gegnerischen Feldeinwirkungen bestehen, oder (C) eine Dame geschlagen wird oder (C) (ein Turm geschlagen wird und mehr eigene als gegnerische Feldeinwirkungen auf das Schlagfeld bestehen) oder aber (D) (mehr eigene als gegnerische Feldeinwirkungen bestehen und seitens des Gegners alleine der König auf das Feld einwirkt – der somit nicht zurückschlagen kann ).
- neutral g. d. w. nicht vorteilhaft und (A) ein Turm geschlagen wird oder (B) mindestens eine Leichtfigur geschlagen wird und mehr eigene als gegnerische Feldeinwirkungen auf das Schlagfeld bestehen);
- nachteilig g. d. w. weder vorteilhaft noch neutral.
Für die übrigen Figurentypen wurden ähnliche Einstufungskriterien operationalisiert, wobei nicht in jedem Falle alle Kategorien existieren – beispielsweise werden Bauernschlagzüge stets mindestens als neutral eingestuft, da die schlagende Figur nur einen geringen Wert hat und somit (lokal) keine dezidiert negative Materialdifferenz entstehen kann.