Schachprogramm

aus remoteSchach-Wiki, der freien Wissensdatenbank
Wechseln zu: Navigation, Suche

Ein Schachprogramm ist ein Computerprogramm zum Spielen von Computerschach. Es läuft entweder auf Allzweckcomputern wie PCs als ein Programm unter vielen, oder in speziell zum Schachspielen angefertigten Schachcomputern.

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 Minimax-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.

Ein sehr frühes Schachprogramm wurde 1950 von Claude Shannon entwickelt. Dieses Programm wurde mangels leistungsfähiger Computer auf Notizzetteln simuliert. Vorher hatte jedoch bereits Konrad Zuse ein Schachprogramm in seiner Programmiersprache Plankalkül erstellt.

Aufbau

Ein Schachprogramm besteht mindestens aus einem Zuggenerator, einer Bewertungsfunktion und einem Programmteil zur Steuerung der Suche.

Zuggenerator

Der Zuggenerator erzeugt, ausgehend von einem bestimmten Spielstand, eine Liste aller bei diesem Spielstand regelkonformen Antwortzüge (mögliche Bewegungen der Spielfiguren). In der Anfangsstellung sind 20 Figurenbewegungen möglich (16 Bauernzüge, 4 Springerzüge), im weiteren Spielverlauf kann man mit ca. 38-40 möglichen Antwortzügen pro Stellung rechnen.

Bewertungsfunktion

Die Bewertungsfunktion liefert die Bewertung einer Stellung zurück. Sie setzt sich aus einer materiellen und einer positionellen Komponente zusammen. Die positionelle Komponente ergänzt die materielle, da die Stärke der Spielfiguren auch von ihrer Position untereinander abhängt.

Für die materielle Wertung werden für die auf dem Brett befindlichen Spielfiguren Werte addiert (eine einfache Zuordnung ist z.B. Bauer=100, Läufer=300, Springer=300, Turm=450, Dame=900, für Schwarz die entsprechenden negativen Werte). Der König braucht nicht mitgezählt zu werden, da beide Parteien während des Spiels jeweils einen König haben.

Die positionelle Wertung zu bestimmen, ist eine Aufgabe von größerer Komplexität, in der sich die verschiedenen Schachprogramme deutlich voneinander unterscheiden und die kommerziellen auch gemeinhin nicht in die Karten schauen lassen. Dabei wird versucht, Stellungen aufgrund von schachrelevanten Parametern zu bewerten. Schachrelevante Parameter lassen sich grob klassifizieren in Königssicherheit, Bauernstruktur, beherrschte und bedrohte Felder, Figurenentwicklung etc.

Innerhalb dieser Kategorien gibt es quasi beliebig viele Parameter (für Bauernstrukturen z.B.: Freibauer, Doppelbauer, Hebel, Bauernduo, Widder, Isolani, Bauernkette. Für Königssicherheit z.B. König kann leicht links oder rechts rochieren, oder im Zentrum bleiben, Bauern vor dem König etc.). Es bietet sich an, diese Parameter zunächst wertneutral aus der gegebenen Stellung zu extrahieren. Kann ein Schachprogramm die Werte dieser Parameter pro Stellung effizient bestimmen, müssen diese untereinander gewichtet werden. Die Gewichtung der positionellen Komponente kann teilweise automatisch über das Analysieren von Eröffnungsdatenbanken, Großmeisterpartien oder durch Spiele gegen andere Schachprogramme erfolgen. Einfacher aufgebaute Bewertungsfunktionen geben sich für die positionelle Komponente mit statischen Positionsgewichten für die sechs Spielfigurentypen zufrieden, die aber für Eröffnung, Mittel- und Endspiel jeweils unterschiedlich ausfallen.

Schachprogrammierer stehen vor der Entscheidung, wie viel Rechenzeit sie für die positionelle Komponente einer ausgefeilten Bewertungsfunktion aufwenden sollen, und welche Parameter überhaupt einfliessen sollen: Je tiefer die Schachprogramme den Suchbaum analysieren können, desto eher wird nämlich die Umwandlung positioneller Vorteile in materielle Vorteile sichtbar.

Es sollte klargeworden sein, daß die Bewertungsfunktion außer in Grenzfällen wie Endspielen oder Matt- oder Pattsituationen keine objektiv richtigen Ergebnisse liefern kann. Indem die Bewertungsfunktion die materielle und positionelle Komponente zu einer einzigen Bewertungszahl zusammenfasst, ermöglicht sie aber die Sortierung und Auswahl des "besten" bzw. "schlechtesten" Zuges.

Steuerung der Suche und Zugauswahl

Grundsätzlich basiert die Steuerung der Suche auf dem Aufbau eines Positionsbaumes (Suchbaum) beginnend bei der aktuellen Stellung, allen Antwortzügen des Anziehenden, sowie für jeden Antwortzug aller möglichen Antwortzüge des Nachziehenden und so weiter, allein begrenzt durch die Rechenleistung und die für den Zug zur Verfügung gestellte Zeit. Jede dabei entstehende Stellung wird prinzipiell bewertet. Am Ende der Berechnung erfolgt die Zugauswahl nach dem Minimax-Algorithmus.

Da die Anzahl der zu untersuchenden Stellungen exponentiell wächst, andererseits eine höhere Suchleistung eine entsprechende Spielstärkeverbesserung hervorbringt, wurde von Programmierern in den rund 50 Jahren der Programmentwicklung ein ganzes Arsenal an Beschleunigungsmaßnahmen erfunden, um ein paar zu nennen:

  • Hashtables
  • Sortieren der Züge nach Ihrer Wertigkeit
  • Alpha-Beta-Pruning, Negamax-Verfahren
  • Einfache Evaluierungsfunktion verwenden, außer für gute Züge
  • Selektive Erweiterungen des Suchbaums
  • Null-Move-Suche

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 Eröffnung und Endspiel sinnvoll, da hier die Anzahl der Brettstellungen begrenzt ist.

Endspiel-Datenbank: Im Endspiel, wenn nur mehr wenige Figuren auf dem Brett sind, kann man den optimalen Zug im Vorhinein durch vollständige Analyse berechnen. Es gibt nicht wenige Endspielstellungen, in denen das menschliche Denken, aber auch die Computeranalyse in Echtzeit völlig überfordert wären. Viele Schachprogramme verwenden deshalb Endspiel-Datenbanken, die alle möglichen Stellungen mit 3, 4 oder 5 Figuren sowie deren Ausgang (bei optimalem Spiel) enthalten.

Kostenlose Schachprogramme

Siehe auch

Literatur

  • Rainer Bartel, Hans-Joachim Kraas, Günther Schrüfer: 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
Von "https://wiki.remoteschach.de/index.php?title=Schachprogramm&oldid=1627"