Home > Logik, Schach > Dame ausanalysiert

Dame ausanalysiert

Sowohl bei Spiegel Online als auch in der Telepolis habe ich heute gelesen, dass das Damespiel ausanalysiert wurde. Die Lösungsstrategie ist interessant:

Stattdessen wählten die Informatiker einen gemischten Ansatz: Sie ließen ihre Computer alle möglichen Spielstellungen mit zehn oder weniger Steinen auf dem Brett analysieren – immerhin mehr als 39 Billionen Optionen. Dann identifizierten sie 19 relevante Spieleröffnungen, die sie so weit durchspielen ließen, bis nur noch zehn oder weniger Steine auf dem Spielbrett waren. Daraus entwickelten die Forscher eine allgemeine Dame-Strategie, mit der sich immer eine Konstellation erreichen lässt, die zu einem Patt führt – und machten ihre Software „Chinook“ unschlagbar.

Mit anderen Worten: Die Software zerlegt die Damepartie in drei Abschnitte: Eröffnung, Mittelspiel und Endspiel. Alle Endspielstellungen, in denen nur noch wenige Steine auf dem Brett sind, wurden vollständig in einer Datenbank erfasst. In der Eröffnung wurden alle guten Möglichkeiten herausgefunden. Das erinnert an Schach, wo die Eröffnungsbibliotheken der Programme mit den Partien der Großmeister gefüttert werden. Zwischen den beiden Partiephasen Eröffnung und Endspiel konnte eine endliche Anzahl von Strategien ermittelt und durchgerechnet werden, die den Übergang von einer ausgeglichenen Eröffnungsstellung in ein Remisendspiel erlauben.

Ob dieser Ansatz theoretisch korrekt ist, kann vermutlich (wie beim Vierfarbenproblem) auch nur mit Rechnerhilfe entschieden werden, denn für ein vollständiges Durchrechnen aller möglichen Stellungen reicht die Rechenkapazität noch (?) nicht aus. Dieser Ansatz macht Mut für weit schwierigere Probleme: Schach und – in einer heute noch sehr weit entfernten Zukunft wegen der noch größeren Komplexität – Go.

Bereits 1993 wurde ein weniger komplexes Brettspiel mit Computerhilfe geknackt: Mühle. Ich habe Mühle in den 90er Jahren häufiger gespielt. Als Aktiver macht nämlich das Schachspielen gegen Laien keinen Spaß, diese verlieren immer und man selbst versaut sich durch das ständige Gewinnen die eigene Spielstärke. Also habe ich auf gemeinsamen Reisen mit Bekannten immer ein Mühlespiel eingesteckt. Allerdings konnte ich auch dabei meinen Ehrgeiz nicht so richtig bremsen. Ich habe den Mühlegroßmeister Manfred Nüscheler angeschrieben, weil sein Buch „So gewinnt man Mühle“ nicht im Buchhandel zu bekommen war. Er hat mir auch sofort geantwortet und mir eins von den Exemplaren verkauft, die er noch zu Hause hatte.

Am schwierigsten bei diesem Kauf war die Überweisung von knapp 10 DM in die Schweiz. Ahnungslos war ich in die Sparkasse gegangen und wollte ihm so das Geld senden. Als die Dame am Schalter ein zwei DIN A4 großes Formular hervor kramte, wurde ich misstrauisch: „Wie hoch ist denn die Überweisungsgebühr?“, fragte ich sie. „50 Mark“, war ihre Antwort. Da habe ich dann doch lieber einen Zehnmarkschein in etwas Silberpapier gewickelt und in einem Brief in die Schweiz geschickt.

Das Buch war sehr nützlich und hat mir sogar einige Siege gegen Programme im Internet eingebracht. Es ist nämlich keinesfalls so, dass man durch bloßes Gieren nach schnellen Mühlen und Steinen des Gegners am leichtesten gewinnt, im Gegenteil! Aber das Ende vom Lied war, dass nach Schach auch niemand mehr Mühle mit mir spielen wollte. Nur Mensch-Ärger-Dich-Nicht geht noch immer.

Theoretisch ist Mühle übrigens genauso Remis, wie es jetzt für Dame bewiesen wurde.

Kommentare

Matthias Gerhards 07/20/2007 09:26:20 PM

Bei Mühle wundert mich das nicht. Nach einigen Spielen bemerkt man schnell, dass es eine sehr begrenzte Anzahl von Strategien gibt und eigentlich der Anziehende immer gewinnt, wenn er keinen Fehler macht. Dame ist schon viel komplizierter. Aber den Ergeiz kann ich gut verstehen. Ich spiele eigentlich nicht, weil ich immer einen so schrecklichen Ergeiz entwickle und dann völlig spaßfrei werde.

Köppnick 07/20/2007 10:36:05 PM

Mit dem Anzugsvorteil bist du im Irrtum. Nüscheler schreibt in seinem Buch:

Beim Schachspiel beweisen Statistiken, dass Weiß als Anziehender einen Vorteil hat und mehr Partien gewinnt. Solche vergleiche fehlen beim Mühlespiel.

Nach unseren Erfahrungen sind die Chancen eher umgekehrt. Schwarz kann den letzten Stein setzen und hat dadurch den Vorteil, als letzter eine Mühle bilden zu können.

Wie sieht es bei gleich starken Gegnern aus? Auch hier lehrt die Erfahrung, dass Schwarz im Vorteil ist. Weiß hat zwar den ersten Zug und ist beim Setzen immer einen Stein voraus, doch für Schwarz ist es der größere Vorteil, den letzten Stein setzen zu können.

Im Buch werden auch Stellungen analysiert, bei denen es von Nachteil ist, wenn man dem Gegner einen Stein wegnehmen kann und dann einen Stein mehr besitzt. Das kann dadurch zum Verlust führen, dass der Gegner springen kann und das Gegennehmen des nächsten Steines so planen kann, dass nacheinander zwei Steine und dadurch die Partie verloren gehen. Das ist der Grund dafür, dass viele Stellungen Remis enden – weil Gewinnversuche zum Verlust führen würden.

Interessant ist auch, dass das „perfekte Programm“, also die Mühledatenbank, Turniere mit menschlicher Beteiligung häufig nicht gewinnt. Weil es „weiß“, dass viele Stellungen Remis sind, spielt es in dieser Situation irgendeinen Remiszug – es kann nicht einschätzen, welche Stellungen für Menschen leicht und welche schwer zu spielen sind. Großmeister hingegen suchen in diesen objektiv Remisstellungen Züge heraus, bei denen es ihren Gegnern schwer fällt, die besten Züge zu finden und gewinnen auf diese Weise. Gegen das Programm hingegen halten sie leicht Remis. Am Ende haben sie mehr Siege in petto als die optimal spielende Datenbank.

Matthias Gerhards 07/21/2007 07:01:18 AM

Da fehlt mir offensichtliche die Erfahung. Aber mein letztes Mühlspiel ist auch ca. 20 Jahre her.

Köppnick 07/20/2007 10:52:17 PM

Bei Chessbase, der Hamburger Computerschachfirma wird die Meldung über das Damespiel auch in einer Kurzmeldung kommentiert:

Damespiel gelöst
Vier gewinnt hat es schon erwischt, Mühle auch und jetzt ist Dame dran. Ein Team von Computerexperten unter Leitung von Jonathan Schaeffer gelang es, mit „Chinook“ ein unschlagbares Dameprogramm zu entwickeln. Zwar wurde Chinook bereits 1994 Dameweltmeister, aber dieser Sieg blieb immer mit einem Makel behaftet, da Chinooks menschlicher Gegner, Marion Tinsley, den Wettkampf wegen seines schweren Krebsleidens abbrechen musste, und manch einer behauptete, der Computer hätte den Wettkampf sonst nicht gewonnen.

Dann folgen einige Links:
Zum Artikel bei Wissenschaft.de
Christian Hesse: Schach ist vollkommener als das Leben
Perfection in Checkers (engl.)
Zur Chinook-Webseite (Chinook ist der Name des perfekten Dameprogramms)

steppenhund 09/15/2007 10:08:51 AM

Dass Dame auf untentschieden zu halten ist, habe ich immer vermutet. Du hast sicher recht, wenn Du meinst, dass der endgültige Beweis nur über einen Computerbeweis zu erbringen ist. Das halte ich aber in diesem Fall nicht für einen Nachteil.
Die Unterteilung in die Spielphasen halte ich für vollkommen in Ordnung. Es gibt auf alle Fälle zwei Phasen (ohne Dame auf dem Spielfeld, mit Dame auf dem Spielfeld) Da es bei optimaler Verteidigung nicht zu einer Dame kommt, bevor nicht einige Steine geschlagen worden sind, ist auch das Kriterium „Anzahl Steine“ für die Phasentrennung zulässig.
Die Frage, die sich mir stellt, ist eigentlich die:
Dame, Bauer – Dame: wieviel Stellungen könnten zu Unentschieden führen – wenn überhaupt?
Als Spiel mit Zugzwang ist Dame bereits ziemlich deterministisch. Der einzige Freiheitsgrad ist die Sprunglänge der Dame und die Auswahl, was geschlagen werden muss, wenn es mehrere Möglichkeiten gibt.

Dass Schach und Go nicht wirklich Remis-deterministisch sein können, läßt bei Go durch das Komi belegen.
Da dieses bei Meisterturnieren mit 4,5 oder 5,5 Punkten festgelegt ist, kann es unmöglich zu einer Remiswertung kommen.
Ich bin mir allerdings nicht sicher, ob die koreanische Ko-Wertung da nicht vielleicht doch Möglichkeiten vorsieht. Aber ich selbst hatte noch nie in irgendeiner Partie ein Triple-Ko im Endspiel.
Bei Schach hast Du ja selbst den Hinweis gegeben.

Zum Schachspielen gegen schwächere Partner:
Ich hege eine gewisse Verachtung für schwache Spieler, die nicht spielen wollen, weil sie immer verlieren. Dieser Menschentyp ist nämlich der, welcher sich auch keine Steine vorgeben lassen will.
Damit wird aber jegliche Möglichkeit unterbunden, an Spielstärke dazu zu gewinnen.
Ich selbst habe Schach bei meinem Vater gelernt:
Endspiel König Turm
König Dame
leichte Umwandlungen Bauer
Partie – Damenvorgabe
(bis ich ein oder zwei gewinnen konnte)
Partie – Turmvorgabe
usw.
Läufer, Springer

Als ich zehn Jahre alt war, spielte ein Tiroler Schachmeister mit mir – Vorgabe Dame, Turm. Es machte ihm Spass zu sehen, wie ich mich abmühte. Er hat mich gelobt, obwohl ich immer verloren hatte.
Vor einigen Jahren habe ich noch manchmal im Kaffeehaus um Mitternacht mit ein paar Wiener Schachgranden gesessen.
Meistens war niemand mehr ganz nüchtern. Aber gegen einen 2450-Elo konnte ich bei einer Vorgabe von 2-5 (er 2 Minuten, ich 5 Minuten) durchaus 60% der Partien gewinnen. Ohne Zeitvorgabe wäre ich chancenlos.

Und mit Vorgabe kann es dann schon wieder ganz schön viel Spass machen.

Köppnick 09/16/2007 05:37:07 PM

Ich glaube, ich hatte dir schon mal „vorgerechnet“, dass du bei derart guten Ergebnissen im Schach ohne jedes Training mit ein bisschen davon ziemlich schnell selbst auf IM-Niveau spielen könntest. 2min-5min zu bestehen gegen eine 2450 spricht für eine 2200 ohne jede Vorbereitung. Die IMs beschäftigen sich jeden Tag mit Schach.

KategorienLogik, Schach Tags:
  1. Bisher keine Kommentare
  1. Bisher keine Trackbacks