Computer-Schach
Autor: Andre Adrian
Version: 2019-08-10
Einleitung
Die ersten elektronischen Computer entstanden Ende der
1940er Jahre. Seit dieser Zeit wird über Schachprogramme
nachgedacht. Computer-Schach wird oft dargestellt als Wettstreit
zwischen dem "Elektronengehirn" und dem menschlichen Gehirn. In
Wirklichkeit ist es eine Auseinandersetzung zwischen den Ideen
eines Programmierers, welche von einem Computer ausgeführt werden,
und den Ideen eines menschlichen Schachspielers.
Schach selbst spielen oder Schach spielen lassen, das ist hier die
Frage. Einige Menschen sind vorzügliche Schachspieler. Andere
Menschen schreiben Schachprogramme. Die Programm-Autoren sind oft
Schachpatzer. Interessant ist auch das Spiel zwischen zwei
Schachprogrammen. Spielen zwei leistungsschwache Programme
gegeneinander, so endet die Partie oft in einer
Stellungswiederholung. Jedes Programm entwickelt sein Spiel bis
zur Grenze seiner Fähigkeiten und verharrt dann dort.
Diese Seite stellt etliche Schachprogramme vor. Besonders die Zeit
der frühen Mikrocomputer von 1976 bis 1984 wird behandelt. Dank
dem Internet sind viele Programme von damals noch vorhanden und
lassen sich per Emulator auf aktuellen Computern ausführen.
Vorgestellt wird auch der Selbstbau Schachcomputer
SHAH, ein Gerät ähnlich dem CompuChess von 1977, aber mit
aktueller Hardware und Schachprogramm in C. Die Zeitschrift
Elektor vertreibt den Bausatz als AVR-Max
Schachcomputer. In einer Folge des ComputerClub 2 wurde der
Schachcomputer sogar vorgestellt.
Überblick
Die Computerschach Historie läßt sich in mehrere
Abschnitte unterteilen. Die erste Schach spielende Maschine war
der elektromechanische Schachautomat von Torres y Quevedo aus dem
Jahr 1914. Dies war eine fest verdrahtete Logik in Relais-Technik
welche nur einen kleinen Teil des Schachspiels beherrschte. In der
Zeit vor 1951 gab es noch keine Computer welche leistungsfähig
genug waren um ein Schachprogramm auszuführen. In dieser Zeit
haben Computerpioniere wie Zuse, Shannon und Turing Grundlagen für
die folgenden Programme gelegt. Die von Shannon 1950
vorgeschlagene A-Strategie wurde als "brute force" Methode
bekannt, die Shannon B-Strategie als "forward pruning".
Zwischen 1951 und 1977 war die Blütezeit der Großrechner
(Mainframes). Groß war der Raumbedarf dieser Computer, die
Rechenleistung war nach heutigen Maßstäben eher klein. Um die
kleine Rechenleistung gut zu nutzen wurden bei der Baumsuche nicht
alle möglichen Züge verfolgt. Die selektiven Schachprogramme mit
"forward pruning" waren zwischen 1958 und 1973 vorherrschend. Von
üblicherweise 35 möglichen Zügen in der Eröffnung und im
Mittelspiel wurden bei einem selektiven Schachprogramm oft nur 8
untersucht. 1974 zeigte das russische Programm Kaissa die Leistung
welche in einem intelligenten "brute force" Schachprogramm steckt.
Kaissa rechnete nicht brutal alle Züge durch, sondern rechnete nur
einen beschnittenen Suchbaum. Welche Teile des Suchbaums nicht
besucht wurden bestimmte aber nicht eine "forward pruning"
Bewertungsfunktion, sondern diese Information stammte aus der
Baumsuche selbst. Wenn bei einem Schachprogramm mit
Vorwärts-Beschneidung die Bewertungsfunktion versagt, dann spielt
das Programm schlecht. Versagt bei einem Schachprogramm mit
vollständiger Baumsuche und Alpha-Beta Beschneidung die
Zugsortierung, dann spielt das Programm langsam. Der grösste
Durchbruch im Computerschach dürfte die Einführung von Alpha-Beta
Beschneidung, schrittweise Vertiefung (iterative Deepening) mit
Zugsortierung und Transpositions-Tabelle (hash table) gewesen
sein.
Ab 1976 begann die Zeit der persönlichen Computer, welche bis
heute anhält. Mit Microchess auf dem KIM-1 und SARGON auf dem
TRS-80 wurde Computerschach verfügbar für deutlich mehr Menschen
als zur Zeit der Mainframe-Schachprogramme. Neben Computerschach,
d.h. Schach auf einem universellen Computer, entstanden zu
gleichen Zeit die Schachcomputer, Computer welche nur für das
Schachspiel geeignet waren. Die Nachfolge der
Mainframe-Schachprogramme traten 1978 mit Belle die
Schachprogramme mit Spezialhardware an. Einfache Berechnungen, die
aber sehr häufig ausgeführt werden mussten, wie das Erzeugen der
möglichen Spielzüge, wurden nicht mehr in Software ausgeführt,
sondern in Hardware.
Im 21. Jahrhundert wurden die Schachprogramme mit Spezialhardware
wieder von Schachprogrammen auf normalen Computern überholt. Das
Gigahertz-Wettrennen der Hersteller von PCs lieferte eine hohe
Rechenleistung. Diese Rechenleistung wurde durch mehrere
Rechenkerne pro Computer noch gesteigert. Neben mehr MIPS
(Millionen von Rechenoperationen pro Sekunde) gab es auch weitere
Verbesserungen bei der Beschneidung des Suchbaums. Die
Programmierer hatten endlich das Ziel erreicht, bei der Baumsuche
in einem schmalen Baum nicht mehr die interessanten Züge zu
übersehen. Ab 2006 ist ein handelsüblicher persönlicher Computer
mit dem entsprechenden Schachprogramm in der Lage den menschlichen
Schachweltmeister zu schlagen.
Für die Künstliche Intelligenz Forschung hat die Beschäftigung mit
Computerschach eine durchwachsene Bilanz hinterlassen: Ein, für
den Menschen, einfach zu lernendes Spiel zeigt sich für den
Programmierer als eine Herkules-Aufgabe. Schach-Spielen ist für
den Menschen leicht, die Umsetzung dieser Fähigkeit in ein
Computerprogramm aber schwierig. Einsicht in die Funktionsweise
der menschlichen Denkprozesse haben die Schachprogramm kaum
gegeben. Schach zwischen Mensch und Computer hat die enorme
Leistungsfähigkeit des menschlichen Gehirns gezeigt.
Die automatische Übersetzung von geschriebenen Text von einer
menschlichen Sprache in eine andere Sprache ist ein weiteres
schwieriges Gebiet der KI Forschung. Vielleicht gelingt
automatisches Übersetzen in der Qualität von menschlichen
Übersetzern, vielleicht auch nicht. Beim Thema Computerschach war
die Frage lange ungeklärt ob der Computer einmal so gut Schach
spielen wird wie der menschliche Schachweltmeister.
Historie
1913
Ernst Zermelo
beweisst den Minimax Algorithmus für Schach.
1914
Leonardo
Torres
y Quevedo zeigt den elektromechanische Automaten
El
Ajedrecista für das König Turm gegen König Endspiel.
1942 Konrad Zuse beschreibt einen
Schach
Zuggenerator in der Programmiersprache Plankalkül.
1949 Claude Shannon benutzt den Minimax Algorithmus
in
"Programming
a
Computer
for Playing Chess"
1951 Der erste kommerzielle Computer
Ferranti Mark 1
kann Matt-in-2-Zügen Aufgaben lösen. Programmautor ist
Dietrich
Prinz.
1953 Alan Turing
"Could
one
make
a machine to play chess?" definiert ein Schachprogramm als
Papiermaschine.
1958 Allen Newell, Herbert Simon and Cliff Shaw
programmieren NSS, das erste Schachprogramm mit Alpha-Beta
Beschneidung Suche.
1962 Alan Kotok dokumentiert in seiner
Bachelor Thesis
(Prof. John McCarthy) das MIT Chess Group Schachprogramm.
1967 Richard Greenblatt vom MIT verbessert das
MIT Programm zu Mac Hack VI und errreicht 1400 Elo Punkte.
1969 Albert Zobrist beschreibt
Transposition
Hash-Tables in "A Hashing Method with Applications for Game
Playing".
1970 Michael Botwinnik beginnt mit Pionier 1,
einem selektiven Schachprogramm. Das Programm ist bei seinem Tod
immer noch nicht fertig.
1970 CHESS 3.0, ein selektives Schachprogramm
von Atkin, Gorlen und Slate gewinnt die erste
US
Computer Chess Championship.
1974 Das russische Schachprogramm Kaissa mit
einem brute Force Algorithmus gewinnt gegen das U.S.A.
Schachprogramm CHESS.
1975 CHESS 4.4, ein brute-force Schachprogramm
von Atkin und Slate gewinnt die sechste US Computer Chess
Championship.
1976 Peter Jennings verkauft
Microchess
für den
KIM-1
im Quelltext für $10. Dem 1.1KByte Programm fehlt Rochade, En
Passant, Bauernumwandlung.
1977 Der Fidelity Chess Challenger 1 mit
Programm von Ron Nelson ist der erste Schach Microcomputer (2MHz
8080) mit 985 Elo Punkten.
1977 Der CompuChess mit Programm von D. B.
Goodrich and Associates wird als Chess Champion Mk I geklont. Es
gibt einen Gerichtsfall.
1978 Ken Thompson und Joe Condon von den Bell Labs
entwickeln den Schach Computer Belle. Belle schlägt mehrere Jahre
alle anderen Schachcomputer.
1978 Der Internationale Meister David Levy
gewinnt seine 10-Jahres-Wette gegen das Programm CHESS 4.7.
1980 Der
Fidelity
CC Champion mit Programm von Dan & Kathe Spracklen
gewinnt die erste Microcomputer Weltmeisterschaft mit 1550 Elo
Punkten.
1981 Das Programm Cyrus von Richard Lang (später im
CXG
Chess 2001) gewinnt die Computerschach Europameisterschaft
mit ebenfalls 1550 Elo Punkten.
1983 Belle erreicht Meister Niveau mit 2250 Elo
Punkten.
1985 Richard Lang entwickelt für Hegener +
Glaser
Mephisto Schachcomputer Programme. Mephisto gewinnt bis 1990
alles in seiner Klasse.
1989 Alexander Reinefeld beschreibt NegaScout
(Principal Variation Search) im Buch "Spielbaum-Suchverfahren".
1989 Deep Thought von
Feng-hsiung
Hsu (Carnegie Mellon Universität) erreicht Grossmeister
Niveau mit 2400 Elo Punkten.
1993 Christian Donninger veröffentlicht "Null
move and deep search: Selective search heuristics for obtuse chess
programs"
1994 Mephisto London 68030 mit 2302 Elo Punkten
von Richard Lang besiegt Weltmeister Garry Kasparov mit 1.5:0.5 in
zwei 25 Minuten Partien.
1996 Schachprogramm Deep Blue gewinnt eine
Partie gegen Weltmeister Kasparov, verliert aber das Turnier mit
4:2.
1997 Ein verbesserter Deep Blue gewinnt das
Turnier gegen Garry Kasparov mit 3.5:2.5. Die Hardware besteht aus
32 RS/6000 und 256 Schach ICs.
1997 IBM lehnt einen Revanche Kampf gegen Deep
Blue ab. Kasparov fühlt sich betrogen (
Link).
2002 Omid David-Tabibi und Nathan Netanyahu
veröffentlichen "
Verified
null-move pruning"
2003 Kasparov spielt 3:3 gegen
Deep
Junior 7 von Amir Ban and Shay Bushinsky. Die Hardware
besteht aus 4 Pentium 4 CPUs mit 1.9GHz.
2006 Weltmeister Wladimir Kramnik verliert gegen
Deep
Fritz 2:4. Ein Höhepunkt ist der menschliche Fehler in der
2. Partie - ein
einzügiges
Matt.
Von Bill Wall gibt es eine
Computer
Chess History in englisch. Eine umfangreiche Historie findet
sich im
Computer
History Museum.
Torres y Quevedo, Endspielautomat, 1914
Der spanische Ingenieur Torres y
Quevedo baute den ersten Schachautomaten. Dieser Automat spielte
das König und Turm gegen König Endspiel. Der Algorithmus wurde mit
einer fest verdrahteten Relaisschaltung realisiert. Neben der
Berechnung der Züge konnte der Automat auch die Züge ausführen.
Ein Greifarm hob die Spielfigur vom Schachbrett, bewegte sie und
stellte sie wieder ab. Der menschliche Gegner bewegte seinen
König. Diese Bewegung wurde ebenfalls von dem Schachautomaten
erkannt. Der Schachautomat wurde 1914 in dem mechanischen Labor
der Sorbonne gezeigt. Torres y Quevedo baute 1922 einen zweiten
Schachautomaten. Bei diesem Modell wurden die Spielfiguren durch
eine Mechanik unterhalb des Schachbrettes bewegt. Dieses Modell
befindet sich heute im Museum des polytechnischen Institutes in
Madrid.
Der Algorithmus bewegt entweder den Turm oder den König um ein
Feld in Richtung feindlichen König. Selbst ein Anfänger im
Schachspiel dürfte schneller Matt setzen als der Schachautomat,
solange der Anfänger nicht in die Patt-Falle gerät.
Der Schachautomat von Torres steht in der Tradition von Automaten
des 18. und 19. Jahrhunderts welche menschliche Tätigkeiten wie
Schreiben, Malen und Musizieren ausführten. Diese Automaten wurden
von einem Federwerk angetrieben. Die Feinmechanik dieser Automaten
ist bewundernswert. Der Torres Automat geht einen deutlichen
Schritt weiter. Es wird nicht ein sequentielles Programm
ausgeführt, sondern der Automat reagiert auf seine Umwelt. Torres
y Quevedo hat eine grosse Ingenieurleistung vollbracht. Er hat
nicht nur den Algorithmus für das KRK Endspiel formuliert, sondern
er hat auch einen funktionsfähigen Automaten gebaut.
Bild: Torres y Quevedo Algorithmus für KRK Endspiel-Automat, aus
der Zeitschrift BYTE, Ausgabe September 1978, Seite 86.
Konrad Zuse, Zuggenerator, 1942
Konrad Zuse baute 1941 den Digitalrechner Z3 in
Relaistechnik. Zwischen 1941 und 1942 entwarf er ein Zuggenerator
Programm. Das Programm konnte die möglichen pseudolegalen
Schachzüge erzeugen. Eventuell hat Zuse über eine Baumsuche oder
über ein Programm für das König, Turm, König Endspiel nachgedacht.
Diese Ideen sind in den 1940er Jahren nicht veröffentlicht worden.
Konrad Zuse hatte mit Plankalkül eine frühe Programmiersprache
entwickelt. Das Buchmanuskript von 1945 wurde erst 1972
veröffentlicht. Zu diesem Zeitpunkt hatte Plankalkül keine
Auswirkung mehr auf die Entwicklung von Programmiersprachen. Im
Zuse Internet Archiv findet sich das Kapitel über Schach
im
Plankalkül
Manuskript sowie ein späterer Artikel über Plankalkül
und Schach.
In einem Artikel von 1959 spricht Zuse über die Anwendung der
Datenverarbeitung bei der Flugsicherung: "Es ist z.B. geplant, für
die Aufgaben der europäischen Flugsicherung eine Großrechenanlage
einzusetzen. Die hierbei zu lösenden Probleme sind jedoch so
komplex und schwierig, daß man zunächst einmal auf der Z22 diese
Aufgaben programmiert hat, um die günstigste Struktur der
Programme zu erforschen. Ferner wurde auf der Z22 die Arbeitsweise
einer geplanten Großrechenanlage (TR4, Telefunken) für diese
Zwecke simuliert".
Anmerkung: Die TR4 wurde gebaut und später die TR86. Beide wurden
für die Flugsicherung in Deutschland eingesetzt. Der Autor durfte
selbst noch eine TR86 in Funktion bewundern als er 1991 bei der
Flugsicherung begann. Von Wolfgang Pavel gibt es einen Z22 Simulator.


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

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

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

Bild: Robot Chess Matt in 2 Zügen, Weiss am Zug. Die Lösung ist 1.
Th6 gxh6 2. g7#.
We grow Systems - Exkurs zum Thema Entwicklung
Heil den unbekannten
Höheren Wesen,
Die wir ahnen!
(Goethe, Das
Göttliche)
Claude Shannon beschreibt einen wichtigen Unterschied
zwischen Mensch und Computer: "It is possible to give a person one
or two specific examples of a general situation and have him
understand and apply the general principles involved. With a
computer an exact and completely explicit characterization of the
situation must be given with all limitations, special cases, etc.
taken into account."
Dem Menschen genügen wenige, oft unvollständige Beispiele um die
Generalisierung anzuregen. Dem Computer fehlt diese Eigenschaft
und alles muß haarklein erklärt werden. Dieser nüchterne Blick des
Wissenschaftlers Shannon ist die wohltuende Sicht der Vernunft. In
den 1950er Jahren wurden vom Elektronengehirn Wunder erwartet -
manche Chefs erwarten diese Wunder noch heute.
In der Zwischenzeit ist das Übertragungsproblem zum ständigen
Begleiter des Systementwicklers geworden. Menschen können ohne
besondere Schwierigkeiten ihre Tätigkeiten ausführen. Eine
Automatisierung scheitert weil die Beschreibung der Tätigkeiten
nicht präzise genug für den Computer gelingt. Siehe auch den Unvollständigkeitssatz
von Kurt Gödel oder das Halteproblem
von Alan Turing.
Wahrscheinlich ist es dem Menschen sogar unmöglich nicht zu lernen
- die Konditionierung
ist ein Beispiel dafür. Shannon schreibt auch über das lernende
Schachprogramm: "Some thought has been given to designing a
program which is self-improving but, although it appears to be
possible, the methods thought of so far do not seem to be very
practical.". Bis heute ist die Künstliche Intelligenz Forschung
über das "not very practical" nicht weit hinausgekommen. Der
Unvollständigkeitssatz läßt sich philosophisch interpretieren als
"ein System kann sich nicht selbst erklären" mit der Anwendung
"der Mensch kann seine Lernfähigkeit nicht erklären" und deshalb
nicht in ein Computerprogramm übertragen.
Andererseits ist die natürliche Intelligenz mit ihrer
Lernfähigkeit irgendwie entstanden. Die übliche Hypothese ist
Entstehung durch Mutation und Selektion, d.h. durch Wechselwirkung
zwischen einfachem Lebewesen und komplizierter Umwelt. Vielleicht
läßt sich eine künstliche Intelligenz "mendeln". Wenn das
Universum (die ganze Umwelt) als das komplexere System begriffen
wird, kann das einfachere System sich daran hochentwickeln ohne
gegen den Unvollständigkeitssatz zu verstoßen. Äußere Komplexität
der Umwelt wird durch Evolution umgewandelt in innere Komplexität
des Untersystems Lebewesen. Es gibt auch keinen Widerspruch zur Thermodynamik.
Die Komplexität als Entsprechung der Wärme fließt von der
heißeren, komplexeren Umwelt in das kältere, primitivere
Lebewesen. Die angenommene grosse Komplexität des Weltalls macht
die Entstehung von Lebewesen zwangsläufig. Die Entstehung des
Weltalls kann dieser Exkurs auch nicht erklären. Der "Am Anfang
war das Nichts und das ist dann explodiert" Urknall
ist das grösste Wunder.
Komplizierte Umwelt, einfaches Lebewesen ist die Kernidee. Im
Sinne von "ich
denke, also bin ich" fühlt der Mensch sich vielleicht wohler
wenn "die Krone der Schöpfung" komplizierter ist als alles andere.
Jeder Informatiker lernt aber "don't mess
with Ms. Murphy". Was ist schon der einzelne Mensch in all
seiner Pracht verglichen mit dem Kosmos der auch alle Menschen
beinhaltet? Die Umwelt der Fische besteht zum Großteil aus anderen
Fischen und produziert emergent
behaviour wie Schwarmverhalten
als kollektive
Intelligenz.
Oft heißt es ja "die Zeit war reif" wenn Doppelerfindungen
auftreten. Eigentlich hat die Evolution von äußerer Komplexität
(es ist da) zu innerer Komplexität (es gibt eine Patentanmeldung)
dazu geführt das nur noch ein kleiner Entwicklungsschritt zu gehen
war. Und den haben dann verschiedene Erfinder fast gleichzeitig
getan.
Eine aktuelle Denkrichtung der Informatik arbeitet mit sehr kurzen
Entwicklungszyklen und beginnt schon mit der Entwicklung des
Systems - in einer prototypischen Version - bevor die Systemziele
komplett verstanden und festgelegt sind. Dieser Ansatz hat "entwicklungsbiologische"
Züge. "We
grow systems" anstelle von "we construct systems".
Für zielgerichtete Programmweiterentwicklung ist eine
Bewertungsfunktion nötig um festzustellen ob die neue
Programmversion besser als die alte Programmversion ist. Auch wenn
eine solche Bewertungsfunktion oft schwer zu finden ist, die
Bewertungsfunktion ist doch einfacher als das zu bewertende
Programm. Eine Komplexitätsreduktion findet statt.
Aktueller Kenntnisstand der Informatik ist somit: selbstlernende
Programme gibt es immer noch nicht. Die heutige beste Annäherung
ist die Mutation von Programmversionen durch den Programmierer und
die anschließende Selektion mit Hilfe einer Bewertungsfunktion.
Wiederholung von Mutation und Selektion bis die in der ebenfalls
fortgeschriebenen Aufgabenstellung festgelegten Ziele erreicht
sind. Wer denkt jetzt nicht an "alles fließt"?
Die Bewertungsfunktion wird gemäß Galileo Galilei nach dem
wissenschaftlichen Prinzip bestimmt: "Es ist nötig, alles zu
messen, was messbar ist, und zu versuchen, messbar zu machen, was
es noch nicht ist".
Die Entwicklung des "Schachprogramms an
sich" von den ersten Versionen der Programmzüchter Konrad
Zuse, Claude Shannon, Dietrich Prinz, Alan Turing bis heute können
als "evolution in progress" gesehen werden. Mit dieser
Betrachtungsweise war die Schachprogramm-Entwicklung in der
Künstlichen Intelligenz Forschung ein voller Erfolg - auch wenn
einige sagen "wir haben für teuer Geld und viel Zeit gelernt was
wir niemals wissen wollten". Damit Geld und Zeit nicht
verschwendet waren sollten wir die gelernten Lektionen bezüglich
Übertragungsproblem, Fortschreibung der Anforderungen,
schrittweise Erweiterung und Komplexitätsreduzierung bei der
Entwicklung anderer komplexer Systeme anwenden.
Alex Bernstein, IBM 704 Chess, 1958
Der Artikel "
Computer
vs. Chess-Player" in der Juni 1958 Ausgabe von Scientific
American von Alex Bernstein und Michael de V. Roberts beschreibt
ein Schach-Programm von 1958. Dieses Programm beherrschte alle
Phasen den Schachspiels, nicht nur einen Teil des Endspiels. Wegen
der geringen Rechenleistung des Computers, einer IBM 704, wurden
immer nur 7 Kandidatenzüge genauer untersucht. Eine
Bewertungsfunktion bestimmte diese Kandidaten aus der Menge der
möglichen Züge. Die Suchtiefe war 4 Halbzüge. Der Computer
benötigte im Durchschnitt 8 Minuten für die Berechnung seines
Zuges. Der Artikel endete mit dem typischen Optimismus der
Künstlichen Intelligenz Forschung zum Thema Computer Learning:
"and some day - not overnight - we may have machines which will
improve their game as they gain experience in play against their
human opponents".
Bild: IBM 704 Chess gegen Mensch 1958. Die
Partie in PGN.
MIT Chess Group Schachprogramm, 1959 - 1962
Alan Kotok hat 1962 ein Schachprogramm zum Thema seiner
Bachelor Thesis
bei Prof. John McCarthy gemacht. Im Anhang 1 ist der Fortran und
Assembler Quelltext dieses frühen Schachprogrammes dokumentiert.
Heutige Schachprogramme haben eine große Suchtiefe bei einfacher
Bewertungsfunktion und arbeiten damit ganz anders als die
Schachliteratur das Schachspiel darstellt. Kotok schreibt über den
Versuch der Chess Group das Wissen der Schach Literatur in ein
Computer Programm zu übertragen: "Although many tips were given
concerning the play of the game, relative importance of various
strategies was uncertain". Jahre später hat Ken Thompson mit
seinen Endspieldatenbanken die Schach Literatur im Bereich
Endspielwissen korrigiert und erweitert.
Richard Greenblatt, Mac Hack VI, 1967
Das Programm
Mac
Hack Six lief auf einem PDP-6 Computer, einem 36 Bit
Großrechner von DEC welcher ab 1963 gebaut wurde. Mac Hack war ein
erfolgreiches Programm. Es besiegte bei Turnierspielen menschliche
Schachspieler und erhielt deshalb als erstes Schachprogramm eine
offizielle Wertung von 1400 Punkten nach dem US Wertungs-System.
Greenblatt beschreibt die Ursachen des Erfolges so: "We did not
pretend to be writing a general problem solving system, but
addressed ourselves directly to the problem of chess ... The
program has been edited and reassembled over 200 times and has
played several hundred complete games". Greenblatt hat sich auf
das naheliegende Ziel konzentriert und hat viel Arbeit in Test,
Fehlererkennung, Fehlerbeseitigung und erneuten Test investiert.
Mac Hack hatte als erstes Schachprogramm eine
Eröffnungsbibliothek.
Eine Partie spielte Mac Hack gegen den Philosophen Hubert Dreyfus.
Dreyfus verkündete 1964 sehr kritische Ansichten über Künstliche
Intelligenz in dem Artikel
Alchemy
and Artificial Intelligence. Seine Aussage "there will
always be games that people can win and machines cannot" führte zu
einer Partie zwischen Dreyfus und Mac Hack. Diese Partie gewann
der Computer. Nach Seymour Papert führte diese Partie aber nur zu
der Erkenntnis, daß weder Computer noch Dreyfus richtig Schach
spielen können.

Bild links: Massachusetts State Championship 1967, Spiel 3,
Turnier 2, Weiss: Mac Hack VI, Schwarz: Spieler mit 1510 USCF
Punkten. Die
Partie in PGN.
Bild rechts: Weiss: Hubert Dreyfus, Schwarz: Mac Hack VI. Die
Partie in PGN.
Atkin, Slate, CHESS, 1970 - 1979
Das bekannteste Schachprogramm für
Großrechner war CHESS von Larry Atkin, David Slate und Keith
Gordon. In den Jahren 1970 bis 1979 gewann CHESS acht mal die US
Computer Chess Championship. Die Versionen 3.x waren selektive
Schachprogramme, die Versionen 4.x waren brute force Programme.
CHESS lief auf leistungsstarken Computern wie der Control Data
Corporation (CDC) Cyber 176. Das Programm CHESS benutzte
Bitboards.
Kaissa und Belle
Die 1960er und 1970er Jahre waren
die Zeit des Computerschach auf dem Großrechner. Die
Schachcomputer
Geschichte von Karsten Bauermeister und die
Computer
Chess History by Bill Wall liefern viel Information zum
Thema Großrechner-Schach.
Bei der ersten Computer-Weltmeisterschaft 1974 in Stockholm gewann
das UdSSR Programm Kaissa. Ab 1978 konnten CHESS und Kaissa beide
einpacken. Ken Thompson, einer der Entwickler der
Programmiersprache C und des Betriebssystem UNIX, benutzte einen
maßgeschneiderten Computer für das Schachspiel. Eine PDP-11 plus
spezielle Hardware führten Belle zu vielen Erfolgen in den
nächsten Jahren.
Peter Jennings, Microchess, 1976
Im Dezember 1976 konnte sich ein Schachspieler den
ersten Schachcomputer kaufen. Der fertig aufgebaute KIM-1
von MOS Technology war ein Einplatinen-Computer mit 6502 CPU. Die
CPU wurde später auch im Apple II, Commodore
PET und Commodore C64 verbaut. Die Computer-Programme wurden
auf Kassettenrecorder gespeichert. Die Eingabe erfolgte über 23
Tasten, die Ausgabe über eine 6-stellige LED Anzeige. Das
Schachprogramm für den KIM-1 war Microchess
von Peter Jennings. Die Preise waren 245 US-Dollar für den
Computer, 10 US-Dollar für das Schachprogramm und einige zehn
Dollar für Netzteil und Kassettenrecorder.
Das original 6502 Assembler Programm von Peter Jennings wurde 2002
von Bill Forster in C umgeschrieben. Ich habe ein xboard/WinBoard
Interface hinzugefügt. Nun kann Microchess von 1976 mit
zeitgemässer Grafik gegen die Computerschach Spieler von heute
antreten. Oder Microchess spielt gegen sich selbst oder gegen
andere Computerschach Programme. Gegen Microchess haben auch
Anfänger eine Chance!
Drei Musterpartien zeigen die Schachfähigkeiten von Microchess:



Bild links: Microchess - Microchess 0:1. Die Partie in PGN gibt es hier.
Die komplette Partie dauerte 2 Sekunden!
Bild mitte: Anfänger - Microchess 1:0. Die Partie in PGN.
Bild rechts: Microchess - Anfänger 0:1. Die Partei in PGN.
Download Microchess
Der C Quelltext für die
WinBoard Version von Microchess ist hier. Kompiliert wurde mit der
kostenlosen Microsoft Visual C++ 2005 Express Edition.
Die MS-Windows Programmdatei (Exe
Datei) ist hier. Die Datei ist 11 KByte gross.
Installation Microchess
Zuerst einmal muss xboard/Winboard
installiert werden, z.B. in das Verzeichnis C:\Programme\WinBoard.
In dieses Verzeichnis muss die microchessw.exe Datei kopiert
werden. Damit die Microchess Schach-Engine gefunden wird sind
Änderungen in der winboard.ini Datei nötig. Der relevante
Ausschnitt der Ini-Datei vor und nach der Änderung:
vorher
|
nachher
|
/firstChessProgramNames={GNUChess
"GNUChes5 xboard"
}
/secondChessProgramNames={GNUChess
"GNUChes5 xboard"
} |
/firstChessProgramNames={GNUChess
"GNUChes5 xboard"
microchessw
}
/secondChessProgramNames={GNUChess
"GNUChes5 xboard"
microchessw
} |
Eine geänderte winboard.ini Datei für
WinBoard Version 4.2.7 gibt es hier. Diese Datei enthält die
obigen Änderungen und ersetzt die alte Ini-Datei im WinBoard
Verzeichnis.
Robert Arnstein, 8080 Chess, 1977
Das Programm 8080 Chess von Robert Arnstein lief auf
einem Processor Technology Sol 20. Der Sol 20 hatte eine Intel
8080 CPU. Die Bildschirmauflösung von 64 Zeichen in 16 Zeilen war
wie beim Tandy TRS-80. 8080 Chess war ein Teilnehmer der ACM US
Computer Chess Championship im Jahr 1977. Dieses
Mikroprozessorprogramm belegte den 9. Platz von 12 Plätzen.
Von Jim Battle gibt es eine Sol 20 Seite mit
Emulator und Software.

Bild: AVR-Max 4.8 gegen 8080 Chess. Partie in PGN.
Spracklen, SARGON CHESS, 1978
SARGON
von Dan & Kathe Spracklen hat 1978 das Microcomputer Schach
Turnier auf der West Coast Computer Faire gewonnen. SARGON lief
auf einem Wavemate
Jupiter III mit Zilog Z80 Prozessor. Der Jupiter hatte eine
hohe Auflösung von 64 ASCII Zeichen auf 32 Zeilen oder 128 mal 96
Pixel Blockgrafik.
Zuerst haben die Autoren das Z80 Assembler Listing in TDL ZASM
Syntax selbst vertrieben. Später wurde das Listing als Buch "Sargon
A
Computer
Chess Program" von dem Verlag Hayden veröffentlicht. Das SARGON Assembler Listing wurde von Andre
Adrian nach CP/M portiert, siehe das SARGON
CP/M Programm. Von Takeda Toshiya gibt es einen einfachen
CP/M Emulator für MS-Windows, den CP/M
Player. Im Internet findet sich auch der TDL
Assembler für CP/M zusammen mit dem Linker.
Das ausführbare Programm wird erzeugt mit den Kommandos "cpm zasm
sargon", "cpm linker sargon". Ausgeführt wird das Programm mit
"cpm sargon".
Das SARGON Programm wurde auf die Z80 Computer TRS-80 (U.S.A) und
Nascom 1 (England) portiert.
Um die Jupiter III Grafik zu sehen wurde der CP/M Player
erweitert. Hier ist der Jupiter III
Emulator für SARGON und hier ist der Quelltext des Jupiter III Emulator.
Das Programm ist in C geschrieben für die Microsoft WinAPI unter
Visual C++ 2010 Express.
Bild links: Hayden Books ISBN 0-8104-51554
Bild rechts: AVR-Max 4.8 gegen Jupiter SARGON Level 4. Remis durch
Stellungswiederholung. Partie in PGN.
TRS-80 SARGON CHESS, 1978
Der Tandy Radio Shack TRS-80
war 1977 ein erfolgreicher Heimcomputer. Tandy verkaufte 55000 Rechner
im ersten Jahr. Das SARGON Programm auf dem TRS-80 benötigte
Level 2 BASIC (12KByte ROM). Die Bildschirmauflösung war 64 x 16
Buchstaben oder 128 x 48 Pixel Pseudografik. Sargon kann nicht das
Brett drehen und spielt weiss von unten nach oben.
Der TRS-80 Emulator von
Matthew Reed wurde in Einstellung "Model 1" verwendet. Der
Emulator benötigt das Model 1 ROM und
die SARGON CMD Datei.


Bild links: SARGON CHESS Intro.
Bild rechts: Videochess auf Stufe 3 gegen SARGON auf Stufe 1.
Sargon gewinnt Material mit einer Springergabel.
Nascom SARGON CHESS, 1978?
In Europa war ab 1977 der
Nascom der englischen
Firma Nasco ein erfolgreicher Z80 Computer-Bausatz. Blue Label
Software Pascal, der Vorläufer von Turbo Pascal, erschien auf dem
Nascom. Sargon Chess auf dem Nascom benutzt ein eigenes
Zeichensatz-ROM. Dadurch ist die Spielfelddarstellung besser als
auf dem TRS-80. Weitere Programme für den Nascom waren Tiny BASIC
nach Li-Chen Wang, Microsoft BASIC, Forth und CP/M 2.2.
Bild: Sargon Version 1.3 auf Nascom. Der
VNascom
Emulator läuft in DOSBox unter MS-Windows.
Spracklen, SARGON II, 1978
Bei der ACM US Computer Chess
Championship im Jahr 1978 belegte Sargon II den 5. Platz von 12
Plätzen. Ein Mikrocomputer-Programm besiegte Großrechner-Programme
wie
DUCHESS
für IBM
S/370
MVS, eine Neuigkeit
im Computerschach. Die TRS-80 Version von SARGON II erschien 1979.
Frey, Atkin, Chess 0.5, 1978
In der Zeitschrift Byte wurde
zwischen Oktober 1978 und Januar 1979 in der Artikelserie "
Creating
a Chess Player" von den Autoren Peter W. Frey und Larry R.
Atkin ein Schachprogramm in der Programmiersprache Pascal
vorgestellt. Larry Atkin war einer der Programmierer von CHESS,
einem sehr erfolgreichen Schachprogramm für Großrechner. Der
Quelltext wurde von
Scott A.
Moore von CDC6000 Pascal nach GNU Pascal umgestellt. Mit
Hilfe von
Dev+GNU
Pascal, einer GNU Pascal Programmierumgebung für MS-Windows
von Abimbola Olowofoyeku und anderen, lässt sich dieser
Chess 0.5 Quelltext in dieses
Chess 0.5 MS-Windows Programm
übersetzen.
Das Chess 0.5 Programm benutzt die klassische Schachnotation. Der
weisse Zug E2E4 wird eingeben als P-K4. Der Anwortzug E7E5 von
Schwarz wird eingeben als P-K4. Bei beiden Zügen wurde der
Königsbauer auf das vierte Feld vor den König gestellt, deshalb
die gleiche Schreibweise.
QR8
|
QN8
|
QB8
|
Q8
|
K8
|
KB8
|
KN8
|
KR8
|
QR7
|
QN7
|
QB7
|
Q7
|
K7
|
KB7
|
KN7
|
KR7
|
QR6
|
QN6
|
QB6
|
Q6
|
K6
|
KB6
|
KN6
|
KR6
|
QR5
|
QN5
|
QB5
|
Q5
|
K5
|
KB5
|
KN5
|
KR5
|
QR4
|
QN4
|
QB4
|
Q4
|
K4
|
KB4
|
KN4
|
KR4
|
QR3
|
QN3
|
QB3
|
Q3
|
K3
|
KB3
|
KN3
|
KR3
|
QR2
|
QN2
|
QB2
|
Q2
|
K2
|
KB2
|
KN2
|
KR2
|
QR1
|
QN1
|
QB1
|
Q1
|
K1
|
KB1
|
KN1
|
KR1
|
Bild: Feldbezeichnung in klassischer
Schachnotation für Weiss. Das Feld Q1 von Weiss ist das Feld Q8
für Schwarz.
Das Programm Chess 0.5 versteht einige Kommandos. Hier ist die
komplette
Kommadoliste.
LE FNODEL 1000
|
Spielstärke einstellen auf
1000.
|
PR
|
Spielfeld ausgeben
|
IN
|
Neues Spiel
|
EN
|
Programm beenden
|
GO
|
Einen Zug ausführen
|
GO 2
|
Zwei Züge ausführen (einen
für Weiss, einen für Schwarz)
|
Eine Partie zwischen Chess 0.5 und Micro-Max 4.8 endet nachdem
Chess 0.5 den Zug Läufer f8 schlägt Bauer b4 nicht annimmt.
Wahrscheinlich haben sich bei der Portierung von CDC Pascal auf
GNU Pascal einige Fehler eingeschlichen. Immerhin arbeitet Chess
0.5 mit Bitboards.

Bild links: Chess 0.5 Anzeige. Bild rechts: WinBoard Darstellung
der Partie.
Central Data 2650 Chess, 1978?
Die Firma Central Data Corporation
aus Champaign, IL in U.S.A. produzierte ab 1977 den Central Data
2650 Computer. Mit einer Anzeige von 80 Zeichen in 16 Zeilen war
dieser Computer gut ausgestattet. Das Central Data Chess sieht
sehr nach Sargon Chess aus.

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


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


Bild links: Mein Mephisto III. Vor einigen Jahren war hier das
Foto von einem Mephisto aus dem Internet. Der "Urheber" dieses
Fotos war unfreundlich, deshalb habe ich "sein" Foto von "seinem"
Mephisto entfernt. Dies ist das Foto von meinem Mephisto.
Bild rechts: Entwurf Selbstbau Schachcomputer mit ATMega88V
Mikrocontroller und LED 7-Segmentanzeigen.

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

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

Bild: AVR Max Prototype. Die Lochstreifenplatine passt in das
TEKBOX Gehäuse mit Batteriefach (16 x 9.4 x 3.15 cm3).
Die Zeitschrift Elektor hat
eine Platine für AVR-Max entwickelt. Der Elektor Schachzwerg wird
in Ausgabe 2009/6 vorgestellt. Hier die professionelle Verpackung
von Antoine Authier. Vielen Dank an Erich Krempelsauer, Jerry
Jacobs, Antoine Authier, Hedwig Hennekens und andere von Elektor
und an Wolfgang Rudolph und andere von ComputerClub 2. Das Elektor
ATM18 Board mit 2-Draht LCD Anzeige und einer 11 Tasten Matrix
Tastatur ergibt einen Luxus Schachzwerg mit ausführlicher
Benutzerführung durch die 20 Zeichen mal 4 Zeilen LCD Anzeige.

Bild: Elektor Schachzwerg im Bopla Gehäuse BS
400 F-7024. Einfach schick!
Bedienungsanleitung SHAH Schachcomputer
Wir beglückwünschen Sie zum Bau des SHAH
Schachcomputers, die neueste Entwicklung unseres Hauses. SHAH
zeichnet sich durch seinen nostalgischen Charme aus, besonders
bemerkenswert ist die Spannungsversorgung mit zwei Mignon
Batterien. Das Schachprogramm ist Micro-Max 4.8 von Harm-Geert
Müller in einer Portierung von Andre Adrian.
Um die Fähigkeiten Ihres neuen SHAH Schachcomputers voll
auszuschöpfen, empfehlen wir Ihnen, die nachfolgende
Gebrauchsanweisung sorgfältig durchzulesen.
Schachbrett aufstellen, SHAH einschalten. Die Anzeige SHAH
erscheint. Die 'CL' Taste drücken, die Anzeige wird dunkel,
anschließend Züge nach dem international bekannten
Koordinaten-System eingeben, z.B. E2 E4.
Nach Eingabe des Zuges zweimal die Taste 'Go' drücken,
damit der Computer den Zug registriert. Bei Fehleingabe einen
neuen Zug eingeben. Ein ungültiger Zug wird mit der Anzeige ZUG
abgelehnt.
Nach Eingabe Ihres Zuges verarbeitet der Computer Ihre
Informationen. Solange die Anzeige blinkt zeigt der Computer den
Kandidatenzug. Der endgültige Zug wird ohne Blinken dargestellt.
Wird ein König Matt gesetzt erscheint MATT.
Damit der Computer weiss spielt nach dem Einschalten die 'CL'
Taste und danach die 'Go' Taste drücken.
Der Computer führt einen Zug aus wenn die 'Go' Taste gedrückt
wird.
Tipp: Wenn die Stellung schlecht für den Menschen steht, 'Go'
drücken und den Computer ab sofort die schwächere Seite spielen
lassen. Der Philosoph Hubert
Dreyfus hat nämlich festgestellt das Computer nicht Schach
spielen können, man aber gegen Computer im Schachspiel verlieren
kann.
Der SHAH Schachcomputer hat keine Eröffnungsbibliothek. Sie können
aber eine beliebige Eröffnung eingeben indem Sie die weissen und
schwarzen Züge eingeben. Nach jeder Zugeingabe nur einmal
Taste 'Go' drücken. Eine übliche Eröffnung ist E2E4, E7E5, G1F3,
B8C6.
Über die 'FN' Taste erreichen Sie Zusatzfunktionen. 'FN' und 1
startet ein neues Spiel. 'FN' und 2 läßt die Spielstufe
einstellen. Mit Taste 'Go' wird die Spielstufen Einstellung
verlassen. 'FN' und 3 schaltet die Anzeige der Hauptvariante
(Kandidatenzug) ein oder aus.
Die Taste 'CL' löscht die Eingabe.
Entwicklungsziel für SHAH ist eine Elo-Zahl von 1200-1399 unter
Turnierbedenkzeit (120 Minuten für die ersten 40 Züge). Das
entspricht Amateur, Klasse D, durchschnittlicher Hobbyspieler.
Spielstufe 1 ist Blitzschach mit 7 Sekunden pro Zug, Stufe 5 ist
Aktivschach mit 30 Sekunden und Spielstufe 8 ist Turnier mit 3
Minuten. Nach dem Einschalten spielt SHAH auf Spielstufe 3.
Software für SHAH Schachcomputer
Der Negamax
Suchalgorithmus in Mikro-Max ist rekursiv definiert. Die Negamax
Funktion ruft sich selbst auf bis eine Abbruchbedingung wie
maximale Suchtiefe erreicht ist. Eine Rekursion läßt sich in eine
Iteration umwandelt. Aus dem Selbstaufruf der Funktion wird eine
Schleife über die Funktion. Für einfache Funktionen wie Fakultät
oder Fibonacci Reihe ist die Umwandlung Rekursion zu Iteration
trivial. Der Negamax Algorithmus läßt sich nach dem gleichen
Verfahren in eine iterative Version umschreiben. Diese Lösung
benötigt nur noch 34Bytes pro Halbzug (ply). Damit läßt sich mit
einem 1Kbyte RAM eine Suchtiefe von 20 Halbzügen erreichen. Der
ROM Speicherbedarf wächst nicht. Ob die Adressierung auf den
Stack-Framepointer bezogen wird oder auf den Stack-Array-Pointer
ist ungefähr gleich aufwendig.
Hier ist der C Quelltext von AVR Max 4.8
für den SHAH Schachcomputer, und hier die Hex
Datei. Hier ist C Quelltext AVR Max
mit xboard Schnittstelle und als MS-Windows
Programmdatei. Die Exe Datei ist 10KByte gross.
Die MS-Windows Programmdatei gibt es auch zusammen mit WinBoard in
einer selbst-extrahierenden Exe Datei avrmax_48_winboard.exe.
Auspacken mit Doppel-Klick. Das Unterverzeichnis avrmax_48_winboard
wird erzeugt. In diesem Unterverzeichnis Doppel-Klick auf das winboard.exe
Programm. Im "WinBoard Startup" Popup die Auswahl "Play against a
chess engine.." anklicken. Im Winboard Fenster kann Weiss den
ersten Zug ausführen indem die Figur mit der Maus und Links-Klick
angefasst wird. AVR-Max versteht auch die Zeitkontrolle. Eine
Blitzschachpartie dauert 5 Minuten, eine Aktivschach Partie hat 40
Züge in 20 Minuten oder 30 Minuten für die Partie.
Weitere Informationen zu Winboard gibt es auf Tim Mann's Chess
Pages.


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



Bild links: AVR-Max 1.61 verliert im 26. Zug gegen Micro-Max 4.8.
Partie in PGN.
Bild mitte: AVR-Max 4.81 gewinnt im 20. Zug gegen GNU Chess 5 in
Einstellung gesamte Bedenkzeit 10 Sekunden. Partie in PGN.
Bild rechts: AVR Butterfly. In Deutschland z.B. zu kaufen über www.mikrocontroller.net
Shop.
Atari VCS Video Chess, 1979
Das Atari Video Computer
System Video
Chess läuft mit 4KByte ROM und 128Byte RAM. Das Programm
kennt alle Schachregeln. Mit Hilfe des VCS Emulators Stella oder MESS läßt sich Video Chess heute
noch spielen. Der Video Chess Prototype
von 1978 heißt Computer
Chess. Beim Prototype erfolgt die Steuerung über den rechten
Joystick. Wahrscheinlich wurde VCS Video Chess und Atari 400
Computer Chess von den gleichen Personen entwickelt.
Die VCS hat keinen Bildspeicher. Die CPU muss das Bild 60 mal pro
Sekunde neu erzeugen. Diese Bilderzeugung wird während der
Berechnung des Computerzuges abgeschaltet. Atari 2600 ist Atari
VCS in einem neueren Gehäuse.



Bild links: Atari VCS Computer Chess (Prototype). Die Läufer
erinnern an Raketen.
Bild mitte: Partie Crafty 19.3 gegen Video Chess 1:0. Die Partie in PGN. Video
Chess spielte auf Stufe 3.
Bild rechts: Partie Video Chess gegen Crafty 19.3 0:1. Die Partie in PGN.
Video Chess spielt weiss von oben nach unten.
Der Emulator benötigt das Video Chess
ROM. Die Bedienung ist einfach. Mit dem "Right Difficulty
Switch" wird die vom Computer gespielte Farbe ausgewählt. Mit dem
"Left Difficulty Switch" kann zwischen Eingabe Schachproblem (A)
und Spiel (B) umgeschaltet werden. Mit der Taste 1 wird die
Spielstärke ausgewählt. Für die Zug-Eingabe ist zuerst der Cursor
auf das Von-Feld zu bewegen, dann die Strg Taste drücken, Cursor
auf das Ziel-Feld bewegen, dann wieder Strg Taste drücken. Bei
AtariAge gibt es das
Video Chess Manual.
Das Schachprogramm wurde von Larry Wagner mit Unterstützung des
internationalen Schach Meister Julio Kaplan entwickelt. Die Grafik
stammt von Bob
Whitehead. Laut Überlieferung
war die Entwicklungszeit für das Schachprogramm zwei Jahre und die
Entwicklungszeit für die "venetian
blinds" graphische Darstellung war zwei Tage.
Atari 400/800 Computer Chess, 1979
Der Atari 400 (Folientastatur) und der Atari 800
(normale Tastatur) Computer haben eine Bildschirmauflösung von
maximal 320x192 Pixel. Die 6502 CPU arbeitet mit 1.8MHz. Die gute
Grafik und die schnelle CPU übertrafen die Leistung von TRS-80,
Commodore PET und Apple ][. Die Computer erschienen Dezember 1979,
siehe Atari
8-Bit
Historie. Ein Atari 400/800 Emulator unter Linux und
MS-Windows ist Atari++
von Thomas Richter. Die Computer Chess Cartridge enthält 8KByte
ROM. Im Atari 400/800 sind minimal 8KByte RAM enthalten.
Die Bedienung erfolgt im Emulator mit den Tasten des Zehnerblocks.
Mit 8, 4, 6, 2 wird der Cursor bewegt, mit 0 wird eine Figur
aufgenommen oder abgesetzt. Taste F2 wechselt die Farbe. Mit F3
wird die Spielstufe eingestellt.


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



Bild links: Saba Videoplay Schach läuft im Emulator MESS.
Bild mitte: Eröffnung (Anfänger gegen Saba Videoplay Schach).
Bild rechts: Das Ende ist nahe.
Der Emulator MESS benötigt das Channel F
BIOS ROM und das Schach ROM.
Im Intro Bildschirm die Taste Y für Computer spielt schwarz oder X
für Computer spielt weiss, dann Taste 1 drücken für Start. Der Zug
a1-a1 wählt Spielstufe 1, Zug b1-b1 wählt Spielstufe 2 usw. Für
die Zug-Eingabe ist zuerst der Cursor auf das Von-Feld zu bewegen,
dann Taste A drücken, Cursor auf das Ziel-Feld bewegen, nochmal
Taste A und zuletzt Taste Q drücken. Ist bei der Zugeingabe das
Von-Feld gleich dem Nach-Feld führt Saba Schach zuerst einen Zug
für den Menschen und dann für den Computer aus. Mit Taste S
anstelle von Taste Q wird die Zugeingabe abgebrochen.
Anstelle von Taste 1 und Spielstufe Auswahl kann man Taste C
drücken. Das wählt die schwächste Spielstufe aus. Die Info über
Spielstufen stammt von "Ein Freund".
TRS-80 SARGON-II, 1979
Im Jahr 1979 erschien Sargon 2. Die Grafik auf dem
TRS-80 ist keine Verbesserung gegenüber der SARGON CHESS Grafik.
Die Sargon Programme des Ehepaars Spracklen gewannen in Fidelity
Schachcomputern von 1980 bis 1984 viermal die World
Microcomputer
Chess Championship.
Der TRS-80 Emulator benötigt das Model 1 ROM
und die SARGON2 CMD Datei.


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


Bild links: TI-99/4 animierte Video Chess Intro. Die ersten
TI-99/4 gab es erst ab Anfang 1980 zu kaufen.
Bild rechts: TI-99/4 Video Chess. Die Figuren sehen futuristisch
aus.
Mattel Intellivision, USCF Chess, 1981
Der Erfolg von Atari VCS bewog Mattel 1980 die
Intellivision (INTV) herauszubringen. CPU ist die 16-Bit General
Instruments CP1610 mit 0.9MHz Takt. Die Grafikauflösung ist 160 x
196. Das USCF Chess Module hatte zusätzliches RAM um die
Spielleistung zu verbessern. Mit Schachuhr und Darstellung der
geschlagenen Figuren ist USCF Chess benutzerfreundlich. USCF Chess
kann nicht das Brett drehen und spielt weiss von unten nach oben.
Der Sound Chip AY-3-8914 ist dreistimmig. Wird USCF Chess besiegt
ertönt Applaus und Pfiffe. Es gibt unter anderen die Emulatoren Nostalgia
und Bliss für die INTV.


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



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



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



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


Bild links: Mephisto Rebell 5 auf Stufe 3 gewinnt im 61. Zug.
Rebel hat 1875
Elo im Computer-Aktivschach. Partie in PGN.
Bild mitte: JB schlägt AVR-Max Stufe 5 in 16 Zügen. Partie in PGN. JB besiegt Mephisto
MM I in 17 Zügen.
ohne Bild: JB schlägt AVR-Max Stufe 8 in 24 Zügen. Partie in PGN. Der Mephisto
2 wird von JB nach 26 Zügen besiegt.
Das JB System
Der französische Schachspieler JB
eröffnet mit 1.d4 2.Sc3 3.Lf4 oder wenn nötig 1.d4 2.Sc3 3.a3
4.Lf4. Diese Eröffung hat den ECO-Code D00 oder nach Zugumstellung
D02. Wie die Partien von JB gegen Schachcomputer der 2100 Elo
Klasse wie
Mephisto
Master Chess zeigen ist diese Eröffnung konkurrenzfähig,
wenigstens für Spiele unterhalb der Schach Weltelite. Der Novag
Turquoise hat in seiner 8900 Halbzüge Eröffnungsbibliothek 3.Lf4
c5, 4.e3 a6. Nach dem Druck auf c7 mit Drohung Springergabel auf
Turm a8 und König folgt bei JB der zweite Angriff mit dem h-Bauern
und Opfer auf g7. In der dritten Phase der Partie verwendet JB oft
die lange Rochade um über die dann offene h-Linie beide Türme ins
Spiel zu bringen. Zu dieser Zeit ist im Idealfall ein schwarzer
Turm noch in Grundstellung auf a8 und der andere Turm steht wegen
der kurzen Rochade hinter dem König wenn der h-Linie Angriff
rollt. Die Partien von JB gegen Schachcomputer sind wirklich nicht
langweilig. JB opfert und gewinnt!
Da die Dame den d-Bauern deckt ist Sf6 im zweiten Zug nicht so
notwendig wie der Springerzug in der spiegelbildlichen
italienischen
Partie 1.e4 e5, 2.Sf3 Sc6, 3.Lc4. Der Novag Sapphire 2
spielt z.B.: 1.d4 e6, 2.Sc3 d5, 3.Lf4 Ld6, 4.Lxd6 Dxd6, 5.e3 Sf6,
6.Ld3 Sbd7, 7.Sf3 c5, 8.h4. Der Novag Star Sapphire spielt ähnlich
1.d4 e6, 2.Sc3 d5, 3.Lf4 Ld6, 4.Dd2 Sf6, 5.Sb5 Se4, 6.Dc1 g5?,
7.Lxd6 cxd6, 8.e3 Da5+, 9.c3 Ld7, 10.Sa3 O-O, 11.f3 Sf6, 12.h4.
ECO-Code
|
Hauptreihen
|
Name
|
D00 |
1.d4 d5, 2.Sc3
Sf6, 3.Sf3 |
Damenbauernspiel |
D02 |
1.d4 d5, 2.Sf3 Sf6, 3.Lf4 |
Damenbauernspiel |
Hier einige Partien JB gegen Schachcomputer nach 1.d4 d5, 2.Sc3
Sf6 bis zum Beginn des h-Bauer Angriffs:
Schachcomputer
|
Fortsetzung
|
Novag Citrine |
3.Lf4 c5, 4.e3 a6, 5.Sf3
e6, 6.a3 Le7, 7.Ld3 b6, 8.h4 O-O |
Novag Ruby |
3.Lf4 c5, 4.e3 a6, 5.Sf3
Db6, 6.Tb1 e6, 7.Ld3 cxd4, 8.exd4 Lb4, 9.h4 |
Novag Emerald Classic |
3.Lf4 c5, 4.e3 a6, 5.Sf3
Db6, 6.Sa4 Da5, 7.c3 cxd4, 8.exd4 e6, 9.b4 Dd8, 10.Ld3
Le7, 11.h4 |
Novag Turquoise |
3.Lf4 c5, 4.e3 a6, 5.Ld3
cxd4, 6.exd4 Db6, 7.Tb1 e6, 8.a3 Sc6, 9.Sf3 Ld7, 10.Le2
Le7, 11.b4 O-O, 12.h4 |
Excalibur Phantom Force |
3.Lf4 e6, 4.a3 Ld6, 5.Lxd6
cxd6, 6.e3 O-O, 7.Sf3 Sc6, 8.Le2 e5, 9.h4 |
Novag Zircon II
|
3.Lf4 e6, 4.a3 Ld6, 5.Lxd6
cxd6, 6.e3 O-O, 7.Ld3 Db6, 8.Sf3 e5, 9.Le2 Lf5, 10.Tb1
Sbd7, 11.h4
|
Mephisto MM VI |
3.Lf4 e6, 4.a3 Ld6, 5.Lxd6
Dxd6, 6.e3 c5, 7.Sf3 cxd4, 8.exd4 O-O, 9.Ld3 b6, 10.h4 |
Saitek Bravo
|
3.Lf4 e6, 4.a3 Ld6, 5.Lxd6
Dxd6, 6.e3 Db6, 7.Tb1 O-O, 8.Ld3 Sbd7, 9.Sf3 c5, 10.h4
|
Mephisto Master Chess |
3.Lf4 Lf5, 4.e3 e6, 5.a3
Le7, 6.Ld3 Lxd3, 7.Dxd3 O-O, 8.Sf3 c5, 9.h4 |
Excalibur Alexandra |
3.Lf4 Lf5, 4.e3 e6, 5.a3
Le7, 6.Sf3 O-O, 7.Ld3 Se4, 8.h4 |
Novag Sapphire
|
3.Lf4 c5, 4.Sf3 Se4, 5.Dd3
Da5, 6.Db5 Dxb5, 7.Sxb5 Sa6, 8.e3 e6, 9.Ld3 Le7, 10.Se5
g5, 11.Lg3 O-O, 12.f3 Sxg3, 13.hxg3
|
Mephisto Magellan
|
3.Lf4 g6, 4.Sb5 Sa6, 5.e3
c6, 6.Sc3 Db6, 7.b3 Lf5, 8.a3 Lg7, 9.Sf3 Sh5, 10.Lg5 f6,
11.Lh4 e5, 12.Le2 O-O, 13.h3
|
Verbesserungen AVR-Max Programm
Das AVR-Max 4.8 Programm belegt 4968 Bytes von 8192
Bytes im ATMega88V. Die freien Bytes lassen sich für
Programmerweiterungen nutzen.
Eine naheliegende Erweiterung ist die Stellungseingabe. Für
Matt-in-N-Zügen Aufgaben oder für die "findet der Computer den
besten Zug in einer (künstlichen) Stellung" Tests der
Schachcomputer Journalisten und Fans.
Mehr Komfort für den menschlichen Spieler bieten die Funktionen
Zug zurücknehmen (take back) und Zug vorschlagen (hint).
Dem Programm fehlt noch Kenntnis über Remis nach dreifacher
Wiederholung der Stellung und Remis nach 50 Zügen ohne Bauern-Zug
oder Figur schlagen.
Die folgenden Erweiterungen sollen die Spielstärke steigern. Von
Ken Thompson stammt die Erkenntnis, daß die Stärke um 200
Elo-Punkte ansteigt wenn die Suche einen Halbzug tiefer geht. Für
Belle hat Thompson bei 4 Halbzügen eine Leistung von 1235 Punkten
und bei 5 Halbzügen von 1570 bestimmt. Pro Halbzug steigt der
Rechenaufwand um den Faktor 6.
Kontrolle der Zentralfelder
Das Kotok Schachprogramm von 1962
verfügte schon über einen "center control evaluator". Diese
Positions-Bewertungsfunktion vergibt für die Zentralfelder c3 bis
f6 einen Bonus. Die Tabelle aus der Kotok Thesis lenkt die Figuren
von Weiss in Richtung Damenflügel. Diese Tabelle empfiehlt wenn
Schwarz die lange Rochade durchgeführt hat.
8 8 4 4
4 8 8 4
2 4 4 2
1 1 1 1
Das AVR-Max Programm benutzt nur eine Tabelle für den
Positionsbonus. Sinnvoll dürften unterschiedliche Tabellen für
Weiss und Schwarz sein. Der grösste Bonus wird für Felder in der
Nähe des gegnerischen Königs vergeben.
Zug Sortierung
Alpha-Beta Beschneidung
funktioniert am besten wenn die Züge nach der Qualität sortiert
sind. Züge die den König ins Schach setzen haben die beste
Qualität. Dann folgen die Schlagzüge. Je größer der
Materialunterschied zwischen schlagender Figur und geschlagener
Figur umso besser. Bauer schlägt Dame ist besser als Dame schlägt
Dame - und wird meistens im nächsten Zug selbst geschlagen.
Bauernumwandlungen sind seltene, aber gute Züge. Bauernzüge von
der sechsten Reihe zur siebten Reihe sind auch schon interessant.
Zuletzt folgen die stillen Züge. Der "inverse Zug Generator" kann
für die Zug Sortierung benutzt werden. Zuerst wird die Schach
Erkennung durchgeführt, diesmal aber als Angriff. Züge die den
König in Schach setzen werden in der Baumsuche auf Matt oder
Widerlegung untersucht. Im zweiten Schritt werden die gegnerischen
Figuren auf dem Brett gesucht. Der "inverse Zug Generator" sucht
Schlagzüge die in der Baumsuche weiterverfolgt werden. Zuletzt
sucht der normale Zuggenerator die stillen Züge. Bei der Ruhesuche
(quiescent search) werden stille Züge nicht betrachtet.
Üblicherweise werden durch den Zuggenerator alle pseudolegalen
Züge erzeugt. Dann werden diese Züge sortiert. Im dritten Schritt
wird die Baumsuche ausgeführt. Wegen dem kleinen RAM Speicher kann
AVR-Max keine Zugsortierung durchführen. Deshalb werden zwei
unterschiedliche Zuggeneratoren benutzt. Der erste Zuggenerator,
ein inverser Zuggenerator, findet nur Schlagzüge, der zweite
Zuggenerator findet nur stille Züge. Der erste Zuggenerator
beginnt mit der Zugsuche auf dem Feld des Königs, dadurch werden
zuerst alle Züge welche zu Schachmatt führen erzeugt.
Schach Erkennung
Im AVR-Max Programm erfolgt die
"König steht im Schach" Erkennung durch den Zuggenerator. Eine
neue Ebene im Suchbaum wird gestartet. Alle Züge werden generiert.
Ist mindestens ein Zug dabei der den König schlägt stand der König
im Schach. Für die Schach Erkennung alle Züge zu generieren ist
aufwändig - aber Quelltext sparend. Die reine Schach Erkennung
geht einfacher mit einem "inversen Zug Generator". Dabei beginnt
die Zug-Generation nicht vom Start-Feld, sondern vom Ziel-Feld.
Das Ziel-Feld ist das Königsfeld. Ausgehend von diesem Feld wird
die Bewegung einer "Super-Figur" generiert. Zuerst wird getestet
ob im Springer-Abstand ein feindlicher Springer zu finden ist.
Dann ob ein feindlicher Bauer einen Schlagzug auf das Königsfeld
ausführen kann. Es folgen die Suchstrahlen in vertikaler und
horizontaler Richtung für Turm und Dame und in diagonaler Richtung
für Läufer und Dame. Findet die "Super-Figur" nur leere
Start-Felder, eigene Figuren oder den Spielfeldrand, dann steht
der König nicht im Schach. Ob der König im Patt steht bemerkt die
Schachmatt-Prüfung nicht.
Eröffnungsbibliothek
Eine Eröffnungsbibliothek hilft dem AVR-Max die ersten
Züge schnell und gut auszuführen. Die einfachsten
Eröffnungsroutinen folgen einer Zugfolge. Diese Routinen verstehen
keine Zugumstellung. Bessere Eröffnungsroutinen gehen von der
Position aus und suchen einen Folgezug in der
Eröffnungsbibliothek. Die opening-book Position wird üblicherweise
in der Hash-table (transposition-table)
gespeichert. AVR-Max hat keine Hash-table. Die Suche in der
Eröffnungsbibliothek erfolgt durch Ausspielen der Bibliothekszüge
auf einen zweiten Spielfeld und Vergleich der beiden Spielfelder.
Dadurch werden gleiche Stellungen erkannt die durch Zugumstellung
entstanden sind. Der Suchaufwand ist linear mit der Anzahl der
Eröffungen in der Bibliothek wenn die aktuelle Stellung im N.ten
Zug nur mit den Bibliotheksstellungen im N.ten Zug verglichen
werden.
Ein Zug besteht aus zwei Halbzügen. Jeder Halbzug hat ein Von- und
ein Nach-Feld. Für die 64 Felder sind 6 Bit nötig. Ein Zug
benötigt somit 4*6Bit = 24Bit = 3 Bytes an Speicher. Der Rochade
Zug wird durch e1-c1 oder e1-g1 kodiert. Die Ausspiel-Routine muß
den Turm-Halbzug hinzufügen. En-Passant Schlagen kann durch Bauer
zieht nach rechts oder nach links kodiert werden, z.B. b4-a4. Die
Ausspiel-Routine korrigiert den Bauernzug nach b4-a3 und löscht
den Bauern auf a4.
Mit einem Präfix-code
läßt sich ein Halbzug der Eröffnungsbibliothek in einem Byte
speichern. In dem Byte wird der Figur-Index, z.B. a-Turm oder
e-Bauer und der Bewegungsvektor abgespeichert. Wenn die Figuren in
einem Array (piece list) gespeichert werden dann ist das
Ausspielen der Bibliotheks-Züge einfach. Der Präfix-code:
Bitmuster
|
Figur
|
Beschreibung
|
111rrrdd |
Dame
|
rrr=3Bit neue Reihe/Spalte/Diagonale,
dd=2Bit Richtung
|
110irrrd |
Turm
|
i=welcher Turm, rrr=3Bit neue Reihe/Spalte,
d=1Bit Richtung
|
101irrrd |
Läufer
|
i=welcher Läufer, rrr=3Bit neue Diagonale,
d=1Bit Richtung |
100iiidd |
Bauer |
iii=welcher Bauer, dd=2Bit Schlagzug
Richtung (normal, e.p.)
|
0111iiid |
Bauer |
iii=welcher Bauer, d=1Bit Richtung (ein
Feld, zwei Felder)
|
0110iddd |
Springer |
i=welcher Springer, ddd=3Bit Richtung |
01011ddd
|
König |
ddd=3Bit Richtung
|
0101011d
|
König
|
d=1Bit kurze, lange Rochade
|
Natürlich hat das Bitmuster 0 für Richtung beim Turm eine andere
Bedeutung als beim Läufer. Die Eröffnungsbibliothek kann im
512Byte grossen EEPROM gespeichert werden.
Material-Baumsuche und Positions-Baumsuche
Interessant ist eine Feststellung
von Aske Plaat, dem
MTD(f)
Vater, die allgemein für Baumsuchen gilt und die mir auch schon
aufgefallen ist. Je weniger unterschiedliche Werte die
Bewertungsfunktion liefert, umso mehr Knoten werden durch
Beschneidung entfernt: "The coarser the grain of eval, the less
passes MTD(
f) has to make to converge to the minimax
value." Eine Bewertungsfunktion die nur die Materialdifferenz
liefert erlaubt viele Schnitte bei der Baumsuche. Noch einfacher
ist die Bewertung auf gewonnen, verloren oder Remis welche bei
Matt-in-N-Zügen Aufgaben genügt. Zur Untersuchung der Leistung der
Baumsuche Routinen NegaMax, NegaScout und MTD(f) gibt es das
Rahmenprogramm
baumsuche.c welche die
Bewertungsfunktion durch Zufallszahlen in einem Array simuliert.
Der Suchbaum ist immer gleich groß, nur die Anzahl der return
Werte der Bewertungsfunktion ist unterschiedlich.
return Werte
|
NegaMax
|
NegaScout Reinefeld
|
NegaScout
Wikipedia
|
MTD(f) ohne Hash
|
3
|
9222
|
9222
|
9222
|
9824
|
30
|
90224
|
72515
|
72592
|
89035
|
300
|
140032
|
105671
|
106338
|
342049
|
Tabelle: Besuchte End-Knoten in
einem Suchbaum mit Tiefe=6, Verzweigung=20.
Für eine schnelle Suche sollte die Baumsuche in zwei Teilen
erfolgen. Zuerst wird mit grosser Tiefe eine Baumsuche mit
einfacher Bewertungsfunktion aufgerufen. Im Endspiel genügen die
Werte für Matt-in-1, Matt-in-2, usw., Gewinn-in-1, Gewinn-in-2,
usw. und Remis. Im Mittelspiel sind zusätzlich die
Materialdifferenz der return Wert wenn die Suche nicht bis zum
Spielende sondern nur bis zu einer ruhigen Position geführt wird.
Wenn die "Material-Baumsuche" einen Gewinner-Zug findet wie
Matt-in-N oder Bauer schlägt gedeckte Dame mit +8 Materialgewinn
wird natürlich dieser Zug ausgeführt. Beim Eröffnungszug gibt es
für Weiss aber 20 Züge die alle die gleiche Materialdifferenz
Bewertung von 0 haben. Im Mittelspiel ist es üblich das die Hälfte
der Züge die gleiche gute Materialdifferenz Bewertung liefern.
Diese 10 bis 15 Züge müssen in einer zweiten Baumsuche mit einer
positionellen Bewertungsfunktion untersucht werden. Im einfachsten
Fall wird für diese Entwicklungszüge ein static evaluator ohne
Baumsuche aufgerufen. Oft muß die Position aber zuerst schlechter
werden um dann besser zu werden - das bekannte Problem der lokalen
Minima und Maxima. Die positionelle Baumsuche ist ein oder mehrere
Halbzüge weniger tief als die Material-Baumsuche. Natürlich muß
die positionelle Baumsuche nicht nach Matt suchen - das läßt sich
nicht mehr finden.
Hauptvariante Zug Sortierung
Die Halbzüge der Hauptvariante (Principal
Variation) beschreiben nach Ansicht des Schachprogrammes das
beste Spiel für Weiss und Schwarz. Wenn ein Hauptvarianten Halbzug
in einer Position möglich ist, dann wird damit mit guter
Wahrscheinlichkeit der Baum beschnitten. Während die Baumsuche
läuft werden unterschiedliche Hauptvarianten-Kandidaten angelegt.
Auf Ebene 1 gibt es einen 1 Halbzug langen Kandidaten, auf Ebene 2
gibt es einen 2 Halbzug langen Kandidaten usw.
Speicherplatzsparend werden die Hauptvarianten Kandidaten in einem
eindimensionalen Array abgelegt welches als Dreiecks-Matrix
benutzt wird. Wird mit Ebene 0 = Wurzel Ebene gearbeitet läßt sich
Ebene d nach Index i umrechnen mit i = ((d+1)*d)/2. Für d=0
ist i=0, für d=1 ist i=1 und für d=2 ist i=3. Die Halbzüge der
Ebene d werden unter Index i bis i+d abgelegt.
Endspiel King Mobility
Die Partie AVR-Max gegen Chess Champion Mk II zeigt die
typische Endspielschwäche der alten Schachcomputer. Trotz Turm,
Läufer und zwei Bauern gelingt AVR-Max kein Matt. Im Papier
"Programming a Computer for Playing Chess" von 1949 schreibt
Claude Shannon auch über die Bewertungsfunktion. Bei Shannon gibt
es einen Mobility Term. Für ein erfolgreiches Matt Setzen muß die
Mobilität des Königs immer weiter reduziert werden. Die Shannon
Mobilität "number of legal moves available to white" hilft nicht
viel im Endspiel. Die König Mobilität im Endspiel ist definiert
als "Anzahl der Felder die der König, auch in mehreren Zügen,
erreichen kann ohne in Schach zu geraten". Diese Definition
beschreibt eine Fläche. Die Königs-Fläche die der König von seiner
aktuellen Position aus erreichen kann ohne das die anderen Figuren
bewegt werden und ohne das der König in Schach gerät. Die
Ermittlung der König Mobilität kann erfolgen indem zuerst durch
den Zug-Generator die bedrohten Felder markiert werden (die
Umrandung der Königs-Fläche) und dann die Größe der Königs-Fläche
mit Hilfe des Flood-Fill Algorithmus o.ä. ermittelt wird.
Bei Endspielen wie König, Springer, Läufer gegen König dürfte die
Königs-Fläche nicht ständig kleiner werden (nicht monoton fallen).
Eine Baumsuche bleibt weiterhin nötig. Die Suchtiefe ist aber
nicht mehr bis zum Matt sondern nur noch bis zur echten(!) nächst
kleineren Königs-Fläche.
NegaScout oder MTD(f) anstelle von NegaMax
NegaScout
oder Principal Variation Search von Alexander Reinefeld ist eine
Verbesserung von NegaMax. MTD(f)
von Aske Plaat soll eine Verbesserung von NegaScout sein. In
beiden Fällen wird die Baumsuche an der Wurzel mit einem
Alpha-Beta Fenster mit Werten kleiner plus/minus Unendlich
gestartet. Bei NegaScout gibt es nur einen Aufruf mit zu kleinem
Suchfenster. Bei MTD(f) werden in einer Schleife solange minimale
Suchfenster probiert bis zum Erfolg. MTD(f) ist iterativer als
NegaScout. Bei NegaScout ist eine Hash-table empfehlenswert, bei
MTD(f) ist eine Hash-table notwendig. AVR-Max hat bei nur 1KByte
RAM keinen Platz für eine Hash-table die üblicherweise bei
128KByte Grösse beginnt. Bei Mikro-Max wird iterative deepening
mit einer aspiration
window NegaMax Suche verwendet. Diese mehrfache Baumsuche
mit eingeschränktem Fenster wird ähnlich effektiv wie NegaScout
und MTD(f) eingeschätzt.
Mikroprozessor Entwickler
Der Italiener Federico Faggin war der Designer der Intel
CPUs 4004, 8008, 8080 und der Zilog Z80 CPU. Bei Fairchild hatte
Faggin vorher den 3708 entwickelt, den ersten Chip in Silizium
Gate MOS (Metal Oxid Semiconductor) Technik, einen 8-fach
Analogmultiplexer wie der heutige 74HC4051.
Chuck Peddle hatte bei der Entwicklung des Motorola 6800
mitgearbeitet. Bei MOS Technology war er der Chefentwickler des
6502. Der 6502 war zuerst eine Niedrigpreisalternative
zu 6800 und 8080. Später zeigte sich das der einfache "Opcode
Fetch" Zyklus des 6502 gut passt zu dem Video-Refresh und
DRAM-Refresh von grafikfähigen Computern wie Apple II und
Commodore C64. Der 6502 war ein sehr guter Kompromis aus einfachen
internen Aufbau und guter Leistung für den Anwender.
Der englische Ingenieur Sophie Wilson hat die RISC (Reduced
Instruction Set Computer) populär gemacht. Die ARM (Acorn RISC
Machine) CPU cores sind oft eingebaut in elektronischen Geräten
die nicht als Computer angesehen werden, zB. dem Apple
iPhone. RISC bedeutet einfache Assemblerbefehle die schnell
von der CPU dekodiert und damit auch schnell ausgeführt werden.
Nachteil ist der grössere Speicherbedarf für Programme.
Mark Uniacke, HIARCS, 1981
Von Mark Uniacke gibt es das Schachprogramm HIARCS. Die erste
Programmversion stammt von 1981, aktuell gibt es die Version
HIARCS 13. Die HIARCS
Version 0.3 von 1981 ist geschrieben in PDP11 BASIC. Von
Andre Adrian gibt es eine Portierung von HIARCS
0.3 auf QuickBASIC 4.5 von Microsoft. Der QuickBASIC
Compiler von 1988 versteht noch BASIC mit Zeilennummern. Der
Nachfolger Visual Basic erlaubt BASIC Programme ohne Quelltext.
Interton VC4000 Schach II, 1982
Die Signetics 2650 CPU erschien
1975. Ab 1976 wurde die Videokonsole 1292 Advanced Programmable
Video System von Radofin vertrieben. Die Interton VC4000
Videokonsole benutzt die gleiche Hardware. Für die VC4000 gab es
zwei Schach-Cartidges. Cassette 13 mit einem 4KByte langen
Programm. und Cassette 22 aus dem Jahr 1982 mit 6KByte. Das VC4000
Schach zeigt kein Spielfeld, sondern nur den letzten Halbzug.

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


Abbildung links: ZX81 1KByte Chess.
Abbildung rechts: ZX81 1kchess gegen KIM-1 Microchess endet in
Zugwiederholung. Partie in
PGN.
Sargon III, 1983 und 1984
Im Jahr 1983 wurde Sargon 3 für den Apple 2
veröffentlicht. Im Jahr 1984 erschien Sargon 3 für den Commodore
C64. Auf dem C64 gibt es eine wunderschöne farbige
Spielfelddarstellung, auf dem Apple 2 leidet die farbige
Darstellung unter den typischen Farbsäumen. Sargon III wurde
Weihnachten 1984 für 49,95 $ angeboten für Apple II, Macintosh,
Commodore C64 und IBM PC laut New
York Times.


Bild links: Sargon
3 auf dem AppleWin
Apple 2e Emulator in Schwarz/Weiss. Mit Strg-Ü wird auf die
graphische Darstellung geschaltet.
Bild rechts: Sargon
3 auf dem VICE
Commodore C64 Emulator. Start mit LOAD "*",8,1 und RUN.
Mychess, 1984
David Kittinger ist neben Ron Nelson der dienstälteste
kommerzielle Programmierer für Mikrocomputer Schach. Das Programm
Mychess stammt von 1979, die MS-DOS Version des Programmes stammt
von 1984. Bei der WCCC
Weltmeisterschaft 1980 in Linz hat Mychess den 14. Platz
belegt. Weitere Turnierteilnehmer waren Belle (1. Platz), Chess
4.9 und Kaissa. Mychess lief auf einem Cromenco Mikrocomputer mit
Z80 CPU. David Kittinger ist laut Bruce Moreland der Erfinder des
0x88
Boards. Auch die Pre
Scan Heuristics (PSH) sind von ihm.

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


Bild links: Commodore
C64
Colossus
4 Intro
Bild rechts: Commodore C64 Spielfelddarstellung. Zugeingabe
erfolgt durch Eingabe von z.B. e2 RETURN e4 RETURN.
Cyrus II, 1985, 1986
Nach dem Ehepaar Spracklen war Richard Lang sehr
erfolgreich bei der World
Microcomputer
Chess Championship. Von 1985 bis 1990 haben Mephisto
Schachcomputer sechsmal mit seinen Programmen gewonnen. Der
Sinclair ZX
Spectrum 128 hatte mit 128KByte doppelt soviel RAM wie der
Amstrad CPC464 oder Commodore C64. Die 3D Darstellung des
Spielfeldes ist unübersichtlich - aber seinerzeit war es modern.
Cyrus II erschien zuerst auf Amstrad CPC464, dann ZX Spectrum
128K, MSX und zuletzt auf Commodore C64.



Bild links: Cyrus
II auf dem WinApe32
CPC464 Emulator. Start mit run "cyrus"
Bild mitte: Cyrus
II auf dem Klive
ZX Spectrum 128K Emulator von Steeve Snake. EmuZWin von
Vladimir Kladov ist auch ein guter Emulator.
Bild rechts: Cyrus II auf dem Spectrum in 2D Ansicht. Crafty 19.3
zerlegt Cyrus II auch auf Stufe 7. Die Partie in PGN.
Computerschach nach 1984
Mit dem Apple Macintosh wird 1984 der moderne
Bürocomputer eingeführt. Die Heimcomputer folgten dem Trend zu
16-Bit CPU und graphischer Benutzeroberfläche. Atari ST und
Commodore Amiga waren die letzten eigenständigen Entwürfe bevor
die IBM-PC Kompatiblen den Markt aufrollten. Wie so oft ging eine
Ära langsam zu Ende. Das Programm Cyrus II und auch der Spectrum
128K erschienen als die beste Zeit für 8-Bit Heimcomputer schon
vorbei war. Im Nintendo
Gameboy von 1989 leben die 8-Bit Computer weiter.
Die Schachcomputer konnten sich noch eine Zeitlang gegen die
IBM-PC Kompatiblen behaupten. Spätestens mit der Einführung der Intel 80486 CPU
Anfang der 1990er Jahre sind die Schachprogramme auf den
Bürocomputern dann den Schachcomputern davongerannt.



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


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


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

Bild links: Anfänger gegen Novag Obsidian auf Stufe EA1 mit 1
Halbzug Suche und 2 Halbzüge Abtausch Suche. Matt nach 32 Zügen.
Partie in PGN.
Bild rechts: Anfänger gegen Novag Obsidian, Stufe EA2, 1 Halbzug
Suche, 3 Halbzüge Abtausch Suche. Matt nach 41 Zügen.
Partie in PGN.
RISC und CISC
Die Unterschiede zwischen Reduced Instruction Set
Computer (RISC) und Complex Instruction Set Computer (CISC) sollen
am Beispiel der CPUs Atmel ATMega und Renesas H8 veranschaulicht
werden.
- 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.
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 Wiki-Elo-Liste.
CPU
|
Schachcomputer
|
Programmierer
|
Elo Punkte
|
Intel 8080,
1974, 8bit
|
Fidelity
Chess
Challenger
1, 1977
|
Ron Nelson
|
810
|
Fairchild F8,
1975, 8bit |
Data
Cash Systems CompuChess, 1977
|
D. B. Goodrich and Associates |
728
|
MOS Technology 6504,
1975, 8bit |
Commodore
Chessmate, 1978
|
Peter Jennings
|
814
|
Zilog Z80,
1976, 8bit |
Fidelity
Chess
Challenger
10, 1978 |
Ron Nelson |
1207 |
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 |
1218 |
GI CP1610, 1975, 16bit
|
Mattel
Intellivision USCF
Chess, 1981
|
Teletape, Inc., Russ Ludwick
|
?
|
Motorola 68000,
1979, 16bit
|
Mephisto
III-S Glasgow, 1984
|
Thomas Nietsche, Elmar
Henne
|
1776
|
Hitachi 6301,
1983, 8bit |
CXG
Star Chess, 1985
|
Kaare Danielson
|
1276
|
Intel 80C50,
198?, 8bit
|
Fidelity
The Gambit, 1987
|
Ron Nelson
|
1072
|
Hitachi HMCS40, 198?, 4bit
|
CXG
Sphinx
Chess
Card, 1989
|
David Levy, Mark Taylor
|
944
|
Motorola 68HC05, 198?, 8bit
|
Saitek
Sensor XL, 1995
|
Craig Barnes
|
1475
|
Acorn ARM,
1986, 32bit |
Mephisto
Risc 1MB, 1992
|
Ed Schröder
|
2260 |
Hitachi H8,
1990, 8/16bit
|
Saitek
GK 2000, 1992
|
Frans Morsch
|
1972 |
Sun SPARC,
1987, 32bit
|
Saitek
Sparc, 1993
|
Dan & Kathe Spracklen
|
2204
|
Motorola 68030,
1987, 32bit
|
Mephisto
London 68030, 1996
|
Richard Lang
|
2337
|
ATMega88V, 8bit
|
AVR
Max Schachzwerg, 2009
|
H.G. Muller, Andre Adrian
|
1290
|
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. Fast jeder bekannte Schach-Programmierer außer Richard Lang
und Kaare Danielsen hat mindestens ein 6502 Programm erstellt. Die
Elo Wertung liegt zwischen 814 und 2087. Eine ähnliche Leistung
von 2000 Elo holt das David Kittinger Programm im Novag
Obsidian aus einer H8 CPU mit 20MHz, 32KByte ROM und 1KByte
RAM. Bemerkenswert ist auch die Leistung der 4bit CPU von Hitachi.
Mit 0.5MHz Takt, 2.5KByte ROM und 80Byte(!) RAM haben die
Programmierer ein echtes "small is beautiful" Wunderwerk
geschaffen. Auch die F8 und 80C50 CPUs wurden wohl aufgrund des
niedrigen Preises ausgewählt. Die zweite Generation Schachcomputer
mit Fidelity Chess Challenger 10, Mephisto I, TRS80 Sargon II,
Atari 400 Computer Chess und TI99/4 Video Chess hatten schon genug
Spielleistung für Gelegenheitsspieler mit 1200 Elo Punkten.
Der Mephisto III von 1983 mit 1507 Elo war schon ein Gegner für
Klasse C Amateure.
Die Schach Cartridges für Saba Videoplay, Interton VC4000 und
Mattel Intellivision enthielten zusätzlichen RAM Speicher. Das
Schach-Module C7010 für die Magnavox
Odyssey
2 (Philips
G7000) enthielt sogar eine eigene CPU.
Die Entwicklung der 6502 CPU Schachcomputer:
CPU
|
Schachcomputer
|
Programmierer
|
Elo Punkte
|
6504, 1MHz |
Commodore
Chessmate, 1978 |
Peter Jennings |
814 |
6502, 2MHz |
Novag
Chess Champion Super System MK III, 1979
|
David Levy, Mike Johnson
|
1112
|
65C02, 2MHz
|
SciSys
Chess Champion Mark V, 1981
|
David Broughton, Mark Taylor
|
1466
|
6502, 3.2MHz
|
Fidelity
Elite A/S Budapest, 1983
|
Dan & Kathe Spracklen |
1755
|
65C02, 3.7MHz
|
Mephisto
MM II, 1985
|
Ulf Rathsman
|
1834
|
6502, 4MHz
|
SciSys
Turbostar 432, 1984
|
Julio Kaplan
|
1770
|
65C02, 4MHz
|
Mephisto
Monte Carlo, 1987
|
Frans Morsch
|
1881
|
6502, 5MHz
|
Novag
Super Forte C, 1990
|
David Kittinger
|
2036
|
65C02, 10MHz
|
Mephisto
Polgar 10 MHz, 1990
|
Ed Schröder
|
2087
|
Bemerkenswert bei den 6502 Programmen sind die ersten fünf Jahre.
Von 814 auf 1755 Elo bei einer Taktfrequenzsteigerung von 1MHz auf
3.2MHz.
Schach und künstliche Intelligenz
Viele Schachprogramme entstanden im Umfeld der
Künstlichen Intelligenz Forschung. Bis heute entzieht sich der
Begriff "Intelligenz" einer naturwissenschaftlichen Definition.
Einige Grundlagen der menschlichen Intelligenz werden allgemein
anerkannt: Ein Mensch kann aus Beispielen eine Regel
generalisieren. Diese "rule extraction" benötigt ein Gedächtnis
(memory). Beim Generalisieren oder Abstrahieren werden die
einzelnen Beispiele durch eine Schablone oder Regel (rule)
ersetzt. Diese Schablone ist weniger detailliert.
Höchstwahrscheinlich ist für "rule extraction" nicht nur Lernen im
Sinne von Beispiel-Ansammeln nötig sondern auch ein gezieltes
Vergessen. Die Ausnahmen widerlegen die Regel, werden aber bei der
Regel-Bildung ignoriert. Lernen und Vergessen sind die
Grundbausteine der menschlichen Intelligenz, wenn Intelligenz mit
Regelextraktion gleichgesetzt wird.
Ein Schachprogramm realisiert eine Baumsuche mit einer Bewertung.
Ausgehend von der aktuellen Brettstellung werden mögliche Züge
durch einen Zuggenerator berechnet. Kann der Schachcomputer bis
zum Spielende vorausrechnen kann der beste Zug fehlerfrei bestimmt
werden. Im Endspiel reicht die Rechenleistung dazu heute schon
aus. Im Mittelspiel wird die Vorausberechnung nach einer Anzahl
von Zügen abgebrochen und die entstehende Position wird bewertet.
Die Bewertungsfunktion ist in allen Details vom Programmierer
vorgegeben. Eine gute Bewertungsfunktion liefert für möglichst
viele Positionen eine korrekte Bewertung im Sinne von "Weiss im
Vorteil" oder "Schwarz im Vorteil".
Der Schachprogrammierer ist auf jeden Fall intelligent. Es ist
eine schwierige Aufgabe die - höchstwahrscheinlich unbewusst
ablaufende - eigene Regelextraktion bewusst zu machen und dann in
einer Programmiersprache zu formulieren. Das Schachprogramm selbst
führt keine Regelextraktion aus. Es wendet die vom Programmierer
vorgegebenen Regeln an.
Eventuell gibt es doch Gemeinsamkeiten zwischen den Abläufen im
Gehirn eines Schach spielenden Menschen und in einem
Schachprogramm. Vielleicht laufen die Funktionen Baumsuche und
Bewertung auf einer unbewußten Ebene ab. Das "bewußte Ich" des
Schachspielers hat nicht Zugriff auf seinen "unbewussten Computer"
sondern erhält nur die Ergebnisse der Rechenvorgänge mitgeteilt.
Als Beleg mag folgendes Beispiel dienen: Nachdem die Figurbewegung
gelernt ist, spielt ein Schachneuling sehr langsam. Jeder Zug wird
"vorausberechnet". Durch die Rückmeldung aus den verlorenen und
gewonnenen Spielen werden Regeln extrahiert. Diese gelernten
Regeln machen das Schachspiel immer schneller und besser.
Irgendwann wird vor allem das Eröffnungsspiel und das Endspiel
nicht mehr langsam "vorausberechnet" sondern schnell durch
Regel-Anwendung gespielt. Ein Schach Könner ist entstanden. Im
Mittelspiel ist die Anzahl der Varianten am grössten und deshalb
die Regel-Extraktion am schwierigsten. Deshalb werden
Schachpartien oft am Ende des Mittelspiels aufgegeben: Beiden
Schachspielern ist klar wie das Endspiel ausgehen wird.
Die Schach
Endspiel Theorie wird heute im Zusammenspiel zwischen Mensch
und Computer korrigiert: Inverse
Zuggenerator Programme erzeugen vollständige Bäume von
Endspielen. Schachmeister führen auf diese vollständigen
Informationen die Regelextraktion aus. Die Bücher "Secrets of Rook
Endings" usw. von John Nunn enthalten die Erkenntnisse aus den
Endspiel Datenbanken von Ken Thompson.
Baumsuche
Die Baumsuche ist von den Spielregeln unabhänging. Für
die 2-Personen Spiele Tic Tac Toe,
Vier Gewinnt,
Dame, Schach usw. kann die gleiche Baumsuche verwendet werden. Der
Minimax
Algorithmus ist eine vollständige Baumsuche mit korrekter
Rückmeldung der Ergebnisse. Durch Alpha-Beta
Beschneidung (Pruning) kann die Baumsuche stark beschleunigt
werden. Alpha-Beta liefert die gleichen Ergebnisse wie Minimax.
Eine weitere Verbesserung ist Principal
Variation Suche. Hier wird im ersten Anlauf mit einem
minimal kleinen Suchfenster gesucht. War die Suche erfolglos, wird
die Suche mit einem normal grossen Suchfenster wiederholt. Noch
schneller ist die Null-Zug
Heuristik Suche. Diese Baumsuche ist aber nicht mehr
vollständig. Im Endspiel oder bei Zugzwang
Schachaufgaben kann die Lösung übersehen werden. Deshalb wird im
Endspiel Null-Zug Suche abgeschaltet.
Damit Alpha-Beta und Principal Variation Suche optimal arbeiten
müssen die Züge sortiert sein. Der stärkste Zug muß zuerst
bewertet werden. Die Sortierung der Züge an der Baum-Wurzel läßt
sich durch schrittweise Vertiefung (iterative
Deepening) erreichen. Die Killer-Zug
Heuristik hilft bei der Zugsortierung weiter unten im Baum.
Das iterative Deepening läßt sich auch auf allen Baumsuch-Ebenen
anwenden.
Die gleichen Stellungen lassen sich über verschiedene Zugfolgen
erreichen (z.B. 1. e4 e5, 2. d4 d5 oder 1. d4 d5, 2. e4 e5). Diese
Wiederholungen können mit Hilfe einer Hash-Tabelle
(hash table, transposition
table) erkannt werden. Anstelle eine Baumsuche des gleichen
Teilbaums auszuführen wird das Ergebnis aus der Hash Tabelle
übernommen. In der Hash-Tabelle steht pro Eintrag üblicherweise
ein zweiter Hash-Schlüssel um Kollisionen zu erkennen. Weiterhin
die Baumtiefe, Alpha- und Beta-Werte der originalen Suche um
festzustellen ob das Suchfenster der alten Suche den Anforderungen
der neuen Suche genügt (MiniMAX
Hashtabellen).
Bewertung
Die Bewertung einer Brettposition ist von den
Spielregeln abhängig. Bei vollständiger Baumsuche wie sie z.B. bei
Tic Tac Toe, Vier Gewinnt und auch bei Schachendspielen bis 7
Figuren heute möglich ist, genügt die Feststellung von gewonnen,
verloren oder unentschieden (Remis, Patt). Im Schach Mittelspiel
ist eine vollständige Baumsuche bis zum Partieende nicht möglich.
Hier müssen "Faustformeln" (Heuristiken) für die Bewertung benutzt
werden.
Eine Bewertungsfunktion kann ohne tiefe Baumsuche benutzt werden.
Eine falsche Beurteilung durch die Bewertungsfunktion hat bei
einer solchen 1-Halbzug Baumsuche die stärkste Auswirkung. Die
Fehler der Bewertungsfunktion werden durch eine tiefere Baumsuche
abgeschwächt. Einmal werden Partieende-Positionen mit einer
abschließenden Bewertung erreicht, z.B. beim Schäfermatt,
Seekadettenmatt.
Zweitens werden Schlagfolgen bis zum Ende verfolgt und erst dann
beurteilt. Dies läßt den Computer Gabeln, Opfer usw. erkennen.
Materialbewertung
Die einfachste Bewertung ist die Materialbewertung.
Turing schreibt darüber: "A very simple form of
values, but one not having this property, is an evaluation of
material, e.g. on the basis– Pawn = 1, Knight = 3, Bishop =
3.5, Rook = 5, Queen = 10, Checkmate = 1000. If B is black's
total and W is white's, then W/B is quite a good measure of
value. This is better than W – B... ". Shannon
schreibt "The relative values of queen, rook, bishop, knight and
pawn are about 9, 5, 3, 3, 1, respectively"
Heute üblich ist Bauer=1, Springer, Läufer=3, Turm=5, Dame=9 und
König=Unendlich. Die Materialbewertung ist Weisses Material -
Schwarzes Material. Zur Materialbewertung gehört auch die
Erkennung von Spielende. Einmal durch Schachmatt, aber auch durch
Remis, Patt, 50-Zug-Regel, 3-fache Wiederholung und Partieende
durch zuwenig Material, z.B. nur noch König, zwei Springer und
König auf dem Feld. Ein Matt in einem Zug sollte übrigens besser
bewertet werden als ein Matt in zwei Zügen um "ewige" Partien zu
vermeiden.
Besonders im Mittelspiel liefert die Baumsuche mit
Materialbewertung oft mehrere Züge mit gleicher Bewertung zurück.
Aus diesen Kandidatenzügen kann ein Zug per Zufall ausgesucht
werden. Besser ist eine positionelle Bewertung dieser von der
Materialbewertung her gleichwertigen Züge.
Positionelle Bewertung
Das Schach Fachwissen (domain knowledge) der Brute Force
Schachprogramm Autoren zeigt sich in der positionellen Bewertung.
Alan Turing schreibt: "If I were to sum up the weakness of the
above system in a few words I would describe it as a caricature of
my own play. It was in fact based on an introspective analysis of
my thought processes when playing, with considerable
simplifications. It makes oversights which are very similar to
those which I make myself".
Siegbert Tarrasch
Dr. Siegbert Tarrasch hatte keine
Verbindung zum Computerschach. Er war aber ein guter Schachspieler
der als Autor seine Einsichten präzise zu Papier brachte. Sein
Buch "Das Schachspiel" von 1931 ist immer noch eine gute
Einleitung zu den Themen Endspiel und Mittelspiel. Die Eröffnung
wird natürlich auch behandelt. Für Tarrasch besteht das Spiel aus
den Faktoren Kraft, Raum und Zeit. Die Kraft wird heute
Materialbilanz genannt und die Zeit ist besser als Tempo bekannt.
Der Raum ist abstrakter, er beschreibt die Herrschaft über das
Spielfeld, besonders über die eigene Spielfeldhälfte, d.h. die
erste bis vierte Reihe für Weiss. Eine geöffnete Linie ist ein
Beispiel für Raumgewinn.
Tarrasch schreibt über die Kraft: "Springer und Läufer sind gleich
stark, jeder ungefähr gleich drei Bauern. Der Turm ist stärker als
eine leichte Figur [Springer, Läufer]. Zwei leichte Figuren sind
stärker als ein Turm. Die Dame ist so viel wert wie die beiden
Türme oder wie drei leichte Figuren." Die übliche
Materialbewertung von Springer, Läufer = 3, Turm = 5 und Dame = 9
Bauerneinheiten findet sich schon bei Tarrasch.
Das vorhandene Material beeinflußt die Materialbilanz laut
Tarrasch: "Turm, eine leichte Figur und ein Freibauer auf der
sechsten Reihe sind stärker als die Dame. Zwei leichte Figuren
sind um 0,5 Bauern stärker als Turm und ein Bauer. Wenn ein
Springer im Zentrum steht, auf den Linien c-f, auf der vierten bis
sechsten Reihe, womöglich gedeckt von einem Bauern und
unangreifbar durch einen Bauern, dann ist er dem Läufer überlegen
und beinah so stark wie ein Turm. Hat ein Spieler einen
Mittelbauern gegen einen Springerbauern, so wird er etwas im
Vorteil sein."
Was Tempo im Schach bedeutet zeigt Tarrasch anschaulich für die
Eröffnung: "Rochade = 1 Tempo, die Dame entwickelt = 1 Tempo, Turm
der mindestens die dritte Reihe erreichen kann = 1 Tempo, Turm auf
einer halboffenen Linie = 1 Tempo, Läufer bewegt = 1 Tempo,
Springer auf der zweiten oder dritten Reihe = 1 Tempo, Springer
auf der vierten oder fünften Reihe = 2 Tempi, Springer auf der
sechsten oder siebten Reihe = 3 Tempi, Bauer der c, d oder e Linie
gezogen = 1 Tempo".
Die Baumsuche kann nur einen Minimax-Wert liefern, deshalb müssen
Kraft und Zeit in der gleichen Einheit gemessen werden. Hier sagt
Tarrasch: "erst drei Tempi sind genügend, ein Gambit zu
rechtfertigen". Ein Gambit bedeutet ein Bauernopfer, d.h. 1 Bauer
= 3 Tempi.
Claude Shannon
Die Bewertungsfunktion f(P) besteht bei Shannon aus der
Materialbewertung, einem Abschlag für schlechte Bauernstellungen
(doppelter Bauer, rückständiger Bauer und isolierter Bauer) sowie
einem Mobilitätsbonus:
f(P)=200(K-K')+9(Q-Q')+5(R-R')+3(B-B'+N-N')+(P-P')-.5(D-D'+S-S'+I-I')
+.1(M-M')+...
in which:-
K,Q,R,B,B,P are the number of White kings, queens, rooks, bishops,
knights
and pawns on the board.
D,S,I are doubled, backward and isolated White pawns.
M= White mobility (measured, say, as the number of legal moves
available
to White).
Alan Turing Papiermaschine
Die Papiermaschine
von Alan Turing arbeitet mit folgender positionellen Bewertung:
Jeder weiße Stein leistet einen Beitrag zur Spielposition, ebenso
der schwarze König. Alles muß aufaddiert werden, um die Bewertung
der Spielposition zu ermitteln.
For a Q, R, B, or N, count
- The square root of the number of moves the piece can make
from the position, counting a capture as two moves, and not
forgetting that the king must not be left in check.
- (If not a Q) 1.0 if it is defended, and an additional 0.5 if
twice defended.
For a K, count
- For moves other than castling as (1) above.
- It is then necessary to make some allowance for the
vulnerability of the K. This can be done by assuming it to be
replaced by a friendly Q on the same square, estimating as in
(1), but subtracting instead of adding.
- Count 1.0 for the possibility of castling later not being
lost by moves of K or rooks, a further 1.0 if castling could
take place on the next move, and yet another 1.0 for the
actual performance of castling.
For a P, count
- 0.2 for each rank advanced.
- 0.3 for being defended by at least one piece (not P).
For the black K, count
- 1.0 for the threat of checkmate.
- 0.5 for check.
Turing selbst hat eine Partie
seiner Papiermaschine gegen Alick Glennie notiert. Für das
Schachprogramm Fritz gibt es eine Turing Engine. Eine
Partie zwischen den Schachprogrammen Turing und Fritz 6 zeigt die
Schwächen der Turing Positionsbewertung und auch einen Fehler in
der Engine Implementierung - der Springer hat auf f3 eine bessere
Mobilität als auf h3. Der Bauer auf a4 und die Dame auf f3
erlauben eine hohe Mobilität, dürften aber selbst einem Schach
Neuling als wenig sinnvolle Eröffnungszüge erscheinen.

Bild links: Turing Papiermaschine (Schach Engine) - Fritz 6.
Position nach dem 5. Zug. Beide Programme spielten ohne
Eröffnungsbibliothek.
Bild rechts: Turing Papiermaschine (von Turing ausgeführt) - Alick
Glennie, 1952. Position nach dem 8. Zug. Die Dame diesmal ohne
Wandertrieb - hat Turing hier gemogelt?
Peter Jennings Microchess
Die positionelle Bewertung von Microchess von Peter
Jennings ist umfangreicher. Die Details stehen im Programmer'
Manual. Die Bewertung ist:
MOB Mobliity. The total
number of moves available for a
given side from
a given position. Each queen move is
counted as two
moves,
MAXC Maximum Capture.
The number of points,to be gained
by cacturing
the most valuable piece currently under
attack.
CC Capture
Count. The total points of all
opposing
pieces under
attack.
MAXP Maximum Capturable
Piece. Identification of the
opponent's
piece under attack which is worth the most
points.
PRIOR COUNTS (.PMOB, .PMAXC, PCC, .PMAXP) reflect
the status
of the position as it exists for the computer before any
move
is made. This is a benchmark, against which further moves
are
to be compared.
CONTINUATION COUNTS (.WMOB, .WMAXC, .WCC, .WMAXP) are obtained
for each move tested to determine the
potential of the new
position that would result if the move were made.
REPLY COUNTS (.BMOB, .BMAXC, .BCC, .BMAXP) are
obtained for
each move tested to determine the
potential danger of the
opponent's available replies.
EXCHANGE COUNTS (.WCAPO, .WCAP1,
.WCAP2, .BCAP0, .BCAP1,
.BCAP2) are used to analyse
the effect of the potential
exchange combinations. Each count reflects the maximum
number
of points capturable at each level of an exchange combination.
Capture chains are halted by pawn captures, king captures,
or
by reaching a limit of three captures per side.
In addition, information regarding the moving piece and its TO
and FROM squares can also be used by the STRATGY algorithm.
All information available is combined by the algorithm in
the
subprogram STRATGY to calculate a single strategic
value for
the move under analysis. The algorithm, a weighted sum of
the
count information, is shown below:
VALUE = + 4.00 * WCAP0
+ 1.25 * WCAP1
+ 0.75 * (WMAXC +
WCC)
+ 0.25 * (WMOB
+ WCAP2)
- 2.56 * BMAXC
- 2.00 * BCC
- 1.25 * BCAP1
- 0.50 * BMAXC
- 0.25 * (PMAXC + PCC
+ PMOB + BCAP0 + BCAP2 + BMOB)

Bild links: Soft6502 KIM-1 Simulator von Charles Bond führt Microchess
aus. 0F1333 bedeutet Microchess eröffnet mit Königsbauer e2-e4.
Bild rechts: Microchess zählt die Spalten a bis h als 0 bis 7 und
die Reihen 1 bis 8 ebenfalls als 0 bis 7.
Wieviel Bewertung ist nötig?
Claude Shannon schreibt schon 1949 in "Programming
a Computer for Playing Chess":
The more violent tactical weapons, such as discovered checks,
forks and pins by a piece of lower value are omitted since they
are best accounted for by the examination of specific variations.
Bei Schachaufgaben genügt es Matt und die anderen Spielende
Bedingungen wie Patt und Remis zu bewerten. Hierzu
David Broughton, Programmierer des Scisys
Chess
Champion
Mark V von 1981:
Wiki: The Mark V was not only very well playing, he was
also the best chess puzzle solver for many years. What was his
secret?
D.B.: Simply efficient programming to a fixed depth of
search and cutting out all material and positional evaluations
other than the king value.
Die heutige Suchtiefe von 13 bis 15 Halbzügen macht für Ed
Schröder einiges Schach Fachwissen im Programm unnötig:
To escape from the horizon effect all kind of tricks were
invented, chess knowledge about dangerous pins, knight forks,
double attacks, overloading of pieces and reward those aspects in
eval. Complicated and processor time consuming software it was (15-20%
less performance) but it did the trick escaping from the horizon
effect in a reasonable way.
Today we run chess program on 1500 Mhz machines and instead of the
5-7 plies Rebel now gets 13-15 plies in the middle game and the
horizon effect which was a major problem at 5 Mhz slowly was
fading away.
So I wondered, what if I throw that complicated "anti-horizon"
code out of Rebel, is it still needed? So I tried and found out
that Rebel played as good with the "anti-horizon" code as without
the code. In other words, the net gain was a "free" speed gain of
15-20%, thus an improvement.
Thomas Nietsche, Elmar Henne schreiben über das nötige
Schachwissen einer Baumsuche am Beispiel Mephisto
III:
"Finde einen Schlüsselzug, der dem Gegner zu einer oder zu wenigen
Antworten zwingt; setze 1-2 Züge mit Druck fort; rechne sie i.A.
klare Abwicklung durch." Wenn Sie als Leser die mehr oder weniger
berühmten Kombinationen unter diesem Gesichtspunkt betrachten, so
werden Sie feststellen, daß sich 90%-95% unter diesem Schema
subsumieren lassen.
Michail Botwinnik schreibt in "Computers in Chess" über die
Probleme einer Bewertungsfunktion ohne Baumsuche:
In chess, on the other hand, the data destined for analysis is
deeply hidden in the initial data. The principal task consists in
transforming the initial data to a form suitable for analysis.
Herein lies one of the reasons for our delay in finishing
PIONEER-1.
Bobby
Fischer fasst zusammen: "Concentrate on material gains.
Whatever your opponent gives you take, unless you see a good
reason not to."
Nach den obigen Empfehlungen kann ein Schachprogramm so vorgehen:
Eine erste Tiefensuche liefert nur Gewinn, Unentschieden (Patt,
Remis), Verlust oder Unbekannt, wenn die Suchtiefe nicht
ausreicht. Falls diese Schachmatt-Tiefensuche das Ergebnis
Unbekannt liefert, dann startet eine zweite Tiefensuche. Diesmal
ist die maximale Suchtiefe kleiner und die Bewertungsfunktion
liefert die Materialbalance. Findet diese zweite Tiefensuche
keinen Zug der den anderen Zügen überlegen ist, dann folgt eine
dritte Tiefensuche mit einer komplexen Bewertungsfunktion. Die
maximale Suchtiefe ist bei der ersten Tiefensuche am größten und
bei der dritten Suche am kleinsten. Die Bewertungsfunktion der
dritten Tiefensuche darf auch fehlerhafte Heuristiken
enthalten. Die erste und zweite Tiefensuche haben die schweren
Fälle wie Schachmatt oder Materialverlust schon gefunden.
Die Strategie des Läuferendspiel
(König und zwei Läufer gegen König) ist die Beweglichkeit des
König einzuschränken bis eine Mattführung in der Ecke möglich ist.
Im Bauernendspiel wird die Quadratregel
benutzt um festzustellen welcher Bauer erfolgreich in eine Dame
umgewandelt werden kann. Weitere bekannte Endspielstrategien sind
die Abdrängung
und das Réti
Manöver. Diese Endspielstrategien lassen sich als spezielle
Bewertungsfunktionen ausprogrammieren. Diese Erweiterungen haben
die Endspielschwäche der frühen Schachprogramme überwunden.
Eröffnungsbibliothek
Für den ersten Zug von Weiss gibt es 20 Möglichkeiten: 8
Bauernzüge um ein Feld, 8 Bauernzüge um zwei Felder und 4
Springerzüge. Schwarz hat ebenfalls 20 Möglichkeiten zur Auswahl.
Von diesen 20*20 Möglichkeiten werden 1. e4, e5 und 1. d4, d5 am
meisten gespielt. Eine Eröffnungsbibliothek katalogisiert den
Anfang einer Schachpartie. Wichtig sind die Eröffnungszüge welche
Weiss und Schwarz gleiche Chancen für das Mittelspiel lassen. Die
Enzyklopädie der Schacheröffnungen ("Encyclopedia of Chess
Openings") sortiert mit den ECO-Codes die
ausgewogenen Eröffnungen in 5 Bänden. Die ECO-Codes A00 bis E99
entsprechen 500 Gliederungsfächern. Dabei ist die Belegung der
Fächer sehr unterschiedlich. Unter A00 werden 14 der 20
Eröffnungszüge abgelegt. Die Damengambits D68 und D69
unterscheiden sich erst ab dem 13. Zug.
500 Eröffnungen bei einer Spieltiefe von durchschnittlich 6 Zügen
oder 12 Halbzügen ergibt einen Verzweigungsfaktor 12-te Wurzel aus
500 = 1.68. In einer Baumdarstellung mit 2 Halbzügen pro Baumebene
benötigt man dann 2 + 2*2 + 2*2*2 ... + 2^12 = 2^13 -1 = 8191
Speicherplätze für die Eröffnungsbibliothek.
Ein solches Eröffnungswissen vermeidet schlechte Züge in der
Eröffnung bei Spieler oder Schachprogramm. Microchess von Peter
Jennings zeigt den typischen Damen Wandertrieb aufgrund der
Mobilitätsbewertung deutlich: 1.e4 c5 2.Dh5. (Üblich ist die
sizilianische Verteidigung mit 2. Sf3). Die Eröffnung 1.e4 e5
2.Sf3 Sc6 3.Lc4 Lc5 4.c3 Sf6 5.d4 xd4 6.xd4 Lb4+ 7.Sc3 Sxe4 8.0-0
Lxc3 9.d5 (italienische Partie - Möller Angriff) spielt Microchess
komplett aus der Eröffnungsbibliothek, obwohl Microchess keine
richtige Rochade kann - es bewegt nur den König um zwei Felder.
Einige Schachcomputer wie die Mephisto
Schachschule II konnten die Rochade nur aus der
Eröffnungsbibliothek ausführen.
Im Microchess Programm werden für die Eröffnungsbibliothek pro Zug
(zwei Halbzüge) nur die Informationen weisse Figur, Nach-Feld
weisse Figur und Nach-Feld schwarze Figur abgelegt. Die
Eröffnungsbibliothek enthält somit 1.Be4 e5 2.Sf3 c6 3.Lc4 c5
4.Bc3 f6 5.Bd4 d4 6.Bd4 b4 7.Sc3 e4 8.0-0 c3 9.Bd5. Microchess
kann genau eine maximal 9 Züge lange Eröffnung speichern. Manche
heutige Schachprogramme kennen die komplette Enzyklopädie und noch
mehr.
Das einfachste Schachprogramm
Im Internet lassen sich etliche Schachprogramme im
Quelltext finden. Das einfachste Schachprogramm
- historisch gesehen ist die Schach
Papiermaschine (1952) von Alan Turing.
- für den KIM-1 6502 Mikrocomputer ist Microchess
(1976) von Peter Jennings.
- für den Z80 mit guter Spielstärke ist Sargon (1978) von Dan
& Kathe Spracklen in TDL
ZASM.
- für den 6502 mit guter Spielstärke ist Atari 2600 Video
Chess (1979) von Larry Wagner, IM Julio Kaplan und Bob
Whitehead.
- für den ZX81 Z80 Mikrocomputer ist das 672 byte lange ZX81
Schachprogramm (1983) von David Horne.
- aus einem Buch ist MiniMAX
(1995) von Christian "Chrilly" Donninger.
- mit guter Spielstärke in C ist TSCP
(1997) von Tom Kerrigan.
- in C ist das unter 2000 Quelltext Zeichen lange Micro-Max
(2005) von Harm-Geert Müller.
Dan & Kathe Spracklen SARGON
Aus dem Buch "SARGON A Computer Chess Program" von Dan
& Kathe Spracklen, 1978, Verlag Hayden kommt die Beschreibung
eines klassischen Schachprogrammes:
SARGON is written in Z-80 assembly language using the TDL Macro
Assembler. The program occupies 8K of RAM, which includes 2K of
data areas, 2K graphics display and user interface, and 4K move
logic. The move logic is the heart of SARGON. It is displayed in
the block diagram as the set of routines called by FNDMOV (Find
Move). FNDMOV controls the search for the computer's best move by
performing a depth first-tree search using the techniques of alpha
beta pruning. Listed first under FNDMOV's calls on the block
diagram is PINFND (Pin Find Routine). PINFND produces a list of
all pieces pinned against the king or queen for both white and
black. Pinned pieces must be treated carefully when analyzing
battles engaged on the chess board, since their attacking power
may be an illusion. FNDMOV also calls POINTS (Point Evaluation
Routine). POINTS performs a static evaluation and derives a score
for a given board position. POINTS takes factors of material,
board control, and development into account. Predominant in the
evaluation is material. Material scores must be adjusted to
reflect unresolved battles on the chess board. It is the function
of XCHNG (Exchange Evaluation Routine) to judge the outcome of
these unresolved battles. The factors of development and board
control are not allowed to dominate the move choice. LIMIT is
called to truncate the contribution of those factors to the score.
FNDMOV controls the generation of legal moves by GENMOV (Generate
Move Routine). GENMOV produces the move set for all of the pieces
of a given color. For each piece in turn, GENMOV calls MPIECE
(Piece Mover Routine), which generates all the possible legal
moves for a given piece. MPIECE itself calls a series of routines.
PATH generates a single possible move for a given piece along its
current path of motion. ADMOVE adds a move to the move list.
CASTLE and ENPSNT (En Passant Pawn Capture Routine) handle the
special moves. After MPIECE has produced all legal moves, GENMOV
calls INCHK, which determines whether or not the king is in check.
Basic to the success of alpha beta pruning is the sorting of moves
generated at each ply level. FNDMOV calls SORTM (Sort Routine) to
accomplish this task. A sort is dependent on an evaluation, so
SORTM calls EVAL (Evaluation Routine). To evaluate a given move on
the move list, EVAL first makes the move on the board by calling
MOVE. It is determined if the move is legal by calling INCHK.
Then, if the move is legal, it is evaluated by calling PNFND and
POINTS. Finally, EVAL restores the board position by calling
UNMOVE.
The bookkeeping required by alpha beta pruning is for the most
part coded in line in FNDMOV. However, FNDMOV calls ASCEND (Ascend
Tree Routine) to adjust all the parameters in transferring the
parameters up one ply in the tree.
At the bottom of FNDMOV's call list on the block diagram is BOOK.
BOOK provides, an opening book of a single move. lf white, SARGON
will play P-K4 or P-Q4 at random. If black, SARGON replies to any
opening move with P-K4 or P-Q4, whichever is most appropriate.
The move selection logic of FNDMOV is embedded in a whole network
of routines that forms SARGON's interface to the outside world.
The DRIVER routine initiates and coordinates, the entire game.
First on the block diagram in DRIVER's list of calls is CHARTR
(Accept Input Character). CHARTR is a totally machine-dependent
input routine whose sole purpose is to accept a single character
input from the keyboard. All machine-dependent aspects of SARGON
have been isolated in this manner to simplify conversion to Z-80
machines running under different operating systems.
Machine-dependent code appears in only two other places. The first
is the macro definition area, where all the output functions are
listed, and the second is in the routine DSPBRD (Display Graphics
Board and Pieces), where machine-dependent lines of code are
clearly marked.
Next on the block diagram is ANALYS (Set Up Position for
Analysis). ANALYS allows the user to set the board to any position
of his choosing. The routine blinks the graphics board squares in
turn, allowing the user to input a piece ofhis choice or leave the
contents unchanged. When the board has been set to the desired
arrangement of pieces, play of the game may be resumed. ANALYS
also provides a handy means of correcting a move entered by
mistake.
As a part of game initialization, DRIVER calls INTERR (Interrogate
for Ply and Color). INTERR questions the player for his choice of
white or black, and allows him to select the depth of search.
DSPBRD and INITBD complete initialization by setting up the
graphics board display and internal board array. PGIFND (New Page
if Needed) and TBCPCL (Tab to Computer's Column) are used to
control spacing in the move list. The move list is displayed to
the left of the graphics board on the video screen.
The most important routines called by DRIVER are, of course,
CPTRMV and PLYRMV, which are control routines for the computer's
and player's moves, respectively. Central to CPTRM V is FNDMOV,
the logic to select the computer's move, which has already been
discussed. Below FNDMOV on the block diagram is FCDMAT (Forced
Mate Handling). If the computer is checkmated, it acknowledges the
fact with a message displayed in the move list and by tipping over
its king. Assuming the computer is not mated, MOVE makes the
chosen move on the board array and EXECMV displays it on the
graphics board. In displaying the move, the piece first blinks a
few times, moves to its new location, and then blinks a few times
again. The function of BITASN (Board Index to ASCII Square Name)
is to convert the internal move into a representation in algebraic
chess notation on the move list, then INCHK determines whether or
not the computer should call "Check."
When the opponent is on the move, PLYRMV controls the events. It
calls CHARTR to accept the move entry. ASNTBI (ASCII Square Name
to Board Index) converts the move to internal representation. Then
VALMOV checks the player's move for validity. If the move is
legal, EXECMV displays it on the graphics board as in CPTRMV.
PGIFND (New Page if Needed) and TRPLCL (Tab to Player's Column)
control spacing in the move list.

Bild: Calltree von Sargon
Weitere Schachprogramme im Quelltext
Auf WBEC
Ridderkerk gibt es eine Rankinglist von Schachprogrammen.
Über die Download Seite findet man die im Quelltext verfügbaren
Schachprogramme in C/C++:
Rank Program: Rating + - games score Av.Opp draws Lang.GUI Lizenz
3 Fruit X060620a 2852 63 61 92 64% 2754 28% C++ UCI GPL
8 Glaurung 1.2-X64 2779 57 57 92 53% 2757 46% C++ UCI GPL
12 Scorpio 1.8 2747 59 59 92 48% 2758 36% C++ xboard own
24 Crafty 20.13BH-x64 2664 60 59 88 62% 2589 40% C xboard freeware
76 Phalanx XXII 2455 18 18 1084 48% 2467 25% C xboard GPL
101 Resp 0.19 2349 19 19 1020 48% 2360 25% C++
138 GNUChess 4TM 2215 29 29 444 52% 2198 21% xboard
176 GNU Chess 5.00+ 2022 76 77 60 48% 2035 20% xboard
247 TSCP 1.81 1655 41 41 272 47% 1675 15% C xboard
Bayesian Elo Ratinglist WBEC Ridderkerk after edition 15:
Rank Program: Rating + - games score av.Opp draws
3 Fruit 2.3.4n-x64 2962 67 63 92 73% 2795 26%
7 Glaurung 2.01-x64 2858 61 59 92 60% 2800 37%
12 Scorpio 2.0-x64 2794 60 61 92 48% 2803 32%
42 Crafty 22.0-x64 2630 65 69 92 26% 2810 24%
95 Phalanx XXII Reb 2434 62 61 92 51% 2428 25%
120 Resp 0.19 2342 17 17 1232 47% 2363 26%
160 GNUChess 4TM 2207 27 26 528 52% 2193 21%
194 GNU Chess 5.00+ 2014 76 77 60 48% 2028 20%
235 Amundsen 0.60ja 1846 136 143 25 46% 1876 4%
236 micro-Max 4.8-m 1845 143 142 25 56% 1752 8%
278 TSCP 1.81 1662 37 38 328 44% 1701 15%
302 Cefap 0.7.2 1455 53 55 161 36% 1588 16%
Einfache Schachprogramme mit graphischer Oberfläche
Das WinBoard
(XBoard) Programm stellt für Schachprogramme (chess engines) eine
graphische Oberfläche zur Verfügung. Einmal für Mensch/Maschine
Spiele, aber auch für das Schach Spiel zwischen zwei
Schachprogrammen. WinBoard enthält GNUChess als Schachprogramm.
Weitere Schachprogramme lassen sich über die winboard.ini Datei
leicht einbinden. Die einfachen Schachprogramme TSCP, Micro-Max
und MiniMAX
gibt es mit WinBoard Schnittstelle.
Ohne WinBoard laufen die MiniMAX Versionen DelphiMAX
und MyMAX.
Weitere Internet Links
Das SARGON CMD für TRS-80 und das Channel F BIOS ROM
stammt von Planetemu.
Das System 80 (TRS-80 Clone) ROM stammt von Dick
Smith.
Das TRS-80 Model 3 ROM stammt aus dem TRS-80 Emulator von
Matt Hamilton.
Das Atari VCS 2600 Videochess ROM stammt von AtariAge.
Das Channel F Schach ROM stammt von der Channel
F Info Seite aus dem Multi Game ROM.
Improving
a
Chess
Classic beschreibt die Entwicklung von Sargon 2 zu Sargon 3.
Literatur
Schach ist ein altes Spiel. Die deutsche Übersetzung der
Philidor Einleitung von 1754 ist heute noch lesenswert. Die heute
klassischen Einleitungen in das Schachspiel von Tarrasch oder
Nimzowitsch erschienen 1931. Computerschach hatte seine Blütezeit
zwischen 1970 und 1990. Die Bücher gibt es im Antiquariat oder als
Nachdrucke.
Colditz, Karl; Lehr-, Übungs- und Testbuch der
Schachkombinationen; Edition Olms, 1992; ISBN 978-3-283-00302-9
Frey, Peter W.; Chess Skill in Man and Machine; Springer-Verlag,
1977, 1978, 1983; ISBN 3-540-90790-4
Kmoch, Hans; Pawn Power in Chess; David McKay Company, 1959; Dover
Publications, 1990; ISBN 0-486-26486-6
Levy, David; Computer Chess Compendium; Springer-Verlag, 1988;
Ishi Press International, 2009; ISBN 4-87187-804-X
Enthält Artikel von Vigneron, Shannon, Turing, Prinz, Bernstein,
Newell, Kotok, Greenblatt, Adelson-Velskiy, Atkin, ...
Levy, David; Newborn, Monty; How Computers play Chess; Freeman
& Company 1991; Ishi Press International 2009; ISBN
4-87187-801-5
Liffick, Blaise W.; The BYTE Book of Pascal; BYTE Publications,
1979; ISBN 0-07-037823-1
Enthält den Quelltext von CHESS 0.5 in Pascal
Nimzowitsch, Aaron; Mein System; A. Siedentop Verlag, 1931;
Jens-Erik Rudolph Verlag, 2010; ISBN 978-3-941670-19-8
Nunn, John; Einführung in die Schachtaktik; Gambit Publications,
2004; ISBN 1-904600-11-5
Pfleger, Helmut; Kurz, Eugen; Treppner, Gerd; Schach Zug um Zug;
Bassermann Verlag, 2004; ISBN 978-3-8094-1643-2
Philidor, François-André; Stamma, Philipp; Die Kunst im
Schachspiel ein Meister zu werden (Analyse du Jeu des Échecs);
1754;
Auf Google Books gibt es das Philidor
Buch.
Spracklen, Dan; Spracklen, Kathe; SARGON A Computer chess Program;
Hayden Books, 1978; ISBN 0-8104-5155-7
Enthält den Quelltext von SARGON in Z80 Assembler
Steinwender, Dieter; Friedel, Frederic A.; Schach am PC; Markt und
Technik, 1995; ISBN 3-87791-522-1
Enthält den Quelltext von MiniMAX in Basic und C
Tarrasch, Dr. Siegbert; Das Schachspiel; Deutsche
Buch-Gemeinschaft, Berlin 1931; Jens-Erik Rudolph Verlag, 2009;
ISBN 978-3-941670-00-6
Hier ist das Tarrasch
Buch online. Dieses Buch ist seit 1931 der Klassiker für den
Anfänger.
Reinefeld, Alexander; Spielbaum-Suchverfahren; Springer-Verlag,
1989; ISBN 3-540-50742-6
Andere Computer-Spiele



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



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



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



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



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



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