Im Oktober letzten Jahres konnten wir die Sensation verkünden, dass Reto Aschwanden mit seinem Stelvio Prüfprogramm die Korrektheit der berühmten 57,5 zügigen Beweispartie von Dmitri W. Pronkin und Andriy Frolkin nachweisen konnte. Damit sollten deutlich kürzere Beweispartien doch immer und leicht prüfbar sein?

Dass dies ein Trugschluss wäre und warum das so ist, will ich heute mit einem Beispiel aus dem Urdrúckteil der Schwalbe vom August letzten Jahres diskutieren.

 
Die Aufgabe ist ziemlich kurz, die Autoren geben jedoch an, dass das Stück (nur) bis zum 13. Zug mit Stelvio geprüft ist, und auch Silvio Baier weist darauf hin, dass sich diese Beweispartie vollständiger Prüfung widersetze. Woran liegt das?

Ein „Brute Force“ Lösen ist bei nicht extrem kurzen Beweispartien ausgeschlossen: Im Schnitt gibt es in einer legalen Schachstellung etwa 30 Züge — damit etwa 30^32 16-zügige (32 Halbzüge!) Partien, das sind etwa 1,85 * 10^47 Partien. Könnte ein Computer in einer Sekunde eine Million Partien spielen, bräuchte er immer noch 1,85 * 10^41 Sekunden für alle. Ein Jahr hat im Schnitt etwa 31,6 Millionen Sekunden, wir brauchten also 5 * 10^33 Jahre für alle 16-zügigen Schachpartien. Und dann ist es auch egal, wenn davon vielleicht 90% bereits vorher wegen Matt beendet wären …

Daher suchen Prüfprogramme stets am Anfang nach möglichst umfangreichen Möglichkeiten, den „Spielbaum“ zu beschneiden, die durchschnittliche Zügezahl also so weit wie möglich zu reduzieren. So machen wir es hier auch meist, indem wir Überlegungen über die Stellung anstellen und daraus Schlussfolgerungen für den Lösungsablauf ziehen, bevor wir über konkrete Lösungszüge nachdenken.

Neben „impliziten“ Schlüssen (Schwarz hat 15 Steine, daher muss Weiß exakt einmal schlagen) sind das vor allen Dingen Feststellungen über Bauernstrukturen (… , dieser Schlag musste also mittels bxc3 erfolgen) und Abhängigkeiten von Zugreihenfolgen (g6 konnte erst nach Lh7 gespielt werden).

Continue reading →