Zugsortierung

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:

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:

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:

Exemplarisch soll hier noch die Definition der Kriterien zur Kategorisierung der Schlagzüge von Türmen gegeben werden – diese Züge werden eingestuft als

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.