Mühle spielender Roboter

[Murus]

Tja, das wird das Thema meiner Maturaarbeit. Ziel ist es, einen (Greifarm)-Roboter zu bauen, der Mühle spielt.
Wollte eigentlich nur mal eure Meinung hören. Hat schonmal jemand so etwas ähnliches realisiert? (Spielbäume, MinMax, Heuristik etc.)

Hier mal meine Ideen:
Greifarm: 3 Servos, Elektromagnet
Spielfeld: per Reedsensoren digitalisiert und gemultiplext
Chip: Mega32 @ 16Mhz, falls nötig mit externem Eeprom

Dann gilt: Mensch gegen Maschine.
Das schwierigste wird, den Spielbaum (der Chip überlegt sich alle Züge und Folgezüge des Geners, bewertet diese nach bestimmten Kriterien und wählt dann den besten Zug) und die Heuristik (Zugbewertung) im Chip zu realisieren... Das wird einiges an Know-How, Speicher und Rechenleistung brauchen...
Wie bringt man das Ding dazu, die einzelnen Züge sich zu überlegen und zu bewerten... Und das alles mit Bascom... :-k

Aber mein Mathelehrer ist genial, mit dem hoffe ich, das zu packen. Und sonst rüsten wir das Mühlefeld auf Bauernschach um, ist einfacher.

Hat jemand von euch schon Erfahrungen in diesem Bereich gesammelt?

Herzlichen Gruss
Mario

[super_castle]

bascom und mathe..ne..ne...

wenn du schon so etwas ansetzen tust, dann nimmst du winavr-c oder microbasic avr.

die hardware ist nicht schwer umzusetzen, ist eine fleissarbeit. braucht man nicht viel zu denken.

die schachzüge kannst du aus alten qbasicprogrammen herausholen. sind klein in der struktur und sehr effektiv.

Castle

[gast1234]

Die, nennen sie wir mal, "KI" ist gar nicht so schwer.
Du musst erstmal die Regeln eingeben, a la Zustandsänderung aus der Graphentheorie. Du brauchst eine Computerinterne Repräsentation des Spielfeldes, vielleicht array oder so. Wichtig ist, dass der Computer aus einer Spielfeldkostellation alle möglichen Züge berechnen kann. Des weiteren wie bereits erwähnt eine Bewertungsfunktion, da kann man schön rumprobieren.
Letztendlich lässt du dir alle x möglichen Züge berechnen, und ausgehend von den x Spielfeldern, die aus den x Zügen hervorgehen, lässt du dir wieder alle möglichen Züge errechen. Dies machst du bis zu einer gewissen Tiefe. Natürlich fällt und steigt damit der Rechen und Speicherbedarf. Am Ende bewertest du und nimmst den besten Weg.


Beispiel mit einer Tiefe 3

am Zug

Du 1 2 3 4
Gegner 11 12 21 22 23 33 41 42
Du 111 112 113 121 211 212 221 222 223 231 331 411 412 413 414 421 422

Du lässt dir alle möglichen Züge berechnen das sind 1, 2, 3 und 4.
Aus dieser Liste nimmst du den ersten Zug und wendest ihn an und bekommst ein entsprechendes Spielfeld.
Du lässt wieder alle Züge berechnen nämlich 11 und 12. Von denen nimmst du wieder den ersten und wendest ihn an.
Ausgehend von dem Spielfeld, welches sich aus der Anwendung von Zug 11 auf das Spielfeld, welches von der Anwendung aus Zug 1 herrührt, ergibt, berechnest du alle möglichen Züge.
111 112 und 113. Du wendest den ersten Zug 111 an und bekommst ein Spielfeld. Wir sind jetzt in der Ebene 3 also in der Zielebene. Dieses Spielfeld bewertest du nun und merkst dir die Bewertung.
Auf dem Spielfeld vom erfolgten Zug 11 führst du Zug 112 aus und bewertest das Feld. Du hast jetzt 3 Bewertungen, eine für 111,eine für 112 und eine für 113.
Du nimmst die schlechteste und schreibst sie klein neben den Zug 11, nun nimmst du das Spielfeld von Zug 12 und erstellst alle mögl. Züge. Ausgehend davon berechnest du wieder alle Spielfelder und bewertest sie, nimmst die schlechteste bewertung und schreibst sie dir neben 12.
Du nimmst deswegen die schlechteste, weil ja dein Gegner in Ebene 2 am Zug ist und er wird wahrscheinlich, die beste Wahl für sich , also die schlechtest für dich nehmen.
Nun schreibst du die bessere Bewertung von 11 und 12 oben neben die 1, weil du ja in Ebene 1 am Zug bist.
Positive und negative Bewertungswahl wechseln sich also ab, jeh nachdem wer am Zug ist. Die Bewertungsfunktion kann so immer gleich bleiben.
Jetzt lässt du dir von 2 wieder alle Züge erstellen bis unten mit bewertung usw. Du bewegst dich also den Baum von oben nach unten und wieder nach oben und von links nach rechts.
Am Ende steht neben jedem Zug in Ebene 1,2,3 und 4 eine kleine Bewertung. Die beste repräsentiert den Zug, den du machst oder machen solltest.
Soweit erstmal das, Fragen oder schon abgeschaltet?

Gast 2000

[Murus]

Nene, das kapier ich schon! Die Minmax-Methode ist bekannt.
Wollte eigentlich gar net, dass das hier erklärt wird, das mach ich selber, is mir alles klar. Werde auch mit Alpha-Beta-Pruning arbeiten.
Die Spielpositionen speicher ich in ein Array, dann muss ich noch ne Routine schreiben, die mir da die möglichen Züge rausholt. Dann mal per Tiefensuche den erstbesten Zug nehmen, weiter in die Tiefe stossen, bewerten, nächster Zug etc. Wird glaub noch recht Speicher fressen, ich werde ja wohl "virtuelle" Spielfelder aufbauen müssen (die Knoten im Spielbaum) und von denen aus weitergehen... Nehmen wir an, ich gehe in eine Tiefe von 3 Ebenen, dann hab ich schon 24 hoch 3 Bytes nur schon im Array.. Ich denke deshalb auch, ein externes Flash mit 1 MegaBit anzusteuern und dort die Werte reinhauen.

Wegen dem Bascom: Das sollte doch problemlos funktionieren... Ab und zu muss man vielleicht etwas "unorthodox" arbeiten, aber ich halte es für möglich.
Das schwierigste wird die Umsetzung des Spielbaumes im Programm und die Feldbewertung.
Lustig werden auch die verschiedenen Phasen von Mühle.. Am Anfang muss er gescheit setzen, dann auf "schieben" wechseln und zum Schluss noch rumhüpfen, aber das lass ich vielleicht weg. Als Chip werd ich doch dne Mega 32 nehmen, hat mehr Flash.

Jaja, das wird schwer... Hab jetzt knapp 1 Jahr Zeit dafür. Wenn sich in 3/4 Jahr keine Lösung abzeichnen sollte, ziehen wir den Notschalter und wechseln auf Bauernschach.

[HannoHupmann]

Denke das mit dem Roboter ist Kinderfasching, hier geht es eher um reines Programmieren. Für Dame gibt es glaub ich schon einige Lösungen die extrem gut spielen (praktisch unbesiegbar) deswegen hat man sich auch nicht weiter damit beschäftigt. Ich kenn mich wenig mit dem komplexen Programm aus aber ich würd sagen sowas in nen MicroController zu packen ist schon sehr heikel (kommt auf den Prozessor drauf an). Ich würde da eher auf ein Computer gestütztes System gehen.

Sprich schreib mein Programm und lass das Dame spielen und geb über nen Seriellen Port aus was der Greifarm zu tun hat (das geht problemlos, mein Roboter konnte schliesslich auch Klötze Sortieren, was dem Dame sehr nahe kommt und der hing am serrielen Port).

Vorteil du kannst jede IDE nehmen und wirklich ohne Speicherprobleme rumskripten.

Es sei den du hast als klare Vorgabe, dass es ohne PC gehen muss.

[Murus]

Also ich sollte es per Mikrocontroller machen.
Denke schon, dass man das gesamte Programm in 32kB verstauen kann und dann noch auf ein externes Flash die Datenbanken schmeissen. (Irgendein per SPI angesteuerter Flash-Chip von Atmel, muss mal noch gucken, wie ich das lösen kann... wie macht man das? Hat Bascom fertige Routinen, die Variablen direkt in ein am SPI hängenden Flash-Chip brennen kann?)

[Goblin]

nur zum erkennen der spielsteine: nimm doch evtl reflex-optokoppler. weil dann müsstest du kein metall in die steine packen. andererseits: wenn du schon metallische spielsteine hast könntest du natürlich deinen bot mit nem elektromagneten austatten. bestimmt einfacher als nen greifer.

[Spion]

Hi, ich habe schon einmal gegen so ein Roboter gespielt, er steht im Technorama in Winterthur (Schweiz), (vielleicht bist du ja schon da gewesen und hast ihn gesehen?)

http://www.technorama.ch/uploads/pics/muehleroboter.jpg

Also ich erzähle mal alles über diesen Mühle Roboter das ich weis.

Man kann zwischen verschiedenen Schwierigkeiten wechseln, also scheint er dann mehr oder weniger Fehler einzubauen.

Die Kugeln sind aus zwei verschieden Materialien.

Damit sich niemand an dem Roboter verletzen konnte wenn er sich bewegt, ist er, wie man sieht in einem Kasten, an desen Öffnung eine Lichtschranke angebracht ist. Wenn man dann hinein fasst, stopt er automatisch.

Zum greifen hat er, zwei Metallstangen, die sich schliesen und öffnen, an der Spitze hat es dann je eine einbuchtung um die Kugel zu fassen.

So das ist dann mal alles was mir einfällt.

Ich hoffe ich konnte helfen, am besten geht ihr euch denn Robo selbst mal anschauen.


mfg Luca

[Murus]

Ich werde ja einen Elektromagneten für den Greifarm verwenden....
Nen externen Speicher brauch ich net, die 32kB reichen, da ich die Tiefensuche verwende (maximal so 100 Bytes brauch ich so für die Spielzustände abzuspeichern in nem Array)

Herzlichen Gruss
Mario

[Murus]

Hallo,

ich grab das hier mal schnell aus, weil ich euch noch eine erste Fassung des Berichtes zukommen lassen möchte. Es ist noch nicht endgültig, wird von mir und vom Betreuer noch durchleuchtet.
Aber für diejenigen, die es interessiert, ist alles drin, was man braucht.

Edit: Hmm, das Dokument ist zu gross (3MB)... Wo könnte ich das PDF hochladen?

Ah, habs geschafft:
http://www.avrfreaks.net/index.php?module=Freaks%20Academy&func=viewItem&item_id=703&item_type=project

Herzlichen Gruss
Mario

[phaidros]

Also Mühle hab ich selber mal programmiert. Das Ding spielte auf einem Amiga mit Standard Alpha-Beta-Algorithmus schon ganz gut. Inzwischen ist Mühle vollständig gelöst. Google mal nach "Ralph Gasser Mühle". Es ist bei bestem Spiel beiderseits unentschieden. Du brauchst allerdings einige Gigabyte für die Speicherung der Spielzüge. Na gut, auf einem Microcontroller kriegst du maximal einen durchschnittlich guten Spieler hin, denke ich.

[Murus]

Jo, Mit Ralph Gasser hab ich auch kurz gemailt :)
Jürg Nievergelt hat so einen Mühleroboter als Diplomarbeit gebaut... Er steht im Technorama in Winterthur. War uns dann zu "oversized" für ne Maturaarbeit.

[Murus]

So, habs doch noch geschafft:
http://rapidshare.de/files/36926720/Dokumentation_zum_Roboter.pdf

[phaidros]

Herzlichen Glückwunsch. Sehr gelungene Arbeit. Die Idee mit den Magneten und Reed-Kontakten ist clever. Spart den Greifer. Das Ganze sieht auch noch sehr gut aus.
Wie ist denn jetzt der spieltheoretische Wert von "einfacher Mühle" ?
Gewinnt immer der, der zuerst anfängt oder ist es unentschieden?

[Murus]

Also das weiss ich nicht, aber der, der beginnt, kann, wenn er den Kniff weiss, eine Zwickmühle beim Setzen aufbauen, (und auch nur dann) und gewinnen....
Der Roboter kennt diese und verhindert sie, er wendet sie aber selbst nicht aktiv an, da die Sache dann immer zu schnell vorbei wäre ==> zu langweilig.
In der Hüpfphase kann man keine Zwickmühlen aufbauen, da wid einfach gespielt.

Ob einfache Mühle unentschieden ist weiss ich net, Ralph Gasser hat darauf nicht geantwortet...

[ogni42]

Sehr, sehr schöne Arbeit. Herzlichen Glückwunsch!