Connect 4 Gewinnt

Alles rund um TX(T) und RoboPro, mit ft-Hard- und Software
Computing using original ft hard- and software
Forumsregeln
Bitte beachte die Forumsregeln!
Antworten
hamlet
Beiträge: 332
Registriert: 12 Jan 2011, 21:41

Connect 4 Gewinnt

Beitrag von hamlet » 14 Jun 2011, 20:45

Hallo,
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.
Natürlich lässt sich das Programm einfach zur Steuerung eines "Vier Gewinnt" Roboters erweitern. Ein Quick-And-Dirty Beispiel für die Roboteransteuerung ist ebenfalls enthalten (Game_Robot Funktion und die Funktionen in der Gruppe "Robot"). Dabei hat mir Rei Vilos Encoder-Motoransteuerung gute Dienste geleistet. Meiner eigener Roboter ist ein wenig klobig geraten. Wird aber noch ...
Bild
Bild
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.
Erfahrungen:
  • 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.

Benutzeravatar
Dirk Fox
ft:pedia-Herausgeber
Beiträge: 1832
Registriert: 01 Nov 2010, 00:49
Wohnort: Karlsruhe
Kontaktdaten:

Re: Connect 4 Gewinnt

Beitrag von Dirk Fox » 14 Jun 2011, 22:16

Hallo Helmut,

das ist ja eine tolle Modellidee - und eine Realisierung leicht jenseits der Möglichkeiten von Robo Pro, scheint mir ... Hoffentlich saugt ft aus Deinen Erfahrungshinweisen kräftig Honig für die nächste Version...

Gibt es das Modell auf der Convention zu sehen?
(Und vorab vielleicht sogar ein Artikelchen in der ft:pedia - z.B. über die Implementierung einer MiniMax-Strategie in RoboPro? :P )

Beste Grüße,
Dirk

hamlet
Beiträge: 332
Registriert: 12 Jan 2011, 21:41

Re: Connect 4 Gewinnt

Beitrag von hamlet » 15 Jun 2011, 22:40

Hallo Dirk,
an dem Termin der Convention im September bin ich leider verhindert. Einen Artikel für die ft:pedia werde ich aber in Angriff nehmen, und hoffe, dass etwas Brauchbares dabei herauskommt. Ich bin mir noch nicht so ganz klar über den Schwerpunkt, habe aber schon einige Ideen.
Die ft:pedia ist wirklich großartig. Es macht Freude in den hervorragend verfassten Artikeln nach guten Lösungen zu stöbern. Verglichen dazu sind die "didaktischen" ft-Begleitheftchen in ihrer heutigen Form ... Asche.
Beste Grüße,
Helmut

Benutzeravatar
Dirk Fox
ft:pedia-Herausgeber
Beiträge: 1832
Registriert: 01 Nov 2010, 00:49
Wohnort: Karlsruhe
Kontaktdaten:

Re: Connect 4 Gewinnt

Beitrag von Dirk Fox » 15 Jun 2011, 23:17

Hallo Helmut,

danke für die Blumen (mal stellvertretend für die vielen Mitstreiter...).
Wir haben so viele Ideen für tolle Beiträge, dass Stefan eigentlich schon morgen Ausgabe 3 herausbringen wollte ;-)
Toll, wenn Du etwas beisteuerst! In Deinem Modell stecken eine Menge pfiffiger Ideen...

Beste Grüße,
Dirk

vleeuwen
Beiträge: 1557
Registriert: 31 Okt 2010, 22:23
Wohnort: Enschede (NL)
Kontaktdaten:

Re: Connect 4 Gewinnt

Beitrag von vleeuwen » 16 Jun 2011, 07:00

"rekursiver Negamax Algorithmus"
Recursive function needs sometime a lot of stack space; this depends on the number of recusive function calls.
I am not so sure if the TX-C processor is able to manage it.
See datasheet:
http://www.atmel.com/dyn/resources/prod ... oc6221.pdf

hamlet
Beiträge: 332
Registriert: 12 Jan 2011, 21:41

Re: Connect 4 Gewinnt

Beitrag von hamlet » 16 Jun 2011, 22:11

Exactly, that's why I suspected a stack overflow as reason for the observed crash of the OS.

I am not an expert in this field, but I don't think that the stack size is constrained by the processor. It provides a special stack pointer and some stack operations, and the stack managment itself is the responsibility of the OS. But anyway, thank you for the ARM9 document reference.
I have chosen a stack size of 32K per thread, which is the maximum value you can set in RoboPro. And in my opinion this should be sufficient. There is not that much of local data in the NegaMax function.
- 3 input parameters
- 1 loop index
- 2 lokal list indices
All the oher data is global, and I suspect that RoboPro has to allocate a local buffer for each input of each operator, command, function and list input.
- operators in Negamax and sub-objects: 2*(3+3+8)+4=32
- commands: 11
- functions: 10
- list: 4
Sum = 63 inputs
All are 16bit integers
=> 126 byte
Maximum recursion depth of 8
=> 1008 byte
This is ~3% of the 32K stack.
OK , what really happens in the background, I am afraid, we will never know.

fischli
Beiträge: 123
Registriert: 06 Nov 2010, 17:18
Wohnort: Elmshorn

Re: Connect 4 Gewinnt

Beitrag von fischli » 16 Jun 2011, 22:19

Irgendwie komme nicht auf die Seite, und der Link funktioniert auch nicht. NAch 30 sek "Seitenladefehler"

Ist das nur bei mir so oder hat auch gerade jemand anderes dieses Problem?

MFG fischli

hamlet
Beiträge: 332
Registriert: 12 Jan 2011, 21:41

Re: Connect 4 Gewinnt

Beitrag von hamlet » 16 Jun 2011, 22:45

Hi fischli,
hab gerade nochmal ausprobiert das zip runter zu laden ... kein Problem, auch die anderen links scheinen intakt zu sein.
Beste Grüße,
Helmut

fischli
Beiträge: 123
Registriert: 06 Nov 2010, 17:18
Wohnort: Elmshorn

Re: Connect 4 Gewinnt

Beitrag von fischli » 17 Jun 2011, 20:57

Ja, jetzt funktionierts.

Wieviele Jahre hast du an dem Programm gearbeitet???

Fischli

hamlet
Beiträge: 332
Registriert: 12 Jan 2011, 21:41

Re: Connect 4 Gewinnt

Beitrag von hamlet » 19 Jun 2011, 10:22

Hi Fischli,
Jahre waren es glücklicherweise nicht, ... aber es ist schön wieder am sozialen Leben teilzunehmen ;)
5 Tage intensiv und ein paar Abende.
Beste Grüße,
Helmut

fischli
Beiträge: 123
Registriert: 06 Nov 2010, 17:18
Wohnort: Elmshorn

Re: Connect 4 Gewinnt

Beitrag von fischli » 19 Jun 2011, 21:28

Ich verliere bei so großen Programmen mit ROBO-Pro ja immer den Überblick. Ich baue das Programm nach und nach auf, denn wenn ich fertig bin, gibt es meisten mehrere Unterprogramme, deren Verwendung ich nicht mehr ganz nachvollziehen kann.

Ich muss das Programm von dir endlich mal testen. Man bräuchte bloß Zeit. Naja, heut jedenfalls nicht mehr, gääähhhhnnnnnn.........

Fischli

hamlet
Beiträge: 332
Registriert: 12 Jan 2011, 21:41

Re: Connect 4 Gewinnt

Beitrag von hamlet » 20 Jun 2011, 20:16

Hello,
a new version of Con4Core is available:
http://www.alice-dsl.net/helmut.schmuec ... re_002.zip
Changes:
- Bug fix: Value of variable "infinity" has been increased => Correct end of game detection, if last move completes more than one row of four.
- Minor beautifications
Cheers,
Helmut

Michi74er
Beiträge: 2
Registriert: 06 Feb 2022, 10:16

Re: Connect 4 Gewinnt

Beitrag von Michi74er » 06 Feb 2022, 10:25

Hallo hamlet

Wir haben einen 4-gewinnt Roboter gebaut und sind auf Deine Berechnung der Züge mit rekursivem Negamax Algorithmus gestoßen.

Die Datei ist leider nicht verfügbar. Gibt es denn die Datei noch?
Schöne Grüße

Michael Neumaier

Benutzeravatar
EstherM
Beiträge: 1466
Registriert: 11 Dez 2011, 21:24

Re: Connect 4 Gewinnt

Beitrag von EstherM » 06 Feb 2022, 11:45

Hallo Michael,
eine Suche nach "gewinnt" auf unserer Webseite führt (neben anderen) zu diesem Treffer: https://ftcommunity.de/knowhow/computin ... /con4core/
Vielleicht ist das die Datei, die Du suchst.

Gruß
Esther

Michi74er
Beiträge: 2
Registriert: 06 Feb 2022, 10:16

Re: Connect 4 Gewinnt

Beitrag von Michi74er » 06 Feb 2022, 13:03

Vielen Dank,
ich bin beheistert von der schnellen Hilfe.
Und erstaunt über die Meisterleistung dieses ROBO Pro Programms.
Wir haben unser Programm in Python geschrieben und sind nun daran die Berechnung in C
zu machen um die Rechentiefe zu erhöhen.
Vielen Dank und schöne Grüße

Michael

Antworten