Dr. Roland Stuckardt

IT-Beratung - Sprachtechnologie - Medienanalyse

Stellungsrepräsentation

Die Stellungsrepräsentation von Fischerle basiert auf dem Rotated-Bitboard-Modell, wie es u. A. von Robert Hyatt beschrieben wird.

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.

Statische Stellungsbewertung

Die Spielbaumknoten, an denen die rekursive Suche stoppt ("Blätter"), werden einer ausführlichen Stellungsevaluation unterzogen. Die entsprechende Bewertungsfunktion legt hierbei sowohl materielle als auch zahlreiche positionelle Kriterien zugrunde. Zu den positionellen Kriterien zählen u. A. Kriterien betreffend

  • die Bauernstruktur (Freibauern, isolierte Bauern, rückständige Bauern),
  • die Vorrückungsweite der Bauern,
  • (partiephasenabhängig) die Königssicherheit,
  • Zentralisierung bzw. Wirkungsradius der Figuren,
  • Zusammenspiel der Figuren (z. B. Turmverdopplung).

Die Stellungsbewertungsfunktion verkörpert den Kern der schachlichen Intelligenz eines Schachmotors; sie ist insofen ein entscheidender Faktor sowohl der Spielstärke als auch des Spielcharakters eines Programms.

Den Ausgangspunkt für die Implementierung von Fischerles Bewertungsfunktion bildete u. A. die umfassende Dokumentation der Bewertungskriterien des sehr erfolgreichen Programms Chess 4.5 von Slate & Atkin aus den siebziger Jahren.

Eröffungsbibliothek

Fischerle verfügt über eine aus der umfangreichen, derzeit mehr als 3.1 Mio. Partien umfassenden ICOfY-PGN-Datenbank generierten Eröffungsbibliothek und deckt damit ab:

  • 221035 unterschiedliche Stellungen mit insgesamt
  • 538515 Zugoptionen