Vier verliert

Team Name: Vier gewinnen @ Institut: IAS

Vier verliert ist ein Plastikhaufen, gegen den man auf einem handelsüblichen Vier-Gewinnt-Feld spielen kann. Dazu verwendet er einen ausgeklügelten Algorithmus, um dem Spieler das Gewinnen zu ermöglichen.{readmorelink}Weiter zum Beitrag.{/readmorelink}

Inspiriert von einem Tic-Tac-Toe spielenden Roboter, wollten wir ein etwas komplexeren Robotor schaffen, der dennoch in der vorgegeben Zeit zu realisieren war. Nach mehrmaliger Anpassung des Gerüsts zu einer (relativ) stabilen Konstruktion und langen Verhandlungen um diverse Bauteile, kam schließlich dieser Roboter zustande:

Hardware:

Folgende Teile wurden zur Konstruktion verwendet:

 

  • 3 Motoren
  • 2 Drucksensoren
  • 1 Farbsensor
  • Diverse Lego-Teile

 

Achsensteuerung

Achsensteuerung:

Zwei Motoren wurden zur Achsensteuerung verwendet um den Farbsensor (XY-Achse) und den Einwerfer (X-Achse) zu positionieren:

Die Ansteuerung der einzelnen Löcher des Vier-Gewinnt-Felds geschah über konstante Offsets ausgehend von der Nullposition, die der Roboter selbständig bestimmen konnte, unter Verwendung des:

 

 

 

 

 

Home-Sensor:

Ein Tastsensor wurde oben-links (Frontansicht) angebracht. Dieser Taster war in der Nullposition (X) aktiv. Dadurch konnte der Roboter diese Position immer wieder anfahren, unabhängig von seiner ursprünglichen X-Position. Insbesondere konnte mit voller Geschwindigkeit durchgängig zur Ausgangsposition gefahren werden, nachdem etwa das Spielfeld gescannt oder ein Stein gespielt wurde. Dies verkürzt die Wartezeiten. Die Y-Position musste zum Start 0 betragen, ein weiterer Sensor war allerdings nicht nötig, da die Steuerung auf dieser Achse zuverlässiger funktionierte.

 

 

Farbsensor:

Zum Scannen der gelben und roten Spielsteine wurde ein Farbsensor (Hightechnic) verwendet. Dieser wurde auf einem Schlitten auf der Y-Achse angebracht und konnte so über die Achsensteuerung alle Positionen scannen. Der Sensor lief im aktiven Modus, um die Messung vom Umgebungslicht unabhängig zu machen.

Einwerfer:

Auf dem oberen Spielfeldrand, ebenfalls verbunden mit der X-Achsensteurung, fuhr der Einwerfer mit. Der Zug des Roboters wurde ausgeführt, indem eine Position angefahren wurde und anschließend ein Stein eingeworfen wurde. Dies geschah über den dritten Motor, der durch Rotation eines Einwurfarmes ein Stein aus dem Magazin in den Einwurfschacht beförderte.

NXT:

Die Intelligenz unseres Roboters wurde als Gegengewicht zum Einwerfer auf der gegenüberliegenden Seite der X-Achse montiert. Dies reduzierte außerdem die Reibung des Einwerfers auf dem oberen Spielfeldrand.

Bestätigungssensor:

Neben dem NXT war ein Drucksensor befestigt, um einerseits das Gewicht des Einwerfers auszugleichen, aber in erster Linie zum Bestätigen eines Zugs betätigt werden musste.

Software:

Die Software zum Vier-Verliert Roboter wurde grob in drei Teile aufgeteilt:

NXTController:

Zur Ansteuerung wurde eine Klasse (NXTController) implementiert, die sich um die Kommunikation zwischen Hardware und Software kümmert, so dass im Hauptprogramm beispielsweise nur eine Funktion dieser Klasse aufgerufen wird und eine Instanz der Klasse Board zurückgibt.

Board:

Die Hilfsklasse Board stellt Funktionen bereit um beispielsweise Steine zu setzen oder zu entfernen oder das Spielfeld zu bewerten (siehe KI). Außerdem kann ein Objekt der Klasse Board als Feld dargestellt werden (im Video im Hintergrund zu sehen).

KI:

Minimax

Den dritten Teil der Software stellt die KI des Roboters dar, eine Implementierung des bekannten Minimax-Algorithmus. Der Algorithmus geht rekursiv alle möglichen Züge und Folgezüge durch und wählt letztendlich den Zug, der dem Computer den höchsten Gewinn bringt (Gegnerzüge werden als Minuspunkte gezählt). Der Algorithmus ist nicht auf ein konkretes Spiel beschränkt und kommt beispielsweise auch bei Schach oder Tic-Tac-Toe zum Einsatz. Die Abbildung zeigt den Minimax Algorithmus für zwei mögliche Züge. Die Kreise sind die Züge von Spieler 1. Dieser versucht die Punktzahl zu maximieren. Die Quadrate sind die Züge von Spieler 2. Dieser versucht den Punktzahl zu minimieren.

Um die Punktzahl zu ermitteln, muss dem Algorithmus mitgeteilt werden, wie eine bestimmte Spielsituation zu bewerten ist. Dies ist in unserem Fall in der Klasse Board implementiert, die alle möglichen Gewinnmöglichkeiten (insgesamt 69 bei Vier-Gewinnt) durchgeht und schaut wie viele Steine ein Spieler in einer bestimmten Kombination bereits hat.

Die Bewertung funktioniert folgendermaßen:

    • Steine Beider Spieler in einer Kombination: 0 Punkte
    • 1 Stein in Kombination: 1 Punkt
    • 2 Steine in Kombination: 10 Punkte
    • 3 Steine in Kombination: 50 Punkte
    • 4 Steine in Kombination: 10000 Punkte

Die Werte und auch die Bewertungsfunktion beeinflussen die Spielweise der KI und sind natürlich nicht optimal gewählt, allerdings konnte dies in kurzer Zeit realisiert werden und funktioniert auch recht gut (siehe Video).

Das berechnen der Züge erfordert einen hohen Rechenaufwand, da die Größe des Suchbaums exponentiell wächst. Unter Annahme, dass das Spielfeld zunächst leer ist, gibt es sieben mögliche Züge, so dass die Größe des Suchbaums 7Suchtiefe entspricht. Um die Wartezeit möglichst kurz zu halten, simuliert die KI in der aktuellen Einstellung (auch im Video) nur bis zu einer Suchtiefe von 2, dass heißt nur den eigenen und einen folgenden Gegnerzug. Durch diese Beschränkung lässt einem der Roboter die Chance zu gewinnen, da die meisten Spieler häufig auch 2 bis 3 Züge im Vorraus handeln. Ab einer Suchtiefe von 4 oder höher gewinnt die Minimax-Algorithmus in Vier-Gewinnt normalerweise immer, da menschliche Spieler so weit nicht für ale Züge denken können. Durch die variable Suchtiefe ist die Stärke der KI allerdings hervorragend skalierbar und es können beliebige Schwierigkeiten gewählt werden.

Verbesserungsmöglichkeiten:

  • Implementierung des Alpha-Beta-Algorithmus: Der Alpha-Beta-Algorithmus (auch Alpha-Beta-Cut) stellt eine wesentliche Verbesserung des Minimax-Algorithmus dar. Durch eine Heuristik wird ermittelt, welche Teilbäume nicht mehr durchsucht werden müssen, da sie das Ergebnis nicht beeinflussen können. Dadurch verringert sich der Rechenaufwand erheblich, etwa um 91%[wikipedia] .
  • Verwendung stabilierer Materialien: Lego eignet sich durch den verwendeten Kunststoff nicht um stabile größere Konstruktionen zu bauen. Dadurch wäre die Konstruktion bespielsweise transportabel und weniger Anfällig für Berührungen und generelles Fehlverhalten gewesen.
  • Stärke der Motoren: Durch das hohe Gewicht des Aufbaus und die geringe Stärke der Motoren musste eine hohe Untersetzung gewählt werden. Durch schnellere und stärkere Motoren könnte beispielsweise die Anfahrtsgeschwindigkeit von Positionen enorm erhöht und somit Wartezeiten drastisch verkürzt werden.

 

Fazit:

Der Vier-verliert-Roboter sorgt für lang anhaltenden Spielspaß für 3 bis 99-jährige. Unser Anti-Frustrationsalgorithmus (Minimax nur bis Suchtiefe 2) lässt auch ab und zu durchschnittliche Spieler gewinnen und ist somit für ein breites Spielerspektrum geeignet. Durch die gute Dokumentation der Pflichtversuche wurden uns ausreichende Kenntnisse im Umgang mit Matlab und Lego-Mindstorms vermittelt, was uns die Ferstigstellung des Roboters Vier-verliert innerhalb des kurzen Zeitraums ermöglichte.

Video-Demo

 


 

Roboter Wintersemester 2013/14

  • Team Name: Die J.A.M.M.M.E.R. @ Institut: TI Die J.A.M.M.M.E.R. konstruierten insgesamt 3 Projekte. Das Hauptprojekt ist die 3D-Fräse. Nebenprojekte sind eine
    Weiterlesen
  • Team Name: Vier gewinnen @ Institut: IAS Vier verliert ist ein Plastikhaufen, gegen den man auf einem handelsüblichen Vier-Gewinnt-Feld spielen kann.
    Weiterlesen
  • Team Name: Die Kneppster @ Institut: IND Unser Ziel war es, einen intelligenten und v.a. interaktionsfähigen Roboter zu konstruieren. Da bot
    Weiterlesen
  • Team Name: JukeboNXT @ Institut: IENT UNFERTIG Der JukeboxRobo liest einen Farbcode aus und spielt korrespondierende Töne ab. Für diesen Zweck
    Weiterlesen
  • Team Name: TheHotWheels @ Institut: IFHT Ferngesteuerter Fahrroboter "Kaller". Interaktive Steuerung per Tastatur oder Maus, Synchron-Heckantrieb mit Einzelradaufhängung, Lenkung der Vorderräder
    Weiterlesen
  • Team Name: L&S SmartTouch @ Institut: LfBS TouchSmart ist ein Roboter, der den Touchscreen des Motorola Razers bedienen kann. {readmorelink}Weiter zum
    Weiterlesen
load more hold SHIFT key to load all load all

Aktuelles

  • 1
  • 2
  • 3
  • 4
  • 5

Kontakt

Bei weiteren Fragen bzgl. des Projekts - MATLAB meets LEGO Mindstorms - wenden sich Externe bitte an Marcin Kpaczka.

Fragen von Projektteilnehmern werden dagegen im Diskussionsforum des projektspezifischen L²P Lern- und Lehrportals unter
www.elearning.rwth-aachen.de beantwortet.

Login

Copyright © 2017 Mindstorms - Projektseite. Alle Rechte vorbehalten.
Joomla! ist freie, unter der GNU/GPL-Lizenz veröffentlichte Software.