Turochamp -Turochamp
Turochamp | |
---|---|
Entwickler | Alan Turing , David Champernowne |
Genre(s) | Computerschach |
Modus(e) | Einzelspieler |
Turochamp ist ein Schachprogramm, das1948von Alan Turing und David Champernowne entwickelt wurde. Es wurde als Teil der Forschung des Paares über Informatik und maschinelles Lernen entwickelt. Turochamp ist in der Lage, eine ganze Schachpartie gegen einen menschlichen Spieler auf niedrigem Spielniveau zu spielen, indem er alle möglichen Züge und alle möglichen Spielerzüge als Reaktion sowie einige weitere Züge berechnet, die er für beträchtlich hält. Es weist dann jedem Spielzustand Punktwerte zu und wählt den Zug aus, der den höchsten Punktwert ergibt.
Turochamp ist das früheste bekannte Computerspiel, das in die Entwicklung ging, wurde jedoch von Turing und Champernowne nie fertiggestellt, da sein Algorithmus zu komplex war, um von den frühen Computern dieser Zeit wie der Automatic Computing Engine ausgeführt zu werden . Turing versuchte, das Programm in ausführbaren Code für den Ferranti Mark 1- Computer von 1951 in Manchester umzuwandeln , konnte dies jedoch nicht. Turing spielte im Sommer 1952 ein Match gegen den Informatiker Alick Glennie , der das Programm benutzte und es Schritt für Schritt manuell ausführte, aber bis zu seinem Tod im Jahr 1954 war das Programm immer noch nicht in der Lage, das Programm auf einem echten Computer auszuführen. Champernowne setzte das Projekt nicht fort und das ursprüngliche Programmdesign wurde nicht beibehalten. Obwohl das Programm nie auf einem Computer ausgeführt wurde, ist es ein Kandidat für das erste Schachprogramm; mehrere andere Schachprogramme wurden ungefähr zur gleichen Zeit entworfen oder vorgeschlagen, darunter ein weiteres, das Turing erfolglos auf der Ferranti Mark 1 laufen ließ. Das erste erfolgreiche Programm im Jahr 1951, ebenfalls für die Mark 1 entwickelt, wurde direkt von Turochamp inspiriert und war nur " Mate-in-two "-Probleme lösen können. Eine Nachbildung von Turochamp wurde 2012 für die Alan Turing Centenary Conference gebaut . Diese Version wurde in einem Match mit Schachgroßmeister Garry Kasparov verwendet , der auf der Konferenz eine Keynote hielt.
Spielweise
Turochamp simuliert ein Schachspiel gegen den Spieler, indem er die Züge des Spielers als Eingabe akzeptiert und seinen Zug als Reaktion ausgibt. Der Algorithmus des Programms verwendet eine Heuristik , um den besten Zug zu bestimmen, berechnet alle möglichen Züge, die es machen kann, dann alle möglichen Spielerreaktionen, die der Reihe nach gemacht werden könnten, sowie weitere "erhebliche" Züge, wie z nicht verteidigte Figuren, Rückeroberungen und das Erobern einer höherwertigen durch eine niedrigerwertige Spielfigur. Das Programm weist dann jedem resultierenden Zustand einen Punktwert zu und führt dann die Bewegung mit den höchsten resultierenden Punkten aus, wobei ein Minimax-Algorithmus verwendet wird, um dies zu tun. Die Punkte werden auf der Grundlage mehrerer Kriterien bestimmt, wie der Beweglichkeit jeder Figur, der Sicherheit jeder Figur, der Gefahr eines Schachmatts, des Werts der Figur des Spielers, wenn sie genommen wird, und mehrerer anderer Faktoren. Unterschiedliche Züge erhalten unterschiedliche Punktwerte; zum Beispiel erhält die Dame 10 Punkte, aber ein Bauer nur einen Punkt, und das Setzen des Königs in Schach erhält einen Punkt oder einen halben Punkt, basierend auf der Anordnung des Brettes. Laut Champernowne ist der Algorithmus in erster Linie auf die Entscheidung ausgelegt, eine Figur zu nehmen oder nicht; Laut Turing produziert das resultierende Gameplay ein Schachspiel auf niedrigem Niveau, das er als angemessen für seine selbstbeschriebenen durchschnittlichen Fähigkeiten des Spiels ansah.
Geschichte
Alan Turing war ein englischer Mathematiker , Informatiker , Logiker , Kryptoanalytiker , Philosoph und theoretischer Biologe . Turing war bei der Entwicklung von sehr einflussreichem theoretischer Informatik , eine Formalisierung der Konzepte der Bereitstellung Algorithmus und Berechnung mit der Turing - Maschine , die ein Modell eines Allzweck- betrachtet werden kann Computer . Turing gilt als Vater der theoretischen Informatik und der künstlichen Intelligenz . Ab 1941 begann Turing , während er in der Kriegskryptanalyse in Bletchley Park arbeitete , mit seinen Kollegen über die Möglichkeit einer Maschine zu diskutieren, Schach zu spielen oder andere "intelligente" Aufgaben auszuführen, sowie über die Idee eines Computers, der ein Problem durch Durchsuchen aller möglichen Lösungen mit Hilfe einer Heuristik oder eines Algorithmus. Einige von Turings kryptanalytischen Arbeiten, wie zum Beispiel an der Bombe , wurden anhand dieses Modells einer Rechenmaschine durchgeführt, die nach Möglichkeiten für eine Lösung suchte. Während des gesamten Krieges diskutierte er die Idee weiter mit seinen Kollegen, beispielsweise mit dem Wirtschaftsstatistiker DG Champernowne im Jahr 1944, und 1945 war er überzeugt, dass eine Maschine, die allgemeine Berechnungen durchführen kann, theoretisch in der Lage sein würde, alles zu replizieren, was ein menschliches Gehirn tun könnte. einschließlich Schach spielen.
Nach dem Zweiten Weltkrieg arbeitete Turing am National Physical Laboratory (NPL), wo er die Automatic Computing Engine (ACE) entwarf , eines der ersten Designs für einen speicherprogrammierbaren Computer. Im Jahr 1946 schrieb Turing einen Bericht für die NPL mit dem Titel "Proposed Electronic Calculator", der mehrere Projekte beschrieb, für die er den ACE verwenden wollte; Eines davon war ein Programm zum Schachspielen. Im darauffolgenden Jahr hielt er eine Lesung bei der London Mathematical Society, in der er die Idee vorstellte, dass eine auf Schach programmierte Maschine selbstständig lernen und eigene Erfahrungen sammeln kann. Anschließend verfasste er 1948 einen neuen Bericht für die NPL mit dem Titel "Intelligent Machinery", der eine Form der Schachimitation vorschlug.
Im Spätsommer 1948 entwickelten Turing und Champernowne, damals sein Kollege am King's College in Cambridge , ein System theoretischer Regeln, um die nächsten Züge einer Schachpartie zu bestimmen. Sie entwarfen ein Programm, das einen Algorithmus ausführte, der diesen Regeln folgte, obwohl das Programm zu komplex war, um auf dem ACE oder einem anderen Computer der damaligen Zeit ausgeführt zu werden. Das Programm wurde Turochamp genannt , eine Kombination ihrer Nachnamen. Es wird manchmal als "Turbochamp" falsch gemeldet. Laut Champernowne spielte seine Frau ein simuliertes Spiel gegen das Programm, das den Spitznamen "Papiermaschine" trug, und verlor. Turing versuchte, das Programm in ausführbaren Code für den 1951er Ferranti Mark 1- Computer in Manchester umzuwandeln , konnte dies jedoch aufgrund der Komplexität des Codes nicht. Laut Jack Copeland , Autor mehrerer Bücher über Turing, machte er sich keine Sorgen, dass das Programm nicht ausgeführt werden könnte, da er davon überzeugt war, dass die Geschwindigkeit und die Leistungsfähigkeit von Computern bald steigen würden, um dies möglich zu machen. Im Sommer 1952 spielte Turing mit dem Programm ein Match gegen den Informatiker Alick Glennie und führte es Schritt für Schritt manuell aus. Das Spiel, das aufgezeichnet wurde, hatte das Turochamp- Programm in 29 Zügen gegen Glennie verloren, wobei jeder der Züge des Programms bis zu 30 Minuten brauchte , um sie auszuwerten. Obwohl das Spiel demonstrierte, dass das Programm in einem vollständigen Spiel gegen einen Menschen spielen konnte, wurde es vor Turings Tod im Jahr 1954 nicht auf einem echten Computer ausgeführt.
Erbe
Turochamp ist ein Kandidat für das erste Schachprogramm, obwohl das ursprüngliche Programm nie auf einem Computer ausgeführt wurde. Mehrere andere Schachprogramme wurden ungefähr zur gleichen Zeit entworfen und ausprobiert, wie zum Beispiel in Claude Shannons Artikel Programming a Computer for Playing Chess von 1950 , Konrad Zuses Schachroutinen, die von 1941 bis 1945 für seine vorgeschlagene Programmiersprache Plankalkül entwickelt wurden , und Donald Michie und Shaun Wylies Schachprogramm Machiavelli , das Turing gleichzeitig mit Turochamp erfolglos auf dem Ferranti Mark I zu starten versuchte . Im November 1951 entwickelte Dietrich Prinz , der bei Ferranti arbeitete und sich von Turings Arbeit an Turochamp inspirieren ließ , für die Ferranti Mark I das erste lauffähige computerbasierte Schachprogramm, das „ Mate-in-two “-Probleme lösen konnte.
Der ursprüngliche Code und Algorithmus von Turing und Champernowne ist nicht erhalten geblieben. 1980 beschrieb Champernowne die Arbeitsweise von Turochamp , konnte sich jedoch nicht an alle Details der Spielregeln erinnern. Eine Version von Turochamp wurde 2012 aus Beschreibungen des Spielalgorithmus als symbolische Nachbildung entwickelt. Nachdem die anfängliche Erholung nicht in der Lage war Turings simuliert Spiel gegen Glennie, mehrere Computerschachexperten und Zeitgenossen von Turing nachzubilden wurden bei der Interpretation von Turing und Champernowne Beschreibungen des Programms gehört, darunter Ken Thompson , der Schöpfer der 1983 Belle Schachmaschine und dem Unix - Betriebssystem . Sie konnten die Erklärung für die Abweichung nicht finden, bis sie sich mit Donald Michie beraten hatten, der darauf hinwies, dass Turing sich nicht darum gekümmert hatte , genau auszuarbeiten, welchen Zug Turochamp empfehlen würde. Vor diesem Hintergrund konnten sie nachweisen, dass Turing vom ersten Zug der Partie an fälschlicherweise von suboptimal erscheinenden Zügen abgewichen war, ohne deren Punktwert zu berechnen. Die daraus resultierende Nachbildung wurde auf der Alan Turing Centenary Conference vom 22. bis 25. Juni 2012 in einem Match mit dem Schachgroßmeister und ehemaligen Weltmeister Garry Kasparov präsentiert . Kasparov gewann das Match in 16 Zügen und lobte das Programm für seinen Platz in der Geschichte und die "außergewöhnliche Leistung", ein funktionierendes Computerschachprogramm zu entwickeln, ohne es jemals auf einem Computer ausführen zu können.
Siehe auch
Anmerkungen
Verweise
Quellen
- Hodges, Andrew (2014). Alan Turing: Das Rätsel . Princeton University Press . ISBN 978-1-4008-6512-3.
- Biber, Anthony (2013). Cooper, S. Barry; van Leeuwen, Jan (Hrsg.). Alan Turing: Seine Arbeit und Wirkung . Sonst . ISBN 978-0-12-386980-7.
- Oppy, Graham; Trakakis, Nick (2011). Der antipodische Philosoph . Lexington-Bücher . ISBN 978-0-7391-6655-0.
- Atkinson, George W. (1998). Schach und Maschinenintuition . Intellekt Bücher. ISBN 978-1-871516-44-9.
- Copeland, B. Jack (2004). Das wesentliche Turing . Oxford University Press . ISBN 978-0-19-825079-1.
- Levy, David; Neugeborenes, Monty (2009). Wie Computer Schach spielen . Ishi-Presse . ISBN 978-4-87187-801-2.
- Sipser, Michael (2006). Einführung in die Rechentheorie . PWS-Publishing. ISBN 978-0-534-95097-2.
- Dasgupta, Subrata (2014). Es begann mit Babbage: The Genesis of Computer Science . Oxford University Press . ISBN 978-0-19-930941-2.
- Turing, Dermot (2015). Prof: Alan Turing Dekodiert . Die Geschichtspresse . ISBN 978-0-7509-6524-8.
Externe Links
- Video des Schachspiels zwischen Garry Kasparov und der Turochamp- Erholung
- Alan Turing vs Alick Glennie (1952) "Turing Test" bei Chessgames.com
- Turochamp (Computer) gegen Garry Kasparov (2012) bei Chessgames.com
- PyTuroChamp auf GitHub — Open-Source-Python-Implementierung von Turochamp
- Turochamp in einem Webbrowser , basierend auf dieser Nim- Version: nimTUROCHAMP auf GitHub