Von Günther Rosenbaum , 11.07.2005
Untersuchung einiger Strategien beim Spiel Mikro-Bluff für 2 Spieler
Wie im Teil 1 dieses Artikels beschrieben, ist mit "Mikro-Bluff" hier das Endspiel von Bluff mit 2 Spielern und je einem Würfel gemeint.
Vor der Diskussion einer speziellen Strategie möchte ich aber noch 2 Zitate aus Teil II von Ferguson, Thomas. S.: Game Theory erläutern, da wir diese Argumente weiter unten nutzen werden.
Zitat 1:
<The Minimax Theorem.
Every finite game has a value, and both players have minimax strategies.
We note one remarkable corollary of this theorem. If the rules of the game are changed
so that Player II is required to announce her choice of a mixed strategy before Player I
makes his choice, then the apparent advantage given to Player I by this is illusory. Player II can simply announce her minimax strategy.
…..
Any p ∈X* that achieves the maximum of (3) is called a best response or a Bayes
strategy against q. In particular, any row i that achieves the maximum of (1) is a (pure)
Bayes strategy against q. There always exist pure Bayes strategies against q for every
q ∈Y* in finite games. > (Aus Teil II, Kapitel 4)
Wir sehen:
- Wenn ein Spieler seine optimale Minimax-Strategie wählt, so kann er diese ruhig veröffentlichen; sein Gegenspieler kann hieraus keinen Vorteil ziehen !
- Wenn wir zu einer vorgegebenen Strategie eines Spielers eine optimale Gegenstrategie suchen (best response), so findet man hier auch immer eine reine (nicht gemischte) Strategie! Eine solche optimale Gegenstrategie zu einer vorgegebenen Minimax-Strategie realisiert zwar den gleichen Spielwert wie die optimale Minimax-Strategie des Gegenspielers, ist allerdings im allgemeinen keine optimale Minimax-Strategie!
Zitat 2:
< In general, the dimension of the space of behavioral strategies is much smaller than
the dimension of the space of mixed strategies. The question arises - Can we do as well
with behavioral strategies as we can with mixed strategies? The answer is we can if both
players in the game have perfect recall . The basic theorem, due to Kuhn in 1953 says that in finite games with perfect recall, any distribution over the payoffs achievable by mixed strategies is achievable by behavioral strategies as well. > (Aus Teil II, Kapitel 5)
- Wir
befassen uns hier immer mit der expliziten Darstellung des Spieles als
"Kuhn-Baum", also genau so, wie die Spieler ihre Züge abwechselnd durchführen
... und nicht mit der Matrix-Darstellung des Spieles. Der obige Satz sagt nun, dass
wir unsere Strategien als Verhaltensstrategien beschreiben dürfen - also zu jedem
Zeitpunkt als Wahrscheinlichkeitsverteilung über die verfügbaren Alternativen! (Denn
Bluff hat die Eigenschaft "perfect recall", d.h. die Spieler vergessen keine
Infos über frühere Züge und Erkenntnisse).
Nun aber Schluss mit der Theorie, die hier an dieser Stelle doch nie vollständig sein kann !
Wir wollen uns jetzt mit einer ganz speziellen Strategie bei Mikro-Bluff beschäftigen, die lange Zeit bei einigen Westparkgamern als ziemlich gut - ja sogar optimal galt!
Die folgende Behauptung ist falsch:
Der 1. Zug des Startspielers "Konstant 4 ansagen, unabhängig vom eigenen Würfelzug" ist optimal beim Bluff-Endspiel mit 2 Personen mit jeweils 1 Würfel.
Leider ist das ja keine komplette Beschreibung einer Strategie, sondern nur der ERSTE Zug von vielen möglichen Strategien. Die Behauptung heißt also eigentlich nur: Es gibt eine optimale Minimax- Strategie (A) mit Startzug "Konstant 4".
Diese Behauptung hat dann zu einer schnellen (und unbedachten) Wette geführt - weshalb ich diese Behauptung hier also widerlegen werde (und damit die Wette gewonnen habe J).
Der Gegenbeweis muss also zeigen, dass keine Strategie mit "Konstant 4 " als Startzug (egal welche Folgeansagen gemacht werden), optimal sein kann! (Dies ist leider bedeutend schwieriger zu beweisen, als wenn diese Strategie komplett ausformuliert wäre mit allen Reaktionen in den Folgerunden!)
Wir führen den Beweis in 2 Schritten:
1) Wir definieren eine
Gegenstrategie (B1) für Spieler 2 und zeigen damit, dass die "Konstant 4
Strategie" mit Wahrscheinlichkeit <= 15/36 gegen (B1) gewinnt.
Es mag noch eine bessere Gegenstrategie des Spielers 2 geben, aber wir wissen zu
mindestens, dass die Gewinnwahrscheinlichkeit von Spieler 1 bei optimaler Gegenwehr von
Spieler 2 höchstens 15/36 ist !
2) Wir definieren dann eine "bessere" Strategie (A2) als "Konstant 4", von welcher wir zeigen werden, dass sie bei optimaler Gegenwehr von Spieler 2 eine Gewinnwahrscheinlichkeit von mehr als 15/36 garantiert!
Da die optimale Minimax-Strategie von Spieler 1 gerade so definiert ist, dass sie die beste Gewinnwahrscheinlichkeit unter allen möglichen Strategien von Spieler 1 bei optimaler Gegenwehr von Spieler 2 garantiert, kann "Konstant 4" also nicht optimal sein - denn es gibt ja noch eine bessere Strategie (A2).
Beginnen wir also mit Schritt 1:
Sei die Strategie A1 für den Startspieler definiert durch:
1. Runde:
Ungesehen immer 4 ansagen !
2. Runde:
"optimal" (mit vollständiger Kenntnis der Strategie B1, was dem Spieler 1 gegebenenfalls noch einen Vorteil verschafft)
Sei die Strategie B1 für den Spieler 2 definiert durch:
1. Runde:
4 gehört: Hat 1,2,3 : anzweifeln
: Hat 4,5 oder * : auf 5 erhöhen
2. Runde:
Hört * und hat * : Auf Pasch * erhöhen;
sonst immer anzweifeln
Behauptung 1: Gewinnwahrscheinlichkeit der Strategie A1 ist <= 15/36
Beweis:
Wir berechnen die Gewinnwahrscheinlichkeit von A1 bei fest vorgegebenem B1 und erhalten damit eine obere Schranke für die Gewinnwahrscheinlichkeit von A1.
Berechnung:
1. Sp2 hat 1,2,3 und hört 4:
Anzweifeln: 2/6 Gewinnwahrscheinlichkeit für Sp2, 1/6 für Sp1
2. Sp2 hat 4,5,* und hört 4:
Spieler 2 erhöht auf 5;
2.1 Sp1 hat 1..3:
Sp1 weiß: Spieler 2 hat 4,5 oder *;
Alternativen: Anzweifeln oder auf * oder Pasch 1..3 erhöhen ergibt 1/3 Chance;
Es ergeben sich also folgende Gewinnwahrscheinlichkeiten:
Sp2: ½ * ½ * 2/3= 6/36 Sp1: 3/36
2.2 Sp1 hat 4:
Ansage Pasch 4 und gewinnen mit 2/3 (anzweifeln oder * liefern nur 1/3)
Sp2: ½ * 1/6 * 1/3 =1/36 Sp1: 1/2*1/6*2/3 = 2/36
2.3 Sp1 hat 5:
Anzweifeln geht nicht; Erhöhen auf Pasch 5 liefert 2/3 ( * liefert nur 1/3)
Sp2: 1/2 * 1/6*1/3 = 1/36 Sp1: ½ * 1/6 * 2/3 = 2/36
2.4 Sp1 hat *:
Ansage *, Pasch 5/4 liefern 2/3; Pasch 1,2,3, * liefert 1/3
Sp2: ½* 1/6 * 1/3 = 1/36 Sp1: ½ * 1/6 * 2/3 = 2/36
In Summe ergeben sich also folgende Gewinnwahrscheinlichkeiten:
Sp2 = 12/36 + 6/36 + 1/36 +1/36 + 1/36 = 21/36
Sp1 = 6/36 + 3/36 + 2/36 + 2/36 + 2/36 = 15/36
Anbei noch die Matrix der Gewinnwahrscheinlichkeiten für Spieler 2 bei den 36 möglichen Würfelergebnissen (bei der oben fett markierten Strategie von Spieler 1; *1/36)::
Sp1/Sp2 |
1 |
2 |
3 |
4 |
5 |
* |
Summe/6 |
|
1 |
1 |
1 |
1 |
0 |
1 |
1 |
5/6 |
|
2 |
1 |
1 |
1 |
0 |
1 |
1 |
5/6 |
|
3 |
1 |
1 |
1 |
0 |
1 |
1 |
5/6 |
|
4 |
0 |
0 |
0 |
0 |
1 |
0 |
1/6 |
|
5 |
1 |
1 |
1 |
1 |
0 |
0 |
2/3 |
|
* |
0 |
0 |
0 |
1 |
0 |
0 |
1/6 |
|
Summe/6 |
2/3 |
2/3 |
2/3 |
1/3 |
2/3 |
½ |
21/36 |
q.e.d.
Nun folgt der Schritt 2:
Sei die Strategie A2 für den Startspieler definiert durch:
1. Runde
1,2,* -> Zu je 1/3 Wahrscheinlichkeit 3,4,5 sagen
3,4,5 -> die Wahrheit sagen
2. Runde
Hört 4:
- hat 1,2,3: anzweifeln
- hat 4,5,*: auf Pasch 4 erhöhen
Hört 5:
- hat 1,2,3,4: anzweifeln
- hat 5,*: auf Pasch 5 erhöhen
Hört *:
- hat 1,2,3,4,5: anzweifeln
- hat *: Pasch * ansagen
Hört beliebigen Pasch : Anzweifeln
weitere Runden: Anzweifeln
Behauptung 2: Gewinnwahrscheinlichkeit der Strategie A2 ist >= 46/108>15/36
Beweis:
Spieler 2 kennt die Strategie von Spieler 1 und nutzt die optimale Gegenstrategie !
(Spieler 1 hat nach seinem zweiten Gebot alle Informationen über seinen Wurf preisgegeben!)
Die optimale Gegenstrategie von Spieler 2 ist jeweils fett markiert;
z.B. "hat 4: hört 3 : 4 : 5/6" bedeutet:
Spieler 2 hat eine 4 geworfen; er hört das Gebot "3" von Spieler 1 und antwortet mit einem Gebot "4" und gewinnt in diesem Fall mit einer bedingten Wahrscheinlichkeit von "5/6" . Die alternativen (schlechteren) Strategien sind in den Folgezeilen aufgeführt um zu überprüfen, dass keine besseren Alternativen vorhanden sind
hat *: hört 3 : 5 : 1
Anzweifeln : 0
4 : 1
5 : 1
* : 5/6
Pasch 1,2 : 1/3
Pasch 3 : 2/3
Pasch 4,5 : 1/6
Pasch * : 1/6
hört 4 : 5 : 1
(Berechnung dito)
hört 5 : * : 5/6
Anzweifeln : 0
* : 5/6
Pasch 1,2 : 1/3
Pasch 3,4 : 1/6
Pasch 5 : 2/3
Pasch * : 1/6
hat 5: hört 3 : 5 : 5/6
Anzweifeln : 1/3
4 : 1/6
5 : 5/6
* : 1/6
Pasch 1,2,3,4 : 0
Pasch 5 : 1/6
Pasch * : 0
hört 4 : 5 :5/6
(Berechnung dito)
hört 5 : Pasch 5 : 2/3
Anzweifeln : 0
* : 1/6
Pasch 1,2,3,4 : 0
Pasch 5 : 2/3
Pasch * : 0
hat 4: hört 3 : 4 : 5/6
Anzweifeln : 1/3
4 : 5/6
5 : 1/6
* : 1/6
Pasch 1,2,3 : 0
Pasch 4 : 1/6
Pasch 5 : 0
Pasch * : 0
hört 4 : Pasch 4 : 2/3
Anzweifeln : 0
5 : 1/6
* : 1/6
Pasch 1,2,3 : 0
Pasch 4 : 2/3
Pasch 5 : 0
Pasch * : 0
hört 5 : Anzweifeln : 1/3
Anzweifeln : 1/3
* : 1/6
Pasch 1,2,3 : 0
Pasch 4 : 1/6
Pasch 5 : 0
Pasch * : 0
hat 3: hört 3 :Pasch 3 : 2/3
Anzweifeln : 0
4 : 1/6
5 : 1/6
* : 1/6
Pasch 1,2 : 0
Pasch 3 : 2/3
Pasch 4,5 : 0
Pasch * : 0
hört 4 :Anzweifeln : 1/3
Anzweifeln : 1/3
5 : 1/6
* : 1/6
Pasch 1,2 : 0
Pasch 3 : 1/6
Pasch 4,5 : 0
Pasch * : 0
hört 5 :Anzweifeln : 1/3
Anzweifeln : 1/3
* : 1/6
Pasch 1,2 : 0
Pasch 3 : 1/6
Pasch 4,5 : 0
Pasch * : 0
hat 2: Anzweifeln : 1/3
hört 3: anzweifeln : 1/3
4 : 1/6
5 : 1/6
* : 1/6
Pasch 1,3,4,5 : 0
Pasch 2 : 1/3
Pasch * : 0
Hört 4: anzweifeln : 1/3
5 : 1/6
* : 1/6
Pasch 1,3,4,5 : 0
Pasch 2 : 1/3
Pasch * : 0
Hört 5: anzweifeln : 1/3
* : 1/6
Pasch 1,3,4,5 : 0
Pasch 2 : 1/3
Pasch * : 0
hat 1: Anzweifeln : 1/3
(Berechnung wie bei 2)
In Summe ergeben sich also folgende Gewinnwahrscheinlichkeiten für Spieler 2:
1/6 * ( 2/3 + 1/3*5/6 + 2/3*5/6 + 1/3*2/3 + 1/3*5/6 + 1/3*2/3 + 1/3*1/3 +
+ 1/3*2/3 + 2/3*1/3 + 1/3 + 1/3)
= 1/6 * 1/18 *(12+5+10+4+5+4+2+4+4+6+6)
= 1/6 * 1/18 * 62 = 62/108
Sp1 = 46/108 > 45/108 = 15/36.
Anbei noch die Matrix der Gewinnwahrscheinlichkeiten für Spieler 2 bei den 36 möglichen Würfelergebnissen (bei der oben fett markierten Strategie von Spieler 1; *1/36)::
Sp1/Sp2 |
1 |
2 |
3 |
4 |
5 |
* |
Summe/6 |
|
1 |
1 |
1 |
2/3 |
2/3 |
2/3 |
1 |
5/6 |
|
2 |
1 |
1 |
2/3 |
2/3 |
2/3 |
1 |
5/6 |
|
3 |
0 |
0 |
1 |
1 |
1 |
1 |
4/6 |
|
4 |
0 |
0 |
0 |
1 |
1 |
1 |
3/6 |
|
5 |
0 |
0 |
0 |
0 |
1 |
1 |
1/3 |
|
* |
0 |
0 |
1/3 |
1/3 |
1/3 |
2/3 |
5/18 |
|
Summe/6 |
1/3 |
1/3 |
4/9 |
11/18 |
7/9 |
17/18 |
62/108 |
q.e.d.
Die Untersuchung der "Konstant 4 Strategie" ist damit abgeschlossen -
Die echten, optimalen Minimax-Strategien bei Mikro-Bluff kennen wir aber immer noch nicht !
Die obigen Untersuchungen liefern ein paar Hinweise darauf - vielleicht gibt es die Lösung dann in einem späteren Artikel ?!
Als Abschluss dieses Artikels möchte ich noch die Berechnung der Gewinnwahrscheinlichkeiten von einigen Strategien anfügen, die jeweils in der zweiten Runde generell "Anzweifeln" !
|
Strategie A = "Konstant 5":
Falls 1,2,3,4,5,* gewürfelt , sage 5 an In Folgerunden immer anzweifeln !
Gewinnwahrscheinlichkeit = 1/3 |
Berechnung Strategie A:
1) Spieler 2 hört 5:
1a)er hat 1,2,3,4
Zweifeln liefert:
Spieler 2: 2/3 Wahrscheinlichkeit zu gewinnen
Alles andere ist schlechter.
1b) er hat 5
Pasch 5 liefert:
Spieler 2: 1/3
1c) er hat *
Ansage * liefert: 1
In Summe ergibt das:
Gewinnwahrscheinlichkeit für Spieler 2:
2/3 * 2/3 + 1/6 * 1/3 + 1/6 * 1 =
= 8/18 + 1/18 + 3/18
= 24/36
Strategie A: Spieler 1 hat also nur 12/36 = 1/3 Gewinnwahrscheinlichkeit !
|
Strategie B (Die modifizierte 4er Strategie; 0<=p<=1) 1,2,3,4,* -> 4 5 -> mit Wkeit p -> 5 mit Wkeit 1-p -> 4 Folgerunden anzweifeln.
Gewinnwahrscheinlichkeit = 10/36 + 3p/36 |
Berechnung Strategie B:
1)Spieler 2 hört 4
1a)er hat 1,2,3
Anzweifeln liefert: (4-p)/(6-p)
1b) hat 4
Pasch 4 liefert: 2/(6-p)
1c) hat 5
Ansage 5 liefert: 1
1d) hat *
Ansage * liefert: 1
In Summe ergibt Fall 1) also:
Gewinnwahrscheinlichkeit für Spieler 2:
(6-p)/6 *
( 1/2 * (4-p)/(6-p) +
1/6 * 2/(6-p) +
1/3 * (6-p)/(6-p) )
= 1/6 ( 2 - p/2 + 1/3 + 2 - p/3 )
= 1/6 (13/3 - p*5/6)
= 26/36 - p* 5/36
2) Spieler 2 hört 5
2a) er hat 1,2,3,4
Verloren: 0
2b) er hat 5,*
Ansage Pasch 5 liefert: 1
In Summe ergibt Fall 2) also:
Gewinnwahrscheinlichkeit für Spieler 2:
p/6 * ( 2/3 * 0 + 1/3 *1)
= p/18
1)+2) zusammen liefern also folgende Gewinnwahrscheinlichkeit für Spieler 2:
26/36 - P *5/36 + p/18
= 26/36 - p * 3/36
Sp1 minimiert dies mit p=1 zu 23/36 und garantiert sich mindestens 13/36 !!
Die Strategie "Konstant 4" (entspricht p=0) liefert nur 1 - 26/36 = 10/36 Gewinnwahrscheinlichkeit !
In diesem Sinne ist die Strategie "Konstant 4" (10/36) schlechter als "Konstant 5" (12/36)
Aber noch etwas besser ist mit 13/36 die folgende Strategie (p=1)
1,2,3,4,* -> 4
5 -> 5
Folgerunden anzweifeln.
All diese Aussagen gelten natürlich nur, falls in Runde 2 immer angezweifelt wird !!
|
Strategie C 1 -> Pasch 1 2,3,4,5 -> die Wahrheit sagen * -> Pasch 5 Folgerunden anzweifeln
Gewinnwahrscheinlichkeit = 13/36 |
Berechnung Strategie C:
1) Spieler 2 hört 2
hat 1 -> verloren
2 -> Pasch 2, gewinnt
3,4,5,* -> 3,4,5,* gewinnt
Wkeit: 1/6 * 5/6 = 5/36
2) hört 3
Wkeit: 1/6 * 4/6 = 4/36
3) hört 4
Wkeit: 1/6 * 3/6 = 3/36
4) hört 5
Wkeit: 1/6 * 2/6 = 2/36
5) hört Pasch 1
Anzweifeln liefert
Wkeit 1/6 * 2/3 = 1/9
6) hört Pasch 5
hat 1,2,3,4 -> anzweifeln, gewinnt
hat 5 -> verliert
hat * -> Pasch * , gewinnt
Wkeit 1/6 * 5/6 = 5/36
In Summe ergibt das also:
Gewinnwahrscheinlichkeit für Spieler 2:
1/36 * (5+4+3+2+4+5) = 23/36
Für Spieler 1 bleiben also noch 13/36 !
Dies ist genauso viel, wie die verbesserte "konstant 4" Strategie !