Prüfprogramme für Beweispartien haben besonders dann große Probleme, in überschaubarer Zeit ein Prüfergebnis zu liefern, wenn sowohl bei Weiß als auch bei Schwarz “freie”, also nicht aus dem Diagramm ableitbare Züge vorhanden sind: Beim “Brute Force” Rechnen, also der Berücksichtigung aller theoretisch möglichen Züge, führt dies schnell zu extremen Prüfzeiten, die etwa exponenziell mit der Anzahl der freien Züge wächst. Wie sagte mal ein Professor während meines Studiums? “Nichts wächst so schnell wie exponenziell.” (Schaut euch mal die Ackermannfunktion an, wenn ihr sehen wollt, wie schnell “exponenziell” wachsen kann!)

Kann man einem Prüfprogramm nun “menschliche Erkenntnisse” zum Beispiel zu Reihenfolgen von Zügen oder zur Mindest- und Höchstzahl von Zügen eines Steins mitteilen, so kann man damit die Prüfzeiten drastisch verkürzen — man muss sich dabei “nur” darüber im Klaren sein, dass dies keine vollständige Computerprüfung darstellt, denn wenn die Überlegungen zu möglichen Einschränkungen (englisch: “constraints”) des Suchbaums einen Denk- oder Notationsfehler enthalten, kann das Ergebnis unseres Rechenknechts (englisch: “computer”) natürlich nicht korrekt sein.

Natch und Euklide enthalten rudimentäre Möglichkeiten, solche “constrains” einzugeben und zu nutzen; diese wurden bei Jacobi noch erweitert. In dem interessanten Artikel “Solving program Jacobi equipped with constraints — a new tool to check proof games” haben nun Michel Caillaud, Nicolas Dupont und François Labelle anhand von jeweils drei orthodoxen und Märchen-Beweispartien die Möglichkeiten ausführlich dargestellt. Dieser lesenswerte Artikel kann auf Julias Fairy-Seite als pdf-Datei gelesen bzw. direkt heruntergeladen werden.

Sehr empfehlenswerte Lektüre!