#1 19. Juli 2007 Professor Jonathan Schaeffer von der Universität Alberta hat nach eigenen Angaben die amerikanische Dame-Variante Checkers gelöst. Das Resultat: Bei beiderseits bestem Spiel endet eine Checkers-Partie mit einem Remis. Schaeffers Computerprogramm Chinook kann also nicht mehr verlieren. Um dieses Resultat zu erreichen, ließ Schaeffer mehr als 50 Computer mehrere Jahre lang rechnen. Zunächst erzeugte er riesige Datenbanken, die für alle Stellungen mit zehn oder weniger Steinen auf dem Brett eine perfekte Bewertung enthalten. Das funktioniert relativ einfach: Ein Programm generiert alle Stellungen mit zwei Steinen. Beim Checkers hat ein Spieler gewonnen, wenn sein Gegner keinen Stein mehr hat. Im nächsten Schritt prüft das Programm also, welche Stellungen durch einen Schlagzug sofort entschieden werden und markiert sie mit "Gewinn in einem Zug". Dann durchsucht es die verbleibenden Stellungen, um herauszufinden, welche davon zwangsläufig zu einer der bereits berechneten Gewinn-Stellungen führen ... und so weiter, bis keine Positionen mehr zu bereits berechneten führen können. Die restlichen Stellungen müssen unentschieden sein. Nachdem die Zweisteiner-Datenbank vorliegt, kann man sich an die Dreisteiner machen, wobei die Gewinnkondition im Übergang in eine gewonnene Zweisteiner-Stellung besteht. Die Zehnsteiner-Datenbank enthält mehr als 39 Billionen Stellungen, Achtsteiner immerhin noch ca. 440 Milliarden. Auch andere Programmierer haben mittlerweile Zehnsteiner berechnet und verteilen sie gegen einen Unkostenbeitrag auf Festplatte; die Achtsteiner gibt es zum Herunterladen. Im nächsten Schritt rechnete ein Programm von bestimmten Ausgangsstellungen drauflos, bis es in allen relevanten Varianten so tief in den Suchbaum vordrang, dass es die perfekte Bewertung aus der Zehnsteiner-Datenbank lesen konnte. Sowohl Datenbank-Generierung als auch Baumsuche stellen für erfahrene Programmierer keine so große Herausforderung dar; das Problem besteht in der langen Rechenzeit und der großen Datenmenge – um ein Spiel beweisbar zu lösen, müssen selbst Fehler wie zufällig umgekippte Speicher-Bits oder falsch gelesene Festplatten-Daten ausgeschlossen werden. Schaeffer löste jede Stellung darum nach zwei verschiedenen Methoden, um solche Fehler zu vermeiden. Checkers ist das komplexeste Spiel, welches je komplett berechnet wurde und löst damit Mühle ab. Gegen den perfekten Datenbank-Mühle-Spieler können Interessierte auf Inetplay antreten, aber ebenfalls kaum auf mehr als ein Remis hoffen. Checkers ist die einfachste der unzähligen Dame-Varianten; auf einem 8×8-Brett stehen sich jeweils 12 Steine gegenüber, die Dame darf wie ein einfacher Stein immer nur ein Feld weit ziehen, nur zusätzlich rückwärts. Dass Checkers im Unentschieden endet, überrascht keinen Experten. Schon seit langer Zeit spielen die Profis nicht mehr von der Grundstellung aus, weil diese zu einfach remis ist, sondern von einer aus drei zufälligen Halbzügen entstandenen Eröffnung. Davon gibt es insgesamt 216, von denen 60 als gewonnen anerkannt und weitere 12 nicht vom Checkersverband für Turniere zugelassen sind. In der Mitteilung Schaeffers heißt es, das Chinook-Team habe "19 relevante Eröffnungen identifiziert", sie bis in die Endspieldatenbanken durchrechnen lassen und daraus eine "allgemeine Strategie" entwickelt. Wahrscheinlicher ist jedoch, dass bis dato nur 19 der verbleibenden bei Turnieren zugelassenen 144 Startpositionen durchgerechnet wurden. Unter Experten gelten alle als remis, aber bewiesen wurde das eben bis jetzt noch nicht. Praktisch spielen nach Ansicht des Schweizer Checkers-Programmierers Martin Fierz die drei weltstärksten PC-Checkers-Programme Nemesis, Cake und Kingsrow sehr dicht an der Perfektion und dürften nur zu schlagen sein, wenn sie nicht genug Rechenpower verpulvern dürfen. Professor Jonathan Schaeffer beschäftig sich seit 1989 mit Checkers. Nachdem er einen eher weniger erfolgreichen Versuch in der Schachprogrammierung unternommen hatte, startete er das Projekt Chinook mit dem klaren Ziel, den Weltmeister zu schlagen. Das gelang nur halb, denn der damalige Champion, Marion Tinsley, der in vielen Jahrzehnten nur eine einstellige Anzahl Partien verloren hatte, besiegte 1992 Chinook, musste den Revanche-Kampf 1994 bei Gleichstand aus gesundheitlichen Gründen aufgeben und starb wenig später. Sein Schüler Don Lafferty sprang für ihn ein, und erreichte ebenfalls ein Unentschieden, sodass Chinook durch Aufgabe des Weltmeisters und Unentschieden gegen den Herausforderer die Palme errang, obwohl es den Wettkampf nicht gewinnen konnte. Es handelte sich auch nicht um eine offizielle Weltmeisterschaft, denn der Checkers-Verband hatte sich dagegen gesträubt und erst nach Intervention Tinsleys einen Titel "Mensch-Maschine-Weltmeister" extra für dieses Match erfunden. Das erste nicht triviale Denkspiel, in dem ein Computer gegen den Weltmeister aller Menschen siegreich blieb, dürfte Backgammon sein: 1979 schlug ein Programm den Champion Luigi Villa in Monte Carlo mit 7 zu 1. (Lars Bremer) / (jk/c't) Quelle:http://www.heise.de/newsticker/meldung/92996 + Multi-Zitat Zitieren