Kiebitz: Programmlogik

Skat gegen den Computer

Kiebitz: Programmlogik

Beitragvon bloody_fighter » 17. Jun 2009 08:15

Guten Morgen,
Also erstmal: Ich möchte in diesem Thread nur über die Logik, die hinter dem Programm steckt, diskutieren, und NICHT über den Preis oder über die Vermarktung des Programms.

Wenn ich das Programm richtig verstanden habe, spielt es alle Möglichkeiten durch, die auf die Karte folgen können, und zeigt dann am Ende die durchschnittliche Punktzahl an, die mit der entsprechenden Karte erreicht wird.
1. In dem Vorschauvideo habe ich nirgends eine Prozentzahl gesehen, die angibt, mit welcher Wahrscheinlichkeit man gewinnt, sondern es wird nach dem höchsten Durchschnitt entschieden....Ist das nicht falsch?
ich denke, dass es besser ist, wenn man 62 Punkte(im Durchschnitt natürlich) erreicht,aber in 70% der Fällen auf über 60 Punkte kommt, als wenn man 70 Punkte im Schnitt erreicht, aber nur zu 65% über 60 Punkte kommt. Weil es am Ende egal ist, ob man 62 oder 70 hat, man aber in der ersten Variante eher gewinnt, würde ich jetzt selber die 62 Punkte auswählen, Kiebitz würde aber die zweite Variante nehmen, weil es nur auf den Durchschnitt achtet...Was meint ihr dazu?

2. Wie gut ist dieses System? Weil man rechnet ja damit, dass der Gegner einen "durchschnittlichen" Zug macht, nicht aber, dass er einen guten Zug macht...(wie heißt das System eigentlich? :oops: )

3. Wenn man Alleinspieler ist und den Skat kennt, gibt es für die Gegnerischen Karten etwa 185 000 verschiedene Verteilmöglichkeiten...Wenn man all diese Möglichkeiten durchspielt, und dann den Durchschnittswert davon nimmt, wie "sinnvoll" ist dann das Ergebnis? Und wenn es zu viel Rechenleistung nimmt, und man deshalb nur etwa 20% der Verteilungen ( zufällig ausgewählt) Simuliert...Wie nah ist dieses Ergebnis dann an dem von allen Verteilungen?


Grüße,
Dani
bloody_fighter
 
Beiträge: 38
Registriert: 15. Jun 2009 16:18

Beitragvon marvin » 17. Jun 2009 08:43

Nee, ich glaube, du hast das nicht richtig verstanden. Kiebitz geht von einer konkreten, feststehenden Kartenverteilung aus (deshalb heißt es ja Kiebitz). Dann baut er alle Abwicklungsmöglichkeiten auf, dabei entsteht eine Art Baum. Den geht er dann von hinten her durch und entscheidet sich immer für den Zug, der aus Sicht des jeweiligen Spielers optimal wäre. Wenn er dann vorne angekommen ist, zeigt er für jede Karte an, wieviele Punkte sie erreicht - unter der Voraussetzung dass jeder Spieler in Kenntnis der konkreten Kartenverteilung optimal spielt!

Beispiel: Du hast noch Karo-Bube und Trumpf-Ass und bist in MH. HH (der Alleinspieler) hat Pik-Bube und Herz-9, VH hat Karo-König ausgespielt und zusätzlich Karo-8. Jetzt baut Kiebitz die folgenden Varianten auf (angegeben ist nur die Fortsetzung des 9. Stichs, der Rest ergibt sich von selbst).

1.1 Karo-Bube Pik-Bube
1.2 Karo-Bube Herz-9
2.1 Trumpf-Ass Pik-Bube
2.2 Trumpf-Ass Herz-9

Für dich bedeuten diese Varianten folgende Augen (zusätzlich zu den bisher eingebrachten)
1.1) 14
1.2) 6
2.1) 5
2.2) 15
Kiebitz geht nun davon aus, dass HH in Variante 1 die 9 legen und in Variante 2 übernehmen würde. Daher zeigt er dir für Karo-Bube 6 Augen und für Trumpf-Ass 5 Augen an.

Das kann nützlich sein, um ein konkretes Spiel zu analysieren (hätte ich den Sieg erzwingen können?). Für die Entscheidung, wie zu spielen ist, wenn man die anderen Karten nicht kennt, ist es dagegen wenig nützlich. Da muss erst noch ein Programm draufgesattelt werden, welches Kiebitz mit allen denkbaren Verteilungen füttert und danach die von dir angesprochenen Wahrscheinlichkeiten berechnet. Ein Ansatz dazu ist Siegfried-Skat, der aber aus Zeitgründen nicht alle schafft, sondern nur eine Stichprobe.
marvin
 
Beiträge: 1189
Registriert: 23. Mär 2007 01:31
Wohnort: Idstein

Beitragvon bloody_fighter » 17. Jun 2009 08:44

du hast mich nicht verstanden ;) nur die Frage 3 war auf eine unbekannte Kartenverteilung bezogen, die ersten beiden Fragen waren auf Glaskarten bezogen!Aber ansonsten weiß ich wohl, was du meinst..muss jetzt weg, werde dann aber heute Mittag darüber nachdenken, vielen Dank schonmal!
bloody_fighter
 
Beiträge: 38
Registriert: 15. Jun 2009 16:18

Beitragvon Chevalier » 17. Jun 2009 09:49

Kiebitz Pro entscheidet sich nicht für den optimalen Zug, sondern gibt für jede Karte an, mit wieviel Augen die betreffende Partei gewinnt oder verliert, wenn genau diese Karte gespielt wird. Oft sind ja mehrere Karten vom Ergebnis her gleichwertig, d.h. bei allseits optimalem Spiel gewinnt man z.B. mit 63:57, wenn Karte a b oder c gespielt wird.

Zur Frage 3: Die Folgeversion von Kiebitz Pro ist derzeit in der Mache, und da werden zusätzliche und erweiterte Funktionen enthalten sein, die von Kiebitz-Anwendern vorgeschlagen wurden. Dazu soll u.a. auch die Prüfung gehören, ob ein Blatt bei bekantem Skat gegen unbekannte Verteilung wasserdicht ist (alle möglichen Verteilungen werden geprüft) bzw. mit welcher mathematischen Wahrscheinlichkeit das Spiel auf Gewinn oder Verlust sitzt.

Vielleicht melden sich ja die Programmierer an dieser Stelle.
Benutzeravatar
Chevalier
 
Beiträge: 3758
Registriert: 2. Aug 2006 09:23
Wohnort: Planet Erde

Beitragvon mannikr » 17. Jun 2009 16:00

Auch wenn ich vom Thema abweiche, gibt es irgendwo eine kostenlose Shareware Version vom Kiebitz?
mannikr
 
Beiträge: 949
Registriert: 10. Jul 2007 00:31

Beitragvon ag0ny » 17. Jun 2009 16:30

mannikr hat geschrieben:Auch wenn ich vom Thema abweiche, gibt es irgendwo eine kostenlose Shareware Version vom Kiebitz?


Siehe dazu den folgenden Thread hier im Forum:

http://www.32karten.de/forum/viewtopic.php?t=2860
ag0ny
 
Beiträge: 266
Registriert: 11. Feb 2009 09:47
Wohnort: Bei Darmstadt

Beitragvon marvin » 17. Jun 2009 20:07

bloody_fighter hat geschrieben:du hast mich nicht verstanden ;) nur die Frage 3 war auf eine unbekannte Kartenverteilung bezogen, die ersten beiden Fragen waren auf Glaskarten bezogen!Aber ansonsten weiß ich wohl, was du meinst..muss jetzt weg, werde dann aber heute Mittag darüber nachdenken, vielen Dank schonmal!


Ich hatte dich schon verstanden. Auch bei Glaskarten sind auf jede ausspielbare Karte verschiedene Abwicklungen möglich (siehe mein Beispiel). Kiebitz gibt jetzt aber nicht die durchschnittliche Punktzahl an, die sich aus diesen Abwicklungen ergibt, sondern die Punktzahl, die der Spieler bei optimalem Gegenspiel erzwingen kann. Das wollte ich mit meinem Beitrag ausdrücken.
marvin
 
Beiträge: 1189
Registriert: 23. Mär 2007 01:31
Wohnort: Idstein

Beitragvon bloody_fighter » 4. Sep 2009 16:09

Also jetzt habe ich die Logik soweit verstanden, jetzt stellt sich mir aber die Geschwindigkeitsfrage. Geht das Programm jeden möglichen Spielverlauf durch?
bloody_fighter
 
Beiträge: 38
Registriert: 15. Jun 2009 16:18

Beitragvon First » 4. Sep 2009 16:45

ja es wickelt sämtliche Spielverläufe ab, wie oben schon beschrieben.

Dann kommt am Ende die Karte mit der besten Wahrscheinlichkeit raus. Wenn du dann mit 61 gewinnst, dann können sich die Gegner winden wie sie wollen, du gewinnst, vorausgesetzt du spielst auch die Folgezüge entsprechend. Das bedeutet, das du wenn diese Karte gespielt wurde nach Zugabe der Karten durch die Gegenspieler Kiebitz wieder rechnen lassen musst, welches nun der beste Zug ist, denn die Gegenspieler halten sich ja nicht an den zuerst erechneten Ablauf.

Nimm an du hast beim Grand hebu und pibu. Kiebitz errechnet den Gewinnweg in dem du mit (hier ist es egal pibu oder hebu) eröffnest und geht davon aus, dass HH der 2 Buben hat, mit krbu übernimmt. Dieser verweigert aber nun die Stichübernahme. Jetzt muss Kiebitz einem neuen Pfad folgen, der den besten Weg nach diesem Stich aufzeigt und die beste Folgekarte errechnen. Es werden immer sämtliche Stichmöglichkeiten bis zum Ende verfolgt und daraus die Wege gefunden imit denen du gewinnst oder verlierst.

Heisst zB für den Fall oben nach 1. pibu ...... kabu.

hebu gewinnt mit 75
kras gewinnt mit 80
kr07 verliert mit 58.

Je nach dem was MH dann zb. auf hebu legt kommen wieder ganz andere Pfade zur Geltung.
Gut Blatt
Benutzeravatar
First
 
Beiträge: 3678
Registriert: 30. Sep 2005 08:15
Wohnort: NRW

Beitragvon First » 4. Sep 2009 17:04

ZWenn du Kiebitz zum Spielende hinfragst, wenn alle nur noch 4 KArten auf der Hand halten, dann sind natürlich entsprechend weniger Möglichkeiten da die zu errechen sind.

Spieler 1 hat die Karten a,b,c,d
Spieler 2 hat die Karten e,f,g,h
Spieler 3 hat die Karten i,j,k,l

Kiebitz rechnet jetz sämtliche Möglichkeiten.

also a,e,i - a,e,j - a,e,k - a,e,l, - a, f, i - ..... bis d,h,l.

Viele fallen von vornherein raus, weil es ja den Bedienzwang gibt.

Aber es sind halt 4*4*4 = 64 Möglichkeiten die geprüft werden müssen.
Anschließend geht es weiter, im nächsten Stich sind es dann noch 3*3*3 =27 Möglichkeiten und im vorletzten noch 2*2*2 Möglichkeiten.

Es gibt also 4x4x4 x3x3x3 x 2x2x2 Möglichkeiten die letten 4 Stich zu spielen, (wenn es keinen Bedienzwang gäbe) also 13824 mögliche Verteilungen die Karten zu legen.


Wenn alle Karten noch auf der Hand sind gibt es demnach 103*93...........*23 = 3.628.800 hoch 3 Möglichkeiten. Die Zahl möchte ich jetzt nich ausschreiben.

Diese zu verfolgen dauert natürlich länger als 13824 Möglichkeiten zu errechen oder was wir noch hinbekommen in den letzten beiden Stichen 8 Möglichkeiten zu errechnen oder mit etwas Phantasie den besten Pfad aus 216 Pfaden im drittletzten Stich zu erfassen.


Ich hoffe ich habe richtig gerechnet
Gut Blatt
Benutzeravatar
First
 
Beiträge: 3678
Registriert: 30. Sep 2005 08:15
Wohnort: NRW

Beitragvon bloody_fighter » 5. Sep 2009 18:21

ja, darum geht es mir nicht, soweit ist mir das alles klar, auch mit dem bedienzwang. Aber geht das Programm wirklich alle moeglichkeiten durch, oder bricht es auch manchmal ( nach bestimmten kriterien) früher ab?
bloody_fighter
 
Beiträge: 38
Registriert: 15. Jun 2009 16:18

Beitragvon Chevalier » 5. Sep 2009 18:45

Das Kiebitz Programm rechnet alle zulässigen (Bedienpflicht) Varianten durch. Das geht seltsamerweise sehr schnell, auch mit älteren PCs. Ist eine neue Verteilung eingegeben, wird angeklickt, wer rauskommt, wer AS ist, und was gespielt wird. Nur in dieser Startphase dauert es einmalig etwas länger (maximal 2 bis 3 Sekunden), bis die 10 Handkarten des Vorhand-Spielers bewertet sind. Bei den Folgezügen geht es viel schneller.

Ist die erste Karte ausgespielt, werden die Werte der Handkarten des Mittelhandspielers gezeigt. Das geschieht sofort ohne merkbare Wartezeit usw., d.h. man hat nicht den Eindruck, dass Kiebitz an dieser Stelle nochmal was neu errechnet. Das Programm hat mit der Startphase alle Abläufe "gespeichert".

Ich hoffe, ich habe das jetzt richtig ausgedrückt (genauere Infos können Dir die Programmierer geben).

Also nochmal: Alle möglichen Züge werden durchgerechnet (sonst macht das ja keinen Sinn), das Programm bricht nicht ab. Wozu auch? Weil es so schnell geht, würde ein Abbruch nach bestimmten Kriterien (nach welchen?) überhaupt keinen Vorteil bringen.

Bei den Drückungen, die das Programm vergleicht, dauert es manchmal einige Sekunden, bis alle Kombis im Ergebnis durch sind. Alle Drückungen werden nacheinander bewertet, und das wird angezeigt, d.h. man sieht, welche Drück-Kombination gerade geprüft wird. In dieser Drücktabelle sieht man dann, welche Drückung mit wieviel Augen gewinnt, wenn der AS optimal (im Sinne von Kiebitz, d.h. mit Glaskarten) spielt. Auch hier gilt wieder: Kiebitz prüft zu jeder Drückung alle möglichen Züge.
Benutzeravatar
Chevalier
 
Beiträge: 3758
Registriert: 2. Aug 2006 09:23
Wohnort: Planet Erde

Beitragvon bloody_fighter » 6. Sep 2009 01:29

nunja, es könnte ja sein, dass das programm z.B. "abbricht" und einen bestimmten wert zurückgibt wenn das programm "merkt", dass sowieso nicht mehr erreichbar sind. Mich wundert es nur, dass es so EXTREM! viele berechnungen in so kurzer zeit schafft..
gruß
dani
bloody_fighter
 
Beiträge: 38
Registriert: 15. Jun 2009 16:18

Beitragvon Chevalier » 6. Sep 2009 08:29

Genau das ist eine der wesentlichen Leistungen der Programmierer: Effiziente Algorithmen.
Benutzeravatar
Chevalier
 
Beiträge: 3758
Registriert: 2. Aug 2006 09:23
Wohnort: Planet Erde


Zurück zu Skatprogramme

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 2 Gäste

cron