Chinook (Software)
Chinook ist ein Computerprogramm, das die englische Dame-Variante spielt. Es wurde um 1989 an der University of Alberta unter Leitung von Jonathan Schaeffer entwickelt. Mitarbeiter waren Rob Lake, Paul Lu, Martin Bryant und Norman Treloar. Im Juli 2007 wurde Chinook so stark, dass es nicht mehr verlieren kann.[1]
Mensch-gegen-Maschine-Weltmeister
Chinook ist das erste Computerprogramm, das den Weltmeistertitel im Kampf gegen Menschen gewann. 1990 gewann es das Recht, an der Weltmeisterschaft teilzunehmen, indem es nach Marion Tinsley den zweiten Platz bei der USA-Meisterschaft errang. Zunächst waren die American Checkers Federation und die English Draughts Association gegen die Teilnahme eines Computers an einer Menschen-Meisterschaft. Als Tinsley in Protest seinen Titel abgab, kreierten beide Organisationen die neue Mensch-gegen-Maschine-Weltmeisterschaft. Tinsley gewann 1992 viermal gegen Chinook, Chinook nur zweimal, 33 Partien endeten unentschieden.
1994 gab es einen neuen Titelkampf zwischen Tinsley und Chinook. Nach sechs unentschiedenen Partien musste Tinsley sich wegen Bauchspeicheldrüsenkrebs zurückziehen, so dass Chinook den Titel ohne Sieg über Tinsley, den mit Abstand besten Dame-Spieler aller Zeiten, gewann.[2]
1995 verteidigte Chinook seinen Mensch-gegen-Maschine-Weltmeister-Titel gegen Don Lafferty in 32 Spielen, von denen Chinook eines gewann, während die anderen unentschieden endeten.[3] Danach entschied Jonathan Schaeffer, Chinook nicht mehr in Turnieren spielen zu lassen, sondern löste Dame. Chinook hatte eine Rangpunktzahl von 2814.
Algorithmus
Chinooks Programm-Algorithmus beinhaltet ein Eröffnungsbuch, eine Bibliothek von Eröffnungszügen von Großmeister-Partien, einen Tiefensuche-Algorithmus, eine gute Stellungsbewertungsfunktion und eine Endspiel-Datenbank für alle Stellungen mit acht oder weniger Steinen. Die lineare handgeschriebene Stellungsbewertungsfunktion berücksichtigt diverse Bretteigenschaften inklusive Steineanzahl, Damenanzahl, gefangene Damen, wer am Zug ist, ungeblockte Wege zur Damenkreation und andere mindere Faktoren. Alles Wissen von Chinook wurde von seinen Kreatoren programmiert, nicht mit künstlicher Intelligenz gelernt.
Zeittafel
Jonathan Schaeffer schrieb 1997 das Buch One Jump Ahead: Challenging Human Supremacy in Checkers über Chinook.[4] Eine verbesserte Version wurde im November 2008 neu aufgelegt.
Am 24. Mai 2003 war die Datenbank von Chinook über 10 Steine mit 5 Steinen pro Seite fertig.[5]
Am 2. August 2004 publizierte das Chinook-Team, dass die Eröffnung Weißer Doktor (10-14 22-18 12-16) als unentschieden nachgewiesen ist.[6]
Am 18. Januar 2006 publizierte das Chinook-Team, dass die Eröffnung 09-13 21-17 05-09 als unentschieden nachgewiesen ist.
Am 18. April 2006 publizierte das Chinook-Team, dass die Eröffnung 09-13 22-17 13-22 als unentschieden nachgewiesen ist.
Am 10. März 2007 kündigte Jonathan Schaeffer (auf der ACM-SIGCSE-Konferenz) die vollständige Lösung von Dame innerhalb von 3 bis 5 Monaten an.
Am 19. Juli 2007 veröffentlichte die Zeitschrift Science den Artikel von Schaeffers Team Checkers Is Solved, der bewies, dass das beste Resultat eines Gegners von Chinook nur unentschieden sein kann.[7]
Einzelnachweise
- Computer Checkers Program Is Invincible. In: New York Times
- Partien Chinook-Tinsley von 1994 (Memento vom 29. August 2006 im Internet Archive)
- Details der Mensch-gegen-Maschine-Weltmeisterschaft 1995
- Jonathan Schaeffer: One Jump Ahead: Challenging Human Supremacy in Checkers. Springer, 1997, ISBN 978-0-387-94930-7.
- Chinook home page, 24 June 2003 (Memento vom 24. Juni 2003 im Internet Archive)
- Chinook home page, 30 September 2004 (Memento vom 30. September 2004 im Internet Archive)
- Schaeffer et al.: Checkers Is Solved. In: Science, doi:10.1126/science.1144079