Logo "blaue" Seiten

 
 
 
 
- Anzeige -
Für den Erwerb von Schachartikeln empfiehlt Ihnen der SC Leinzell den
 Schachversand Dreier 
 
 
Testen Sie Ihr Schach!
 
Diagramm 23-2006
 
Diagramm 23 – 2006
Schwarz hat zwei Bauern geopfert und steht nun vor der Frage, ob er sich auf e5 wieder einen zurück holen soll. Was meinen Sie?
 zur Lösung 
 
 
 
zur Startseite
 News | Sitekalender | Sitemap | Team | Kontakt 
Rochade-EuropaStefan Meyer-Kahlen
 
 
Schachprogrammierung
von Stefan Meyer-Kahlen - Juni 2001
 
 
Viele Leser haben mich gefragt, wie man eigentlich vorgehen soll, wenn man ein eigenes Schachprogramm entwickeln möchte. Ich möchte daher kurz auf einzelne grundlegende Gesichtspunkte der Schachprogrammierung eingehen, ohne dabei jedoch zu technisch zu werden oder zu weit ins Detail zu gehen. Bevor ich damit anfange, noch eine ernstzunehmende Warnung: Schachprogrammierung macht süchtig!
 
Nach jedem einzelnen erfolgreich durchgeführten Schritt wächst schnell die Begeisterung. Wenn das eigene Programm zum ersten Mal legale Züge ausführt und die erste vollständige Partie ohne Abstürze gespielt wird, ist das ein kaum zu beschreibendes Erfolgserlebnis. Wenn dabei noch sinnvolle Züge herauskommen, gibt es dann definitiv kein zurück mehr. In diesem Fall sieht man es sogar gelassen, wenn man gegen das eigene Programm verliert ...
 
 
Programmiersprache
Wie und womit aber soll man anfangen? Zuerst muss man sich überlegen, in welcher Computersprache man das Programm schreiben will. Mein Programm Shredder ist in C geschrieben, obwohl ich das, ebenso wenig wie die Programmierung in Assembler oder Maschinensprache, eigentlich keinem Einsteiger empfehlen kann. Heutzutage gibt es da weit bessere Möglichkeiten, wie z.B. Delphi, Visual Basic, C++ oder auch Java. Im Prinzip ist jede dieser Sprachen gleich gut geeignet und kann uneingeschränkt empfohlen werden.
 
Man muss allerdings noch beachten, dass manche der kommerziellen Entwicklungswerkzeuge für diese Sprachen recht teuer sind, denn bis zu 1000 DM für ein erstes kleines Schachprojekt sind sicher nicht nach jedermanns Geschmack. Aber keine Panik, es gibt auch deutlich preiswertere und zum Teil auch sehr gute kostenlose Alternativen. Fast alle Hersteller bieten deutlich billigere Einsteigerversionen ihrer Programmpakete mit der Einschränkung an, dass man mit ihnen erstellte Programme nicht verkaufen darf, doch bis dahin ist es anfangs ein sehr weiter Weg.
 
Oft tut es auch eine ältere Version, die es zu vielen Lehrbüchern über Programmiersprachen kostenlos als Beigabe dazu gibt. Wenn ich mich für eine Sprache entscheiden müsste, dann würde ich wohl Java vorschlagen. Programme in Java laufen zwar meistens langsamer ab, jedoch spielt dies für unsere ersten Versuche noch keine entscheidende Rolle und meiner Meinung nach wiegen die Vorteile von Java dessen Nachteile bei weitem auf.
 
 
Der Start
Nun aber frisch ans Werk. Als erster Schritt steht die Frage an, wie man das Schachbrett und die Figuren intern im Programm und damit im Computer abspeichert. Allen Figurenarten wird dabei eine Zahl zugeordnet, der weiße Bauer ist z.B. die 1, der weiße Springer die 2, der weiße Läufer ist 3, der weiße Turm ist 4, Dame und König von Weiß sind dann 5 und 6. Danach kommen dann die schwarzen Figuren beginnend mit dem schwarzen Bauern mit 7.
 
Dabei haben wir nun schon unbemerkt die erste Optimierung vorgenommen: Mit dieser Nummerierung kann man nun leicht feststellen, ob eine Figur weiß oder schwarz ist, nicht ganz unwichtig, denn man darf ja z.B. nur die gegnerischen Figuren schlagen und mit den eigenen ziehen. Die weißen Figuren sind alle kleiner gleich 6 und die schwarzen sind größer als 6, ein sehr einfacher Test.
 
Weiter geht es mit der Darstellung des Schachbrettes: Das Schachbrett hat 64 Felder und auf jedem Feld kann eine Figur stehen. Es liegt also nahe, für jedes Feld eine eigene Speicherzelle zu reservieren, welche wir dann ebenfalls von 1 bis 64 durchnummerieren. Feld 1 ist dabei A1, 2 ist B1, 3 ist C1 und 64 ist dann H8. Wenn wir nun darstellen wollen, dass ein weißer Läufer auf b1 steht, dann müssen wir nur eine 3 = weißer Läufer in die Speicherzelle Nummer 2 = B1 schreiben.
 
Eine Kleinigkeit fehlt noch: Wie zeigen wir, dass ein Feld leer ist? Dafür bestimmen wir einfach auch eine Zahl, die dann "keine Figur" bedeutet, hier bietet sich natürlich die 0 an. Ist das Feld a2 z.B. leer, dann steht in der Speicherzelle mit der Nummer 9 eine 0. So kann man jedes beliebige Schachbrett darstellen, doch was passiert, wenn eine Figur einen Zug machen soll?
 
 
Die Regeln
Wie kann man heraus finden, welche Züge für eine Figur legal sind oder einfacher gesagt, wie zieht eine Figur überhaupt? Jeder Schachspieler weiß, dass ein Läufer nur diagonal, ein Bauer nur vorwärts und ein König in jede Richtung, aber nur ein Feld weit, ziehen darf. Das müssen wir dem Programm beibringen. Nehmen wir dazu als Beispiel einen Turm. Der Turm kann nach links, rechts oben und unten ziehen, und zwar immer so weit, bis er auf eine andere Figur oder auf den Brettrand trifft. Wenn man sich auf unserm internen Schachbrett ansieht, was es bedeutet, ein Feld nach rechts zu ziehen, dann sehen wir, dass sich die Feldnummer immer um genau 1 vergrößert. Von Feld B1 mit Nummer 2 zu Feld C1 mit der Nummer 3 nach rechts ist der Schritt also genau 1. Nach links werden die Feldnummer analog immer um genau 1 kleiner.
 
Ebenso können wir feststellen, dass sich die Feldnummern nach oben und unten immer genau um 8 bzw. -8 verändern. Wenn wir vom Feld A1 mit Nummer 1 nach oben zu A2 gehen, stellen wir fest, dass das Feld A2 genau die Nummer 9 hat. Damit haben wir eine sehr wichtige Beobachtung gemacht, die es uns ermöglicht, alle legalen Züge für einen Turm zu berechnen. Dazu gehen wir vom Turmfeld aus nacheinander in alle 4 möglichen Zugrichtungen, also 1, -1, 8 und -8, des Turmes los, indem wir zu der Feldnummer immer die entsprechende Schrittrichtung addieren bzw. subtrahieren. Dies machen wir für jede Richtung so lange, bis wir auf eine andere Figur oder auf den Brettrand stoßen.
 
Treffen wir dabei auf eine gegnerische Figur, dann bedeutet dies, dass der Turm diese Figur schlagen kann. Wenn wir uns dabei alle Felder merken, die wir auf diese Art und Weise erreichen können, dann haben wir schon unsere Aufgabe gelöst und alle legalen Züge für den Turm bestimmt. Na ja, ganz so einfach ist die Sache nun auch wieder nicht, denn wir müssen für jeden Zug immer noch nachschauen, ob wir unseren eigenen König dadurch ins Schach stellen, diese Züge müssen dann natürlich aussortiert werden, denn sie wären illegal. Wenn wir schon im Schach stehen, müssen wir auch prüfen, ob einer dieser Turmzüge das Schach verhindert. Prinzipiell werden aber so auch für alle anderen Figuren die möglichen Züge bestimmt, man muss immer nur die Werte für die entsprechende Richtung bestimmen und bei Springer und König noch beachten, dass sie jeweils nur ein Feld weit in jede Richtung ziehen können.
 
Die Bauern machen da noch die meisten Probleme, denn sie ziehen und schlagen in verschiedene Richtungen, können unter besonderen Umständen auch zwei Felder auf einmal ziehen oder en passent schlagen und verwandeln sich in eine andere Figur, wenn sie die gegnerische Grundreihe erreicht haben, doch mit etwas Sorgfalt lassen sich auch all diese Besonderheiten, ebenso wie die Rochade als besonderer Königszug, meistern.
 
Das eigentlich Ausführen der Züge ist dann wieder eine Kleinigkeit. Wenn ein weißer Turm von a1 nach a2 ziehen soll, dann schreiben wir einfach in das Feld mit der Nummer 1 (A1) eine 0, denn diese Feld ist ja nach dem Zug leer. In das Feld mit der Nummer 9 (A2) kommt dann eine 4 für einen weißen Turm, der ja dort landet. Das war's auch schon. Auf diese Weise können wir alle legalen Züge in einer Stellung bestimmen und diese Züge dann auch auf unserem internen Schachbrett ausführen, mehr brauchen wir auch nicht, damit unser Programm nun alle möglichen Züge bis zu einer bestimmten Tiefe ausprobieren kann, so wie es heute alle üblichen Schachprogramme tun.
 
 
Bewertung
Um herauszufinden, welche Seite denn nun besser steht, müssen wir unserem Programm zunächst einmal sagen, dass eine Dame besser als ein Turm ist und ein Springer besser als ein Bauer. Springer und Läufer sind ungefähr gleich gut. Alle Figuren bekommen deshalb einen Wert zugewiesen, der bestimmt, wie gut oder wertvoll eine Figur ist. Folgende Werte haben sich dabei, wie jeder Schachspieler bestätigen kann, als vernünftig erwiesen. Die Dame ist 900, der Turm 500, Läufer und Springer 300 und ein Bauer ist 100 Punkte wert.
 
Um eine Stellung nun grob zu bewerten, lassen wir unser Programm die Summe der Werte aller weißen und die Summe aller schwarzen Figuren berechnen. Davon bilden wir dann die Differenz, also Summe Weiß Minus Summe Schwarz, und bekommen einen Wert der uns sagt, ob Weiß oder Schwarz besser steht. Ist der Wert größer 0, dann ist Weiß im Vorteil, ist der Wert kleiner 0 dann steht Schwarz besser. Bei 0 ist die Stellung ausgeglichen. Ein Wert von 100 besagt z.B., dass Weiß einen Bauern mehr hat. Dies gibt natürlich nur einen ersten groben Wert für die Bewertung einer Stellung, den man noch beliebig erweitern und verfeinern kann.
 
Denkbar ist z.B., dass man Doppelbauern mit -10 bestraft und einen Turm auf einer offenen Linie mit +6 belohnt. Alle diese Werte werden dann aufaddiert und bilden dann zusammen die Stellungsbewertung, wie wir sie aus allen Schachprogrammen kennen. Um den besten Zug in einer Stellung zu finden, probiert das Programm nun einfach alle Züge bis zu einer bestimmten Tiefe aus und berechnet für alle Züge einen Wert nach dem obigen Muster. Der Zug mit dem höchsten Wert ist dann nach dieser Logik der beste und wird vom Programm gewählt.
 
 
Fazit
Wenn wir bis hier gekommen sind, dann haben wir ein Schachprogramm, welches schon keine völlig sinnlosen Züge mehr macht und auch keine Figuren mehr einstellt. Umgekehrt wird es auch keine Figureneinsteller mehr übersehen und alle Figuren einsammeln, die man ihm bewusst oder unbewusst zum Fraß vorwirft. Der Weg, ein Programm zu schreiben, gegen das man selber auch mal verlieren kann, ist also unter Umständen gar nicht so weit ...
 
Stefan Meyer-Kahlen – www.shredderchess.de
 
zum Seitenanfang zurück |