skat

Du hast eine Idee für ein Projekt?
joh#
User
Beiträge: 139
Registriert: Freitag 6. November 2009, 13:16

(Anfscd)

Vielleicht kennt der eine oder andere das beliebte Skatspiel. Die Anzahl aller
möglichen Spielverläufe beläuft sich bekanntlich auf 47.784.725.839.872.000.000
Allerdings schränkt der Bedienzwang (vom Anspielenden gelegte Farbe muß zugegeben
werden) die Anzahl der Möglichkeiten stark ein. Wie stark, das möchte ich ermitteln.

Nun ist Python als Interpretersprache ja nicht gerade schnell deshalb die Frage:
Würde man sie für diese Sache überhaupt nehmen?
Ich bin nämlich mit Forth dabei schon am Ende, es ist zwar schneller, aber alle
komplexeren Datenstrukturen müssen von Hand aufgebaut werden
Bislang läuft das so:
-Mit 10 Karten führe aus:
-ermittle alle möglichen (mit Bedienzwang) 3er Kombinationen und pushe die auf einen Stack
-nehme die erste dieser Kombinationen und ermittle mit dem entsprechend verringertem Blatt
wieder alle Möglichkeiten usw.
Das läuft allerdings schon bei 7 Karten über 2 Minuten, mglw. weil aufgrund der verwendeten
Datenstruktur nach jeder ausgespielten Karte das Blatt mit quicksort sortiert werden muß
und das multipliziert sich natürlich.
BlackJack

@joh#: Ich kenne die Regeln nicht, aber ich würde mich fragen, ob man das überhaupt auf diese Weise ermitteln würde, und sich nicht vielleicht eher mathematisch Gedanken darüber macht, statt stupide auszuprobieren. Je nachdem wie viel oder wenig von dieser gigantischen Zahl der Möglichkeiten durch die Regeln eingeschränkt werden, kann die Wahl der Programmiersprache relativ egal sein -- eine exponentielle Laufzeit kann auch in jeder Sprache "zu langsam" sein.
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Ich hätte ja beim letzten Prominentenspecial von "Wer wird Millionär?" eine Million verdient, weil ich die Zahl, für die Jauch da eine Million Euro ausgelobt hatte, wenn man sie denn hätte vorlesen können, vorlesen hätte können. Sie war 5 Trillionen kleiner als was du uns hier zeigst. Da ging es um Zauberwürfelzustände. Wie auch immer.

Selbst wenn ein Computer 100.000 Spielverläufe pro Sekunde bewerten könnte, was ihm 10 Microsekunden pro Spielverlauf lässt, wäre das Gerät 477.847.258.398.720 Sekunden oder 5.530.639.565 Tage oder 15.152.437 Jahre damit beschäftigt. Bis dahin ist zwar die Sonne noch nicht zur Supernova geworden, aber wahrscheinlich laufen dann intelligente Tintenfische über das Land und fragen sich, was sollte wohl dieser Computer da berechnet.

Ohne theoretische mathematische Überlegungen und nur mit Ausprobieren wird das nichts. Jedenfalls nicht in diesem Leben. Egal welche Programmiersprache du da nimmst.

Stefan
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

sma hat geschrieben:Bis dahin ist zwar die Sonne noch nicht zur Supernova geworden, aber wahrscheinlich laufen dann intelligente Tintenfische über das Land und fragen sich, was sollte wohl dieser Computer da berechnet.
Die Antwort auf die Frage nach dem Leben, dem Universum und dem ganzen Rest natürlich.
Benutzeravatar
Hyperion
Moderator
Beiträge: 7478
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

snafu hat geschrieben: Die Antwort auf die Frage nach dem Leben, dem Universum und dem ganzen Rest natürlich.
Da kommt aber 42 bei raus - oder wußtest Du das noch nicht? :-D
Benutzeravatar
cofi
Python-Forum Veteran
Beiträge: 4432
Registriert: Sonntag 30. März 2008, 04:16
Wohnort: RGFybXN0YWR0

Das weiss der Rechner ja noch nicht :) Oder er berechnet gerade die Frage zu 42. Wie wir ja wissen, dauert das signifikant länger *g
problembär

XSkat ist eine sehr schöne freie Umsetzung, allerdings nicht in Python.

Ich fänd's eigentlich toll, wenn das Projekt mehr Leute unterstützen würden (so daß es dann so gut spielt wie die kommerziellen Versionen). Aber es ist so auch schon recht klasse.

Gruß
Benutzeravatar
hendrikS
User
Beiträge: 420
Registriert: Mittwoch 24. Dezember 2008, 22:44
Wohnort: Leipzig

Ich vermute, daß Python aus Performancegründen nicht in Frage kommt.
Da auch Einzelspielermodus erlaubt ist, müssen ja die ganzen Strategien implementiert sein. Bestimmt sehr aufwendig und zeitraubend.
Sieht ansonsten vielversprechend aus.
BlackJack

@hendrikS: Wofür kommt Python nicht in Frage? Eine Skat AI? Wäre die soo rechenaufwändig? Wobei das wohl auch alles nicht mehr viel mit der Ausgangsfrage zu tun hat.
ms4py
User
Beiträge: 1178
Registriert: Montag 19. Januar 2009, 09:37

hendrikS hat geschrieben:Ich vermute, daß Python aus Performancegründen nicht in Frage kommt.
Da auch Einzelspielermodus erlaubt ist, müssen ja die ganzen Strategien implementiert sein. Bestimmt sehr aufwendig und zeitraubend.
Sieht ansonsten vielversprechend aus.
Beim Entwurf einer AI ist das Problem eigentlich nie die Laufzeit, sondern wie man das Verhalten des Computers "menschlich" machen kann. Diese Diskussion hatten wir erst vor kurzem mit einem sehr interessanten Artikel dazu, hab den Link aber auf die Schnelle nicht gefunden.
Keiner will doch einen Gegenspieler, der alle möglichen Resultate berechnen kann, und immer den optimalsten Weg auswählt (von den Schachweltmeister mal abgesehen ;) ).

Aber selbst dann ist die Performanz IMHO immer noch kein Problem (auf jeden Fall bei Skat, bei Schach wäre es vllt was anderes), der Mensch als Spieler benötigt ja selbst auch Zeit zum Überlegen und Reagieren, das müsste dem Rechner eigentlich genug Zeit geben...
Benutzeravatar
jbs
User
Beiträge: 953
Registriert: Mittwoch 24. Juni 2009, 13:13
Wohnort: Postdam

ice2k3 hat geschrieben:
hendrikS hat geschrieben:Ich vermute, daß Python aus Performancegründen nicht in Frage kommt.
Da auch Einzelspielermodus erlaubt ist, müssen ja die ganzen Strategien implementiert sein. Bestimmt sehr aufwendig und zeitraubend.
Sieht ansonsten vielversprechend aus.
Beim Entwurf einer AI ist das Problem eigentlich nie die Laufzeit, sondern wie man das Verhalten des Computers "menschlich" machen kann. Diese Diskussion hatten wir erst vor kurzem mit einem sehr interessanten Artikel dazu, hab den Link aber auf die Schnelle nicht gefunden.
Keiner will doch einen Gegenspieler, der alle möglichen Resultate berechnen kann, und immer den optimalsten Weg auswählt (von den Schachweltmeister mal abgesehen ;) ).

Aber selbst dann ist die Performanz IMHO immer noch kein Problem (auf jeden Fall bei Skat, bei Schach wäre es vllt was anderes), der Mensch als Spieler benötigt ja selbst auch Zeit zum Überlegen und Reagieren, das müsste dem Rechner eigentlich genug Zeit geben...
Ich denke du meinst den: http://www.gamasutra.com/view/feature/3 ... php?page=1
[url=http://wiki.python-forum.de/PEP%208%20%28%C3%9Cbersetzung%29]PEP 8[/url] - Quak!
[url=http://tutorial.pocoo.org/index.html]Tutorial in Deutsch[/url]
ms4py
User
Beiträge: 1178
Registriert: Montag 19. Januar 2009, 09:37

Danke! Genau den :)
Benutzeravatar
hendrikS
User
Beiträge: 420
Registriert: Mittwoch 24. Dezember 2008, 22:44
Wohnort: Leipzig

BlackJack hat geschrieben:@hendrikS: Wofür kommt Python nicht in Frage? Eine Skat AI? Wäre die soo rechenaufwändig? Wobei das wohl auch alles nicht mehr viel mit der Ausgangsfrage zu tun hat.
Mit der Ausgangsfrage hat es nichts mehr zu tun. Davon abgesehen ist Skat wie Schach ein Strategiespiel. Bringe doch mal Deinem PC bei einen Grand ohne 4 zu spielen oder richtig zu reizen und dann ist dann ja manchmal der König zu dritt, der ja immer n'en Ritt macht. Wird keiner in Python schreiben. Zumindest nicht, wenn es gut werden soll.
Benutzeravatar
Hyperion
Moderator
Beiträge: 7478
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

hendrikS hat geschrieben:Wird keiner in Python schreiben. Zumindest nicht, wenn es gut werden soll.
Was würdest Du da nehmen? Eine rein funktionale Sprache? Oder woran dachtest Du?
Benutzeravatar
hendrikS
User
Beiträge: 420
Registriert: Mittwoch 24. Dezember 2008, 22:44
Wohnort: Leipzig

Hyperion hat geschrieben:Was würdest Du da nehmen? Eine rein funktionale Sprache? Oder woran dachtest Du?
Gute Frage.
Am Ende ist die Implementierung ziemlich aufwendig und es muss schnell sein. Ich will ja nicht 5 min warten bis mein PC mal 18 sagt.
So würde ich wahrscheinlich C++ wählen.
Haskell käme vielleicht auch in Frage, aber da muss man schon sehr geübt darin sein. Würde ich mir nicht zutrauen. Aber selbst in C++ ist das eine absolute Challenge.
Benutzeravatar
Sr4l
User
Beiträge: 1091
Registriert: Donnerstag 28. Dezember 2006, 20:02
Wohnort: Kassel
Kontaktdaten:

hendrikS hat geschrieben:
BlackJack hat geschrieben:@hendrikS: Wofür kommt Python nicht in Frage? Eine Skat AI? Wäre die soo rechenaufwändig? Wobei das wohl auch alles nicht mehr viel mit der Ausgangsfrage zu tun hat.
Mit der Ausgangsfrage hat es nichts mehr zu tun. Davon abgesehen ist Skat wie Schach ein Strategiespiel. Bringe doch mal Deinem PC bei einen Grand ohne 4 zu spielen oder richtig zu reizen und dann ist dann ja manchmal der König zu dritt, der ja immer n'en Ritt macht. Wird keiner in Python schreiben. Zumindest nicht, wenn es gut werden soll.
Ich sehe kein Problem bei sowas. Die KI hat die Karten vor sich und agiert einfach nach ein paar Regeln. z.B geht die KI alles durch.

Möchte ich Kreuz spiele? 3Bube *10pkt + 2kreuz*5punkte = 25punkte
Möchte ich ....
Möchte ich Grand spielen? 3Buben * 15pkt + 1ass*5punkte + 2 10nen*3punkte = 56punkte

das macht man für alle Spielvarianten und der PC wählt dann die Modi wo er die meisten Punkte erreicht hat und reizt dann bis zu den Punkten die dieser Spielvariante hergibt. Falls ein Computerspieler zu oft bei einem Spielmodus verliert muss man die Punkteverteilung anpassen.

So wenn der Spielvariante entschieden ist ist es nur noch Rechnerei, hat mein Gegenspieler noch Trumpf? hat er noch Kreuz? Ja hat er letze runde bedient dann spiel ich mein Kreuzass.

Man muss nicht mehrer Varianten durchspielen um ein realistisches Spielverhalten zu bekommen.
Benutzeravatar
hendrikS
User
Beiträge: 420
Registriert: Mittwoch 24. Dezember 2008, 22:44
Wohnort: Leipzig

Sr4l hat geschrieben:Ich sehe kein Problem bei sowas. Die KI hat die Karten vor sich und agiert einfach nach ein paar Regeln. z.B geht die KI alles durch.
Ohne 11, Spiel 12 * Eichholz = 144.
Bei Deiner Variante könnte also auf Eichholz gereizt werden obwohl der PC Spieler gar kein Trumpf hat. Dies ist eher theorescher Natur und kommt in einem von 10000 Fällen vor.
Ne so einfach geht das nicht. Du musst schon Deinen PC befähigen das Blatt zu bewerten, welche Farbe die höchsten Gewinnaussichten hat, oder ob es überhaupt eine gibt. Dabei spielt auch eine Rolle ob ich in Vor, Mittel oder Hinterhand sitze und noch 100 andere Faktoren.
Benutzeravatar
Sr4l
User
Beiträge: 1091
Registriert: Donnerstag 28. Dezember 2006, 20:02
Wohnort: Kassel
Kontaktdaten:

Ich habe mir das so vorgestellt:
http://paste.pocoo.org/show/152873/

Ausgabe z.B:

Code: Alles auswählen

SPIELRKARTEN
============
[Karte(kreuz, dame, spieler1), Karte(kreuz, 8, spieler1), Karte(karo, 8, spieler1), Karte(kreuz, 9, spieler1),
Karte(karo, 10, spieler1), Karte(karo, koenig, spieler1), Karte(kreuz, bube, spieler1), Karte(herz, bube, spieler1),
Karte(karo, ass, spieler1), Karte(kreuz, ass, spieler1)]
SPIELMODUS
==========
{'herz': 36, 'pik': 26, 'kreuz': 76, 'karo': 66, 'grand': 37}
Nach der Ausgabe sollte die KI also als spielvariante kreuz wählen karo könnte aber nach nach Aufnahme des Skats recht gut abschneiden.
Benutzeravatar
hendrikS
User
Beiträge: 420
Registriert: Mittwoch 24. Dezember 2008, 22:44
Wohnort: Leipzig

Sr4l hat geschrieben:Ich habe mir das so vorgestellt:
http://paste.pocoo.org/show/152873/
Ja, schon mal ein Ansatz zu einer Bewertung des Blattes zu kommen. Die NULL fehlt noch. Müßte man mal n'paar zufällige Tests machen wie nahe das dem Normalspiel kommen würde.
problembär

Übrigens: Bei xskat sollte man noch die Kartenbilder von

http://www.xskat.de/xskat-cards-de.html

runterladen und installieren, damit es wie gewohnt aussieht (sonst ist es etwas häßlich).
Auf den Kartenbildern war wohl ein Copyright (siehe auf der Seite).

Die Quellen von xskat 4.0 sind 873K C-Code. Könnte man vielleicht mal versuchen, nach Python zu übersetzen. Wenn einen das sehr interessiert und man unbedingt was zu dem Thema lernen will, heißt das :) ...

Gruß
Antworten