Chinook ist ein Computerprogramm, das das Brettspiel Dame spielt. Entwickelt von einem Team an der University of Alberta unter der Leitung des Informatikers Jonathan Schaeffer, wurde Chinook entwickelt, um auf höchstem Niveau gegen menschliche Damespieler anzutreten. Es erreichte 1994 einen historischen Meilenstein, indem es als erstes Computerprogramm eine Weltmeisterschaft in einem Strategiespiel gegen einen menschlichen Weltmeister gewann und Marion Tinsley besiegte. Im Jahr 2007 gab das Chinook-Team bekannt, dass das Programm Dame effektiv gelöst habe, was bedeutet, dass das Spiel bei perfektem Spiel beider Seiten immer unentschieden endet.
Die Entwicklung von Chinook begann 1989 als Forschungsprojekt in künstlicher Intelligenz und Spieltheorie. Das Programm verwendet eine Kombination aus Suchalgorithmen, Bewertungsfunktionen und einem umfangreichen Eröffnungsbuch. Sein Erfolg basierte auf den Prinzipien der Minimax-Suche mit Alpha-Beta-Beschneidung, einer Technik, die es dem Programm ermöglicht, Millionen von Stellungen pro Sekunde zu untersuchen. Das Programm wurde über mehrere Jahre verfeinert, mit erheblichen Verbesserungen seiner Bewertungsfunktion und Sucheffizienz.
Weltmeisterschaftserfolge
Chinooks berühmtester Erfolg kam 1990, als es sich das Recht erwarb, um die Weltmeisterschaft zu kämpfen, indem es bei der US-amerikanischen Nationalmeisterschaft im Dame den zweiten Platz belegte und damit das erste Computerprogramm wurde, das sich für einen menschlichen Weltmeistertitel qualifizierte. 1992 spielte Chinook ein Match gegen Marion Tinsley, den amtierenden Weltmeister, der weithin als der größte Damespieler aller Zeiten gilt. Das Match endete nach 40 Partien unentschieden, wobei Tinsley seinen Titel behielt. 1994 wurde ein Rückkampf ausgetragen, aber Tinsley zog sich nach sechs Partien aus gesundheitlichen Gründen zurück, und Chinook wurde zum Sieger erklärt, was es zum ersten Computerprogramm machte, das eine Weltmeisterschaft in einem Brettspiel hielt.
Nach Tinsleys Rücktritt verteidigte Chinook seinen Titel 1995 gegen Don Lafferty und gewann das Match. Das Programm trat weiterhin in menschlichen Turnieren an, wurde aber nach der Saison 1996 schließlich vom Wettbewerb zurückgezogen.
Das Lösen von Dame
Im Jahr 2007 veröffentlichte das Chinook-Team einen Artikel in der Zeitschrift Science, in dem es bekannt gab, dass es Dame gelöst habe. Die Lösung umfasste eine massive Rechenanstrengung, die eine Kombination aus retrograden Analysen und Suchalgorithmen verwendete, um zu beweisen, dass das Spiel bei perfektem Spiel ein Unentschieden ist. Das Team berechnete eine Datenbank aller Stellungen mit bis zu 10 Steinen auf dem Brett, was etwa 10^14 Berechnungen erforderte und über 18 Jahre kontinuierlicher Rechenzeit (unter Verwendung von verteiltem Rechnen) in Anspruch nahm. Das Ergebnis zeigte, dass Dame von der Standardstartposition aus ein theoretisches Unentschieden ist, was bedeutet, dass kein Spieler einen Sieg erzwingen kann, wenn beide optimal spielen.
Die Lösung von Dame war eine wegweisende Leistung in maschinellem Lernen und Spiel-KI, da es das größte zu dieser Zeit gelöste Spiel war, mit einem Suchraum von etwa 5×10^20 möglichen Stellungen. Es demonstrierte die Kraft der Kombination von Suchalgorithmen mit groß angelegter Berechnung und lieferte Einblicke in die Grenzen menschlicher Expertise in Spielen.
Technischer Ansatz
Chinooks Architektur basierte auf einem klassischen KI-Design für spielende Programme. Es verwendete eine Tiefensuche mit Alpha-Beta-Beschneidung, um Stellungen zu bewerten, und nutzte eine ausgefeilte Bewertungsfunktion, die Material, Mobilität und positionelle Vorteile berücksichtigte. Das Programm hatte auch ein großes Eröffnungsbuch mit Millionen von Stellungen aus Expertenpartien sowie eine Endspieldatenbank, die mit retrograden Analysen erstellt wurde. Die Endspieldatenbank war entscheidend für den Lösungsprozess, da sie es dem Programm ermöglichte, in den späten Phasen des Spiels perfekt zu spielen.
Für die Lösungsanstrengung verwendete das Team eine Technik namens "Proof-Number-Suche", um die Suche auf Stellungen zu lenken, die am wahrscheinlichsten Siege oder Niederlagen waren. Sie nutzten auch ein verteiltes Rechnernetzwerk, um die Milliarden von Stellungen in der Endspieldatenbank zu verarbeiten. Die endgültige Lösung war ein Beweis, dass Dame ein Unentschieden ist, aber das Team zeigte auch, dass, wenn ein Spieler einen Fehler macht, der andere einen Sieg erzwingen kann.
Vermächtnis und Einfluss
Chinooks Erfolg hatte einen bedeutenden Einfluss auf das Feld der künstlichen Intelligenz und Spielforschung. Es inspirierte spätere Bemühungen, andere Spiele zu lösen, wie Vier gewinnt (gelöst 1988) und später das Spiel Go, das von Programmen wie AlphaGo angegangen wurde. Chinook trug auch zur Entwicklung von Techniken zum Lösen von Spielen mit großen Zustandsräumen bei, und sein Ansatz wurde auf andere kombinatorische Probleme angewendet.
Zusätzlich zu seinen technischen Beiträgen warf Chinook philosophische Fragen über die Natur menschlicher versus maschineller Intelligenz auf. Der Sieg des Programms über einen menschlichen Weltmeister war ein Vorläufer späterer Erfolge im Schach (Deep Blue 1997) und Go (AlphaGo 2016). Heute wird Chinook als eine bahnbrechende Anstrengung in Erinnerung gerufen, die das Potenzial von Computern demonstrierte, komplexe Strategiespiele zu meistern.
Das Chinook-Projekt führte auch zur Entwicklung des Fhourstones-Benchmarks, eines Tests zur Messung der Leistung von Suchalgorithmen. Der Code und die Datenbanken des Programms wurden für Forschungszwecke verfügbar gemacht, und sein Vermächtnis beeinflusst weiterhin das Design von KI-Systemen für Spiele.