Suchtechniken

Am Zug befindlich sucht Fischerle nach „plausibelsten“ Zug auf der Grundlage einer Negamax-Implementierung des Standard-Minimax-Algorithmus über dem Spielbaum, ergänzt um die Technik des Alpha-Beta-Backward-Pruning, womit die Suche von irrelevanten Teilen des Spielbaums vermieden wird. Die Spielbaumsuche erfolgt bis zu einer bestimmten (konfigurierbaren) Tiefe in voller Breite. In als „unruhig“ klassifizierten Stellungen wird selektiv tiefer gesucht – sog. Ruhesuche bzw. Quiescence Search (kurz: QS). Als „unruhig“ werden hierbei Stellungen angesehen, in der die am Zug befindliche Partei

  • im Schach steht,
  • eine vorteilhaft erscheinende Abtauschsequenz weiter verfolgen kann,
  • einen Bauern umwandeln kann.

Im Rahmen der QS werden dann ausschließlich die entsprechenden Züge weiter verfolgt, womit sich die Betrachtungen auf einen Spielbaum mit sehr begrenzter Breite fokussieren.

Während für die Standardsuche eine konfigurierbare maximale Rekursionstiefe vorgegeben ist, wird im Rahmen der QS (nahezu) beliebig tief rekurriert; da nur sehr wenige Varianten betrachtet werden, wurde für die QS von Fischerle bislang noch keine kritische Explosion der Rechenzeit beobachtet.

Die Suchtiefe wird ferner modifiziert durch einige Suchverfeinerungen:

  • Transpositiontafeln,
  • Selektive Suche.

Speziell die Selektive Suche weist auf den ersten Blick bestimmte Ähnlichkeiten mit der hier skizzierten Ruhesuche auf, darf jedoch nicht mit dieser verwechselt werden.

Neben den bereits genannten grundlegenden Suchtechniken und -verfeinerungen kommen zusätzlich eine Reihe weiterer State-of-the-Art-Techniken zum Einsatz:

  • Killerzugheuristik,
  • Transpositionstafel-Heuristik,
  • History-Heuristik,
  • Iterative Vertiefung,
  • Aspirationsfenster-Suche,
  • Hauptvarianten- bzw. Minimalfenstersuche (PVS, MVS).

Sämtliche vorstehend genannten Suchtechniken werden in der gesonderten Detailbeschreibung ausführlich beschrieben.

Schreibe einen Kommentar