Es wird extrem nerdy gerade. Aber da ich sowas nur ab und zu mache, setze ich nicht gleich einen neuen Blog dafür auf.
Da ich die Woche nur minimalen Druck auf der Arbeit habe, hatte ich die Zeit, eine sog.
Künstliche Intelligenz (Abk.: KI) zu entwickeln. Ich habe mich für das einfachste Spiel der Welt entschieden, was meist unentschieden ausgeht:
Tic-Tac-Toe. Erst einmal klingt Künstliche Intelligenz total nach Magie. Erstens künstlich und zweitens auch noch intelligent.
Dabei ist das alles ziemlich einfach: Man läßt einfach unbemerkt den Computer im Hintergrund gegen sich selbst spielen. Der Computer spielt abwechselnd sich und den Gegner und schaut sich dann immer das Ergebnis an. Dann trifft er die Annahme, dass er immer den besten Zug und der Gegner immer den für den Computer schlechtesten Zug spielen würde.
Man muss dem Programm also nur noch kurz erklären, wie das Spiel funktioniert, d.h. dass immer abwechselnd gezogen wird, wo ein Spieler hinsetzen darf und wann ein Spieler gewonnen hat.
Für die KI habe ich den einfachsten Algorithmus schlechthin genommen, sodass der Computer wirklich jeden Zug ausrechnet - es gibt auch bessere Verfahren, aber für meine erste Implementierung reicht mir auch ein "schlechter"
(MiniMax) Algorithmus.
Man glaubt gar nicht, was dabei alles schief gehen kann, aber es hat mich in der Summe etwa 16h Entwicklungszeit gekostet.
Folgende triviale Fehler habe ich gemacht:
- Beim erklären der Regeln (Man hatte bereits gewonnen, wenn noch kein einziger Stein gesetzt war, da in jedem Feld die "gleiche Farbe lag", nämlich die Farbe "null" -- oder bei der diagonale, die von links unten nach rechts oben geht, hat plötzlich der gewonnen, der seinen Stein links oben hat ... jaja, Sachen gibts...) (Fehler im Stellungsbewerungsalgorithmus)
- Beim Vergleichen von Ergebnissen (Verloren war zwar schlechter als unentschieden, aber unentschieden nicht besser als Verloren ...) (Fehler in der Vergleichsmethode der Bewertungspunkteklasse)
- Gab es keine gültigen Züge mehr, galt das Plötzlich als Verloren, obwohl es ein klares unentschieden war (Fehler in der MiniMax Implementierung)
Auf Deutsch, Fehler lauern an jeder Stelle im Programm. Wenn man die Liste der Fehler ansieht, die gemacht wurden, lacht man sich fast schlapp und denkt, was ein Anfänger, ist doch klar dass ...
Gelernt habe ich daraus noch viel mehr, dass man praktisch davon ausgehen darf, dass alles falsch ist, bevor man nicht abgeprüft hat, dass es richtig ist. Und dann darf man noch die Überprüfung der Überprüfung kontrollieren. Dafür hat man ja
JUnit, damit man alles komponentenweise abprüft. Da die ganze Lösung aus zwei Komponenten besteht, habe ich zu Anfang folgenden Fehler gemacht: Ich habe zuerst dass ganze Tic-Tac-Toe spiel überprüft und anhand ein paar weniger Stellungen geschaut, ob der Computer den "logisch richtigen" Zug macht. Wen wundert es, dass hat er zu Anfang natürlich nicht gemacht.
Mein Fehler war, 2 Komponenten gleichzeitig abzuprüfen, und nicht erst die Klassen der Kernkomponente
- Bewertungspunkteklasse auf Richtigkeit für alle Möglichkeiten testen (1 besser Unentschieden, Verloren schlechter als Gewonnen etc.)
- Computer zieht abwechselnd sich und den Gegner, ruft die Bewertung auf, vergleicht, sucht das beste bzw. schlechteste heraus - einmal für einen flachen Baum, einmal für einen etwas tieferen.
Also musste "ein Spiel" erfunden werden, welches noch einfacher ist, als TicTacToe - dies war sehr schnell gefunden - man spielt einfach mit Bäumen und jedes Blatt hat einen Wert :) Und dann schaut man, ob sich der Computer das beste Blatt genommen hat.
Jetzt führt der Computer bei der tiefsten Berechnungsstufe bei freiem Feld auch den richtigen Zug aus: Er setzt einfach in die Mitte. Und dass, obwohl dass Programm nur weiß, welche Endstellung verloren, gewonnen oder unentschieden ist.
Und da das ganze so schön Komponentenweise (
Modular) aufgebaut ist, kann ich dem Programm einfach die Schach-, Dame- oder Mühle Regeln beibringen, ohne den MiniMax Algorithmus nochmal schreiben zu müssen.
(Die Problematik der schnellsten Lösung (für Maximierung, bzw. umgekehrt im Fall der Minimierung), d.h. dass ein direkter Sieg angestrebt wird anstelle von einer gleichwertigen, aber längeren Lösung, habe ich hier einmal ausgeklammert - diese wurde aber beim implementieren berücksichtigt und funktioniert auch)
