Dr. Roland Stuckardt

IT-Beratung - Sprachtechnologie - Medienanalyse

Transpositionstafel

Fischerle verwendet eine Standardtechnik zur Suchverkürzung, die von praktisch allen State-of-the-Art-Schachmotoren eingesetzt wird: Transpositionstafeln (auch: Hashtafeln oder kurz TransTa) zur Verfügbarhaltung bereits berechneter Suchergebnisse.

Konzeptuelle Beschreibung

Skizze der Grundidee: (Besonders) im Rahmen einer vollständigen Suche des Spielbaums wird ein und dieselbe Stellung qua Zugumstellung (daher die Bezeichnung Transposition) auf unterschiedliche Weise erreicht. Es bietet sich deshalb an, die Suchergebnisse insbesondere der häufiger in Erscheinung tretenden Positionen abzuspeichern; wird nun eine Stellung erneut erreicht, so kann unter bestimmten Voraussetzungen eine erneute Suche über den Stellungsknoten hinaus entfallen. Je höher ein bestimmter Stellungsknoten im Spielbaum lokalisiert ist, desto höher die potenzielle Ersparnis.

Unter bestimmten Voraussetzungen heißt hier folgendes: Ein in der Transpositionstafel für eine bestimmte Stellung gespeicherter Evaluationswert taugt nur dann als vollwertiger Ersatz für eine erneute Suche des entsprechenden Spielbaumknotens, wenn der Evaluationswert das Ergebnis einer Suche verkörpert,

  • die mindestens so tief erfolgte wie im aktuellen Verwendungskontext erforderlich;
  • die unter Maßgabe einer oberen Schranke beta erfolgte, die mindestens so groß ist wie diejenige im aktuellen Verwendungskontext vorliegende.

Sind diese Bedingungen erfüllt, so kann die Suche vorzeitig abgebrochen werden, da die in der Transpositionstafel gespeicherte Bewertung mindestens so genau ist, wie gefordert.