Constraints

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!

One thought on “Constraints

  1. Thanks so much for advising us, Thomas.
    I tried it on a recent proof game from Problemskak, where the editor had spent 10 days with Natch to reach C+; Jacobi with constraints used under 2 minutes. If others want to try, here is the input.
    stipulation dia 20.5
    forsyth r2q1bs1/p1ppp1pQ/2s4r/1p1S1p1p/P7/SbP4P/1PkPPPP1/R1B1K2R
    constraints Ke8-c2-d1-e1xf1-e1-d1-c2 Ke1-d1-c2-d3-g3-h2-g1-f1-e1

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.