Schlag den Raab: Kartenspiel (Gewinnstrategie)

fidionael · Verfasst: Mo 20.11.06 01:17

Hallo,

vergangenen Samstag lief auf ProSieben die Live-Sendung "Schlag den Raab", bei welcher ein Kandidat 1.000.000€ gewinnen konnte, wenn er Stefan Raab in 15 Spielen schlug.

Eines dieser Spiele war ein Kartenspiel, bei welchem beide Spieler 11 Karten erhielten, von 1 - 11 durchnummeriert. In jeder Runde müssen beide Spieler eine Karte auswählen (diese bekommen sie auch nicht wieder) ohne zu wissen, welche der andere auswählt. Wer die höhere Zahl hat, bekommt einen Punkt, bei Gleichstand werden die Karten ohne Zählung weggelegt. Gewonnen hat schließlich der, der wenn alle Karten verspielt sind, die meisten Punkte hat.

Dieses Spiel habe ich mal kurz und knapp in Python implementiert:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:

#/usr/bin/python
# -*- coding: utf-8 -*-
import random
#########################################################################################
# Listenmethoden
def getIndexByVal(l,val):
  """ Diese Funktion gibt den Index eines Wertes in einer Liste zurück.
  Wird der Wert in der Liste nicht gefunden, wird -1 zurückgegeben."""

  ergebnis = 0
  while not l[ergebnis] == val:
    ergebnis += 1
    if ergebnis == len(l):
      return -1
  return ergebnis
#########################################################################################
# Klassen
class Spiel:
  def __init__(self):
    self.deck = [ [], [] ]
    for deck in self.deck:
      for i in range(1,12):
        deck.append(i)
    self.score = 0
  def zug(self,zahl):
    """Diese Funktion wählt zufällig für den Computer, zieht die Karten von den Decks ab und wertet aus."""

    if getIndexByVal(self.deck[0],zahl) > -1:
      del self.deck[0][getIndexByVal(self.deck[0],zahl)]
      gegner = self.deck[1][int(random.random()*len(self.deck[1]))]
      del self.deck[1][getIndexByVal(self.deck[1],gegner)]
      if zahl < gegner:
        self.score -= 1
      if zahl > gegner:
        self.score += 1
      return gegner
    else:
      return -1
#########################################################################################
# Hauptprogrammfluss
MeinSpiel = Spiel()
while len(MeinSpiel.deck[0]) > 0:
  print MeinSpiel.deck[0]
  try:
    buf = raw_input("Welche Karte möchten Sie legen?")
    gegner = MeinSpiel.zug(int(buf))
    if gegner > -1:
      if gegner < int(buf):
        print "Sie haben den Zug gewonnen (%d)" % (gegner)
      else:  
        print "Sie haben den Zug nicht gewonnen (%d)" % (gegner)
    else:
      print "Diese Zahl haben Sie gar nicht!"
  except:
    print "Falsche Eingabe."
print "Spiel zuende. Punktestand:",MeinSpiel.score

Soweit, so gut, doch nun frage ich mich (als aufstrebender Möchtegerninformatiker ;-)

) natürlich, ob man bei diesem Spiel gegen den Computer eine gewisse (sinnvolle) Strategie verfolgen kann. Zur Vereinfachung des Problems kann man hier zunächst davon ausgehen, dass der Gegner zufällig Karten zieht. Das das in der Sendung natürlich nicht so ist, sei erstmal dahingestellt.

Ich tüftel jetzt schon seit einiger Zeit an diesem Problem und nun, nachdem ich noch keinen Schritt weiter bin, wollte ich mich hier einmal umhören, ob jemand eine Idee hat.

Schonmal vielen Dank im Vorraus.

Edit:
Da Python leider nicht unterstützt wird, habe ich mal den Quelltext in PDF-Form deutlich hübscher und besser lesbarer angehängt.

Moderiert von Christian S.: Topic aus Algorithmen, Optimierung und Assembler verschoben am Mo 20.11.2006 um 01:22

Einloggen, um Attachments anzusehen!

Martin1966 · Beiträge: 1068 Win 2000, Win XP Delphi 7, Delphi 2005

Moin!

Ich habs auch am Samstag gesehen und fand das Kartenspiel recht gut. ;-)

Als Delphi Programmierer habe ich mir dann auch gleich überlegt wie der Computer vorgehen müsste wenn er den Part eines Spielers übernehmen würde.

Viel ist mir dabei nicht eingefallen. :mrgreen:

Das einzige wäre, dass der Computer immer 100%ig genau weiß welche Karten der andere Spieler noch nicht gezogen hat. Das wäre ein kleiner Vorteil gegenüber dem menschlichen Spieler der sich vielleicht nicht alle Zahlen seines Gegenspielers merken kann.

Vielleicht haben andere von Euch noch Ideen... ;-)

Lg Martin

_________________
Ein Nutzer der Ecke ;-)

fidionael · Verfasst: Mo 20.11.06 11:13

Martin1966 hat folgendes geschrieben:

Das einzige wäre, dass der Computer immer 100%ig genau weiß welche Karten der andere Spieler noch nicht gezogen hat. Das wäre ein kleiner Vorteil gegenüber dem menschlichen Spieler der sich vielleicht nicht alle Zahlen seines Gegenspielers merken kann.

Ich dachte auch zunächst, dass dies ein Vorteil seien müsste, vor allem da sie immer davon redeten, dass man nicht sehen dürfte und sich merken müsste, welche Karten der Andere bereits gespielt hat. Doch bei weiterer Überlegung bin auch hier skeptisch: Was bringt es mir denn, zu wissen, welche Karten mein Gegner hat, bzw. nicht hat? Sichere Gewinnkarten bleiben sichere Gewinnkarten, egal wie ich sie spiele und über die Reihenfolge in der mein Gegner spielen wird, sagt mir auch dieses Wissen nichts.

Zum Beispiel:

markieren

Quelltext

1:
2:
3:
4:
5:

Spieler1:
1 3 4 7 9

Spieler2:
4 5 8 10 11

Hier weiß ich, dass Spieler2 im Worstcase noch zwei sichere Stiche hat (10 und 11) und im Bestcase alle Stiche bekommt. Dies zu wissen bringt mir jedoch nichts bei der Entwicklung einer Strategie, da ich nicht wissen kann, wann der Gegner welche Karte legt.

LLCoolDave · Beiträge: 212 Win XP Delphi 2005

fidionael hat folgendes geschrieben:

Zum Beispiel:

markieren

Quelltext

1:
2:
3:
4:
5:

Spieler1:
1 3 4 7 9

Spieler2:
4 5 8 10 11

Hier kommt es für mich in einer Mensch/Mensch Situation ganz darauf an, wie ich den Gegner einschätze.

Erst mal meine Strategie als Spieler 2:

Ich würde hier als Spieler2 ganz klar die 4 spielen. Damit gewinne ich gegen eine 1 und eine 3 und es gibt ein Unentschieden gegen die 4 des Gegners. Aus eigener Erfahrung weiß ich, dass falls mein Gegenspieler weiß das ich noch die 10 und die 11 habe (wovon ich ausgehe), dieser versuchen wird, seine 9 und 7 länger aufzubewahren, weil er damit hofft am Ende noch einen Stich zu machen, weil ich meine beiden sicheren Stiche zu früh vergeude. In jedem Fall rechne ich gegen einen normal starken Gegner nicht damit, dass er die 7 spielt, die einzige gute Karte in seiner Situation. Spielt er die 9, verliere ich zwar den Stich, habe dadurch aber mit meiner 8 einen weiteren Stich sicher.

Als Spieler1 würde ich, wie schon erwähnt, die 7 spielen, ausser ich hab berechtigte Annahme zu glauben, mein Gegner würde die 4 spielen, in welchem Fall ich diese mit meiner entwerte (bzw je nach Punkte Situation. Bei der gegebenen kartenverteilung gehe ich von einem Stand 4:2 für Spieler 1 aus), um mit der 7 die 5 schlagen zu können und mit der 9 die 8. Die 9 in dieser Situation würde ich eher nicht spielen, ausser ich weiß dass ich einen strategisch sehr starken Spieler hab, der meine 7 vorhersieht, in dem Fall würde ich die 1 spielen, da ich davon ausgehe, dass mein Gegner aus eben diesem Grund die 10 oder 11 spielen könnte, um meine 9 als Konter zu schlagen.

Wie man sieht besteht der Großteil des Spiels nicht aus Strategie, sondern aus Psychologie und Mindgames. Es geht darum, genau das zu tun von dem man ausgehen kann dass der Gegner nicht damit rechnet, bzw. es ihm am ehesten schadet. Dabei hängt das Vorgehen SEHR stark davon ab, welche Informationen ich über den Gegner habe und welche Information er über mich hat (dazu gehört auch, welche Informationen er glaubt über mich zu haben, sozusagen ein MetaMindgame).

Ob es eine allgemein gute Strategie gegen einen unbekannten Gegner gibt, weiß ich nicht, es wäre aber recht interessant da mal danach zu suchen. Als guten Eröffnungszug schlage ich einfach mal die 3 vor, da:

-Viele Spieler mit einer 1 anfangen werden, in der Hoffnung dass der Gegner eine hohe Karte spielt, und sie somit förmlich vergeudet.
-Einige Spieler aus eben diesem Grund eine 2 Spielen, die im Falle einer Niederlage nur einen Geringfügig größeren Verlust darstellt, aber gegen die vielen 1er gewinnt.

Mit der 3 liege ich in beiden Fällen vorne, der eigentliche Verlust ist nicht sonderlich viel höher (die unteren 3-4 Karten sin eh eher Opfer als Angriffskarten, die ausser in wenigen Situationen mehr taktische Züge als den Gewinn eines Stichs bewirken). Spielt mein Gegner eine 3-6 habe ich zwar keinen Stich gemacht, aber die Information gewonnen, dass ich wohl gegen einen einigermaßen durchdachten Spieler spiele. Alle anderen Karten beinhalten imo keine weiteren Informationen.

Ob man öfters gegen den selben Spieler spielen sollte hängt davon ob, ob dieser mitdenkt und auf einer Metaebene Strategien überlegt. Macht er dies auf einem ähnliche Niveau wie man selbst, sollte man nach wenigen Spielen den gegner wechseln, wenn es um den Gewinn geht, ähnlich wie beim Poker. Am lukrativsten kann man gegen solche Menschen spielen, wenn sie einen nicht kennen und man ihnen vortäuschen kann, ein miserabler Spieler zu sein.

Ähnlich wie beim Poker kommt es in diesem Spiel nicht nur auf die Karten an, sondern vorallem um das richtige Einschätzen des Gegners und der daraus resultierenden Strategie. Da auch das Glück aussen vor ist und beide Spieler die exakt selben Chancen haben, und zudem die Komplexität des eigentlichen Spiels (nicht des Metaspiels) sehr gering ist, glaube ich kaum dass es analog zum Rechnen mit Odss&Outs und Starting Hands Charts beim Poker eine simple Strategie gibt, mit der auch Anfänger einigermaßen rentabel spielen können.

Vielleicht sollten wir einfach mal verschiedene Ideen für Strategien durchprobieren und diese gegeneinander antreten lassen. Vielleicht hilft uns das ja weiter in die Richtung einer allgemein guten Strategie.

Edit: Achja, jetzt hab ich ja ganz die Antwort auf die vereinfachte Version mit dem zufällig ziehenden Gegner doch ganz vergessen. Ich schlage da mal diese Strategie vor. Sie ist wohl nicht optimal, aber sie sollte langfristig gewinnen können, wenn mir langweilig ist kann ich ja mal überlegen ob ich das beweisen kann.

markieren

Quelltext

1:
2:
3:

a) WENN Karte, die KLEINER ALS jede gegnerische Karte DANN a1 SONST b
   a1) WENN Median der Gegnerkarten HÖHER ALS Median der eigenen Karten DANN spiele karte aus a SONST b
b) spiele niedrigste Karte, die Median des Gegners schlägt.

Einzige Frage dabei ist ob man als Median bei gerader Kartenzahl die obere oder untere der beiden mittleren Karten wählt (Mittelwert ist eher ungünsitg imo). Ich denke der Unterschied ist marginal, ich schlage aber mal aus dem Bauch heraus vor, dass man mit der höheren Karte etwas besser da steht, oder zumindest nicht schlechter. Zumindest sollte man mit dieser Strategie in jedem Zug entweder die besseren Chancen haben, den Gegner zu schlagen (b) oder die Chancen des Gegners zu verschlechtern, da er wahrscheinlicher eine Karte spielt, die seine Situation verschlechtert als verbessert (a1).

In wiefern diese Strategie auch gegen Menschliche Gegner funktioniert ist fragwürdig, sie ist leicht zu durchschauen und spielt nicht konkret gegen einen Gegner sondern gegen eine Kartenmenge. Die Taktischen und Strategischen Züge werden imo soweit von einem Zufallsspiel abweichen, dass man mit dieser Strategie keinen Vorteil haben sollte. Als Eröffnungsspiel gegen einen unbekannten Gegner halte ich sie dennoch für sinnvoll.

fidionael · Verfasst: Mo 20.11.06 16:09

Ui, du hast dir ja richtig viele Gedanken gemacht :-)

In diese Richtung habe ich auch schon überlegt, aber ich wollte nun nicht zu tief in das Einschätzen des Gegners eingehen, da ich (wie oben bereits gesagt) den Schwerpunkt auf der informatischen Ansichtsweise anstatt den zwischenmenschlichen Beziehungen setze. Während das Einschätzen eines Gegners immer eine rein subjektive Angelegenheit ist, bei der man sich auch beliebig verschätzen kann, lassen sich Erkenntnisse in der informatischen Sichtweise wenigstens begründen und beweisen, was in meinen Augen die einzige Grundlage ist, auf der man wirklich diskutieren kann (zumindest in einem Programmierforum, bei einem Psychologieforum sähe dies vermutlich anders aus).

LLCoolDave hat folgendes geschrieben:

Vielleicht sollten wir einfach mal verschiedene Ideen für Strategien durchprobieren und diese gegeneinander antreten lassen. Vielleicht hilft uns das ja weiter in die Richtung einer allgemein guten Strategie.

Das ist, finde ich, eine tolle Idee und ich wäre voller Begeisterung, wenn sich der ein oder andere noch bereit erklären würden, hierfür Strategien zu entwickeln und zu testen. Wir können ja dann unsere jeweilig entwickelte Strategie implementieren und ihre Gewinnquote gegen einen zufällig ziehenden Computer festhalten.

LLCoolDave · Beiträge: 212 Win XP Delphi 2005

Gegen einen zufällig ziehenden Gegner zu spielen ist langweilig. Ich bin mir recht sicher, dass meine Strategie aus dem Edit dort langfristig gewinnen sollte, ich implementiere das Ganze mal schnell als Test. Interessanter wäre es, die Strategien direkt gegeneinander antreten zu lassen, ohne dass sie wissen, gegen wen sie spielen.

Edit: Die von mir oben genannte Strategie spielt auf 100000 Spiele etwa (gemittelt):
51400 Siege, 34000 Niederlagen, 14600 Unentschieden

Die Schwankungen sind gering und belaufen sich auf etwa +-300 in jeder Kategorie. Selbst wenn man gegen eine Bank spielen würde, bei der man bei Gewinn verdoppelt und sowohl bei Niederlage als auch Unentschieden sein Geld verliert, würde man so gegen den Zufall profit machen =)

fidionael · Verfasst: Mo 20.11.06 17:01

Ich habe deinen Algorithmus auch mal implementiert, komme aber zu einem völlig anderem Ergebnis:

40.000 Gewinne (d.h. 60.000 Niederlagen oder Unentschieden)

Demnach würde man tendenziell verlieren. Zwar nicht allzuschnell, aber man verliert.

Der Ausschnitt deines Algorithmus hier, die vollständige Implementation wie bereits oben hübsch und in Farbe im Anhang.

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

def LLCoolDaveStrategy(self):
    """Strategievorschlag von LLCoolDave aus dem Delphi-Forum:
    a) WENN Karte, die KLEINER ALS jede gegnerische Karte DANN a1 SONST b
    a1) WENN Median der Gegnerkarten HÖHER ALS Median der eigenen Karten DANN
        spiele karte aus a SONST b
    b) spiele niedrigste Karte, die Median des Gegners schlägt."""
    if self.deck[0][0] < self.deck[1][0]:
      if median(self.deck[1]) > median(self.deck[0]):
        return self.deck[0][0]
    n = 0
    while self.deck[0][n] < median(self.deck[1]):
      if n < len(self.deck[0])-1:
        n += 1
      else:
        break
    return self.deck[0][n]

Einloggen, um Attachments anzusehen!

LLCoolDave · Beiträge: 212 Win XP Delphi 2005

Mmh, du berechnest den Median bei gerader Kartenzahl, indem du die beiden Mittleren Karten addierst und durch zwei teilst. Nimm stattdessen einfach die höhere der beiden Karten und versuche es nochmal. Dieser feine Unterschied macht viel bei der Strategie aus.

Edit: Und nochwas, ich kann zwar kein Python, aber soweit ich den Code verstehe nimmst du die erste Karte aus deinem Stapel, die größer oder gleich dem gegnerischen Median ist. Das ist falsch, du solltest die Karte nehmen, die den Median schlägt.

Martok · Verfasst: Mo 20.11.06 18:19

Das interessiert mich jetzt aber auch.

Schreibt doch mal eure Algos (Random, User (menschl. Spieler), Dave, usw.) so, dass sie sich mit Telnet verbinden auf einen Server.

Kommandos (vom Client aus):
HELLO - Anmeldung
LIST - gibt die Karten aus, die der Spieler hat
PUT nummer - legt die Karte mit dem Wert nummer

Antworten vom Server:
GAME - neues Spiel startet
ROUND - neue Runde startet
WIN
LOSS - Gewonnen/Verloren

Der Server kommt heute Abend irgendwann, je nachdem, wann ich zuhause bin, dann können wir mal loslegen mit Real Life Tests

Grüße,
Martok

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

fidionael · Verfasst: Mo 20.11.06 22:31

LLCoolDave hat folgendes geschrieben:

Mmh, du berechnest den Median bei gerader Kartenzahl, indem du die beiden Mittleren Karten addierst und durch zwei teilst. Nimm stattdessen einfach die höhere der beiden Karten und versuche es nochmal. Dieser feine Unterschied macht viel bei der Strategie aus.

Okay, ist korrigiert. Ich habe mich bei meiner Implementation des Medians an die Richtlinien des Medians bei Stichproben aus der Wikipedia gehalten.

LLCoolDave hat folgendes geschrieben:

Edit: Und nochwas, ich kann zwar kein Python, aber soweit ich den Code verstehe nimmst du die erste Karte aus deinem Stapel, die größer oder gleich dem gegnerischen Median ist. Das ist falsch, du solltest die Karte nehmen, die den Median schlägt.

Auch das ist nun korrigiert.

Mit dem neuen, korrigierten Algorithmus komme ich auf... die selben Ergebnisse. Erstaunlich ist jedoch, wenn man sich auch die Niederlagen und Unentschieden betrachtet, dass man genau genommen doch nicht verliert:

markieren

Quelltext

1:
2:
3:
4:
5:

Gewonnen: 40061
Verloren: 39842
Unentschieden: 20097

Gewinnquote: 40%

Aber Tatsache ist, dass ich immer noch keine Gewinne verzeichne, auch wenn ich den Sinn deiner Heuristiken durchaus verstehe. Den Quelltext aktualisiere ich im obigen Post.

LLCoolDave · Beiträge: 212 Win XP Delphi 2005

Find ich seltsam. Ich kann ja mal meinen Quellcode posten, auch wenn der nur in 4 minuten dahingeschlampt war (ist völlig ineffektiv, unegordnet, unkommentiert etc.), vielleicht kommen wir darauf woher die unterschiedlichen ergebnisse kommen.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:

procedure TForm1.Button1Click(Sender: TObject);
var sl1,sl2: TStringlist;
    tempint,tempint2: integer;
    a,b,aw,bw: integer;
    w,l,d: integer;
    i,j,k: integer;
    bool: boolean;
begin
sl1 := TStringlist.create;
sl2 := TStringlist.create;
w := 0;
l := 0;
d := 0;
for i:=1 to StrtoInt(Edit1.text) do
begin
sl1.clear;
sl2.clear;
aw := 0;
bw := 0;
  for j:=1 to 11 do
     begin
     sl1.add(InttoStr(j));
     sl2.add(InttoStr(j));
     end;
for j:= 1 to 11 do
begin
tempint2 := Random(sl1.count);
a := StrtoInt(sl1[tempint2]);

bool := false;
if StrtoInt(sl2[0]) < StrtoInt(sl1[0]) then
  begin
  tempint := Floor(sl1.count/2);
  if StrtoInt(sl2[tempint]) < StrtoInt(sl1[tempint]) then bool:= true;
  end;

if bool = false then
begin
tempint := StrtoInt(sl1[Floor(sl1.count/2)]);
for k:=0 to sl2.Count-1 do
begin
if StrtoInt(sl2[k]) > tempint then begin b := StrtoInt(sl2[k]); break; sl2.Delete(k); end;
end;
end else begin b:= Strtoint(sl2[0]); sl2.delete(0); end;

if a <> b then
  if a > b then inc(aw) else inc(bw);

sl1.Delete(tempint2);
end;

if aw = bw then inc(d) else
  if aw > bw then inc(l) else inc(w);

end;
Label1.Caption := 'w: '+Inttostr(w);
Label2.Caption := 'l: '+Inttostr(l);
Label3.Caption := 'd: '+Inttostr(d);
end;

Dafür habe ich gerade noch einen fehler korigiert was die Zahlen etwas ändert, aber meinem Eindruck nach setzt meine Simulation meine Stratgie so um wie ich sie beschrieben habe. Jetzt habe ich etwa 48000 Siege, 40000 Niederlagen und 12000 Draws. Ich schau mir gleich nochmal deinen code an.

fidionael · Verfasst: Mo 20.11.06 23:50

So, der Übersicht zu liebe sind hier erstmal meine bisherigen Ergebnisse, alle bei 100000 Spielen:

markieren

Zufall vs Zufall

1:
2:
3:
4:
5:

Gewonnen: 40052
Verloren: 39778
Unentschieden: 20170

Gewinnquote: 40.0%

markieren

LLCoolDave-Algo vs LLCoolDave-Algo

1:
2:
3:
4:
5:

Gewonnen: 0
Verloren: 0
Unentschieden: 100000

Gewinnquote: 0.0%

markieren

LLCoolDave-Algo vs Zufall

1:
2:
3:
4:
5:

Gewonnen: 39867
Verloren: 39799
Unentschieden: 20334

Gewinnquote: 39.9%

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme