Kartenspiel-KI: Strategie einprogrammieren oder Machine-Learning

[simpsonsfan]

Hi,

ich würde mal eine etwas allgemein gehaltene Frage an die Runde stellen, was ihr von zwei Alternativen zur Implementierung von Computergegen- bzw. -mitspielern bei nicht zu komplexen aber auch nicht ganz simplen Anwendungsfällen haltet.

Als konkretes Beispiel für einen solchen Anwendungsfall würde ich das Kartenspiel Arschloch anführen (gibt dazu viele regional leicht abweichende Regelwerke; falls ich irgendwann mal hobbymäßig was implementieren werde, werde ich natürlich das mir geläufige hernehmen.) Also ein Spiel, dass jetzt nicht übermäßig komplex ist aber schon einige strategische Elemente mitsamt Kartenzählen und unterschiedlichen Zielsetzungen hat. Man kann versuchen, König zu werden, nicht-Arschloch zu werden. Mehrere Spieler könnten gemeinsam versuchen, den König zu entthronen.

In meiner Denke bieten sich hier zwei Optionen an:

• eigenhändig Strategien entwickeln (oder bereits von anderen Menschen entwickelte hernehmen, im Wikipedia-Artikel zum Spiel ist dazu bspw. ein Buch verlinkt.)
• die Regeln implementieren und ein KNN trainieren, indem man Bots gegeneinander spielen lässt.

Beim KNN stelle ich mir das so vor, dass die Bots zunächst einfach zufällige (regelkonforme) Aktion wählen würden und dann eben eine Zielfunktion maximieren/minimieren sollen. Für die unterschiedlichen Strategien (Königwerden, Arschlochvermeidung) müsste man dann ja lediglich verschiedene Bewertungsfunktionen aufstellen.

Was sind eure Einschätzungen dazu?
Was bringt bessere (kompetentere) Computerspieler?
Was ist mit weniger Aufwand für den Entwickler verbunden?
Wo lassen sich leichter Abstufungen in Schwierigkeitsgraden einbauen?
- Wird für einen schwächeren Spieler beim KNN einfach weniger lang trainiert?
- Arbeitet man bei händischer Programmierung bspw. mit unterschiedlich großem Merkvermögen für die Kartenverteilung?
- Soll man bei hohen Schwierigkeitsgraden schummeln und die Kartenhände aller Spieler zugänglich machen? Muss man beim KNN dazu wieder neu trainieren oder kann man das nachträglich berücksichtigen?

Ihr könnt gerne auch Material verlinken, das ihr für diese Fragestellungen für brauchbar haltet. Ich muss gestehen, dass ich gerade erstmal diesen Thread erstelle und noch nicht großartig gesucht habe.
Das soll auch ein bisschen einfach als Austausch und zur Diskussion dienen.

Also, was immer hier zu dem Thema habt, nur her damit!

 

[Tornhoof]

Les dir mal durch wie schachengines Schwierigkeitsgrade abbilden, das ist vglw. gut dokumentiert. Die Konzepte lassen sich auch auf andere Spielarten abbilden. Also zb Suchbäume, da lässt sich gut die suchtiefe variieren

Die üblichen KI Konzepte bei spieleengines die ich kenne sind alles recurrent neural networks da die gut mit sequentiellen Daten funktionieren.

 

[BeBur]

Ich würde Reinforced Deep Learning "Q-Learning" umetzen, OpenAI Gym bietet das an. Das sollte relativ easy zu implementieren sein und sehr gute Ergebnisse erzielen. Meine Erinnerung mag mich täuschen, aber ich meine es gibt auch Parameter an denen man zwecks verschiedener Schwierigkeitsgrade schrauben kann.

ein KNN trainieren

KNN wie in "k-nearest neighbours"? Bei KNN wird kein Modell antrainiert. Es ist auch kein Optimierungsverfahren, es gibt dort keine Zielfunktion. Ich sehe spontan gar nicht, wie man KNN in diesem Kontext einsetzen könnte, wenn man wollte (was ich bezweifel).

 

[Tornhoof]

KNN

Knn ist die deutsche Übersetzung von ANN

 

[simpsonsfan]

An sowas wie Suchbäume mit variierender Tiefe hätte ich auch schon gedacht, bzgl. Schwierigkeitsgraden.
Das Q-Learning und Recurrent Neutal Networks werde ich mir dann auch mal anschauen, danke für die Schlagwörter.
Und so als reine Meinungsfrage, gefallen euch dazu KI-Ansätze besser oder "klassische Programmierung".

 

[Keylan]

Also zum Thema ANN-KI und Schwierigkeitsgrade. geringere Schwierigkeitsgrade brauchen nicht weniger Trainingszeit, sondern entsprechend andere Zielfunktionen.

Zum Thema welcher Ansatz ist besser?

Ich sehe das abhängig davon wie die Finale Implementierung aussehen soll. Um ANN-KI zu trainieren braucht man Daten, wo kommen die her?
Wenn man die ANN-KI mit Bot's trainiert, musste man ja die Bot's vorher entwickeln die schon haben die das eigentliche Ziel bereits erfüllen.
Wenn ich das Spiel aber nur Online anbiete und den Verlauf jedens Spiels aufmeinem Server tracken kann um damit wieder meine ANN-KI zu füttern bietet das ganz andere Möglichkeiten.

 

[simpsonsfan]

Inwiefern andere Zielfunktionen? Als Laie wäre meine Idee, eine KI gegen Bots spielen zu lassen, die bspw. zufällige, gültige Spielzüge machen oder [konkret bei Arschloch] bspw. immer den nierdigstmöglichen Kartenwert ausspielen (aber bspw. nicht strategisch passen.)

Die KI müsste doch dann über die Zeit lernen können, welche ihrer Spielzüge zu den besten Ergebnissen führen. Wie sich die KI dann verhält, wenn sie auf einmal auf Gegenspieler mit anderem Verhalten trifft, wäre sicher auch interessant.
Ich würde jetzt (grundlos) vermuten, dass bei einer begrenzten Komplexität so ein Zufallsverhalten funktionieren könnte (wobei die KI dann kein strategisches Verhalten der Gegenspieler vorhersagen könnte.) Hingegen würde die zweite Variante vermutlich der KI beim Lernen quasi vermitteln, dass ein Spieler nicht passen kann und die KI würde diese Erwartung entsprechend in das Spielverhalten einbauen.
Und was würde passieren, wenn man im zweiten Schritt die (halbfertige) KI gegen eine Kopie von sich selbst spielen lässt?

 

[Keylan]

@simpsonsfan Ok, mit dem Begrenzten KnowHow darüber wie so eine ANN-KI überhaupt konzeptionell Funktioniert. Und mit dem Fehlenden Anwendungsfall der diese Technologie rechtfertigt, rate ich dir ganz klar davon ab.

Die Hürden bei der technischen Umsetzung lassen sich später nehmen. Aber dir fehlt der Einblick wie man ein Netzwerk überhaupt in eine KI überführt und was man dazu Konzeptionell braucht.
Und nochmal, wenn du Bot's für die KI brauchst. Was macht dann noch deine KI? Du hast doch schon die Bot's.

 

[Maviapril2]

Als Laie wäre meine Idee, eine KI gegen Bots spielen zu lassen

Noch besser: die KI gegen sich selbst oder Varianten spielen lassen. Gibt da von DeepMind echt coole Paper und Artikel dazu, wie sie das bei ihren Agenten umgesetzt haben

 

[Keylan]

Noch besser: die KI gegen sich selbst oder Varianten spielen lassen.

Das funktioniert aber erst, wenn man die ersten Versionen geschaffen hat die die Grundlegende Aufgabenstellung bereits beherrschen. Dann kann man wunderbar GAN's einsetzen um diese weiter zu Optimieren.
Dennoch brauchen auch diese eine Datenbasis auf der das Training läuft, und noch wichtiger eine weitere Optimierung der Zielfunktionen, da die Netzwerke dazu tendieren eher die Zielfunktion zu hacken als das eigentliche Problem zu lösen.

Sprich die KI fängt zum Beispiel schon beim Eröffnungszug an zu Kapitulieren, weil beide Netze mehr Reward (Siegpunkte) bekommen wenn Spiele schnell beendet werden. Gewinnen ja trotzdem noch 50% der Spiele.

Auch für DeepMind, war das Netzwerk zu erstellen nur ein kleiner Schritt. Aber es dazu zu bringen Aufgaben zu Lösen und dabei vor allem Lösungen die wir nicht haben wollen zu ignorieren ist ein ganz erheblicher Teil der Arbeit.

 

[simpsonsfan]

Also eine geeignete Zielfunktion / Bewertungsfunktion ist ja auch bei klassischen Optimierungen elementar wichtig.
Eine erste Datenbasis würde in der Denkweise beim Trainieren gegen recht primitive, quasi strategielose Bots aufgebaut.
Der Sinn, falls ich persönlich irgendwas in die Richtung machen würde, wäre nur zu sehen, was so dabei rumkommt.
Am Ende könnte sicher auch ein Vergleich sein, wie sich ein trainiertes KNN dann gegen den klassischen Bot schlägt.
Aber es geht mir auch nicht unbedingt ganz konkret darum, was dabei rauskommen würde, wenn ich mich selbst daran versuchen würde. (Vielleicht mache ich das irgendwann mal.)

Sprich die KI fängt zum Beispiel schon beim Eröffnungszug an zu Kapitulieren, weil beide Netze mehr Reward (Siegpunkte) bekommen wenn Spiele schnell beendet werden. Gewinnen ja trotzdem noch 50% der Spiele.

Sowas ist doch bspw. interessant. War dann aber wohl eine unpassende Zielfunktion, wenn man das Verhalten nicht möchte. Ganz konkret das kann bei dem Beispiel Arschloch nicht passieren. Da gibt es keine Kapitulation. ^^

 

[Maviapril2]

@Keylan dass man die nötigen Voraussetzungen schafft, dass das System nicht ausgetrickst wird, hatte ich mal so “vorausgesetzt”. Aber guter Hinweis