(Rund um die...) KI Tipps?

[Flux]

Hallo!

Wir haben das Problem, eine KI für das Kartenspiel Doppelkopf (sehr Skat ähnlich und komplex) schreiben zu müssen. Auch haben wir schon verschiedene Einfälle gehabt wie dies unter Umständen zu lösen ist:

1.) Brute-Force Methode. Dabei würde jeweils für jede ausspielbare Karte des Computers die Erfolgschance berechnet. Dies sollte geschehen, indem alle möglichen Kartenverteilungen der Mitspieler in Betracht gezogen werden, und aus der Wahrscheinlichkeit der jeweiligen Verteilung und der errechneten Erfolgschance, eine "Sieg"-Wahrscheinlichkeit der ziehbaren Karte errechnet werden soll. Der Haken an der Sache ist nur, dass selbst wenn wir nur einen Zug im Vorraus berrechnen würden, wir unter Ungünstiger Spielsituation Unmengen an verschiedenen Zügen zu berechnen hätten, und dies auch noch für drei verschiedene PC-Gegner. Ganz davon abgesehen, dass der Computer dabei aufgrund seiner Beschränkheit der Zugtiefe schlecht spielen würde. Bei x-beliebiger Zugtiefe könnten wir wohl nur mit einem Großrechner das Spiel schnell bekommen ;).

2.) Dem Computer Gegner eine Art "Gefühl für das Spiel" vermitteln. Diese Methode gestaltet sich jedoch aufgrund der Komplexität des Spieles als unglaublich schwer. Es gibt zu viele Sonderfälle und Sonderbehandlungen als dass ein guter Mitspieler zu erwarten ist. Auch wäre es schon ansich schwer, dem PC ein "Gefühl" zu vermitteln, da die einzige Möglichkeit die mir hierzu einfällt, der Umgang mit Konstanten und Variablen wäre, die in geschickten Algorhythmen die richtigen Endwerte liefern. Allein schon die Testphase für ein solches System wäre denke ich riesig.

3.) Dem PC das "selber lernen" ermöglichen. Dabei habe ich an eine große Datenbank gedacht, in der alle Züge gespeichert werden die der Computer bisher vollzogen hat, sowie deren Erfolgsquote (wobei es hierbei schwer ist, nicht nur eine Erfolgsquote für den im Moment gespielten Zug und dessen erwirtschafteten Punkte, sondern auch in Betracht bis zum Spielende festzulegen). Wenn nun eine ähnliche oder gar die gleiche Situation erneut auftritt, soll sich die KI "errinern" und aus möglicherweise schlechten Erfahrungen "lernen". Um einen guten Einstieg zu ermöglichen könnten wir auch schon eine Datenbank mit von uns aufgezeichneten Spielen (was allerdings viel Zeit in Anspruch nehmen würde) anlegen, die der PC dann selbstständig erweitert.
Doch auch bei dieser Methode machen wir uns Sorgen um die Geschwindigkeit (man denke nur an die riesigen Datenmengen...), die Umsetzbarkeit (Erfolgsquote auf ganzem Spiel? Ähnlichkeit?) und den Erfolg (wird überhaupt ein merklicher Lernprozess stattfinden? Wird der PC-Gegner so überhaupt Spielstark?).

Wir sind zur Zeit also in einer sehr hilflosen Lage. Alle Möglichkeiten haben meiner Meinung nach gravierende Mängel aufzuweisen.

Falls jemand Vorschläge, Tipps oder Lösungsansätze hat wären wir unendlich dankbar wenn er diese hier posten würde.

Grüße,
Nico und Felix

[moon]

Es gibt eine methode, die was mit reinforcement learning zu tun hat. Du kannst mal unter google TD-Gammon eingeben, dann findest Du infos darueber wie ein Backgammon spiel mit Hilfe eines Neuronalen Netzes programmiert werden kann. Das bekannteste zu Zeit existierende Programm spielt weltmeisterlich.

Das Prinzip kann man meiner Meinung nach auch auf Kartenspiele anwenden (adaptieren). Der Computer wuerde sehr oft gegen sich selbst spielen und quasi aus seinen eigenen Fehlern lernend irgendwann (bei backgammon sind es zur Zeit 4000000 Spiele ca. (!!!)) gut spielen.

gruss

[HumeSikkins]

Hallo,
passt besser nach Rund um...