Checkers-Programme sind Computersoftware, die dafür entwickelt wurde, das Brettspiel Checkers zu spielen, das auch als Dames bekannt ist. Diese Programme verwenden algorithmische Techniken, um Positionen zu bewerten, optimale Züge zu suchen und gegen menschliche Spieler oder andere Computer anzutreten. Das bekannteste Checkers-Programm ist Chinook, das an der University of Alberta (obwohl das Projekt dort angesiedelt war, nicht in Toronto) von einem Team unter der Leitung von Jonathan Schaeffer entwickelt wurde und historische Meilensteine sowohl im Wettkampfspiel als auch bei der Spiellösung erreichte.
Chinook wurde zwischen 1989 und 2007 von einem Team an der University of Alberta entwickelt, bestehend aus Jonathan Schaeffer, Rob Lake, Paul Lu, Martin Bryant und Norman Treloar. Im Gegensatz zu modernen Ansätzen, die auf maschinellem Lernen basieren, war Chinooks Wissen vollständig von seinen Entwicklern handkodiert und verwendete traditionelle Künstliche-Intelligenz-Techniken wie Suchalgorithmen und Bewertungsfunktionen. Diese Unterscheidung verdeutlicht die Entwicklung der KI von regelbasierten Systemen zu datengetriebenen Methoden.
Mann gegen Maschine Weltmeister
Im Jahr 1990 sicherte sich Chinook das Recht, an der menschlichen Weltmeisterschaft teilzunehmen, indem es bei den US-Nationalmeisterschaften den zweiten Platz hinter Marion Tinsley belegte. Zunächst lehnten die American Checkers Federation und die English Draughts Association die Teilnahme von Computern an menschlichen Meisterschaften ab. Als Tinsley aus Protest seinen Titel niederlegte, schufen diese Organisationen den neuen Titel Mann-gegen-Maschine-Weltmeisterschaft, wodurch der Wettbewerb fortgesetzt werden konnte. Tinsley gewann das erste Match mit vier Siegen, zwei Niederlagen und 33 Unentschieden.
Ein Rückkampf im Jahr 1994 führte dazu, dass Chinook nach sechs unentschiedenen Partien zum Mann-Maschine-Weltmeister erklärt wurde, da Tinsley sich aufgrund von Bauchspeicheldrüsenkrebs zurückzog. Damit war Chinook das erste Computerprogramm, das einen Weltmeistertitel gegen Menschen gewann, obwohl es Tinsley nie besiegte, der selbst seinen engsten Konkurrenten deutlich überlegen war. Im Jahr 1995 verteidigte Chinook seinen Titel gegen Don Lafferty in einem Match über 32 Partien und gewann mit 1-0 bei 31 Unentschieden. Danach entschied sich Schaeffer, den Wettkampfbetrieb einzustellen und sich vollständig auf die Lösung von Checkers zu konzentrieren.
Algorithmus
Chinooks Algorithmus bestand aus vier Hauptkomponenten: einem Eröffnungsbuch mit Zügen aus Großmeisterpartien, einem tiefen Suchalgorithmus zur Erkundung möglicher Züge, einer Zugbewertungsfunktion und einer Endspieldatenbank, die alle Positionen mit acht oder weniger Steinen abdeckte. Die Bewertungsfunktion war eine lineare, handgefertigte Funktion, die Merkmale wie Steinanzahl, Königanzahl, gefangene Könige, Zugrecht und durchlaufende Steine (Steine mit ungehindertem Weg zum König) berücksichtigte. Das gesamte Wissen wurde von den Entwicklern programmiert und nicht gelernt, was einen Gegensatz zu späteren KI-Systemen wie den Ansätzen von DeepMind darstellt.
Zeitplan und Lösung von Checkers
Wichtige Meilensteine in Chinooks Entwicklung umfassen: 1997, als Schaeffer das Buch "One Jump Ahead: Challenging Human Supremacy in Checkers" veröffentlichte (aktualisiert im November 2008); den 24. Mai 2003, als die 10-Steine-Datenbank (5 Steine pro Seite) fertiggestellt wurde; und den 2. August 2004, als die Eröffnung "White Doctor" (10-14 22-18 12-16) als Unentschieden bewiesen wurde. Weitere Eröffnungen wurden am 18. Januar 2006 (09-13 21-17 05-09) und am 18. April 2006 (09-13 22-17 13-22) als Unentschieden bewiesen.
Am 10. März 2007 kündigte Schaeffer auf der ACM-SIGCSE-Konferenz an, dass eine endgültige Lösung innerhalb von 3-5 Monaten erwartet werde. Am 19. Juli 2007 veröffentlichte die Zeitschrift Science "Checkers Is Solved", das bewies, dass bei perfektem Spiel das beste Ergebnis ein Unentschieden ist. Damit war Checkers das erste große Brettspiel, das vollständig gelöst wurde, nach früheren Arbeiten an einfacheren Spielen. Zum Zeitpunkt seines Wettkampfhöhepunkts war Chinook mit 2814 Elo bewertet.
Vermächtnis
Chinooks Erfolg demonstrierte die Stärke klassischer KI-Techniken, einschließlich tiefer Suche und handgefertigter Bewertung, vor dem Aufstieg des Deep Learning. Seine Lösung von Checkers bleibt eine wegweisende Leistung in der Spiel-KI, vergleichbar mit Schachcomputern wie Deep Blue. Während moderne Checkers-Programme möglicherweise neuronale Netze verwenden, beeinflusste Chinooks Ansatz die spätere Forschung in Spieltheorie und kombinatorischer Spiellösung, und seine Methoden werden weiterhin in KI-Kursen an Institutionen wie der Carnegie Mellon University und dem MIT CSAIL gelehrt.