Computer-Schach

Autor: Andre Adrian
Version: 22.Dez.2011

Einleitung

Die ersten elektronischen Computer entstanden Ende der 1940er Jahre. Seit dieser Zeit wird über Schachprogramme nachgedacht. Computer-Schach wird oft dargestellt als Wettstreit zwischen dem "Elektronengehirn" und dem menschlichen Gehirn. In Wirklichkeit ist es eine Auseinandersetzung zwischen den Ideen eines Programmierers, welche von einem Computer ausgeführt werden, und den Ideen eines menschlichen Schachspielers.
Schach selbst spielen oder Schach spielen lassen, das ist hier die Frage. Einige Menschen sind vorzügliche Schachspieler. Andere Menschen schreiben Schachprogramme. Die Programm-Autoren sind oft Schachpatzer. Interessant ist auch das Spiel zwischen zwei Schachprogrammen. Spielen zwei leistungsschwache Programme gegeneinander, so endet die Partie oft in einer Stellungswiederholung. Jedes Programm entwickelt sein Spiel bis zur Grenze seiner Fähigkeiten und verharrt dann dort.
Diese Seite stellt etliche Schachprogramme vor. Besonders die Zeit der frühen Mikrocomputer von 1976 bis 1984 wird behandelt. Dank dem Internet sind viele Programme von damals noch vorhanden und lassen sich per Emulator auf aktuellen Computern ausführen.
Vorgestellt wird auch der Selbstbau Schachcomputer SHAH, ein Gerät ähnlich dem CompuChess von 1977, aber mit aktueller Hardware und Schachprogramm in C. Die Zeitschrift Elektor vertreibt den Bausatz als AVR-Max Schachcomputer. In einer Folge des ComputerClub 2 wurde der Schachcomputer sogar vorgestellt.

Überblick

Die Computerschach Historie läßt sich in mehrere Abschnitte unterteilen. Die erste Schach spielende Maschine war der elektromechanische Schachautomat von Torres y Quevedo aus dem Jahr 1914. Dies war eine fest verdrahtete Logik in Relais-Technik welche nur einen kleinen Teil des Schachspiels beherrschte. In der Zeit vor 1951 gab es noch keine Computer welche leistungsfähig genug waren um ein Schachprogramm auszuführen. In dieser Zeit haben Computerpioniere wie Zuse, Shannon und Turing Grundlagen für die folgenden Programme gelegt. Die von Shannon 1950 vorgeschlagene A-Strategie wurde als "brute force" Methode bekannt, die Shannon B-Strategie als "forward pruning".
Zwischen 1951 und 1977 war die Blütezeit der Großrechner (Mainframes). Groß war der Raumbedarf dieser Computer, die Rechenleistung war nach heutigen Maßstäben eher klein. Um die kleine Rechenleistung gut zu nutzen wurden bei der Baumsuche nicht alle möglichen Züge verfolgt. Die selektiven Schachprogramme mit "forward pruning" waren zwischen 1958 und 1973 vorherrschend. Von üblicherweise 35 möglichen Zügen in der Eröffnung und im Mittelspiel wurden bei einem selektiven Schachprogramm oft nur 8 untersucht. 1974 zeigte das russische Programm Kaissa die Leistung welche in einem intelligenten "brute force" Schachprogramm steckt. Kaissa rechnete nicht brutal alle Züge durch, sondern rechnete nur einen beschnittenen Suchbaum. Welche Teile des Suchbaums nicht besucht wurden bestimmte aber nicht eine "forward pruning" Bewertungsfunktion, sondern diese Information stammte aus der Baumsuche selbst. Wenn bei einem Schachprogramm mit Vorwärts-Beschneidung die Bewertungsfunktion versagt, dann spielt das Programm schlecht. Versagt bei einem Schachprogramm mit vollständiger Baumsuche und Alpha-Beta Beschneidung die Zugsortierung, dann spielt das Programm langsam. Der grösste Durchbruch im Computerschach dürfte die Einführung von Alpha-Beta Beschneidung, schrittweise Vertiefung (iterative Deepening) mit Zugsortierung und Transpositions-Tabelle (hash table) gewesen sein.
Ab 1976 begann die Zeit der persönlichen Computer, welche bis heute anhält. Mit Microchess auf dem KIM-1 und SARGON auf dem TRS-80 wurde Computerschach verfügbar für deutlich mehr Menschen als zur Zeit der Mainframe-Schachprogramme. Neben Computerschach, d.h. Schach auf einem universellen Computer, entstanden zu gleichen Zeit die Schachcomputer, Computer welche nur für das Schachspiel geeignet waren. Die Nachfolge der Mainframe-Schachprogramme traten 1978 mit Belle die Schachprogramme mit Spezialhardware an. Einfache Berechnungen, die aber sehr häufig ausgeführt werden mussten, wie das Erzeugen der möglichen Spielzüge, wurden nicht mehr in Software ausgeführt, sondern in Hardware.
Im 21. Jahrhundert wurden die Schachprogramme mit Spezialhardware wieder von Schachprogrammen auf normalen Computern überholt. Das Gigahertz-Wettrennen der Hersteller von PCs lieferte eine hohe Rechenleistung. Diese Rechenleistung wurde durch mehrere Rechenkerne pro Computer noch gesteigert. Neben mehr MIPS (Millionen von Rechenoperationen pro Sekunde) gab es auch weitere Verbesserungen bei der Beschneidung des Suchbaums. Die Programmierer hatten endlich das Ziel erreicht, bei der Baumsuche in einem schmalen Baum nicht mehr die interessanten Züge zu übersehen. Ab 2006 ist ein handelsüblicher persönlicher Computer mit dem entsprechenden Schachprogramm in der Lage den menschlichen Schachweltmeister zu schlagen.
Für die Künstliche Intelligenz Forschung hat die Beschäftigung mit Computerschach eine durchwachsene Bilanz hinterlassen: Ein, für den Menschen, einfach zu lernendes Spiel zeigt sich für den Programmierer als eine Herkules-Aufgabe. Schach-Spielen ist für den Menschen leicht, die Umsetzung dieser Fähigkeit in ein Computerprogramm aber schwierig. Einsicht in die Funktionsweise der menschlichen Denkprozesse haben die Schachprogramm kaum gegeben. Schach zwischen Mensch und Computer hat die enorme Leistungsfähigkeit des menschlichen Gehirns gezeigt.
Die automatische Übersetzung von geschriebenen Text von einer menschlichen Sprache in eine andere Sprache ist ein weiteres schwieriges Gebiet der KI Forschung. Vielleicht gelingt automatisches Übersetzen in der Qualität von menschlichen Übersetzern, vielleicht auch nicht. Beim Thema Computerschach war die Frage lange ungeklärt ob der Computer einmal so gut Schach spielen wird wie der menschliche Schachweltmeister.

Historie

1913    Ernst Zermelo beweisst den Minimax Algorithmus für Schach.
1914    Leonardo Torres y Quevedo zeigt den elektromechanische Automaten El Ajedrecista für das König Turm gegen König Endspiel.
1942    Konrad Zuse beschreibt einen Schach Zuggenerator in der Programmiersprache Plankalkül.
1949    Claude Shannon benutzt den Minimax Algorithmus in "Programming a Computer for Playing Chess"
1951    Der erste kommerzielle Computer Ferranti Mark 1 kann Matt-in-2-Zügen Aufgaben lösen. Programmautor ist Dietrich Prinz.
1953    Alan Turing  "Could one make a machine to play chess?" definiert ein Schachprogramm als Papiermaschine.
1958    Allen Newell, Herbert Simon and Cliff Shaw programmieren NSS, das erste Schachprogramm mit Alpha-Beta Beschneidung Suche.
1962    Alan Kotok dokumentiert in seiner Bachelor Thesis (Prof. John McCarthy) das MIT Chess Group Schachprogramm.
1967    Richard Greenblatt vom MIT verbessert das MIT Programm zu Mac Hack VI und errreicht 1400 Elo Punkte.
1969    Albert Zobrist beschreibt Transposition Hash-Tables in "A Hashing Method with Applications for Game Playing".
1970    Michael Botwinnik beginnt mit Pionier 1, einem selektiven Schachprogramm. Das Programm ist bei seinem Tod immer noch nicht fertig.
1970    CHESS 3.0, ein selektives Schachprogramm von Atkin, Gorlen und Slate gewinnt die erste US Computer Chess Championship.
1974    Das russische Schachprogramm Kaissa mit einem brute Force Algorithmus gewinnt gegen das U.S.A. Schachprogramm CHESS.
1975    CHESS 4.4, ein brute-force Schachprogramm von Atkin und Slate gewinnt die sechste US Computer Chess Championship.
1976    Peter Jennings verkauft  Microchess für den KIM-1 im Quelltext für $10. Dem 1.1KByte Programm fehlt Rochade, En Passant, Bauernumwandlung.
1977    Der Fidelity Chess Challenger 1 mit Programm von Ron Nelson ist der erste Schach Microcomputer (2MHz 8080) mit 985 Elo Punkten.
1977    Der CompuChess mit Programm von D. B. Goodrich and Associates wird als Chess Champion Mk I geklont. Es gibt einen Gerichtsfall.
1978    Ken Thompson und Joe Condon von den Bell Labs entwickeln den Schach Computer Belle. Belle schlägt mehrere Jahre alle anderen Schachcomputer.
1978    Der Internationale Meister David Levy gewinnt seine 10-Jahres-Wette gegen das Programm CHESS 4.7.
1980    Der Fidelity CC Champion mit Programm von Dan & Kathe Spracklen gewinnt die erste Microcomputer Weltmeisterschaft mit 1550 Elo Punkten.
1981    Das Programm Cyrus von Richard Lang (später im CXG Chess 2001) gewinnt die Computerschach Europameisterschaft mit ebenfalls 1550 Elo Punkten.
1983    Belle erreicht Meister Niveau mit 2250 Elo Punkten.
1985    Richard Lang entwickelt für Hegener + Glaser Mephisto Schachcomputer Programme. Mephisto gewinnt bis 1990 alles in seiner Klasse.
1989    Alexander Reinefeld beschreibt NegaScout (Principal Variation Search) im Buch "Spielbaum-Suchverfahren".
1989    Deep Thought von Feng-hsiung Hsu (Carnegie Mellon Universität) erreicht Grossmeister Niveau mit 2400 Elo Punkten.
1993    Christian Donninger veröffentlicht "Null move and deep search: Selective search heuristics for obtuse chess programs"
1994    Mephisto London 68030 mit 2302 Elo Punkten von Richard Lang besiegt Weltmeister Garry Kasparov mit 1.5:0.5 in zwei 25 Minuten Partien.
1996    Schachprogramm Deep Blue gewinnt eine Partie gegen Weltmeister Kasparov, verliert aber das Turnier mit 4:2.
1997    Ein verbesserter Deep Blue gewinnt das Turnier gegen Garry Kasparov mit 3.5:2.5. Die Hardware besteht aus 32 RS/6000 und 256 Schach ICs.
1997    IBM lehnt einen Revanche Kampf gegen Deep Blue ab. Kasparov fühlt sich betrogen (Link).
2002    Omid David-Tabibi und Nathan Netanyahu veröffentlichen "Verified null-move pruning"
2003    Kasparov spielt 3:3 gegen Deep Junior 7 von Amir Ban and Shay Bushinsky. Die Hardware besteht aus 4 Pentium 4 CPUs mit 1.9GHz.
2006    Weltmeister Wladimir Kramnik verliert gegen Deep Fritz 2:4. Ein Höhepunkt ist der menschliche Fehler in der 2. Partie - ein einzügiges Matt.

Von Bill Wall gibt es eine Computer Chess History in englisch. Eine umfangreiche Historie findet sich im Computer History Museum.

Torres y Quevedo, Endspielautomat, 1911

Der spanische Ingenieur Torres y Quevedo baute den ersten Schachautomaten. Dieser Automat spielte das König und Turm gegen König Endspiel. Der Algorithmus wurde mit einer fest verdrahteten Relaisschaltung realisiert. Neben der Berechnung der Züge konnte der Automat auch die Züge ausführen. Ein Greifarm hob die Spielfigur vom Schachbrett, bewegte sie und stellte sie wieder ab. Der menschliche Gegner bewegte seinen König. Diese Bewegung wurde ebenfalls von dem Schachautomaten erkannt. Der Schachautomat wurde 1914 in dem mechanischen Labor der Sorbonne gezeigt. Torres y Quevedo baute 1922 einen zweiten Schachautomaten. Bei diesem Modell wurden die Spielfiguren durch eine Mechanik unterhalb des Schachbrettes bewegt. Dieses Modell befindet sich heute im Museum des polytechnischen Institutes in Madrid.
Der Algorithmus bewegt entweder den Turm oder den König um ein Feld in Richtung feindlichen König. Selbst ein Anfänger im Schachspiel dürfte schneller Matt setzen als der Schachautomat, solange der Anfänger nicht in die Patt-Falle gerät.
Der Schachautomat von Torres steht in der Tradition von Automaten des 18. und 19. Jahrhunderts welche menschliche Tätigkeiten wie Schreiben, Malen und Musizieren ausführten. Diese Automaten wurden von einem Federwerk angetrieben. Die Feinmechanik dieser Automaten ist bewundernswert. Der Torres Automat geht einen deutlichen Schritt weiter. Es wird nicht ein sequentielles Programm ausgeführt, sondern der Automat reagiert auf seine Umwelt. Torres y Quevedo hat eine grosse Ingenieurleistung vollbracht. Er hat nicht nur den Algorithmus für das KRK Endspiel formuliert, sondern er hat auch einen funktionsfähigen Automaten gebaut.



Bild: Torres y Quevedo Algorithmus für KRK Endspiel-Automat, aus der Zeitschrift BYTE, Ausgabe September 1978, Seite 86.

Konrad Zuse, Zuggenerator, 1942

Konrad Zuse baute 1941 den Digitalrechner Z3 in Relaistechnik. Zwischen 1941 und 1942 entwarf er ein Zuggenerator Programm. Das Programm konnte die möglichen pseudolegalen Schachzüge erzeugen. Eventuell hat Zuse über eine Baumsuche oder über ein Programm für das König, Turm, König Endspiel nachgedacht. Diese Ideen sind in den 1940er Jahren nicht veröffentlicht worden. Konrad Zuse hatte mit Plankalkül eine frühe Programmiersprache entwickelt. Das Buchmanuskript von 1945 wurde erst 1972 veröffentlicht. Zu diesem Zeitpunkt hatte Plankalkül keine Auswirkung mehr auf die Entwicklung von Programmiersprachen. Im Zuse Internet Archiv findet sich das Kapitel über Schach im Plankalkül Manuskript sowie ein späterer Artikel über Plankalkül und Schach.
In einem Artikel von 1959 spricht Zuse über die Anwendung der Datenverarbeitung bei der Flugsicherung: "Es ist z.B. geplant, für die Aufgaben der europäischen Flugsicherung eine Großrechenanlage einzusetzen. Die hierbei zu lösenden Probleme sind jedoch so komplex und schwierig, daß man zunächst einmal auf der Z22 diese Aufgaben programmiert hat, um die günstigste Struktur der Programme zu erforschen. Ferner wurde auf der Z22 die Arbeitsweise einer geplanten Großrechenanlage (TR4, Telefunken) für diese Zwecke simuliert".
Anmerkung: Die TR4 wurde gebaut und später die TR86. Beide wurden für die Flugsicherung in Deutschland eingesetzt. Der Autor durfte selbst noch eine TR86 in Funktion bewundern als er 1991 bei der Flugsicherung begann. Von Wolfgang Pavel gibt es einen Z22 Simulator.



Bild links: Skizze von Konrad Zuse von 1941. Wahrscheinlich Speicherberechnung für die interne Brettdarstellung  64 Felder x 4Bit = 256Bit.
Bild rechts: Skizze von Konrad Zuse von 1941. Wahrscheinlich Programmfragment zum König, Turm, König Endspiel.

Claude Shannon, Random Mover, 1949

Im März 1949 hält Claude Shannon auf der IRE Convention in New York den Vortrag "Programming a Computer for Playing Chess". Der Artikel ist heute noch lesenswert. Die Shannon Type A Strategie ist Minimax. Die Type B Strategie lautet "Select the variations to be explored by some process so that the machine does not waste its time in totally pointless variations" (Durch einen Prozess die Züge auswählen damit der Computer nicht seine Zeit mit sinnlosen Varianten vergeudet).
Wird aus den legalen Zügen des Zuggenerators ein Zug zufällig ausgewählt, so entsteht ein Random Mover Schachprogramm. Shannon schreibt: "The writer played a few games against this random strategy and was able to checkmate generally in four or five moves (by fool's mate, etc.). The following game will illustrate the utter purposelessness of random play:"



Bild: Random Mover gegen Claude Shannon, 1949. Matt nach 4 Zügen. Partie in PGN.

Alan Turing, Turochamp, 1951

Alan Turing arbeitete an dem Schachprogramm Turochamp (Turbochamp). Für die Partie Turochamp gegen Alick Glennie im Jahr 1952 hat Turing das Schachprogramm mit Papier und Bleistift simuliert, siehe Manuskript "Digital computers applied to games" in dem Buch "Faster than thought" von B.V. Bowden, 1953. Turing beschreibt eine Baumsuche mit einer Tiefe von zwei Halbzügen und anschliessender Ruhesuche: "Every possibility for white's next move and for black's reply is 'considerable'. If a capture is considerable then any recapture is considerable" (Jeder weisse Zug und jede schwarze Antwort ist zu berücksichtigen. Wenn ein Schlagzug zu berücksichtigen ist, dann ist jedes Zurückschlagen zu berücksichtigen).
Die Partie Turochamp gegen Glennie ist in zwei Varianten überliefert. Bis zum 20. Zug sind beide Partien gleich.



Bild links: Turochamp gegen Alick Glennie, Partieverlauf aus Turing Manuskript. Partie in PGN.
Bild rechts: Turochamp gegen Alick Glennie, Verlauf nach "Schach am PC". Partie in PGN.

Dietrich Prinz, Robot Chess, 1952

Der Ferranti Mark I aus England war der erste kommerzielle Computer welcher in Stückzahl gebaut wurde. Eine Fließkommazahl war 40 Bit lang, ein Assemblerbefehl 20Bit. Der Computer in Röhrentechnik benutzte Williams-Kilburn-Röhren für das Random Access Memory (RAM) und magnetischen Trommelspeicher für Programme und Daten. Der Trommelspeicher fasste maximal 80kByte: "Each drum had up to 256 separate peripheral tracks accessed by up to 16 blocks of 16 heads with each track holding 64 words each of 40 digits. The total upper capacity of each drum was 655,360 digits". Dr. Dietrich Günther Prinz war der Leiter der Programmierabteilung (head of programming). Er entwickelte ein Programm zur Lösung von Matt in zwei Zügen Aufgaben an der Universität von Manchester. Im Jahr 1952 veröffentlichte er den Artikel "Robot chess" in der Zeitschrift Research [Prinz, D. G., 1952, Robot chess, Research 5: 261–266]. Im Artikel wird ein einfaches Mattproblem vorgestellt. Der Mark I benötigte 15 Minuten für die Lösung
Das Programm arbeitete "brute force". Dr. Prinz schrieb "the machine is forced to investigate every possible move". Alle zukünftigen Entwicklungen wurden von dem Autor gut vorausgesagt: "The possibility must, of course, not be excluded that by refined programming, by the use of faster machine, or both, a superior game played by a universal computer may finally be realized, not to mention the possibilities of special machines built for the purpose of playing chess only". Die Programmierung wurde besser, die computer wurden viel(!) schneller und die spezielle Hardware für Computerschach wurde ebenfalls gebaut.
Von Dr. Prinz stammt wahrscheinlich das "mailbox chessboard". Er schrieb: "Figure 3 which shows a 10x10 board ... Of these 100 squares, only the central 64 constitute the proper or active board while the remaining 36 form a border". Um im Robot Chess Programm den Brettrand erkennen zu können wurde das 8 mal 8 Felder grosse Schachfeld in ein 10 mal 10 Felder grosses Array gelegt. Weil der Springer zwei Schritte in eine Richtung ausführt wurde später die 12 mal 10 Felder grosse mailbox üblich. Robot chess unterteilte einen Springerzug in einen Schritt in die eine Richtung und zwei Schritte in eine andere Richtung. Nach dem ersten Schritt wurde auf Spielfeldrand geprüft.



Bild: Robot Chess Matt in 2 Zügen, Weiss am Zug. Die Lösung ist 1. Th6 gxh6 2. g7#.

We grow Systems - Exkurs zum Thema Entwicklung

Heil den unbekannten
Höheren Wesen,
Die wir ahnen!
(Goethe, Das Göttliche)

Claude Shannon beschreibt einen wichtigen Unterschied zwischen Mensch und Computer: "It is possible to give a person one or two specific examples of a general situation and have him understand and apply the general principles involved. With a computer an exact and completely explicit characterization of the situation must be given with all limitations, special cases, etc. taken into account."
Dem Menschen genügen wenige, oft unvollständige Beispiele um die Generalisierung anzuregen. Dem Computer fehlt diese Eigenschaft und alles muß haarklein erklärt werden. Dieser nüchterne Blick des Wissenschaftlers Shannon ist die wohltuende Sicht der Vernunft. In den 1950er Jahren wurden vom Elektronengehirn Wunder erwartet - manche Chefs erwarten diese Wunder noch heute.
In der Zwischenzeit ist das Übertragungsproblem zum ständigen Begleiter des Systementwicklers geworden. Menschen können ohne besondere Schwierigkeiten ihre Tätigkeiten ausführen. Eine Automatisierung scheitert weil die Beschreibung der Tätigkeiten nicht präzise genug für den Computer gelingt. Siehe auch den Unvollständigkeitssatz von Kurt Gödel oder das Halteproblem von Alan Turing.
Wahrscheinlich ist es dem Menschen sogar unmöglich nicht zu lernen - die Konditionierung ist ein Beispiel dafür. Shannon schreibt auch über das lernende Schachprogramm: "Some thought has been given to designing a program which is self-improving but, although it appears to be possible, the methods thought of so far do not seem to be very practical.". Bis heute ist die Künstliche Intelligenz Forschung über das "not very practical" nicht weit hinausgekommen. Der Unvollständigkeitssatz läßt sich philosophisch interpretieren als "ein System kann sich nicht selbst erklären" mit der Anwendung "der Mensch kann seine Lernfähigkeit nicht erklären" und deshalb nicht in ein Computerprogramm übertragen.
Andererseits ist die natürliche Intelligenz mit ihrer Lernfähigkeit irgendwie entstanden. Die übliche Hypothese ist Entstehung durch Mutation und Selektion, d.h. durch Wechselwirkung zwischen einfachem Lebewesen und komplizierter Umwelt. Vielleicht läßt sich eine künstliche Intelligenz "mendeln". Wenn das Universum (die ganze Umwelt) als das komplexere System begriffen wird, kann das einfachere System sich daran hochentwickeln ohne gegen den Unvollständigkeitssatz zu verstoßen. Äußere Komplexität der Umwelt wird durch Evolution umgewandelt in innere Komplexität des Untersystems Lebewesen. Es gibt auch keinen Widerspruch zur Thermodynamik. Die Komplexität als Entsprechung der Wärme fließt von der heißeren, komplexeren Umwelt in das kältere, primitivere Lebewesen. Die angenommene grosse Komplexität des Weltalls macht die Entstehung von Lebewesen zwangsläufig. Die Entstehung des Weltalls kann dieser Exkurs auch nicht erklären. Der "Am Anfang war das Nichts und das ist dann explodiert" Urknall ist das grösste Wunder.
Komplizierte Umwelt, einfaches Lebewesen ist die Kernidee. Im Sinne von "ich denke, also bin ich" fühlt der Mensch sich vielleicht wohler wenn "die Krone der Schöpfung" komplizierter ist als alles andere. Jeder Informatiker lernt aber "don't mess with Ms. Murphy". Was ist schon der einzelne Mensch in all seiner Pracht verglichen mit dem Kosmos der auch alle Menschen beinhaltet? Die Umwelt der Fische besteht zum Großteil aus anderen Fischen und produziert emergent behaviour wie Schwarmverhalten als kollektive Intelligenz.
Oft heißt es ja "die Zeit war reif" wenn Doppelerfindungen auftreten. Eigentlich hat die Evolution von äußerer Komplexität (es ist da) zu innerer Komplexität (es gibt eine Patentanmeldung) dazu geführt das nur noch ein kleiner Entwicklungsschritt zu gehen war. Und den haben dann verschiedene Erfinder fast gleichzeitig getan.
Eine aktuelle Denkrichtung der Informatik arbeitet mit sehr kurzen Entwicklungszyklen und beginnt schon mit der Entwicklung des Systems - in einer prototypischen Version - bevor die Systemziele komplett verstanden und festgelegt sind. Dieser Ansatz hat "entwicklungsbiologische" Züge. "We grow systems" anstelle von "we construct systems".
Für zielgerichtete Programmweiterentwicklung ist eine Bewertungsfunktion nötig um festzustellen ob die neue Programmversion besser als die alte Programmversion ist. Auch wenn eine solche Bewertungsfunktion oft schwer zu finden ist, die Bewertungsfunktion ist doch einfacher als das zu bewertende Programm. Eine Komplexitätsreduktion findet statt.
Aktueller Kenntnisstand der Informatik ist somit: selbstlernende Programme gibt es immer noch nicht. Die heutige beste Annäherung ist die Mutation von Programmversionen durch den Programmierer und die anschließende Selektion mit Hilfe einer Bewertungsfunktion. Wiederholung von Mutation und Selektion bis die in der ebenfalls fortgeschriebenen Aufgabenstellung festgelegten Ziele erreicht sind. Wer denkt jetzt nicht an "alles fließt"? Die Bewertungsfunktion wird gemäß Galileo Galilei nach dem wissenschaftlichen Prinzip bestimmt: "Es ist nötig, alles zu messen, was messbar ist, und zu versuchen, messbar zu machen, was es noch nicht ist".
Die Entwicklung des "Schachprogramms an sich" von den ersten Versionen der Programmzüchter Konrad Zuse, Claude Shannon, Dietrich Prinz, Alan Turing bis heute können als "evolution in progress" gesehen werden. Mit dieser Betrachtungsweise war die Schachprogramm-Entwicklung in der Künstlichen Intelligenz Forschung ein voller Erfolg - auch wenn einige sagen "wir haben für teuer Geld und viel Zeit gelernt was wir niemals wissen wollten". Damit Geld und Zeit nicht verschwendet waren sollten wir die gelernten Lektionen bezüglich Übertragungsproblem, Fortschreibung der Anforderungen, schrittweise Erweiterung und Komplexitätsreduzierung bei der Entwicklung anderer komplexer Systeme anwenden.

Alex Bernstein, IBM 704 Chess, 1958

Der Artikel "Computer vs. Chess-Player" in der Juni 1958 Ausgabe von Scientific American von Alex Bernstein und Michael de V. Roberts beschreibt ein Schach-Programm von 1958. Dieses Programm beherrschte alle Phasen den Schachspiels, nicht nur einen Teil des Endspiels. Wegen der geringen Rechenleistung des Computers, einer IBM 704, wurden immer nur 7 Kandidatenzüge genauer untersucht. Eine Bewertungsfunktion bestimmte diese Kandidaten aus der Menge der möglichen Züge. Die Suchtiefe war 4 Halbzüge. Der Computer benötigte im Durchschnitt 8 Minuten für die Berechnung seines Zuges. Der Artikel endete mit dem typischen Optimismus der Künstlichen Intelligenz Forschung zum Thema Computer Learning: "and some day - not overnight - we may have machines which will improve their game as they gain experience in play against their human opponents".



Bild: IBM 704 Chess gegen Mensch 1958. Die Partie in PGN.

MIT Chess Group Schachprogramm, 1959 - 1962

Alan Kotok hat 1962 ein Schachprogramm zum Thema seiner Bachelor Thesis bei Prof. John McCarthy gemacht. Im Anhang 1 ist der Fortran und Assembler Quelltext dieses frühen Schachprogrammes dokumentiert. Heutige Schachprogramme haben eine große Suchtiefe bei einfacher Bewertungsfunktion und arbeiten damit ganz anders als die Schachliteratur das Schachspiel darstellt. Kotok schreibt über den Versuch der Chess Group das Wissen der Schach Literatur in ein Computer Programm zu übertragen: "Although many tips were given concerning the play of the game, relative importance of various strategies was uncertain". Jahre später hat Ken Thompson mit seinen Endspieldatenbanken die Schach Literatur im Bereich Endspielwissen korrigiert und erweitert.

Richard Greenblatt, Mac Hack VI, 1967

Das Programm Mac Hack Six lief auf einem PDP-6 Computer, einem 36 Bit Großrechner von DEC welcher ab 1963 gebaut wurde. Mac Hack war ein erfolgreiches Programm. Es besiegte bei Turnierspielen menschliche Schachspieler und erhielt deshalb als erstes Schachprogramm eine offizielle Wertung von 1400 Punkten nach dem US Wertungs-System. Greenblatt beschreibt die Ursachen des Erfolges so: "We did not pretend to be writing a general problem solving system, but addressed ourselves directly to the problem of chess ... The program has been edited and reassembled over 200 times and has played several hundred complete games". Greenblatt hat sich auf das naheliegende Ziel konzentriert und hat viel Arbeit in Test, Fehlererkennung, Fehlerbeseitigung und erneuten Test investiert. Mac Hack hatte als erstes Schachprogramm eine Eröffnungsbibliothek.
Eine Partie spielte Mac Hack gegen den Philosophen Hubert Dreyfus. Dreyfus verkündete 1964 sehr kritische Ansichten über Künstliche Intelligenz in dem Artikel Alchemy and Artificial Intelligence. Seine Aussage "there will always be games that people can win and machines cannot" führte zu einer Partie zwischen Dreyfus und Mac Hack. Diese Partie gewann der Computer. Nach Seymour Papert führte diese Partie aber nur zu der Erkenntnis, daß weder Computer noch Dreyfus richtig Schach spielen können.



Bild links: Massachusetts State Championship 1967, Spiel 3, Turnier 2, Weiss: Mac Hack VI, Schwarz: Spieler mit 1510 USCF Punkten. Die Partie in PGN.
Bild rechts: Weiss: Hubert Dreyfus, Schwarz: Mac Hack VI. Die Partie in PGN

Atkin, Slate, CHESS, 1970 - 1979

Das bekannteste Schachprogramm für Großrechner war CHESS von Larry Atkin, David Slate und Keith Gordon. In den Jahren 1970 bis 1979 gewann CHESS acht mal die US Computer Chess Championship. Die Versionen 3.x waren selektive Schachprogramme, die Versionen 4.x waren brute force Programme. CHESS lief auf leistungsstarken Computern wie der Control Data Corporation (CDC) Cyber 176. Das Programm CHESS benutzte Bitboards.

Kaissa und Belle

Die 1960er und 1970er Jahre waren die Zeit des Computerschach auf dem Großrechner. Die Schachcomputer Geschichte von Karsten Bauermeister und die Computer Chess History by Bill Wall liefern viel Information zum Thema Großrechner-Schach.
Bei der ersten Computer-Weltmeisterschaft 1974 in Stockholm gewann das UdSSR Programm Kaissa. Ab 1978 konnten CHESS und Kaissa beide einpacken. Ken Thompson, einer der Entwickler der Programmiersprache C und des Betriebssystem UNIX, benutzte einen maßgeschneiderten Computer für das Schachspiel. Eine PDP-11 plus spezielle Hardware führten Belle zu vielen Erfolgen in den nächsten Jahren.

Peter Jennings, Microchess, 1976

Im Dezember 1976 konnte sich ein Schachspieler den ersten Schachcomputer kaufen. Der fertig aufgebaute KIM-1 von MOS Technology war ein Einplatinen-Computer mit 6502 CPU. Die CPU wurde später auch im  Apple II, Commodore PET und Commodore C64 verbaut. Die Computer-Programme wurden auf Kassettenrecorder gespeichert. Die Eingabe erfolgte über 23 Tasten, die Ausgabe über eine 6-stellige LED Anzeige. Das Schachprogramm für den KIM-1 war Microchess von Peter Jennings. Die Preise waren 245 US-Dollar für den Computer, 10 US-Dollar für das Schachprogramm und einige zehn Dollar für Netzteil und Kassettenrecorder.
Das original 6502 Assembler Programm von Peter Jennings wurde 2002 von Bill Forster in C umgeschrieben. Ich habe ein xboard/WinBoard Interface hinzugefügt. Nun kann Microchess von 1976 mit zeitgemässer Grafik gegen die Computerschach Spieler von heute antreten. Oder Microchess spielt gegen sich selbst oder gegen andere Computerschach Programme. Gegen Microchess haben auch Anfänger eine Chance!
Drei Musterpartien zeigen die Schachfähigkeiten von Microchess:



Bild links: Microchess - Microchess 0:1. Die Partie in PGN gibt es hier. Die komplette Partie dauerte 2 Sekunden!
Bild mitte: Anfänger - Microchess 1:0. Die Partie in PGN.
Bild rechts: Microchess - Anfänger 0:1. Die Partei in PGN.

Download Microchess

Der C Quelltext für die WinBoard Version von Microchess ist hier. Kompiliert wurde mit der kostenlosen Microsoft Visual C++ 2005 Express Edition.
Die MS-Windows Programmdatei (Exe Datei) ist hier. Die Datei ist 11 KByte gross.

Installation Microchess

Zuerst einmal muss xboard/Winboard installiert werden, z.B. in das Verzeichnis C:\Programme\WinBoard. In dieses Verzeichnis muss die microchessw.exe Datei kopiert werden. Damit die Microchess Schach-Engine gefunden wird sind Änderungen in der winboard.ini Datei nötig. Der relevante Ausschnitt der Ini-Datei vor und nach der Änderung:
vorher
nachher
/firstChessProgramNames={GNUChess
"GNUChes5 xboard"
}
/secondChessProgramNames={GNUChess
"GNUChes5 xboard"
}
/firstChessProgramNames={GNUChess
"GNUChes5 xboard"
microchessw
}
/secondChessProgramNames={GNUChess
"GNUChes5 xboard"
microchessw
}

Eine geänderte winboard.ini Datei für WinBoard Version 4.2.7 gibt es hier. Diese Datei enthält die obigen Änderungen und ersetzt die alte Ini-Datei im WinBoard Verzeichnis.

Robert Arnstein, 8080 Chess, 1977

Das Programm 8080 Chess von Robert Arnstein lief auf einem Processor Technology Sol 20. Der Sol 20 hatte eine Intel 8080 CPU. Die Bildschirmauflösung von 64 Zeichen in 16 Zeilen war wie beim Tandy TRS-80. 8080 Chess war ein Teilnehmer der ACM US Computer Chess Championship im Jahr 1977. Dieses Mikroprozessorprogramm belegte den 9. Platz von 12 Plätzen.
Von Jim Battle gibt es eine Sol 20 Seite mit Emulator und Software.



Bild: AVR-Max 4.8 gegen 8080 Chess. Partie in PGN.

Spracklen, SARGON CHESS, 1978

SARGON von Dan & Kathe Spracklen hat 1978 das Microcomputer Schach Turnier auf der West Coast Computer Faire gewonnen. SARGON lief auf einem Wavemate Jupiter III mit Zilog Z80 Prozessor. Der Jupiter hatte eine hohe Auflösung von 64 ASCII Zeichen auf 32 Zeilen oder 128 mal 96 Pixel Blockgrafik.
Zuerst haben die Autoren das Z80 Assembler Listing in TDL ZASM Syntax selbst vertrieben. Später wurde das Listing als Buch "Sargon A Computer Chess Program" von dem Verlag Hayden veröffentlicht. Das SARGON Assembler Listing wurde von Andre Adrian nach CP/M portiert, siehe das SARGON CP/M Programm. Von Takeda Toshiya gibt es einen einfachen CP/M Emulator für MS-Windows, den CP/M Player. Im Internet findet sich auch der TDL Assembler für CP/M zusammen mit dem Linker.
Das ausführbare Programm wird erzeugt mit den Kommandos "cpm zasm sargon", "cpm linker sargon". Ausgeführt wird das Programm mit "cpm sargon".
Das SARGON Programm wurde auf die Z80 Computer TRS-80 (U.S.A) und Nascom 1 (England) portiert.
Um die Jupiter III Grafik zu sehen wurde der CP/M Player erweitert. Hier ist der Jupiter III Emulator für SARGON und hier ist der Quelltext des Jupiter III Emulator. Das Programm ist in C geschrieben für die Microsoft WinAPI unter Visual C++ 2010 Express.



Bild links: Hayden Books ISBN 0-8104-51554
Bild rechts: AVR-Max 4.8 gegen Jupiter SARGON Level 4. Remis durch Stellungswiederholung. Partie in PGN.

TRS-80 SARGON CHESS, 1978

Der Tandy Radio Shack TRS-80 war 1977 ein erfolgreicher Heimcomputer. Tandy verkaufte 55000 Rechner im ersten Jahr. Das SARGON Programm auf dem TRS-80 benötigte Level 2 BASIC (12KByte ROM). Die Bildschirmauflösung war 64 x 16 Buchstaben oder 128 x 48 Pixel Pseudografik. Sargon kann nicht das Brett drehen und spielt weiss von unten nach oben.
Der TRS-80 Emulator von Matthew Reed wurde in Einstellung "Model 1" verwendet. Der Emulator benötigt das Model 1 ROM und die SARGON CMD Datei.



Bild links: SARGON CHESS Intro.
Bild rechts: Videochess auf Stufe 3 gegen SARGON auf Stufe 1. Sargon gewinnt Material mit einer Springergabel.

Nascom SARGON CHESS, 1978?

In Europa war ab 1977 der Nascom der englischen Firma Nasco ein erfolgreicher Z80 Computer-Bausatz. Blue Label Software Pascal, der Vorläufer von Turbo Pascal, erschien auf dem Nascom. Sargon Chess auf dem Nascom benutzt ein eigenes Zeichensatz-ROM. Dadurch ist die Spielfelddarstellung besser als auf dem TRS-80. Weitere Programme für den Nascom waren Tiny BASIC nach Li-Chen Wang, Microsoft BASIC, Forth und CP/M 2.2.



Bild: Sargon Version 1.3 auf Nascom. Der VNascom Emulator läuft in DOSBox unter MS-Windows.

Spracklen, SARGON II, 1978

Bei der ACM US Computer Chess Championship im Jahr 1978 belegte Sargon II den 5. Platz von 12 Plätzen. Ein Mikrocomputer-Programm besiegte Großrechner-Programme wie DUCHESS für IBM S/370 MVS, eine Neuigkeit im Computerschach. Die TRS-80 Version von SARGON II erschien 1979.

Frey, Atkin, Chess 0.5, 1978

In der Zeitschrift Byte wurde zwischen Oktober 1978 und Januar 1979 in der Artikelserie "Creating a Chess Player" von den Autoren Peter W. Frey und Larry R. Atkin ein Schachprogramm in der Programmiersprache Pascal vorgestellt. Larry Atkin war einer der Programmierer von CHESS, einem sehr erfolgreichen Schachprogramm für Großrechner. Der Quelltext wurde von Scott A. Moore von CDC6000 Pascal nach GNU Pascal umgestellt. Mit Hilfe von Dev+GNU Pascal, einer GNU Pascal Programmierumgebung für MS-Windows von Abimbola Olowofoyeku und anderen, lässt sich dieser Chess 0.5 Quelltext in dieses Chess 0.5 MS-Windows Programm übersetzen.
Das Chess 0.5 Programm benutzt die klassische Schachnotation. Der weisse Zug E2E4 wird eingeben als P-K4. Der Anwortzug E7E5 von Schwarz wird eingeben als P-K4. Bei beiden Zügen wurde der Königsbauer auf das vierte Feld vor den König gestellt, deshalb die gleiche Schreibweise.

QR8
QN8
QB8
 Q8
 K8
KB8
KN8
KR8
QR7
QN7
QB7
 Q7
 K7
KB7
KN7
KR7
QR6
QN6
QB6
 Q6
 K6
KB6
KN6
KR6
QR5
QN5
QB5
 Q5
 K5
KB5
KN5
KR5
QR4
QN4
QB4
 Q4
 K4
KB4
KN4
KR4
QR3
QN3
QB3
 Q3
 K3
KB3
KN3
KR3
QR2
QN2
QB2
 Q2
 K2
KB2
KN2
KR2
QR1
QN1
QB1
 Q1
 K1
KB1
KN1
KR1

Bild: Feldbezeichnung in klassischer Schachnotation für Weiss. Das Feld Q1 von Weiss ist das Feld Q8 für Schwarz.

Das Programm Chess 0.5 versteht einige Kommandos. Hier ist die komplette Kommadoliste.

LE FNODEL 1000
Spielstärke einstellen auf 1000.
PR
Spielfeld ausgeben
IN
Neues Spiel
EN
Programm beenden
GO
Einen Zug ausführen
GO 2
Zwei Züge ausführen (einen für Weiss, einen für Schwarz)

Eine Partie zwischen Chess 0.5 und Micro-Max 4.8 endet nachdem Chess 0.5 den Zug Läufer f8 schlägt Bauer b4 nicht annimmt. Wahrscheinlich haben sich bei der Portierung von CDC Pascal auf GNU Pascal einige Fehler eingeschlichen. Immerhin arbeitet Chess 0.5 mit Bitboards.



Bild links: Chess 0.5 Anzeige. Bild rechts: WinBoard Darstellung der Partie.

Central Data 2650 Chess, 1978?

Die Firma Central Data Corporation aus Champaign, IL in U.S.A. produzierte ab 1977 den Central Data 2650 Computer. Mit einer Anzeige von 80 Zeichen in 16 Zeilen war dieser Computer gut ausgestattet. Das Central Data Chess sieht sehr nach Sargon Chess aus.



Bild links: Central Data Chess Startbildschirm unter WinArcadia.
Bild rechts: Nascom Sargon Stufe 1 gegen Central Data Chess Stufe 3 mit Gewinn für Schwarz.

Novag Chess Champion Mk I und Mk II, 1978, 1979

Im Vergleich zu SARGON ist der Schachcomputer Novag Mk I ein Rückschritt. Mk I spielt nur schwarz. Rochade und En Passant lassen sich nur umständig mit der MD (Mehr Daten) Taste eingeben. Der Mk I hat eine F8 CPU, 2KByte ROM und 256Bytes RAM. Im Mk I Handbuch steht: "Vergessen Sie jedoch nicht, daß es sich beim CHESS CHAMPION MK I um einen programmierten Computer handelt, der dem menschlichen Geist in dem Maße überlegen ist, je mehr Spielfiguren, d.h. Spielvariationen zur Auswahl stehen". Der Mk I prüft die eingegebenen Züge nicht auf Gültigkeit: "Sollten Sie jedoch einen verbotenen oder unmöglichen Zug eingeben, wird der Computer diesen akzeptieren". Die Endspielschwäche des Mk I wird übrigens so verklärt: "daß Sie in einer eindeutigen Endspielsituation zu Ihren Ungunsten .. das Spiel aufgeben sollten .. Im anderen Fall wird .. das Spiel unnötig in die Länge gezogen, da der CHESS CHAMPION MK I nicht angreifen wird, sondern abwartet, bis Sie sich selbst in eine Position bringen, die ein "Schach-Matt" zur unmittelbaren Folge hat." Die Bedienungsanleitung ist schon irreführend.
Übrigens wurde JS&A, der U.S.A. Distributor des Mk I, von Data Cash Systems, dem Hersteller des CompuChess Schachcomputer, verklagt. Der Mk I hat den gleichen ROM-Inhalt wie der ältere CompuChess von 1977, siehe Flaum, J. Der CompuChess und somit auch der Mk I enthält ein Programm von "D. B. Goodrich and Associates".
Der Schachcomputer Mk II hat als Programm Microchess Version 1.5 von Peter Jennings in 5KByte ROM mit 6504 CPU. Laut Schach-Computer.info enthält der Mk II das gleiche Programm wie der Commodore Chessmate.



Bild links: Chess Champion Mk I (Foto von Schachcomputer.info)
Bild rechts Chess Champion MK II, eine Bauform (Foto von Schachcomputer.info)

Selbstbau Schachcomputer SHAH

Der Chess Champion Mk I und Mk II von 1978/1979 und der Mephisto I von 1980 sind für mich typische Schachcomputer: ein Plastikklotz mit wenigen Tasten und einer bescheidenen 7-Segment Anzeige. Nach Eingabe von E2E4 erscheint E7E5.
Von Harm-Geert Müller gibt es das Schachprogramm Micro-Max. Dieses Programm besteht aus weniger als 150 Quelltextzeilen der Programmiersprache C bzw. weniger als 2000 ASCII Zeichen. uMax 4.8 wurde von Andre Adrian mit dem WinAVR GCC Compiler auf den Atmel AVR 8-Bit Mikrocontroller portiert. Der AVR hat eine Harvard RISC Architektur mit 16-Bit Opcodes. Der ATMega88 hat 8KByte ROM, 1KByte RAM und ein schmalles 28poliges DIP Gehäuse. Der ATMega644 hat 64KByte ROM, 4KByte RAM und ein normales 40poliges DIP Gehäuse. Taktfrequenz mit eingebautem RC Oszillator ist maximal 8MHz. Spannungsversorgung erfolgt mit 2 Mignon Batterien. Die Stromaufnahme mit ATMega88V ist unter 20mA. Die Schaltung funktioniert noch bei 1.9V.
AVR Max läuft auch im AVR Studio Simulator. Der ATMega644 mit 8Mhz Takt benötigt laut Simulator 0.6s für den Eröffnungszug c2-c4. Dafür hat der Simulator fast 50 Sekunden lang gerechnet.
Pro Halbzug (ply) benötigt AVR Max 108 Byte auf dem Stack. Ein Stack für 30 Halbzüge benötigt 3240 Bytes. Das Schachfeld in 0x88 Form benötigt 129 Byte RAM. Bei einem ATMega644 mit 4KByte RAM bleiben noch 727 Bytes für andere Variablen. Hier ist der C Quelltext von AVR Max für ATMega644. Das mit Option -O2 kompilierte Programm ist 3192Bytes lang.
Der Entwurf sieht 8 Tasten A1 bis H8 für die Zugeingabe vor. Die rechten 3 Tasten haben die Aufgaben FN Sonderfunktionen aufrufen (rot), CL Zugeingabe löschen (gelb) und GO Zug ausführen (grün).



Bild links: Mephisto I (Foto von Schachcomputer.info).
Bild rechts: Entwurf Selbstbau Schachcomputer mit ATMega88V Mikrocontroller und LED 7-Segmentanzeigen.




Bild: AVR Max Schaltplan. Der ATMega88V benutzt den internen 8MHz RC-Oszillator. Die MCU wird über den In-System-Programming Stecker SV1 programmiert. Ich verwende den AVRISP mkII Programmer mit USB Anschluß unter Microsoft Vista. Die 7-Segment Anzeigen mit gemeinsamer Anode werden im Multiplex angesteuert. Die Low-active Multiplex Lines PC0 bis PC3 werden auch für die Matrixtastatur benutzt. Die Multiplex Lines werden als Open Collector betrieben. Werden mehrere Tasten gleichzeitig gedrückt gibt es keinen Kurzschluß.



Bild: AVR Max Layout. Platinengrösse 100mm x 80mm. Layout von Hand erstellt mit Eagle 5.3 Freeware-Version.



Bild: AVR Max Prototype. Die Lochstreifenplatine passt in das TEKBOX Gehäuse mit Batteriefach (16 x 9.4 x 3.15 cm3).

Die Zeitschrift Elektor hat eine Platine für AVR-Max entwickelt. Der Elektor Schachzwerg wird in Ausgabe 2009/6 vorgestellt. Hier die professionelle Verpackung von Antoine Authier. Vielen Dank an Erich Krempelsauer, Jerry Jacobs, Antoine Authier, Hedwig Hennekens und andere von Elektor und an Wolfgang Rudolph und andere von ComputerClub 2. Das Elektor ATM18 Board mit 2-Draht LCD Anzeige und einer 11 Tasten Matrix Tastatur ergibt einen Luxus Schachzwerg mit ausführlicher Benutzerführung durch die 20 Zeichen mal 4 Zeilen LCD Anzeige.



Bild: Elektor Schachzwerg im Bopla Gehäuse BS 400 F-7024. Einfach schick!

Bedienungsanleitung SHAH Schachcomputer

Wir beglückwünschen Sie zum Bau des SHAH Schachcomputers, die neueste Entwicklung unseres Hauses. SHAH zeichnet sich durch seinen nostalgischen Charme aus, besonders bemerkenswert ist die Spannungsversorgung mit zwei Mignon Batterien. Das Schachprogramm ist Micro-Max 4.8 von Harm-Geert Müller in einer Portierung von Andre Adrian.

Um die Fähigkeiten Ihres neuen SHAH Schachcomputers voll auszuschöpfen, empfehlen wir Ihnen, die nachfolgende Gebrauchsanweisung sorgfältig durchzulesen.

Schachbrett aufstellen, SHAH einschalten. Die Anzeige SHAH erscheint. Die 'CL' Taste drücken, die Anzeige wird dunkel, anschließend Züge nach dem international bekannten Koordinaten-System eingeben, z.B. E2 E4.

Nach Eingabe des Zuges zweimal die Taste 'Go' drücken, damit der Computer den Zug registriert. Bei Fehleingabe einen neuen Zug eingeben. Ein ungültiger Zug wird mit der Anzeige ZUG abgelehnt.

Nach Eingabe Ihres Zuges verarbeitet der Computer Ihre Informationen. Solange die Anzeige blinkt zeigt der Computer den Kandidatenzug. Der endgültige Zug wird ohne Blinken dargestellt.

Wird ein König Matt gesetzt erscheint MATT.

Damit der Computer weiss spielt nach dem Einschalten die 'CL' Taste und danach die 'Go' Taste drücken.

Der Computer führt einen Zug aus wenn die 'Go' Taste gedrückt wird.

Tipp: Wenn die Stellung schlecht für den Menschen steht, 'Go' drücken und den Computer ab sofort die schwächere Seite spielen lassen. Der Philosoph Hubert Dreyfus hat nämlich festgestellt das Computer nicht Schach spielen können, man aber gegen Computer im Schachspiel verlieren kann.

Der SHAH Schachcomputer hat keine Eröffnungsbibliothek. Sie können aber eine beliebige Eröffnung eingeben indem Sie die weissen und schwarzen Züge eingeben. Nach jeder Zugeingabe nur einmal Taste 'Go' drücken. Eine übliche Eröffnung ist E2E4, E7E5, G1F3, B8C6.

Über die 'FN' Taste erreichen Sie Zusatzfunktionen. 'FN' und 1 startet ein neues Spiel. 'FN' und 2 läßt die Spielstufe einstellen. Mit Taste 'Go' wird die Spielstufen Einstellung verlassen. 'FN' und 3 schaltet die Anzeige der Hauptvariante (Kandidatenzug) ein oder aus.

Die Taste 'CL' löscht die Eingabe.

Entwicklungsziel für SHAH ist eine Elo-Zahl von 1200-1399 unter Turnierbedenkzeit (120 Minuten für die ersten 40 Züge). Das entspricht Amateur, Klasse D, durchschnittlicher Hobbyspieler. Spielstufe 1 ist Blitzschach mit 7 Sekunden pro Zug, Stufe 5 ist Aktivschach mit 30 Sekunden und Spielstufe 8 ist Turnier mit 3 Minuten. Nach dem Einschalten spielt SHAH auf Spielstufe 3.

Software für SHAH Schachcomputer

Der Negamax Suchalgorithmus in Mikro-Max ist rekursiv definiert. Die Negamax Funktion ruft sich selbst auf bis eine Abbruchbedingung wie maximale Suchtiefe erreicht ist. Eine Rekursion läßt sich in eine Iteration umwandelt. Aus dem Selbstaufruf der Funktion wird eine Schleife über die Funktion. Für einfache Funktionen wie Fakultät oder Fibonacci Reihe ist die Umwandlung Rekursion zu Iteration trivial. Der Negamax Algorithmus läßt sich nach dem gleichen Verfahren in eine iterative Version umschreiben. Diese Lösung benötigt nur noch 34Bytes pro Halbzug (ply). Damit läßt sich mit einem 1Kbyte RAM eine Suchtiefe von 20 Halbzügen erreichen. Der ROM Speicherbedarf wächst nicht. Ob die Adressierung auf den Stack-Framepointer bezogen wird oder auf den Stack-Array-Pointer ist ungefähr gleich aufwendig.
Hier ist der C Quelltext von AVR Max 4.8 für den SHAH Schachcomputer, und hier die Hex Datei. Hier ist C Quelltext AVR Max mit xboard Schnittstelle und als MS-Windows Programmdatei. Die Exe Datei ist 10KByte gross.
Die MS-Windows Programmdatei gibt es auch zusammen mit WinBoard in einer selbst-extrahierenden Exe Datei  avrmax_48_winboard.exe. Auspacken mit Doppel-Klick. Das Unterverzeichnis avrmax_48_winboard wird erzeugt. In diesem Unterverzeichnis Doppel-Klick auf das winboard.exe Programm. Im "WinBoard Startup" Popup die Auswahl "Play against a chess engine.." anklicken. Im Winboard Fenster kann Weiss den ersten Zug ausführen indem die Figur mit der Maus und Links-Klick angefasst wird. AVR-Max versteht auch die Zeitkontrolle. Eine Blitzschachpartie dauert 5 Minuten, eine Aktivschach Partie hat 40 Züge in 20 Minuten oder 30 Minuten für die Partie.
Weitere Informationen zu Winboard gibt es auf Tim Mann's Chess Pages.



Bild links: WinBoard Startup Popup.
Bild rechts: WinBoard in voller Schönheit. Die ganzen Schachdiagramme auf dieser Seite sind WinBoard screen shots.

Mit dieser RAM schonenden Mikro-Max Version sollte sich auch aus dem AVR Butterfly ein Schachcomputer bauen lassen. Der Butterflay hat eine LCD Anzeige und einen 4-Wege Joystick. Über links-rechts läßt sich die Eingabeposition anwählen. Über hoch-runter läßt sich die Reihe a bis h oder die Spalte 1 bis 8 auswählen. Mit Druck auf den Joystick wird der Zug ausgeführt. Programmiert wird der Butterfly über die RS232 Schnittstelle ohne spezielles Programmiergerät.



Bild links: AVR-Max 1.61 verliert im 26. Zug gegen Micro-Max 4.8. Partie in PGN.
Bild mitte: AVR-Max 4.81 gewinnt im 20. Zug gegen GNU Chess 5 in Einstellung gesamte Bedenkzeit 10 Sekunden. Partie in PGN.
Bild rechts: AVR Butterfly. In Deutschland z.B. zu kaufen über www.mikrocontroller.net Shop.

Atari VCS Video Chess, 1979

Das Atari Video Computer System Video Chess läuft mit 4KByte ROM und 128Byte RAM. Das Programm kennt alle Schachregeln. Mit Hilfe des VCS Emulators Stella oder MESS läßt sich Video Chess heute noch spielen. Der Video Chess Prototype von 1978 heißt Computer Chess. Beim Prototype erfolgt die Steuerung über den rechten Joystick. Wahrscheinlich wurde VCS Video Chess und Atari 400 Computer Chess von den gleichen Personen entwickelt.
Die VCS hat keinen Bildspeicher. Die CPU muss das Bild 60 mal pro Sekunde neu erzeugen. Diese Bilderzeugung wird während der Berechnung des Computerzuges abgeschaltet. Atari 2600 ist Atari VCS in einem neueren Gehäuse.



Bild links: Atari VCS Computer Chess (Prototype). Die Läufer erinnern an Raketen.
Bild mitte: Partie Crafty 19.3 gegen Video Chess 1:0. Die Partie in PGN. Video Chess spielte auf Stufe 3.
Bild rechts: Partie Video Chess gegen Crafty 19.3 0:1. Die Partie in PGN. Video Chess spielt weiss von oben nach unten.

Der Emulator benötigt das Video Chess ROM. Die Bedienung ist einfach. Mit dem "Right Difficulty Switch" wird die vom Computer gespielte Farbe ausgewählt. Mit dem "Left Difficulty Switch" kann zwischen Eingabe Schachproblem (A) und Spiel (B) umgeschaltet werden. Mit der Taste 1 wird die Spielstärke ausgewählt. Für die Zug-Eingabe ist zuerst der Cursor auf das Von-Feld zu bewegen, dann die Strg Taste drücken, Cursor auf das Ziel-Feld bewegen, dann wieder Strg Taste drücken. Bei AtariAge gibt es das Video Chess Manual.
Das Schachprogramm wurde von Larry Wagner mit Unterstützung des internationalen Schach Meister Julio Kaplan entwickelt. Die Grafik stammt von Bob Whitehead. Laut Überlieferung war die Entwicklungszeit für das Schachprogramm zwei Jahre und die Entwicklungszeit für die "venetian blinds" graphische Darstellung war zwei Tage.

Atari 400/800 Computer Chess, 1979

Der Atari 400 (Folientastatur) und der Atari 800 (normale Tastatur) Computer haben eine Bildschirmauflösung von maximal 320x192 Pixel. Die 6502 CPU arbeitet mit 1.8MHz. Die gute Grafik und die schnelle CPU übertrafen die Leistung von TRS-80, Commodore PET und Apple ][. Die Computer erschienen Dezember 1979, siehe Atari 8-Bit Historie. Ein Atari 400/800 Emulator unter Linux und MS-Windows ist Atari++ von Thomas Richter. Die Computer Chess Cartridge enthält 8KByte ROM. Im Atari 400/800 sind minimal 8KByte RAM enthalten.
Die Bedienung erfolgt im Emulator mit den Tasten des Zehnerblocks. Mit 8, 4, 6, 2 wird der Cursor bewegt, mit 0 wird eine Figur aufgenommen oder abgesetzt. Taste F2 wechselt die Farbe. Mit F3 wird die Spielstufe eingestellt.


Bild links: Atari 400/800 Computer Chess mit 160x192 Pixel Auflösung in 4 Farben. Irgendwie erinnert der Springer an ein Krokodil.
Bild rechts: Micro-Max 4.8 gewinnt im 34. Zug gegen Atari 400 Computer Chess Stufe 1. Partie in PGN.

Fairchild Channel F/Saba Videoplay Schach, 1979?

Das Fairchild Channel F (ursprünglicher Name war Video Entertainment System oder VES) wurde in Deutschland als Saba Videoplay vertrieben. Das Saba Videoplay Schach Modul enthält 6KByte ROM und 2KByte RAM sowie einen MK3853 Memory Support Chip laut Sean Riddle und kennt alle Schachregeln. Videoplay Schach kann nicht das Brett drehen und spielt weiss von unten nach oben.
Die Channel F wurde 1976 ausgeliefert, Atari VCS 2600 erst 1977. Die Channel F verwaltet einen zweidimensionalen Videospeicher, die Atari VCS verwaltet nur Sprites. Trotzdem sieht die VCS Grafik mit 176 x 223 Pixel Auflösung deutlich besser als bei der Channel F mit 102 x 58. Während der Berechnung des Computerzuges bleibt die Bildschirmanzeige erhalten, dies ist ein Vorteil der Channel F Lösung.
Das VESWiki enthält Hardware Info, den FVE100 Schaltplan vom 22.Jun.1976 und Disassembler Listing der Spielprogramme. Die MK3850 CPU hatte nur einen Program Counter Buffer PC1, keinen echten Stackpointer. Trotzdem haben einige Fans neue Programme wie Pac-Man und Tetris für die VES geschrieben.



Bild links: Saba Videoplay Schach läuft im Emulator MESS.
Bild mitte: Eröffnung (Anfänger gegen Saba Videoplay Schach).
Bild rechts: Das Ende ist nahe.

Der Emulator MESS benötigt das Channel F BIOS ROM und das Schach ROM. Im Intro Bildschirm die Taste Y für Computer spielt schwarz oder X für Computer spielt weiss, dann Taste 1 drücken für Start. Der Zug a1-a1 wählt Spielstufe 1, Zug b1-b1 wählt Spielstufe 2 usw. Für die Zug-Eingabe ist zuerst der Cursor auf das Von-Feld zu bewegen, dann Taste A drücken, Cursor auf das Ziel-Feld bewegen, nochmal Taste A und zuletzt Taste Q drücken. Ist bei der Zugeingabe das Von-Feld gleich dem Nach-Feld führt Saba Schach zuerst einen Zug für den Menschen und dann für den Computer aus. Mit Taste S anstelle von Taste Q wird die Zugeingabe abgebrochen.
Anstelle von Taste 1 und Spielstufe Auswahl kann man Taste C drücken. Das wählt die schwächste Spielstufe aus. Die Info über Spielstufen stammt von "Ein Freund".

TRS-80 SARGON-II, 1979

Im Jahr 1979 erschien Sargon 2. Die Grafik auf dem TRS-80 ist keine Verbesserung gegenüber der SARGON CHESS Grafik. Die Sargon Programme des Ehepaars Spracklen gewannen in Fidelity Schachcomputern von 1980 bis 1984 viermal die World Microcomputer Chess Championship.
Der TRS-80 Emulator benötigt das Model 1 ROM und die SARGON2 CMD Datei.



Bild links: SARGON-II Intro auf TRS-80 Model 1.
Bild rechts: SARGON2 auf Stufe 4 gegen Crafty 19.3 endet 0:1. Die Partie in PGN.

Texas Instruments TI-99/4 Video Chess, 1980

Der TI-99/4 Computer enthält die 16-Bit CPU TMS9900. Grafikauflösung ist 256x192 Pixel. Zusammen mit 16KByte RAM sollte der TI-99/4 ein leistungsfähiger Computer seiner Zeit sein. Leider kann die CPU das Video RAM nicht direkt ansprechen. Im direkten Zugriff sind nur 256Byte RAM. Die TI-99/4 Cartridges enthalten üblicherweise GROM ICs. Diese ROM Speicher können nicht direkt adressiert werden. Die leistungsfähige CPU wird durch Video-RAM und GROM ausgebremst, siehe TI99 History. Am Markt wurde TI von Commodore mit den Modellen VIC-20 und C64 ausgebremst. Für einen Systementwickler wie mich ist es schwer nachzuvollziehen wie das TI Management den TI Entwicklern ein solches Systemdesign genehmigen konnte. Einsatz von Patenten und "non-disclosure agreements" bei der GPL (Graphics Programming Language) machten vielleicht die TI Juristen froh, aber sonst niemanden.
Beim Classic99 Emulator ist Video Chess dabei. Die Zeitkontrolle von Video Chess ist vorbildlich.



Bild links: TI-99/4 animierte Video Chess Intro. Die ersten TI-99/4 gab es erst ab Anfang 1980 zu kaufen.
Bild rechts: TI-99/4 Video Chess. Die Figuren sehen futuristisch aus.

Mattel Intellivision, USCF Chess, 1981

Der Erfolg von Atari VCS bewog Mattel 1980 die Intellivision (INTV) herauszubringen. CPU ist die 16-Bit General Instruments CP1610 mit 0.9MHz Takt. Die Grafikauflösung ist 160 x 196. Das USCF Chess Module hatte zusätzliches RAM um die Spielleistung zu verbessern. Mit Schachuhr und Darstellung der geschlagenen Figuren ist USCF Chess benutzerfreundlich. USCF Chess kann nicht das Brett drehen und spielt weiss von unten nach oben. Der Sound Chip AY-3-8914 ist dreistimmig. Wird USCF Chess besiegt ertönt Applaus und Pfiffe. Es gibt unter anderen die Emulatoren Nostalgia und Bliss für die INTV.



Bild links: Intellivison Chess Intro.
Bild rechts: Micro-Max 4.8 hat Intellivison Chess geschlagen.

Veteranen Emulator Turnier

Im Turnier treten an Chess Champion Mk I und Mk II, Sargon und Sargon II auf TRS80, Computer Chess auf Atari 400, Video Chess auf Atari 2600, Saba Videoplay Schach auf Channel F, Video Chess auf TI-99/4 und USCF Chess auf Mattel Intellivision. Gegner ist immer SHAH AVR-Max 4.8 von Harm-Geert Müller/Andre Adrian auf Stufe 5 (30 Sekunden pro Zug, Aktivschach). Mikro-Max besteht aus weniger als 200 Zeilen C und hat keine Eröffungsbibliothek und keine Endspieldatenbank. Von Nick "spacious_mind" gibt es ein größeres Veteranen Turnier 1980 World Micro Computer Chess Championship Revisited mit kommentierten Partien. Sehr lesenswert!



Bild links: Atari 400 Computer Chess auf Stufe 2 hält Remis durch Stellungswiederholung. Partie in PGN.
Bild mitte: Atari VCS Video Chess auf Stufe 4 hält Remis durch Stellungswiederholung. Partie in PGN.
Bild rechts: TI-99/4 Video Chess auf Stufe 30 Sekunden hält Remis durch Stellungswiederholung. Partie in PGN.



Bild links: TRS80 SargonII auf Stufe 2 hält Remis durch Stellungswiederholung. Partie in PGN.
Bild mitte: Chess Champion Mk II auf Stufe 7 hält Remis durch Stellungswiederholung. Partie in PGN.
Bild rechts: TRS80 Sargon auf Stufe 2 verliert im 36. Zug. Partie in PGN.



Bild links: Intellivison Chess auf Stufe 2 verliert im 35. im Zug durch Zeitüberschreitung (eingefroren). Partie in PGN.
Bild mitte: Chess Champion Mk I auf Stufe 3 verliert im 33. Zug. Mk I hat 985 Elo im Aktivschach. Partie in PGN.
Bild rechts: ChannelF Saba Schach auf Stufe 2 verliert im 32. Zug. Partie in PGN.

Turnierergebnis für AVR-Max: 4 gewonnen, 5 Remis, 0 verloren. Die Boliden TI-99/4 mit 3MHz CPU und 16KByte RAM und Atari 400/800 mit 1.8MHz CPU und 8KByte RAM zeigen dem AVR-Max mit 8MHz CPU und 1KByte RAM Remis. Erstaunlich gut hält sich Atari VCS mit 1.2MHz CPU und 128Byte RAM. Aufgrund der Zeitüberschreitung hat Atari VCS eigentlich verloren, aber ein solcher Oldtimer wird nachsichtig behandelt. Die Schachintelligenz von SargonII kompensiert die schwache CPU. Die ältesten Programme Sargon, Chess Champion Mk I und Saba Videoplay Schach mit den auch schwächsten CPUs zeigen die schlechteste Leistung. Soweit so verständlich. Das Ergebnis von Intellivision enttäuscht und zeigt, neuere Schachprogramme sind nicht immer besser als ältere.
Das AVR-Max auch verlieren kann zeigt die Partie gegen Mephisto Rebel5 von Ed Schröder aus dem Jahr 1986. Die CPU hat 4.9MHz mit 32KByte ROM und 8KByte RAM. Haushoch verliert SHAH (schwarz) gegen JB, einen Schachcomputer Sammler. AVR-Max ist gegen die h-Bauer Attacke machtlos.



Bild links: Mephisto Rebell 5 auf Stufe 3 gewinnt im 61. Zug. Rebel hat 1875 Elo im Computer-Aktivschach. Partie in PGN.
Bild mitte: JB schlägt AVR-Max Stufe 5 in 16 Zügen. Partie in PGN. JB besiegt Mephisto MM I in 17 Zügen.
ohne Bild: JB schlägt AVR-Max Stufe 8 in 24 Zügen. Partie in PGN. Der Mephisto 2 wird von JB nach 26 Zügen besiegt.

Das JB System

Der französische Schachspieler JB eröffnet mit 1.d4 2.Sc3 3.Lf4 oder wenn nötig 1.d4 2.Sc3 3.a3 4.Lf4. Diese Eröffung hat den ECO-Code D00 oder nach Zugumstellung D02. Wie die Partien von JB gegen Schachcomputer der 2100 Elo Klasse wie Mephisto Master Chess zeigen ist diese Eröffnung konkurrenzfähig, wenigstens für Spiele unterhalb der Schach Weltelite. Der Novag Turquoise hat in seiner 8900 Halbzüge Eröffnungsbibliothek 3.Lf4 c5, 4.e3 a6. Nach dem Druck auf c7 mit Drohung Springergabel auf Turm a8 und König folgt bei JB der zweite Angriff mit dem h-Bauern und Opfer auf g7. In der dritten Phase der Partie verwendet JB oft die lange Rochade um über die dann offene h-Linie beide Türme ins Spiel zu bringen. Zu dieser Zeit ist im Idealfall ein schwarzer Turm noch in Grundstellung auf a8 und der andere Turm steht wegen der kurzen Rochade hinter dem König wenn der h-Linie Angriff rollt. Die Partien von JB gegen Schachcomputer sind wirklich nicht langweilig. JB opfert und gewinnt!
Da die Dame den d-Bauern deckt ist Sf6 im zweiten Zug nicht so notwendig wie der Springerzug in der spiegelbildlichen italienischen Partie 1.e4 e5, 2.Sf3 Sc6, 3.Lc4. Der Novag Sapphire 2 spielt z.B.: 1.d4 e6, 2.Sc3 d5, 3.Lf4 Ld6, 4.Lxd6 Dxd6, 5.e3 Sf6, 6.Ld3 Sbd7, 7.Sf3 c5, 8.h4. Der Novag Star Sapphire spielt ähnlich 1.d4 e6, 2.Sc3 d5, 3.Lf4 Ld6, 4.Dd2 Sf6, 5.Sb5 Se4, 6.Dc1 g5?, 7.Lxd6 cxd6, 8.e3 Da5+, 9.c3 Ld7, 10.Sa3 O-O, 11.f3 Sf6, 12.h4.

ECO-Code
Hauptreihen
Name
D00 1.d4 d5, 2.Sc3 Sf6, 3.Sf3 Damenbauernspiel
D02 1.d4 d5, 2.Sf3 Sf6, 3.Lf4 Damenbauernspiel

Hier einige Partien JB gegen Schachcomputer nach 1.d4 d5, 2.Sc3 Sf6 bis zum Beginn des h-Bauer Angriffs:

Schachcomputer
Fortsetzung
Novag Citrine 3.Lf4 c5, 4.e3 a6, 5.Sf3 e6, 6.a3 Le7, 7.Ld3 b6, 8.h4 O-O
Novag Ruby 3.Lf4 c5, 4.e3 a6, 5.Sf3 Db6, 6.Tb1 e6, 7.Ld3 cxd4, 8.exd4 Lb4, 9.h4
Novag Emerald Classic 3.Lf4 c5, 4.e3 a6, 5.Sf3 Db6, 6.Sa4 Da5, 7.c3 cxd4, 8.exd4 e6, 9.b4 Dd8, 10.Ld3 Le7, 11.h4
Novag Turquoise 3.Lf4 c5, 4.e3 a6, 5.Ld3 cxd4, 6.exd4 Db6, 7.Tb1 e6, 8.a3 Sc6, 9.Sf3 Ld7, 10.Le2 Le7, 11.b4 O-O, 12.h4
Excalibur Phantom Force 3.Lf4 e6, 4.a3 Ld6, 5.Lxd6 cxd6, 6.e3 O-O, 7.Sf3 Sc6, 8.Le2 e5, 9.h4
Novag Zircon II
3.Lf4 e6, 4.a3 Ld6, 5.Lxd6 cxd6, 6.e3 O-O, 7.Ld3 Db6, 8.Sf3 e5, 9.Le2 Lf5, 10.Tb1 Sbd7, 11.h4
Mephisto MM VI 3.Lf4 e6, 4.a3 Ld6, 5.Lxd6 Dxd6, 6.e3 c5, 7.Sf3 cxd4, 8.exd4 O-O, 9.Ld3 b6, 10.h4
Saitek Bravo
3.Lf4 e6, 4.a3 Ld6, 5.Lxd6 Dxd6, 6.e3 Db6, 7.Tb1 O-O, 8.Ld3 Sbd7, 9.Sf3 c5, 10.h4
Mephisto Master Chess 3.Lf4 Lf5, 4.e3 e6, 5.a3 Le7, 6.Ld3 Lxd3, 7.Dxd3 O-O, 8.Sf3 c5, 9.h4
Excalibur Alexandra 3.Lf4 Lf5, 4.e3 e6, 5.a3 Le7, 6.Sf3 O-O, 7.Ld3 Se4, 8.h4
Novag Sapphire
3.Lf4 c5, 4.Sf3 Se4, 5.Dd3 Da5, 6.Db5 Dxb5, 7.Sxb5 Sa6, 8.e3 e6, 9.Ld3 Le7, 10.Se5 g5, 11.Lg3 O-O, 12.f3 Sxg3, 13.hxg3
Mephisto Magellan
3.Lf4 g6, 4.Sb5 Sa6, 5.e3 c6, 6.Sc3 Db6, 7.b3 Lf5, 8.a3 Lg7, 9.Sf3 Sh5, 10.Lg5 f6, 11.Lh4 e5, 12.Le2 O-O, 13.h3

Verbesserungen AVR-Max Programm

Das AVR-Max 4.8 Programm belegt 4968 Bytes von 8192 Bytes im ATMega88V. Die freien Bytes lassen sich für Programmerweiterungen nutzen.
Eine naheliegende Erweiterung ist die Stellungseingabe. Für Matt-in-N-Zügen Aufgaben oder für die "findet der Computer den besten Zug in einer (künstlichen) Stellung" Tests der Schachcomputer Journalisten und Fans.
Mehr Komfort für den menschlichen Spieler bieten die Funktionen Zug zurücknehmen (take back) und Zug vorschlagen (hint).
Dem Programm fehlt noch Kenntnis über Remis nach dreifacher Wiederholung der Stellung und Remis nach 50 Zügen ohne Bauern-Zug oder Figur schlagen.
Die folgenden Erweiterungen sollen die Spielstärke steigern. Von Ken Thompson stammt die Erkenntnis, daß die Stärke um 200 Elo-Punkte ansteigt wenn die Suche einen Halbzug tiefer geht. Für Belle hat Thompson bei 4 Halbzügen eine Leistung von 1235 Punkten und bei 5 Halbzügen von 1570 bestimmt. Pro Halbzug steigt der Rechenaufwand um den Faktor 6.

Kontrolle der Zentralfelder

Das Kotok Schachprogramm von 1962 verfügte schon über einen "center control evaluator". Diese Positions-Bewertungsfunktion vergibt für die Zentralfelder c3 bis f6 einen Bonus. Die Tabelle aus der Kotok Thesis lenkt die Figuren von Weiss in Richtung Damenflügel. Diese Tabelle empfiehlt wenn Schwarz die lange Rochade durchgeführt hat.

8    8    4    4
4    8    8    4
2    4    4    2
1    1    1    1

Das AVR-Max Programm benutzt nur eine Tabelle für den Positionsbonus. Sinnvoll dürften unterschiedliche Tabellen für Weiss und Schwarz sein. Der grösste Bonus wird für Felder in der Nähe des gegnerischen Königs vergeben.

Zug Sortierung

Alpha-Beta Beschneidung funktioniert am besten wenn die Züge nach der Qualität sortiert sind. Züge die den König ins Schach setzen haben die beste Qualität. Dann folgen die Schlagzüge. Je größer der Materialunterschied zwischen schlagender Figur und geschlagener Figur umso besser. Bauer schlägt Dame ist besser als Dame schlägt Dame - und wird meistens im nächsten Zug selbst geschlagen. Bauernumwandlungen sind seltene, aber gute Züge. Bauernzüge von der sechsten Reihe zur siebten Reihe sind auch schon interessant. Zuletzt folgen die stillen Züge. Der "inverse Zug Generator" kann für die Zug Sortierung benutzt werden. Zuerst wird die Schach Erkennung durchgeführt, diesmal aber als Angriff. Züge die den König in Schach setzen werden in der Baumsuche auf Matt oder Widerlegung untersucht. Im zweiten Schritt werden die gegnerischen Figuren auf dem Brett gesucht. Der "inverse Zug Generator" sucht Schlagzüge die in der Baumsuche weiterverfolgt werden. Zuletzt sucht der normale Zuggenerator die stillen Züge. Bei der Ruhesuche (quiescent search) werden stille Züge nicht betrachtet.
Üblicherweise werden durch den Zuggenerator alle pseudolegalen Züge erzeugt. Dann werden diese Züge sortiert. Im dritten Schritt wird die Baumsuche ausgeführt. Wegen dem kleinen RAM Speicher kann AVR-Max keine Zugsortierung durchführen. Deshalb werden zwei unterschiedliche Zuggeneratoren benutzt. Der erste Zuggenerator, ein inverser Zuggenerator, findet nur Schlagzüge, der zweite Zuggenerator findet nur stille Züge. Der erste Zuggenerator beginnt mit der Zugsuche auf dem Feld des Königs, dadurch werden zuerst alle Züge welche zu Schachmatt führen erzeugt.

Schach Erkennung

Im AVR-Max Programm erfolgt die "König steht im Schach" Erkennung durch den Zuggenerator. Eine neue Ebene im Suchbaum wird gestartet. Alle Züge werden generiert. Ist mindestens ein Zug dabei der den König schlägt stand der König im Schach. Für die Schach Erkennung alle Züge zu generieren ist aufwändig - aber Quelltext sparend. Die reine Schach Erkennung geht einfacher mit einem "inversen Zug Generator". Dabei beginnt die Zug-Generation nicht vom Start-Feld, sondern vom Ziel-Feld. Das Ziel-Feld ist das Königsfeld. Ausgehend von diesem Feld wird die Bewegung einer "Super-Figur" generiert. Zuerst wird getestet ob im Springer-Abstand ein feindlicher Springer zu finden ist. Dann ob ein feindlicher Bauer einen Schlagzug auf das Königsfeld ausführen kann. Es folgen die Suchstrahlen in vertikaler und horizontaler Richtung für Turm und Dame und in diagonaler Richtung für Läufer und Dame. Findet die "Super-Figur" nur leere Start-Felder, eigene Figuren oder den Spielfeldrand, dann steht der König nicht im Schach. Ob der König im Patt steht bemerkt die Schachmatt-Prüfung nicht.

Eröffnungsbibliothek

Eine Eröffnungsbibliothek hilft dem AVR-Max die ersten Züge schnell und gut auszuführen. Die einfachsten Eröffnungsroutinen folgen einer Zugfolge. Diese Routinen verstehen keine Zugumstellung. Bessere Eröffnungsroutinen gehen von der Position aus und suchen einen Folgezug in der Eröffnungsbibliothek. Die opening-book Position wird üblicherweise in der Hash-table (transposition-table) gespeichert. AVR-Max hat keine Hash-table. Die Suche in der Eröffnungsbibliothek erfolgt durch Ausspielen der Bibliothekszüge auf einen zweiten Spielfeld und Vergleich der beiden Spielfelder. Dadurch werden gleiche Stellungen erkannt die durch Zugumstellung entstanden sind. Der Suchaufwand ist linear mit der Anzahl der Eröffungen in der Bibliothek wenn die aktuelle Stellung im N.ten Zug nur mit den Bibliotheksstellungen im N.ten Zug verglichen werden.
Ein Zug besteht aus zwei Halbzügen. Jeder Halbzug hat ein Von- und ein Nach-Feld. Für die 64 Felder sind 6 Bit nötig. Ein Zug benötigt somit 4*6Bit = 24Bit = 3 Bytes an Speicher. Der Rochade Zug wird durch e1-c1 oder e1-g1 kodiert. Die Ausspiel-Routine muß den Turm-Halbzug hinzufügen. En-Passant Schlagen kann durch Bauer zieht nach rechts oder nach links kodiert werden, z.B. b4-a4. Die Ausspiel-Routine korrigiert den Bauernzug nach b4-a3 und löscht den Bauern auf a4.
Mit einem Präfix-code läßt sich ein Halbzug der Eröffnungsbibliothek in einem Byte speichern. In dem Byte wird der Figur-Index, z.B. a-Turm oder e-Bauer und der Bewegungsvektor abgespeichert. Wenn die Figuren in einem Array (piece list) gespeichert werden dann ist das Ausspielen der Bibliotheks-Züge einfach. Der Präfix-code:

Bitmuster
Figur
Beschreibung
111rrrdd Dame
rrr=3Bit neue Reihe/Spalte/Diagonale, dd=2Bit Richtung
110irrrd Turm
i=welcher Turm, rrr=3Bit neue Reihe/Spalte, d=1Bit Richtung
101irrrd Läufer
i=welcher Läufer, rrr=3Bit neue Diagonale, d=1Bit Richtung
100iiidd Bauer iii=welcher Bauer, dd=2Bit Schlagzug Richtung (normal, e.p.)
0111iiid Bauer iii=welcher Bauer, d=1Bit Richtung (ein Feld, zwei Felder)
0110iddd Springer i=welcher Springer, ddd=3Bit Richtung
01011ddd
König ddd=3Bit Richtung
0101011d
König
d=1Bit kurze, lange Rochade

Natürlich hat das Bitmuster 0 für Richtung beim Turm eine andere Bedeutung als beim Läufer. Die Eröffnungsbibliothek kann im 512Byte grossen EEPROM gespeichert werden.

Material-Baumsuche und Positions-Baumsuche

Interessant ist eine Feststellung von Aske Plaat, dem MTD(f) Vater, die allgemein für Baumsuchen gilt und die mir auch schon aufgefallen ist. Je weniger unterschiedliche Werte die Bewertungsfunktion liefert, umso mehr Knoten werden durch Beschneidung entfernt: "The coarser the grain of eval, the less passes MTD(f) has to make to converge to the minimax value." Eine Bewertungsfunktion die nur die Materialdifferenz liefert erlaubt viele Schnitte bei der Baumsuche. Noch einfacher ist die Bewertung auf gewonnen, verloren oder Remis welche bei Matt-in-N-Zügen Aufgaben genügt. Zur Untersuchung der Leistung der Baumsuche Routinen NegaMax, NegaScout und MTD(f) gibt es das Rahmenprogramm baumsuche.c welche die Bewertungsfunktion durch Zufallszahlen in einem Array simuliert. Der Suchbaum ist immer gleich groß, nur die Anzahl der return Werte der Bewertungsfunktion ist unterschiedlich.

return Werte
NegaMax
NegaScout Reinefeld
NegaScout Wikipedia
MTD(f) ohne Hash
3
9222
9222
9222
9824
30
90224
72515
72592
89035
300
140032
105671
106338
342049

Tabelle: Besuchte End-Knoten in einem Suchbaum mit Tiefe=6, Verzweigung=20.

Für eine schnelle Suche sollte die Baumsuche in zwei Teilen erfolgen. Zuerst wird mit grosser Tiefe eine Baumsuche mit einfacher Bewertungsfunktion aufgerufen. Im Endspiel genügen die Werte für Matt-in-1, Matt-in-2, usw., Gewinn-in-1, Gewinn-in-2, usw. und Remis. Im Mittelspiel sind zusätzlich die Materialdifferenz der return Wert wenn die Suche nicht bis zum Spielende sondern nur bis zu einer ruhigen Position geführt wird.
Wenn die "Material-Baumsuche" einen Gewinner-Zug findet wie Matt-in-N oder Bauer schlägt gedeckte Dame mit +8 Materialgewinn wird natürlich dieser Zug ausgeführt. Beim Eröffnungszug gibt es für Weiss aber 20 Züge die alle die gleiche Materialdifferenz Bewertung von 0 haben. Im Mittelspiel ist es üblich das die Hälfte der Züge die gleiche gute Materialdifferenz Bewertung liefern. Diese 10 bis 15 Züge müssen in einer zweiten Baumsuche mit einer positionellen Bewertungsfunktion untersucht werden. Im einfachsten Fall wird für diese Entwicklungszüge ein static evaluator ohne Baumsuche aufgerufen. Oft muß die Position aber zuerst schlechter werden um dann besser zu werden - das bekannte Problem der lokalen Minima und Maxima. Die positionelle Baumsuche ist ein oder mehrere Halbzüge weniger tief als die Material-Baumsuche. Natürlich muß die positionelle Baumsuche nicht nach Matt suchen - das läßt sich nicht mehr finden.

Hauptvariante Zug Sortierung

Die Halbzüge der Hauptvariante (Principal Variation) beschreiben nach Ansicht des Schachprogrammes das beste Spiel für Weiss und Schwarz. Wenn ein Hauptvarianten Halbzug in einer Position möglich ist, dann wird damit mit guter Wahrscheinlichkeit der Baum beschnitten. Während die Baumsuche läuft werden unterschiedliche Hauptvarianten-Kandidaten angelegt. Auf Ebene 1 gibt es einen 1 Halbzug langen Kandidaten, auf Ebene 2 gibt es einen 2 Halbzug langen Kandidaten usw. Speicherplatzsparend werden die Hauptvarianten Kandidaten in einem eindimensionalen Array abgelegt welches als Dreiecks-Matrix benutzt wird. Wird mit Ebene 0 = Wurzel Ebene gearbeitet läßt sich Ebene d nach Index i umrechnen mit  i = ((d+1)*d)/2. Für d=0 ist i=0, für d=1 ist i=1 und für d=2 ist i=3. Die Halbzüge der Ebene d werden unter Index i bis i+d abgelegt.

Endspiel King Mobility

Die Partie AVR-Max gegen Chess Champion Mk II zeigt die typische Endspielschwäche der alten Schachcomputer. Trotz Turm, Läufer und zwei Bauern gelingt AVR-Max kein Matt. Im Papier "Programming a Computer for Playing Chess" von 1949 schreibt Claude Shannon auch über die Bewertungsfunktion. Bei Shannon gibt es einen Mobility Term. Für ein erfolgreiches Matt Setzen muß die Mobilität des Königs immer weiter reduziert werden. Die Shannon Mobilität "number of legal moves available to white" hilft nicht viel im Endspiel. Die König Mobilität im Endspiel ist definiert als "Anzahl der Felder die der König, auch in mehreren Zügen, erreichen kann ohne in Schach zu geraten". Diese Definition beschreibt eine Fläche. Die Königs-Fläche die der König von seiner aktuellen Position aus erreichen kann ohne das die anderen Figuren bewegt werden und ohne das der König in Schach gerät. Die Ermittlung der König Mobilität kann erfolgen indem zuerst durch den Zug-Generator die bedrohten Felder markiert werden (die Umrandung der Königs-Fläche) und dann die Größe der Königs-Fläche mit Hilfe des Flood-Fill Algorithmus o.ä. ermittelt wird.
Bei Endspielen wie König, Springer, Läufer gegen König dürfte die Königs-Fläche nicht ständig kleiner werden (nicht monoton fallen). Eine Baumsuche bleibt weiterhin nötig. Die Suchtiefe ist aber nicht mehr bis zum Matt sondern nur noch bis zur echten(!) nächst kleineren Königs-Fläche.

NegaScout oder MTD(f) anstelle von NegaMax

NegaScout oder Principal Variation Search von Alexander Reinefeld ist eine Verbesserung von NegaMax. MTD(f) von Aske Plaat soll eine Verbesserung von NegaScout sein. In beiden Fällen wird die Baumsuche an der Wurzel mit einem Alpha-Beta Fenster mit Werten kleiner plus/minus Unendlich gestartet. Bei NegaScout gibt es nur einen Aufruf mit zu kleinem Suchfenster. Bei MTD(f) werden in einer Schleife solange minimale Suchfenster probiert bis zum Erfolg. MTD(f) ist iterativer als NegaScout. Bei NegaScout ist eine Hash-table empfehlenswert, bei MTD(f) ist eine Hash-table notwendig. AVR-Max hat bei nur 1KByte RAM keinen Platz für eine Hash-table die üblicherweise bei 128KByte Grösse beginnt. Bei Mikro-Max wird iterative deepening mit einer aspiration window NegaMax Suche verwendet. Diese mehrfache Baumsuche mit eingeschränktem Fenster wird ähnlich effektiv wie NegaScout und MTD(f) eingeschätzt.

Mikroprozessor Entwickler

Der Italiener Federico Faggin war der Designer der Intel CPUs 4004, 8008, 8080 und der Zilog Z80 CPU. Bei Fairchild hatte Faggin vorher den 3708 entwickelt, den ersten Chip in Silizium Gate MOS (Metal Oxid Semiconductor) Technik, einen 8-fach Analogmultiplexer wie der heutige 74HC4051.
Chuck Peddle hatte bei der Entwicklung des Motorola 6800 mitgearbeitet. Bei MOS Technology war er der Chefentwickler des 6502. Der 6502 war zuerst eine Niedrigpreisalternative zu 6800 und 8080. Später zeigte sich das der einfache "Opcode Fetch" Zyklus des 6502 gut passt zu dem Video-Refresh und DRAM-Refresh von grafikfähigen Computern wie Apple II und Commodore C64. Der 6502 war ein sehr guter Kompromis aus einfachen internen Aufbau und guter Leistung für den Anwender.
Der englische Ingenieur Sophie Wilson hat die RISC (Reduced Instruction Set Computer) populär gemacht. Die ARM (Acorn RISC Machine) CPU cores sind oft eingebaut in elektronischen Geräten die nicht als Computer angesehen werden, zB. dem Apple iPhone. RISC bedeutet einfache Assemblerbefehle die schnell von der CPU dekodiert und damit auch schnell ausgeführt werden. Nachteil ist der grössere Speicherbedarf für Programme.

Mark Uniacke, HIARCS, 1981

Von Mark Uniacke gibt es das Schachprogramm HIARCS. Die erste Programmversion stammt von 1981, aktuell gibt es die Version HIARCS 13. Die HIARCS Version 0.3 von 1981 ist geschrieben in PDP11 BASIC. Von Andre Adrian gibt es eine Portierung von HIARCS 0.3 auf QuickBASIC 4.5 von Microsoft. Der QuickBASIC Compiler von 1988 versteht noch BASIC mit Zeilennummern. Der Nachfolger Visual Basic erlaubt BASIC Programme ohne Quelltext.

Interton VC4000 Schach II, 1982

Die Signetics 2650 CPU erschien 1975. Ab 1976 wurde die Videokonsole 1292 Advanced Programmable Video System von Radofin vertrieben. Die Interton VC4000 Videokonsole benutzt die gleiche Hardware. Für die VC4000 gab es zwei Schach-Cartidges. Cassette 13 mit einem 4KByte langen Programm. und Cassette 22 aus dem Jahr 1982 mit 6KByte. Das VC4000 Schach zeigt kein Spielfeld, sondern nur den letzten Halbzug.



Bild links: Interton VC4000 Cassette 13 in Aktion im WinArcadia Emulator.
Bild rechts: Erklärung der Anzeige.

ZX81 1KByte Chess, 1983

Das 1KByte Chess von David Horne ist noch kleiner als das KIM-1 Microchess. Rochade usw. ist dem Programm unbekannt. Zugeingabe d7-d5 erfolgt mit Zahlen zuerst, d.h. die Tasten 7, D, 5, D eingeben. Der Mensch spielt die schwarze Seite. Der ZX81 Emulator Eightyone von Michael D. Wynne arbeitet auch unter Microsoft Vista. Die 1kchess.p Datei findet sich auf der ZX81 Download Page. Das Programm wurde in dem Artikel Full ZX-81 Chess in 1K vorgestellt.



Abbildung links: ZX81 1KByte Chess.
Abbildung rechts: ZX81 1kchess gegen KIM-1 Microchess endet in Zugwiederholung. Partie in PGN.

Sargon III, 1983 und 1984

Im Jahr 1983 wurde Sargon 3 für den Apple 2 veröffentlicht. Im Jahr 1984 erschien Sargon 3 für den Commodore C64. Auf dem C64 gibt es eine wunderschöne farbige Spielfelddarstellung, auf dem Apple 2 leidet die farbige Darstellung unter den typischen Farbsäumen. Sargon III wurde Weihnachten 1984 für 49,95 $ angeboten für Apple II, Macintosh, Commodore C64 und IBM PC laut New York Times.



Bild links: Sargon 3 auf dem AppleWin Apple 2e Emulator in Schwarz/Weiss. Mit Strg-Ü wird auf die graphische Darstellung geschaltet.
Bild rechts: Sargon 3 auf dem VICE Commodore C64 Emulator. Start mit LOAD "*",8,1 und RUN.

Mychess, 1984

David Kittinger ist neben Ron Nelson der dienstälteste kommerzielle Programmierer für Mikrocomputer Schach. Das Programm Mychess stammt von 1979, die MS-DOS Version des Programmes stammt von 1984. Bei der WCCC Weltmeisterschaft 1980 in Linz hat Mychess den 14. Platz belegt. Weitere Turnierteilnehmer waren Belle (1. Platz), Chess 4.9 und Kaissa. Mychess lief auf einem Cromenco Mikrocomputer mit Z80 CPU. David Kittinger ist laut Bruce Moreland der Erfinder des 0x88 Boards. Auch die Pre Scan Heuristics (PSH) sind von ihm.



Bild: Mychess in MS-DOS High-Res 640x400.

Colossus Chess 4, 1985

Martin P. Bryant ist der Autor von Colossus Chess. Version 2 erschien 1984, Version 4 erschien 1985. Nach Aussage von Herr Bryant spielt Colossus 4 stärker als Sargon 3. Auf jeden Fall hat Colossus 4 einen Intro-Bildschirm, welcher bei Sargon 3 fehlt. Colossus 4 erschien für Commodore C64, Amstrad CPC464, Sinclair ZX Spectrum und die japanischen MSX Computer. Preis war £9.95.



Bild links: Commodore C64 Colossus 4 Intro
Bild rechts: Commodore C64 Spielfelddarstellung. Zugeingabe erfolgt durch Eingabe von z.B. e2 RETURN e4 RETURN.

Cyrus II, 1985, 1986

Nach dem Ehepaar Spracklen war Richard Lang sehr erfolgreich bei der World Microcomputer Chess Championship. Von 1985 bis 1990 haben Mephisto Schachcomputer sechsmal mit seinen Programmen gewonnen. Der Sinclair ZX Spectrum 128 hatte mit 128KByte doppelt soviel RAM wie der Amstrad CPC464 oder Commodore C64. Die 3D Darstellung des Spielfeldes ist unübersichtlich - aber seinerzeit war es modern. Cyrus II erschien zuerst auf Amstrad CPC464, dann ZX Spectrum 128K, MSX und zuletzt auf Commodore C64.



Bild links: Cyrus II auf dem WinApe32 CPC464 Emulator. Start mit run "cyrus"
Bild mitte: Cyrus II auf dem Klive ZX Spectrum 128K Emulator von Steeve Snake. EmuZWin von Vladimir Kladov ist auch ein guter Emulator.
Bild rechts: Cyrus II auf dem Spectrum in 2D Ansicht. Crafty 19.3 zerlegt Cyrus II auch auf Stufe 7. Die Partie in PGN.

Computerschach nach 1984

Mit dem Apple Macintosh wird 1984 der moderne Bürocomputer eingeführt. Die Heimcomputer folgten dem Trend zu 16-Bit CPU und graphischer Benutzeroberfläche. Atari ST und Commodore Amiga waren die letzten eigenständigen Entwürfe bevor die IBM-PC Kompatiblen den Markt aufrollten. Wie so oft ging eine Ära langsam zu Ende. Das Programm Cyrus II und auch der Spectrum 128K erschienen als die beste Zeit für 8-Bit Heimcomputer schon vorbei war. Im Nintendo Gameboy von 1989 leben die 8-Bit Computer weiter.
Die Schachcomputer konnten sich noch eine Zeitlang gegen die IBM-PC Kompatiblen behaupten. Spätestens mit der Einführung der Intel 80486 CPU Anfang der 1990er Jahre sind die Schachprogramme auf den Bürocomputern dann den Schachcomputern davongerannt.



Bild links: Psion Chess für MS-DOS von Richard Lang (Psion, 1985) auf dem DOSBOX Emulator.
Bild mitte: Gameboy The Chessmaster von Park Place Production Team (Nintendo, 1990) auf dem BGB Emulator.
Bild rechts: Battle Chess für MS-Windows von Patrick Wyatt (Interplay, 1991).

Micro Travel Chess Computer von 2007

Der Saitek Micro Travel Chess (Saitek Modell CH09) hat laut Schachcomputer.info 1393 Elo im Aktivschach. Angeboten wird das Gerät für 30 bis 40 Euro. Die Figurendarstellung ist deutlich, aber die LCD Anzeige hat einen geringen Kontrast und ist schlecht lesbar. Bedienung erfolgt mit Stift über touch screen. Eine gute Eigenschaft des Gerätes sind die 44 verschiedenen "Fun-Level". Im Fun-Level fährt der Micro Travel mit angezogener Handbremse. Der Computer führt mehr oder minder sinnvolle, menschlich wirkende Züge aus, läßt aber z.B. die Dame in der Schusslinie stehen.
Ich bin ein sehr schlechter Schachspieler. Ich kenne die Regeln, ich kann Pläne entwickeln, aber bei der Umsetzung fehlt die Sorgfalt, die Erfahrung. Der übliche Schachcomputer klaut mir eine Figur nach der anderen. Beim Micro Travel Chess habe ich mir vorgenommen möglichst viele Fun-Levels durchzuspielen. Wenn ich gewinne gehts im nächsten Fun-Level weiter. Jeder Gewinn gegen den Schachcomputer ist positive Rückmeldung - gut zum Lernen.
Ältere Schachcomputer haben auch schwache Level. Aber die Computer Züge waren so "blöde", da wollte ich nicht spielen. Einen Dank an Saitek Mephisto für dieses Lernen macht Spaß Gerät. Die 1393 Elo liefert der Micro Travel angenehm schnell mit 15 Sekunden pro Zug. Nicht zu vergleichen mit meinem Krypton Jupiter von 1994 der für 1400 Elo noch 10 Minuten pro Zug benötigt.
Um die schlechte LCD Anzeige erträglicher zu machen habe ich "contrast" auf 5 und "automove" auf off gestellt.
Der Maestro Travel Chess Computer (Saitek Modell CH08) hat Hintergrundbeleuchtung und laut Schachcomputer.info 1570 Elo. Preis ist 60 bis 80 Euro. Auch hier gibt es die "Fun-Level". Anstelle der 5 Tasten für Cursor Steuerung gibt es einen Mini-Joystick. Bei neuen Geräten ist die Hintergrundbeleuchtung weiss. Eine schwarze Ledertasche wird mitgeliefert.


Bild links: Micro Travel Chess Computer in silber
Bild mitte: Micro Travel Chess Computer in schwarz, mein Modell.
Bild rechts: Maestro Travel Chess Computer

Aktuelle Schachcomputer

Die Blütezeit der Schachcomputer ist vorbei. Die Fimen Novag, Saitek Mephisto und Excalibur bauen immer noch gute Geräte die heute recht günstig angeboten werden. Das beste Preis-Leistungs Verhältnis haben die 8-Bit CPUs ohne Hashspeicher bei 2000 Elo und rund 100 Euro. Für das Geld gibt es ein Sensorbrett mit 16 LEDs und eine häßliche, aber nützliche 7-Segment LCD Anzeige. Die CPU ist ein 8/16bit Type aus der Renesas (früher Hitachi) Serie H8/300. Wenn auf einem Schachcomputer mit H8 CPU der Begriff "RISC Style" steht ist das mehr Marketing Geschrei als technische Tatsache. Im Prospekt steht übrigens "CISC Style" Prozessor. Die Programme sind von Frans Morsch oder David Kittinger. Auch wenn das Innenleben sehr ähnlich ist, die äußere Form ist unterschiedlich.
Das Mephisto Expert Travel Chess ist ein Steckschach (kein Magnetschach). Die Seitenlänge ist 1,4cm pro Feld. Es ist eine echte Rennmaus mit 2031 Aktivschach Elo aus einem Frans Morsch Programm. Preis ist 100 Euro. Stromversorgung sind 4 Mignon Batterien.
Der Mephisto Chess Challenger oder Mephisto Admiral hat ein Spielfeld mit 2,5cm Seitenlänge pro Feld. Ein Turnierbrett hat 5,8cm Felder. Die Figuren sind aus Kunststoff. Wahrscheinlich arbeitet hier das gleiche Frans Morsch Programm wie im Expert Travel Chess. Preis ist 100 Euro. Stromversorgung sind 6 Baby Batterien oder mitgeliefertes 9V Netzteil.
Der Novag Obsidian hat ein Spielfeld mit 2,8cm großen Feldern. Die Figuren sind aus Holz. Zu den Holzfiguren und dem schwarzen Plastikgehäuse würde ein braun/weisses oder grün/weisses Spielfeld besser aussehen. Der fast baugleiche Excalibur Karpov 2294 hatte eine braunes Holzimitat Gehäuse und Spielfeld. Das Programm ist von David Kittinger und hat 2036 Aktivschach Elo. Preis ist 125 Euro. Stromversorgung sind 6 Baby Batterien oder extra zu kaufendes 9V Netzteil. Die Spielstärke des Novag Obsidian läßt sich gut reduzieren. Auf Stufe EA1 (Easy 1) hat auch ein 1000 Elo Spieler wie ich eine Gewinnchance. Schon auf dieser Stufe spielt der Obsidian ein zielgerichtetes Endspiel wenn der Computer die Gelegenheit bekommt.



Bild links: Mephisto Expert Travel Chess
Bild mitte: Mephisto Chess Challenger
Bild rechts: Novag Obsidian, mein zweiter Schachcomputer.



Bild links: Anfänger gegen Novag Obsidian auf Stufe EA1 mit 1 Halbzug Suche und 2 Halbzüge Abtausch Suche. Matt nach 32 Zügen. Partie in PGN.
Bild rechts: Anfänger gegen Novag Obsidian, Stufe EA2, 1 Halbzug Suche, 3 Halbzüge Abtausch Suche. Matt nach 41 Zügen. Partie in PGN.

RISC und CISC

Die Unterschiede zwischen Reduced Instruction Set Computer (RISC) und Complex Instruction Set Computer (CISC) sollen am Beispiel der CPUs Atmel ATMega und Renesas H8 veranschaulicht werden.
Die ATMega CPU ist eine typische RISC mit einem Befehl pro Maschinenzyklus. Die H8 ist etwas mehr CISC als RISC, aber auch keine typische CISC.

Programmiersprache für Schachprogramme

Auf die Frage: "Was ist die beste Programmiersprache für eine gewisse Aufgabe" gibt es immer zwei Antworten: "Jede" und "Ihre Lieblingsprogrammiersprache". Jede Turing komplette Programmiersprache hat die gleiche Mächtigkeit. Je nach Sprache und mehr noch Entwicklungsumgebung ist es für den Programmierer leichter oder schwieriger diese Mächtigkeit für die Aufgabenstellung zu nutzen. Die Programmiersprache FORTRAN kennt keine Rekursion. Der FORTRAN Programmierer muß daher einen rekursiven Algorithmus in eine iterative Form bringen. Die Assembler Sprachen kennen keine strukturierte Programmierung. Der Programmier muß seine if-then-else Kontrollstrukturen in Vergleich- und Sprungbefehle (Compare, Jump) umsetzen. Auch Programmiersprachen wie Lisp, Prolog und Perl bieten nur die Mächtigkeit einer Turing kompletten Programmiersprache.
Für Schachprogramme wurden die üblichen Verdächtigen als Programmiersprache benutzt: FORTRAN für die Großrechner Schachprogramme der 1950er und 1960er Jahre. Assembler für die ersten Mikrocomputer Schachprogramme der 1970er Jahre. Und C für das "übliche" Schachprogramm seit den 1980er Jahren. Natürlich gab und gibt es Schachprogramme in PASCAL, BASIC und Java. Diese Programmiersprachen sind nicht schlechter als C - aber oft optimiert der C Compiler besser und erzeugt dadurch aus dem gleichen Quelltext ein schnelleres und/oder kleineres Maschinensprache-Programm. Weil FORTRAN keine Rekursion unterstützt kann ein FORTRAN Compiler oft noch besser optimieren als ein C Compiler.
Eine interessante Programmiersprache für Schachprogramme der 1980er Jahre war die Compiler Description Language (CDL). Bei dieser Programmiersprache mußte der Programmierer zwei Aufgaben lösen. Einmal den Quelltext schreiben. Dann aber auch die Maschinensprache-Generierung festlegen. Bei FORTRAN und C hat der Compiler-Entwickler festgelegt welche Maschinensprache Befehle den "+" Operator realisieren. Bei CDL war das offen. Weil die Compiler für kleine Mikrocomputer der 1980er Jahre oft eine schlechte Code-Optimierung hatten, war CDL mit seiner Möglichkeit der selbstgemachten Code-Optimierung eine gute Alternative zu Assembler. Siehe Das Mephisto 3 Projekt.
Heute sind die Maschinensprache Befehle der CPUs besser auf die Anforderungen der Compiler abgestimmt. Die GCC Compiler Code-Optimierung für kleine Mikrocontroller wie die AVR 8-Bit Serie ist genauso gut wie für grössere CPUs. Wer möchte kann weiterhin in CDL2 die Schachprogramme schreiben. Aber C genügt. Von Assembler ist wie immer bei umfangreicheren Aufgaben abzuraten.

Mikroprozessor Schachcomputer

Viele Mikroprozessoren der 1970er und 1980er Jahre wurden für Schachcomputer verbaut. Selbst 4 Bit Mikrocomputer - üblicherweise in Waschmaschinen oder Brotbackautomaten zu finden - wurden als Schach Engine eingesetzt. Die Elo Punkte stammen von der Schachcomputer.info Aktivschach Liste.
CPU
Schachcomputer
Programmierer
Elo Punkte
Intel 8080, 1974, 8bit
Fidelity Chess Challenger 1, 1977
Ron Nelson
985
Fairchild F8, 1975, 8bit Data Cash Systems CompuChess, 1977
D. B. Goodrich and Associates 985
MOS Technology 6504, 1975, 8bit Commodore Chessmate, 1978
Peter Jennings
1090
Zilog Z80, 1976, 8bit Fidelity Chess Challenger 10, 1978 Ron Nelson 1153
Zilog Z80, 1976, 8bit TRS-80 SARGON CHESS,1978 Dan & Kathe Spracklen ?
MOS Technology 6507, 1975, 8bit Atari 2600 Video Chess, 1979 L.Wagner, B.Whitehead, Julio Kaplan
?
Fairchild F8, 1975, 8bit Channel F Saba Videoplay Schach, 1979
?
?
Signetics 2650A, 1976, 8bit
Interton VC4000 Schach, 1979?
?
?
TI TMS9900, 1976, 16bit TI 99/4 Video Chess, 1980 David Levy ?
RCA 1802, 1976, 8bit
Mephisto I, 1980
Thomas Nietsche, Elmar Henne 1252
GI CP1610, 1975, 16bit
Mattel Intellivision USCF Chess, 1981
Teletape, Inc., Russ Ludwick
?
RCA 1802, 1976, 8bit Mephisto III, 1983
Thomas Nietsche, Elmar Henne 1464
Motorola 68000, 1979, 16bit
Mephisto Excalibur, 1983
Thomas Nietsche, Elmar Henne
1610
Hitachi 6301, 1983, 8bit CXG Star Chess, 1985
Kaare Danielson
1423
Intel 80C50, 198?, 8bit
Fidelity The Gambit, 1987
Ron Nelson
1300
Hitachi HMCS40, 198?, 4bit
CXG Sphinx Chess Card, 1989
David Levy, Mark Taylor
1087
Motorola 68HC05, 198?, 8bit
Saitek Traveller, 1991
Craig Barnes
1300
Acorn ARM, 1986, 32bit Mephisto Risc 1MB, 1991
Ed Schröder
2203
Hitachi H8, 1990, 8/16bit
Saitek GK 2000, 1992
Frans Morsch
1966
Sun SPARC, 1987, 32bit
Saitek Sparc, 1993
Dan & Kathe Spracklen
2225
Motorola 68030, 1987, 32bit
Mephisto London 68030, 1994
Richard Lang
2302

Die stärksten Schachcomputer hatten die stärksten und teuersten CPUs. Interessanter als diese Materialschlacht zwischen Motorola 68000 und Acorn ARM ist die Entwicklung der Spielstärke der 6502 CPU. 1984 erreichte Scisys Turbostar 432 KSO (4MHz Takt, 40KByte ROM, 8KByte RAM) mit einem Programm von Julio Kaplan 1780 Elo Punkte und 1991 hat Mephisto Milano (4.9MHz Takt, 32KByte ROM, 8KByte RAM) mit einem Programm von Ed Schröder sogar 1961 Elo Punkte erreicht. Eine ähnliche Leistung von 2000 Elo holt das David Kittinger Programm im Novag Obsidian aus einer H8 CPU mit 20MHz, 32KByte ROM und 1KByte RAM. Bemerkenswert ist auch die Leistung der 4bit CPU von Hitachi. Mit 0.5MHz Takt, 2.5KByte ROM und 80Byte(!) RAM haben die Programmierer ein echtes Wunderwerk geschaffen. Auch die F8 und 80C50 CPUs wurden wohl aufgrund des niedrigen Preises ausgewählt. Die zweite Generation Schachcomputer mit Fidelity Chess Challenger 10, Mephisto I, TRS80 Sargon II, Atari 400 Computer Chess und TI99/4 Video Chess hatten schon genug Spielleistung für Gelegenheitsspieler mit 1100 Elo Punkten. Der Mephisto III von 1983 war schon ein Gegner für Klasse C Amateure.
Die Schach Cartridges für Saba Videoplay, Interton VC4000 und Mattel Intellivision enthielten zusätzlichen RAM Speicher. Das Schach-Module C7010 für die Magnavox Odyssey 2 (Philips G7000) enthielt sogar eine eigene CPU.

Schach und künstliche Intelligenz

Viele Schachprogramme entstanden im Umfeld der Künstlichen Intelligenz Forschung. Bis heute entzieht sich der Begriff "Intelligenz" einer naturwissenschaftlichen Definition. Einige Grundlagen der menschlichen Intelligenz werden allgemein anerkannt: Ein Mensch kann aus Beispielen eine Regel generalisieren. Diese "rule extraction" benötigt ein Gedächtnis (memory). Beim Generalisieren oder Abstrahieren werden die einzelnen Beispiele durch eine Schablone oder Regel (rule) ersetzt. Diese Schablone ist weniger detailliert. Höchstwahrscheinlich ist für "rule extraction" nicht nur Lernen im Sinne von Beispiel-Ansammeln nötig sondern auch ein gezieltes Vergessen. Die Ausnahmen widerlegen die Regel, werden aber bei der Regel-Bildung ignoriert. Lernen und Vergessen sind die Grundbausteine der menschlichen Intelligenz, wenn Intelligenz mit Regelextraktion gleichgesetzt wird.
Ein Schachprogramm realisiert eine Baumsuche mit einer Bewertung. Ausgehend von der aktuellen Brettstellung werden mögliche Züge durch einen Zuggenerator berechnet. Kann der Schachcomputer bis zum Spielende vorausrechnen kann der beste Zug fehlerfrei bestimmt werden. Im Endspiel reicht die Rechenleistung dazu heute schon aus. Im Mittelspiel wird die Vorausberechnung nach einer Anzahl von Zügen abgebrochen und die entstehende Position wird bewertet. Die Bewertungsfunktion ist in allen Details vom Programmierer vorgegeben. Eine gute Bewertungsfunktion liefert für möglichst viele Positionen eine korrekte Bewertung im Sinne von "Weiss im Vorteil" oder "Schwarz im Vorteil".
Der Schachprogrammierer ist auf jeden Fall intelligent. Es ist eine schwierige Aufgabe die - höchstwahrscheinlich unbewusst ablaufende - eigene Regelextraktion bewusst zu machen und dann in einer Programmiersprache zu formulieren. Das Schachprogramm selbst führt keine Regelextraktion aus. Es wendet die vom Programmierer vorgegebenen Regeln an.
Eventuell gibt es doch Gemeinsamkeiten zwischen den Abläufen im Gehirn eines Schach spielenden Menschen und in einem Schachprogramm. Vielleicht laufen die Funktionen Baumsuche und Bewertung auf einer unbewußten Ebene ab. Das "bewußte Ich" des Schachspielers hat nicht Zugriff auf seinen "unbewussten Computer" sondern erhält nur die Ergebnisse der Rechenvorgänge mitgeteilt.
Als Beleg mag folgendes Beispiel dienen: Nachdem die Figurbewegung gelernt ist, spielt ein Schachneuling sehr langsam. Jeder Zug wird "vorausberechnet". Durch die Rückmeldung aus den verlorenen und gewonnenen Spielen werden Regeln extrahiert. Diese gelernten Regeln machen das Schachspiel immer schneller und besser. Irgendwann wird vor allem das Eröffnungsspiel und das Endspiel nicht mehr langsam "vorausberechnet" sondern schnell durch Regel-Anwendung gespielt. Ein Schach Könner ist entstanden. Im Mittelspiel ist die Anzahl der Varianten am grössten und deshalb die Regel-Extraktion am schwierigsten. Deshalb werden Schachpartien oft am Ende des Mittelspiels aufgegeben: Beiden Schachspielern ist klar wie das Endspiel ausgehen wird.
Die Schach Endspiel Theorie wird heute im Zusammenspiel zwischen Mensch und Computer korrigiert: Inverse Zuggenerator Programme erzeugen vollständige Bäume von Endspielen. Schachmeister führen auf diese vollständigen Informationen die Regelextraktion aus. Die Bücher "Secrets of Rook Endings" usw. von John Nunn enthalten die Erkenntnisse aus den Endspiel Datenbanken von Ken Thompson.

Baumsuche

Die Baumsuche ist von den Spielregeln unabhänging. Für die 2-Personen Spiele Tic Tac Toe, Vier Gewinnt, Dame, Schach usw. kann die gleiche Baumsuche verwendet werden. Der Minimax Algorithmus ist eine vollständige Baumsuche mit korrekter Rückmeldung der Ergebnisse. Durch Alpha-Beta Beschneidung (Pruning) kann die Baumsuche stark beschleunigt werden. Alpha-Beta liefert die gleichen Ergebnisse wie Minimax. Eine weitere Verbesserung ist Principal Variation Suche. Hier wird im ersten Anlauf mit einem minimal kleinen Suchfenster gesucht. War die Suche erfolglos, wird die Suche mit einem normal grossen Suchfenster wiederholt. Noch schneller ist die Null-Zug Heuristik Suche. Diese Baumsuche ist aber nicht mehr vollständig. Im Endspiel oder bei Zugzwang Schachaufgaben kann die Lösung übersehen werden. Deshalb wird im Endspiel Null-Zug Suche abgeschaltet.
Damit Alpha-Beta und Principal Variation Suche optimal arbeiten müssen die Züge sortiert sein. Der stärkste Zug muß zuerst bewertet werden. Die Sortierung der Züge an der Baum-Wurzel läßt sich durch schrittweise Vertiefung (iterative Deepening) erreichen. Die Killer-Zug Heuristik hilft bei der Zugsortierung weiter unten im Baum. Das iterative Deepening läßt sich auch auf allen Baumsuch-Ebenen anwenden.
Die gleichen Stellungen lassen sich über verschiedene Zugfolgen erreichen (z.B. 1. e4 e5, 2. d4 d5 oder 1. d4 d5, 2. e4 e5). Diese Wiederholungen können mit Hilfe einer Hash-Tabelle (hash table, transposition table) erkannt werden. Anstelle eine Baumsuche des gleichen Teilbaums auszuführen wird das Ergebnis aus der Hash Tabelle übernommen. In der Hash-Tabelle steht pro Eintrag üblicherweise ein zweiter Hash-Schlüssel um Kollisionen zu erkennen. Weiterhin die Baumtiefe, Alpha- und Beta-Werte der originalen Suche um festzustellen ob das Suchfenster der alten Suche den Anforderungen der neuen Suche genügt (MiniMAX Hashtabellen).

Bewertung

Die Bewertung einer Brettposition ist von den Spielregeln abhängig. Bei vollständiger Baumsuche wie sie z.B. bei Tic Tac Toe, Vier Gewinnt und auch bei Schachendspielen bis 7 Figuren heute möglich ist, genügt die Feststellung von gewonnen, verloren oder unentschieden (Remis, Patt). Im Schach Mittelspiel ist eine vollständige Baumsuche bis zum Partieende nicht möglich. Hier müssen "Faustformeln" (Heuristiken) für die Bewertung benutzt werden.
Eine Bewertungsfunktion kann ohne tiefe Baumsuche benutzt werden. Eine falsche Beurteilung durch die Bewertungsfunktion hat bei einer solchen 1-Halbzug Baumsuche die stärkste Auswirkung. Die Fehler der Bewertungsfunktion werden durch eine tiefere Baumsuche abgeschwächt. Einmal werden Partieende-Positionen mit einer abschließenden Bewertung erreicht, z.B. beim Schäfermatt, Seekadettenmatt. Zweitens werden Schlagfolgen bis zum Ende verfolgt und erst dann beurteilt. Dies läßt den Computer Gabeln, Opfer usw. erkennen.

Materialbewertung

Die einfachste Bewertung ist die Materialbewertung. Turing schreibt darüber: "A very simple form of values, but one not having this property, is an evaluation of material, e.g. on the basis– Pawn = 1, Knight = 3, Bishop = 3.5, Rook = 5, Queen = 10, Checkmate = 1000. If B is black's total and W is white's, then W/B is quite a good measure of value. This is better than W – B... ". Shannon schreibt "The relative values of queen, rook, bishop, knight and pawn are about 9, 5, 3, 3, 1, respectively"
Heute üblich ist Bauer=1, Springer, Läufer=3, Turm=5, Dame=9 und König=Unendlich. Die Materialbewertung ist Weisses Material - Schwarzes Material. Zur Materialbewertung gehört auch die Erkennung von Spielende. Einmal durch Schachmatt, aber auch durch Remis, Patt, 50-Zug-Regel, 3-fache Wiederholung und Partieende durch zuwenig Material, z.B. nur noch König, zwei Springer und König auf dem Feld. Ein Matt in einem Zug sollte übrigens besser bewertet werden als ein Matt in zwei Zügen um "ewige" Partien zu vermeiden.
Besonders im Mittelspiel liefert die Baumsuche mit Materialbewertung oft mehrere Züge mit gleicher Bewertung zurück. Aus diesen Kandidatenzügen kann ein Zug per Zufall ausgesucht werden. Besser ist eine positionelle Bewertung dieser von der Materialbewertung her gleichwertigen Züge.

Positionelle Bewertung

Das Schach Fachwissen (domain knowledge) der Brute Force Schachprogramm Autoren zeigt sich in der positionellen Bewertung. Alan Turing schreibt: "If I were to sum up the weakness of the above system in a few words I would describe it as a caricature of my own play. It was in fact based on an introspective analysis of my thought processes when playing, with considerable simplifications. It makes oversights which are very similar to those which I make myself".

Siegbert Tarrasch

Dr. Siegbert Tarrasch hatte keine Verbindung zum Computerschach. Er war aber ein guter Schachspieler der als Autor seine Einsichten präzise zu Papier brachte. Sein Buch "Das Schachspiel" von 1931 ist immer noch eine gute Einleitung zu den Themen Endspiel und Mittelspiel. Die Eröffnung wird natürlich auch behandelt. Für Tarrasch besteht das Spiel aus den Faktoren Kraft, Raum und Zeit. Die Kraft wird heute Materialbilanz genannt und die Zeit ist besser als Tempo bekannt. Der Raum ist abstrakter, er beschreibt die Herrschaft über das Spielfeld, besonders über die eigene Spielfeldhälfte, d.h. die erste bis vierte Reihe für Weiss. Eine geöffnete Linie ist ein Beispiel für Raumgewinn.
Tarrasch schreibt über die Kraft: "Springer und Läufer sind gleich stark, jeder ungefähr gleich drei Bauern. Der Turm ist stärker als eine leichte Figur [Springer, Läufer]. Zwei leichte Figuren sind stärker als ein Turm. Die Dame ist so viel wert wie die beiden Türme oder wie drei leichte Figuren." Die übliche Materialbewertung von Springer, Läufer = 3, Turm = 5 und Dame = 9 Bauerneinheiten findet sich schon bei Tarrasch.
Das vorhandene Material beeinflußt die Materialbilanz laut Tarrasch: "Turm, eine leichte Figur und ein Freibauer auf der sechsten Reihe sind stärker als die Dame. Zwei leichte Figuren sind um 0,5 Bauern stärker als Turm und ein Bauer. Wenn ein Springer im Zentrum steht, auf den Linien c-f, auf der vierten bis sechsten Reihe, womöglich gedeckt von einem Bauern und unangreifbar durch einen Bauern, dann ist er dem Läufer überlegen und beinah so stark wie ein Turm. Hat ein Spieler einen Mittelbauern gegen einen Springerbauern, so wird er etwas im Vorteil sein."
Was Tempo im Schach bedeutet zeigt Tarrasch anschaulich für die Eröffnung: "Rochade = 1 Tempo, die Dame entwickelt = 1 Tempo, Turm der mindestens die dritte Reihe erreichen kann = 1 Tempo, Turm auf einer halboffenen Linie = 1 Tempo, Läufer bewegt = 1 Tempo, Springer auf der zweiten oder dritten Reihe = 1 Tempo, Springer auf der vierten oder fünften Reihe = 2 Tempi, Springer auf der sechsten oder siebten Reihe = 3 Tempi, Bauer der c, d oder e Linie gezogen = 1 Tempo".
Die Baumsuche kann nur einen Minimax-Wert liefern, deshalb müssen Kraft und Zeit in der gleichen Einheit gemessen werden. Hier sagt Tarrasch: "erst drei Tempi sind genügend, ein Gambit zu rechtfertigen". Ein Gambit bedeutet ein Bauernopfer, d.h. 1 Bauer = 3 Tempi.

Claude Shannon

Die Bewertungsfunktion f(P) besteht bei Shannon aus der Materialbewertung, einem Abschlag für schlechte Bauernstellungen (doppelter Bauer, rückständiger Bauer und isolierter Bauer) sowie einem Mobilitätsbonus:
f(P)=200(K-K')+9(Q-Q')+5(R-R')+3(B-B'+N-N')+(P-P')-.5(D-D'+S-S'+I-I')
+.1(M-M')+...

in which:-
K,Q,R,B,B,P are the number of White kings, queens, rooks, bishops, knights
and pawns on the board.

D,S,I are doubled, backward and isolated White pawns.
M= White mobility (measured, say, as the number of legal moves available
to White).

Alan Turing Papiermaschine

Die Papiermaschine von Alan Turing arbeitet mit folgender positionellen Bewertung:
 
Jeder weiße Stein leistet einen Beitrag zur Spielposition, ebenso der schwarze König. Alles muß aufaddiert werden, um die Bewertung der Spielposition zu ermitteln.

For a Q, R, B, or N, count
  1. The square root of the number of moves the piece can make from the position, counting a capture as two moves, and not forgetting that the king must not be left in check.
  2. (If not a Q) 1.0 if it is defended, and an additional 0.5 if twice defended.
For a K, count
  1. For moves other than castling as (1) above.
  2. It is then necessary to make some allowance for the vulnerability of the K. This can be done by assuming it to be replaced by a friendly Q on the same square, estimating as in (1), but subtracting instead of adding.
  3. Count 1.0 for the possibility of castling later not being lost by moves of K or rooks, a further 1.0 if castling could take place on the next move, and yet another 1.0 for the actual performance of castling.
For a P, count
  1. 0.2 for each rank advanced.
  2. 0.3 for being defended by at least one piece (not P).
For the black K, count
  1. 1.0 for the threat of checkmate.
  2. 0.5 for check.
Turing selbst hat eine Partie seiner Papiermaschine gegen Alick Glennie notiert. Für das Schachprogramm Fritz gibt es eine Turing Engine. Eine Partie zwischen den Schachprogrammen Turing und Fritz 6 zeigt die Schwächen der Turing Positionsbewertung und auch einen Fehler in der Engine Implementierung - der Springer hat auf f3 eine bessere Mobilität als auf h3. Der Bauer auf a4 und die Dame auf f3 erlauben eine hohe Mobilität, dürften aber selbst einem Schach Neuling als wenig sinnvolle Eröffnungszüge erscheinen.

        

Bild links: Turing Papiermaschine (Schach Engine) - Fritz 6. Position nach dem 5. Zug. Beide Programme spielten ohne Eröffnungsbibliothek.
Bild rechts: Turing Papiermaschine (von Turing ausgeführt) - Alick Glennie, 1952. Position nach dem 8. Zug. Die Dame diesmal ohne Wandertrieb - hat Turing hier gemogelt?

Peter Jennings Microchess

Die positionelle Bewertung von Microchess von Peter Jennings ist umfangreicher. Die Details stehen im Programmer' Manual. Die Bewertung ist:

MOB      Mobliity.  The total number of moves available for  a
         given side from a given position.  Each queen move is
         counted as two moves,

MAXC     Maximum  Capture.   The number of points,to be gained
         by cacturing the most valuable piece currently  under
         attack.

CC       Capture  Count.   The  total  points  of all opposing
         pieces under attack.

MAXP     Maximum  Capturable  Piece.   Identification  of  the
         opponent's piece under attack which is worth the most
         points.

PRIOR  COUNTS (.PMOB, .PMAXC,  PCC, .PMAXP) reflect the status
of the position as it exists for the computer before any  move
is made.  This is a benchmark, against which further moves are
to be compared.

CONTINUATION COUNTS (.WMOB, .WMAXC, .WCC, .WMAXP) are obtained
for  each  move  tested  to determine the potential of the new
position that would result if the move were made.

REPLY COUNTS (.BMOB, .BMAXC, .BCC, .BMAXP)  are  obtained  for
each  move  tested  to  determine  the potential danger of the
opponent's available replies.

EXCHANGE  COUNTS  (.WCAPO,  .WCAP1,  .WCAP2,  .BCAP0,  .BCAP1,
.BCAP2)  are  used  to  analyse  the  effect  of the potential
exchange combinations.  Each count reflects the maximum number
of points capturable at each level of an exchange combination.
Capture chains are halted by pawn captures, king captures,  or
by reaching a limit of three captures per side.

In addition, information regarding the moving piece and its TO
and FROM squares can also be used by the STRATGY algorithm.

All  information available is combined by the algorithm in the
subprogram STRATGY to calculate a single strategic  value  for
the move under analysis.  The algorithm, a weighted sum of the
count information, is shown below:

VALUE = + 4.00 * WCAP0
        + 1.25 * WCAP1
        + 0.75 * (WMAXC + WCC)
        + 0.25 * (WMOB  + WCAP2)
        - 2.56 * BMAXC
        - 2.00 * BCC
        - 1.25 * BCAP1
        - 0.50 * BMAXC
        - 0.25 * (PMAXC + PCC + PMOB + BCAP0 + BCAP2 + BMOB)


        

Bild links: Soft6502 KIM-1 Simulator von Charles Bond führt Microchess aus. 0F1333 bedeutet Microchess eröffnet mit Königsbauer e2-e4.
Bild rechts: Microchess zählt die Spalten a bis h als 0 bis 7 und die Reihen 1 bis 8 ebenfalls als 0 bis 7.

Wieviel Bewertung ist nötig?

Claude Shannon schreibt schon 1949 in "Programming a Computer for Playing Chess":
The more violent tactical weapons, such as discovered checks, forks and pins by a piece of lower value are omitted since they are best accounted for by the examination of specific variations.

Bei Schachaufgaben genügt es Matt und die anderen Spielende Bedingungen wie Patt und Remis zu bewerten. Hierzu David Broughton, Programmierer des Scisys Chess Champion Mark V von 1981:
Wiki: The Mark V was not only very well playing, he was also the best chess puzzle solver for many years. What was his secret?
D.B.: Simply efficient programming to a fixed depth of search and cutting out all material and positional evaluations other than the king value.

Die heutige Suchtiefe von 13 bis 15 Halbzügen macht für Ed Schröder einiges Schach Fachwissen im Programm unnötig:
To escape from the horizon effect all kind of tricks were invented, chess knowledge about dangerous pins, knight forks, double attacks, overloading of pieces and reward those aspects in eval. Complicated and processor time consuming software it was (15-20% less performance) but it did the trick escaping from the horizon effect in a reasonable way.
Today we run chess program on 1500 Mhz machines and instead of the 5-7 plies Rebel now gets 13-15 plies in the middle game and the horizon effect which was a major problem at 5 Mhz slowly was fading away.
So I wondered, what if I throw that complicated "anti-horizon" code out of Rebel, is it still needed? So I tried and found out that Rebel played as good with the "anti-horizon" code as without the code. In other words, the net gain was a "free" speed gain of 15-20%, thus an improvement.

Thomas Nietsche, Elmar Henne schreiben über das nötige Schachwissen einer Baumsuche am Beispiel Mephisto III:
"Finde einen Schlüsselzug, der dem Gegner zu einer oder zu wenigen Antworten zwingt; setze 1-2 Züge mit Druck fort; rechne sie i.A. klare Abwicklung durch." Wenn Sie als Leser die mehr oder weniger berühmten Kombinationen unter diesem Gesichtspunkt betrachten, so werden Sie feststellen, daß sich 90%-95% unter diesem Schema subsumieren lassen.

Michail Botwinnik schreibt in "Computers in Chess" über die Probleme einer Bewertungsfunktion ohne Baumsuche:
In chess, on the other hand, the data destined for analysis is deeply hidden in the initial data. The principal task consists in transforming the initial data to a form suitable for analysis. Herein lies one of the reasons for our delay in finishing PIONEER-1.

Bobby Fischer fasst zusammen: "Concentrate on material gains. Whatever your opponent gives you take, unless you see a good reason not to."

Nach den obigen Empfehlungen kann ein Schachprogramm so vorgehen: Eine erste Tiefensuche liefert nur Gewinn, Unentschieden (Patt, Remis), Verlust oder Unbekannt, wenn die Suchtiefe nicht ausreicht. Falls diese Schachmatt-Tiefensuche das Ergebnis Unbekannt liefert, dann startet eine zweite Tiefensuche. Diesmal ist die maximale Suchtiefe kleiner und die Bewertungsfunktion liefert die Materialbalance. Findet diese zweite Tiefensuche keinen Zug der den anderen Zügen überlegen ist, dann folgt eine dritte Tiefensuche mit einer komplexen Bewertungsfunktion. Die maximale Suchtiefe ist bei der ersten Tiefensuche am größten und bei der dritten Suche am kleinsten. Die Bewertungsfunktion der dritten Tiefensuche darf auch fehlerhafte Heuristiken enthalten. Die erste und zweite Tiefensuche haben die schweren Fälle wie Schachmatt oder Materialverlust schon gefunden.

Die Strategie des Läuferendspiel (König und zwei Läufer gegen König) ist die Beweglichkeit des König einzuschränken bis eine Mattführung in der Ecke möglich ist. Im Bauernendspiel wird die Quadratregel benutzt um festzustellen welcher Bauer erfolgreich in eine Dame umgewandelt werden kann. Weitere bekannte Endspielstrategien sind die Abdrängung und das Réti Manöver. Diese Endspielstrategien lassen sich als spezielle Bewertungsfunktionen ausprogrammieren. Diese Erweiterungen haben die Endspielschwäche der frühen Schachprogramme überwunden.

Eröffnungsbibliothek

Für den ersten Zug von Weiss gibt es 20 Möglichkeiten: 8 Bauernzüge um ein Feld, 8 Bauernzüge um zwei Felder und 4 Springerzüge. Schwarz hat ebenfalls 20 Möglichkeiten zur Auswahl. Von diesen 20*20 Möglichkeiten werden 1. e4, e5 und 1. d4, d5 am meisten gespielt. Eine Eröffnungsbibliothek katalogisiert den Anfang einer Schachpartie. Wichtig sind die Eröffnungszüge welche Weiss und Schwarz gleiche Chancen für das Mittelspiel lassen. Die Enzyklopädie der Schacheröffnungen ("Encyclopedia of Chess Openings") sortiert mit den ECO-Codes die ausgewogenen Eröffnungen in 5 Bänden. Die ECO-Codes A00 bis E99 entsprechen 500 Gliederungsfächern. Dabei ist die Belegung der Fächer sehr unterschiedlich. Unter A00 werden 14 der 20 Eröffnungszüge abgelegt. Die Damengambits D68 und D69 unterscheiden sich erst ab dem 13. Zug.
500 Eröffnungen bei einer Spieltiefe von durchschnittlich 6 Zügen oder 12 Halbzügen ergibt einen Verzweigungsfaktor 12-te Wurzel aus 500 = 1.68. In einer Baumdarstellung mit 2 Halbzügen pro Baumebene benötigt man dann 2 + 2*2 + 2*2*2 ... + 2^12 = 2^13 -1 = 8191 Speicherplätze für die Eröffnungsbibliothek.
Ein solches Eröffnungswissen vermeidet schlechte Züge in der Eröffnung bei Spieler oder Schachprogramm. Microchess von Peter Jennings zeigt den typischen Damen Wandertrieb aufgrund der Mobilitätsbewertung deutlich: 1.e4 c5  2.Dh5. (Üblich ist die sizilianische Verteidigung mit 2. Sf3). Die Eröffnung 1.e4 e5 2.Sf3 Sc6 3.Lc4 Lc5 4.c3 Sf6 5.d4 xd4 6.xd4 Lb4+ 7.Sc3 Sxe4 8.0-0 Lxc3 9.d5 (italienische Partie - Möller Angriff) spielt Microchess komplett aus der Eröffnungsbibliothek, obwohl Microchess keine richtige Rochade kann - es bewegt nur den König um zwei Felder. Einige Schachcomputer wie die Mephisto Schachschule II konnten die Rochade nur aus der Eröffnungsbibliothek ausführen.
Im Microchess Programm werden für die Eröffnungsbibliothek pro Zug (zwei Halbzüge) nur die Informationen weisse Figur, Nach-Feld weisse Figur und Nach-Feld schwarze Figur abgelegt. Die Eröffnungsbibliothek enthält somit 1.Be4 e5 2.Sf3 c6 3.Lc4 c5 4.Bc3 f6 5.Bd4 d4 6.Bd4 b4 7.Sc3 e4 8.0-0 c3 9.Bd5. Microchess kann genau eine maximal 9 Züge lange Eröffnung speichern. Manche heutige Schachprogramme kennen die komplette Enzyklopädie und noch mehr.

Das einfachste Schachprogramm

Im Internet lassen sich etliche Schachprogramme im Quelltext finden. Das einfachste Schachprogramm

Dan & Kathe Spracklen SARGON

Aus dem Buch "SARGON A Computer Chess Program" von Dan & Kathe Spracklen, 1978, Verlag Hayden kommt die Beschreibung eines klassischen Schachprogrammes:

SARGON is written in Z-80 assembly language using the TDL Macro Assembler. The program occupies 8K of RAM, which includes 2K of data areas, 2K graphics display and user interface, and 4K move logic. The move logic is the heart of SARGON. It is displayed in the block diagram as the set of routines called by FNDMOV (Find Move). FNDMOV controls the search for the computer's best move by performing a depth first-tree search using the techniques of alpha beta pruning. Listed first under FNDMOV's calls on the block diagram is PINFND (Pin Find Routine). PINFND produces a list of all pieces pinned against the king or queen for both white and black. Pinned pieces must be treated carefully when analyzing battles engaged on the chess board, since their attacking power may be an illusion. FNDMOV also calls POINTS (Point Evaluation Routine). POINTS performs a static evaluation and derives a score for a given board position. POINTS takes factors of material, board control, and development into account. Predominant in the evaluation is material. Material scores must be adjusted to reflect unresolved battles on the chess board. It is the function of XCHNG (Exchange Evaluation Routine) to judge the outcome of these unresolved battles. The factors of development and board control are not allowed to dominate the move choice. LIMIT is called to truncate the contribution of those factors to the score.

FNDMOV controls the generation of legal moves by GENMOV (Generate Move Routine). GENMOV produces the move set for all of the pieces of a given color. For each piece in turn, GENMOV calls MPIECE (Piece Mover Routine), which generates all the possible legal moves for a given piece. MPIECE itself calls a series of routines. PATH generates a single possible move for a given piece along its current path of motion. ADMOVE adds a move to the move list. CASTLE and ENPSNT (En Passant Pawn Capture Routine) handle the special moves. After MPIECE has produced all legal moves, GENMOV calls INCHK, which determines whether or not the king is in check.

Basic to the success of alpha beta pruning is the sorting of moves generated at each ply level. FNDMOV calls SORTM (Sort Routine) to accomplish this task. A sort is dependent on an evaluation, so SORTM calls EVAL (Evaluation Routine). To evaluate a given move on the move list, EVAL first makes the move on the board by calling MOVE. It is determined if the move is legal by calling INCHK. Then, if the move is legal, it is evaluated by calling PNFND and POINTS. Finally, EVAL restores the board position by calling UNMOVE.

The bookkeeping required by alpha beta pruning is for the most part coded in line in FNDMOV. However, FNDMOV calls ASCEND (Ascend Tree Routine) to adjust all the parameters in transferring the parameters up one ply in the tree.

At the bottom of FNDMOV's call list on the block diagram is BOOK. BOOK provides, an opening book of a single move. lf white, SARGON will play P-K4 or P-Q4 at random. If black, SARGON replies to any opening move with P-K4 or P-Q4, whichever is most appropriate.

The move selection logic of FNDMOV is embedded in a whole network of routines that forms SARGON's interface to the outside world. The DRIVER routine initiates and coordinates, the entire game. First on the block diagram in DRIVER's list of calls is CHARTR (Accept Input Character). CHARTR is a totally machine-dependent input routine whose sole purpose is to accept a single character input from the keyboard. All machine-dependent aspects of SARGON have been isolated in this manner to simplify conversion to Z-80 machines running under different operating systems. Machine-dependent code appears in only two other places. The first is the macro definition area, where all the output functions are listed, and the second is in the routine DSPBRD (Display Graphics Board and Pieces), where machine-dependent lines of code are clearly marked.

Next on the block diagram is ANALYS (Set Up Position for Analysis). ANALYS allows the user to set the board to any position of his choosing. The routine blinks the graphics board squares in turn, allowing the user to input a piece ofhis choice or leave the contents unchanged. When the board has been set to the desired arrangement of pieces, play of the game may be resumed. ANALYS also provides a handy means of correcting a move entered by mistake.

As a part of game initialization, DRIVER calls INTERR (Interrogate for Ply and Color). INTERR questions the player for his choice of white or black, and allows him to select the depth of search. DSPBRD and INITBD complete initialization by setting up the graphics board display and internal board array. PGIFND (New Page if Needed) and TBCPCL (Tab to Computer's Column) are used to control spacing in the move list. The move list is displayed to the left of the graphics board on the video screen.

The most important routines called by DRIVER are, of course, CPTRMV and PLYRMV, which are control routines for the computer's and player's moves, respectively. Central to CPTRM V is FNDMOV, the logic to select the computer's move, which has already been discussed. Below FNDMOV on the block diagram is FCDMAT (Forced Mate Handling). If the computer is checkmated, it acknowledges the fact with a message displayed in the move list and by tipping over its king. Assuming the computer is not mated, MOVE makes the chosen move on the board array and EXECMV displays it on the graphics board. In displaying the move, the piece first blinks a few times, moves to its new location, and then blinks a few times again. The function of BITASN (Board Index to ASCII Square Name) is to convert the internal move into a representation in algebraic chess notation on the move list, then INCHK determines whether or not the computer should call "Check."

When the opponent is on the move, PLYRMV controls the events. It calls CHARTR to accept the move entry. ASNTBI (ASCII Square Name to Board Index) converts the move to internal representation. Then VALMOV checks the player's move for validity. If the move is legal, EXECMV displays it on the graphics board as in CPTRMV. PGIFND (New Page if Needed) and TRPLCL (Tab to Player's Column) control spacing in the move list.



Bild: Calltree von Sargon

Weitere Schachprogramme im Quelltext

Auf  WBEC Ridderkerk gibt es eine Rankinglist von Schachprogrammen. Über die Download Seite findet man die im Quelltext verfügbaren Schachprogramme in C/C++:
Rank Program:                Rating  +   - games score    Av.Opp draws Lang.GUI    Lizenz 
3 Fruit X060620a 2852 63 61 92 64% 2754 28% C++ UCI GPL
8 Glaurung 1.2-X64 2779 57 57 92 53% 2757 46% C++ UCI GPL
12 Scorpio 1.8 2747 59 59 92 48% 2758 36% C++ xboard own
24 Crafty 20.13BH-x64 2664 60 59 88 62% 2589 40% C xboard freeware
76 Phalanx XXII 2455 18 18 1084 48% 2467 25% C xboard GPL
101 Resp 0.19 2349 19 19 1020 48% 2360 25% C++
138 GNUChess 4TM 2215 29 29 444 52% 2198 21% xboard
176 GNU Chess 5.00+ 2022 76 77 60 48% 2035 20% xboard
247 TSCP 1.81 1655 41 41 272 47% 1675 15% C xboard

Bayesian Elo Ratinglist WBEC Ridderkerk after edition 15:

Rank Program: Rating + - games score av.Opp draws
3 Fruit 2.3.4n-x64 2962 67 63 92 73% 2795 26%
7 Glaurung 2.01-x64 2858 61 59 92 60% 2800 37%
12 Scorpio 2.0-x64 2794 60 61 92 48% 2803 32%
42 Crafty 22.0-x64 2630 65 69 92 26% 2810 24%
95 Phalanx XXII Reb 2434 62 61 92 51% 2428 25%
120 Resp 0.19 2342 17 17 1232 47% 2363 26%
160 GNUChess 4TM 2207 27 26 528 52% 2193 21%
194 GNU Chess 5.00+ 2014 76 77 60 48% 2028 20%
235 Amundsen 0.60ja 1846 136 143 25 46% 1876 4%
236 micro-Max 4.8-m 1845 143 142 25 56% 1752 8%
278 TSCP 1.81 1662 37 38 328 44% 1701 15%
302 Cefap 0.7.2 1455 53 55 161 36% 1588 16%

Einfache Schachprogramme mit graphischer Oberfläche

Das WinBoard (XBoard) Programm stellt für Schachprogramme (chess engines) eine graphische Oberfläche zur Verfügung. Einmal für Mensch/Maschine Spiele, aber auch für das Schach Spiel zwischen zwei Schachprogrammen. WinBoard enthält GNUChess als Schachprogramm. Weitere Schachprogramme lassen sich über die winboard.ini Datei leicht einbinden. Die einfachen Schachprogramme TSCP, Micro-Max und MiniMAX gibt es mit WinBoard Schnittstelle.
Ohne WinBoard laufen die MiniMAX Versionen DelphiMAX und MyMAX.

Weitere Internet Links

Das SARGON CMD für TRS-80 und das Channel F BIOS ROM stammt von Planetemu.
Das System 80 (TRS-80 Clone) ROM stammt von Dick Smith.
Das TRS-80 Model 3 ROM stammt aus dem TRS-80 Emulator von Matt Hamilton.
Das Atari VCS 2600 Videochess ROM stammt von AtariAge.
Das Channel F Schach ROM stammt von der Channel F Info Seite aus dem Multi Game ROM.
Improving a Chess Classic beschreibt die Entwicklung von Sargon 2 zu Sargon 3.

Literatur

Schach ist ein altes Spiel. Die deutsche Übersetzung der Philidor Einleitung von 1754 ist heute noch lesenswert. Die heute klassischen Einleitungen in das Schachspiel von Tarrasch oder Nimzowitsch erschienen 1931. Computerschach hatte seine Blütezeit zwischen 1970 und 1990. Die Bücher gibt es im Antiquariat oder als Nachdrucke.

Colditz, Karl; Lehr-, Übungs- und Testbuch der Schachkombinationen; Edition Olms, 1992; ISBN 978-3-283-00302-9

Frey, Peter W.; Chess Skill in Man and Machine; Springer-Verlag, 1977, 1978, 1983; ISBN 3-540-90790-4

Kmoch, Hans; Pawn Power in Chess; David McKay Company, 1959; Dover Publications, 1990; ISBN 0-486-26486-6

Levy, David; Computer Chess Compendium; Springer-Verlag, 1988; Ishi Press International, 2009; ISBN 4-87187-804-X
Enthält Artikel von Vigneron, Shannon, Turing, Prinz, Bernstein, Newell, Kotok, Greenblatt, Adelson-Velskiy, Atkin, ...

Levy, David; Newborn, Monty; How Computers play Chess; Freeman & Company 1991; Ishi Press International 2009; ISBN 4-87187-801-5

Liffick, Blaise W.; The BYTE Book of Pascal; BYTE Publications, 1979; ISBN 0-07-037823-1
Enthält den Quelltext von CHESS 0.5 in Pascal

Nimzowitsch, Aaron; Mein System; A. Siedentop Verlag, 1931; Jens-Erik Rudolph Verlag, 2010; ISBN 978-3-941670-19-8

Nunn, John; Einführung in die Schachtaktik; Gambit Publications, 2004; ISBN 1-904600-11-5

Pfleger, Helmut; Kurz, Eugen; Treppner, Gerd; Schach Zug um Zug; Bassermann Verlag, 2004; ISBN 978-3-8094-1643-2

Philidor, François-André; Stamma, Philipp; Die Kunst im Schachspiel ein Meister zu werden (Analyse du Jeu des Échecs); 1754;
Auf Google Books gibt es das Philidor Buch.

Spracklen, Dan; Spracklen, Kathe; SARGON A Computer chess Program; Hayden Books, 1978; ISBN 0-8104-5155-7
Enthält den Quelltext von SARGON in Z80 Assembler

Steinwender, Dieter; Friedel, Frederic A.; Schach am PC; Markt und Technik, 1995; ISBN 3-87791-522-1
Enthält den Quelltext von MiniMAX in Basic und C

Tarrasch, Dr. Siegbert; Das Schachspiel; Deutsche Buch-Gemeinschaft, Berlin 1931; Jens-Erik Rudolph Verlag, 2009; ISBN 978-3-941670-00-6
Hier ist das Tarrasch Buch online. Dieses Buch ist seit 1931 der Klassiker für den Anfänger.

Reinefeld, Alexander; Spielbaum-Suchverfahren; Springer-Verlag, 1989; ISBN 3-540-50742-6

Andere Computer-Spiele



Bild links: TRS-80, Adventure 01, Scott Adams, Adventure International 1979
Bild mitte: TRS-80, Space Intruders, Doug Kennedy, Adventure International 1980
Bild rechts: TRS-80, Flight Simulator 1, ?, SubLogic 1980



Bild links: Apple 2, Wizardry 1, Andrew Greenberg, Robert Woodhead,  Sir-Tech Software 1981
Bild mitte: Apple 2, Lode Runner, Doug Smith, Broderbund 1983
Bild rechts: Apple 2, Where in the world is Carmen Sandiego, Dane Bigham, Gene Portwood, Lauren Elliot, Broderbund 1985



Bild links: Atari 2600, Galaxian, ?, Atari 1983
Bild mitte: Atari 2600, Pole Position, Doug Macare, Atari 1983
Bild rechts: Atari 2600, Midnight Magic, Glenn Axworthy, Atari 1984



Bild links: Sinclair ZX Spectrum, Deathcase, Mervyn Estcourt, Micromega 1983
Bild mitte: Sinclair ZX Spectrum, Atic Atac, ?, Ultimate Play the Game 1983
Bild rechts: Sinclair ZX Spectrum, Tetris, Alexey Pazhitnov, 1986



Bild links: Commodore C64, Pitstop II, Stephen Landrum, Dennis Caswell, Epyx 1984
Bild mitte: Commodore C64, Suicide Express, Tony Crowther, Gremlin 1985
Bild rechts: Commodore C64, Turrican, Manfred Trenz, Rainbow Arts 1990



Bild: SNES, Legend of Zelda: A Link to the Past, Nintendo 1992
Bild: SNES, Wizardry 1-2-3 Story of Llylgamyn auf ZSNES Emulator, Andrew Greenberg, Sir-Tech, ASCII 1992
Bild: SNES, Final Fantasy 6, Square 1994