Inhaltsverzeichnis

1  Einleitung  1

1.1  Motivation  1

1.2  Aufbau  2

2  Schach  3

2.1  Geschichte  3

2.2  Grundlegendes  4

2.3  Spielende  5

2.3.1  Matt  5

2.3.2  Remis  5

2.4  Spieltheorie  6

3  Software Engineering  7

3.1  Denition  7

3.2  Vom Programm zur Software  9

3.3  Phasen der Softwareentwicklung  12

3.4  Programmfehler  13

4  Schachsoftware  15

4.1  Spezikation  15

4.2  Systementwurf zu Teil 1  15

4.2.1  Die Datenstrukturen  15

4.2.1.1  Interne Brettdarstellung  15

4.2.1.2  Klassen, Records, globale Variablen  16

4.2.2  Frontend  17

4.2.3  Zugregeln  17

4.2.3.1  Grundzüge  17

4.2.3.1.1  Turm  17

4.2.3.1.2  Läufer  18

4.2.3.1.3  Dame  18

4.2.3.1.4  König  18

4.2.3.1.5  Springer  18

4.2.3.1.6  Bauer  19

4.2.3.2  Kollisionsprüfung  19

4.2.3.3  Gültiger Zug ohne Schachberücksichtigung  20

4.2.3.4  En passant gültig  20

4.2.3.5  Rochade gültig  20

4.2.4  Wichtige Funktionen  21

4.2.4.1  Schach  22

4.2.4.2  Figur verschieben  22

4.2.4.3  En passant ausführen  22

I

4.2.5 Benutzersteuerung . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.2.5.1 Zugeingabe . . . . . . . . . . . . . . . . . . . . . . . . . . 24

4.3 Anmerkungen zur Implementierung von Teil 1 . . . . . . . . . . . . . . . . 26 4.4 Systementwurf zu Teil 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.4.1 Bewertungsfunktionen . . . . . . . . . . . . . . . . . . . . . . . . . 27

4.4.2 Spielbaumsuche mit dem Minimax-Algorithmus . . . . . . . . . . . 28 4.5 Anmerkungen zur Implementierung von Teil 2 . . . . . . . . . . . . . . . . 30 4.6 Die ersten Testpartien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.7 Optimierung der Rechenzeit . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.8 Weitere Tests von Dritten . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5 Nachwort 32

5.1 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 5.2 Ausblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.3 Danksagung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.4 Benutzte Programme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5.5 Literaturverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5.6 Online-Verfügbarkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.7 Erklärung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 A Quelltext i

⁰ Titelbild: Die Mattstellung der 1851 auÿerhalb eines Turniers gespielten unsterblichen Partie zwischen den Schachmeistern Adolf Anderssen und Lionel Kieseritzky. [1]

II

Kapitel 1

Einleitung

1.1 Motivation

Im Alter von etwa 10 Jahren kaufte ich mir meinen ersten Schachcomputer Krypton Schachpartner 2 ; schon damals war ich von der Spielstärke fasziniert und versuchte zu ergründen, nach welchen Kriterien der Computer seinen nächsten Zug ermittelt. Mir fehlten meistens echte Gegner gleicher Spielstärke, sodass ich mir die Grundzüge des Schachspiels fast ausschlieÿlich mit diesem Schachcomputer aneignete.

Mit den Informatikkenntnissen der MSS 11 begann ich erstmals ernsthaft über die Entwicklung und Implementierung eines Schachprogramms nachzudenken. Mit besseren Programmierkenntnissen schrieb ich in der MSS 12 ein ca. 1000 Zeilen langes Grundgerüst eines Schachprogramms, das die Regeln bis auf wenige Sonderzüge wie das Schlagen en passant beherrschte und die Figurenkonstellation mit einer 2D-Frontend ausgab, sodass zwei menschliche Spieler mit diesem Programm gegeneinander spielen konnten. Gleichzeitig schrieb Johannes Bayer an einer 3D-Engine, die zum Ziel hatte, in Arrays gespeicherte Polygone im Raum mithilfe von Matrizen und Vektoren auf die Monitorebene zu projizieren und so unsere Wahrnehmung von Objekten im Raum zu simulieren. Das Ziel dieses arbeitsteiligen Projekts war ein im Raum dargestelltes Schachbrett, auf dem der Benutzer gegen den Computer spielen kann.

Früh mussten wir trotz vieler Fortschritte und Erfolge erkennen, dass dieses Projekt auf-grund mangelnder Planung zu viel Zeit verschlingen würde und selbst dann nicht zufriedenstellende Ergebnisse liefern würde, deshalb brachen wir das Projekt im Entwicklungsstadium vorerst ab. Dennoch hat uns dieser Fehlschlag viel gebracht. Ich machte mir über ein halbes Jahr lang immer wieder Gedanken über die Datenstrukturen und zugrundeliegenden Algorithmen und gewann so immer mehr eine konsistente Vorstellung davon, wie mein Programm die komplexe Aufgabe des Schachspielens bewältigen sollte. Da ich die MSS 12 krankheitsbedingt wiederholen musste, entschloss ich mich zu Beginn des Schuljahrs schlieÿlich dazu, die Umsetzung dieses Programms im Rahmen einer Besonderen Lernleistung, im Folgenden als BLL abgekürzt, zu behandeln. Mein Informatiklehrer Herr Schowalter verwies schon im ersten Gespräch auf das Gebiet Software Engineering, das einen Ansatz liefert, sehr komplexe Programme zu realisieren, sodass das genaue Thema meiner BLL recht schnell festgelegt war.

1

1.2 Aufbau

Im folgenden Kapitel möchte ich kurz auf die Entstehung, Grundlegendes und auf das Spielziel von Schach eingehen sowie eine Einordnung des Schachspiels unter dem Aspekt der Spieltheorie vornehmen.

Im dritten Kapitel werde ich dem Leser die Grundzüge und das Ziel des Software Engineering aufzeigen sowie die Bedeutung einiger Fachbegrie vermitteln. Auÿerdem soll eine Dierenzierung der Begrie Programm und Software vorgenommen werden. Es folgt eine Darstellung der Softwareentwicklungsphasen und ein Abschnitt über Ursachen und die Auswirkungen von verschiedenen Programmfehlern.

Das vierte Kapitel ist der eigentliche Kern dieser BLL, denn hier werde ich versuchen, die in Kapitel 3 erläuterte allgemeine Vorgehensweise auf das spezielle Problem der Entwicklung einer Schachsoftware zu übertragen. In diesem Kapitel sollen der Aufbau und die Funktionsweise des Programms möglichst detailliert dokumentiert werden, angefangen von der internen Brettdarstellung und anderen Datenstrukturen über die Implementierung der Spielregeln bis hin zur Realisierung einer schwachen künstlichen Intelligenz (KI ).

Im fünften Kapitel werde ich kurz die Resultate dieser BLL zusammenfassen sowie einen Ausblick auf Erweiterungsmöglichkeiten geben, es folgt eine Danksagung, eine Liste der benutzten Programme sowie eine Quellenangabe für diesen schriftlichen Teil der BLL.

Im Anhang bendet sich der vollständige Quelltext der letzten Programmversion vor Abgabe der BLL. Für den geneigten Leser sind die Sourcen und das Programm auch online verfügbar (URL siehe 5.6). Voraussichtlich wird das Programm auch nach dem Abgabetermin noch weiterentwickelt.

⁰ Die vorliegende BLL setzt beim Leser Fachkenntnisse in Informatik der MSS 11 und 12 voraus.

2

Kapitel 2

Schach

Schach ist nicht nur ein Sport, sondern auch eine Kunst und eine Wissenschaft.

Garri Kasparow [2]

2.1 Geschichte

Man geht heute davon aus, dass die Urform des Schachspiels, Caturanga, im Indien des sechsten Jahrhunderts nach Christus entstand, von dort aus gelangte es nach Persien. [3] Hier kam das Schachspiel zu seinem heutigen Namen: Schah ist das persische Wort für König, Schah Mat bedeutet soviel wie: Der König ist hilos. [4] Im frühen Mittelalter gelangte das königliche Spiel dank der Araber über Griechenland schlieÿlich auch nach Mitteleuropa. [3] Schon damals wurde mit den heute noch üblichen arabischen Spielsteinen gespielt. Die Schachregeln zu dieser ersten Blütezeit unterschieden sich jedoch noch sehr von den heutigen oziellen Schachregeln des Weltschachverbandes ed´ eration Internationale des ´ FIDE (F ´ Echecs).

Doch schon zu dieser Zeit war ein wesentliches Merkmal gegeben, das wohl einen beträchtlichen Reiz des Schachspiels ausmacht: Die wichtigste Figur auf dem Brett, der König, ist nicht die mächtigste, sondern vielmehr die schutzbedürftigste. [5] Deshalb muss jeder erfolgreiche Schachspieler ein gutes Mittel zwischen Angri und Verteidigung nden, dies kann jedoch nur durch ein eektives Zusammenwirken der Figuren erfolgen. Gegen Ende des 15. Jahrhunderts wurden die Zugregeln grundsätzlich geändert, der Aktionsradius vieler Figuren wie z.B. von Dame und Läufer wurde vergröÿert, was die Dame zur stärksten Figur auf dem Feld machte. [3] Diese Vergröÿerung des Aktionsradius und insbesondere die neue Möglichkeit der Bauern, aus der Grundstellung zwei Felder nach vorne zu ziehen, hatte einen beschleunigten Spielablauf zur Folge. Der König hingegen wurde schwach und schutzbedürftig.

Seit dieser Zeit wurden nur noch kleine Anpassungen der Spielregeln vorgenommen. Schach ist bis heute das älteste und bekannteste Brettspiel der Welt und genieÿt in unserer heutigen Gesellschaft sogar den Ruf eines Statussymbols. Einer 2007 veröentlichten Umfrage zufolge spielen in Deutschland 32,6% der Männer und 12,2% der Frauen zumindest gelegentlich Schach. [6]

3

2.2 Grundlegendes

Schach wird von zwei Spielern auf einem 8x8 Felder groÿen Brett gespielt, dessen quadratische Felder abwechselnd schwarz und weiÿ gefärbt sind. Das Schachbrett wird so gedreht, dass das linke Feld der Grundreihe beider gegenüber sitzender Spieler schwarz ist. Die waagerechten Reihen werden mit arabischen Ziern durchnummeriert, die senkrechten Linien alphabetisch. So entspricht jedem Feld ein kartesisches Koordinatenpaar von a1 bis h8.

Die 8 Figuren ¹ (Turm, Springer, Läufer, Dame, König) und die 8 Bauern beider Spieler werden zu folgender Grundaufstellung aufgestellt:

Die Bauern werden auf den Reihen 2 und 7 aufgestellt, auf den Grundreihen (1 und 8) nden von auÿen nach innen Turm, Springer und Läufer Platz. Auf die verbliebenen zwei Grundreihenfelder gehören die Dame und der König, wobei der Grundsatz regina regit colorem [7] gilt: die Damen besetzen jeweils das Feld ihrer eigenen Farbe. Auf das jeweils andere Feld wird der König gesetzt.

Die beiden Kontrahenten ziehen nun abwechselnd jeweils eine Figur. Ein Zug besteht aus zwei Halbzügen: Beim ersten Halbzug zieht Weiÿ, beim zweiten Schwarz. Daraus folgt, dass Weiÿ die Partie immer erönet.

Für die sechs verschiedenen Figuren gibt es genau denierte Zugregeln sowie zwei Sonderzüge (der Bauernschlagzug en passant und die Rochade), auf die an dieser Stelle nicht weiter eingegangen werden kann (4.2.3.1).

Zusätzlich gelten folgende Regeln, deren exaktes Verständnis für die spätere Programmierung grundlegend ist:

• Figuren dürfen weder eigene noch gegnerische Figuren überspringen. Die Rochade und der Springer stellen die einzigen beiden Ausnahmen dar.

• Figuren dürfen nur auf bereits belegte Felder ziehen, wenn auf dem Feld eine gegnerische Figur steht. Der ziehende Stein schlägt dann den anderen, der vom Brett genommen wird. Der einzige Stein, der niemals geschlagen werden darf, ist der König. Im Schach herrscht auÿerdem kein Schlagzwang.

• Wird ein König durch eine gegnerische Figur bedroht, so muss der Spieler, dessen König im sogenannten Schach steht, so ziehen, dass der König im nächsten Zug nicht mehr im Schach steht.

Steht der eigene König nicht im Schach, so ist naheliegend, dass der ziehende Spieler keinen Zug ausführen darf, der den eigenen König ins Schach stellt.

• Erreicht ein Bauer die gegnerische Grundreihe, so muss er sofort in einen beliebigen Ozier (Turm, Springer, Läufer, Dame) umgewandelt werden, unabhängig von der auf dem Brett schon vorhandenen Anzahl an Ozieren.

¹ Im Folgenden werden auch die Bauern als Figuren bezeichnet, obwohl sie streng genommen als Steine bezeichnet werden müssten.

4

2.3 Spielende

Es gibt zwei mögliche Ausgänge einer Partie: Das Schachmatt oder das Remis. Eine Auswertung von Schachdatenbanken ergab, dass ca. 32% aller Partien remis ausgehen. [7] Der Anteil an Remispartien steigt jedoch auch mit dem Spielniveau.

2.3.1 Matt

Bleibt einem Spieler, dessen König im Schach steht, kein gemäÿ 2.2 gültiger Zug, der das Schachgebot aufhebt, so ist dieser Spieler schachmatt, was das Ende der Partie zugunsten des Gegners bedeutet. Den gegnerischen König so vollständig zu bedrohen, dass er weder durch Wegziehen des Königs, Schlagen der Schach bietenden Figur, noch durch Zwischenziehen in die Schlaglinie das Schachgebot aufheben kann, erfordert sehr viel taktisches Geschick. Dieses taktische Geschick zu vermitteln ist die Hauptaufgabe der sogenannten Schachprobleme oder Schachkompositionen, bei denen in ausgedachten Stellungen sichere Mattwendungen gefunden werden sollen. Ein Algorithmus, der diese Problemstellungen löst, ist unbedingt erforderlich für das erfolgreiche Spiel eines Schachprogramms. Ein Problem ist von zentraler Bedeutung bei der späteren Entwicklung einer Funktion, die feststellt, ob ein König unbedroht ist, im Schach steht oder sogar matt ist: Ein König steht auch dann im Schach, wenn die bedrohende Figur durch den Schlagzug seinen eigenen König wegen eines Abzugschachs ins Schach stellen würde. Kurz: Auch wenn es keinen gültigen Schlagzug auf den König gibt, kann dieser bedroht oder sogar mattgesetzt sein.

Diese sonderbare Feststellung ergibt sich daraus, dass der König niemals geschlagen werden darf, sondern nur vollständig bedroht werden muss.

2.3.2 Remis

Ein Schachspiel endet remis, das heiÿt unentschieden, wenn eine der folgenden Bedingungen erfüllt ist: [8]

• ein am Zug bendlicher Spieler bietet dem Kontrahenten ein Remis an, das angenommen wird.

• es wurde 50 Züge lang keine Figur geschlagen und kein Bauer bewegt (beide Züge sind irreversibel).

• eine Stellung mit den gleichen Zugmöglichkeiten eines Spielers tritt zum dritten Mal auf.

• Eine sogenannte tote Stellung wird erreicht. Das bedeutet, dass kein Spieler selbst bei ungeschicktestem Spiel seines Gegners den anderen matt setzen kann.

• einem Spieler bleibt keine gültige Zugmöglichkeit und sein König steht nicht im Schach. Dieses spezielle Ergebnis wird auch als Patt bezeichnet.

5

2.4 Spieltheorie

Die Spieltheorie ist eine zwischen Mathematik, Ökonomie und Sozialwissenschaften anzusiedelnde Disziplin, deren Gegenstand die mathematische Modellierung von Spielen im weitesten Sinne, also Entscheidungsprobleme mit zwei oder mehr Entscheidern, ist. Die Spieltheorie ist daher die Wissenschaft vom strategischen Denken. [9, Seite 1] Schach lässt sich als ein zufallsfreies, sequentielles Zwei-Personen-Nullsummenspiel mit perfekter Information klassizieren. Die Nullsummeneigenschaft bedeutet, dass der Sieg eines Spielers immer mit der Niederlage des anderen einhergeht. Perfekte Information heiÿt, dass beiden Spielern zu allen Enscheidungszeitpunkten das gesamte vorangegangene Spielgeschehen und somit alle zuvor getroenen Entscheidungen seines Gegenspielers (im Rahmen seines Erinnerungsvermögens) bekannt sind. [10]

Diese Klassizierung bedeutet, dass es tatsächlich für jeden Spieler am Zug immer einen perfekten Zug gibt - allerdings wird dabei auch ein perfektes Spiel des Gegners vorausgesetzt. Dieser perfekte Zug lässt sich mithilfe des Minimax-Algorithmus ermitteln ² . Es ist eine sogenannte dominante Strategie, seine Züge mit dem Minimax-Algorithmus zu bestimmen, denn die Minimax-Strategie garantiert das beste Ergebnis bei optimaler Spielweise des Gegners. Wenden beide Spieler zur Bestimmung ihrer Strategie den Minimax-Algorithmus an, dann bildet das Strategiepaar daher ein spezielles Nash-Gleichgewicht ³ oder Nash Equilibrium. [13] [14]

Um diesen perfekten Zug zu nden, benötigt man jedoch den kompletten sogenannten Spielbaum, in dem alle möglichen Stellungen durch die Züge verbunden sind, mit denen man von einer Stellung in die jeweils andere gelangt. Diesen Spielbaum könnte man ausgehend von den Blättern (alle möglichen Endstellungen) bis zur Wurzel (Beginn der Partie in der Grundstellung) mithilfe des Minimax-Algorithmus aufarbeiten und dann eine Aussage darüber treen, ob bei beiderseits perfektem Spiel Weiÿ oder Schwarz gewinnt oder die Partie remis enden muss. [7]

Diese Möglichkeit scheint jedoch zur Freude der Schachspieler aufgrund der Komplexität des Schachspiels nicht realisierbar zu sein. Denn der komplette Spielbaum müsste aus geschätzten 2, 28 ∗ 10 ⁴⁶ verschiedenen Stellungen bestehen. Auf dieser Schätzung basiert die Annahme, dass die Anzahl aller möglichen Spielverläufe in der Gröÿenordnung 10 ¹¹⁵ bis 10 ¹²⁰ liegt. [7] Diese Zahl entspricht der Anzahl der Blätter und somit aller möglichen Pfade innerhalb des Spielbaums.

Zum Vergleich: Die Anzahl aller Quarks im sichtbaren Teil des Universums liegt etwa in der Gröÿenordnung 10 ⁸⁰ . [15, Anhang Seite 351]

Diese Zahlen sprengen alle heutigen - und wahrscheinlich auch zukünftigen - Grenzen der Berechenbarkeit, sodass man einen Algorithmus zur Zugsuche auf einen sehr kleinen Ausschnitt des gesamten Spielbaums begrenzen muss. Zur numerischen Bewertung der Stellungen in diesem Ausschnitt bedient man sich dann sogenannter Heuristiken ⁴ (also Schätz- und Erfahrungswerte sowie Faustregeln zur Bewertung von positionellen und materiellen Vor- und Nachteilen und der Abwägung derselben). Anhand dieser approximativen Bewertungen der verschiedenen Stellungen lässt sich dann mit einer optimierten Version des Minimax-Algorithmus ein wahrscheinlich guter Zug ermitteln. Die mathematische Exaktheit sowie die Garantie dafür, dass dieser Zug gut ist, wird damit verworfen. Dennoch liefert dieser heuristische Ansatz sehr gute Lösungen.

² Der Mathematiker und Mitbegründer der Spieltheorie John von Neumann bewies dieses Min-Max-Theorem 1928. [11, Anmerkung zur deutschen Übersetzung]

³ Das Nash-Gleichgewicht wurde 1950 vom genialen Nobelpreisträger John Forbes Nash Jr. in seiner Dissertation als grundlegendes Lösungskonzept der Spieltheorie entwickelt. [12]

⁴ Die Heuristik ist die Lehre von der methodischen Gewinnung neuer Erkenntnisse mithilfe von Denkmodellen, Analogien, Gedankenexperimenten; im Unterschied zur Logik, die lehrt, sie zu begründen. [16]

6

Kapitel 3

Software Engineering

Was ist Programmieren? Manche sagen, es sei eine Wissenschaft;

andere, es sei eine Kunst; wieder andere: ein Handwerk. Ich sage: keines allein, aber von jedem etwas.

Augusta Ada Byron [17, Seite 154]

3.1 Denition

Software Engineering (Softwaretechnik) befasst sich mit der professionellen, ingenieurgemäÿen Entwicklung umfangreicher Softwaresysteme. [18, Seite 764] Groÿe Softwareprojekte werfen grundlegend andere Probleme auf als die Entwicklung kleiner Programme, es sind komplexe, arbeitsteilige und vor allem kreative Prozesse, die sich nur schwer organisieren und umsetzen lassen.

Ein sehr groÿer Teil der Softwareprojekte muss aufgrund unvorhergesehener Probleme eingestellt werden, da deren Lösung sonst oft eine Kostenexplosion zur Folge hätte. Andere Produkte werden wegen Zeitmangel oft noch trotz bekannter Fehler in Umlauf gebracht, um die Kosten im Planungsrahmen zu halten.

Die folgende Karikatur [19] macht auf die Probleme aufmerksam, die entstehen, wenn in einem groÿen Softwareprojekt viele verschiedene Ansichten und Vorgehensweisen der Entwickler aufeinandertreen:

7

Um diese Probleme beherrschbar zu machen, müssen wir uns zunächst klar machen, was Software eigentlich ist.

8

Was macht nun ein Programm genau? Aus was ist es aufgebaut?

Programme sind eigentlich nichts weiter als eine Folge von sehr einfachen Befehlen. Um diese Befehle von einem Computer ausführen lassen zu können, müssen wir zunächst einige wenige elementare Befehle und Operationen denieren, die ein Prozessor eindeutig interpretieren und ausführen kann. Diese Befehle (vor allem ADD, SUB, AND, OR) bilden die sogenannte Maschinensprache. Ein Programm, das in Maschinensprache (also einer klar denierten Folge dieser Befehle) vorliegt, ist für Computer ausführbar, für Menschen jedoch nur sehr schwer - zum Beispiel mit Traces - nachvollziehbar. Das Schreiben aller Programme ist prinzipiell immer auch in Maschinensprache möglich, der Aufwand ist jedoch enorm und die Programmierung sehr fehleranfällig, weil die Maschinensprache sich vom intuitiven Verständnis des Menschen zu sehr unterscheidet. Deshalb entstanden, auf der Maschinensprache aufbauend ¹ , die abstrakteren, höheren Programmiersprachen, zum Beispiel Fortran, Lisp, Cobol, Pascal, C, Java, Perl oder Delphi. Alle Programmiersprachen haben - wie Sprachen allgemein - eine Syntax ² und eine Semantik (Bedeutung der syntaktischen Sprachelemente).

Die Syntax der höheren Programmiersprachen orientiert sich mehr an der menschlichen Intuition. Programme werden deshalb üblicherweise in höheren Programmiersprachen geschrieben und dann mit einem Compiler in semantisch äquivalente Maschinensprache übersetzt. Wir erweitern also unser Modell um diese Erkenntnis und fügen auÿerdem noch den Entwickler und den Anwender, der mit dem Programm mittels der Eingabedaten interagiert, ein:

¹ Deshalb werden Maschinensprachen unter dem Begri Second Generation Languages (2GL) und höhere Programmiersprachen unter Third Generation Languages (3GL) zusammengefasst. Darüber hinaus existieren heute auch Programmiersprachen der vierten Generation.

² Die Syntax einer Programmiersprache ist eine Beschreibung einer Obermenge der zulässigen Programmtexte. [18, Seite 480]

9

Die Mittel ³ , die uns die meisten modernen Programmiersprachen zur Verfügung stellen, sind:

• Abstraktion

• Klassen

• Datentypen (Variablen)

• Prozeduren (Befehlsblöcke)

• An- und Zuweisungen

• Bedingungen

• Schleifen

• Rekursion

• Kommentare

³ Seit der Begründung und Durchsetzung der strukturierten Programmierung durch Edsger Wybe Dijkstras legendäres Manuskript Go To Statement Considered Harmful im Jahr 1968 entfällt die von ihm als schädlich entlarvte Sprunganweisung Go To. [20]

10

Nun ist ersichtlich, wieso die Bewältigung von so komplexen Problemen wie Schach spielen mithilfe dieser wenigen, einfachen Befehle so schwierig ist; gleichzeitig liefern sie jedoch auch einen gängigen Lösungsansatz, den schon Ren´ e Decartes in seinen Regeln zur Leitung des Geistes im 17. Jahrhundert allgemein formulierte: [17, Seite 170]

• Jede der zu untersuchenden Schwierigkeiten ist in so viele Teile zu zerlegen als möglich und zur besseren Lösbarkeit nötig ist.

• Mit den einfachsten und fasslichsten Objekten ist zu beginnen und von da aus schrittweise zur Erkenntnis der kompliziertesten fortzufahren.

Dieser philosophische Leitfaden sieht, auf unser Problem übertragen, eine sogenannte Bottom-Up-Methode beim Entwickeln von Softwaresystemen vor (Das Pendant dazu ist die Top-Down-Methode). Bottom-Up-Design bedeutet im Software Engineering, dass das zu lösende Problem solange in kleinere, weniger komplexe Teilprobleme untergliedert wird, bis einzelne Teile so einfach geworden sind, dass man sie mit niedrigem Fehlerrisiko (also möglichst mit den aufgeführten elementaren Mitteln der höheren Programmiersprachen) implementieren kann. Darauf werden dann die Lösungen für die komplexeren Probleme mithilfe des Black-Box- bzw. Geheimhaltungsprinzips aufgebaut. Es ndet also eine Reduktion der Komplexität zur Bewältigung des Problems statt, was gleichermaÿen ein Grundsatz der strukturierten Programmierung ist. Dieses Prinzip soll im nächsten Kapitel nach Kräften meine Vorgehensweise kennzeichnen.

Bei der Entwicklung von kleinen Programmen lassen sich meist keine grundsätzlich verschiedenen Phasen feststellen, bei der Entwicklung von Software jedoch muss unbedingt eine klare Struktur und Phasenplanung vorhanden sein, da die Komplexität von Softwareentwicklung die von der Programmierung im Kleinen bei Weitem übersteigt und das Projekt somit ohne eine hinreichend detailliert geplante Vorgehensweise nicht zu handhaben ist.

Wenn wir uns der Beherrschung der Softwareentwicklung, also dem Software Engineering, zuwenden, müssen wir stets den evolutionären Charakter von Software ins Auge fassen: Software entsteht nicht in einem einfachen linearen Ablauf, sie ist das Endprodukt eines langwierigen, zyklischen Prozesses, in dessen Verlauf Wissen gefunden wird. Es ist ein abstraktes sprachliches Gebilde, das in der Regel immer Fehler unterschiedlicher Arten enthält.

Allgemein anerkannt ist, dass sich die professionelle Entwicklung von Software vom speziellen Fachbereich unabhängig immer in verschiedene Phasen einteilen lässt.

11

3.3 Phasen der Softwareentwicklung

Ein mögliches Modell ist die Einteilung der Softwareentwicklung in drei Phasen: 1. Problemanalyse, Anforderungsdenition (Spezikation) 2. (a) Systementwurf, Komponentenzerlegung, Verfeinerung

(b) Implementierung (Programmierung) 3. (a) Validation (Tests)

(b) Betriebseinsatz, Wartung

Die erste Phase beginnt damit, dass ein Kunde oder eine Firma an die Entwickler herantritt und bei ihnen ein Projekt in Auftrag gibt. Im Rahmen dieser Phase versuchen die Entwickler, das hinter der Software stehende Problem zu analysieren, über mögliche Lösungsansätze zu diskutieren und dadurch eine Vorstellung davon zu bekommen, wie komplex das zu bewältigende Problem ist.

Das Ergebnis dieser Phase, das an die zweite Phase weitergereicht wird, ist eine Anforderungsdenition, meist Spezikation genannt, die formal festlegt, was die zu entwickelnde Software leisten soll und ein Zeit- und Kostenplan, in dessen Rahmen die Umsetzung verwirklicht werden soll. Nicht festgelegt ist jedoch, wie die Software diese Leistung erbringen soll.

Diese modale Fragestellung ist zentraler Bestandteil der zweiten Phase, in der ein genauer Entwurf ent- und weiterentwickelt wird, also eine konkrete Lösung, die meist unter Befolgung der Bottom-Up-Methode durch Komponentenzerlegung gefunden wird. Es wird also festgelegt, wie die Software die in der ersten Phase spezizierte Leistung erbringen soll. Das Ergebnis wird zunächst plattformunabhängig zum Beispiel mit der standardisierten Sprache zur Modellierung von Software UML (Unied Modeling Language) festgehalten und algorithmisiert. Andere Hilfsmittel sind Pseudocode, Nassi-Shneiderman-Diagramme (Struktogramme), Ablauf- oder Flussdiagramme und Entscheidungstabellen. [21] Im zweiten Teil dieser Phase erfolgt dann die Implementierung, also die eigentliche Programmierung in einer geeigneten höheren Programmiersprache. Hier ist eine Verteilung der Aufgaben und die präzise Festlegung der Schnittstellen (API s) von gröÿter Wichtigkeit, um die Funktionsfähigkeit und die Kommunikation der einzelnen, unabhängig voneinander (von verschiedenen Programmierern) programmierten Module bzw. Komponenten zu gewährleisten.

In der dritten Phase erfolgt zunächst die Validation, die mit der Implementierung in enger Wechselwirkung steht, weshalb der Übergang von der zweiten zur dritten Phase ieÿend ist.

Durch systematisches Testen, angefangen mit Modultests, bei denen die Funktionsfähigkeit der einzelnen Module getestet wird, über Integrationstest, die den korrekten Informationsaustausch der Module untereinander überprüfen, bis zu Systemtests, die das System als ganzes testen, wird die programmierte Software validiert.

Eine wichtige Einsicht ist, dass die Korrektheit eines Programms mittels Tests nie veriziert, sondern nur falsizert werden kann: ein bestandener Test kann niemals die Abwesenheit von Fehlern beweisen ⁴ . Es wurde lediglich kein Fehler gefunden. Die Korrektheit

⁴ Program testing can be used to show the presence of bugs, but never to show their absence! Edsger Wybe Dijkstra [22]

12

eines Programms kann nur mithilfe des Hoare-Kalküls formal bewiesen werden, diese Möglichkeit ist praktisch jedoch sehr eingeschränkt.

Tests sollten in der Regeln nicht von den Programmierern der Software erdacht und durchgeführt werden, da die Gefahr besteht, dass sie aufgrund des Wissens über die innere Funktionsweise der Software die Tests so an das System anpassen, dass Schwächen umgangen und so nicht gefunden werden. Bei einem unabhängigen Testteam besteht diese Gefahr nicht, denn sie wissen nicht, wie ein zu testendes Modul oder System das Ergebnis einer Eingabe ermittelt. Bei einer Personalunion von Programmierer und Tester empehlt es sich daher, die Tests vor der Implementierung zu entwickeln. Das Ziel der Testphase ist die Reduzierung des Restrisikos von Fehlern im Programmcode und damit die Steigerung der Softwarequalität, wobei jeder Test genau dokumentiert wird. Zeigt die Software bei einem Test ein unerwünschtes Verhalten, wird mit einem Debugger versucht, die Ursache zu lokalisieren und dann zu korrigieren. Die Validation endet mit dem Abnahmetest, bei dem die Software anhand echter Daten gegen die ursprüngliche Spezikation getestet wird.

Auf das Bestehen des Abnahmetests folgt die technische Übertragung des Softwaresystems aus der Entwicklungs- in die Einsatzumgebung (Installation) und die Verfassung der Benutzerdokumentation als Hilfe für den Anwender. [18, Seite 776] Doch auch nach der Inbetriebnahme am Standort ist die Arbeit der Entwickler nicht abgeschlossen. Die Software muss gewartet werden, wobei zwischen der Fehlerbereinigung der aktuellen Version und der Entwicklung einer neuen Version unterschieden werden kann.

Zur konkreten Planung dieser verschiedenen Phasen konkurrieren verschiedene Modelle, auf die hier nicht weiter eingegangen werden kann, von denen jedoch jedoch einige erwähnt werden sollen: Phasen- oder Wasserfallmodelle, V-Modelle, Spiralmodelle und Zyklische Modelle.

Hervorzuheben ist das Anfang der 1990er vom Verteidigungsministerium entwickelte V-Modell, dessen Name sich von der V-förmigen Darstellung der Phasen ableitet. [21, Seite

321] Grundprinzip dieses Modells ist die Zerlegung des Projekts in kleinere, detailliertere Projekte und deren spätere Verzahnung. Das V-Modell bzw. das erweiterte W-Modell wird heute in den meisten Softwareprojekten angewendet.

3.4 Programmfehler

Es gibt verschiedene Arten von Programmfehlern (Bugs), die bei der Entwicklung von Software auftreten können: [23]

1. logische Fehler : Sie entstehen nur dann, wenn beim Systementwurf die Komplexität des Problems nicht vollständig verstanden und daher fehlerhafte oder unvollständige Algorithmen zur Lösung des Problems bemüht werden. Der gesamte Lösungsansatz ist also falsch oder unvollständig. Ein Fehler dieser Art, der erst in der Implementierung entdeckt wird, hat meist fatale Auswirkungen auf den Projektfortschritt, denn das gesamte Konzept muss überarbeitet oder sogar verworfen werden.

2. Syntaxfehler : Syntaxfehler sind die wohl unproblematischsten Programmierfehler, denn ein syntaktisch falsches Programm kann nicht kompiliert werden. Die meisten Programmierumgebungen geben dem Programmierer die Möglichkeit, diese Verstöÿe gegen die Syntax der Programmiersprache anzeigen zu lassen, sodass der Fehler sofort gefunden und schnell behoben werden kann.

13

3. Semantikfehler : Semantik - oder Laufzeitfehler sind alle Fehler, die dadurch entstehen, dass der Programmierer die innere Programmlogik nicht vollständig durchschauen kann. Daraus entsteht das Problem, dass die Semantik des Programmcodes von der eigentlichen Absicht des Programmierers abweicht. Lapidar gesagt: Das Programm tut nicht das, was der Programmierer will.

Diese Fehler zu erkennen und zu vermeiden ist wohl das schwierigste an der Implementierung, weil umfangreiches Wissen über den Aufbau und die Funktionsweise von Computern benötigt wird. Die Folgen von Semantikfehlern reichen von falschen Ausgabedaten über Speicherlecks bis hin zum kompletten Crash der Software. Unter den Laufzeitfehlern gibt es einige erwähnenswerte Exoten [23], die aufgrund der Namensgebung für Naturwissenschaftler recht unterhaltsam sein mögen: (a) Bohrbugs (nach Niels Bohr ): Ein Fehler, der zuverlässig reproduzierbar ist.

(b) Mandelbugs (nach Benoît Mandelbrot): Ein Fehler, dessen Ursachen so komplex sind, das sein Auftreten chaotisch erscheint (Mandelbrotmenge).

(c) Heisenbugs (nach Werner Heisenberg): Es kann sogar vorkommen, dass Fehler nicht mehr auftreten oder ihr Verhalten ändern, wenn man versucht, sie mit

(d) Schrödinbugs (nach Erwin Schrödinger ): Ein Fehler, der im Quelltext zufällig entdeckt wird und bis zu diesem Zeitpunkt niemals ein unerwünschtes Verhal-

Die Folgen von Programmfehlern können erheblich sein: [24]

Am 25.02.1991 verfehlte eine amerikanische Patriot-Abwehrrakete aufgrund von Rundungsfehlern bei zu langer Betriebszeit des Steuerungssystems eine Scud-Rakete und schlug in eine amerikanische Barracke ein. 28 amerikanische Soldaten starben.

Am 04.06.1996 explodierte die Ariane 5-Rakete in vier Kilometern Höhe, weil von der Ariane 4 übernommener Quelltext zu einem Überlauf in der Flugbahnberechnung führte. Der Schaden belief sich auf 600 Millionen Euro.

Diese zwei Fallbeispiele machen einerseits deutlich, wie wichtig die durchdachte Planung und Fehlerarmut von Software sein kann, andererseits zeigen sie auch, dass selbst Expertenteams nicht in der Lage sind, fehlerfreie Software zu kreieren. Wir kommen also zu der ernüchternden Feststellung, dass Software ab einer gewissen Gröÿe aufgrund der Komplexität sowohl des Entwurfs als auch des Codes immer fehlerbehaftet ist, Fehlerfreiheit ist selbst bei sorgfältigster Entwicklung nicht erreichbar. Je früher ein Fehler auftritt und je später er entdeckt wird, umso aufwendiger wird es, ihn zu beheben.

Irren ist menschlich.

Solange Menschen Programme schreiben, werden diese mit Fehlern behaftet sein.

Harry Marsh Sneed [17, Seite 179]

14

Kapitel 4

Schachsoftware

Premature optimization is the root of all evil.

Sir Charles Antony Richard Hoare [25]

4.1 Spezikation

Es soll eine Schachsoftware erstellt werden, die eine Figurenkonstellation auf einem zweidimensionalen Schachbrett (also mit einer Frontend ) ausgeben kann. Die Software soll, ausgehend von einer Konstellation, alle gültigen nächsten Züge ermitteln und ausgeben können, falls ein König im Schach steht oder matt (patt) ist. Mit diesen Leistungen soll dann zunächst ermöglicht werden, dass zwei menschliche Spieler gegeneinander Schach spielen können (Teil 1).

Weiterführend sollen die Spielpositionen der beiden Spieler mit verschiedenen heuristischen Bewertungsfunktionen numerisch bewertet werden.

Die Software soll anhand dieser Bewertungen dann in der Lage sein, sinnvoll gegen menschliche Spieler Schach spielen zu können und die meisten durchschnittlichen Spieler zu besiegen (Teil 2).

4.2 Systementwurf zu Teil 1

Der nachfolgende Systementwurf ist durch ein hierarchisches Funktionsgefüge mit starker Interdependenz gekennzeichnet. Es liegt ein Bottom-Up-Design vor, da mit einfachen, sehr speziellen Funktionen angefangen wird und darauf dann die schwierigeren, weil allgemeineren, aufgebaut werden. Der Entwurf ist für eine spätere Implementierung nach dem strukurierten bzw. prozeduralen Programmierparadigma vorgesehen.

Diser Systementwurf ist das Ergebnis eines sehr langen Denkprozesses (über ein Jahr). Warum ich mich für diese konkreten Lösungsansätze entschieden habe, kann dem Leser deshalb nur an einigen wenigen Stellen erläutert werden, da der Umfang sonst zu groÿ werden würde. Ich hoe dennoch, dass dem Leser einige Probleme klar werden.

4.2.1 Die Datenstrukturen

4.2.1.1 Interne Brettdarstellung

Das Schachbrett wird intern als zweidimensionales Array ['a'..'h',1..8] aus Bytes dargestellt. Dabei entsprechen denen im Array gespeicherten Zahlen folgende Figuren:

15

0 - leeres Feld 1 - schwarzer Bauer 2 - weiÿer Bauer

4 - weiÿer Turm 6 - weiÿer Springer 8 - weiÿer Läufer 10 - weiÿe Dame 11 - schwarzer König 12 - weiÿer König Diese Zuordnung hat den Vorteil, dass sich schwarze und weiÿe Figuren aufgrund der Teilbarkeit durch 2 mit oder ohne Rest unterscheiden lassen (modulo).

4.2.1.2 Klassen, Records, globale Variablen

Global deniert wird ein Datentyp TFeld für die Speicherung eines Feldes und TZug für die Speicherung eines Zuges (Start- und Zielfeld): TFeld = record Linie: Char; (a bis h) Reihe: Byte; (1 bis 8) end;

TZug = record

Von, Nach: TFeld; end;

Auÿerdem wird das Schachbrett (Array) in einem eigenen Record TSchachbrett zusammen mit den Königspositionen gespeichert, da die Königspositionen immer wieder für spätere Funktionen gebraucht werden. TSchachbrett = record Feld: array['a'..'h',1..8] of Byte; Pos_weisser_Koenig, Pos_schwarzer_Koenig: TFeld; end;

Der Datentyp TSchachbrett wird dann zusammen mit anderen wichtigen Variablen in den Datentyp TSchachkonstellation eingebettet: TSchachkonstellation = record Schachbrett: TSchachbrett; Spieler_am_Zug: Char; ('w' oder 's')

RochadeSpeicher: String[6]; (Speicherung von rochaderelevanten Zügen) en_passant_moeglich: Byte; (0-2: Anzahl der möglichen en passant-Züge) en_passant_Zug1, en_passant_Zug2: TZug; end;

Für die dynamische Darstellung - also die Erzeugung und Zerstörung von Bildinstanzen zur Laufzeit - wird ein Array aus Bildern deklariert und auÿerdem global abgespeichert, wieviele Instanzen im Moment aktiv sind (wichtig für die Zerstörung): Figurbild: array[1..32] of TImage; (bis zu 32 Instanzen von TImage) BilderAnzahl: Byte;

16

4.2.2 Frontend

Die Frontend ist eine gekapselte Prozedur, die Daten vom Typ TSchachbrett übergeben bekommt und dieses Schachbrett dann grasch ausgibt. Die einzelnen Figurenbilder dafür liegen als Bitmaps in 12 unsichtbaren Images auf der Form vor. Dazu sei in Pseudocode kurz beschrieben, wie die Prozedur dabei vorgeht: procedure Schachbrett_Zeichnen(Schachbrett); begin

Zeichne ein leeres Schachbrett;

Zerstöre alle Instanzen von TImage;

für alle Felder von Schachbrett tue:

wenn dieses Feld nicht leer ist dann begin

end;

4.2.3 Zugregeln

4.2.3.1 Grundzüge

Die nachfolgenden Funktionen gehen (mit Ausnahme des Bauern wegen verschiedener Schlag- und Zugrichtung) von einem leeren Schachbrett aus, es wird also noch nicht berücksichtigt, ob bei einem Zug Figuren im Weg stehen oder das Zielfeld bereits belegt ist. Ebenfalls nicht berücksichtigt sind die Sonderzüge von König und Bauer sowie die Überprüfung, ob der eigene König nach diesem Zug im Schach steht. Auf diese elementaren Funktionen wird dann nachher Stück für Stück eine Funktion aufgebaut, die prüft, ob ein Zug gültig oder ungültig ist (4.2.4.7).

Quelle der FIDE -Zugdenitionen: [26]

4.2.3.1.1 Turm Der Turm darf auf ein beliebiges anderes Feld entlang der Linie

4.2.3.1.2 Läufer Der Läufer darf auf ein beliebiges anderes Feld entlang einer der

4.2.3.1.3 Dame Die Dame darf auf ein beliebiges anderes Feld entlang der Linie,

4.2.3.1.4 König Er zieht auf ein beliebiges angrenzendes Feld.

4.2.3.1.5 Springer Der Springer darf auf eines der Felder ziehen, die seinem Standfeld

4.2.3.1.6 Bauer a) Der Bauer darf vorwärts auf das unbesetzte Feld direkt vor ihm

4.2.3.2 Kollisionsprüfung

Ist die Figur, die gezogen werden soll, ein Läufer, ein Turm oder eine Dame, so muss überprüft werden, ob die zwischen Start- und Zielfeld liegenden Felder leer sind. Ob das Zielfeld belegt ist, wird nicht berücksichtigt, denn das kann auf einer noch höheren Ebene (4.2.3.3) überprüft werden (nicht nur für Läufer, Turm und Dame sondern für alle Figuren).

function Kollisionsfrei(Schachbrett,Zug):Boolean; begin

wenn mindestens ein Feld zwischen Start- und Zielfeld belegt ist dann findet eine Kollision statt, der Rückgabewert ist also False; sonst ist der Rückgabewert True; end;

19

4.2.3.3 Gültiger Zug ohne Schachberücksichtigung

Eine Funktion, die prüft, ob ein Zug abgesehen vom ins Schach stellen des eigenen Königs gültig ist, ist aufgrund der in 2.3.1 festgestellten Problematik notwendig, um eine Funktion erstellen zu können, die erkennt, ob ein König bedroht ist. Zu beachten ist, dass die Rochade und das Schlagen en passant hier noch nicht berücksichtigt werden. Die Rochade kann auch gar nicht berücksichtigt werden, weil die Implementierung der Rochade auf die Funktion GueltigerZugOhneSchach zurückgreifen muss, um festzustellen, ob eine Rochade gültig ist. Deshalb muss GueltigerZugOhneSchach vor der Rochade implementiert werden. Diese komplexe Interdependenz der einzelnen Funktionen ist äuÿerst schwierig zu durchdringen und hat mir viel Kopfzerbrechen bereitet, bis ein konsistenter Entwurf

Es werden also nur die Grundzüge erkannt. Nicht berücksichtigt wird auch, welcher der Spieler gerade am Zug ist (es wird nur das Schachbrett übergeben, in dem nicht gespei-Im Datentyp TSchachkonstellation wird gespeichert, wieviele en passant-Schlagzüge der am Zug bendliche Spieler gerade ausführen darf (0-2). Gibt es eine Möglichkeit, wird diese in en_passant_Zug1 gespeichert, gibt es eine zweite, wird sie in en_passant_Zug2

Die Funktion en_passant_gueltig(Schachkonstellation,Zug):Boolean prüft, ob der übergebene Zug ein gültiger en passant-Zug ist. en_passant_moeglich, en_passant_Zug1 und en_passant_Zug2 müssen also nach jedem ausgeführten Halbzug in der Funktion ZugAusführen(Schachkonstellation,Zug):Schachkonstellation (4.2.4.6) aktualisiert werden.

4.2.3.5 Rochade gültig

Die Eigenschaft RochadeSpeicher des Datentyps TSchachkonstellation speichert in einem 6-stelligen String aus '0' (nicht bewegt) und '1' (bewegt), welche der 4 Türme und 2 Könige in der Partie bisher bewegt wurden. Diese rochaderelevanten Eigenschaften werden, genauso wie die für das Schlagen en passant relevanten, von der Funktion ZugAusführen

20

aktuell gehalten.

Die Funktion RochadeGueltig(Schachkonstellation,Art_der_Rochade):Boolean überprüft, ob bei

1. Art_der_Rochade = 1: einer kleinen schwarzen 2. Art_der_Rochade = 2: einer kleinen weiÿen 3. Art_der_Rochade = 3: einer groÿen schwarzen 4. Art_der_Rochade = 4: einer groÿen weiÿen Rochade der betreende König und Turm bereits bewegt wurden.

Dann muss überprüft werden, ob die Felder zwischen Turm und König leer sind. Dazu

kann die Funktion Kollision(Schachbrett,Zug:König>Turmfeld):Boolean auf ihren Rückgabewert überprüft werden. Ist nämlich die Rückgabe True, dann sind die Felder leer, bei

Als letztes wird überprüft, ob das Startfeld, Zielfeld oder das dazwischenliegende Feld des Königszug vom Gegner bedroht wird. Bedroht heiÿt, dass es mindestens einen gülti-Die nachfolgenden Funktionen bauen auf den bisherigen auf und sind die Grundlage für die zwei benötigten Funktionen GueltigerZug(Schachkonstellation,Zug):Boolean sowie ZugAusfuehren(Schachkonstellation,Zug):Schachkonstellation. GueltigerZug soll True zurückgeben, wenn der Zug regelkonform ist (nun unter Berücksichtigung aller Aspekte wie Sonderzüge und Schach). ZugAusfuehren führt diesen Zug dann aus, wobei diese Funktion nur aufgerufen wird, wenn der übergebene Zug vorher auf seine Gültigkeit überprüft wurde.

21

Bauer noch steht.

4.2.4.4 Rochade ausführen

RochadeAusfuehren(Schachbrett,Zug):Schachbrett soll ein Schachbrett übergeben bekommen, bei dem gerade der König seinen Rochadezug (als Zug übergeben) um zwei Felder nach links oder rechts ausgeführt hat. RochadeAusfuehren verschiebt dann den entsprechenden Turm auf das Zielfeld.

4.2.4.5 Bauernumwandlung

Da es relativ komplex ist ¹ , in das bisherige System eine beliebige Bauernumwandlung einzubetten, habe ich mich an dieser Stelle dazu entschieden, Bauern, die die gegnerische Grundreihe erreichen, immer in eine Dame zu verwandeln. Eine Unterverwandlung ndet so selten statt, dass sie im Rahmen dieses Projekts vernachlässigt werden kann.

¹ Das Problem besteht darin, dass die 4 verschiedenen Umwandlungen in der Erstellung des Spielbaums für die KI als 4 separate Züge behandelt werden müssen.

22

4.2.4.6 Zug ausführen

Während die bisherigen Funktionen alle nichts an den in TSchachkonstellation gespeicherten Parametern änderten, soll ZugAusfuehren(Schachkonstellation,Zug):Schachkonstellation nun auch diese Eigenschaften aktualisieren. Es wird aber davon ausgegangen, dass der übergebene Zug vorher auf seine Gültigkeit überprüft wurde (4.2.4.7).

4.2.4.7 Gültiger Zug

Die Funktion GueltigerZug(Schachkonstellation,Zug):Boolean soll True zurückliefern, wenn der übergebene Zug gültig ist, sonst False. Es werden dabei nun alle Sonderzüge berücksichtigt sowie überprüft, ob der eigene König nach dem Zug im Schach steht. Auÿerdem wird berücksichtigt, wer gerade am Zug ist (Spieler_am_Zug). Zur Überprüfung, ob der eigene König nach dem Zug im Schach stehen würde, wird Schach(ZugAusfuehren(Zug)) aufgerufen, aber vor der Übergabe des Rückgabewerts vom Typ TSchachkonstellation von ZugAusfuehren an Schach wird Spieler_am_Zug getauscht. Getauscht wird der Spieler am Zug, weil die Funktion Schach nur überprüft, ob der König

23

nur dass Schach(Schachkonstellation) auf False hin untersucht wird.

4.2.5 Benutzersteuerung

4.2.5.1 Zugeingabe

Der Zug des Benutzers soll per Mausklick auf das Start- und dann auf das Zielfeld eingegeben werden. Die Funktion MausPos_To_Feld(MausPos):Feld soll den übergebenen Mauskoordinaten das entsprechende Feld zuordnen. Wurde das Start- und das Zielfeld so übergeben, wird geprüft, ob der Zug gültig ist. Wenn ja, wird der Zug ausgeführt (also global die neue Konstellation übernommen), das Schachbrett neu gezeichnet (Schach- brettZeichnen(Schachbrett)) undüberprüft, ob durch diesen Zug eine Schach-, Matt- oder Pattsituation entstanden ist und das Zutreende ausgegeben. Ist der übergebene Zug nicht gültig, wird eine Fehlermeldung ausgegeben.

24

MomentanePartieKonstellation verweist immer auf den Speicherplatz, wo die mit der Frontend angezeigte Figurenkonstellation abgespeichert ist und dient somit als Anker der Zeigerkette.

Um den letzten Halbzug rückgängig zu machen, wird MomentanePartieKonstellation der Wert MomentanePartieKonstellation.VorherigeKonstellation zugewiesen und diese neue Konstellation ausgegeben. MomentanePartieKonstellation.VorherigeKonstellation = nil muss abgefangen werden und mit einer Fehlermeldung behandelt werden (die Partie bendet sich dann in der Grundstellung).

4.2.5.3 Mögliche Züge

Dem Benutzer sollen auf Anfrage alle gültigen Züge ausgegeben werden, die zur Auswahl stehen. Dies wird mit zwei (bzw. vier) verschachtelten Schleifen ermittelt, die für alle erdenklichen Züge prüft, ob dieser Zug gültig ist. Dem Benutzer wird dann eine Liste mit einer einfachen algebraischen Notation aller gültigen Züge ausgegeben.

² Die Funktion Grundstellung:Schachkonstellation soll diese Grundstellung zurückliefern.

25

4.3 Anmerkungen zur Implementierung von Teil 1

Der bisher beschriebene Systementwurf wurde innerhalb von zwei Tagen mit einem Umfang von 1.328 Zeilen Code implementiert. Bei der Frontend traten keinerlei Probleme auf, bei den Zugregeln nur zwei kleine Fehler (Start- und Zielfeld vertauscht), die innerhalb weniger Minuten mithilfe des Debuggers gefunden waren. Teilweise wurden die in 4.2 dargestellten Struktogramme etwas vereinfacht oder kleinere Fehler bemerkt und korrigiert (zum Beispiel beim Bauernzug). Bei der Implementierung der Benutzersteuerung traten keine Probleme auf.

Im Groÿen und Ganzen war der erarbeitete Systementwurf so gut, dass keine grundsätzlichen Probleme bei der Implementierung entstanden. Das ermöglichte erst die überraschend schnelle und sehr fehlerarme (vielleicht sogar fehlerfreie) Implementierung, was zeigt, wie wichtig ein guter Systementwurf für die Entwicklung von Software ist und wie klein dadurch der Zeitanteil der eigentlichen Implementierung ist.

Der bisher realisierte Teil wurde von mir und einigen Freunden (Bananensoftware) ausgiebig (vor allem auf die Korrektheit der generierten Zugmöglichkeiten) getestet ³ . Es wurden bisher keine Fehler gefunden, sodass auf diesem Teil nun der zweite Teil aufgebaut werden kann.

4.4 Systementwurf zu Teil 2

Der nun folgende Systementwurf zur Entwicklung einer schwachen künstlichen Intelligenz, die dann den schwarzen Spieler steuert, beruht auf folgender Grundlage:

Es gibt zwei grundlegend verschiedene Strategien zur Entwicklung einer Schach-KI, die A-Strategie und die B-Strategie. Die A-Strategie ist eine sogenannte Brute-Force-Methode, bei der alle möglichen Züge berücksichtigt werden, bei der B-Strategie hingegen wird versucht, sich auf wenigere, plausible Züge zu begrenzen und somit mehr wie ein Mensch vorzugehen. [27]

Das hier entworfene System folgt der A-Strategie. Es soll ein Spielbaum mit fester Tiefe erstellt werden. Dieser Spielbaum soll dann mithilfe des in 2.4 schon erwähnten Minimax-Algorithmus aufgearbeitet werden.

Dazu wird zunächst eine gute Bewertungsfunktion benötigt, die für eine Schachkonstellation einen numerischen Wert zurückliefert, der etwas darüber aussagt, wie gut oder schlecht es für die beiden Spieler momentan steht.

Ein Wert um 0 steht für eine ausgeglichene Stellung, je gröÿer der Wert, desto besser ist die Stellung für weiÿ, je kleiner (negativ), desto besser für schwarz. Die Blätter (nicht die Knoten!) des generierten Spielbaums werden mit dieser Bewertungsfunktion bewertet.

Der Minimax-Algorithmus ordnet dann jedem Knoten des Baumes das Maximum der Bewertungen der Folgestellungen zu, wenn weiÿ am Zug ist und das Minimum, wenn schwarz am Zug ist. Dieses Vorgehen sichert das am wenigsten schlechte Ergebnis bei

³ Dazu wurden sowohl Modul-, Schnittstellen- als auch Systemtests mit und ohne Debugger durchgeführt

26

optimaler Spielweise des Gegners.

An der Wurzel des Baumes angelangt, wird dann der Zug ausgewählt, für den der Minimax-Algorithmus die kleinste Zahl "hochliefert", denn das ist der (durch den kleinen Spielbaumausschnitt und die Güte der Bewertungsfunktion begrenzte) beste Zug für schwarz.

4.4.1 Bewertungsfunktionen

Die folgenden drei Bewertungsfunktionen sind sehr einfach aufgebaut und aufgrund meiner amateurmäÿigen Schachkenntnisse nicht sehr aussagekräftig. Sie können aber jederzeit unabhängig vom Rest des Systems geändert werden, sodass diese Bewertungsfunktionen vorerst genügen sollten.

4.4.1.1 Materielle Bewertung

Die materielle Komponente der Bewertungsfunktion geht von folgenden Wertigkeiten aus:

• Bauer: 100

• Springer: 275

• Läufer: 325

• Turm: 465

• Dame: 900

Weiÿe Figuren werden addiert, schwarze subtrahiert, sodass aus einem Materialübergewicht einer Seite eine positive oder negative Zahl resultiert.

4.4.1.2 Positionelle Bewertung

Die positionelle Komponente berücksichtigt den Standort verschiedener Figuren.

• für jedes nach vorne gezogene Feld erhält ein Bauer 15 Punkte (näher an der Um-wandlung)

• ein Freibauer (kein gegnerischer Bauer auf der gleichen oder den angrenzenden Linien) erhält 20 Punkte, weil er von einer höherwertigen Figur von der Umwandlung abgehalten werden muss

• für einen Doppelbauern (zwei Bauern gleicher Farbe hintereinander) werden 20 Punkte abgezogen, weil der vordere den hinteren blockiert

• für einen Randbauern (auf a- oder h-Linie) werden 10 Punkte abgezogen, da sie leichter blockiert werden können

• steht diagonal vor einem Bauer ein Bauer gleicher Farbe, werden 5 Punkte addiert (bei zwei +10), um die Bildung von Bauernketten zu unterstützen

• für einen am Brettrand stehenden Springer werden 20 Punkte abgezogen, für einen in der Ecke stehenden sogar 40

• steht links, rechts, über oder unter einem Läufer ein zweiter Läufer gleicher Farbe, werden 20 Punkte addiert

27

• steht auf der gleichen Reihe oder Linie eines Turms ein zweiter Turm gleicher Farbe und sind die dazwischen liegenden Felder leer, werden 30 Punkte addiert

• steht auf der gleichen Reihe oder Linie einer Dame ein Turm gleicher Farbe und sind die dazwischen liegenden Felder leer, werden 40 Punkte addiert

• steht eine Dame nicht mehr auf der eigenen Grundreihe, werden 20 Punkte addiert

• hat eine Dame mindestens ein freies Feld um sich herum, werden 30 Punkte addiert

• hat ein König mindestens ein freies Feld um sich herum, werden 50 Punkte addiert

4.4.1.3 Beherrschter Raum

Für eine Bewertung des beherrschten Raumes habe ich mich für folgende Vorgehensweise entschieden:

Zunächst wird ein ShortInt-Array mit 64 Feldern deklariert und dessen Werte auf 0 gesetzt. Felder auf denen eine schwarze Figur steht erhalten den Wert -2, Felder mit weiÿen Figuren den Wert +2. Danach werden alle erdenklichen Züge in vier verschachtelten Schleifen auf ihre Gültigkeit (ohne Schachberücksichtigung) überprüft. Gibt es einen gültigen Zug einer schwarzen Figur auf ein leeres Feld, so wird vom Wert dieses Feldes 1 subtrahiert (Vorteil für schwarz). Bei einem gültigen Zug einer weiÿen Figur auf ein leeres Feld wird 1 addiert.

Wurden alle erdenklichen Züge überprüft, wird das Array ausgewertet. Alle Feldwerte des Arrays werden mit 5 multipliziert und dann aufsummiert, die vier zentralen Felder (d4, d5, e4, e5 ) werden jedoch dreifach gewertet, da die Beherrschung dieser Felder vorteilhaft ist.

4.4.1.4 Zusammenfassung zu einer Bewertungsfunktion

Die Bewertungsfunktion Bewertung(TSchachkonstellation):Integer, die diese drei Komponenten zusammenfasst, prüft zunächst, ob weiÿ oder schwarz matt ist. Ist weiÿ matt, liefert die Bewertungfunktion -100.000 zurück, bei schwarz 100.000. Liegt ein Patt vor, liefert die Funktion 0 zurück.

Liegt weder ein Matt noch ein Patt vor, werden die drei Komponenten aufsummiert. Diese Bewertungsfunktion wird nun zur Blattbewertung verwendet:

4.4.2 Spielbaumsuche mit dem Minimax-Algorithmus Iterativ arbeiten ist menschlich, rekursiv arbeiten ist göttlich.

Anonym [28]

Der Minimax-Algorithmus soll mit der rekursiven Funktion BesterZug(Schachkonstellation: TSchachkonstellation;Tiefe:Byte):Integer umgesetzt werden, deren Rückgabewert die Bewertung des besten Zuges zurückliefert. Wird diese Funktion für ein Blatt aufgerufen, liefert sie die Bewertung dieses Blatts zurück (Rekursionsanfang). Wird sie für einen Knoten aufgerufen, wird das Minimum oder Maximum (je nachdem ob schwarz oder weiÿ

28

am Zug ist) der Zugbewertungen aller gültigen Züge bei der vorliegenden Schachkonstellation zurückgeliefert (Rekursionsschritt).

Damit der erste Aufruf der Funktion mit der Schachkonstellation und der Tiefe 0 nicht nur die Bewertung des besten Zuges zurückliefert, sondern auch den Zug selbst, wird innerhalb der Funktion bei der Tiefe 0 jedes Mal, wenn ein neuer bester Zug gefunden wurde, dieser Zug global in Computerzug abgespeichert. Auf den Rückgabewert von BesterZug(MomentaneKonstellation,0):Integer wird deshalb überhaupt nicht zugegrien, nur auf die Rückgabewerte der Funktion mit Tiefe > 0.

Die Zeitkomplexität in Abhängigkeit von der Tiefe wächst selbstverständlich exponentiell, sodass bei einer nicht optimierten Variante zunächst nur bis zu einer Tiefe von 2 Halbzügen gerechnet wird. Eine feste Tiefe birgt viele Schwierigkeiten, die auf den begrenzten, starren Horizont der KI zurückzuführen sind. Eine wesentliche Verbesserung lieÿe sich mit einer Manipulation der Tiefenvariablen bei Schachgeboten und Schlagzügen erreichen, damit diese tiefer untersucht werden (Quiescent-Suche).

Die rekursive Funktion BesterZug, das Herzstück der KI, in Pseudocode: function BesterZug(Schachkonstellation:TSchachkonstellation;Tiefe:Byte; var

BewertungBesterZug, BewertungPruefZug:Integer; begin

wenn (Tiefe = MAX_TIEFE) oder (Matt) oder (Patt) dann

BesterZug := Bewertung dieser Schachkonstellation sonst begin für alle gültigen Prüfzüge tue begin

BesterZug := BewertungBesterZug

end;

end;

29

4.5 Anmerkungen zur Implementierung von Teil 2

Die beschriebenen Bewertungfunktionen wurden ohne Probleme umgesetzt, bei der Funktion BesterZug verursachte ein fehlendes else einen Laufzeitfehler, der aber nach ein paar Minuten lokalisiert und beseitigt war.

Der Programmieraufwand für diesen zweiten Teil war weitaus weniger groÿ als der des ersten Teils, da viel auf schon vorhandene Funktionen zurückgegrien werden konnte und ein relativ groÿer Teil einfache Benutzersteuerung war.

Die Gesamtlänge des Codes der letzten Version beläuft sich auf 2.105 Zeilen.

4.6 Die ersten Testpartien

Direkt nach der Implementierung des Minimax-Algorithmus spielte ich zwei Testpartien gegen den Computer, die ich trotz einer maximalen Tiefe von nur 2 Halbzügen beide verlor.

Diese zwei Partien haben mich sehr überrascht, denn ich dachte nicht, dass mein eigenes Programm mich schon in einer so frühen Version mühelos besiegen würde.

Dennoch wurden zwei Probleme deutlich:

• die für die Tiefe von 2 viel zu hohe Rechenzeit von bis zu 3 Sekunden

• die KI hat aufgrund des begrenzten Horizonts Probleme beim Mattsetzen im Endspiel

4.7 Optimierung der Rechenzeit

Das Problem des Mattsetzens lässt sich durch eine tiefere Spielbaumsuche zumindest relativieren, diese wiederum lässt sich mit einer besseren Zeitezienz der Suchfunktion umsetzen. Beide Probleme resultieren also aus der hohen Laufzeit. Die Ursache für diese überraschend hohe Laufzeit war schnell gefunden:

Das Problem besteht im Wesentlichen aus zwei Teilen:

• beim Rekursionsanfang in der Funktion BesterZug wird die Konstellation sowohl auf Matt als auch auf Patt untersucht, bevor von diesem Knoten aus die gültigen Züge ermittelt werden. Beim überwiegenden Teil aller Konstellation liegt jedoch weder ein Matt noch ein Patt vor, deswegen sollte diese Abfrage später stattnden, um massiv Rechenzeit einzusparen.

• die zweite Ursache ist der zu frühe Aufruf der Funktion Schach in der Funktion GueltigerZug. Da innerhalb der Funktion BesterZug insgesamt für alle 8 ⁴ = 4.096 erdenklichen Züge die Funktion GueltigerZug aufgerufen wird, die ihrerseits - selbst wenn der übergebene Zug auch ohne Schachberücksichtigung ungültig ist! - bis zu 4.096 Züge auf ihre Gültigkeit hin untersucht, ndet hier eine Explosion der Laufzeit statt.

Diese beiden oensichtlichen Ursachen wurden optimiert, das Ergebnis der Optimierung war wie erwartet sehr gut: Die Laufzeit wurde etwa auf ein Drittel reduziert! Infolgedessen hob ich die maximale Tiefe auf 3 an, die Zugsuche konnte im Mittelspiel

30

damit in etwa 30 - 40 Sekunden ausgeführt werden.

Weitere kleine Optimierungen, die im Quelltext als solche gekennzeichnet sind, trugen auch zu einer schnelleren Laufzeit bei, sodass in der letzten Programmversion vor Abgabe mit akzeptabler Wartezeit (bei meinem System 10 - 30 Sekunden) gegen den Computer mit Suchtiefe 3 (schwer) gespielt werden kann.

Tests mit Zählern, die die Anzahl der Aufrufe der einzelnen Funktionen speicherten, zeigten, wo das eigentliche Problem der Laufzeit liegt: der Zuggenerator könnte wesentlich eektiver realisiert werden. Es werden zu viele Züge auf Gültigkeit überprüft, die schon vorher ausgeschlossen werden könnten. Doch für diese BLL soll dieses Ergebnis genügen.

4.8 Weitere Tests von Dritten

Die Software wurde von mehreren Hobbyspielern getestet, dabei wurde ein Programmabsturz beim matt- oder pattsetzen der KI entdeckt. Der Fehler bestand darin, dass die Zugsuche unter bestimmten Umständen auch bei einem Matt oder Patt aufgerufen wurde, also wenn gar kein Zug möglich war. Das hatte zur Folge, dass nach dem Durchlaufen der Zugsuche noch der alte Computerzug global abgespeichert war. Dieser wurde dann noch einmal ausgeführt mit dem Ergebnis, dass der König vom Brett verschwand und sich das Programm völlig unvorhersehbar verhielt. Dank der detaillierten Fehlerbeschreibung lieÿ sich der Fehler schnell lokalisieren und beheben.

Die Spielstärke der KI lässt zwar zu wünschen übrig, von einer BLL kann jedoch kaum mehr verlangt werden als das, was diese KI zu leisten imstande ist. Die in 4.1. festgelegte Spezikation kann hiermit als erfüllt angesehen werden, da der Computer in der Lage ist, mit dem Minimax-Algorithmus mehr oder weniger sinnvoll gegen menschliche Spieler Schach zu spielen.

31

Kapitel 5

Nachwort

5.1 Zusammenfassung

Diese BLL entstand hauptsächlich in vier intensiven Arbeitsphasen:

Die erste Phase bestand hauptsächlich aus Nachdenken über die Architektur der Software, also der Bestandteile und deren Abhängigkeiten voneinander (Hierarchie). Diese Phase erstreckte sich über den längsten Zeitraum.

Es folgte eine Phase, in der ich die Kapitel 2 und 3 über Schach und Software Engineering verfasste, die jedoch später noch mehrmals abgeändert wurden, bis ich damit zufrieden war.

Nach dieser Phase (nach den Osterferien) wurde die Zeit dann immer knapper, und ich begann, jede freie Minute in der Schule für einen schriftlichen Systementwurf aufzuwenden. In dieser Phase entstanden die meisten der ca. 80 Seiten umfassenden handschriftlichen Ausarbeitungen: Entwürfe, Notizen, Problemfeststellungen, Lösungsansätze, Struktogramme, Skizzen, Modelle und Texte - oft sehr chaotisch.

Die letzte Phase bestand aus der Implementierung und den Tests. Die erste Zeile des Programms wurde gerade einmal zwei Wochen vor Abgabe geschrieben, trotzdem kam ich in diesen zwei Wochen wesentlich schneller voran als erwartet. Diese zwei Wochen waren aber mit Abstand die arbeitsintensivsten und belastendsten. Ständig die Befürchtung im Hinterkopf, die Software könne vielleicht nicht die Leistung erbringen die ich mir von ihr erhote, was in dieser kritischen Phase groÿe Teile der Planung sowie auch meinen eigenen Anspruch umgeworfen hätte, war die Erleichterung dann umso gröÿer, als ich die erste Partie gegen mein eigenes Programm spielte und merkte, dass es im Grunde sehr gut funktionierte.

Als Fazit dieser BLL lässt sich sagen, dass mir die Recherche im Themenbereich Software Engineering und Schachsoftware und das Schreiben darüber viel Spaÿ gemacht hat, tiefe Einblicke in die Probleme von Softwareentwicklung ermöglicht und meinen Horizont in systematischen Problemlösungsfähigkeiten, Anwendung von wissenschaftlichen Arbeitsmethoden aber auch Beherrschung von kreativen Prozessen sukzessive erweitert hat. Gleichzeitig hat mir diese umfassende Arbeit aber auch gezeigt, dass ein solch ehrgeiziges Projekt nie wirklich fertig wird, denn die Verbesserungsmöglichkeiten scheinen schier unbegrenzt. Im Rahmen der Möglichkeiten einer von einer einzelnen Person erbrachten Leistung bin ich mit dem Gesamtergebnis deshalb vollkommen zufrieden.

32

5.2 Ausblick

Die hier realisierte schwache KI ist geradezu minimalistisch gehalten, kann aber später um viele Aspekte erweitert werden, zum Beispiel mit: [29]

• einer besseren Zeitezienz, denn das gleiche Ergebnis in kürzerer Zeit bedeutet mehr untersuchte Stellungen und somit eine verbesserte Spielstärke

• einem ezienteren Zuggenerator mit Bitboards

• besseren Bewertungsfunktionen (Material, beherrschter Raum, Beweglichkeit, Bedrohungen, Figurenzusammenspiel, Entwicklungstempo, Verlust der Rochademöglichkeit)

• Erkennung von Erönung, Mittelspiel und Endspiel, verschiede Algorithmen, Suchtiefen und Gewichtungen der Bewertungsfunktionen für die einzelnen Phasen

• einem Alpha-Beta-Algorithmus zur Zugsuche (Alpha-Beta-Cutos)

• einer Zugsortierung, damit die Alpha-Beta-Cutos gröÿere Teile des Spielbaums abschneiden

• der Erkennung und Abschneidung von Nullzügen (auÿer bei Zugzwang)

• einer iterativen Tiefensuche, die den Spielbaum Schritt für Schritt erweitert

• einer Quiescent-Suche zur variablen Tiefensuche z.B. bei Schlagzügen, Königsbedrohungen oder anderen kritischen Stellungen

• Hash-Tabellen zur Wiederverwendung von bereits ausgewerteten Stellungen

• Erönungs- und Endspielbibliotheken, die als Datenbank zur Verfügung stehen

• einer KI, die ihr Verhalten auf das des Gegners anpasst, also z.B. Bewertungsfunktionen zur Laufzeit ändert

• einer lernfähigen, starken KI 1

5.3 Danksagung

Zunächst möchte ich mich bei meinem Informatiklehrer Andreas Schowalter für die inhaltliche Zielsetzung und Planung dieser BLL bedanken. Der didaktisch hervorragende Unterricht hat zusätzlich zu dem Vorhaben beigetragen, diese BLL zu verfassen und gab Denkanstöÿe, die ich in dieser Arbeit weiter vertieft habe.

Mein besonderer Dank gilt auÿerdem meinem ehemaligen Informatiklehrer Joachim Ehlers, dessen anspruchsvoller Unterricht mich dazu motivierte während der MSS 11 und MSS 12 neben dem Unterricht zahlreiche Programme (insgesamt 76) zu entwickeln und umzusetzen, von simplen Spielen und Übungsprogrammen über rekursive Problemlösungen mit mathematischem Hintergrund bis hin zu physikalischen Anwendungen wie Interferenzsimulationen und Fraktaldarstellungen. Die Erfahrung in der Planung und Umsetzung dieser vielfältigen Programme ermöglichte erst die Bewältigung dieser BLL.

¹ ein Durchbruch in diesem Bereich (neuronale Netze, Schöpfung von echter Intelligenz und Bewusstsein) ist heute stark umstritten und wird wahrscheinlich nur Gegenstand von Science-Fiction-Büchern bleiben

33

Auÿerdem möchte ich mich bei meinem ehemaligen Mitschüler Johannes Bayer für die vielen Gespräche und die Zusammenarbeit in Mathematik, Physik, Informatik bis hin zur Philosophie bedanken. Das in der Einleitung geschilderte Arbeitsprojekt war meine erste Erfahrung in der arbeitsteiligen Softwareentwicklung und trug maÿgeblich zu meinem Verständnis von Software Engineering bei.

Bedanken möchte ich mich auch bei Arno Trautmann, der für einige Hilfestellungen und Tipps bezüglich des Softwarepakets L ^A T E X zur Verfügung stand und mir schon in der MSS 11 bei der Installation behilich war.

Zuletzt möchte ich mich bei allen bedanken, die die Software und vor allem die KI hilfsbereit auf Fehler und Spielstärke getestet haben.

5.4 Benutzte Programme

• dieser schriftliche Teil wurde mit dem L ^A T E X-Editor LEd 0.466020 erzeugt

• die Diagramme wurden mit Dia 0.96.1 erstellt

• die Struktogramme wurden mit Structorizer 3.08 erzeugt

• der Programmteil wurde mit Borland Delphi Enterprise 7.0 geschrieben

5.5 Literaturverzeichnis

[1] http://de.wikipedia.org/wiki/Unsterbliche_Partie

[2] http://de.wikiquote.org/wiki/Schach [3] http://www.schachgeschichte.de/ [4] http://de.wikipedia.org/wiki/Schachmatt [5] http://de.wikibooks.org/wiki/Schach:_CHAP1 [6] http://www.presseportal.de/story.htx?nr=925770 [7] http://de.wikipedia.org/wiki/Schach [8] http://de.wikipedia.org/wiki/Remis

[9] Avinash Dixit, Barry Nalebu: Spieltheorie für Einsteiger, Schäer-Poeschel, 1. Auage 1997

[10] http://de.wikipedia.org/wiki/Spiel_(Spieltheorie) [11] http://de.wikipedia.org/wiki/John_von_Neumann [12] http://www.spieltheorie.de/Nobelpreis/john-nash.htm [13] http://de.wikipedia.org/wiki/Minimax-Algorithmus [14] http://william-king.www.drexel.edu/top/eco/game/nash.html [15] Harald Fritzsch: Vom Urknall zum Zerfall, Piper, 6. Auage 2002 [16] http://lexikon.meyers.de/meyers/Heuristik

34

[17] Rüdeger Baumann: Informatik für die Sekundarstufe II Band 1, Klett, 1. Auage

1999

[18] Gustav Pomberger, Peter Rechenberg: Informatik-Handbuch, HANSER, 3. Auage

2002

[19] Unterrichtsmaterial der MSS 11 von Joachim Ehlers [20] http://www.cs.utexas.edu/users/EWD/ewd02xx/EWD215.PDF [21] Hartmut Ernst: Grundkurs Informatik, vieweg, 3. Auage 2003 [22] http://www.cs.utexas.edu/users/EWD/ewd02xx/EWD249.PDF [23] http://de.wikipedia.org/wiki/Programmfehler [24] http://www.munopag.de/archiv/SoftwareEngineering/ 2004Sommersemester/1__Folien/I-Einfuehrung-2-auf-1.pdf [25] http://www.faqs.org/docs/artu/ch01s06.html [26] http://www.chessica.de/regeln.html [27] http://de.wikipedia.org/wiki/A-Strategie [28] http://delphi.zsg-rottenburg.de/parser.html [29] http://www.top-5000.nl/ps/Tutorial how to write a chess program.pdf

Der letzte Aufruf der Internetquellen fand am 19. Juni 2008 statt.

5.6 Online-Verfügbarkeit

Diese BLL ist in drei Teilen online verfügbar:

• Dieser schriftliche Teil als pdf : http://home.arcor.de/danielwitzke/BLL/BLL.pdf

• Der Programmteil als exe: http://home.arcor.de/danielwitzke/BLL/Schach.exe

• Die vollständigen Sourcen des Programms als selbstentpackendes exe-Archiv : http://home.arcor.de/danielwitzke/BLL/SchachSource.exe

5.7 Erklärung

Hiermit erkläre ich, dass ich diese Arbeit selbstständig verfasst

und keine anderen als die angegebenen Hilfsmittel benutzt habe.

Daniel Witzke

Altenbamberg, den 19. Juni 2008

35

Anhang A

Quelltext

Dieser Quelltext ist wegen besserer Lesbarkeit in Delphi auch online verfügbar (siehe 5.6)

unit SchachUnit;

interface uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, ExtCtrls, StdCtrls, Math, ComCtrls; type

TPartieZeiger = ^TPartie; // Pointerdeklaration für die Partiezeigerkette TSchachForm = class(TForm) SchachbrettImage: TImage; Image1: TImage; Image2: TImage; Image3: TImage; Image4: TImage; Image5: TImage; Image6: TImage; Image7: TImage; Image8: TImage; Image9: TImage; Image10: TImage; Image11: TImage; Image12: TImage; KlickImage: TImage; AusgabeLoeschenTimer: TTimer; RueckgaengigLabel: TLabel; NeuePartieLabel: TLabel; MoeglicheZuegeLabel: TLabel; SpielerGegenSpielerLabel: TLabel; SpielerGegenComputerLabel: TLabel; EinfachLabel: TLabel; MittelLabel: TLabel; SchwerLabel: TLabel; InfoLabel: TLabel; InformationenRichEdit: TRichEdit; procedure FormCreate(Sender: TObject); procedure FormKeyPress(Sender: TObject; var Key: Char); procedure KlickImageClick(Sender: TObject); procedure AusgabeLoeschenTimerTimer(Sender: TObject); procedure FormClose(Sender: TObject; var Action: TCloseAction); procedure RueckgaengigLabelClick(Sender: TObject); procedure NeuePartieLabelClick(Sender: TObject); procedure MoeglicheZuegeLabelClick(Sender: TObject); procedure SpielerGegenComputerLabelClick(Sender: TObject); procedure SpielerGegenSpielerLabelClick(Sender: TObject); procedure EinfachLabelClick(Sender: TObject); procedure MittelLabelClick(Sender: TObject); procedure SchwerLabelClick(Sender: TObject); procedure InformationenRichEditKeyPress(Sender: TObject; var Key: Char);

procedure InfoLabelClick(Sender: TObject); private { Private-Deklarationen } public { Public-Deklarationen } end; TFeld = record Linie: Char; // 'a' bis 'h' Reihe: Byte; // 1 bis 8 end;

TRochade = record // benötigt für eine Funktion, die die drei Felder zurückliefert, die bei einer Rochade auf Bedrohung untersucht werden müssen PruefFeld: array[1..3] of TFeld; end; TZug = record Von, Nach: TFeld; end; TSchachbrett = record

i

Feld: array['a'..'h',1..8] of Byte; // hier werden die Figurenwerte gespeichert: { 0 - leeres Feld 1 - schwarzer Bauer 2 - weisser Bauer 3 - schwarzer Turm 4 - weisser Turm 5 - schwarzer Springer 6 - weisser Springer 7 - schwarzer Läufer 8 - weisser Läufer 9 - schwarze Dame 10 - weisse Dame 11 - schwarzer König 12 - weisser König }

Pos_weisser_Koenig, Pos_schwarzer_Koenig: TFeld; // die Positionen der Könige end;

TErweitertesSchachbrett = record // Für die Überprüfung der Felder um Figuren herum (ausserhalb des eigentlichen Schachbretts liegende Felder erhalten den Wert -1) Feld: array['`'..'i',0..9] of ShortInt; end; TSchachkonstellation = record Schachbrett: TSchachbrett; Spieler_am_Zug: Char; // 'w' oder 's'

RochadeSpeicher: String[6]; // 6-stelliger String, in dem gespeichert wird, welcher der 4 Türme und 2 König in der Partie schon bewegt wurden {

1. Stelle - schwarzer Turm auf A8 2. Stelle - schwarzer König auf E8 3. Stelle - schwarzer Turm auf H8 4. Stelle - weisser Turm auf A1 5. Stelle - weisser König auf E1 6. Stelle - weisser Turm auf H1 }

en_passant_moeglich: Byte; // Anzahl der für den am Zug befindlichen Spieler gültigen en-passant-Züge en_passant_Zug1, en_passant_Zug2: TZug; // Die en-passant-Züge end; TPartie = record Konstellation: TSchachkonstellation; VorherigeKonstellation: TPartieZeiger; end; var SchachForm: TSchachForm;

Figurbild: array[1..32] of TImage; // Es werden maximal 32 Figurenbilder gebraucht BilderAnzahl: Byte; // Anzahl der zur Laufzeit erzeugten Instanzen von TImage

Startfeld,Zielfeld: TFeld; // Speicherung der vom Benutzer per Mausklicks festgelegten Start- und Zielfelder Startfeld_festgelegt: Boolean; // Wurde ein Startfeld festgelegt? MomentanePartieKonstellation: TPartieZeiger; // Anker der Partiezeigerkette

GegenComputer: Boolean; // True wenn ein Spieler gegen den Computer spielt, False bei Spieler gegen Spieler ComputerZug: TZug; // der vom Minimax-Algorithmus ermittelte beste Zug des Computers Max_Tiefe: Byte; // die maximale Suchtiefe in Halbzügen const HINTERGRUNDFARBE = clBlue; // materielle Bewertung: BAUER = 100; SPRINGER = 275; LAEUFER = 325; TURM = 465; DAME = 900; // positionelle Bewertung: BAUERFORTSCHRITT = 15; FREIBAUER = 20; DOPPELBAUER = -20; RANDBAUER = -10; BAUERDECKUNG = 5; RANDSPRINGER = -20; ECKSPRINGER = -40; LAEUFERPAAR = 20; TURMPAAR = 30; DAMETURMPAAR = 40; DAMEVORNE = 20; DAMENBEWEGLICHKEIT = 30; KOENIGSBEWEGLICHKEIT = 50; // andere Bewertungen: FELDBEHERRSCHUNG = 5; GEWICHTUNGSFAKTOR_ZENTRALE_FELDER = 3; SCHACHBEWERTUNG = 100; MATTBEWERTUNG = 100000; PATTBEWERTUNG = 0; implementation {$R *.dfm}

function Gerade(Zahl:Byte):Boolean; // liefert die Parität einer natürlichen Zahl zurück begin if Zahl mod 2 = 0

ii

then Gerade := True else Gerade := False; end;

function sgn(Zahl:ShortInt):ShortInt; // Die Signumfunktion (Vorzeichenfunktion) für ganze Zahlen (wird nur für die Kollisionsfunktion benötigt, deshalb der kleine Definitionsbereich! Die Eingabewerte liegen zwischen -8 und 8) begin if Zahl = 0 then sgn := 0 else if Zahl > 0 then sgn := 1 else sgn := -1; end;

function BooleanToString(Input:Boolean):String; // True --> 'True', False --> 'False' begin if Input then BooleanToString := 'True' else BooleanToString := 'False'; end;

function FarbeChar_To_FarbeString(Spieler_am_Zug:Char):String; // 'w' --> 'weiss', 's' --> 'schwarz' begin if Spieler_am_Zug = 'w' then

FarbeChar_To_FarbeString := 'weiss' else

FarbeChar_To_FarbeString := 'schwarz'; end;

function Linie_To_Zahl(Linie:Char):Byte; // Ordnet einer Linie ('a' bis 'h') eine entsprechende Zahl zu (1 bis 8) begin

Linie_To_Zahl := succ(ord(Linie) - ord('a')); end;

function Linie_Reihe_To_Feld(Linie:Char;Reihe:Byte):TFeld; // Kapselt Linie und Reihe zum Datentyp TFeld var RueckgabeSpeicher: TFeld; begin

RueckgabeSpeicher.Linie := Linie; RueckgabeSpeicher.Reihe := Reihe; Linie_Reihe_To_Feld := RueckgabeSpeicher; end;

function Feld_To_FeldString(Feld:TFeld):String; // gibt das Feld als String zurück, z.B. 'A1', 'E4' begin

Feld_To_FeldString := Uppercase(Feld.Linie) + IntToStr(Feld.Reihe); end;

function Von_Nach_To_Zug(Von,Nach:TFeld):TZug; // Kapselt Von und Nach zum Datentyp TZug var RueckgabeSpeicher: TZug; begin RueckgabeSpeicher.Von := Von; RueckgabeSpeicher.Nach := Nach; Von_Nach_To_Zug := RueckgabeSpeicher; end;

function Grundstellung:TSchachkonstellation; // Liefert die Grundstellung einer Partie als Datentyp TSchachkonstellation zurück var LinienZaehler: Char; ReihenZaehler: Byte; RueckgabeSpeicher: TSchachkonstellation; begin with RueckgabeSpeicher do begin with Schachbrett do begin for ReihenZaehler := 3 to 6 do for LinienZaehler := 'a' to 'h' do Feld[LinienZaehler,ReihenZaehler] := 0; // leere Felder for LinienZaehler := 'a' to 'h' do Feld[LinienZaehler,7] := 1; // schwarze Bauern

iii

for LinienZaehler := 'a' to 'h' do Feld[LinienZaehler,2] := 2; // weisse Bauern Feld['a',8] := 3; // schwarze Türme Feld['h',8] := 3; Feld['a',1] := 4; // weisse Türme Feld['h',1] := 4; Feld['b',8] := 5; // schwarze Springer Feld['g',8] := 5; Feld['b',1] := 6; // weisse Springer Feld['g',1] := 6; Feld['c',8] := 7; // schwarze Läufer Feld['f',8] := 7; Feld['c',1] := 8; // weisse Läufer Feld['f',1] := 8; Feld['d',8] := 9; // schwarze Dame Feld['d',1] := 10; // weisse Dame Feld['e',8] := 11; // schwarzer König Feld['e',1] := 12; // weisser König

Pos_weisser_Koenig := Linie_Reihe_To_Feld('e',1); // speichert die Position des weissen Königs Pos_schwarzer_Koenig := Linie_Reihe_To_Feld('e',8); // speichert die Position des schwarzen Königs end;

Spieler_am_Zug := 'w'; // weiss ist als erstes am Zug

RochadeSpeicher := '000000'; // keiner der vier Türme und 2 Könige wurden bewegt en_passant_moeglich := 0; // keine Schlagmöglichkeit en passant end;

Grundstellung := RueckgabeSpeicher; end;

procedure Leeres_Schachbrett_Zeichnen; // Zeichnet ein leeres Schachbrett var LinienZaehler: Char; ReihenZaehler: Byte; begin

with SchachForm.SchachbrettImage do begin with Canvas do begin Pen.Color := HINTERGRUNDFARBE; Brush.Color := Pen.Color;

RectAngle(0,0,Width,Height); // Hintergrund einfärben end;

for LinienZaehler := 'a' to 'h' do for ReihenZaehler := 1 to 8 do // für alle Felder begin

if Gerade(Linie_To_Zahl(LinienZaehler) + ReihenZaehler) // Wenn die Summe aus Linien- und Feldindex gerade ist then

else

Canvas.Pen.Color := Canvas.Brush.Color;

Canvas.Rectangle((Width - Height) div 2 + pred(Linie_To_Zahl(LinienZaehler))*(Height div 8),Height - pred(ReihenZaehler)*(Height div 8), (Width - Height) div 2 + Linie_To_Zahl(LinienZaehler)*(Height div 8),Height - ReihenZaehler*(Height div 8)); // färbt das Feld Canvas.TextOut((Width - Height) div 2 + Linie_To_Zahl(LinienZaehler)*(Height div 8) - Canvas.TextWidth(Feld_To_FeldString (Linie_Reihe_To_Feld(LinienZaehler,ReihenZaehler))) - 1,Height - pred(ReihenZaehler)*(Height div 8) - Canvas.TextHeight(Feld_To_FeldString (Linie_Reihe_To_Feld(LinienZaehler,ReihenZaehler))),Feld_To_FeldString(Linie_Reihe_To_Feld(LinienZaehler,ReihenZaehler))); // beschriftet das Feld in der unteren rechten Ecke mit den kartesischen Koordinaten end; end; end;

procedure FigurBildPlatzieren(Linie:Char;Reihe:Byte); // Platziert die zuletzt erzeugte Instanz von TImage zentriert auf dem Feld begin with SchachForm do begin

Figurbild[BilderAnzahl].Left := (Width - Height) div 2 + pred(Linie_To_Zahl(Linie))* (Height div 8) + (Height div 8 - Figurbild[BilderAnzahl].Width) div 2;

Figurbild[BilderAnzahl].Top := Height - Reihe*(Height div 8) + (Height div 8 - Figurbild[BilderAnzahl].Height) div 2;

iv

end; end;

procedure Schachbrett_Zeichnen(Schachbrett:TSchachbrett); // Gibt das übergebene Schachbrett grafisch aus (Frontend) var ZerstoerungsZaehler: Byte; LinienZaehler: Char; ReihenZaehler: Byte; begin

Leeres_Schachbrett_Zeichnen; // Zeichne ein leeres Schachbrett auf der Canvas von SchachbrettImage for ZerstoerungsZaehler := 1 to BilderAnzahl do

Figurbild[ZerstoerungsZaehler].Free; // Alle dynamisch erzeugten Instanzen von TImage zerstören BilderAnzahl := 0; for ReihenZaehler := 1 to 8 do for LinienZaehler := 'a' to 'h' do // für alle Felder

if Schachbrett.Feld[LinienZaehler,ReihenZaehler] <> 0 // wenn das Feld nicht leer ist then begin inc(BilderAnzahl);

FigurBild[BilderAnzahl] := TImage.Create(SchachForm); // dann wird eine neue Instanz von TImage erzeugt FigurBild[BilderAnzahl].Parent := SchachForm; FigurBild[BilderAnzahl].Transparent := True; with SchachForm do begin

die Bildbreite und -höhe angepasst

1: begin

end; end;

SchachForm.KlickImage.BringToFront; // Das KlickImage über die Figuren legen Startfeld_festgelegt := False; // es wurde noch kein Startfeld per Klick festgelegt end;

function schwarze_Figur(Schachbrett:TSchachbrett;PruefFeld:TFeld):Boolean; begin // überprüft, ob auf dem übergebenen Feld eine schwarze Figur steht schwarze_Figur := not (Gerade(Schachbrett.Feld[PruefFeld.Linie,PruefFeld.Reihe])); end;

function weisse_Figur(Schachbrett:TSchachbrett;PruefFeld:TFeld):Boolean; begin // überprüft, ob auf dem übergebenen Feld eine weisse Figur steht

weisse_Figur := (Schachbrett.Feld[PruefFeld.Linie,PruefFeld.Reihe] <> 0) and (Gerade(Schachbrett.Feld[PruefFeld.Linie,PruefFeld.Reihe])); end;

function TurmZugGueltig(Zug:TZug):Boolean; begin with Zug do

TurmZugGueltig := (Von.Reihe = Nach.Reihe) or (Von.Linie = Nach.Linie); // gleiche Reihe oder gleiche Linie end;

function LaeuferZugGueltig(Zug:TZug):Boolean; begin with Zug do

LaeuferZugGueltig := abs(Nach.Reihe - Von.Reihe) = abs(Linie_To_Zahl(Nach.Linie) - Linie_To_Zahl(Von.Linie)); // Liniendifferenz = Reihendifferenz end;

function DameZugGueltig(Zug:TZug):Boolean; begin

DameZugGueltig := TurmZugGueltig(Zug) or LaeuferZugGueltig(Zug); // Die Dame ist die Superposition von Turm und Läufer end;

function KoenigZugGueltig(Zug:TZug):Boolean; begin with Zug do

KoenigZugGueltig := (abs(Nach.Reihe - Von.Reihe) < 2) and (abs(Linie_To_Zahl(Nach.Linie) - Linie_To_Zahl(Von.Linie)) < 2); // die Linien- und Reihendifferenz darf jeweils höchstens 1 sein end;

function SpringerZugGueltig(Zug:TZug):Boolean; begin with Zug do

SpringerZugGueltig := ((abs(Nach.Reihe - Von.Reihe) = 2) and (abs(Linie_To_Zahl(Nach.Linie) - Linie_To_Zahl(Von.Linie)) = 1)) or ((abs(Nach.Reihe - Von.Reihe) = 1) and (abs(Linie_To_Zahl(Nach.Linie) - Linie_To_Zahl(Von.Linie)) = 2)); // (Liniendifferenz = 2 und Reihendifferenz = 1) oder (Liniendifferenz = 1 und Reihendifferenz = 2) end;

function BauerZugGueltig(Schachbrett:TSchachbrett;Zug:TZug):Boolean; begin with Zug do begin

if Schachbrett.Feld[Von.Linie,Von.Reihe] = 1 then // schwarzer Bauer if (Von.Reihe - Nach.Reihe) = 1 then // 1 nach vorne bewegt

if abs(Linie_To_Zahl(Nach.Linie) - Linie_To_Zahl(Von.Linie)) = 1 then // 1 nach links oder rechts bewegt

else // um mindestens 2 nach vorne bewegt

BauerZugGueltig := (Von.Reihe = 7) and (Nach.Reihe = 5) and (Von.Linie = Nach.Linie) and (Schachbrett.Feld[Von.Linie,5] = 0) and (Schachbrett.Feld[Von.Linie,6] = 0) // gültig wenn von der siebten auf die fünfte Reihe ohne seitliche Bewegung gezogen wird und die Felder frei sind else // weisser Bauer if (Nach.Reihe - Von.Reihe) = 1 then // 1 nach vorne bewegt

if abs(Linie_To_Zahl(Nach.Linie) - Linie_To_Zahl(Von.Linie)) = 1 then // 1 nach links oder rechts bewegt

else // um mindestens 2 nach vorne bewegt

vi

BauerZugGueltig := (Von.Reihe = 2) and (Nach.Reihe = 4) and (Von.Linie = Nach.Linie) and (Schachbrett.Feld[Von.Linie,3] = 0) and (Schachbrett.Feld[Von.Linie,4] = 0) // gültig wenn von der zweiten auf die vierte Reihe ohne seitliche Bewegung gezogen wird und die Felder frei sind end; end;

function Kollisionsfrei(Schachbrett:TSchachbrett;Zug:TZug):Boolean; // prüft für Turm, Läufer und Dame ob die Felder zwischen Start- und Zielfeld leer sind var RueckgabeSpeicher: Boolean; FeldZaehler: Byte; begin

RueckgabeSpeicher := True; // bisher keine Kollision with Zug do

for FeldZaehler := 1 to pred(Max(abs(Nach.Reihe - Von.Reihe),abs(Linie_To_Zahl(Nach.Linie) - Linie_To_Zahl(Von.Linie)))) do // der Zähler soll von 1 bis zur grössten Differenz (Reihen- oder Liniendifferenz) - 1 laufen. Das führt zu einer Anzahl an Schleifendurchläufen, die gleich der Anzahl der zwischen Start- und Zielfeld liegenden Felder ist

if Schachbrett.Feld[chr(ord(Von.Linie) + sgn(Linie_To_Zahl(Nach.Linie) - Linie_To_Zahl(Von.Linie))*FeldZaehler),Von.Reihe + sgn(Nach.Reihe - Von.Reihe)*FeldZaehler] <> 0 // die beiden Ausdrücke in den eckigen Klammern ergeben für jeden Schleifendurchlauf eines der zwischen Start- und Zielfeld liegenden Felder then // wenn dieses Feld belegt ist

RueckgabeSpeicher := False; // dann ist der Zug nicht kollisionsfrei Kollisionsfrei := RueckgabeSpeicher; end;

function Turm_Laeufer_oder_Dame(Figurenwert:Byte):Boolean; // liefert True zurück, wenn der übergebene Figurenwert dem eines Turms, Läufers oder der Dame entspricht begin case Figurenwert of

3,4,7,8,9,10: Turm_Laeufer_oder_Dame := True; else

Turm_Laeufer_oder_Dame := False; end; end;

function GueltigerZugOhneSchach(Schachbrett:TSchachbrett;Zug:TZug):Boolean; var FigurZugGueltig: Boolean; begin

FigurZugGueltig := False; // eigentlich überflüssig, vermeidet aber eine Warnung, dass FigurZugGueltig möglicherweise nicht initialisiert wurde with Zug do

if Schachbrett.Feld[Von.Linie,Von.Reihe] = 0 then // Startfeld leer GueltigerZugOhneSchach := False else // Startfeld nicht leer

if (Schachbrett.Feld[Nach.Linie,Nach.Reihe] = 0) or (weisse_Figur(Schachbrett,Von) and schwarze_Figur(Schachbrett,Nach)) or (schwarze_Figur(Schachbrett,Von) and weisse_Figur(Schachbrett,Nach)) then // Zielfeld leer oder andere Farbe als Startfeld begin

case Schachbrett.Feld[Von.Linie,Von.Reihe] of // prüft den Zug mittels der figurenspezifischen Funktionen

end;

if FigurZugGueltig

end

else // Zielfeld nicht leer oder gleiche Figurenfarbe von Start- und Zielfeld GueltigerZugOhneSchach := False; end;

function Felder_gleich(Feld1,Feld2:TFeld):Boolean; // prüft, ob die übergebenen Felder gleich sind begin

Felder_gleich := (Feld1.Linie = Feld2.Linie) and (Feld1.Reihe = Feld2.Reihe); end;

function Zuege_gleich(Zug1,Zug2:TZug):Boolean; // prüft, ob die übergebenen Züge gleich sind begin

Zuege_gleich := Felder_gleich(Zug1.Von,Zug2.Von) and Felder_gleich(Zug1.Nach,Zug2.Nach); end;

function en_passant_gueltig(Schachkonstellation:Tschachkonstellation;Zug:TZug):Boolean; // prüft, ob der übergebene Zug ein gültiger en-passant-Zug der momentanen Konstellation ist begin

vii

with Schachkonstellation do case en_passant_moeglich of

1: en_passant_gueltig := Zuege_gleich(en_passant_Zug1,Zug);

2: en_passant_gueltig := Zuege_gleich(en_passant_Zug1,Zug) or Zuege_gleich(en_passant_Zug2,Zug); else en_passant_gueltig := False; end; end;

function RochadePruefFelder(Art_der_Rochade:Byte):TRochade; // liefert die 3 Felder in einem Array zurück, die bei der jeweiligen Rochade auf Bedrohung durch gegnerische Figuren überprüft werden müssen var RueckgabeSpeicher: TRochade; LinienZaehler: Char; begin case Art_der_Rochade of 1: for LinienZaehler := 'e' to 'g' do

RueckgabeSpeicher.PruefFeld[Linie_To_Zahl(LinienZaehler) - Linie_To_Zahl('d')] := Linie_Reihe_To_Feld(LinienZaehler,8); 2: for LinienZaehler := 'e' to 'g' do

RueckgabeSpeicher.PruefFeld[Linie_To_Zahl(LinienZaehler) - Linie_To_Zahl('d')] := Linie_Reihe_To_Feld(LinienZaehler,1); 3: for LinienZaehler := 'e' downto 'c' do

RueckgabeSpeicher.PruefFeld[Linie_To_Zahl('f') - Linie_To_Zahl(LinienZaehler)] := Linie_Reihe_To_Feld(LinienZaehler,8); 4: for LinienZaehler := 'e' downto 'c' do

RueckgabeSpeicher.PruefFeld[Linie_To_Zahl('f') - Linie_To_Zahl(LinienZaehler)] := Linie_Reihe_To_Feld(LinienZaehler,1); end;

RochadePruefFelder := RueckgabeSpeicher; end;

function Rochade_Gueltig(Schachkonstellation:TSchachkonstellation;Art_der_Rochade:Byte):Boolean; // liefert zurück, ob die übergebene Rochadeart bei der übergebenen Konstellation gültig ist var

RueckgabeSpeicher,kein_gueltiger_Zug: Boolean; PruefFelder: TRochade; PruefZaehler,ReihenZaehler: Byte; LinienZaehler: Char; KollisionsPruefzug: TZug; begin with Schachkonstellation do begin

case Art_der_Rochade of // überprüft, ob die entsprechenen 2 Figuren in der Partie schon bewegt wurden 1: RueckgabeSpeicher := (RochadeSpeicher[2] = '0') and (RochadeSpeicher[3] = '0'); // kleine schwarze Rochade 2: RueckgabeSpeicher := (RochadeSpeicher[5] = '0') and (RochadeSpeicher[6] = '0'); // kleine weisse Rochade 3: RueckgabeSpeicher := (RochadeSpeicher[1] = '0') and (RochadeSpeicher[2] = '0'); // grosse schwarze Rochade 4: RueckgabeSpeicher := (RochadeSpeicher[4] = '0') and (RochadeSpeicher[5] = '0'); // grosse weisse Rochade else RueckgabeSpeicher := False; end; if RueckgabeSpeicher then begin case Art_der_Rochade of

1: KollisionsPruefZug := Von_Nach_To_Zug(Linie_Reihe_To_Feld('e',8),Linie_Reihe_To_Feld('h',8)); 2: KollisionsPruefZug := Von_Nach_To_Zug(Linie_Reihe_To_Feld('e',1),Linie_Reihe_To_Feld('h',1)); 3: KollisionsPruefZug := Von_Nach_To_Zug(Linie_Reihe_To_Feld('e',8),Linie_Reihe_To_Feld('a',8)); 4: KollisionsPruefZug := Von_Nach_To_Zug(Linie_Reihe_To_Feld('e',1),Linie_Reihe_To_Feld('a',1)); end;

RueckgabeSpeicher := Kollisionsfrei(Schachbrett,KollisionsPruefzug); // Prüft, ob die Felder zwischen dem entsprechenden Turm und König leer sind end; if RueckgabeSpeicher then begin kein_gueltiger_Zug := True; PruefFelder := RochadePruefFelder(Art_der_Rochade);

// For-Schleifen weil diese Funktion nicht so häufig aufgerufen wird, dass sich eine while-Schleife auf die Laufzeit merkbar auswirken würde

for PruefZaehler := 1 to 3 do // für die drei auf Bedrohung zu untersuchenden Felder for ReihenZaehler := 1 to 8 do for LinienZaehler := 'a' to 'h' do

if (GueltigerZugOhneSchach(Schachbrett,Von_Nach_To_Zug(Linie_Reihe_To_Feld(LinienZaehler,ReihenZaehler), PruefFelder.PruefFeld[PruefZaehler]))) and (((weisse_Figur(Schachbrett,PruefFelder.PruefFeld[1]) and

(schwarze_Figur(Schachbrett,Linie_Reihe_To_Feld(LinienZaehler,ReihenZaehler)))) or ((schwarze_Figur(Schachbrett,PruefFelder.PruefFeld[1])) and (weisse_Figur(Schachbrett,Linie_Reihe_To_Feld(LinienZaehler,ReihenZaehler))))))

then // wenn es einen gültigen Zug ohne Schach von einer andersfarbigen Figur auf eines dieser Felder gibt kein_gueltiger_Zug := False; // dann ist mindestens eines dieser Felder von mindestens einer gegnerischen Figur bedroht RueckgabeSpeicher := kein_gueltiger_Zug; end; end;

Rochade_Gueltig := RueckgabeSpeicher; // wenn alle drei Teile True zurückliefern, ist die Rochade gültig end;

function Schach(Schachkonstellation:TSchachkonstellation):Boolean; // liefert zurück, ob der König des am Zug befindlichen Spielers bedroht wird

viii

var Pos_Koenig: TFeld; Zug_moeglich: Boolean; LinienZaehler: Char; ReihenZaehler: Byte; begin with Schachkonstellation do if Spieler_am_Zug = 'w' then // Position des Königs speichern Pos_Koenig := Schachbrett.Pos_weisser_Koenig else

Pos_Koenig := Schachbrett.Pos_schwarzer_Koenig; Zug_moeglich := False; // kein Zug auf das Königsfeld möglich LinienZaehler := 'a';

while (not Zug_moeglich) and (LinienZaehler < 'i') do // zwei verschachtelte while-Schleifen (zum vorzeitigen Abbruch sobald ein Zug gefunden wurde - die Funktion Schach wird sehr häufig aufgerufen) begin ReihenZaehler := 1;

while (not Zug_moeglich) and (ReihenZaehler < 9) do // Schleife über alle 64 Felder begin

Zug_moeglich := GueltigerZugOhneSchach(Schachkonstellation.Schachbrett,Von_Nach_To_Zug(Linie_Reihe_To_Feld (LinienZaehler,ReihenZaehler),Pos_Koenig)); // kann von diesem Feld auf das Königsfeld gezogen werden? inc(ReihenZaehler); end; inc(LinienZaehler); end;

Schach := Zug_moeglich; // Zuweisung des Ergebnisses end;

function FigurVerschieben(Schachbrett:TSchachbrett;Zug:TZug):TSchachbrett; // verschiebt die Figur von Zug.Von nach Zug.Nach und löscht das Startfeld var

RueckgabeSpeicher: TSchachbrett; begin

RueckgabeSpeicher := Schachbrett;

RueckgabeSpeicher.Feld[Zug.Nach.Linie,Zug.Nach.Reihe] := Schachbrett.Feld[Zug.Von.Linie,Zug.Von.Reihe]; RueckgabeSpeicher.Feld[Zug.Von.Linie,Zug.Von.Reihe] := 0; FigurVerschieben := RueckgabeSpeicher; end;

function en_passant_ausfuehren(Schachbrett:TSchachbrett;Zug:TZug):TSchachbrett; var

RueckgabeSpeicher: TSchachbrett; begin

RueckgabeSpeicher := Schachbrett; if Zug.Nach.Reihe = 3 then // schwarz hat en passant geschlagen

RueckgabeSpeicher.Feld[Zug.Nach.Linie,4] := 0 // Bauer auf der vierten Reihe auf der gleichen Linie wie der Bauer, der geschlagen hat, wird gelöscht

else // weiss hat en passant geschlagen

RueckgabeSpeicher.Feld[Zug.Nach.Linie,5] := 0; // Bauer auf der fünften Reihe auf der gleichen Linie wie der Bauer, der geschlagen hat, wird gelöscht

en_passant_ausfuehren := RueckgabeSpeicher; end;

function Rochade_Ausfuehren(Schachbrett:TSchachbrett;Zug:TZug):TSchachbrett; var

RueckgabeSpeicher: TSchachbrett; begin

RueckgabeSpeicher := Schachbrett; if Felder_gleich(Zug.Nach,Linie_Reihe_To_Feld('g',8)) then // kleine schwarze Rochade

RueckgabeSpeicher := FigurVerschieben(Schachbrett,Von_Nach_To_Zug(Linie_Reihe_To_Feld('h',8),Linie_Reihe_To_Feld('f',8))); // Turm von h8 nach f8 verschieben if Felder_gleich(Zug.Nach,Linie_Reihe_To_Feld('g',1)) then // kleine weisse Rochade

RueckgabeSpeicher := FigurVerschieben(Schachbrett,Von_Nach_To_Zug(Linie_Reihe_To_Feld('h',1),Linie_Reihe_To_Feld('f',1))); // Turm von h1 nach f1 verschieben if Felder_gleich(Zug.Nach,Linie_Reihe_To_Feld('c',8)) then // grosse schwarze Rochade

RueckgabeSpeicher := FigurVerschieben(Schachbrett,Von_Nach_To_Zug(Linie_Reihe_To_Feld('a',8),Linie_Reihe_To_Feld('d',8))); // Turm von a8 nach d8 verschieben if Felder_gleich(Zug.Nach,Linie_Reihe_To_Feld('c',1)) then // grosse weisse Rochade

RueckgabeSpeicher := FigurVerschieben(Schachbrett,Von_Nach_To_Zug(Linie_Reihe_To_Feld('a',1),Linie_Reihe_To_Feld('d',1))); // Turm von a1 nach d1 verschieben

ix

Rochade_Ausfuehren := RueckgabeSpeicher; end;

function Bauernumwandlung(Schachbrett:TSchachbrett;Zug:TZug):TSchachbrett; // verwandelt den Bauern auf dem Zielfeld in eine Dame gleicher Farbe begin

Schachbrett.Feld[Zug.Nach.Linie,Zug.Nach.Reihe] := Schachbrett.Feld[Zug.Nach.Linie,Zug.Nach.Reihe] + 8; // Figurenwert + 8 macht aus einem Bauer eine Dame gleicher Farbe Bauernumwandlung := Schachbrett; end;

function Spieler_am_Zug_tauschen(Schachkonstellation:TSchachkonstellation):TSchachkonstellation; begin // Tauscht den Spieler, der am Zug ist (für die Funktion GueltigerZug benötigt) if Schachkonstellation.Spieler_am_Zug = 'w' then

Schachkonstellation.Spieler_am_Zug := 's' else

Schachkonstellation.Spieler_am_Zug := 'w'; Spieler_am_Zug_tauschen := Schachkonstellation; end;

function ZugAusfuehren(Schachkonstellation:TSchachkonstellation;Zug:TZug):TSchachkonstellation; // führt den zuvor auf Gültigkeit überprüften Zug aus, aktualisiert alle sonderzugsrelevanten Parameter, Königspositionen, wer am Zug ist etc. var

RueckgabeSpeicher: TSchachkonstellation; begin

RueckgabeSpeicher := Schachkonstellation;

RueckgabeSpeicher.Schachbrett := FigurVerschieben(Schachkonstellation.Schachbrett,Zug); // führt den übergebenen Zug aus

if (Schachkonstellation.Schachbrett.Feld[Zug.Von.Linie,Zug.Von.Reihe] > 10) and (abs(Linie_To_Zahl(Zug.Nach.Linie) - Linie_To_Zahl(Zug.Von.Linie)) = 2) then // wenn ein König zwei Felder seitlich bewegt wurde

RueckgabeSpeicher.Schachbrett := Rochade_Ausfuehren(RueckgabeSpeicher.Schachbrett,Zug); // dann wird eine Rochade ausgeführt (der Turm bewegt) if (Schachkonstellation.Schachbrett.Feld[Zug.Von.Linie,Zug.Von.Reihe] < 3) and (abs(Linie_To_Zahl(Zug.Nach.Linie) - Linie_To_Zahl(Zug.Von.Linie)) = 1) and (Schachkonstellation.Schachbrett.Feld[Zug.Nach.Linie,Zug.Nach.Reihe] = 0) then // wenn ein Bauer diagonal auf ein leeres Feld bewegt wurde

RueckgabeSpeicher.Schachbrett := en_passant_ausfuehren(RueckgabeSpeicher.Schachbrett,Zug); // dann lösche den en passant geschlagenen Bauern if (Schachkonstellation.Schachbrett.Feld[Zug.Von.Linie,Zug.Von.Reihe] < 3) and ((Zug.Nach.Reihe = 1) or (Zug.Nach.Reihe = 8)) then // wenn ein Bauer auf eine Grundreihe gezogen wird

RueckgabeSpeicher.Schachbrett := Bauernumwandlung(RueckgabeSpeicher.Schachbrett,Zug); // dann verwandle ihn in eine Dame if Felder_gleich(Zug.Von,Linie_Reihe_To_Feld('a',8)) // wenn das Startfeld A8 ist then

RueckgabeSpeicher.RochadeSpeicher[1] := '1'; // dann wird der Rochadespeicher für diesen Turm auf 1 (bewegt) gesetzt if Felder_gleich(Zug.Von,Linie_Reihe_To_Feld('e',8)) // wenn das Startfeld E8 ist then

RueckgabeSpeicher.RochadeSpeicher[2] := '1'; // dann wird der Rochadespeicher für diesen König auf 1 (bewegt) gesetzt if Felder_gleich(Zug.Von,Linie_Reihe_To_Feld('h',8)) // wenn das Startfeld H8 ist then

RueckgabeSpeicher.RochadeSpeicher[3] := '1'; // dann wird der Rochadespeicher für diesen Turm auf 1 (bewegt) gesetzt if Felder_gleich(Zug.Von,Linie_Reihe_To_Feld('a',1)) // wenn das Startfeld A1 ist then

RueckgabeSpeicher.RochadeSpeicher[4] := '1'; // dann wird der Rochadespeicher für diesen Turm auf 1 (bewegt) gesetzt if Felder_gleich(Zug.Von,Linie_Reihe_To_Feld('e',1)) // wenn das Startfeld E1 ist then

RueckgabeSpeicher.RochadeSpeicher[5] := '1'; // dann wird der Rochadespeicher für diesen König auf 1 (bewegt) gesetzt if Felder_gleich(Zug.Von,Linie_Reihe_To_Feld('h',1)) // wenn das Startfeld H1 ist then

RueckgabeSpeicher.RochadeSpeicher[6] := '1'; // dann wird der Rochadespeicher für diesen Turm auf 1 (bewegt) gesetzt { RochadeSpeicher: 1. Stelle - schwarzer Turm auf A8 2. Stelle - schwarzer König auf E8 3. Stelle - schwarzer Turm auf H8 4. Stelle - weisser Turm auf A1 5. stelle - weisser König auf E1 6. Stelle - weisser Turm auf H1 }

RueckgabeSpeicher.en_passant_moeglich := 0;

if (Schachkonstellation.Schachbrett.Feld[Zug.Von.Linie,Zug.Von.Reihe] < 3) and (abs(Zug.Nach.Reihe - Zug.Von.Reihe) = 2) then // wenn ein Bauer zwei Felder nach vorne gezogen wurde begin if Zug.Von.Linie <> 'a'

then // wenn der Bauer nicht auf der Linie a gezogen wurde

if ((RueckgabeSpeicher.Schachbrett.Feld[pred(Zug.Nach.Linie),Zug.Nach.Reihe] = 1) and (RueckgabeSpeicher.Schachbrett.Feld[Zug.Nach.Linie,Zug.Nach.Reihe] = 2)) or ((RueckgabeSpeicher.Schachbrett.Feld[pred(Zug.Nach.Linie),Zug.Nach.Reihe] = 2) and (RueckgabeSpeicher.Schachbrett.Feld[Zug.Nach.Linie,Zug.Nach.Reihe] = 1)) then // wenn links neben dem Zielfeld des gezogenen Bauern ein gegnerischer Bauer steht begin

nämlich diese:

Linie_Reihe_To_Feld(Zug.Nach.Linie,(Zug.Nach.Reihe + Zug.Von.Reihe) div 2));

x

end; if Zug.Von.Linie <> 'h'

then // wenn der Bauer nicht auf der Linie h gezogen wurde

if ((RueckgabeSpeicher.Schachbrett.Feld[succ(Zug.Nach.Linie),Zug.Nach.Reihe] = 1) and (RueckgabeSpeicher.Schachbrett.Feld[Zug.Nach.Linie,Zug.Nach.Reihe] = 2)) or ((RueckgabeSpeicher.Schachbrett.Feld[succ(Zug.Nach.Linie),Zug.Nach.Reihe] = 2) and (RueckgabeSpeicher.Schachbrett.Feld[Zug.Nach.Linie,Zug.Nach.Reihe] = 1)) then // wenn rechts neben dem Zielfeld des gezogenen Bauern ein gegnerischer Bauer steht begin

nämlich diese:

Zug.Nach.Reihe),Linie_Reihe_To_Feld(Zug.Nach.Linie,(Zug.Nach.Reihe + Zug.Von.Reihe) div 2))

else

RueckgabeSpeicher.en_passant_Zug2 := Von_Nach_To_Zug(Linie_Reihe_To_Feld(succ(Zug.Nach.Linie), Zug.Nach.Reihe),Linie_Reihe_To_Feld(Zug.Nach.Linie,(Zug.Nach.Reihe + Zug.Von.Reihe) div 2)); end; end;

if Schachkonstellation.Schachbrett.Feld[Zug.Von.Linie,Zug.Von.Reihe] = 11 then // wenn der schwarze König gezogen wurde

RueckgabeSpeicher.Schachbrett.Pos_schwarzer_Koenig := Zug.Nach; // dann wird dessen Position aktualisiert if Schachkonstellation.Schachbrett.Feld[Zug.Von.Linie,Zug.Von.Reihe] = 12 then // wenn der weisse König gezogen wurde

RueckgabeSpeicher.Schachbrett.Pos_weisser_Koenig := Zug.Nach; // dann wird dessen Position aktualisiert RueckgabeSpeicher := Spieler_am_Zug_tauschen(RueckgabeSpeicher); ZugAusfuehren := RueckgabeSpeicher; end;

function RochadeArt(Zug:TZug):Byte; // Ordnet einem Königszug die entsprechende Rochade zu var RueckgabeSpeicher: Byte; // 0: kein Rochadezug, 1: kleine schwarze, 2: kleine weisse, 3: grosse schwarze, 4: grosse weisse begin RueckgabeSpeicher := 0;

if Zuege_gleich(Zug,Von_Nach_To_Zug(Linie_Reihe_To_Feld('e',8),Linie_Reihe_To_Feld('g',8))) then RueckgabeSpeicher := 1;

if Zuege_gleich(Zug,Von_Nach_To_Zug(Linie_Reihe_To_Feld('e',1),Linie_Reihe_To_Feld('g',1))) then RueckgabeSpeicher := 2;

if Zuege_gleich(Zug,Von_Nach_To_Zug(Linie_Reihe_To_Feld('e',8),Linie_Reihe_To_Feld('c',8))) then RueckgabeSpeicher := 3;

if Zuege_gleich(Zug,Von_Nach_To_Zug(Linie_Reihe_To_Feld('e',1),Linie_Reihe_To_Feld('c',1))) then RueckgabeSpeicher := 4; RochadeArt := RueckgabeSpeicher; end;

function GueltigerZug(Schachkonstellation:TSchachkonstellation;Zug:TZug):Boolean; begin

if ((Schachkonstellation.Spieler_am_Zug = 'w') and (weisse_Figur(Schachkonstellation.Schachbrett,Linie_Reihe_To_Feld(Zug.Von.Linie,Zug.Von.Reihe)))) or ((Schachkonstellation.Spieler_am_Zug = 's') and (schwarze_Figur(Schachkonstellation.Schachbrett,Linie_Reihe_To_Feld(Zug.Von.Linie,Zug.Von.Reihe)))) then // wenn die Figur mit der gezogen werden soll zu der Farbe gehört, die am Zug ist if GueltigerZugOhneSchach(Schachkonstellation.Schachbrett,Zug)

then // wenn der Zug ein gültiger normaler Zug ohne Berücksichtigung von Sonderzügen ist

GueltigerZug := not Schach(Spieler_am_Zug_tauschen(ZugAusfuehren(Schachkonstellation,Zug))) // dann ist die Gültigkeit des Zuges davon abhängig, ob der Spieler seinen eigenen König mit dem Zug einer Bedrohung aussetzt else // kein gültiger Zug ohne Berücksichtigung von Rochade und en passant

if (Schachkonstellation.Schachbrett.Feld[Zug.Von.Linie,Zug.Von.Reihe] > 10) and (abs(Linie_To_Zahl(Zug.Nach.Linie) -Linie_To_Zahl(Zug.Von.Linie)) = 2) then // König zwei seitlich bewegt?

GueltigerZug := Rochade_gueltig(Schachkonstellation,RochadeArt(Zug)) // gültig wenn der Königszug einer Rochade entspricht und diese gültig ist

else // kein gültiger Zug ohne Berücksichtigung von en passant

if (Schachkonstellation.Schachbrett.Feld[Zug.Von.Linie,Zug.Von.Reihe] < 3) and (abs(Linie_To_Zahl(Zug.Nach.Linie) -Linie_to_Zahl(Zug.Von.Linie)) = 1) and (Schachkonstellation.Schachbrett.Feld[Zug.Nach.Linie,Zug.Nach.Reihe] = 0) then // Bauer diagonal auf leeres Feld bewegt?

davon abhängig, ob der Spieler seinen eigenen König mit dem Zug einer Bedrohung aussetzt

else // sonst ungültiger Zug

else // Spieler nicht am Zug

GueltigerZug := False; end;

function Matt(Schachkonstellation:TSchachkonstellation):Boolean; // Liefert True zurück, wenn der Spieler am Zug matt ist, sonst False var

LinienZaehler1,LinienZaehler2: Char; ReihenZaehler1,ReihenZaehler2: Byte;

xi

RueckgabeSpeicher: Boolean; begin

RueckgabeSpeicher := Schach(Schachkonstellation); // Ist der König bedroht?

LinienZaehler1 := 'a'; // verschachtelte while-Schleifen, um einen vorzeitigen Abbruch zu ermöglichen while (RueckgabeSpeicher) and (LinienZaehler1 < 'i') do // für alle Linien begin ReihenZaehler1 := 1;

while (RueckgabeSpeicher) and (ReihenZaehler1 < 9) do // für alle Reihen begin LinienZaehler2 := 'a';

while (RueckgabeSpeicher) and (LinienZaehler2 < 'i') do // für alle Linien begin ReihenZaehler2 := 1;

while (RueckgabeSpeicher) and (ReihenZaehler2 < 9) do // für alle Reihen

Linie_Reihe_To_Feld(LinienZaehler2,ReihenZaehler2)))

inc(LinienZaehler2);

end; inc(ReihenZaehler1); end; inc(LinienZaehler1); end;

// ist RueckgabeSpeicher nach diesen Schleifen immer noch True, dann ist der Spieler matt Matt := RueckgabeSpeicher; end;

function Patt(Schachkonstellation:TSchachkonstellation):Boolean; // Liefert True zurück, wenn der Spieler am Zug patt ist, sonst False var

LinienZaehler1,LinienZaehler2: Char; ReihenZaehler1,ReihenZaehler2: Byte; RueckgabeSpeicher: Boolean; begin

RueckgabeSpeicher := not Schach(Schachkonstellation); // Ist der König nicht bedroht? LinienZaehler1 := 'a'; // verschachtelte while-Schleifen, um einen vorzeitigen Abbruch zu ermöglichen while (RueckgabeSpeicher) and (LinienZaehler1 < 'i') do // für alle Linien begin ReihenZaehler1 := 1;

while (RueckgabeSpeicher) and (ReihenZaehler1 < 9) do // für alle Reihen begin LinienZaehler2 := 'a';

while (RueckgabeSpeicher) and (LinienZaehler2 < 'i') do // für alle Linien begin ReihenZaehler2 := 1;

while (RueckgabeSpeicher) and (ReihenZaehler2 < 9) do // für alle Reihen begin // für alle erdenklichen Züge:

Linie_Reihe_To_Feld(LinienZaehler2,ReihenZaehler2))) then // dann nicht patt

inc(LinienZaehler2);

end; inc(ReihenZaehler1); end; inc(LinienZaehler1); end;

// ist RueckgabeSpeicher nach diesen Schleifen immer noch True, dann ist der Spieler patt

xii

Patt := RueckgabeSpeicher; end;

function MausPos_To_Feld(MausPos:TPoint):TFeld; // Errechnet aus der Mausposition das Feld, auf das geklickt wurde begin

if (MausPos.X >= (Screen.Width - Screen.Height) div 2) and (MausPos.X <= Screen.Height + (Screen.Width - Screen.Height) div 2) then

MausPos_To_Feld := Linie_Reihe_To_Feld(chr(ord('a') + ((MausPos.X - (Screen.Width - Screen.Height) div 2) div (Screen.Height div 8))), 8 - (MausPos.Y div (Screen.Height div 8)))

else // wenn nicht auf das Schachbrett geklickt wurde, wird x0 zurückgeliefert MausPos_To_Feld := Linie_Reihe_To_Feld('x',0); end;

function Schachbrett_To_ErweitertesSchachbrett(Schachbrett:TSchachbrett):TErweitertesSchachbrett; // Erweitert das übergebene Schachbrett um einen Rand (Felder mit dem Wert -1) var LinienZaehler: Char; ReihenZaehler: Byte; RueckgabeSpeicher: TErweitertesSchachbrett; begin

for LinienZaehler := 'a' to 'h' do for ReihenZaehler := 1 to 8 do

RueckgabeSpeicher.Feld[LinienZaehler,ReihenZaehler] := Schachbrett.Feld[LinienZaehler,ReihenZaehler]; for LinienZaehler := '`' to 'i' do RueckgabeSpeicher.Feld[LinienZaehler,0] := -1; for ReihenZaehler := 1 to 9 do RueckgabeSpeicher.Feld['i',ReihenZaehler] := -1; for LinienZaehler := 'h' downto '`' do RueckgabeSpeicher.Feld[LinienZaehler,9] := -1; for ReihenZaehler := 1 to 8 do RueckgabeSpeicher.Feld['`',ReihenZaehler] := -1; Schachbrett_To_ErweitertesSchachbrett := RueckgabeSpeicher; end;

function materielle_Bewertung(Schachbrett:TSchachbrett):Integer; // summiert die Figurenwerte der auf dem übergebenen Schachbrett stehenden Figuren auf var LinienZaehler: Char; ReihenZaehler: Byte; RueckgabeSpeicher: Integer; begin RueckgabeSpeicher := 0; for LinienZaehler := 'a' to 'h' do for ReihenZaehler := 1 to 8 do case Schachbrett.Feld[LinienZaehler,ReihenZaehler] of 1: RueckgabeSpeicher := RueckgabeSpeicher - BAUER; 2: RueckgabeSpeicher := RueckgabeSpeicher + BAUER; 3: RueckgabeSpeicher := RueckgabeSpeicher - TURM; 4: RueckgabeSpeicher := RueckgabeSpeicher + TURM; 5: RueckgabeSpeicher := RueckgabeSpeicher - SPRINGER; 6: RueckgabeSpeicher := RueckgabeSpeicher + SPRINGER; 7: RueckgabeSpeicher := RueckgabeSpeicher - LAEUFER; 8: RueckgabeSpeicher := RueckgabeSpeicher + LAEUFER; 9: RueckgabeSpeicher := RueckgabeSpeicher - DAME; 10: RueckgabeSpeicher := RueckgabeSpeicher + DAME; end;

materielle_Bewertung := RueckgabeSpeicher; end;

function positionelle_Bewertung(Schachbrett:TSchachbrett):Integer; // bewertet Die Figurenkonstellation anhand einiger Kriterien var

LinienZaehler,LinienZaehler2: Char; ReihenZaehler,ReihenZaehler2: Byte; RueckgabeSpeicher: Integer; angrenzende_Linien_frei: Boolean; ErweitertesBrett:TErweitertesSchachbrett; begin RueckgabeSpeicher := 0; for LinienZaehler := 'a' to 'h' do for ReihenZaehler := 1 to 8 do case Schachbrett.Feld[LinienZaehler,ReihenZaehler] of 1: begin // schwarzer Bauer

RueckgabeSpeicher := RueckgabeSpeicher - BAUERFORTSCHRITT*(7 - ReihenZaehler); // Bauernfortschritt für schwarz angrenzende_Linien_frei := True; for ReihenZaehler2 := 1 to 8 do

if (angrenzende_Linien_frei) and (LinienZaehler <> 'a')

if (angrenzende_Linien_frei) and (LinienZaehler <> 'h') then

if angrenzende_Linien_frei

then

RueckgabeSpeicher := RueckgabeSpeicher - FREIBAUER; // Freibauer für schwarz if Schachbrett.Feld[LinienZaehler,pred(ReihenZaehler)] = 1 then

RueckgabeSpeicher := RueckgabeSpeicher + DOPPELBAUER; // Doppelbauer für schwarz if (LinienZaehler = 'a') or (LinienZaehler = 'h') then

RueckgabeSpeicher := Rueckgabespeicher + RANDBAUER; // Randbauer für schwarz if (LinienZaehler > 'a') and (ReihenZaehler > 2)

if (LinienZaehler < 'h') and (ReihenZaehler > 2)

then

end;

2: begin // weisser Bauer

RueckgabeSpeicher := RueckgabeSpeicher + BAUERFORTSCHRITT*(ReihenZaehler - 2); // Bauernfortschritt für weiss angrenzende_Linien_frei := True; for ReihenZaehler2 := 1 to 8 do

if (angrenzende_Linien_frei) and (LinienZaehler <> 'a')

then

if (angrenzende_Linien_frei) and (LinienZaehler <> 'h')

then

if angrenzende_Linien_frei

then

RueckgabeSpeicher := RueckgabeSpeicher + FREIBAUER; // Freibauer für weiss if Schachbrett.Feld[LinienZaehler,succ(ReihenZaehler)] = 2 then

RueckgabeSpeicher := RueckgabeSpeicher - DOPPELBAUER; // Doppelbauer für weiss if (LinienZaehler = 'a') or (LinienZaehler = 'h') then

RueckgabeSpeicher := Rueckgabespeicher - RANDBAUER; // Randbauer für weiss if (LinienZaehler > 'a') and (ReihenZaehler < 7) then

if (LinienZaehler < 'h') and (ReihenZaehler < 7)

then

end;

3: begin // schwarzer Turm for LinienZaehler2 := pred(LinienZaehler) to 'a' do

if (Schachbrett.Feld[LinienZaehler2,ReihenZaehler] = 3) and Kollisionsfrei(Schachbrett,Von_Nach_To_Zug(Linie_Reihe_To_Feld (LinienZaehler,ReihenZaehler),Linie_Reihe_To_Feld(LinienZaehler2,ReihenZaehler))) then

RueckgabeSpeicher := RueckgabeSpeicher - TURMPAAR; // Turmpaar auf offener Reihe für schwarz for ReihenZaehler2 := succ(ReihenZaehler) to 8 do

if (Schachbrett.Feld[LinienZaehler,ReihenZaehler2] = 3) and Kollisionsfrei(Schachbrett,Von_Nach_To_Zug(Linie_Reihe_To_Feld (LinienZaehler,ReihenZaehler),Linie_Reihe_To_Feld(LinienZaehler,ReihenZaehler2)))

end; 4: begin // weisser Turm

for LinienZaehler2 := pred(LinienZaehler) to 'a' do

if (Schachbrett.Feld[LinienZaehler2,ReihenZaehler] = 4) and Kollisionsfrei(Schachbrett,Von_Nach_To_Zug(Linie_Reihe_To_Feld (LinienZaehler,ReihenZaehler),Linie_Reihe_To_Feld(LinienZaehler2,ReihenZaehler))) then

RueckgabeSpeicher := RueckgabeSpeicher + TURMPAAR; // Turmpaar auf offener Reihe für weiss for ReihenZaehler2 := succ(ReihenZaehler) to 8 do

if (Schachbrett.Feld[LinienZaehler,ReihenZaehler2] = 4) and Kollisionsfrei(Schachbrett,Von_Nach_To_Zug(Linie_Reihe_To_Feld (LinienZaehler,ReihenZaehler),Linie_Reihe_To_Feld(LinienZaehler,ReihenZaehler2))) then

RueckgabeSpeicher := RueckgabeSpeicher + TURMPAAR; // Turmpaar auf offener Linie für weiss end;

5: begin // schwarzer Springer if (LinienZaehler = 'a') or (LinienZaehler = 'h') then

end;

6: begin // weisser Springer if (LinienZaehler = 'a') or (LinienZaehler = 'h') then

end;

7: begin // schwarzer Läufer if LinienZaehler > 'a' then

if ReihenZaehler > 1

then

end;

8: begin // weisser Läufer if LinienZaehler > 'a' then

if ReihenZaehler > 1

then

end;

9: begin // schwarze Dame for LinienZaehler2 := 'a' to 'h' do

if (LinienZaehler <> LinienZaehler2) and (Schachbrett.Feld[LinienZaehler2,ReihenZaehler] = 3) and

Kollisionsfrei(Schachbrett,Von_Nach_To_Zug(Linie_Reihe_To_Feld(LinienZaehler,ReihenZaehler),Linie_Reihe_To_Feld(LinienZaehler2,ReihenZaehler))) then

RueckgabeSpeicher := RueckgabeSpeicher - DAMETURMPAAR; // Dame-Turm-Paar auf offener Reihe für schwarz for ReihenZaehler2 := 1 to 8 do

if (ReihenZaehler <> ReihenZaehler2) and (Schachbrett.Feld[LinienZaehler,ReihenZaehler2] = 3) and

Kollisionsfrei(Schachbrett,Von_Nach_To_Zug(Linie_Reihe_To_Feld(LinienZaehler,ReihenZaehler),Linie_Reihe_To_Feld(LinienZaehler,ReihenZaehler2))) then

RueckgabeSpeicher := RueckgabeSpeicher - DAMETURMPAAR; // Dame-Turm-Paar auf offener Linie für schwarz if ReihenZaehler <> 8

ErweitertesBrett := Schachbrett_To_ErweitertesSchachbrett(Schachbrett);

with ErweitertesBrett do

xv

if (Feld[pred(LinienZaehler),pred(ReihenZaehler)] = 0) or (Feld[pred(LinienZaehler),ReihenZaehler] = 0) or (Feld[LinienZaehler,pred(ReihenZaehler)] = 0) or (Feld[pred(LinienZaehler),succ(ReihenZaehler)] = 0) or (Feld[succ(LinienZaehler),pred(ReihenZaehler)] = 0) or (Feld[succ(LinienZaehler),ReihenZaehler] = 0) or (Feld[LinienZaehler,succ(ReihenZaehler)] = 0) or (Feld[succ(LinienZaehler),succ(ReihenZaehler)] = 0) then // mindestens ein Feld um die schwarze Dame ist leer RueckgabeSpeicher := RueckgabeSpeicher - DAMENBEWEGLICHKEIT; end; 10: begin // weisse Dame for LinienZaehler2 := 'a' to 'h' do

if (Schachbrett.Feld[LinienZaehler2,ReihenZaehler] = 4) and Kollisionsfrei(Schachbrett,Von_Nach_To_Zug(Linie_Reihe_To_Feld (LinienZaehler,ReihenZaehler),Linie_Reihe_To_Feld(LinienZaehler2,ReihenZaehler))) then

RueckgabeSpeicher := RueckgabeSpeicher + DAMETURMPAAR; // Dame-Turm-Paar auf offener Reihe für weiss for ReihenZaehler2 := 1 to 8 do

if (Schachbrett.Feld[LinienZaehler,ReihenZaehler2] = 4) and Kollisionsfrei(Schachbrett,Von_Nach_To_Zug(Linie_Reihe_To_Feld (LinienZaehler,ReihenZaehler),Linie_Reihe_To_Feld(LinienZaehler,ReihenZaehler2))) then

RueckgabeSpeicher := RueckgabeSpeicher + DAMETURMPAAR; // Dame-Turm-Paar auf offener Linie für weiss if ReihenZaehler <> 1

ErweitertesBrett := Schachbrett_To_ErweitertesSchachbrett(Schachbrett);

with ErweitertesBrett do

if (Feld[pred(LinienZaehler),pred(ReihenZaehler)] = 0) or (Feld[pred(LinienZaehler),ReihenZaehler] = 0) or (Feld[LinienZaehler,pred(ReihenZaehler)] = 0) or (Feld[pred(LinienZaehler),succ(ReihenZaehler)] = 0) or (Feld[succ(LinienZaehler),pred(ReihenZaehler)] = 0) or (Feld[succ(LinienZaehler),ReihenZaehler] = 0) or (Feld[LinienZaehler,succ(ReihenZaehler)] = 0) or (Feld[succ(LinienZaehler),succ(ReihenZaehler)] = 0) then // mindestens ein Feld um die weisse Dame ist leer RueckgabeSpeicher := RueckgabeSpeicher + DAMENBEWEGLICHKEIT; end; 11: begin // schwarzer König

ErweitertesBrett := Schachbrett_To_ErweitertesSchachbrett(Schachbrett); with ErweitertesBrett do

if (Feld[pred(LinienZaehler),pred(ReihenZaehler)] = 0) or (Feld[pred(LinienZaehler),ReihenZaehler] = 0) or (Feld[LinienZaehler,pred(ReihenZaehler)] = 0) or (Feld[pred(LinienZaehler),succ(ReihenZaehler)] = 0) or (Feld[succ(LinienZaehler),pred(ReihenZaehler)] = 0) or (Feld[succ(LinienZaehler),ReihenZaehler] = 0) or (Feld[LinienZaehler,succ(ReihenZaehler)] = 0) or (Feld[succ(LinienZaehler),succ(ReihenZaehler)] = 0) then // mindestens ein Feld um den schwarzen König ist leer RueckgabeSpeicher := RueckgabeSpeicher - KOENIGSBEWEGLICHKEIT; end; 12: begin // weisser König

ErweitertesBrett := Schachbrett_To_ErweitertesSchachbrett(Schachbrett); with ErweitertesBrett do

if (Feld[pred(LinienZaehler),pred(ReihenZaehler)] = 0) or (Feld[pred(LinienZaehler),ReihenZaehler] = 0) or (Feld[LinienZaehler,pred(ReihenZaehler)] = 0) or (Feld[pred(LinienZaehler),succ(ReihenZaehler)] = 0) or (Feld[succ(LinienZaehler),pred(ReihenZaehler)] = 0) or (Feld[succ(LinienZaehler),ReihenZaehler] = 0) or (Feld[LinienZaehler,succ(ReihenZaehler)] = 0) or (Feld[succ(LinienZaehler),succ(ReihenZaehler)] = 0) then // mindestens ein Feld um den weissen König ist leer RueckgabeSpeicher := RueckgabeSpeicher + KOENIGSBEWEGLICHKEIT; end; end;

positionelle_Bewertung := RueckgabeSpeicher; end;

function Raumbeherrschung(Schachbrett:TSchachbrett):Integer; // Liefert eine Zahl zurück, die etwas über das Verhältnis des beherrschten Raumes aussagt var

LinienZaehler,LinienZaehler2: Char; ReihenZaehler,ReihenZaehler2: Byte; RueckgabeSpeicher: Integer;

BeherrschungsArray: array['a'..'h',1..8] of ShortInt; begin

for LinienZaehler := 'a' to 'h' do for ReihenZaehler := 1 to 8 do if Schachbrett.Feld[LinienZaehler,ReihenZaehler] = 0 then

BeherrschungsArray[LinienZaehler,ReihenZaehler] := 0 // leere Felder erhalten den Wert 0 else

if Gerade(Schachbrett.Feld[LinienZaehler,ReihenZaehler]) then

BeherrschungsArray[LinienZaehler,ReihenZaehler] := 2 // von weissen Figuren belegte Felder erhalten den Wert 2 else

BeherrschungsArray[LinienZaehler,ReihenZaehler] := -2; // von schwarzen Figuren belegte Felder erhalten den Wert -2 for LinienZaehler := 'a' to 'h' do for ReihenZaehler := 1 to 8 do if Schachbrett.Feld[LinienZaehler,ReihenZaehler] <> 0

then // verbessert die Laufzeit etwas (weniger Aufrufe der Funktion GueltigerZugOhneSchach) for LinienZaehler2 := 'a' to 'h' do

for ReihenZaehler2 := 1 to 8 do // für alle erdenklichen Züge

if GueltigerZugOhneSchach(Schachbrett,Von_Nach_To_Zug(Linie_Reihe_To_Feld(LinienZaehler,ReihenZaehler), Linie_Reihe_To_Feld(LinienZaehler2,ReihenZaehler2))) and (Schachbrett.Feld[LinienZaehler2,ReihenZaehler2] = 0)

RueckgabeSpeicher := 0; for LinienZaehler := 'a' to 'h' do for ReihenZaehler := 1 to 8 do // Auswertung des Arrays

if ((LinienZaehler = 'd') or (LinienZaehler = 'e')) and ((ReihenZaehler = 4) or (ReihenZaehler = 5)) then // zentrale Felder werden stärker gewichtet

RueckgabeSpeicher := RueckgabeSpeicher + GEWICHTUNGSFAKTOR_ZENTRALE_FELDER*BeherrschungsArray[LinienZaehler,ReihenZaehler]*FELDBEHERRSCHUNG else // alle anderen Felder werden normal gewichtet

RueckgabeSpeicher := RueckgabeSpeicher + BeherrschungsArray[LinienZaehler,ReihenZaehler]*FELDBEHERRSCHUNG; Raumbeherrschung := RueckgabeSpeicher; end;

function Bewertung(Schachkonstellation:TSchachkonstellation):Integer; // fasst die Bewertungsfunktionen zusammen begin if Matt(Schachkonstellation) then // matt

if Schachkonstellation.Spieler_am_Zug = 'w' then // weiss matt Bewertung := - MATTBEWERTUNG else // schwarz matt Bewertung := MATTBEWERTUNG else if Patt(Schachkonstellation) then // patt Bewertung := 0 else // weder matt noch patt with Schachkonstellation do

Bewertung := materielle_Bewertung(Schachbrett) + positionelle_Bewertung(Schachbrett) + Raumbeherrschung(Schachbrett); end;

function BesterZug(Schachkonstellation:TSchachkonstellation;Tiefe:Byte):Integer; // Das Herz der KI, wendet den Minimax-Algorithmus an var

BewertungBesterZug, BewertungPruefZug: Integer; // Der Wert des in diesem Funktionsaufruf bisher besten gefundenen Zuges für den jeweiligen Spieler wird zwischengespeichert LinienZaehler, LinienZaehler2: Char; ReihenZaehler, ReihenZaehler2: Byte; begin if (Tiefe = Max_Tiefe) then // wenn die maximale Tiefe erreicht ist

BesterZug := Bewertung(Schachkonstellation) // dann wird dieses Blatt bewertet (Rekursionsanfang) else // sonst wird es wie ein Knoten behandelt, ausser es liegt ein Matt oder Patt vor begin

if Schachkonstellation.Spieler_am_Zug = 'w' then // wenn weiss am Zug ist

BewertungBesterZug := - succ(MATTBEWERTUNG) // dann wird vorläufig ein so schlechter Wert zugewiesen, dass dieser niemals erreicht werden kann else // das gleiche für schwarz BewertungBesterZug := succ(MATTBEWERTUNG); for LinienZaehler := 'a' to 'h' do for ReihenZaehler := 1 to 8 do // für alle Felder

if (Gerade(Schachkonstellation.Schachbrett.Feld[LinienZaehler,ReihenZaehler]) and

(Schachkonstellation.Schachbrett.Feld[LinienZaehler,ReihenZaehler] <> 0) and (Schachkonstellation.Spieler_am_Zug = 'w')) or (not (Gerade(Schachkonstellation.Schachbrett.Feld[LinienZaehler,ReihenZaehler])) and (Schachkonstellation.Spieler_am_Zug = 's')) then // verbessert die Laufzeit etwas (weniger Aufrufe der Funktion GueltigerZug)

Linie_Reihe_To_Feld(LinienZaehler2,ReihenZaehler2)))

(LinienZaehler,ReihenZaehler),Linie_Reihe_To_Feld(LinienZaehler2,ReihenZaehler2))),succ(Tiefe));

((Schachkonstellation.Spieler_am_Zug = 's') and (BewertungPruefZug < BewertungBesterZug))

sondern auch dieser Zug. Damit dieser Zug nicht verloren geht, muss er global gespeichert werden.

Linie_Reihe_To_Feld(LinienZaehler2,ReihenZaehler2));

if abs(BewertungBesterZug) = succ(MATTBEWERTUNG) // wenn kein gültiger Zug gefunden wurde

then // dann wird die Bewertung dieses Blattes zurückgegeben (der Spieler am Zug ist matt oder patt) BesterZug := Bewertung(Schachkonstellation)

else // sonst wird die Bewertung des ermittelten besten Zuges für diesen Spieler zurückgegeben BesterZug := BewertungBesterZug end; end;

xvii

procedure Zeigerkette_Initialisieren; // Initialisiert eine neue Zeigerkette für eine neue Partie begin

new(MomentanePartieKonstellation);

MomentanePartieKonstellation.Konstellation := Grundstellung; MomentanePartieKonstellation.VorherigeKonstellation := nil; end;

procedure Neue_Partie; // blendet die Anzeigeoptionen für eine neue Partie ein und sperrt die Zugeingabe begin with SchachForm do begin

NeuePartieLabel.Visible := False; RueckgaengigLabel.Visible := False; MoeglicheZuegeLabel.Visible := False; KlickImage.Visible := False; SpielerGegenSpielerLabel.Visible := True; SpielerGegenComputerLabel.Visible := True; end; end;

procedure MessageAusgabe(AusgabeString:String;Loeschen:Boolean;Zeit:Cardinal); // gibt die als String übergebene Meldung aus begin with SchachForm do begin

AusgabeLoeschenTimer.Enabled := False; AusgabeLoeschenTimer.Interval := Zeit; with SchachbrettImage.Canvas do begin Pen.Color := HINTERGRUNDFARBE; Brush.Color := HINTERGRUNDFARBE; Font.Color := clWhite;

Rectangle(20,20,(Screen.Width - Screen.Height) div 2,40); // löscht den Ausgabebereich TextOut(20,20,AusgabeString); // gibt die Meldung aus end;

AusgabeLoeschenTimer.Enabled := Loeschen; // Ist Loeschen True, dann wird die Meldung nach der übergebenen Zeit wieder gelöscht end; end;

procedure Zug_rueckgaengig_machen; // Macht den letzten Halbzug rückgängig begin;

if MomentanePartieKonstellation.VorherigeKonstellation <> nil // wenn sich die Partie nicht in der Grundstellung befindet then begin

MomentanePartieKonstellation := MomentanePartieKonstellation.VorherigeKonstellation; // Halbzug rückgangig machen Schachbrett_Zeichnen(MomentanePartieKonstellation.Konstellation.Schachbrett);

MessageAusgabe('Ein Halbzug zurück',True,1000); // Gibt die Meldung aus, dass ein Halbzug zurückgenommen wurde end

else // Fehlermeldung wenn die Partie sich in der Grundstellung befindet MessageAusgabe('Grundstellung!',True,1000); end;

procedure Zwei_Zuege_rueckgaengig_machen; // Macht die letzten zwei Halbzüge rückgängig begin;

if (MomentanePartieKonstellation.VorherigeKonstellation <> nil) and (MomentanePartieKonstellation.VorherigeKonstellation.VorherigeKonstellation <> nil) // wenn mindestens zwei Züge seit der Grundstellung getätigt wurden then begin

MomentanePartieKonstellation := MomentanePartieKonstellation.VorherigeKonstellation.VorherigeKonstellation; // zwei Halbzüge rückgangig machen

Schachbrett_Zeichnen(MomentanePartieKonstellation.Konstellation.Schachbrett);

MessageAusgabe('Zwei Halbzüge zurück',True,1000); // Gibt die Meldung aus, dass zwei Halbzüg zurückgenommen wurden end

else // Fehlermeldung wenn die Partie sich in der Grundstellung befindet MessageAusgabe('Grundstellung!',True,1000); end;

procedure ZugAusgeben(Zug:TZug); // Erweitert die Zeigerkette der aktuellen Partie und zeichnet das neue Schachbrett var

NeuerPartieKonstellationAnker: TPartieZeiger; // Zur Erweiterung der Zeigerkette begin

xviii

new(NeuerPartieKonstellationAnker); // Zeigerkette erweitern

NeuerPartieKonstellationAnker.Konstellation := ZugAusfuehren(MomentanePartieKonstellation.Konstellation,Zug); NeuerPartieKonstellationAnker.VorherigeKonstellation := MomentanePartieKonstellation; MomentanePartieKonstellation := NeuerPartieKonstellationAnker;

Schachbrett_Zeichnen(MomentanePartieKonstellation.Konstellation.Schachbrett); // Neues Schachbrett ausgeben

MessageAusgabe(Feld_To_FeldString(Zug.Von) + ' --> ' + Feld_To_FeldString(Zug.Nach),True,5000); // ausgeführten Zug fünf Sekunden lang ausgeben with SchachForm.SchachbrettImage.Canvas do begin Font.Color := clWhite; Brush.Color := HINTERGRUNDFARBE; if Matt(MomentanePartieKonstellation.Konstellation) then // wenn ein Matt vorliegt begin

SchachForm.KlickImage.Visible := False; // dann wird die Zugeingabe gesperrt if MomentanePartieKonstellation.Konstellation.Spieler_am_Zug = 'w' then // und ausgegeben dass das Spiel matt endet TextOut(20,60,'weiss ist matt') else

TextOut(20,60,'schwarz ist matt'); end else

if Patt(MomentanePartieKonstellation.Konstellation) then

begin // bei einem Patt entsprechend SchachForm.KlickImage.Visible := False;

if MomentanePartieKonstellation.Konstellation.Spieler_am_Zug = 'w' then

else

end

else // wenn kein Matt oder Patt vorliegt begin

if MomentanePartieKonstellation.Konstellation.Spieler_am_Zug = 'w' then // dann wird ausgegeben wer am Zug ist TextOut(20,60,'weiss ist am Zug')

else if Schach(MomentanePartieKonstellation.Konstellation) then // und ob ein Schachgebot vorliegt TextOut(20,80,'Schach!'); end; end; end;

procedure PartieBeginn; // blendet die Optionen für eine neue Partie aus und aktiviert die Zugeingabe begin Zeigerkette_Initialisieren; with Schachform do begin

SpielerGegenSpielerLabel.Visible := False; SpielerGegenComputerLabel.Visible := False; EinfachLabel.Visible := False; MittelLabel.Visible := False; SchwerLabel.Visible := False; KlickImage.Visible := True; NeuePartieLabel.Visible := True; RueckgaengigLabel.Visible := True; MoeglicheZuegeLabel.Visible := True; end; end;

procedure TSchachForm.FormCreate(Sender: TObject); begin Top := 0; Left := 0;

Height := Screen.Height; // Vollbild Width := Screen.Width; SchachbrettImage.Height := Height; SchachbrettImage.Width := Width; KlickImage.Height := Height; KlickImage.Width := Height; KlickImage.Left := (Width - Height) div 2;

xix

// Komponentenpositionen an die Bildschirmauflösung anpassen NeuePartieLabel.Top := 20;

NeuePartieLabel.Left := Width - NeuePartieLabel.Width - ((Width - Height) div 2 - NeuePartieLabel.Width) div 2; RueckgaengigLabel.Top := 60;

RueckgaengigLabel.Left := Width - RueckgaengigLabel.Width - ((Width - Height) div 2 - RueckgaengigLabel.Width) div 2; MoeglicheZuegeLabel.Top := 100;

MoeglicheZuegeLabel.Left := Width - MoeglicheZuegeLabel.Width - ((Width - Height) div 2 - MoeglicheZuegeLabel.Width) div 2; SpielerGegenSpielerLabel.Top := 20;

SpielerGegenSpielerLabel.Caption := 'Spieler' + chr(13) + 'gegen' + chr(13) + 'Spieler ';

SpielerGegenSpielerLabel.Left := Width - SpielerGegenSpielerLabel.Width - ((Width - Height) div 2 - SpielerGegenSpielerLabel.Width) div 2; SpielerGegenComputerLabel.Top := 100;

SpielerGegenComputerLabel.Caption := 'Spieler' + chr(13) + 'gegen' + chr(13) + 'Computer ';

SpielerGegenComputerLabel.Left := Width - SpielerGegenComputerLabel.Width - ((Width - Height) div 2 - SpielerGegenComputerLabel.Width) div 2; EinfachLabel.Top := 20;

EinfachLabel.Left := Width - EinfachLabel.Width - ((Width - Height) div 2 - EinfachLabel.Width) div 2; MittelLabel.Top := 60;

MittelLabel.Left := Width - MittelLabel.Width - ((Width - Height) div 2 - MittelLabel.Width) div 2; SchwerLabel.Top := 100;

SchwerLabel.Left := Width - SchwerLabel.Width - ((Width - Height) div 2 - SchwerLabel.Width) div 2; InfoLabel.Top := Height - InfoLabel.Height - 20;

InfoLabel.Left := Width - InfoLabel.Width - ((Width - Height) div 2 - InfoLabel.Width) div 2; InformationenRichEdit.Left := Width div 2 - InformationenRichEdit.Width div 2; InformationenRichEdit.Top := Height div 2 - InformationenRichEdit.Height div 2; BilderAnzahl := 0; // bisher keine Instanzen von TImage erzeugt Zeigerkette_Initialisieren; Neue_Partie;

Schachbrett_Zeichnen(MomentanePartieKonstellation.Konstellation.Schachbrett); // Zeichnet die initialisierte Grundstellung Startfeld_festgelegt := False; // es wurde noch kein Startfeld eines Zuges gewählt end;

procedure TSchachForm.KlickImageClick(Sender: TObject); // Bei einem Klick auf das KlickImage wird das dadurch bestimmte Feld evtl. mit einem vorher bestimmten Feld zu einem Zug zusammengefügt und dann - wenn gültig - ausgeführt begin

if not Felder_gleich(MausPos_To_Feld(Mouse.CursorPos),Linie_Reihe_To_Feld('x',0)) then // wenn aufs Schachbrett geklickt wurde if Startfeld_festgelegt

then // wenn ein Startfeld schon vorher festgelegt wurde begin Startfeld_festgelegt := False;

Zielfeld := MausPos_To_Feld(Mouse.CursorPos); // dann wird jetzt das Zielfeld festgelegt

if GueltigerZug(MomentanePartieKonstellation.Konstellation,Von_Nach_To_Zug(Startfeld,Zielfeld)) // und zu einem Zug zusammengefügt, der auf seine Gültigkeit überprüft wird then // gültiger Zug

else // Fehlermeldung bei einem ungültigen Zug

MessageAusgabe('ungültiger Zug!',True,2000); end

else // wenn das Startfeld noch nicht festgelegt war begin Startfeld_festgelegt := True;

xx

Startfeld := MausPos_To_Feld(Mouse.CursorPos); // dann wird es jetzt festgelegt

MessageAusgabe(Feld_To_FeldString(Startfeld) + ' -->',False,1000); // und das festgelegte Startfeld ausgegeben end;

end;

procedure TSchachForm.AusgabeLoeschenTimerTimer(Sender: TObject); // löscht jeden zuvor ausgegeben Text im Ausgabebereich begin

SchachbrettImage.Canvas.Pen.Color := HINTERGRUNDFARBE; SchachbrettImage.Canvas.Brush.Color := HINTERGRUNDFARBE; SchachbrettImage.Canvas.Rectangle(20,20,(Screen.Width - Screen.Height) div 2,40); AusgabeLoeschenTimer.Enabled := False; end;

procedure TSchachForm.NeuePartieLabelClick(Sender: TObject); begin Neue_Partie;

Schachbrett_Zeichnen(Grundstellung.Schachbrett); MessageAusgabe('Neue Partie!',True,1000); end;

procedure TSchachForm.RueckgaengigLabelClick(Sender: TObject); // Zug rückgängig machen begin

if GegenComputer and ((MomentanePartieKonstellation.Konstellation.Spieler_am_Zug = 's') and (not (Matt(MomentanePartieKonstellation.Konstellation)))) and ((MomentanePartieKonstellation.Konstellation.Spieler_am_Zug = 's') and (not (Patt(MomentanePartieKonstellation.Konstellation))))

then // wenn gegen den Computer gespielt wird, müssen zwei Halbzüge rückgängig gemacht werden, ausser wenn schwarz matt oder patt ist , dann nur 1 Halbzug zurück (damit weiss am Zug ist) Zwei_Zuege_rueckgaengig_machen

else // bei Spieler gegen Spieler reicht immer ein Halbzug Zug_rueckgaengig_machen; KlickImage.Visible := True; end;

procedure TSchachForm.MoeglicheZuegeLabelClick(Sender: TObject); // gibt die möglichen Züge in einer einfachen algebraischen Notation aus var

Zuege, ReihenZaehler1, ReihenZaehler2: Byte; LinienZaehler1, LinienZaehler2: Char; begin

with SchachbrettImage.Canvas do begin Font.Color := clWhite; Brush.Color := HINTERGRUNDFARBE; TextOut(20,100,'mögliche Züge:'); Zuege := 0; for LinienZaehler1 := 'a' to 'h' do for ReihenZaehler1 := 1 to 8 do for LinienZaehler2 := 'a' to 'h' do for ReihenZaehler2 := 1 to 8 do

if GueltigerZug(MomentanePartieKonstellation.Konstellation,Von_Nach_To_Zug(Linie_Reihe_To_Feld(LinienZaehler1,ReihenZaehler1), Linie_Reihe_To_Feld(LinienZaehler2,ReihenZaehler2))) then

Feld_To_FeldString(Linie_Reihe_To_Feld(LinienZaehler2,ReihenZaehler2)));

inc(Zuege);

TextOut(20,120 + succ(Zuege)*12,'Anzahl: ' + IntToStr(Zuege)); // gibt die Anzahl der möglichen Zuge aus end; end;

// die nachfolgenden Prozeduren regeln die Wahl der neuen Partie (1. Spieler gegen Spieler 2. Spieler gegen Computer leicht 3. Spieler gegen Computer mittel 4. Spieler gegen Computer schwer) procedure TSchachForm.SpielerGegenSpielerLabelClick(Sender: TObject); begin GegenComputer := False; PartieBeginn; end;

procedure TSchachForm.SpielerGegenComputerLabelClick(Sender: TObject); begin GegenComputer := True;

xxi

SpielerGegenSpielerLabel.Visible := False; SpielerGegenComputerLabel.Visible := False; EinfachLabel.Visible := True; MittelLabel.Visible := True; SchwerLabel.Visible := True; end;

procedure TSchachForm.EinfachLabelClick(Sender: TObject); begin Max_Tiefe := 1; PartieBeginn; end;

procedure TSchachForm.MittelLabelClick(Sender: TObject); begin Max_Tiefe := 2; PartieBeginn; end;

procedure TSchachForm.SchwerLabelClick(Sender: TObject); begin Max_Tiefe := 3; PartieBeginn; end;

procedure TSchachForm.InfoLabelClick(Sender: TObject); begin

if InformationenRichEdit.Visible then

InformationenRichEdit.Visible := False else

InformationenRichEdit.Visible := True; end;

procedure TSchachForm.FormClose(Sender: TObject; var Action: TCloseAction); var Zaehler: Byte; begin

for Zaehler := 1 to BilderAnzahl do // Zur Laufzeit reservierten Speicherplatz freigeben Figurbild[Zaehler].Free; end;

procedure TSchachForm.FormKeyPress(Sender: TObject; var Key: Char); begin if Ord(Key) = 27 // bei ESC then

SchachForm.Close; // SchachForm schliessen end;

procedure TSchachForm.InformationenRichEditKeyPress(Sender: TObject; var Key: Char); begin if Ord(Key) = 27 // bei ESC then

SchachForm.Close; // SchachForm schliessen end; end.

xxii