Mühlespielender Bot

Hallo zusammen,
möchte euch mal mein momentanes Projekt vorstellen:
Ein Roboter, der in der Lage ist, einfache Mühle gegen einen humanen Gegner zu spielen.
Die Hardware ist komplett aufgebaut, die Software läuft im Bascom-Simulator tadellos und muss nur noch an die Hardware angepasst werden (Bewegungsroutinen des Greifarms einbauen, User-Interface etc.)

Der Greifarm ist aus "Mecano" aufgebaut und wird von 3 Servos getrieben, zwei Digitale und ein Analoges.
Das Ganze besteht aus 3 Modulen:
- Spielbrett und LCD
- Spannungsversorgung und Greifarm
- Mainboard mit Spannungsreglern und Controller (Mega128)

Die Servos werden von LM317 angetrieben und der Elektromagnet von einem Step-Down Wandler. Die LMs müssen per Lüfter gekühlt werden, sonst werden sie zu heiss.

Der Mega128 ist ein bisschen Overkill, das Programm wird um die 16-20kB gross werden, und alle Pins brauch ich auch net.
Unter den Spielfeldern liegen Reed-Sensoren, und in den Spielsteinen hat es einen kleinen Magneten.

Im Anhang noch ein paar Bilder.
PS: In meinem Space hats noch mehr Bilder: (==>Fotos==>Maturaarbeit)
http://mariomauerer.spaces.live.com/?_c11_PhotoAlbum_spaHandler=TWljcm9zb2Z0LlNwYWNlcy 5XZWIuUGFydHMuUGhvdG9BbGJ1bS5FZGl0TW9kZUNvbnRyb2xs ZXI%24&_c11_PhotoAlbum_albumid=cns!FE697FA9644F52D 2!324&_c11_PhotoAlbum_spaReturnToFull=0&_c11_Photo Album_spaProcess=1&_c=PhotoAlbum&_c02_owner=1

Herzlichen Gruss
Mario

Hallo Mario!
Ein interessantes Projekt!
Ich bin schon auf ein InAction-Video gespannt! *g*
Im Bild "alle Module.JPG" habe ich das CAS Voyage von TI gesehen, hat der etwas mit dem Projekt zu tun, also steuerst Du mit ihm etwas!?
Ich habe auch den Voyage ... ;p

Viele Grüße
Florian

Nööö, den Voyage brauch ich nur zum irgendwas berechnen :) Hat nix damit zu tun. Der Mega128 arbeitet völlig autonom, der Laptop daneben ist nur da, um ihn zu proggen...

Hmm, weiss jemand, wie ich 20MB Video ins Netz bekomme? 8-[

Das ist richtig klasse =)
Würd mich echt reizen, dein Projekt mal bewegen zu sehen ;)

Unterdessen hab ich knapp 8MB Video.... Wie krieg ich das irgendwie hoch?

Z.B. als *.ZIP auf deinen Webspace hochschieben oder als Alnernative bei http://video.google.de ,wenns dir nichts ausmacht, das andere Leude das auch sehen, ist ja aber in diesem Forum nicht anders \:D/

Ok, habs im Google Video.
Momentan packt er einfach einen Stein und klappert damit alle Felder an. Auf dem LCD zeigt er mir dann, ob der Stein korrekt erkannt wurde. So kann ich die Servowege noch verbessern.
Hier der Link:
http://video.google.de/videoplay?doc...83476915153157

Suuuper geil, und mit welcher Präzision der den Stein nimmt und wieder ablegt, ich find geil, hättest mich mal grinsen sehen sollen \:D/

EDIT:
Wirkt aber noch sehr instabil der Arm ;)

Jaa, der GANZE Arm ist auch auf EINEM Servo befestigt... Halt n bisschen dünn die Achse.. Deshalb warte ich auch vor dem Ablegen und hochnehmen ein bisschen, bis der Arm ausgeschwungen ist... :)

Und ich hätte auch die dünnen Konstrucktschienen getippt, der schwank nämlich seitlich :-k

ja, das schwankt natürlich auch... das Mecano hat halt schon ein wenig Spiel... Naja, was solls, er ist ziemlich genau, ich muss noch zwei Felder verbessern, dann steuert er alle fehlerlos an.

Wirklich ein schickes Projekt! :o)
Hat man theoretisch eine Chance gegen ihn zu gewinnen, oder lässt er keine Fehler zu?!

Viele Grüße
Florian

Soll keine Kritik sein, Projekt ist super, aber: fehlen für ein normales Mühlespiel nicht ein paar Felder ?

nice, ich hab auch lächeln müssen @video

sind die LM317 wirklich nötig für die servos? wie hoch ist deine versorgungsspannung? unter 8V schliesse ich meine servos direkt an und der atmega erzeugt das pwm-signal. das hat bisher immer geklappt, und meine L78S05 werden nicht belastet. ist aber nur ein gedanke.

ich habe vor 2-3 monaten ein mühlespiel in c programmiert allerdings "all virtual". an der KI bin ich aber gescheitert, so dass man nur im netzwerk spielen konnte. (fällt mir nur grade so ein)

in welcher sprache hast du es programmiert? n bissl beispielcode würde wohl manche augen hier erglänzen lassen..

ja, picnick, da scheinen 8 felder zu fehlen. ob man allerdings eine echte mühle-KI in einen atmel packen kann, wage ich zu bezweifeln.

gruesse, eure katz

Oh, ganz vergessen: Es ist einfache Mühle... :)
Der Bot verliert nicht. Wenn der Gegner einigermassen klar im Kopf ist dauert so das Spiel unendlich lange. Der Bot macht keine Fehler.
Versorgungsspannung vom Trafo (12V) im Leerlauf sind 17V... Also nix für Servos. Jo, für die echte Mühlen-KI wars zu dick, zu viele Möglichkeiten und Strategien. Ich hab mit einem ETH-Prof gesprochen, der damals das Mühlespiel komplett identifiziert hat (alle möglichen Situationen )das sind Daten über 2GB... Sein Bot hat alle möglichen Situationen gespeichert und führt auf jede Situation den passenden Zug aus..

Meine KI denkt 2 Ebenen tief, d.H. er betrachtet alle Möglichkeiten, die er selber fahren kann, und danach noch alle folgenden Möglichkeiten, die der Gegner fahren kann. (Minimax-Algorithmus). Ich verwende keine "Vereinfachungsstategien" wie Alpha-Beta Pruning, er braucht eh nur 300ms um den Zug zu berechnen.

Programmiert in Bascom, sind ca. 1200 Zeilen bis jetzt, werden wohl noch 500 mehr.

Hier mal ein Codeschnipsel:

Code:

---

Ebene2:

If Spielphase = 0 Then

'Aus dem Ebene1-Array müssen schrittweise die Feler ausgelesen werden. Dann wird daraus jeweils ein neues Feld erzeugt, welches dann bewertet wird.


For I = 1 To Zugzahl                                        ' Zugzahl aus voriger Routine. Es müssen die jeweils leicht veränderten Felder ins Momfeld eingetragen werden.
Zugzahl2 = 0
A = I - 1
A = A * 9

For M = 1 To 9
A = A + M
If Ebene1(a) = 0 Then                                      'Hier wird bestimmt, wieviele Züge man vom Knoten der ersten Ebene in die zweite Ebene machen kann.
Incr Zugzahl2
End If
A = A - M
Next M

For B = 1 To Zugzahl2
C = 1
A = I - 1
A = A * 9

For J = 1 To 9

A = A + J
If C = 1 Then

If Ebene1(a) <> 0 Then
Momfeld(j) = Ebene1(a)
Elseif Ebene1(a) = 0 Then
Momfeld(j) = Gezogenezuege2                                ' Der (virtuelle) Gegner ist nun dran mit setzen.
Ebene1(a) = 10
C = 2
End If

Elseif C = 2 Then                                         
Momfeld(j) = Ebene1(a)

End If

A = A - J
Next J

For D = 1 To 9
If Momfeld(d) = 10 Then                                    ' Die 10s werden durch 0 ersetzt.
Momfeld(d) = 0
End If
Next D

Gosub Bewerten                                              ' Hier wird das momentane Momfeld zur Bewertung geschickt.Es wird hierher zurückgekehrt

Next B
Next I

For I = 1 To 81
If Ebene1(i) = 10 Then
Ebene1(i) = 0
End If
Next

---

Hier berechnet er alle möglichen Züge, die der Gegner nach seinem Zug machen kann, falls man noch in der ersten Spielphase ist (Steine setzen), diese speichert er in einem Array.

Der Code ist sehr "holprig" geraten, man könnte noch viele Variablen einsparen und verbessern, das lass ich vorerst aber, never change a running system...
Entwickelt hab ich die Speicherstrategien und Abläufe auf einem A3-Block, hat sich super bewährt!

Zitat:

---

Zitat von Murus

Oh, ganz vergessen: Es ist einfache Mühle... :)
Der Bot verliert nicht. Wenn der Gegner einigermassen klar im Kopf ist dauert so das Spiel unendlich lange. Der Bot macht keine Fehler.
Versorgungsspannung vom Trafo (12V) im Leerlauf sind 17V... Also nix für Servos. Jo, für die echte Mühlen-KI wars zu dick, zu viele Möglichkeiten und Strategien. Ich hab mit einem ETH-Prof gesprochen, der damals das Mühlespiel komplett identifiziert hat (alle möglichen Situationen )das sind Daten über 2GB... Sein Bot hat alle möglichen Situationen gespeichert und führt auf jede Situation den passenden Zug aus..

---

Ist Mühle wirklich so komplex? Ich hätte gedacht, das sei relativ problemlos in Echtzeit zu beachten, da es ja nicht soo viele Mögliche Zustände und Zugmöglichkeiten gibt (im Gegensatz z.B. zu Schach).

Ja, für mich war es zu komplex... Es gibt doch noch einige Taktiken, die man eventuell nicht mit dem Minimax-Algorithmus hätte lösen können und in einer Bibliothek hätte ablegen müssen.

Zitat:

---

Zitat von Murus

Ja, für mich war es zu komplex... Es gibt doch noch einige Taktiken, die man eventuell nicht mit dem Minimax-Algorithmus hätte lösen können und in einer Bibliothek hätte ablegen müssen.

---

Ja, das mit den Taktiken stimmt. Ähnliche Probleme hatte ich vor einiger Zeit bei einem Vier-Gewinnt-Programm. Der Computer spielt dann zwar in gewisser Weise perfekt, aber eben ohne echte Taktik - vlg. Fussball-WM...

So, hier mal ein weiteres, etwas besseres Video.
Hier platziert er den Stein einigermassen zufällig auf die einzelnen Felder und schaut, ob der Sensor anspricht.
Z.T. müssen die Steine nicht ganz mit dem weissen Feld übereinstimmen, denn der Sensor befindet sich nicht immer genau unter dem weissen Feld..., hab da etwas ungenau gearbeitet, leider... Also nicht wundern, wenn er den Stein "danebenstellt" :)
Aber er steuert unterdessen alle Felder fehlerlos an.

Limitierender Faktor in Bezug auf die Betriebsdauer ist der Elektromagnet, bei 50°C lass ich ihn abkühlen...

Hier der Link:
http://video.google.de/videoplay?doc...68472960615592

Herzlichen Gruss
Mario

der ganze aufbau sieht sehr schön gemacht aus finde ich.

mfg

Judihui, heut hab ich mal meine Softwarestückchen zusammengesetzt, und siehe da, die Mühle spielt das Spielchen tatsächlich! Er verliert nie, und den Trick, mit dem man ihn besiegen könnte, hab ich ihm gelehrt, sodass er ihn zwar verhindert, den Trick selber kann er jedoch (noch) nicht anwenden.
Das Proggi ist nun 16.6 Kb gross, belegt 12% des Mega-Speichers und ist knapp über 1400 Zeilen lang.

Herzlichen Gruss
Mario

Hallo

Ein Video währe toll, also wo man sieht, wie er auf einen Zug von dir reagiert.

mfg Luca

Kommt in den nächsten Tagen... :)
Momentan beginnt er noch zu ziehen.
Danach sagt er, ich sei dran, ich setze und bestätige mit dem Taster beim LCD. Falls der Stein vom Sensor erkannt wurde, reagiert er mit einem Zug. Falls nicht, gibt es eine Fehlermeldung, ich kann den Stein korrigieren, damit der Reed anzieht und wieder mit dem Taster bestätigen.
Er hat aber noch keine Ausgabe, dass er gewonnen hat...
Einen Verlier-Algorithmus programmier ich gar net erst, er verliert nie.

Ein echt gelungenes Projekt, ist echt n tolles "Spielzeug"^^

Soodele, hier nochmals ein kleines Video. Er spielt ne kleine Partie gegen mich, ich lass ihn gewinnen. Im Vid beginnt er noch zu ziehen, das hab ich unteressen geändert, jetzt kann der Mensch zu ziehen beginnen.

http://video.google.de/videoplay?doc...32664489&hl=de

Herzlichen Gruss
Mario

Hallo

Sieht gut aus, aber er positioniert die Steine nicht sehr genau, das ist ein bischen schade. Aber sonst sehr gelungen.

mfg Luca

Er positioniert die Steine sogar hochgenau! Ich hab ihm gesagt, er soll sie haargenau dort hinstellen, wo er sie jetzt hinstellt. Der Reed-Sensor ist nämlich nicht genau unter dem weissen Feld, also muss er die Figuren leicht versetzt hinstellen... :)

Zitat:

---

Zitat von Murus

Ich hab mit einem ETH-Prof gesprochen, der damals das Mühlespiel komplett identifiziert hat

---

Wie hieß denn dieser Prof?

Cooles Projekt übrigens! Echt gut

Der Profi heisst "Ralph Gasser". Sein "Partner" ist "Jürg Nievergelt".

respekt, wirklich super projekt und coole videos

Hm, was mir noch aufgefallen ist:
Während dem Spiel gibt es keine Siegestaktikt.. Man kann einfach keine "Zwickmühle" aufbauen... Der Sieg beruht darauf, dass der Gegner einen Fehler macht...
Nur beim Setzen der Steine ist es möglich, eine Zwickmühle zu setzen, dann kommt man aber nie in die "Hüpfphase" des Spiels... Ich kann die Kiste also nicht aggressiver machen...

Herzlichen Gruss und Danke
Mario