Die Mathe-Redaktion - 13.12.2018 10:08 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 605 Gäste und 16 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » KI für Qwirkle-Spiel: Suche nach guter Strategie
Druckversion
Druckversion
Autor
Schule J KI für Qwirkle-Spiel: Suche nach guter Strategie
nullptr
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 17.12.2016
Mitteilungen: 56
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-07-16

\(\begingroup\)
Hallo zusammen!

Ich möchte das Spiel Qwirkle implementieren, am liebsten mit einer halbwegs starken KI für den Computergegner. Mein Problem ist, dass ich nur ziemlich triviale Heuristiken kenne, die sich gut programmieren lassen. Beispiele:
  • Lege nur dann 5 Steine in eine Reihe, wenn der Gegner den 6. Stein garantiert nicht bekommt (alle drei Exemplare liegen schon oder man selbst besitzt sie).
  • Wenn in mehreren aufeinanderfolgenden Zügen nur wenige (z.B. $\le 4$) Punkte möglich sind, tausche alle Steine aus.
  • Lege immer ein Qwirkle, wenn das möglich ist.
  • Spiele Züge, die möglichst viele Punkte bringen.
Das sind einfache Ideen aus Spielerfahrung. Ich fürchte aber, dass nur ein schwacher Gegner herauskommt, wenn man das stumpf programmiert. Für den Menschen ist der Gegner vermutlich leicht zu durchschauen und er verwendet zu wenig Tricks, um Punkte zu erzielen (z.B. geschicktes Aufteilen von Zügen).

Für Spiele mit perfekter Information wie 4-Gewinnt oder Schach könnte ich eine Tiefensuche machen (bzw. Minimax-Algorithmus). Bei Qwirkle sind die Steine des Gegners aber nicht bekannt, höchstens Wahrscheinlichkeiten. Zwar ließe sich theoretisch mit einer gigantischen Suche der Erwartungswert ausrechnen, aber das erscheint mir außerordentlich kompliziert und mangels Rechenleistung nicht durchführbar. Zudem gibt es pro Zug sehr viele Möglichkeiten. Hat man z.B. 6 Steine, dann gibt es 63 nicht-leere Teilmengen und die Reihenfolge der ausgespielten Steine kann auch eine Rolle spielen, weil sich dadurch ggf. neue Stellen zum Anlegen eröffnen. Schon ein einziger Stein passt oft an viele Stellen und daher ist die Berechnung des eigenen Zugs mit maximaler Punktzahl schon eine Herausforderung, ganz zu schweigen von der Betrachtung gegnerischer Züge.

Über neuronale Netze habe ich auch schon nachgedacht, kenne mich in der Materie jedoch nicht gut genug aus und schätze die Erfolgschancen eher gering ein. Da über Markov-Entscheidungsprobleme heranzugehen sieht mir ebenfalls schlecht aus, weil es zu viele Zustände gibt.

Nun fehlt es mir an Ideen, eine brauchbare Strategie für dieses Spiel zu berechnen. Hat da jemand einen Vorschlag? Gern auch allgemeine Ansätze und Algorithmen, Spiele zu gewinnen ;)

Gruß
nullptr
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2942
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-07-16


Hallo nullptr,

ich bekunde da einfach mal Interesse an der Aufgabenstellung :) Ich würde so etwas angehen, indem ich erst einmal versuche, ein Gefühl für das Spiel zu bekommen, zB indem ich es selber spiele ( das wirst du schon getan haben, wenn du es gar programmieren willst - war also nicht als Tip gemeint sondern auf mich selber bezogen). Die Regeln sind ja auch im Wiki Artikel zu dem Spiel angegeben. Es wird also etwas dauern, bis ich da mit vernünftigen Vorschlägen um die Ecke kommen kann. Fachmann für neuronale Netze bin ich da nicht, eher kenne ich mich mit Markow Ketten aus ( das wäre in diesem Fall aus der Rubrik "hidden Markov", da wir ja Parameter haben, die wir nicht kennen ). Wenn wir es als kleines Projekt angehen wollen wäre natürlich auch ein Computerturnier reizvoll, da würdest du / würden wir hier auf dem MP sicher interessierte Mitstreiter finden!

Grüsse aus dem Harz
Gerhard/gonz



-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2942
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2018-07-16


Nachtrag:

Einen Ansatz über Markov Ketten kann ich auch nicht als zielführend erkennen, gar nicht mal wegen der grossen Anzahl von Variablen ( das wäre ja für einen Computer handhabbar, es gibt 36 verschiedene Steine ), sondern eher auf grund der hohen Anzahl der verborgenen Informationen ( im wiki Beitrag heisst es ja auch sinngemäß, das Spiel würde eine große Menge an Glückselementen enthalten ).

Eine Frage ist erst einmal, inwieweit ein Element des "Bluffens" enthalten ist. Kann ich davon ausgehen, dass mein Gegenüber immer alles auslegt, was er auslegen kann? Dann könnte ich natürlich schon Rückschlüsse auf seine Steine ziehen, was mir natürlich nur dann hilft, wenn er wenige Steine tauscht. Ich kenne allerdings dann ggf. auch die Situation im "Vorrat" bevor er tauscht, denn ich weiss ja, was ich auf der Hand habe, und kann aus der Situation, dass er nichts auslegen kann, Rückschlüsse auf seine Steine ziehen - und nur der Rest ist ja im Vorrat.

Das bedeutet natürlich auch, dass je kleiner der Vorrat ist umso besser die Chancen sind, da etwas abschätzen zu können. Man könnte ggf. mit "Endspielen" anfangen.


Es wäre vielleicht auch sinnvoll, wenn man mal suchen würde, ob irgendwo im grossen weiten Netz Spieler mal ihre Strategie gepostet haben, oder gibt es auf dem MP gar begeisterte Qwirkle-Spieler, die mal einen Blick in die "Trickkiste" erlauben?

Immer noch interessiert -
Gerhard/gonz



-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 5578
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2018-07-16


Was genau ist Deine Motivation?

Ein Qwirkle-spielendes Computerprogramm wäre für mich als Spielpartner interessant. Da es in diesem Spiel einen großen Zufallseinfluss gibt (ziehe ich den passenden Stein, oder zieht ihn der Gegner) würde auch ein nicht optimal spielendes Programm des Öfteren gewinnen. Gegenüber "normalen" Menschen hätte ein Programm auch den Vorteil, keine guten Züge zu übersehen.
Bevor ich mir Gedanken über eine Spielstärken-Verbesserung mache, würde ich erstmal schauen, ob die bereits genannten Ansätze nicht bereits ausreichen, damit der Computer als Mitspieler gut genug ist.

Als Erweiterungsansätze sehe ich folgende Möglichkeiten:
a) Für jeden eigenen Zug berechnet man den Erwartungswert der besten gegnerischen Antwort und bezieht das Ergebnis in die Bewertung mit ein. Züge, die zwar kurzfristig mehr Punkte bringen, aber dem Gegner auch sehr gute Möglichkeiten eröffnen, werden dadurch vermieden.
b) Die Berechnung aller Möglichkeiten, welche Steine der Gegner haben könnte, kann (vor allem am Anfang) sehr aufwändig sein. Hier käme als Alternative eine Monte-Carlo-Simulation in Frage.
Das wäre auch eine Option, um mehr als einen Zug in die Zukunft zu schauen, insbesondere im Endspielen.

c) Als Alternative zur Berechnung des Erwartungswertes des besten Zuges, könnte man auch abschätzen, mit welcher Wahrscheinlichkeit der Gegner im nächsten Zug ein Qwirkle erreichen kann.



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2842
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2018-07-16


Für das Spiel sehe ich nicht direkt, wie man sich hier mit einem Neuronalen Netz der Sache nähern kann. Mir schwebt noch immer vor, mich dabei einem anderen Spiel zu widmen: EinStein würfelt nicht. Das hat den Vorteil, dass es qua Format ganz gut zur Struktur von Deep-Learning-Netzwerken passt, aber so klein ist, dass die für das selbstforcierte Lernen notwendigen Spiele relativ schnell erzeugt werden können müssten.

Interessant wäre dabei die Frage, wie gut so ein NN mit der Zufallskomponente umgehen kann.

Das Ganze wäre mehr ein Hobby-Projekt, vielleicht vergleichbar mit einer Mikro-Version von AlphaGo o.Ä., nur eben mit einem Spiel ohne volle Information.

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
nullptr
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 17.12.2016
Mitteilungen: 56
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2018-07-17

\(\begingroup\)
Vielen Dank für eure Antworten!

Zur Motivation: Ist ein Freizeitprojekt und bestenfalls hilft die KI dabei, die eigene Spielstärke zu verbessern.

Zum Bluffen: Es kommt auf jeden Fall vor, dass ein Spieler bewusst nicht den punktbesten Zug spielt, z.B. um die Punkte über mehrere Züge zu vermehren (statt 4. und 5. Stein in eine Reihe (5 P.) erst den 4. Stein (4 P.) und dann im nächsten Zug den 5. Stein (weitere 5 P.)). Ich bewahre gute Steine  manchmal auf und warte damit auf eine Qwirkle-Chance. Denkbar ist auch, einen Qwirkle nicht zu spielen, um längere Zeit mehr Steine und damit Chancen auf mehr Punkte zu haben (trotzdem ist ein Qwirkle mit 12 P. zumeist ein sehr guter Zug). Sind bereits die meisten Steine gelegt, kann es sein, dass man sogar einige gegnerische Steine kennt (aus seinem Spielverhalten, z.B. Nichtnutzen von Legemöglichkeiten oder weil wirklich wenige Steine im Beutel sind).

Zu weiteren Ansätzen: Bei a) scheint es mir schwierig, den Erwartungswert der besten gegnerische Antwort zu finden. Selbst wenn schon die Hälfte der Steine liegt, gibt es noch $108/2 - 6 = 48$ übrige Steine und damit $\displaystyle \binom{48}{6} \approx 10^7$ Hände des Gegners. Für jeden eigenen Zug all diese Hände zu betrachten (das wäre wohl dein Ansatz b)) und jeweils den besten gegnerischen Zug zu finden wird auf einem üblichen PC schwierig, wenn auch möglich (bei weniger als 6 Steinen auf der Hand und/oder weniger als 48 übrigen Steinen ist es sicher nicht aussichtlos). Zu c): Das könnte z.B. hilfreich sein, wenn der Gegner das Spiel mit seinem Qwirkle beenden würde, dann kann man schnell einen Zug mit möglichst vielen Punkten spielen. Oder man kann den Qwirkle auch mitten im Spiel durch eine Blockade verhindern.

Ich habe auch noch eine Überlegung zur Anzahl der Züge: Es gibt bei $1 \le n \le 6$ Steinen nicht mehr als

\[ \sum_{k = 1}^n \binom{n}{k}k! = \sum_{k = 1}^n \frac{n!}{(n - k)!} \le 1956 \]
Möglichkeiten, die Steine für einen Zug zu wählen (in der Praxis sind es meistens sehr viel weniger, weil alle gespielten Steine dieselbe Form oder Farbe haben müssen). Da jeder gelegte Stein höchstens $3$ freie Seiten hat und man an einen Stein mit derselben Farbe (davon gibt es $18$ Stück) oder derselben Form (auch $18$) anlegen muss, gibt es weniger als $3 \cdot 36 = 108$ Möglichkeiten, einen Stein irgendwo anzulegen. Auch das sind in meisten Fällen erheblich weniger, sodass alle Züge aufzählen wahrscheinlich machbar ist.

Zu EinStein würfelt nicht: Zumindest auf den ersten Blick sieht das Spiel einfacher aus als Qwirkle (im Sinne von: Es gibt weniger Zustände und Zugmöglichkeiten, sodass ein Computergegner leichter zu realisieren ist. Ein Indiz dafür ist auch die App mit einstellbarer Elo-Zahl. Wobei ich natürlich nicht weiß, wie viel Arbeit reingestreckt wurde und wie aufwendig Qwirkle tatsächlich ist). Sollte der Einsatz NN hier schon nicht ganz einfach sein, erwarte ich bei Qwirkle wenig.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
nullptr hat die Antworten auf ihre/seine Frage gesehen.
Das Thema wurde von einem Senior oder Moderator abgehakt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2018 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]