Schachprogramm
Ein Schachprogramm ist ein Computerprogramm zum Spielen von Schach.
Geschichte
John von Neumann klassifizierte das Schachspiel in seiner Spieltheorie als Zwei-Personen-Nullsummenspiel mit vollständiger Information. Diese Klasse von Problemen (dazu gehört auch Tic tac toe) kann mit dem Minmax-Algorithmus gelöst werden. Schach ist jedoch zu komplex, um den Suchbaum vollständig abarbeiten zu können. Schachprogramme sind deshalb auf Näherungsverfahren angewiesen.
Das erste Schachprogram wurde von Claude Shannon entwickelt. Dieses Programm wurde mangels leistungsfähiger Computer händisch simuliert.
Aufbau
Zuggenerator
Der Zuggenerator erzeugt, ausgehend von einem bestimmten Spielstand, eine Liste aller möglichen Züge.
Bewertungsfunktion
Die Bewertungsfunktion liefert aufgrund von Heuristiken eine ungefähre Bewertung der aktuellen Stellung zurück.
Zugauswahl
Die Zugauswahl funktioniert im Wesentlichen nach dem Minmax-Algorithmus.
Besonderheiten
Eröffnungsbibliothek: Schach wird im Wettkampf auf Zeit gespielt, das heißt, für eine Anzahl von Zügen steht nur eine definierte Zeit zur Verfügung. Viele Schachprogramme sind daher mit einer Eröffnungsbibliothek ausgestattet, in der sehr viele "gute" Zugreihenfolgen in der Eröffnungsphase von Schachspielen abgespeichert sind. In der Anfangsphase des Schachspiels sieht das Programm in dieser Bibliothek nach, welcher Zug in einer bestimmten Brettstellung der geeignetste ist. Dieses "Nachsehen" geht schneller, als den Zug auszurechnen. Die so gesparte Rechenzeit steht dem Programm dann in späteren Phasen des Spiels zur Verfügung. Das Verfahren, Brettstellungen einschließlich der "guten" Züge abzuspeichern, ist nur für die Eröffnungsphase sinnvoll, da hier die Anzahl der Brettstellungen begrenzt ist.
Endspieldatenbank: Im Endspiel, wenn nur mehr wenige Figuren auf dem Brett sind, ist der Ausgang einer Partie für einen menschlichen Spieler oft offensichtlich, der Computer muss aber trotzdem alle Möglichkeiten durchprobieren. Viele Schachprogramme verwenden deshalb Endspieldatenbanken, die alle möglichen Stellungen mit 3, 4 oder mehr Figuren sowie deren Ausgang (bei optimalem Spiel) enthalten.
Freie Schachprogramme:
- http://www.gnu.org/software/chess/ - Gnu Chess
- http://www.limunltd.com/crafty/ - Crafty
Siehe auch
Literatur
- Bartel, Rainer; Kraas, Hans-Joachim; Schrüfer, Günther: Das große Computerschachbuch, Data Becker, 1985, ISBN 3890111173; gute Einführung in die Programmierung von Computerschach mit Beispielen in Basic.
- Shannon, Claude: Programming A Computer for Playing Chess, Philosophical Magazine 1950/41, S. 256-257
- Shannon, Claude: Programming A Computer To Play Chess, Scientific American 2/1950, S. 48-51