spieltheoretische Betrachtung des Schachspiels, Software Engineering, ausführliche Dokumentation der Entwicklung und Implementierung einer Schachsoftware mit einer schwachen künstlichen Intelligenz, Borland Delphi Quelltext. Das Schachprogramm ist erreichbar unter: http://tinyurl.com/Schach
Inhaltsverzeichnis
1 Einleitung
1.1 Motivation
1.2 Aufbau
2 Schach
2.1 Geschichte
2.2 Grundlegendes
2.3 Spielende
2.3.1 Matt
2.3.2 Remis
2.4 Spieltheorie
3 Software Engineering
3.1 De nition
3.2 Vom Programm zur Software
3.3 Phasen der Softwareentwicklung
3.4 Programmfehler
4 Schachsoftware
4.1 Spezi kation
4.2 Systementwurf zu Teil 1
4.2.1 Die Datenstrukturen
4.2.1.1 Interne Brettdarstellung
4.2.1.2 Klassen, Records, globale Variablen .
4.2.2 Frontend
4.2.3 Zugregeln
4.2.3.1 Grundzüge
4.2.3.1.1 Turm
4.2.3.1.2 Läufer
4.2.3.1.3 Dame
4.2.3.1.4 König
4.2.3.1.5 Springer
4.2.3.1.6 Bauer
4.2.3.2 Kollisionsprüfung
4.2.3.3 Gültiger Zug ohne Schachberücksichtigung
4.2.3.4 En passant gültig
4.2.3.5 Rochade gültig
4.2.4 Wichtige Funktionen
4.2.4.1 Schach
4.2.4.2 Figur verschieben
4.2.4.3 En passant ausführen
4.2.4.4 Rochade ausführen
4.2.4.5 Bauernumwandlung
4.2.4.6 Zug ausführen
4.2.4.7 Gültiger Zug
4.2.4.8 Matt
4.2.4.9 Patt
4.2.5 Benutzersteuerung
4.2.5.1 Zugeingabe
4.2.5.2 Züge rückgängig machen
4.2.5.3 Mögliche Züge
4.3 Anmerkungen zur Implementierung von Teil 1
4.4 Systementwurf zu Teil 2
4.4.1 Bewertungsfunktionen
4.4.1.1 Materielle Bewertung
4.4.1.2 Positionelle Bewertung
4.4.1.3 Beherrschter Raum
4.4.1.4 Zusammenfassung zu einer Bewertungsfunktion
4.4.2 Spielbaumsuche mit dem Minimax-Algorithmus
4.5 Anmerkungen zur Implementierung von Teil 2
4.6 Die ersten Testpartien
4.7 Optimierung der Rechenzeit
4.8 Weitere Tests von Dritten
5 Nachwort
5.1 Zusammenfassung
5.2 Ausblick
5.3 Danksagung
5.4 Benutzte Programme
5.5 Literaturverzeichnis
5.6 Online-Verfügbarkeit
5.7 Erklärung
A Quelltext
Kapitel
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 Ent- wicklung und Implementierung eines Schachprogramms nachzudenken. Mit besseren Pro- grammierkenntnissen 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. Gleichzei- tig 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 projizie- ren 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 zufrie- denstellende Ergebnisse liefern würde, deshalb brachen wir das Projekt im Entwicklungs- stadium vorerst ab. Dennoch hat uns dieser Fehlschlag viel gebracht. Ich machte mir über ein halbes Jahr lang immer wieder Gedanken über die Datenstrukturen und zugrundelie- genden 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.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 Fachbegri e vermitteln. Auÿerdem soll eine Di erenzierung der Begri e 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 Ent- wicklung 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 be ndet 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.
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 hil os.[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 o ziellen Schachregeln des Weltschachverbandes FIDE (F é d é ration Internationale des É checs).
Doch schon zu dieser Zeit war ein wesentliches Merkmal gegeben, das wohl einen beträcht- lichen 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 e ektives 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 hinge- gen 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]
2.2 Grundlegendes
Schach wird von zwei Spielern auf einem 8x8 Felder groÿen Brett gespielt, dessen qua- dratische 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 Zi ern durchnummeriert, die senk- rechten Linien alphabetisch. So entspricht jedem Feld ein kartesisches Koordinatenpaar von a1 bis h8.
Die 8 Figuren1 (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 de nierte 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 geg- nerische 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 O zier (Turm, Springer, Läufer, Dame) umgewandelt werden, unabhängig von der auf dem Brett schon vorhandenen Anzahl an O zieren.
Im Folgenden werden auch die Bauern als Figuren bezeichnet, obwohl sie streng genommen als Steine bezeichnet werden müssten.
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 Zwischen- ziehen 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 be ndlicher Spieler bietet dem Kontrahenten ein Remis an, das ange- nommen 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.
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 klassi zieren. 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 getro enen Entscheidungen seines Gegenspielers (im Rahmen seines Erinnerungsvermögens) bekannt sind. [10]
Diese Klassi zierung 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 vorausge setzt. Dieser perfekte Zug lässt sich mithilfe des Minimax-Algorithmus ermitteln .2 Es ist eine sogenannte dominante Strategie, seine Züge mit dem Minimax-Algorithmus zu be- stimmen, denn die Minimax-Strategie garantiert das beste Ergebnis bei optimaler Spiel- weise des Gegners. Wenden beide Spieler zur Bestimmung ihrer Strategie den Minimax- Algorithmus an, dann bildet das Strategiepaar daher ein spezielles Nash-Gleichgewicht3 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 ausge- hend 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 Aus- sage darüber tre en, 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 * 1046 verschiedenen Stellungen bestehen. Auf dieser Schätzung basiert die Annahme, dass die Anzahl aller möglichen Spielverläufe in der Gröÿenordnung 10115 bis 10120 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 1080. [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 4 (also Schätz- und Erfahrungswerte sowie Faustregeln zur Bewertung von positionellen und ma- teriellen Vor- und Nachteilen und der Abwägung derselben). Anhand dieser approxima- tiven 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.
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 De nition
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 aufeinandertre en:
Abbildung in dieser Leseprobe nicht enthalten
Um diese Probleme beherrschbar zu machen, müssen wir uns zunächst klar machen, was Software eigentlich ist.
3.2 Vom Programm zur Software
Ein Programm ist ausführbares Wissen, das in Form von Daten (Bits) vorliegt. Es kann auf andere Daten (Eingabedaten) angewendet werden und diese entweder verändern, oder sie beibehalten und aus diesen neue Daten (Ausgabedaten) erzeugen. Dieses einfache Modell lässt sich also so darstellen:
Abbildung in dieser Leseprobe nicht enthalten
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 de nieren, 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 de nierten 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 aufbauend1, die abstrakteren, höheren Programmiersprachen, zum Beispiel Fortran, Lisp, Cobol, Pascal, C, Java, Perl oder Delphi. Alle Programmiersprachen haben - wie Sprachen allgemein - eine Syntax2 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 ge- schrieben 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 Eingabeda- ten interagiert, ein:
Abbildung in dieser Leseprobe nicht enthalten
Die Mittel3, 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
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 é 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 schritt- weise 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 ver- schiedenen Phasen feststellen, bei der Entwicklung von Software jedoch muss unbedingt eine klare Struktur und Phasenplanung vorhanden sein, da die Komplexität von Softwa- reentwicklung die von der Programmierung im Kleinen bei Weitem übersteigt und das Projekt somit ohne eine hinreichend detailliert geplante Vorgehensweise nicht zu handha- ben 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.
3.3 Phasen der Softwareentwicklung
Ein mögliches Modell ist die Einteilung der Softwareentwicklung in drei Phasen:
1. Problemanalyse, Anforderungsde nition (Spezi kation )
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 Anforde- rungsde nition, meist Spezi kation 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 er- bringen 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 Befol- gung der Bottom-Up-Methode durch Komponentenzerlegung gefunden wird. Es wird also festgelegt, wie die Software die in der ersten Phase spezi zierte Leistung erbringen soll. Das Ergebnis wird zunächst plattformunabhängig zum Beispiel mit der standardisierten Sprache zur Modellierung von Software UML (Uni ed 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 Pro- grammierung in einer geeigneten höheren Programmiersprache. Hier ist eine Verteilung der Aufgaben und die präzise Festlegung der Schnittstellen (API s) von gröÿter Wich- tigkeit, um die Funktionsfähigkeit und die Kommunikation der einzelnen, unabhängig voneinander (von verschiedenen Programmierern) programmierten Module bzw. Kompo- nenten 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 veri - ziert, sondern nur falsi zert werden kann: ein bestandener Test kann niemals die Abwe senheit von Fehlern beweisen.4 Es wurde lediglich kein Fehler gefunden. Die Korrektheit 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 emp ehlt 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 Spezi kation getestet wird.
Auf das Bestehen des Abnahmetests folgt die technische Übertragung des Softwaresy- stems 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 abge- schlossen. 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 Model- le, 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 Implementie- rung 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.
3. Semantikfehler : Semantik - oder Laufzeitfehler sind alle Fehler, die dadurch entste-
hen, 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 Imple- mentierung, 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 einem Debugger zu lokalisieren. Die Erklärung für dieses merkwürdige Ver- halten ist, dass man mit einem Debugger (Messung) das zeitliche Verhalten des Systems verändert. Die scherzhafte Bezeichnung bezieht sich daher auf die Heisenbergsche Unbestimmtheitsrelation aus der Physik.
(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- ten des Systems verursacht hat (Schrödingers Katze ).
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 fehler- behaftet 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]
Kapitel 4 Schachsoftware
Premature optimization is the root of all evil.
Sir Charles Antony Richard Hoare[25]
4.1 Spezi kation
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 ho e 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:
Abbildung in dieser Leseprobe nicht enthalten
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 de niert wird ein Datentyp TFeld für die Speicherung eines Feldes und TZug für die Speicherung eines Zuges (Start- und Zielfeld):
Abbildung in dieser Leseprobe nicht enthalten
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.
Abbildung in dieser Leseprobe nicht enthalten
Der Datentyp TSchachbrett wird dann zusammen mit anderen wichtigen Variablen in den Datentyp TSchachkonstellation eingebettet:
Abbildung in dieser Leseprobe nicht enthalten
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;
4.2.2 Frontend
Die Frontend ist eine gekapselte Prozedur, die Daten vom Typ TSchachbrett übergeben bekommt und dieses Schachbrett dann gra sch 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:
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 -Zugde nitionen:[26]
4.2.3.1.1 Turm
Der Turm darf auf ein beliebiges anderes Feld entlang der Linie oder der Reihe ziehen, auf welchen er steht.
Abbildung in dieser Leseprobe nicht enthalten
4.2.3.1.2 Läufer
Der Läufer darf auf ein beliebiges anderes Feld entlang einer der Diagonalen ziehen, auf welchen er steht.
Abbildung in dieser Leseprobe nicht enthalten
4.2.3.1.3 Dame
Die Dame darf auf ein beliebiges anderes Feld entlang der Linie, der Reihe oder einer der Diagonalen ziehen, auf welchen sie steht.
Abbildung in dieser Leseprobe nicht enthalten
4.2.3.1.4 König
Er zieht auf ein beliebiges angrenzendes Feld.
Abbildung in dieser Leseprobe nicht enthalten
4.2.3.1.5 Springer
Der Springer darf auf eines der Felder ziehen, die seinem Standfeld am nächsten, aber nicht auf gleicher Linie, Reihe oder Diagonalen mit diesem liegen.
Abbildung in dieser Leseprobe nicht enthalten
4.2.3.1.6 Bauer
a) Der Bauer darf vorwärts auf das unbesetzte Feld direkt vor ihmauf derselben Linie ziehen, oder
b) in seinem ersten Zug entweder wie unter a) beschrieben ziehen, oder um zwei Felder entlang derselben Linie vorrücken, vorausgesetzt, dass beide Felder frei sind, oder
c) auf ein von einer gegnerischen Figur besetztes Feld diagonal vor ihm auf einer benachbarten Linie ziehen, indem er die Figur schlägt.
Da der Bauer die einzige Figur ist, die von der Farbe abhängig in verschiedene Richtungen ziehen kann, muss hier anhand der Farbe unterschieden werden:
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).
Abbildung in dieser Leseprobe nicht enthalten
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 Funk- tion 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 Rocha- de kann auch gar nicht berücksichtigt werden, weil die Implementierung der Rochade auf die Funktion GueltigerZugOhneSchach zurückgreifen muss, um festzustellen, ob eine Ro- chade 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 feststand.
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 gespeichert ist, wer am Zug ist).
4.2.3.4 En passant gültig
Im Datentyp TSchachkonstellation wird gespeichert, wieviele en passant-Schlagzüge der am Zug be ndliche 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 gespeichert.
Die Funktion en_passant_gueltig(Schachkonstellation,Zug):Boolean prüft, ob der über- gebene 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 aktuell gehalten.
Die Funktion RochadeGueltig(Schachkonstellation,Art_der_Rochade):Boolean überprüft, ob bei
Abbildung in dieser Leseprobe nicht enthalten
Rochade der betre ende 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 False ist mindestens ein Feld belegt.
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ültigen Zug ohne Schach (4.2.3.3) auf mindestens eines dieser Felder gibt.
Abbildung in dieser Leseprobe nicht enthalten
4.2.4 Wichtige Funktionen
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 zu- rü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 Funkti- on nur aufgerufen wird, wenn der übergebene Zug vorher auf seine Gültigkeit überprüft wurde.
4.2.4.1 Schach
Die Funktion Schach(Schachkonstellation):Boolean soll zurückliefern, ob der König des am Zug be ndlichen Spielers nicht bedroht (False ) oder bedroht (True ) ist. Der andere König kann aufgrund der Zugregeln nie im Schach stehen.
Abbildung in dieser Leseprobe nicht enthalten
4.2.4.2 Figur verschieben
FigurVerschieben(Schachbrett,Zug):Schachbrett weist dem Zielfeld den Figurenwert des Startfelds zu und setzt dann den Figurenwert des Startfelds auf 0 (leer). Es wird nur diese eine Figur verschoben, keine rochade- oder en passant-relevenanten Parameter aktuali- siert und auch nicht z.B. bei der Rochade nach einem Königszug der Turm bewegt. Weil FigurVerschieben immer nur eine Figur verschiebt, werden zwei weitere Funktionen für die Rochade und en passant benötigt, da diese zwei Züge aus zwei Schritten bestehen:
4.2.4.3 En passant ausführen
Hat ein Bauer gerade en passsant geschlagen (als Zug übergeben), so leert die Funktion en_passant_ausfuehren(Schachbrett,Zug):Schachbrett das Feld, auf dem der gegnerische 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 ist1, 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.
4.2.4.6 Zug ausführen
Während die bisherigen Funktionen alle nichts an den in TSchachkonstellation gespeicher ten 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).
Abbildung in dieser Leseprobe nicht enthalten
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
des am Zug be ndlichen Spielers bedroht ist, hier aber die Frage ist, ob der nicht mehr am Zug be ndliche Spieler seinen eigenen König durch den letzten Halbzug ins Schach gestellt hat, wodurch dieser Zug dann ungültig ist.
Abbildung in dieser Leseprobe nicht enthalten
Auf dieser Funktion können nun die Funktionen für Matt und Patt aufgebaut werden:
4.2.4.8 Matt
Um festzustellen, ob der am Zug be ndliche Spieler matt ist, wird zunächst überprüft, ob dessen König bedroht ist (Schach(Schachkonstellation)). Wenn er bedroht ist, dann wer- den in zwei verschachtelten Schleifen alle Felder durchgegangen und damit alle denkbaren Züge durchgegangen (a1 > a1, a1 > a2, a1 > a3 usw. bis h8 > h8). Ist keiner dieser Züge gültig (GueltigerZug(Schachkonstellation,Zug)), dann ist der Spieler matt.
4.2.4.9 Patt
Die Funktion Patt(Schachkonstellation):Boolean arbeitet prinzipiell genauso wie Matt, 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 (SchachbrettZeichnen(Schachbrett)) und überprüft, ob durch diesen Zug eine Schach-, Matt- oder Pattsituation entstanden ist und das Zutre ende ausgegeben. Ist der übergebene Zug nicht gültig, wird eine Fehlermeldung ausgegeben.
4.2.5.2 Züge rückgängig machen
Um Züge rückgängig machen zu können, muss der gesamte Partieverlauf abgespeichert werden. Dazu eignet sich eine Zeigerkette optimal, also wird hierfür ein eigener Datentyp verwendet:
Abbildung in dieser Leseprobe nicht enthalten
Wenn eine neue Partie erö net wird, wird für MomentanePartieKonstellation Speicherplatz reserviert und diesem Speicherplatz die Grundstellung zugewiesen2. VorherigeKonstellation von dieser Grundstellung wird der Wert nil zugewiesen.
Abbildung in dieser Leseprobe nicht enthalten
Wenn ein Zug ausgeführt wird, soll die Zeigerkette folgendermaÿen angepasst werden:
Abbildung in dieser Leseprobe nicht enthalten
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.
4.3 Anmerkungen zur Implementierung von Teil 1
Der bisher beschriebene Systementwurf wurde innerhalb von zwei Tagen mit einem Um- fang 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 inner- halb 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 ) ausgie big (vor allem auf die Korrektheit der generierten Zugmöglichkeiten) getestet 3. 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 ver- sucht, 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 MinimaxAlgorithmus 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 Bewertungs- funktion 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 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 Spiel- baumausschnitt 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 Li- nien) 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
- 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 verschachtel- ten 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 vor- teilhaft 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 Be- wertung 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ÿ am Zug ist) der Zugbewertungen aller gültigen Züge bei der vorliegenden Schachkonstel- lation 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 zugegri en, 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 :
Abbildung in dieser Leseprobe nicht enthalten
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ückgegri en 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 Zeite zienz 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 statt nden, 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 84 = 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 o ensichtlichen 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 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, zeig- ten, wo das eigentliche Problem der Laufzeit liegt: der Zuggenerator könnte wesentlich e ektiver 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 Spezi kation 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.
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 Engi- neering 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 wa- ren 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 erho te, 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.
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 Zeite zienz, denn das gleiche Ergebnis in kürzerer Zeit bedeutet mehr untersuchte Stellungen und somit eine verbesserte Spielstärke
- einem e zienteren Zuggenerator mit Bitboards
- besseren Bewertungsfunktionen (Material, beherrschter Raum, Beweglichkeit, Be- drohungen, Figurenzusammenspiel, Entwicklungstempo, Verlust der Rochademög- lichkeit)
- Erkennung von Erö nung, Mittelspiel und Endspiel, verschiede Algorithmen, Such- tiefen und Gewichtungen der Bewertungsfunktionen für die einzelnen Phasen
- einem Alpha-Beta-Algorithmus zur Zugsuche (Alpha-Beta-Cuto s )
- einer Zugsortierung, damit die Alpha-Beta-Cuto s 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önigsbe- drohungen 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. Bewertungsfunk- tionen zur Laufzeit ändert
- einer lernfähigen, starken KI1
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 umzuset- zen, von simplen Spielen und Übungsprogrammen über rekursive Problemlösungen mit mathematischem Hintergrund bis hin zu physikalischen Anwendungen wie Interferenz- simulationen 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 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 LATEXzurVerfügungstandundmirschoninder MSS 11 bei der Installation behilflich 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 ATEX-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 Nalebuff: Spieltheorie für Einsteiger, Schäffer-Poeschel, 1. Auflage 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. Auflage 2002
[16] http://lexikon.meyers.de/meyers/Heuristik
[17] Rüdeger Baumann: Informatik für die Sekundarstufe II Band 1, Klett, 1. Auflage 1999
[18] Gustav Pomberger, Peter Rechenberg: Informatik-Handbuch, HANSER, 3. Auflage 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. Auflage 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/ 2004 Sommersemester/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.
Anhang A Quelltext
Dieser Quelltext ist wegen besserer Lesbarkeit in Delphi auch online verfügbar (siehe 5.6)
Abbildung in dieser Leseprobe nicht enthalten
[...]
0 Titelbild: Die Mattstellung der 1851 auÿerhalb eines Turniers gespielten unsterblichen Partie zwischen den Schachmeistern Adolf Anderssen und Lionel Kieseritzky.[1]
0 Die vorliegende BLL setzt beim Leser Fachkenntnisse in Informatik der MSS 11 und 12 voraus.
1 Im Folgenden werden auch die Bauern als Figuren bezeichnet, obwohl sie streng genommen als Steine bezeichnet werden müssten
2 Der Mathematiker und Mitbegründer der Spieltheorie John von Neumann bewies dieses Min-Max- Theorem 1928. [11, Anmerkung zur deutschen Übersetzung]
3 Das Nash-Gleichgewicht wurde 1950 vom genialen Nobelpreisträger John Forbes Nash Jr. in seiner Dissertation als grundlegendes Lösungskonzept der Spieltheorie entwickelt. [12]
4 Die Heuristik ist die Lehre von der methodischen Gewinnung neuer Erkenntnisse mithilfe von Denk- modellen, Analogien, Gedankenexperimenten; im Unterschied zur Logik, die lehrt, sie zu begründen.[16]
1 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.
2 Die Syntax einer Programmiersprache ist eine Beschreibung einer Obermenge der zulässigen Programmtexte. [18, Seite 480]
3 Seit der Begründung und Durchsetzung der strukturierten Programmierung durch Edsger Wybe Dijkstra s legendäres Manuskript Go To Statement Considered Harmful im Jahr 1968 entfällt die von ihm als schädlich entlarvte Sprunganweisung Go To.[20]
4 Program testing can be used to show the presence of bugs, but never to show their absence! Edsger Wybe Dijkstra[22]
1 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.
2 Die Funktion Grundstellung:Schachkonstellation soll diese Grundstellung zurückliefern.
3 Dazu wurden sowohl Modul-, Schnittstellen- als auch Systemtests mit und ohne Debugger durchge- führt
1 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
- Quote paper
- Daniel Witzke (Author), 2008, Software Engineering in Theorie und Praxis: Die Entwicklung und Implementierung einer Schach-Software, Munich, GRIN Verlag, https://www.grin.com/document/124079
-
-
-
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X. -
-
Upload your own papers! Earn money and win an iPhone X.