Schach dem C 64!

Eines der interessantesten Gebiete der Computertechnik ist sicherlich die Beschäftigung mit »künstlicher Intelligenz«. Um erste Erfahrungen auf diesem Gebiet zu sammeln, bietet sich ein Schachprogramm gut an. Hier ist eines zum Abtippen!

Man erkennt auch sofort, daß es an diesem Programm keine »künstliche Intelligenz« im eigentlichen Sinne gibt. Die »Intelligenz« beruht nur auf festen, mathematischen Formeln. Trotzdem ist es interessant, auf diesem Gebiet zu experimentieren. Das vorliegende Programm ist ein voll funktionsfähiges Schachprogramm, das über eine grafische Spielfeldanzeige verfügt und eine sehr kurze Rechenzeit von unter 10 Sekunden hat. Natürlich ist das Programm sehr spielstark. Der Sinn dieses Programms ist denn auch ein anderer. Dieses Programm soll dem Benutzer ein Grundstein für selbstgeschriebene Erweiterungen sein. Der interessierte Anwender ist aufgefordert, kreativ zu werden und eigene Ergänzungen zu installieren. So bietet sich zum Beispiel das Stellungsbewertungsprogramm besonders dazu an, erweitert und verfeinert zu werden. Auch die Grafik kann sicher verbessert werden.

So arbeitet das Programm

Der Programmablauf sieht wie folgt aus: Nachdem das Spielfeld initialisiert und ausgegeben ist, wird eine Eingabe eines weißen Zugs erwartet, zum Beispiel E2E4. Der Zug wird auf seine Richtigkeit überprüft und, falls er korrekt ist, ausgeführt. Dann wird eine Schleife gestartet, die sämtliche Spielfelder auf schwarze Figuren hin untersucht. Wird eine schwarze Figur gefunden, so wird der Zuggenerator angesprungen. Hier werden die der Figur möglichen Züge ausgeführt und mittels der Stellungsbewertung beurteilt. Nachdem alle Figuren überprüft wurden, wird der schwarze Zug mit seiner Wertigkeit ausgegeben. Nach einer kurzen Warteschleife wird die aktuelle Stellung ausgegeben, und es kann der nächste weiße Zug ausgeführt werden.

Die verwendete Maschinenunterroutine liegt im Speicherbereich von 49408 ($C100) bis 49864 ($C2D0). Das Unterprogramm überprüft, ob der schwarze König von irgendeiner weißen Figur angegriffen ist. Falls dies der Fall ist, so wird der Wert 128 an Basic übergeben, andernfalls der Wert 0. Es ist nun möglich, mit dem MC-Programm zu überprüfen, ob eine beliebige schwarze Figur angegriffen ist. Dazu wird in Speicherstelle 49409 die Position der aktuellen Figur (im Bewertungsprogramm ZF) geschrieben und in die Speicherstelle 49414 der Wert der Figur (zum Beispiel 130 = Springer). Nach Aufruf des Unterprogramms müssen unbedingt (!!) wieder die Standardwerte gePOKEt werden (49409:100 / 49414:134). Wird dies nicht beachtet, so kann der Computer keine regelwidrigen Stellungen mehr erkennen und antwortet mit unlogischen Zügen. Das Maschinenprogramm ist somit ideal dazu geeignet, um in einem selbst ergänzten Stellungsbewertungs-Programm eingesetzt zu werden. Man sollte jedoch beachten, daß ein umfangreiches Bewertungsprogramm die Rechenzeit pro Zug nicht unerheblich steigert.

Um dem Computer das Schachspiel beizubringen, sind im wesentlichen drei Probleme zu lösen:

1. Die interne Darstellung von Spielfeld und Figuren.
2. Der Zuggenerator: Er muß die Figuren den Regeln entsprechend bewegen und eine Liste möglicher Züge generieren.
3. Die Stellungsbewertung. Von ihrer Genauigkeit hängt die Spielstärke des Programms ab.

Nachfolgend nun eine Anleitung zur Lösung der drei Teilprobleme.

Da der Computer nicht auf das Schachbrett sehen kann, muß man es intern in einer Computerform darstellen, mit der der Computer arbeiten kann. Es bietet sich an, jedem Feld des Schachbretts eine Speicherstelle im Computer zuzuordnen. Den Inhalt der entsprechenden Speicherstellen stellen die Figuren dar, die sich auf dem Schachbrett befinden. Nun taucht aber ein zweites Problem auf: Wie kann der Computer auf einfache Weise überprüfen, wann sich eine Figur am Spielfeldrand befindet und nicht weiterziehen kann. Hier bietet es sich an, daß man um das eigentliche Spielfeld noch einen Rand installiert, der einen speziellen Zahlenwert enthält (Bild 1). In diesem Fall signalisiert der Zahlenwert 128 dem Rechner, daß dieses Feld nicht zum eigentlichen Spielfeld gehört und er es somit mit seinen Figuren nicht betreten darf. Damit hätten wir das Schachbrett in einer computergerechten Fbrm intern dargestellt. Als letztes Problem müssen noch die verschiedenen Spielfiguren auf dem internen Brett codiert werden. Dazu ordnet man jeder Figur eine Zahl zu. Die weißen Figuren bekommen die Werte 1 bis 6 und die schwarzen Figuren die Werte 1 bis 6 plus 128. Somit ist eine einfache Unterscheidung zwischen weißen und schwarzen Figuren möglich: Weiße Figuren haben einen Wert kleiner 128 und schwarze Figuren einen Wert größer 128. Leere Felder werden mit Null initialisiert. Sehen wir uns jetzt im Listing an, wie die Probleme innerhalb des Programms gelöst werden (Zeilen 1030 bis 1080). Das Spielfeld liegt im Rechner ab Speicherstelle 49152. In den Zeilen 1030 bis 1050 werden zunächst der Spielfeldrand (128) und die leeren Felder (0) initialisiert (vergleiche auch Bild 1). In Zeile 1060 werden dann die weißen (1) und schwarzen Bauern (1 + 128 = 129) auf die zweite beziehungsweise siebte Reihe des Spielfeldes positioniert. Die beiden Zeilen 1070 und 1080 dienen dazu, die restlichen Figuren auf den Grundreihen zu positionieren.

Der Zuggenerator

Doch mit dem Spielbeginn taucht ein neues Problem auf: Wie bringe ich den Computer dazu, daß er die Figuren entsprechend den Regeln bewegt? Als Beispiel wollen wir dies mit den Turmzügen durchsprechen (Zeilen 6440 bis 6560). Als Grundlage dient hier das Spielfeld in Bild 1. Der Turm darf den Regeln nach nur senkrecht und waagerecht ziehen, und zwar so lange, bis er auf den Spielfeldrand oder eine andere Figur trifft. Das Ziehen des Turmes bedeutet somit auf dem Computerspielfeld, daß zum Ausgangsfeld des Turmes die Vielfachen von 1 oder 10 addiert beziehungsweise substrahiert werden. Dieses Verfahren wird so lange wiederholt, bis der Turm auf ein Hindernis (Spielfeldrand oder andere Figur) trifft. Diese Zuggenerierung wird vom Programm wie folgt realisiert: Als Beispiel betrachten wir die Zuggenerierung senkrecht nach »oben«, also die Addition der Vielfachen von 10 zum Ausgangsfeld. Die anderen Zugrichtungen ergeben sich analog zu der betrachteten. In Zeile 6440 wird zunächst ein Flag auf Null gesetzt (FF=0). Dieses Flag wird immer dann auf 1 gesetzt, wenn der Turm bei seinem Zug auf ein Hindernis trifft. Als nächstes wird eine FOR-NEXT-Schleife gestartet, die es ermöglicht, alle Felder in »+10-Richtung« zu überprüfen. Die Variable X symbolisiert dabei das momentane Standfeld des Turmes, und Z durchläuft alle möglichen Zielfelder. Zum Schluß wird in Zeile 6440 geprüft, ob auf dem vorgesehenen Zielfeld bereits eine eigene Figur steht oder ob das Feld nicht mehr zum eigentlichen Spielfeld gehört. In beiden Fällen wird das Flag FF auf 1 gesetzt. In Zeile 6450 wird zunächst geprüft, ob das Flag FF gesetzt ist. Ist dies der Fall, so ist das Zielfeld Z regelwidrig, und das folgende wird übersprungen. Da FF jedoch in der gesamten Schleife nicht zurückgesetzt wird, wird sie bis zu ihrem Ende durchlaufen, ohne daß weitere Stellungen ausgewertet werden. Nehmen wir jetzt aber an, daß FF noch Null ist und die Stellung somit legal. Dann wird in Zeile 6450 das erwogene Zielfeld ZF gleich Z gesetzt und die Stellungsbewertung ab Zeile 100 aufgerufen. Anschließend wird noch geprüft, ob auf Feld Z eine weiße Figur steht. Diese Figur darf zwar geschlagen werden, verhindert aber den weiteren Vormarsch des Turmes in diese Richtung. Somit wird das Flag FF in diesem Falle auf 1 gesetzt. Ich nehme an, daß das Prinzip der Zuggenerierung jetzt deutlich geworden ist. Es läßt sich relativ einfach auf die anderen Figuren übertragen, wenn man ihre speziellen Gangarten berücksichtigt.

Die Stellungsbewertung

Somit bleibt als letztes Problem nur noch die Bewertung der entstehenden Stellungen (Zeilen 100 bis 520). Wozu überhaupt eine Stellungsbewertung? Jeder, der schon einmal Schach gespielt hat, weiß, daß es nicht genügt, nur die Regeln zu beherrschen. Man muß zwischen guten und schlechten Zügen unterscheiden können, wenn man das Spiel gewinnen will. Diese Aufgabe hat die Stellungsbewertung.

Versuchen wir, uns die Funktionsweise mit Hilfe des Listings zu verdeutlichen. Zeile 100 führt zunächst einmal den erwogenen Zug auf dem Spielfeld aus. Dazu muß der Inhalt des Zielfeldes in der Variablen WZ gesichert werden, da er sonst verloren gehen würde. Anschließend wird der Zug ausgeführt. Zeile 110 gehört noch nicht zum eigentlichen Stellungsbewertungs-Programm. Hier wird überprüft, ob in der entstandenen Stellung der schwarze König im Schach steht und die Stellung somit illegal ist. Dies wird dadurch angezeigt, daß das Maschinensprache-Programm der Variablen AA den Wert 128 übergibt. Ist dies der Fall, so wird die Stellungsbewertung übersprungen und nach Zeile 520 verzweigt, wo der ausgeführte Zug zurückgenommen und in den Zuggenerator gesprungen wird. In Zeile 200 wird der Wert der Stellung (AA) zunächst um den ursprünglichen Wert des Zielfeldes erhöht. Hat auf dem Zielfeld eine weiße Figur gestanden, so ist diese geschlagen, und der Zug ist somit höherwertig, als wenn Schwarz auf ein leeres Feld (WZ=0) gezogen hätte. In Zeile 210 wird geprüft, ob die Figur auf ihrem Ausgangsfeld angegriffen war. Dies ist der Fall, wenn der Wert der Felder X-9 oder X-11 gleich 1 ist, was bedeutet, daß die Figur auf ihrem Ausgangsfeld bedroht ist. Ein Wegziehen ist somit zu empfehlen, und der Wert AA wird um den Figurenwert erhöht. Das gleiche wird für das Zielfeld überprüft. Ist die Figur dort angegriffen, so wird ihr Wert von AA abgezogen, um zu zeigen, daß das Zielfeld ungünstig gewählt ist. Falls der berechnete Zug eine höhere Wertigkeit hat als der bisher beste Zug (BW), wird der soeben berechnete Zug als bester Zug eingeordnet, und die Ausgangs- und Zielkoordinaten (BA und BZ) werden ebenso wie die bisher beste Wertigkeit (BW) aktualisiert. Danach wird aus Zeile 500 nach 520 gesprungen, wo das Spielfeld zurückgesetzt und das Bewertungsprogramm verlassen wird. Falls der aktuelle Zug exakt die gleiche Wertigkeit hat wie der bisher beste Zug, so entscheidet der Zufallsgenerator darüber, ob der neue Zug als bester eingelistet werden soll. Diese Einrichtung sorgt dafür, daß der Computer in einer bestimmten Stellung nicht immer die gleichen Züge macht, sondern ein Spiel variiert. Das Stellungsbewertungs-Programm ist für eigene erste Experimente besonders geeignet. Man kann zum Beispiel noch eigene Kriterien zur Stellungsbewertung einführen. Jedoch sollte man bedenken, daß das Bewertungsprogramm besonders zeitkritisch ist, da es pro Zugberechnung etwa 30- bis 50mal durchlaufen wird. Jede weitere Zeile macht sich also in der Rechenzeit des Computers bemerkbar.

Literaturhinweis: Computerschach von Ludek und Vas I. Kühnmund, Heyne-Buch Nr. 4704, Wilhelm Heyne Verlag, München, Taschenbuch, Preis: zirka 5,80 Mark.
Dieses Buch bietet eine ausführliche und leicht verständliche Einführung in das Thema Computerschach. Außerdem beinhaltet es einige interessante Partien zwischen Mensch und Computer.

1 rem ******  schachlader c-64  ******
2 rem ** (c) by bernd bettermann    **
3 rem **        amelither str.21    **
4 rem **        3417 bodenfelde     **
5 rem ********************************
10 :
20 fori=49408to49864:readq:pokei,q:next
30 :
40 printchr$(147):print:print"load";chr$(34);"schach";chr$(34);",8"
50 print:print:print:print:print"run";chr$(19);
60 poke198,2:poke631,13:poke632,13:end
100 :
101 data 162,100,189,0,192,201,134,240,4,202,208,246,96,134,20,169
102 data 192,133,21,160,0,138,56,233,9,133,20,177,20,201,1,208
103 data 1,96,138,56,233,11,133,20,177,20,201,1,208,1,96,138
104 data 56,233,21,133,20,177,20,201,2,208,1,96,138,56,233,19
105 data 133,20,177,20,201,2,208,1,96,138,56,233,12,133,20,177
106 data 20,201,2,208,1,96,138,56,233,8,133,20,177,20,201,2
107 data 208,1,96,138,24,105,8,133,20,177,20,201,2,208,1,96
108 data 138,24,105,12,133,20,177,20,201,2,208,1,96,138,24,105
109 data 19,133,20,177,20,201,2,208,1,96,138,24,105,21,133,20
110 data 177,20,201,2,208,1,96,138,56,233,11,133,20,177,20,201
111 data 6,208,1,96,138,56,233,10,133,20,177,20,201,6,208,1
112 data 96,138,56,233,9,133,20,177,20,201,6,208,1,96,138,56
113 data 233,1,133,20,177,20,201,6,208,1,96,138,24,105,1,133
114 data 20,177,20,201,6,208,1,96,138,24,105,9,133,20,177,20
115 data 201,6,208,1,96,138,24,105,10,133,20,177,20,201,6,208
116 data 1,96,138,24,105,11,133,20,177,20,201,6,208,1,96,134
117 data 2,134,20,165,20,24,105,10,133,20,177,20,201,4,208,1
118 data 96,201,5,240,251,201,0,240,234,134,20,165,20,56,233,10
119 data 133,20,177,20,201,4,208,1,96,201,5,240,251,201,0,240
120 data 234,134,20,134,20,165,20,24,105,1,133,20,177,20,201,4
121 data 208,1,96,201,5,240,251,201,0,240,234,134,20,165,20,56
122 data 233,1,133,20,177,20,201,4,208,1,96,201,5,240,251,201
123 data 0,240,234,134,20,165,20,24,105,11,133,20,177,20,201,3
124 data 208,1,96,201,5,240,251,201,0,240,234,134,20,165,20,24
125 data 105,9,133,20,177,20,201,3,208,1,96,201,5,240,251,201
126 data 0,240,234,134,20,165,20,56,233,9,133,20,177,20,201,3
127 data 208,1,96,201,5,240,251,201,0,240,234,134,20,165,20,56
128 data 233,11,133,20,177,20,201,3,208,1,96,201,5,240,251,201
129 data 0,240,234,160,0,32,162,179,96

1 rem ****** schach fur den c-64 ******
2 rem ** (c) by bernd bettermann     **
3 rem **        amelither str.21     **
4 rem **        3417 bodenfelde      **
5 rem **  tel:05572/330 ab 18'00     **
6 rem *********************************
7 :
10 ifpeek(49408)<>162thensys5517
20 goto1000
70 :
80 rem ------ stellungsbewertung ------
90 :
100 wz=peek(zf):pokezf,peek(x):pokex,0
110 aa=usr(128):ifaa=128then520
120 :
200 aa=aa+wz
210 ifpeek(x-9)=1orpeek(x-11)=1thenaa=aa+peek(zf)-128
220 ifpeek(zf-9)=1orpeek(zf-11)=1thenaa=aa-peek(zf)-128
400 :
500 ifaa>bwthenbw=aa:ba=x:bz=zf:goto520
510 ifaa=bwandrnd(1)>.7thenba=x:bz=zf
520 pokex,peek(zf):pokezf,wz:return
1000 :
1010 rem ----- variablendefinition ----
1020 :
1030 forx=49152to49171:pokex,128:pokex+100,128:nextx
1040 forx=49172to49251:pokex,0:nextx
1050 forx=49172to49242step10:pokex,128:pokex+9,128:nextx
1060 forx=49183to49190:pokex,1:pokex+50,129:nextx
1070 restore:forx=49173to49180:reada:pokex,a:pokex+70,a+128:nextx
1080 data 4,2,3,5,6,3,2,4
1090 poke785,0:poke786,193
2000 :
2010 rem ----- spielfeld ausgeben -----
2020 :
2030 poke53280,0:poke53281,0:print"{clr}{grn}{down}{down}  {CBM-@}{CBM-@}{CBM-@}{CBM-@}{CBM-@}{CBM-@}{CBM-@}{CBM-@}"
2040 fory=8to1step-1:printchr$(48+y);"{CBM-M}";:forx=1to8
2050 w=peek(49162+y*10+x)
2060 ifw=0thenprint"{SHIFT-@}";:goto2090
2070 ifw>128thenprint"{rvon}";mid$("bsltdk",w-128,1);"{rvof}";
2080 ifw<128thenprintmid$("bsltdk",w,1);
2090 nextx:print
2100 nexty:print"  {CBM-T}{CBM-T}{CBM-T}{CBM-T}{CBM-T}{CBM-T}{CBM-T}{CBM-T}":print"  abcdefgh{down}{down}":bw=-50
3000 :
3010 rem ------ zugeingabe weiss ------
3020 :
3030 input"ihr zug ";z$
3040 iflen(z$)<>4thenprint"{up}":goto3030
3050 ifmid$(z$,1,1)<"a"ormid$(z$,1,1)>"h"then3030
3060 ifmid$(z$,3,1)<"a"ormid$(z$,3,1)>"h"then3030
3070 ifmid$(z$,2,1)<"1"ormid$(z$,2,1)>"8"then3030
3080 ifmid$(z$,4,1)<"1"ormid$(z$,4,1)>"8"then3030
3090 af=asc(left$(z$,1))-64+10*val(mid$(z$,2,1))+49162
3100 zf=asc(mid$(z$,3,1))-64+10*val(right$(z$,1))+49162
3110 ifpeek(af)=0orpeek(af)>6then3030
3120 ifpeek(zf)>0andpeek(zf)<129then3030
3130 pokezf,peek(af):pokeaf,0
4000 :
4010 rem --- schw. figurenpos. holen --
4020 :
4030 forx=49173to49250:ifpeek(x)>128thengosub6000
4040 nextx
5000 :
5010 rem ---- schw. zug ausfuehren ----
5020 :
5030 pokebz,peek(ba):pokeba,0:print"{down}wert:";bw
5040 print"{down}zug: ";
5050 bb=ba-49172
5055 ifbb>10thenbb=bb-10:goto5055
5057 printchr$(bb+64);
5060 printchr$(int((ba-49172)/10)+49);"-";
5070 bb=bz-49172
5075 ifbb>10thenbb=bb-10:goto5075
5077 printchr$(bb+64);
5080 printchr$(int((bz-49172)/10)+49)
5085 ifbw=-50thenprint"{down}ich gebe auf":end
5090 forx=1to1000:nextx:goto2000
5100 :
5110 end
5120 :
6000 ifpeek(x)<>129then6100
6010 :
6020 rem -------- bauernzuege ---------
6030 :
6040 ifx>49233andpeek(x-10)=0andpeek(x-20)=0thenzf=x-20:gosub100
6050 ifpeek(x-10)=0thenzf=x-10:gosub100
6060 ifpeek(x-9)>0andpeek(x-9)<7thenzf=x-9:gosub100
6070 ifpeek(x-11)>0andpeek(x-11)<7thenzf=x-11:gosub100
6080 return
6100 ifpeek(x)<>130then6200
6110 :
6120 rem ------- springerzuege --------
6130 :
6140 z$="08121921":forz=1to7step2
6150 zz=val(mid$(z$,z,2))
6160 ifpeek(x+zz)<128thenzf=x+zz:gosub100
6170 ifpeek(x-zz)<128thenzf=x-zz:gosub100
6180 nextz:return
6200 ifpeek(x)<>131then6400
6210 :
6220 rem -------- laeuferzuege --------
6230 :
6240 ff=0:forz=x+11tox+77step11:ifpeek(z)>6thenff=1
6250 ifff=0thenzf=z:gosub100:ifpeek(z)<>0thenff=1
6260 nextz
6270 ff=0:forz=x-11tox-77step-11:ifpeek(z)>6thenff=1
6280 ifff=0thenzf=z:gosub100:ifpeek(z)<>0thenff=1
6290 nextz
6300 ff=0:forz=x+9tox+63step+9:ifpeek(z)>6thenff=1
6310 ifff=0thenzf=z:gosub100:ifpeek(z)<>0thenff=1
6320 nextz
6330 ff=0:forz=x-9tox-63step-9:ifpeek(z)>6thenff=1
6340 ifff=0thenzf=z:gosub100:ifpeek(z)<>0thenff=1
6350 nextz
6360 return
6400 ifpeek(x)<>132then6600
6410 :
6420 rem --------- turmzuege ----------
6430 :
6440 ff=0:forz=x+10tox+70step10:ifpeek(z)>6thenff=1
6450 ifff=0thenzf=z:gosub100:ifpeek(z)<>0thenff=1
6460 nextz
6470 ff=0:forz=x-10tox-70step-10:ifpeek(z)>6thenff=1
6480 ifff=0thenzf=z:gosub100:ifpeek(z)<>0thenff=1
6490 nextz
6500 ff=0:forz=x+1tox+7step1:ifpeek(z)>6thenff=1
6510 ifff=0thenzf=z:gosub100:ifpeek(z)<>0thenff=1
6520 nextz
6530 ff=0:forz=x-1tox-7step-1:ifpeek(z)>6thenff=1
6540 ifff=0thenzf=z:gosub100:ifpeek(z)<>0thenff=1
6550 nextz
6560 return
6600 ifpeek(x)<>5then6700
6610 :
6620 rem ---------- damenzuege --------
6630 :
6640 gosub6210:gosub6410:return
6700 :
6710 rem -------- koenigszuege --------
6720 :
6730 z$="01091011":forz=1to7step2
6740 zz=val(mid$(z$,z,2))
6750 ifpeek(x+zz)<7thenzf=x+zz:gosub100
6760 ifpeek(x-zz)<7thenzf=x-zz:gosub100
6770 nextz:return
6780 :
6790 rem ----------- ende -------------
6800 :