unter http://www.alice-dsl.net/helmut.schmuec ... n4Core.zip findet ihr eine RoboPro-Implementierung von "Vier gewinnt":
Das Programm läuft sowohl im Download- als auch im Online-Modus und verwandelt den RoboTX
in eine einfache "Vier Gewinnt" Spielkonsole, wobei es die atemberaubenden grafischen Fähigkeiten
des TX Controllers restlos ausnutzt (-;
- Mit dem Slider unter dem Spielfeld wählt man den Slot in den der nächste Stein geworfen werden soll.
- Der OK-Button führt dann den Zug aus
- Mit dem linken Slider lässt sich die Spielstärke, d.h. die Anzahl der vor-simulierten Züge, einstellen, auch während des Spiels. Level 4 ist ein guter Kompromiss: Die Rechenzeit beträgt wenige Sekunden, einfache Zwick-Vierer werden erkannt und man hat noch Chancen zu gewinnen. In Level 6 kann man im Download-Mode schon mal über eine Minute auf den TX-Zug warten. Level 8 hab ich gerade ausprobiert, ist im Download-Mode 'ne blöde Idee, weil der TX dann einfach einfriert. ... Das kleine rote LED-Herz hörte einfach auf zu schlagen. Wahrscheinlich ein Stack Overflow.
- Von oben nach unten werden folgende Werte angezeigt.
- Zahl der evaluierten Züge
- Die dazu benötigte benötigte Rechenzeit in zehntel Sekunden
- und der augenblickliche Spielstand, d.h. der Score der Spielposition. Je größer, desto besser wird de Position des Spielers bewertet. Naja, ist bei mir meist negativ.
Falls jemand noch eine Idee zur Verbesserung des Programms hat oder einen Fehler findet, bin ich für Hinweise und Kommentare sehr dankbar.
Beste Grüße,
Helmut
Gruppierung:
Wenn ihr das Programm öffnet, seht ihr eine ziemlich lange ungeordnete Liste von Unterprogramm-Tabs. Ich weiß leider nicht ob oder wie man die Tabs sortieren kann. Ich habe aber versucht, ein wenig Struktur hineinzubringen, indem ich die Unterprogramme gruppiert habe.
- "Main" enthält die beiden Haupt-Unterprogramme für den Vier Gewinnt Roboter und das Display-Spiel
"Core" enthält den Vier Gewinnt "Kernel" (Con4Core, und dessen Unterprogramme)
"Display" enthält die TX-Display-Routinen
"Init" enthält einige Initialisierungs-Funktionen ... gehört eigentlich zu "Core"
"Robot" enthält die Unterprogramme der Roboteransteuerung
"Helpers": Kleine Hilfsfunktionen
"Optimization" enthält für den Downloadbetrieb optimierte Versionen von "Core"-Funktionen
Technisches:
Algorithmus:
Zur Berechnung der Züge wird ein rekursiver Negamax Algorithmus (eine MiniMax-Variante), in Kombination mit Alpha-Beta-Pruning verwendet (http://de.wikipedia.org/wiki/Alpha-Beta-Suche). Die möglichen Züge werden nach einem einfachen Algorithmus vorsortiert, was die Effizienz des Alpha-Beta Prunings teilweise erheblich steigert.
Die verwendete Heuristik bzw. Scoring-Funktion ist auf meinem Mist gewachsen:
Das 7*6 Vier Gewinnt Spielfeld enthält 69 mögliche 4-er-Reihen. Falls ausschließlich ein Spieler Steine in einer der Reihen hat, werden ihm abhängig von der Anzahl der Steine Punkte zugesprochen. Falls beide Spieler Anteil an der Reihe haben, ist sie für das Spiel verloren und keiner der Spieler erhält für die Reihe Punkte. Die Punkte der 69 Reihen werden einfach aufaddiert, negativ für den einen und positiv für den anderen Spieler. Falls einer der Spieler eine Reihe voll hat, wird ihm eine sehr große Punktzahl zugesprochen, damit der NegaMax Algorithmus den Sieg erkennt. Ich vermute allerdings, dass es sich hierbei um eine bekannte Methode handelt, da sie simpel und naheliegend ist. Sie ist allerdings auch nicht perfekt, da Vier Gewinnt kein symmetrisches Spiel ist, d.h. die optimale Strategie der beiden Spieler ist für den ersten und zweiten Spieler unterschiedlich. Das wird von der verwendeten Heuristik nicht berückschtigt.
Die Gewichtung von 1,2, oder 3 Steinen in einer 4er_Reihe lässt sich in den beiden Listen der Funktion "Score4" modifizieren. Sie ließen sich im Prinzip optimieren, indem man den Computer gegen sich selbst mit unterschiedlichen Gewichtungen spielen ließe.
Optimierungen:
- Die Score-Funktion wird beim rekursiven Durchschreiten des Zugbaumes sukzessive durch Hinzu- und Wegnehmen von Steinen aktualisiert. So werden die nötigen Berechnungen minimiert. Ein wenig Doku zu den hierbei verwendeten Datenstrukturen und Lookup-Tables findet sich in dem Unterprogramm "InitGlobalVars".
- Ich habe soweit wie möglich versucht, auf Verzweigungen in den blauen Prozesspfaden zu verzichten. Das macht den Code nicht unbedingt leserlicher aber vermeidet die bis zu 2ms Wartezeit pro Verzweigung im Download-Mode.
- In der Funktion DoMove_OPT habe ich die zentrale Schleife, in der der augenblickliche Score berechnet wird, entrollt. Das bringt einen Faktor 3 in der Geschwindigkeit. Allerdings musste ich nachher wieder eine kleine Zwangspause einbauen, weil das Betriebssystem im Download Mode abgeschmiert ist. Ich schätze, dass die entrollten Berechnungen dann doch erheblich länger als die erlaubten 500µs brauchen, woraufhin sich das Betriebssystem einfach aufhängt. Vermutlich ist die TX Firmware komplett ohne Interrupts für wichtige Betriebssystemfunktionen realisiert und verlässt sich darauf, dass der User-Code, der einfach zusammen mit Betriebssystemfunktionen in die Hauptschleife gehängt wird, sich gut benimmt und nicht zu lange rechnet. Robust und Erweiterbar geht anders.
- In einigen reinen Funktionen habe ich nachträglich doch noch blaue Prozesspfade eingefügt, um unnötige Evaluationen der Funktion zu vermeiden. So konnte ich ein paar der Zwangs-Waits wieder entfernen, ohne dass sich die Firmware wieder verabschiedet hat.
- Es ist mir schier unmöglich übersichtlichen Code mit RoboPro zu erstellen. Es ist schon sehr beeindruckend wie eine einfache c oder c++ Routine bei der Reimplementierung in RoboPro zu einem Monster-Mondrian mutiert. Die Hälfte der Zeit ist man mit Objektschieberei beschäftigt um den Überblick zu behalten.
- Objektorientierung ist in RoboPro ein Fremdwort, oder ich habe das Konzept einfach nicht begriffen. Ich kann keine Objekte, oder auch nur Datenstrukturen, definieren, zur Laufzeit instanzieren, kopieren oder als Parameter übergeben oder in ein Array stecken. Somit bin ich immer wieder bei globalen Variablen und Listen gelandet.
- Die Vielzahl von "lokal", "global", "object" und "Namensgebunden"-Optionen für Funktionsaufrufe, Operatoren, Befehls Ein-/Ausgänge, Daten und Indices von Listen ist einfach unübersichtlich, unverständlich und natürlich nicht dokumentiert. So stellt z.B. RoboPro in einer reinen Funktion, d.h. kein Prozess nur gelbe Ein und Ausgänge und keine Objekt-Daten, alle Optionen auf "Objekt". Was soll der Mist? Zudem muss man in so einem "Objekt" für den Zugriff auf eine globale Liste die Index-Lebensdauer unbedingt manuell auf "Objekt" stellen. Die Fehlersuche macht da richtig Spaß.
- Die TX-Firmware informiert einen nicht über einen Stack Overflow. Das Programm stürzt einfach ab.
- Die TX-Firmware prüft nicht ob der User Code zuviel Laufzeit in Anspruch nimmt. Der TX Controller friert einfach ein, erkennbar an der roten "Heartbeat"-LED.