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!

Retro der Woche 47/2018

Im Retro der letzten Woche habe ich hier den 2. Preis der klassischen Retros im Schwalbe 2008 Informalturnier vorgestellt, nun möchte ich euch den 2. Preis der „Beweispartien“-Abteilung aus dem Preisbericht von Nicolas Dupont zeigen.

Dieser Jahrgang war für mich ein ganz besonderer, da ich mit dem Juniheft 2008 die Sachbearbeitung der Schwalbe-Retros übernommen hatte, nachdem Günter Lauinger diese Abteilung über 31 Jahre -– er übernahm sie von bernd ellinghoven mit dem Februarheft 1977 –- so unnachahmlich geleitet hatte.

Dies erklärt natürlich auch den sehr hohen Anteil an Widmungsaufgaben für Günter im Jahr 2008.

Gianni Donati & Olli Heimo
Die Schwalbe 2008, 2. Preis, Günter Lauinger gewidmet
Beweispartie in 19 Zügen (15+12)

 

Wie üblich beginnen wir mit dem Zählen der sichtbaren Züge und einer Analyse der Schlagbilanz.

Bei Weiß sind wir mit dem Zählen recht schnell fertig: 2+1+0+0+0+2=5 sichtbare Züge – das ist nicht viel! Bei Schwarz ist es ein wenig ergiebiger: 1+0+3+3+1+5=13, aber auch das lässt noch komplette sechs Züge frei. Das ist vielleicht auch der Grund, weshalb diese relativ kurze Beweispartie ohne ein „C+“ z.B. in der PDB zu finden ist.

Aber vielleicht hilft uns ja die Analyse der Schlagfälle weiter?

Weiterlesen

Euclide 1.00

Am 18. Februar hatte ich hier über die Fehler in Euclide 0.99 berichtet, die Bernd Gräfrath und Silvio Baier entdeckt hatten.

Heute hat nun Étienne Dupuis die Version 1.00 von Euclide freigegeben, die diese Probleme behebt. Ihr könnt die neue Version von Euclide’s Homepage herunterladen.

Übrigens lässt sich die Frage, was den eigentlich „Co+“ bedeutet, nicht nur auf mögliche Fehler bei Euclide reduzieren: So ist die neueste Popeye-Version im Wesentlichen ein Bugfix-Release — aber noch spannender finde ich die Frage der Interpretation von Märchenschach-Bedingungen, speziell deren Verknüpfung. Und hier interpretieren die drei „Marktführer“ (in alphabetischer Reihenfolge) Alybadix, Popeye und WinChloe Bedingungen häufig unterschiedlich und kommen damit zu unterschiedlichen Prüfergebnissen (was für den einen korrekt ist, ist für den anderen vielleicht unlösbar oder nebenlösig).

Eigentlich reicht also eine Angabe „Co+“ nicht aus; sie benötigt die Zusatzinformation, mit welchem Programm in welcher Version getestet wurde, um aussagekräftig zu sein.