n-Damen-Problem

Sicher kennt ihr alle diese schachmathematische Fragestellung: Auf wie viele Arten kann man n Damen auf einem nxn-Brett aufstellen, sodass sich keine Damen beobachten?

Besonders interessant ist für uns natürlich n=8, also das normale Schachbrett. Hier ist schon seit 1850 die Lösung 92 bekannt (siehe Bonsdorff, Fabel, Riihhimaa: Schach und Zahl, 3. Auflage 1978, S. 55). Diese 92 Stellungen lassen sich aus 12 “Stammlösungen” durch Drehung und Spiegelung erreichen. Wer einmal Programmieren gelernt hat, hat für diese Fragestellung sicher schon einmal ein Programm geschrieben; die Aufgabe ist das klassische Beispiel für “Backtracking Algorithmen”.

Der Rechenaufwand für größere n steigt sehr stark (etwas stärker als exponentiell, siehe [1]), und nun ist vor ein paar Tagen die Anzahl der Lösungen für n=27 veröffentlicht worden: Die Forschergruppe um Thomas Preußer von der TU Dresden fand die Zahl 234.907.967.154.122.528 (also 234,9 Billiarden) [2] mit 29.363.495.934.315.694 Stammlösungen [1].

Für n=26 existiert die Lösung bereits seit 2009, daran sieht man, wie “schwer” das Problem für wachsende n zu lösen ist. Nun bin ich mal gespannt, wann die Lösung für n=28 bekannt wird…

Zwei interessante Artikel aus dem Netz empfehle ich euch zur weiteren Lektüre:

[1] https://de.wikipedia.org/wiki/Damenproblem
[2] http://www.heise.de/newsticker/meldung/Zahlen-bitte-Das-27-Damen-Problem-ist-geloest-3332513.html

Fehler in Natch

Die neueste Version des Beweispartie-Prüfprogramms Natch (Version 3.0Beta1) enthält offensichtlich einen Fehler, der dafür sorgt, dass eventuell nicht alle Lösungen gefunden werden. Pascal Wassong, der Autor, ist dabei, ihn zu untersuchen und dann zu beheben.

Wenn eine fehlerbereinigte Version, die dann auch die längere Original-Beweispartie aus dem aktuellen Problemist lösen kann, erschienen ist, werde ich euch darüber informieren.

Natch Bugfix

Pascal Wassong hat eine fehlerbereinigte Version seines Beweispartie-Prüfprogramms Natch veröffentlicht, nun in der Version 3.0.beta1.

Die Installation ist ganz einfach: Nur die von der Natch-Seite heruntergeladene Zip-Datei (für Windows 64 oder Windows 32) in ein eigenes Verzeichnis entpacken — fertig! Dort findet ihr dann auch die Datei NEWS, die über die Änderungen informiert.

Euclide 1.1

Kaum hatte ich hier die neue Version von Natch angekündigt, gibt es auch vom “Konkurrenzprodukt” Euclide von Étienne Dupuis ein Update: In der Version 1.1 kann man Einschränkungen bezüglich der Lösung angeben, beispielsweise Euclide mitteilen, dass ein bestimmter Bauer auf einem bestimmten Feld in eine bestimmte Figur umgewandelt werden muss.

Mit diesen Möglichkeiten, die die Prüfdauer deutlich verkürzen können, muss man natürlich sehr vorsichtig umgehen, da man damit möglicherweise nicht nur viele Fehlversuche, sondern auch Nebenlösungen ausblenden kann. Sie hilft also besonders während des Kompositionsprozesses, ersetzt schlussendlich aber keine vollständige Prüfung. Auch wenn ihr das sonst nicht so mögt: Lest unbedingt vorher die Beschreibung dazu in der Hilfe-Datei durch!

Dennoch natürlich ein tolles Feature, das Euclide sicher noch attraktiver als bisher schon macht.

Natch und Teddy

Gerade sind zwei interessante, aber auch völlig verschiedene Schachprogramme sind in einer neuen Version erschienen:

Natch ist ein Prüfprogramm von Pascal Wassong für orthodoxe Beweispartien. Der Quelltext ist offen, sodass es z.B. für Linux einfach nutzbar ist; für (64bit) Windows liegt es als bereits übersetztes, sofort ausführbares Programm vor. Es läuft unter Windows im Command-Fenster; “natch -h” zeigt alle möglichen Parameter zur Steuerung des Programms an, ebenso gibt es natürlich Informationen auf der Natch Web-Site.
Die neue Version 3.0beta behebt einige Fehler aus 2.50beta und beschleunigt den Lösevorgang dadurch, dass bestimmte zeitliche Abhängigkeiten im Lösungsverlauf erkannt werden, wodurch der Suchbaum eingeschränkt wird. Auf alle Fälle ausprobieren!!

Teddy ist kein eigenes Löseprogramm, sondern eine graphische Oberfläche für Popeye, das Löseprogramm für orthodoxe und sehr viele Märchenaufgaben (Märchensteine, Märchenbedingungen). Auch dieses Programm, das von Bjørn Enemark stammt, ist frei verfügbar und ebenso wie Natch kostenlos nutzbar.
Bjørn verbessert und erweitert Teddy sehr häufig, sodass für Interessenten und Nutzer ein gelegentlicher Blick auf die Teddy Homepage lohnt. Auch Teddy kann ich euch persönlich, vor allen Dingen ab Version 1.3 (aktuell ist nun Version 1.5) nur empfehlen!

Pünktlich zu Andernach

Pünktlich zum Andernach-Treffen, das ja heute beginnt (auch Spontan-Gäste sind dort natürlich herzlich willkommen!), hat Thomas Maeder die neueste Version von Popeye V4.75 freigegeben und zum Download bereitgestellt.

Neben verschiedenen Fehlerkorrekturen werden nun Märchernsteine und eine Bedingung unterstützt, die, so viel darf ich schon verraten, beim diesjährigen Andernach-Kompositionsturnier eine Rolle spielen werden.

Viel los!

In der Partie-Schach-Welt ist im Moment eine Menge los: Wer sein Interesse am “Party-Schach” noch nicht vollkommen verloren hat, kann im Moment den Schluss der Frauenweltmeisterschaft zwischen Titelverteidigerin Hou Yifan und Herausforderin Maria Muzychuk verfolgen. Heute hat auch das Kandidatenturnier mit acht Teilnehmerner begonnen, die das Recht ausspielen, den Weltmeister Magnus Carlsen im November herausfordern zu dürfen. Bis zum 28. März werden 14 Runden gespielt.

Über beide Ereignisse berichtet im Internet z.B. Chessbase, über das Kandidatenturnier berichtet z.B. auch Spiegel Online ausführlich.

Und wer auch gelegentlich mal über den Tellerrand hinaus schaut, wer nicht nur gern Klötze schiebt, sondern auch mal Steine setzt, sprich: Sich auch ein wenig für Go interessiert, der verfolgt sicher auch die letzten drei Partien zwischen Lee Sedol, einem der besten Spieler der Welt, und dem Go-Programm AlphaGo, das im Google-Konzern entwickelt wurde. Nach zwei Partien steht es 2:0 — für AlphaGo! Damit könnte auch im Go passieren, war im Schach 1997 geschah, als DeepBlue gegen Garri Kasparow gewann.

Die nächsten drei Partien finden am 12., 13. und 15. März in Seoul statt, sie beginnen steht um 05:00 Uhr morgens unserer Zeit. Wer die Partien nachspielen oder live verfolgen will, findet einen sehr guten Einstieg über die Wikipedia-Seite zu AlphaGo.

Nachtrag 12.3.16:
Auch die dritte Partie hat AlphaGo gewonnen. auch wenn das Match nun entschieden ist, werden die folgenden beiden Partien noch gespielt.

ChessComposer nun kostenfrei

Vor etwa anderthalb Jahren hatte ich hier über Diyan Kostadinovs Andriod-App ChessComposer berichtet, mir dem man auf seinem Android Smartphone oder Tablet Probleme verwalten und auch prüfen kann — lokal oder über das Internet mit Popeye bzw. den Popeye-Server Ankona.

Nun ist die neue Version 5.1 von ChessComposer erschienen. Neben neuen Funktionen und Fehlerbehebungen hat sich das Vertriebsmodell geändert: Die Unterscheidung in kostenfrei “light” Version und kostenpflichtige Vollversion ist entfallen; die Vollversion wird nun kostenfrei zur Verfügung gestellt. Ihr könnt sie auf Diyans KobulChess Seite herunterladen.

Wenn das kein doppelter Grund ist, das Programm auszuprobieren …