(Skat)Spielregel/KI-Implementierung - Ideen?

[Frank (no reg)]

Hallo,

ich wollte mich die nächsten Tage mal mit der Programmierung eines Skat-Spiels für Windows PCs versuchen. Gründe hat es derer mehrere, Hauptgrund ist wohl "Experimentierfreude" [*]. Im Fokus steht für mich neben der allgemeinen Spielmaschinerie (wer ist dran, welche Karte darf gespielt werden, wer bekommt den Stich, wer gewinnt sein Spiel) die KI bzw. die Spielstärke des Computerspielers.

Wie könnte man die (Spielstärke)KI des Spiels aufbauen? Ein paar Grundsätze sollte die Computerseite natürlich haben, wie z.b. mitzählen, welche Karten bereits ausgespielt worden sind. Allerdings gibt es dann immer noch ein kleines Universum von Spielmöglichkeiten, die von Oma-Skat bis zu "äusserst gewagt" und "mauern" reichen. Ich dachte so ein bisschen an Bayesschen Algorithmus mit möglichen Spielzügen auf Basis bereits bekannter Spielzüge und deren Ausgang ergeben. Die KI Stärke könnte sich aus der Sample-Grösse bekannter Spielzüge ergeben. Eine Lernfähigkeit der KI wäre dann natürlich über die Zeit auch gegeben. Eine gewisse Vorhersagefähigkeit wer von den anderen Mitspielern welche Karte spielt wird sicherlich auch benötigt.

Wichtig wäre auch, dass zwei Computerspieler unabhängig von einander die Entscheidungen treffen können, dennoch aufgrund desselben Algorithmusses und desselben Sample-Sets. Alles andere wäre ja "virtuelles" in-die-Karten-schauen, was ja nur beim Ouvert-Spiel annähernd erlaubt ist.

Danke für interessante Denkanstösse
Frank

[*] es gibt aktuell kein wirklich gutes Computer-Skatspiel für Windows Vista, schon gar keins mit lernender KI :)

[ritschmanhard]

Hi Frank!

Öhhm - ich will dich da ja nicht entmutigen, aber:

• Du willst SKAT proggen?
• Mit einer annehmbaren Spielstärke?
• Ohne des der Computer "bescheisst" und die Karten kennt, also nach Strategie und nicht nach kalkulierter (bekannter) Verteilung spielt?

Also, ich würde dir für den Anfang (wenn überhaupt) dringend Schafkopf empfehlen; das ist taktisch ähnlich, aber Reizen und Stock entfallen;
doch selbst da wüßt' ich schon nicht mehr sicher, wie ich das angehen würde...

Außerdem besteht ein Gutteil des "Skatkönnens" eines menschlichen Spielers in der Beurteilungsqualität seiner Mitspieler - somit gibt es meines Erachtens keine allgemeingültige Strategie für dein Programm, sondern es müsste eine je nach Spielweise des menschlichen Gegners eine Strategie gebildet werden...

Trotzdem wünsche ich dir viel Erfolg,
Richard

[ritschmanhard]

Hi Frank!

Ich hab zwar keine Ahnung, ob das was taugt, aber es gibt ein diesbezügliches Open Source Projekt:
http://www.spielgeist.net/game.html

Grüsse,
Richard

[Frank (no reg)]

Hi,

Öhhm - ich will dich da ja nicht entmutigen, aber:

• Du willst SKAT proggen?

Ja.

• Mit einer annehmbaren Spielstärke?

Ja, weil mich die Programmierung einer (selbstlernenden) KI für solche Zwecke interessiert und es sicherlich mal ne herausfordernde Aufgabe wäre, mal was zu basteln, was "annehmbar" ist. Dieses Spielgeist KI ist nicht wirklich ausgereift, wenn ich da mit 4 Trumpf (ohne 3) mit Schneider gewinne.

• Ohne des der Computer "bescheisst" und die Karten kennt, also nach Strategie und nicht nach kalkulierter (bekannter) Verteilung spielt?

Genau, das ist ja die Herausforderung.

Schafkopf kenn ich leider gar nicht vom Spiel her. Danke für den Tipp mit der Spielgeist-Seite.

Herausforderung wird vorallem sein, das Spielen einer Karte durch den Computer so flink wie möglich zu halten, max 1 oder 2 Sekunden "Nachdenkzeit". Habe gehört, es sind sogar schon Leute beim Kartenspielen erschossen worden, weil sie zu lange nachgedacht haben. :)

Danke für deinen Input auf jeden Fall!

Grüsse,
Frank

[Adolf]

frag doch mal Herrn Fischer.
Adolf

[Richard Rüfenacht]

Hallo Frank!

ich wollte mich die nächsten Tage mal mit der Programmierung eines Skat-Spiels für Windows PCs versuchen.

Immer diese Ausländer mit ihren ausländischen Spielen. ;-)  Demnächst wird der "Blick" fragen müssen, wieviele Deutsche die Schweiz vertrage, ehe vom Jassen auf Skat umgestellt wird. Stöck Wyys Stich kennest du? Den Escor-Spielautomaten auch?

Im Fokus steht für mich neben der allgemeinen Spielmaschinerie (wer ist dran, welche Karte darf gespielt werden, wer bekommt den Stich, wer gewinnt sein Spiel) die KI bzw. die Spielstärke des Computerspielers.

Dies wird dein zentrales Problem sein. Bei Skat oder Jassen wird dies noch schwieriger sein als bei Schach, weil diese Spiele in gewisser Weise "intelligenter" sind. Intelligenter, weil es kein rettendes Remis gibt und das Spiel nicht primär auf der Vermeidung von Fehlern beruht.

Die KI Stärke könnte sich aus der Sample-Grösse bekannter Spielzüge ergeben. Eine Lernfähigkeit der KI wäre dann natürlich über die Zeit auch gegeben.

Nur worin besteht diese Lernfähigkeit? Du stehst hier vor dem allgemeinen Dilemma der KI: Soll dein Programm etwas lernen, was Menschen bereits besser können? Oder soll es seine Überlegenheit bezüglich Rechen- und Speicherfähigkeit ausnützen?

Eine gewisse Vorhersagefähigkeit wer von den anderen Mitspielern welche Karte spielt wird sicherlich auch benötigt.

Rein statistisch oder aufgrund gelernter "Menschenkenntnis"? Wäre natürlich eine interessante Variante, wenn sich der Computer den Eigenheiten seiner Mitspieler anpassen könnte. Allerdings sind wir dann wieder bei der Frage, was der Computer eigentlich lernen soll. Im Hinblick auf das Lernen des Spiels wäre dieser Punkt aber viel versprechend, die Spieler könnten dann auf ihre Fehler hingewiesen werden.

Beste Grüsse
Richard

PS: Gutes Thema bei einem Bier in Pfäffikä - ich melde mich. Danke für die E-Mail.

[Frank (no reg)]

Hi,

ja, ich warte quasi seit Wochen auf ne Antwort von dir, dachte schon, meine eMail ist im Spam-Ordner verschwunden.

"Jassen" hab ich schon gehört, aber sonst habe ich keinerlei Bezug zu diesem Spiel. Ich find das Versenken von Nägeln mit der schmalen Hammerseite um Längen belustigender :)

Wer liest denn den Blick? Heute und 20minuten reicht völlig für die 6min mit der SBahn.

Deine Argumente sind sehr gut, sie bohren tief genug. Wir sollten sie wirklich einfach mal bei einer Stange vertiefen.

Ich versuche das ganze als Entwicklung und Anwendung eines spezifischen "Data Mining" Algorithmus auf ein nicht-unalltägliches Spiel (zumindest für Sachsen). Plus eben, dass da noch ein paar andere Faktoren hinzukommen, die Spielmaschinerie um die KI herum, Interaktion mit dem Benutzer, saubere Abstraktion zu einer variablen Präsentationsschicht, asynchroner Datenaustausch zwischen den Komponenten. Könnte ich für meine Doktorarbeit verwenden am Ende :)

So long, Grüsse
Frank

[Uusländer]

Hallo Richard,

Demnächst wird der "Blick" fragen müssen, wieviele Deutsche die Schweiz vertrage, ehe vom Jassen auf Skat umgestellt wird.

Müssen? Das macht der ganz freiwillig. Das Thema kommt immer gut an. Man hätte auch einfach die "Ausländer" der 2. und 3. Generation einbürgern können, dann wäre der Ausländeranteil nicht so gross und man müsste sich weniger künstliche Sorgen machen.

Zur KI:

Bei Skat oder Jassen wird dies noch schwieriger sein als bei Schach, weil diese Spiele in gewisser Weise "intelligenter" sind.

Jass kenne ich kaum, aber was ich davon mitbekommen habe, ist es gegen Skat eher ein Kinderspiel ;-)

Intelligenter, weil es kein rettendes Remis gibt und das Spiel nicht primär auf der Vermeidung von Fehlern beruht.

Skat beruht primär schon auf der Vermeidung von Fehlern. Es gibt einige Grundregeln, wie "dem Freunde kurz, dem Feinde lang", deren Einhaltung ausschliesslich der Vermeidung von Fehlern dient.

Letztlich kommt es darauf an, die Kartenverteilung möglichst früh möglichst genau zu ermitteln. Diese Aufgabe lässt sich m.E. durchaus optimieren. Zu diesem Zweck, und auch zur Vermeidung von Fehlern, hält man sich an die Gesetze der Wahrscheinlichkeit und an die nach jedem Stich neu gewonnenen Erkenntnisse.

Eine Skat-KI müsste jeweils die Wahrscheinlichkeiten ermitteln und immer die für den Worst Case günstigste Strategie anwenden. Natürlich sollte der Programmierer ein guter Skatspieler sein.

Gruß, Don P

[Richard Rüfenacht]

Hallo Don!

Jass kenne ich kaum, aber was ich davon mitbekommen habe, ist es gegen Skat eher ein Kinderspiel ;-)

Sehe ich genau umgekehrt. Der Eindruck mag entstehen, weil meist zum Plausch gejasst wird, Schweizerinnen und Schweizer spielen halt zur Freude und nicht mit deutschem Bierernst. Da es aber sehr viele Varianten des Spiels gibt, existieren auch entsprechend komplexe Regeln. Es gibt eine Variante, die dem Skat sehr ähnlich ist, aber bei weitem nicht die schwierigste und interessanteste ist.

Skat beruht primär schon auf der Vermeidung von Fehlern.

Ist eine Möglichkeit. Fragt sich nur, ob dann das Spielen noch als lustvoll empfunden wird. ;-)

Beim Skat kannst du aber alle Fehler vermeiden und trotzdem verlieren. Wenn du beim Schach keine Fehler machst, endet die Partie im ungünstigsten Fall remis. Beim Schach sind dir jederzeit alle Informationen zugänglich, beim Skat nicht.

Letztlich kommt es darauf an, die Kartenverteilung möglichst früh möglichst genau zu ermitteln. Diese Aufgabe lässt sich m.E. durchaus optimieren. Zu diesem Zweck, und auch zur Vermeidung von Fehlern, hält man sich an die Gesetze der Wahrscheinlichkeit und an die nach jedem Stich neu gewonnenen Erkenntnisse.

Die klassische Wahrscheinlichkeitsrechnung hilft dir aber nicht weiter, weil es für die meisten Fälle keine brauchbare Hierarchie von Wahrscheinlichkeiten gibt und zudem der wahrscheinlichere Spielzug keineswegs der erfolgversprechendere sein muss, da dieser emergent ist.

Aus diesem Grunde brachte Frank den Bayesschen Algorithmus ins Spiel, weil es sich ja immer um Entscheidungen bei Unsicherheit handelt. Und er wollte, dass sein Programm lernfähig ist, wie auch immer. Damit ist aber der Abschied von der klassischen Wahrscheinlichkeit unvermeidlich. Ein lernender Automat kann zum Zeitpunkt n unmöglich wissen, was er du einem späteren Zeitpunk n + t wissen wird.

Eine Skat-KI müsste jeweils die Wahrscheinlichkeiten ermitteln und immer die für den Worst Case günstigste Strategie anwenden.

Das ist die Kernfrage der KI. Du folgst hier der Strategie des Schach-Computers. Der muss nur über genügend Rechenkapazität verfügen, dann hat ein menschlicher Spieler keine Gewinnchance. Ich gehöre nun aber zu der Fraktion, die diesem Rechner jegliche Intelligenz abspricht. Es handelt sich um einen vollständig determinierten Vorgang. Insofern halte ich es für verfehlt, in irgend einer Weise von Intelligenz zu sprechen. Es ist eine triviale Maschine, mehr nicht.

Der intelligente und lernfähige Skat-Computer soll wie ein Mensch spielen. Spielen wohlgemerkt, nicht einfach nur gewinnen.

Beste Grüsse
Richard

[Uusländer]

Hallo,

Da es aber sehr viele Varianten des Spiels gibt [Jass], existieren auch entsprechend komplexe Regeln.

Das glaube ich gerne. Vermutlich sind es etwa so viele Varianten, wie es Stammtische gibt ;-)

Skat beruht primär schon auf der Vermeidung von Fehlern.

Ist eine Möglichkeit. Fragt sich nur, ob dann das Spielen noch als lustvoll empfunden wird. ;-)

Nicht wirklich. Deshalb wird auch so gut wie nie ohne Einsatz gespielt. Die Geselligkeit und die zu gewinnenden Biere sind's, die den Lustgewinn bewirken, das Spiel selbst wird oft genug zum Ärgernis ("Bist du wahnsinnig? Wieso hast du nicht die Pik 10 reingebuttert? Nur wegen dir hat er jetzt das Spiel gewonnen!")

Beim Skat kannst du aber alle Fehler vermeiden und trotzdem verlieren.

Sicher, aber wenn man keine Fehler macht, ist die Chance am grössten, dass man auch gewinnt. Wenn man trotz Fehlern gewinnt, ist es einfach nur Glück.

Die klassische Wahrscheinlichkeitsrechnung hilft dir aber nicht weiter, weil es für die meisten Fälle keine brauchbare Hierarchie von Wahrscheinlichkeiten gibt und zudem der wahrscheinlichere Spielzug keineswegs der erfolgversprechendere sein muss, da dieser emergent ist.

Das kann ich nicht nachvollziehen. Es gibt IMO sehr wohl eine brauchbare Hierarchie von Wahrscheinlichkeiten, bzw. evtl. mehrere davon. Wenn mein Blatt z.B. so ist, dass ich sowohl ein Herz- als auch Pik-Spiel mit der gleichen Wahrscheinlichkeit gewinnen könnte, dann kann ich ja eine Zufallsentscheidung treffen. Im weiteren Verlauf stellt sich dann nach und nach die Kartenverteilung heraus, und die Wahrscheinlichkeiten ändern sich natürlich und müssen jeweils berücksichtigt werden, falls du sowas mit Emergenz und Lernen meinst.

Aus diesem Grunde brachte Frank den Bayesschen Algorithmus ins Spiel, weil es sich ja immer um Entscheidungen bei Unsicherheit handelt. Und er wollte, dass sein Programm lernfähig ist, wie auch immer. Damit ist aber der Abschied von der klassischen Wahrscheinlichkeit unvermeidlich. Ein lernender Automat kann zum Zeitpunkt n unmöglich wissen, was er du einem späteren Zeitpunk n + t wissen wird.

Das geht doch auch mit klassischen Wahrscheinlichkeiten. Unter richtigem Lernen verstehe ich aber von Fehlern lernen, d.h. theoretisch müsste der KI-Spieler, wenn er am Anfang nichts kennt, ausser den Spielregeln, mit der Zeit ein hervorragender Skat-Spieler werden können.

Das ist die Kernfrage der KI. Du folgst hier der Strategie des Schach-Computers. [...] Insofern halte ich es für verfehlt, in irgend einer Weise von Intelligenz zu sprechen. Es ist eine triviale Maschine, mehr nicht.

Das sehe ich auch so. Echte KI ist meines Wissens noch nicht erfunden. Man nennt alles KI, was sein Verhalten mehr oder weniger gut an sich ändernde Parameter anpassen kann.

Der intelligente und lernfähige Skat-Computer soll wie ein Mensch spielen. Spielen wohlgemerkt, nicht einfach nur gewinnen.

Wie ein Mensch? Also schlecht spielen und Spass haben? Mir ist noch kein Computer untergekommen, der bei seinen Aktivitäten Spass gezeigt hätte. Aber wer weiss, vielleicht empfindet er ja Schadenfreude, wenn er mal wieder nicht das macht, was ich von ihm will ;-)

Gruß, Don P