Durchbruch beim 27-Damenproblem

Das Schachbrett fordert Hochleistungsrechner noch immer  heraus – etwa bei der Frage, wie man eine bestimmte Anzahl von Damen auf einem Schachbrett platziert, so dass sie sich nicht gegenseitig schlagen können. Nun wurde das so genannte 27-Damenproblem dank eines Tricks beim parallelen Rechnen gelöst. 

Immer wieder muss sich ein Großmeister im Schach der Herausforderung stellen, gegen einen Computer zu spielen. Legendär sind in diesem Zusammenhang die Partien zwischen dem Schachweltmeister Garri Kasparow und dem Schachcomputer Deep Blue von IBM. Nie zuvor war es einem Schachcomputer gelungen, einen amtierenden Schachweltmeister zu schlagen. Heute schmunzeln allerdings viele über die Rechenleistung, die vor rund 20 Jahren ausreichte, Kasparow zu schlagen . "Viele Computersimulationen, für die man früher Supercomputer benötigte, lassen sich heutzutage auf Arbeitsplatzrechnern durchführen“, schreibt Stefan Gerlach in seinem Buchkapitel "Hochleistungsrechnen“. Und er fügt hinzu, dass "sich heute aufgrund der verbesserten Ressourcen und numerischen Methoden Probleme bewältigen lassen, die man früher nicht lösen konnte.“ Dazu gehört etwa das 27-Damenproblem.

Empfehlung der Redaktion

2016 | OriginalPaper | Buchkapitel

Suchen, Spielen und Probleme lösen

Bei fast allen Inferenzsystemen in der Künstlichen Intelligenz stellt die Suche nach einer Lösung, bedingt durch die extrem großen Suchbäume, ein Problem dar. Aus dem Startzustand gibt es für den ersten Inferenzschritt viele Möglichkeiten. Für jede dieser Möglichkeiten gibt es im nächsten Schritt wieder viele Möglichkeiten und so weiter. Wie dieses Problem gelöst werden kann, beschreibt Wolfgang Ertel in diesem Kapitel im Lehrbuch "Grundkurs Künstliche Intelligenz".

Zwar gelingt es jedem handelsüblichen Rechner binnen einer Sekunde, zu errechnen, wie viele Möglichkeiten es gibt, acht Damen auf einem Schachbrett zu platzieren. Doch mit jeder weiteren Schachfigur wächst die Berechnungszeit. So sind mehr als sieben Jahre vergangen, seitdem die erste Berechnung abgeschlossen wurde, um die Anzahl der Lösungen für das 26-Damenproblem zu ermitteln. Die Lösung erfolgte damals mittels Hardwareimplementierung am Institut für Technische Informatik der TU Dresden. Nun haben die Informatiker um Thomas Preußer, erneut als weltweit erstes Team das 27-Damenproblem gelöst. Die von ihnen entwickelten Löser nutzten Field Programmable Gate Arrays (FPGA), die ein massiv paralleles Rechnen ermöglichen. Durch die Vorplatzierung einiger Damen wird der Lösungsansatz so zerlegt, dass die resultierenden Teilprobleme unabhängig und parallel zueinander bearbeitet werden können.

So wurde das 27-Damenproblem gelöst

Nach Angaben der Informatiker wurde das 27-Damenproblem in 2.024.110.796 Teilaufgaben zerlegt, von denen kontinuierlich um die 7.000 gleichzeitig bearbeitet wurden. "Für eine Aussicht auf Erfolg bedurfte es der weiteren mathematischen Optimierung des algorithmischen Ansatzes und einer enormen Steigerung der Leistungsfähigkeit von FPGAs“, schreiben die Forscher. Schließlich mussten diverse FPGA-Boards an der Fakultät Informatik der TU Dresden immer noch über ein Jahr mit all ihrer Leerlaufzeit am 27-Damenproblem rechnen, bevor es geknackt war. Das Ergebnis? "Es ist eine einzige riesige Zahl, Q(27) = 234.907.967.154.122.528, die auch angibt, wie viele verschiedene Anordnungen von 27 Karten man als gut durchmischt ansehen kann. Es wird allerdings noch einige Zeit ins Land gehen, bevor diese Zahl auch für ein einfaches Skatblatt von 32 Karten bekannt sein wird“. Und das kann eine Weile dauern, glaubt Preußer. 

"In Anbetracht des enormen Rechenaufwandes und des dadurch begründeten langsamer werdenden Fortschritts bei der Analyse neuer Brettgrößen wird dieser Rekord wahrscheinlich über einige Jahre bestehen bleiben“. Auch die Bestätigung dieses neuen Ergebnisses durch unabhängige Berechnung könnte auf sich warten lassen. Als hochparalleles Computer-Benchmark ist das n-Damenproblem inzwischen auch für Forscherteams interessant, die Grafikkarten als allgemeine Rechenbeschleuniger einsetzen (GPGPU). Die massiv parallele Architektur von GPUs könnte jedenfalls die Bewältigung ähnlicher oder gar größerer Problemgrößen ermöglichen.