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

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

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

Frey, Atkin, Chess 0.5, 1978

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 cm³).

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



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

Bedienungsanleitung SHAH Schachcomputer

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

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

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

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

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

Wird ein K�nig Matt gesetzt erscheint MATT.

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

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

Tipp: Wenn die Stellung schlecht f�r den Menschen steht, 'Go' dr�cken und den Computer ab sofort die schw�chere Seite spielen lassen. Der Philosoph Hubert Dreyfus hat 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

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

Zug Sortierung

Schach Erkennung

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

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

Claude Shannon

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

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

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

Alan Turing Papiermaschine

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

For a Q, R, B, or N, count

1. The square root of the number of moves the piece can make from the position, counting a capture as two moves, and not forgetting that the king must not be left in check.
2. (If not a Q) 1.0 if it is defended, and an additional 0.5 if twice defended.

For a K, count

3. For moves other than castling as (1) above.
4. 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.
5. 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

6. 0.2 for each rank advanced.
7. 0.3 for being defended by at least one piece (not P).

For the black K, count

8. 1.0 for the threat of checkmate.
9. 0.5 for check.

Turing selbst hat eine Partie seiner Papiermaschine gegen Alick Glennie notiert. F�r das Schachprogramm Fritz gibt es eine Turing Engine. Eine Partie zwischen den Schachprogrammen Turing und Fritz 6 zeigt die Schw�chen der Turing Positionsbewertung und auch einen Fehler in der Engine Implementierung - der Springer hat auf f3 eine bessere Mobilit�t als auf h3. Der Bauer auf a4 und die Dame auf f3 erlauben eine hohe Mobilit�t, d�rften aber selbst einem Schach Neuling als wenig sinnvolle Er�ffnungsz�ge erscheinen.

        

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

Peter Jennings Microchess

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

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

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

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

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

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

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

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

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

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

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

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


        

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

Wieviel Bewertung ist n�tig?

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

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

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

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

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

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

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

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

Er�ffnungsbibliothek

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

Das einfachste Schachprogramm

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

Dan & Kathe Spracklen SARGON

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

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

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

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

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

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

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

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

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

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

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



Bild: Calltree von Sargon

Weitere Schachprogramme im Quelltext

Auf  WBEC Ridderkerk gibt es eine Rankinglist von Schachprogrammen. �ber die Download Seite findet man die im Quelltext verf�gbaren Schachprogramme in C/C++:

Rank Program:                Rating  +   - games score    Av.Opp draws Lang.GUI    Lizenz 
  3 Fruit X060620a            2852   63   61    92   64%  2754   28% C++  UCI    GPL

  8 Glaurung 1.2-X64          2779   57   57    92   53%  2757   46% C++  UCI    GPL
 12 Scorpio 1.8               2747   59   59    92   48%  2758   36% C++  xboard own
 24 Crafty 20.13BH-x64        2664   60   59    88   62%  2589   40% C    xboard freeware
 76 Phalanx XXII              2455   18   18  1084   48%  2467   25% C    xboard GPL
101 Resp 0.19                 2349   19   19  1020   48%  2360   25% C++
138 GNUChess 4TM              2215   29   29   444   52%  2198   21%      xboard
176 GNU Chess 5.00+           2022   76   77    60   48%  2035   20%      xboard
247 TSCP 1.81                 1655   41   41   272   47%  1675   15% C    xboard

Bayesian Elo Ratinglist WBEC Ridderkerk after edition 15:

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

Einfache Schachprogramme mit graphischer Oberfl�che

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

Weitere Internet Links

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

Literatur

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Andere Computer-Spiele

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



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



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



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



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



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