Inhoud De ‘Penney Ante game’ is een spel met een munt dat uitstekend in de kroeg gespeeld kan worden. Zeker omdat er altijd een winnende strategie is. Het spel is voor het eerst genoemd in een artikel in 1969 door Walter Penney en daarna uitgebreid besproken door Martin Gardner in 1974. Het spel wordt gespeeld met een munt en twee spelers. Beide spelers spreken vooraf een serie van drie worpen af (bijvoorbeeld KKM voor Kop, Kop, Munt). Daarna wordt de munt net zolang gegooid totdat de serie van één van de twee spelers is gegooid. De speler van wie de serie het eerst voorkomt is de winnaar. Stel dat speler1 de serie KKM heeft en speler2 de serie MKK heeft en de munt de sequentie KMKMMKK dan heeft speler2 gewonnen omdat zijn serie het eerst geworpen is (beurt 5 t/m 7 is namelijk MKK). Dit lijkt een eerlijk spel omdat de munt iedere keer een kans van 0,5 (50%) heeft om op Kop of Munt te vallen en omdat wij mensen een enorm slechte intuïtie van kansen hebben (de schrijver dezes is daar geen uitzondering op!). Maar het spel is verre van eerlijk. Speler2 kan altijd een winnende serie maken. Kijk maar naar onderstaande tabel: Een ander woord voor “Odds” is “kansverhouding” maar in de praktijk wordt meestal de Engelse term gebruikt. Dus als speler1 de serie MKK kiest dan moet speler2 de serie MMK nemen. Dan wint speler2 ±2 keer zo vaak. En kiest speler1 de serie MMM dan moet speler2 de serie KMM nemen en dan wint speler2 dus zo’n 7 keer meer dan speler1. Hoe kan speler2 nu makkelijk anticiperen met zijn keuze ten opzichte van speler1? Welnu: Speler2 maakt zijn serie door de tweede keuze van speler1 te veranderen (dus K wordt M en andersom) en die dan te laten volgen door de eerste twee keuzes van speler1. In Python heb ik een programmaatje geschreven dat dit spel simuleert. Hier is het resultaat: After 100 games you won 28 games with sequence TTH and I won 72 games with sequence HTT. Natuurlijk kan het ook anders uitvallen, het blijft altijd een gok hoe de munt valt. Maar hoe vaker je het speelt, met een bepaalde serie, hoe meer het naar de kansen vanuit bovenstaande tabel zal gaan. Maar hoe zit het nu met de kansen? Intuïtief ben je geneigd te zeggen dat de kans dat de munt op K of M valt 0,5 (50%) is, en dat is ook zo mits we een eerlijke munt hebben die ook niet op z’n zijkant terecht kan komen. En op de middelbare school hebben we geleerd dat het berekenen van onafhankelijke kansen een kwestie van vermenigvuldigen van kansen is. Maar even terug naar de basis. Wat is een kans? Wiskundig is een kans niets anders dan het quotiënt van het aantal gunstige gebeurtenissen en het totaal aantal gebeurtenissen: De notatie voor kans is: P(“kans op iets…”). De P is van het Engelse woord Probability. Voor het gooien van een munt is het totaal aantal gebeurtenissen twee, namelijk Kop en Munt. En de kans op Kop (en evenzo op Munt) met het opgooien van de munt levert dan een kans van 1/2 op. Wanneer we twee keer achter elkaar met een munt gooien dan zijn deze twee gebeurtenissen onafhankelijk van elkaar. Wanneer we drie keer achter elkaar met een munt gooien dan zijn de mogelijke uitkomsten: KKK, KKM, KMK, KMM, MKK, MKM, MMK en MMM, een totaal van 8. Wil ik nu de serie KMM gooien dan is dat 1 van de 8 ofwel 0,125 (12,5%). Dit resultaat kun je verkrijgen door alle individuele kansen met elkaar te vermenigvuldigen. De vraag is nu: Waarom zijn de kansen bij Penney Ante niet allemaal 1/8? Dit heeft te maken met het feit dat één van de gekozen series niet meteen na drie beurten hoeft op te treden! Het kan ook zijn dat dit pas optreedt na 10 beurten. En dat heeft invloed op de kans. Laten we eens kijken naar een aantal voorbeelden en hoe we de daarbij behorende kansen of odds verkrijgen. Voorbeeld 1: Speler1 kiest KKK, speler2 kiest (dan) MKK. Voorbeeld 2: Speler 1 kiest KKM, speler2 kiest MKK. Voor ons voorbeeld geldt dat a=1, r=1/2 en n loopt van 3 naar oneindig. Wat we dus nodig hebben is: En dat is: Dus P(KKM [hoe dan ook]) = 1/4 en daarmee is P(MKK [hoe dan ook]) = 1 – 1/4 = 3/4. Voorbeeld 3: Speler1 kiest KMK, speler2 kiest KKM. De kans dat speler2 wint is dus 2/3 en de odds zijn dus 2 staat tot 1. En zo kunnen we voor alle kansen een berekening “verzinnen”. John Conway is vooral bekend om zijn simulatie Life, waar in een eenvoudige wereld van cellen simpele regels voor geboorte, overleven en sterven van cellen zijn vastgelegd. Met een initiële vulling van de wereld ga je kijken wat er per generatie gebeurt. Het blijkt dat, ondanks de simpelheid van het geheel, het niet te voorspellen is hoe deze wereld er na x generaties zal uitzien. Conway heeft zich echter ook bezig gehouden met de mate van overlapping van verschillende patronen en kende hier een waarde aan toe. En in het Penney Ante spel hebben we te maken met patronen. Deze patronen bestaan immers uit K’s en M’s en hebben een lengte van 3. Laten we eens kijken hoe één en ander in z’n werk gaat. We gaan kijken naar de overlapping tussen de patronen ‘KKK’ en ‘MKK’ (voorbeeld 1). Zet beide patronen recht boven elkaar: MKK Wanneer beide patronen (lengte 3) overeenkomen zet je een 1 boven het eerste element van het bovenste patroon, anders zet je hier een 0 neer. 0 Schuif nu het bovenste patroon 1 plaats naar links, dan houden we het volgende over: KK Nu gaan we kijken naar de overeenkomst tussen het bovenste patroon en de eerste 2 elementen van het onderste patroon, dus eigenlijk kijken we naar: KK Komen beide overeen dan zetten we een 1 boven het linker element van het bovenste patroon (dit is dus element 2 van het oorspronkelijke patroon), anders een 0. 1 En de vorige stap herhalen we nogmaals. Dus het bovenste patroon weer een plaats naar links en vergelijken met het eerste element van het onderste patroon. Komen ze overeen dan zetten we een 1 erboven en anders een 0. 1 Het totale resultaat ziet er nu als volgt uit: 011 De 011 kan worden gezien als een binair getal en de decimale equivalent hiervan is 3. We zeggen nu dat de waarde van overlapping tussen KKK en MKK 3 is. Merk meteen op dat het “omgekeerde” niet (per se) hetzelfde getal oplevert: De waarde tussen MKK en KKK is: 000 Dus de waarde van overlapping tussen MKK en KKK is 0. Om nu de odds te berekenen tussen KKK en MKK kan de volgende formule gebruikt worden: Gegeven 2 tripels A en B dan zijn de odds van B tot A: ([AA] – [AB])/([BB] – [BA]), waarbij [xy] de waarde van overlapping is tussen y en x. In ons voorbeeld is A=KKK en B=MKK. We hebben dus [AA], [AB], [BB] en [BA] nodig. Hierboven hebben we al [BA] uitgerekend. Wanneer je Conway’s algoritme ook toepast op de andere combinaties dan krijg je: Invullen in bovenstaande formule geeft dan: Odds(MKK boven KKK) = (7-0)/(4-3) = 7/1 = 7. De bijbehorende kans is dan 7/8. De volledige odds-tabel: Met de bijbehorende kans-tabel: Zonder hier in te gaan op de (best wel ingewikkelde) achterliggende wiskunde, kunnen we ook nog iets zeggen over de lengte van de sequentie alvorens de gekozen triplet zal verschijnen. Vanuit de waarde van overlapping (van het triplet met zichzelf), zoals we die met het algoritme van Conway kunnen berekenen, blijkt het 2 x zo lang te duren alvorens een bepaald triplet optreedt. Bekijk eens de volgende tabel: Voordat bijvoorbeeld de triplet KKK zal optreden heb je een sequentie nodig van gemiddeld 14 x gooien met de munt. In de wiskunde heet het Penney Ante spel een non-transitief spel. Een voorbeeld van een transitieve relatie is het welbekende: Als a > b en b > c dan a > c of wat algemener: Als a b impliceert en b c impliceert dan impliceert a c. Als we deze voorbeelden non-transitief zouden maken dan krijgen we: Als a > b en b > c dan c > a of: Als a b impliceert en b c impliceert dan impliceert c a. Wat natuurlijk allemaal wat vreemd overkomt. Toch spelen kinderen vaak het non-transitieve spel “steen-papier-schaar” waarbij geldt: schaar wint van papier, papier wint van steen en steen wint van schaar: En dit is ook het geval met het Penney Ante spel. En dat maakt het allemaal zo boeiend. Hieronder het Python programma dat het spel simuleert: Hieronder de Excel UDF's (User Defiened Function) die ik heb gebruikt voor de tabellen: Function ConwayS(s1 As String, s2 As String) As Integer s = “” For a = 1 To 3 p = 0 Function Odds(s1 As String, s2 As String) If s1 <> s2 ThenInleiding
Hoe gaat het spel?
Speler 1
Speler 2
“Odds”
KKK
MKK
7tot 1
KKM
MKK
3tot 1
KMK
KKM
2tot 1
KMM
KKM
2tot 1
MKK
MMK
2tot 1
MKM
MMK
2tot 1
MMK
KMM
3tot 1
MMM
KMM
7tot 1
Dus kiest speler1 de serie MMK dan is de tweede keuze dus een M. Speler2 verandert de M in een K en zet daarachter dan de eerste twee keuzes van speler1 (MM). Speler2 maakt dus de serie KMM.
Wanneer ik de serie TTH (MMK) invul dan kiest de computer HTT (KMM). Stel dat ik met deze instellingen 100 rondes speel dan is de verwachting vanuit bovenstaande tabel dat de computer zo’n 75 rondes zal winnen.Kansen bepalen
De kans is altijd een getal tussen de 0 en 1 (beide doen mee).
Als de kans 0 is dan betekent dit dat de gebeurtenis nooit zal optreden.
Is de kans 1 dan betekent dit dat de gebeurtenis altijd zal optreden.
Zo is de kans dat je met een vervoermiddel door het paarse verkeerslicht rijdt gelijk aan 0 en de kans dat je ooit dood gaat gelijk aan 1.
Mogelijke uitkomsten zijn: KK, KM, MK, MM, een totaal van 4. Stel dat ik KK wil hebben dan is dat 1 van 4 ofwel 0,25 (25%).
De kans op K = 0,5, de kans op M = 0,5 en de kans op M = 0,5. De kans op KMM is dan 0,5 x 0,5 x 0,5 = 0,125.
Speler1 wint alleen als er 3 keer achtereen een K wordt gegooid. Die kans is P(KKK) = (1/2)3 = 1/8.
Dan is de kans op MKK: P(MKK) = 1 – P(KKK) = 1 – 1/8 = 7/8. De daarbij behorende odd is dan 7 staat tot 1.
Speler1 wint als in de 1e drie beurten KKM valt, of in vier beurten KKKM valt, of in vijf beurten KKKKM valt of in zes…
Het woordje “of” in bovenstaande zin betekent dat we al deze kansen bij elkaar moeten optellen.
Dus P(KKM | KKKM | KKKKM | …) = 1/8 + 1/16 + 1/32 + …
En dit is een meetkundige reeks. En hiervoor bestaat een algemene formule:
Hier is de situatie weer iets anders.
Stel nu p = P(KKM voor KMK).
Als de eerste worp een K is en de tweede ook een K dan is de kans op KKM natuurlijk 1/2. Als de eerste worp echter een M is dan begint het weer helemaal opnieuw en is de kans weer p.
we krijgen dus de vergelijking:
Maar er is ook een generieke manier om deze kansen uit te rekenen.Het algoritme van Conway
En die waarde kan worden omgezet in een kans.
KKK
In het voorbeeld komen de patronen niet overeen dus wordt het een 0:
MKK
KKK
KKK
KK(K)
In het voorbeeld komen beide patronen overeen, dus:
KK
KK(K)
In het voorbeeld komen ze overeen, dus:
K
K(KK)
MKK
KKK
KKK
MKK
[AA] = 7, [AB] = 0 en [BB] = 4.
Odds
KKK
KKM
KMK
KMM
MKK
MKM
MMK
MMM
KKK
1
2
2
7
1
2
1
KKM
1
0
0
3
1
1
0
KMK
1
2
1
1
1
2
1
KMM
1
2
1
1
1
0
0
MKK
0
0
1
1
1
2
1
MKM
1
2
1
1
1
2
1
MMK
0
1
1
3
0
0
1
MMM
1
2
1
7
2
2
1
P(B)
KKK
KKM
KMK
KMM
MKK
MKM
MMK
MMM
KKK
0,500
0,667
0,667
0,875
0,500
0,667
0,500
KKM
0,500
0,000
0,000
0,750
0,500
0,500
0,000
KMK
0,500
0,667
0,500
0,500
0,500
0,667
0,500
KMM
0,500
0,667
0,500
0,500
0,500
0,000
0,000
MKK
0,000
0,000
0,500
0,500
0,500
0,667
0,500
MKM
0,500
0,667
0,500
0,500
0,500
0,667
0,500
MMK
0,000
0,500
0,500
0,750
0,000
0,000
0,500
MMM
0,500
0,667
0,500
0,875
0,667
0,667
0,500
Gemiddelde wachttijd
C(onway)
gem. string lengte=2xC
KKK
7
14
KKM
4
8
KMK
5
10
KMM
4
8
MKK
4
8
MKM
5
10
MMK
4
8
MMM
7
14
Non-transitief
Gebruikte programmatuur
Dim s As String
Dim h1 As String
Dim h2 As String
Dim x1 As String
Dim x2 As String
Dim a As Integer
Dim p As Integer
h1 = s1
h2 = s2
x2 = Mid(h1, 1, 4 – a)
x1 = Mid(h2, a, 4 – a)
If x1 = x2 Then
s = s & “1”
Else
s = s & “0”
End If
Next a
For a = 0 To 2
p = p + (Asc(Mid(s, a + 1, 1)) – 48) * 2 ^ (2 – a)
Next a
ConwayS = p
End Function
Dim AA As Integer
Dim AB As Integer
Dim BA As Integer
Dim BB As Integer
Dim o As Integer
AA = ConwayS(s1, s1)
AB = ConwayS(s2, s1)
BA = ConwayS(s1, s2)
BB = ConwayS(s2, s2)
o = (AA – AB) / (BB – BA)
Odds = o
Else
Odds = “”
End If
End Function
Penney Ante
\text{Kans}=\frac{\text{gunstige gevallen}}{\text{totaal aantal gevallen}}
\sum_{n=0}^{\infty}ar^{n}=\frac{a\text{ - }ar^{n}}{1\text{ - }r}
\sum_{n=3}^{\infty}\left (\frac{1}{2} \right )^{n}=\sum_{n=0}^{\infty} \left (\frac{1}{2}\right )^{n}\text{ - }\sum_{n=0}^{2}\left (\frac{1}{2}\right )^{n}
\sum_{n=3}^{\infty}\left (\frac{1}{2} \right )^{n}=\frac{1}{1\text{ - }\frac{1}{2}}\text{ - }1\text{ - }\frac{1}{2}\text{ - }\frac{1}{4}=2\text{ - }1\text{ - }\frac{1}{2}\text{ - }\frac{1}{4}=\frac{1}{4}
p=\frac{1}{2}+\frac{1}{2}\cdot \frac{1}{2}p\Rightarrow p=\frac{1}{2}+\frac{1}{4}p\Rightarrow \frac{3}{4}p=\frac{1}{2}\Rightarrow p=\frac{1}{2}\cdot \frac{4}{3}=\frac{4}{6}=\frac{2}{3}
#Penney-Ante game
import time
import random
def help():
print(‘-‘*105)
print(‘Explanation on the Penney-Ante game’)
print()
print(‘In this game we will throw a non biased coin.’)
print(‘So the coin is falling on heads(H) or tails(T) with a 50-50% chance.’)
print()
print(‘You choose a sequence of length 3 with heads(H) or tails(T), and so do I.’)
print(‘We will throw the coin until one of our sequences is thrown.’)
print(‘If your sequence is thrown you win, if my sequence is thrown I win, otherwise we throw the coin again.’)
print()
print(‘Example:’)
print(‘You coose the sequence THT.’)
print(‘I choose the sequence TTH.’)
print(‘After throwing the coin 5 times the seqence is HHTHT, so you win!’)
print()
print(‘Now the BIG question is: Is this a fair game???’)
print(‘-‘*105)
print()
quit()
def choose_sequence(opponent_sequence):
mys=””
c=opponent_sequence[1]
if c==’T’:
mys = “H”
else:
mys = “T”
mys = mys + opponent_sequence[:2]
return mys
num_of_games = 1
opponent_sequence = ” #’THH’
computer_sequence = ” #choose_sequence(opponent_sequence)
slow = True
opponent_wins = 0
computer_wins = 0
def check_win(s):
global opponent_sequence, computer_sequence
lens = len(s)
if lens < 3:
return False, ”
else:
h = s[lens-3:lens]
if opponent_sequence == h:
#print(‘[‘+h+’]’)
#print(‘<‘+opponent_sequence+’>’)
return True, ‘opponent’
elif computer_sequence == h:
#print(‘[‘+h+’]’)
#print(‘<‘+computer_sequence+’>’)
return True, ‘computer’
else:
return False, ”
def throw_coin():
global computer_wins, opponent_wins
a = 0
s = “”
win = False
while not win:
a += 1
coin = random.randint(0,1)
if coin == 0:
s = s + ‘H’
if num_of_games <= 100:
print(‘H’, end=”, flush=True)
else:
s = s + ‘T’
if num_of_games <= 100:
print(‘T’, end=”, flush=True)
win, winner = check_win(s)
if winner == ‘computer’:
computer_wins += 1
elif winner == ‘opponent’:
opponent_wins += 1
if slow and num_of_games <= 100:
time.sleep(0.25)
if num_of_games <= 100:
print()
if num_of_games <= 100:
if winner == ‘computer’:
w = ‘I am’
else:
w = ‘You are’
print(w + ‘ the winner after ‘ + str(a) + ‘ throws’)
def play():
for i in range(num_of_games):
if num_of_games <= 100:
print(‘Game ‘ + str(i+1) + ‘:’)
throw_coin()
m = ‘\nAfter ‘ + str(num_of_games) + ‘ games you won ‘ + str(opponent_wins)
m = m + (‘ game’ if opponent_wins == 1 else ‘ games’) + ‘ with sequence ‘ + opponent_sequence + ‘ and I won ‘ + str(computer_wins)
m = m + (‘ game’ if computer_wins == 1 else ‘ games’) + ‘ with sequence ‘ + computer_sequence + ‘.’
print(m)
def start():
global num_of_games, slow, opponent_sequence, computer_sequence
print(‘Penney-Ante game’)
print()
p = input(‘Need explanation (Y or N)[N]? ‘)
if len(p) == 0:
#print(‘\bN’)
p=’N’
if p[0].upper() == ‘Y’:
help()
p = input(“Give your 3-length sequence (only T’s or H’s): “)
p = p.upper()
r=(len(p)==3)
if r:
for i in range(2):
if (p[i]!=’T’ and p[i]!=’H’):
r=False
if not r:
print(‘No valid input. You play with TTT.’)
p=’TTT’
opponent_sequence = p
computer_sequence = choose_sequence(opponent_sequence)
p = input(‘How many games (>0)[10]: ‘)
if len(p)==0:
p=’10’
try:
p = int(p)
except:
p = 10
num_of_games = p
p = input(‘Play Slow or Fast (S or F)[F]: ‘)
if len(p) == 0:
p=’F’
p = p[0].upper()
slow = (p == ‘S’)
print(‘Your sequence is: ‘ + opponent_sequence)
print(‘My sequence is: ‘ + computer_sequence)
print(“Let’s play…”)
play()
start()