Computer Schach

Autor: Andre Adrian
Version: 29.Juli.2009

Einleitung

"Schach 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. Eine dritte Gruppe von Menschen läßt Schachprogramme gegeneinander spielen
Diese Seite stellt frühe Schachprogramme vor. Zum Selber-Spielen Mensch gegen Maschine oder Spielen-Lassen zwischen zwei Schach-Programmen.
Neu ist der Selbstbau Schachcomputer SHAH ein Gerät ähnlich dem CompuChess von 1977, aber mit aktueller Hardware und Schachprogramm in C. Die Zeitschrift Elektor und der ComputerClub 2 haben den Selbstbau Schachcomputer zum Schachzwerg weiterentwickelt.

Konrad Zuse Schach 1942

Konrad Zuse hat 1941 den Digitalrechner Z3 in Relaistechnik gebaut. Zwischen 1941 und 1942 hat er ein Schach Programm entworfen. Das Programm kann die möglichen pseudolegalen Schachzüge erzeugen. Die Bewertungsfunktion sortiert die Züge nach dem Materialgewinn. 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.



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 "Select the variations to be explored by some process so that the machine does not waste its time in totally pointless variations" ist das heute noch verwendete Minimax mit Alpha-Beta Beschneidung, Transposition Hash-Table, Principal Variation Suche, Null-Move Heuristik.
Shannon beschreibt einen Zuggenerator für Schach. Wird aus den legalen Zügen des Zuggenerators ein Zug zufällig ausgewählt 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.

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 was nichts und das Nichts explodierte" 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 des Pflichtenheftes, schrittweise Erweiterung und Komplexitätsreduzierung bei der Entwicklung anderer komplexer Systeme anwenden.

MIT Chess Group Schachprogramm (1959 - 1962)

Alan Kotok hat 1962 das 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.

Microchess Computerschach aus dem Jahr 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 - wie später auch im Commodore PET, Apple II und Commodore C64 verbaut. Programme wurden auf Kassettenrecorder gespeichert. Die Eingabe erfolgte über 23 Tasten, die Ausgabe über eine 6-stellige LED Anzeige. Das Schachprogramm 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 2007 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 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.

SARGON CHESS aus dem Jahr 1978

SARGON von Dan & Kathe Spracklen hat 1978 das Microcomputer Schach Turnier auf der West Coast Computer Fair gewonnen. SARGON lief auf einem Wavemate Jupiter III mit Zilog Z80 Prozessor. 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" vom Verlag Hayden veröffentlicht.
Das Z80 Assembler Listing gibt es hier. Einen Z80 Simulator gibt es hier. Beide Quelltexte ergeben noch kein funktionsfähiges Programm. Vielleicht will ja jemand mithelfen das original SARGON Programm ähnlich wie Microchess wieder ans Laufen zu bringen?
Das SARGON Programm wurde auf die Z80 Computer TRS-80 (U.S.A) und Nascom 1 (England) portiert.



Bild: Hayden Books ISBN 0-8104-51554

TRS-80 SARGON CHESS aus dem Jahr 1978

Der Tandy Radio Shack TRS-80 war 1977 ein erfolgreicher Heimcomputer. Tandy verkaufte 55000 Rechner im ersten Jahr. Die TRS-80 Sargon Portierung benötigt Level 2 BASIC (12KByte ROM). Die Bildschirmauflösung ist 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.

Chess Champion Mk I und Mk II aus dem Jahr 1978, 1979

Im Vergleich zu SARGON ist der 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 cm³).

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 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 aus dem Jahr 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 von 1979

Der Atari 400 (Folientastatur) und 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 PETund 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 VCS Grafik ist 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.
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".

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 725 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

Verbesserungen AVR-Max Programm

Das AVR-Max 4.8 Programm belegt 4968Bytes von 8192Bytes 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.
Interessanter sind hoffentlich die folgenden Erweiterungen.

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

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. 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 oder den Spielfeldrand steht der König nicht im Schach. Ob der König im Patt steht und die Seite am Zug nicht ziehen kann bemerkt die Baumsuche am einfachsten.

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.

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 ist der Designer der Intel CPUs 4004, 8008, 8080 und der Zilog Z80 CPU. Bei Fairchild hat Faggin vorher den 3708 entwickelt, den ersten Chip in Slilizium Gate MOS (Metal Oxid Semiconductor) Technik, einen 8-fach Analogmultiplexer wie der heutige 74HC4051.
Chuck Peddle hat bei der Entwicklung des Motorola 6800 mitgearbeitet. Bei MOS Technology ist er der Chefentwickler des 6502. Der 6502 ist zuerst eine Niedrigpreisalternative zu 6800 und 8080. Später zeigt sich das der einfache "Opcode Fetch" Zyklus des 6502 gut mit dem Video-Refresh und DRAM-Refresh von grafikfähigen Computern wie Apple II und Commodore C64 harmoniert. Der 6502 ist 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 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.

TRS-80 SARGON-II aus dem Jahr 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 von 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 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. Die Brettdarstellung verwirrt etwas. Das Feld A1 links unten ist normalerweise dunkel. 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.

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 aus dem Jahr 1983, 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 aus dem Jahr 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 aus dem Jahr 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 aus dem Jahr 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 70 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. 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.

• Befehlsausführzeit in Maschinenzyklen (opcode execution time in clocks). Die RISC CPU ATMega führt einfache Befehle wie "Erhöhe Register um 1" in einem Machinenzyklus aus. Die CISC CPU H8 benötigt zwei Maschinenzyklen für die einfachsten Befehle. Einfache Befehle in einem Maschinenzyklus auszuführen ist das deutlichste RISC Merkmal.
  
• Anzahl Register. Register sind Zwischenspeicher in der Nähe des Rechenwerkes. Der RISC ATmega hat 32 Register mit 8Bit Breite, der CISC H8 hat 8 Register mit 16Bit Breite. Viele Register sind ein RISC Merkmal.
• Komplexe Adressierungsarten. Eine typische CISC CPU hat das Befehlswort "Erhöhe den Inhalt einer Speicherzelle um 1". Eine RISC CPU benötigt für diese Aufgabe drei Befehlsworte: "Lade Register mit Inhalt der Speicherzelle", "Erhöhe Register um 1" und "Speichere Inhalt des Registers in die Speicherzelle". ATMega und H8 sind RISC bezüglich Adressierungsarten.
• Länge der Befehlsworte. Typisch für CISC sind Befehlsworte unterschiedlicher Länge. Eine RISC CPU hat oft nur eine einzige Befehlswortlänge. Die 8-Bit CISC Typen Z80 oder 6502 haben Befehlsworte (Opcodes) deren Länge bei 8-Bit beginnt. Bei ATMega und H8 beginnt die Befehlswortlänge eher RISC mäßig bei 16Bit.
  

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.

Historie

Die Computerschach Historie läßt sich nach den Anfängen bis 1958 in zwei Abschnitte gliedern. Einmal die Zeit der "Brute Force" Programme und spezieller Schach-Hardware die nur mit backward pruning (Alpha-Beta Beschneidung) arbeiten. Dann in die Zeit der "selektiven" Programme die zusätzlich mit forward pruning (Null-Zug Suche) arbeiten. Der Schach Weltmeister Michail Botwinnik ist mit seinem selektiven Schachprogramm PIONEER-1 gescheitert. Kurz vor Botwinnik's Tod 1995 begann 1993 der erfolgreiche Siegeszug der selektiven Schachprogramme mit Quest von Frans Morsch. Deep Fritz von Frans Morsch besiegte 2006 den amtierenden Weltmeister Kramnik. Nicht das Schach-Hardware Monster Deep Blue sondern zwei Intel Core 2 Duo CPUs genügten um acht Millionen Stellungen pro Sekunde zu berechen und damit eine Suchtiefe von etwa 17 bis 18 Halbzügen im Mittelspiel zu erreichen.

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.
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 MacHack 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 Schachprogramm welches nicht mit Brute Force arbeitet. Er scheitert.
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 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    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.

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	849
Fairchild F8, 1975, 8bit	Data Cash Systems CompuChess, 1977	D. B. Goodrich and Associates	725
MOS Technology 6504, 1975, 8bit	Commodore Chessmate, 1978	Peter Jennings	?
Zilog Z80, 1976, 8bit	Fidelity Chess Challenger 10, 1978	Ron Nelson	1156
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	1205
GI CP1610, 1975, 16bit	Mattel Intellivision USCF Chess, 1981	Teletape, Inc., Russ Ludwick	?
RCA 1802, 1976, 8bit	Mephisto III, 1983	Thomas Nietsche, Elmar Henne	1556
Motorola 68000, 1979, 16bit	Mephisto Excalibur, 1983	Thomas Nietsche, Elmar Henne	?
Hitachi 6301, 1983, 8bit	CXG Star Chess, 1985	Kaare Danielson	1264
Intel 80C50, 198?, 8bit	Fidelity The Gambit, 1987	Ron Nelson	1060
Hitachi HMCS40, 198?, 4bit	CXG Sphinx Chess Card, 1989	David Levy, Mark Taylor	890
Motorola 68HC05, 198?, 8bit	Saitek Traveller, 1991	Craig Barnes	?
Acorn ARM, 1986, 32bit	Mephisto Risc 1MB, 1991	Ed Schröder	2256
Hitachi H8, 1990, 8/16bit	Saitek GK 2000, 1992	Frans Morsch	1988
Sun SPARC, 1987, 32bit	Saitek Sparc, 1993	Dan & Kathe Spracklen	2187
Motorola 68030, 1987, 32bit	Mephisto Genius London 68030, 1994	Richard Lang	2319

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 hat Scisys Turbostar 432 KSO (4MHz Takt, 40KByte ROM, 8KByte RAM) mit einem Programm von Julio Kaplan 1783 Elo Punkte erreicht und 1991 hat Mephisto Milano (4.9MHz Takt, 32KByte ROM, 8KByte RAM) mit einem Programm von Ed Schröder sogar 2022 Elo Punkte erreicht. Eine ähnliche Leistung von 2036 Elo holt das David Kittinger Programm im Novag Obsidian aus einer H8 CPU mit 16MHz, 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 wurde wohl aufgrund des niedrigen CPU 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 und Mattel Intellivision enthalten zusätzlichen RAM Speicher. Die Schach Erweiterung von Interton VC4000 enthält sogar eine eigene Z80 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 Details der einzelnen Beispiele "weggeworfen". Höchstwahrscheinlich ist für "rule extraction" nicht nur Lernen im Sinne von Beispiel-Ansammeln und Sortieren 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 menschlichen Gehirn und Schachprogramm. Vielleicht laufen die Funktionen Variantenbildung, Baumsuche und Bewertung auf einer unbewußten Ebene ab. Diese Funktionen bilden vielleicht das Fundament für die Regelextraktion.
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 mit Hilfe einer wissenschaftlichen Regelextraktion 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".

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.

Für Dame, Turm, Läufer oder Springer berechne:

1. Die Quadratwurzel aus der Anzahl der Züge, die eine Figur von der Position aus machen kann, wobei Schlagen als 2 Züge bewertet wird und beachtet werden muß, daß der König nicht im Schach stehen darf.
2. (Wenn nicht die Dame) 1.0, wenn die Figur gedeckt wird, und zusätzlich 0.5, wenn sie zweimal gedeckt wird.

Für den König berechne:

1. Für Züge außer der Rochade wie in 1. oben.
2. angenommen, der König wird durch eine eigene Dame auf dem selben Feld ersetzt, dann berechne wie in 1. oben, aber subtrahiere statt addiere den ermittelten Wert.
3. Zähle 1.0 für die Möglichkeit der späteren Rochade, dadurch daß weder König noch Turm bewegt wurden, weitere 1.0, wenn die Rochade im nächsten Zug durchgeführt werden könnte, und ebenfalls 1.0 für das tatsächliche Rochieren.

Fur einen Bauern berechne:

1. 0.2 für jeden Schritt nach vorne
2. 0.3 für Deckung durch mindestens eine Figur (nicht Bauer)

Für den schwarzen König berechne:

1. 1.0 für das Androhen von Schachmatt.
2. 0.5 für Schach.

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 Bwertung von Microchess von Peter Jennings ist umfangreicher. Die Details stehen im Programmer' Manual. Die Bewertung ist

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)
  

VALUE  =  VALUE  +  02, A position bonus if the move is to the

                        centre or out of the back rank.



VALUE = 00,  If the move is illegal because  the  king  is  in

                        check.



VALUE = FF,  If the move results in a checkmate.

  

Die Werte sind:

MOB      Mobility.  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.

  

        

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

Die Brute Force Methode (Tiefensuche mit Materialbewertung) ist für das taktische Spiel eines Schachprogrammes verantwortlich. Heute übersieht der Computer kein Matt-in-N-Zügen mehr. In manchen Endspielsituationen genügt Tiefensuche allein nicht. Hier sind strategische, positionelle Bewertungsfunktionen gefragt. Diese Bewertungsfunktionen dürfen auch fehlerhafte "Faustformeln" sein. Die Tiefensuche erkennt Fehler in der Heuristik.

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

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

Dieter Steinwender, Frederic A. Friedel; Schach am PC; Markt und Technik; 1995; ISBN 3-87791-522-1

Andere 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