 |
|
|
|
|
|
 |
 |
Neues aus der Welt der Wissenschaft |
|
|
|
|
|
|
Computer setzt "Dame"-Spiel schachmatt |
|
| | | Kanadische Wissenschaftler haben ein "Dame"-Programm entwickelt, das nicht zu besiegen ist. Dafür mussten 50 Computer über 18 Jahre lang Spielzüge berechnen. Das "Dame"-Spiel gilt somit als gelöst. |
|
|
|
|
|
|
|
|
| |
"Chinook" kann nicht mehr verlieren. Jonathan Schaeffer von der University of Alberta hatte seit 1989 daran gearbeitet, sein "Dame"-Programm zu perfektionieren. Im April dieses Jahres erreichte er sein Ziel: Das Damespiel auf acht mal acht Feldern ist gelöst.
|
|
"Checkers is solved" von Jonathan Schaeffer et al. ist als Online-Vorabpublikation in "Science" (doi: 10.1126/science.1144079; 19.7.07) erschienen. |
|
|
 Zum Abstract |
|
|
|
|
|
|
Fehlerfreies Spiel ergibt Remis |
|
| |
Wenn man davon ausgeht, dass beide Seiten absolut fehlerfrei spielen, ist das Endergebnis immer ein Remis. Großmeister des "Dame"-Spiels hatten schon vor Jahrzehnten diese Vermutung angestellt, doch der Computerbeweis dieser Annahme ließ auf sich warten.
Schließlich musste Schaeffer 500 Milliarden Milliarden (5 x 1020) mögliche Positionen analysieren, um zu diesem Ergebnis zu kommen. Dafür brauchte es die Rechenarbeit von 50 Computern (zu Spitzenzeiten sogar 200), die 18 Jahre lang fast ohne Unterbrechung alle erdenklichen Stellungen durchgingen.
|
|
|
|
|
|
Unbesiegbares Programm |
|
| |
Dafür hat Jonathan Schaeffer, der sich selbst als "grauenhaften" Dame-Spieler beschreibt, nun mit "Chinook" ein unbesiegbares Programm geschaffen.
Egal, ob es mit weiß oder schwarz spielt, es kann gegen jeden beliebigen Gegner ein Remis herausholen, wenn dieser auch fehlerfrei spielt. Das Spiel gilt somit als "weakly solved" - schwach gelöst.
|
|
Ein Spiel mit vollständiger Information für zwei Spieler kann auf drei verschiedenen Ebenen gelöst werden:
- "Ultra-weak": Vorausgesetzt, dass beide Seiten perfekt spielen, kann gezeigt werden, ob ein Spieler mit einem bestimmten Anfangszug gewinnt, verliert oder Remis spielt.
- "Weak": Wenn beide Seiten perfekt spielen, kann mit einem Algorithmus sicher gestellt werden, dass ein Spieler mindestens ein Remis erzielt, egal, welche Züge der Gegner macht.
- "Strong": Ein Algorithmus erzeugt immer den perfekten Zug in jeder Position, auch wenn eine oder beide Seiten bis dahin nicht fehlerfrei gespielt haben. |
|
|
|
|
|
|
"Zwei Jahrzehnte lang besessen" |
|
| |
"Ich bin begeistert von dieser Leistung", sagt Schaeffer in einer Pressemitteilung. "Zwei Jahrzehnte lang war ich besessen von der Idee, das Damespiel zu lösen." Als er im Jahr 1989 das Projekt "Chinook" startete, hatte er das Ziel, damit einmal die "Dame"-Weltmeisterschaft zu gewinnen.
1990 wurde das Programm für die WM zugelassen, 1994 konnte es tatsächlich gewinnen. Damit war "Chinook" das erste Computerprogramm, das eine Weltmeisterschaft in einem Spiel für sich entschieden hat.
Seit 2001 widmete sich Schaeffer ganz der Aufgabe, mehr als nur den besten "Dame"-Spieler der Welt zu schaffen. Er wollte den perfekten "Dame"-Spieler - und damit die Lösung des Spiels.
|
|
|
|
|
|
Komplexestes gelöstes Spiel - bisher |
|
| |
"Dame" ist bis jetzt das komplexeste Spiel, das mit Hilfe von Computern gelöst wurde. "Das ist eine beeindruckende Demonstration der Möglichkeiten, die Software und Hardware mittlerweile bieten", sagt Schaeffer.
Allerdings warten in der Welt der Spiele noch ganz andere Herausforderungen. Vom "Dame"-Spiel zum Schach ist es zwar ein kleiner Schritt für die Menschheit, aber ein riesiger Sprung für die künstliche Intelligenz.
Für die 1043 möglichen Stellungen beim Schach bräuchten selbst die schnellsten Computer Äonen. Was immer noch eine Bagatelle ist gegen die Komplexität des "Spiels der Götter": Das Brettspiel Go bietet ungefähr 4,63 x 10170 Möglichkeiten, noch viel mehr, als es Atome im Universum gibt.
Raffael Fritz, science.ORF.at, 20.7.07
|
|
Noch bis 28. Juli findet im Congress Center Villach der 51. Europäische Go-Kongress statt.
Am Sonntag, den 22.7., 19 Uhr, hält Martin Müller, ebenfalls Professor an der University of Alberta, einen Vortrag über die Möglichkeiten der künstlichen Intelligenz bei der Entwicklung von Go-Programmen. |
|
|
European Go Congress - Villach 2007 |
|
|
|
|
|
|
|
|
| |
Mehr zu diesem Thema in science.ORF.at:
|
|
|
01.01.2010 |
