Hoofdstuk V. Spelen met kansen. Ben van der Genugten

c 2003 Veen Magazines uit: Speeltuin van de wiskunde, Bart de Smit en Jaap Top (red.)

Hoofdstuk V

Spelen met kansen Ben van der Genugten 1. Inleiding Doel van dit hoofdstuk is te laten zien hoe kansrekening gebruikt kan worden bij het oplossen van intrigerende problemen bij enkele (over)bekende spelen. Van sommige problemen kan de oplossing direct uitgedrukt worden in formules. We geven in §2 hiervan enkele illustraties met het casinospel roulette. De meeste problemen staan echter zulke eenvoudige rekenkundige oplossingen niet toe. We zijn dan al blij een methode te kunnen geven waarmee de oplossing bepaald kan worden. Daadwerkelijke berekening gebeurt dan met behulp van de computer. We geven hiervan in §3 een illustratie met het huiskamerspel Mens-erger-je-niet. In het volgende veronderstellen we slechts als voorkennis enige elementaire kansrekening zoals die op het VWO behandeld wordt. De gekozen spelen leiden tot een eerste kennismaking met enkele gebieden uit de wat meer geavanceerde kansrekening. De illustratie in §3 is wel wat moeilijker dan die in §2. 2. Roulette 2.1 Spelbeschrijving. Roulette is wellicht het meest bekende casinospel. De croupier laat een balletje rollen in een roulettecilinder die voorzien is van 37 nummers: de getallen 0 t/m 36. Spelers zetten in op een enkel nummer of op combinaties van k nummers (k = 1, 2, 3, 4, 6, 12 of 18). Zulke combinaties hebben karakteristieke namen b.v. “plein” voor k = 1 en “simple” voor k = 18. Als het balletje op de gekozen combinatie valt, volgt een uitbetaling van 36/k maal de erop geplaatste inzet; anders is de speler gewoon zijn inzet kwijt (zie echter §2.6 voor een uitzondering). In Holland Casino’s kan het hierbij om behoorlijke bedragen gaan. Voor een tafel met de laagste minimum-inzet van f 10 is de bijbehorende maximum-inzet bij plein f 400 en bij simple zelfs f 10000! Door het casino worden kosten noch moeite gespaard om de cilinder zo te construeren en op te stellen dat de 37 mogelijke speluitkomsten gelijkwaardig zijn in die zin dat ze alle dezelfde kans hebben. Met dank aan Peter Borm (KUB, Tilburg) en Frie Govaerts (Bisschop Bekkerscollege, Eindhoven) voor hun commentaar op een eerdere versie.

57

c 2003 Veen Magazines uit: Speeltuin van de wiskunde, Bart de Smit en Jaap Top (red.) 58

BEN VAN DER GENUGTEN

2.2 Voordeel voor casino’s. Casino’s zijn in het voordeel en spelers in het nadeel. We bedoelen hiermee dat voor een speler de gemiddelde winst per ingezette eenheid genomen over een onbeperkt aantal spelronden (“op de lange duur”) negatief is. We gaan dit eerst na voor het eenvoudige geval dat een speler telkens simple speelt met een inzet 1. Voor een enkele spelronde zijn de speluitkomsten W = winst met kans p = 18/37 en V = verlies met kans q = 1 − p = 19/37. Onderstaand schema geeft de bijbehorende consequenties: speluitkomst

kans

inzet

uitbetaling

winst

W

p

1

2

1

V

q

1

0

−1

De verwachte winst G, gedefinieerd als de som van de met de kansen gewogen mogelijke uitkomsten van de winst, wordt dan: G = p(1) + q(−1) = p − q = −1/37 ≈ −0,0270. Dit getal G is dus ook de gemiddelde winst per inzet per spel op de lange duur. Aangezien dit negatief is, is de speler in het nadeel. Als de inzet niet 1 maar, meer algemeen, B is, dan zijn alle uitbetalingen en winsten B maal zo groot. Dit geldt dan ook voor de verwachte winst G, dus deze is G = p(B) + q(−B) = (p − q)B = −B/37. De gemiddelde winst per inzet G/B wordt dan G/B = −1/37. De hoogte van de inzet zelf doet er dus niet toe! We bekijken tenslotte het meer ingewikkelde geval dat een speler telkens op k nummers zet met een inzet B. Dan wint de speler met een kans pk = k/37

c 2003 Veen Magazines uit: Speeltuin van de wiskunde, Bart de Smit en Jaap Top (red.) V. SPELEN EN KANSREKENING

59

het bedrag 36B/k − B en verliest de speler met een kans qk = 1 − pk het bedrag B (zie onderstaand schema): speluitkomst

kans

inzet

uitbetaling

winst

W

pk

B

36B/k

36B/k − B

V

qk

B

0

−B

De verwachte winst G wordt dan: G = pk (36B/k − B) + qk (−B) = −B/37. De gemiddelde winst per inzet op de lange duur G/B is dus gelijk aan −1/37. Dit getal hangt zelf niet van B af en ook niet van k. Er zijn natuurlijk nog vele andere manieren om in te zetten. Het eenvoudigst is in ieder spel een bedrag 1 in te zetten op elk van de 37 nummers. Eén nummer geeft dan een winst van 36 − 1 = 35 en alle andere 36 nummers geven een verlies 1. In dit geval is dus in ieder spel de totale winst G = 35 − 36 = −1 en de totale inzet B = 37. Wederom geeft dit per spel de gemiddelde winst per inzet G/B = −1/37. Het begint erop te lijken dat dit quotient −1/37 steeds dezelfde is, hoe ook ingezet wordt! 2.3 Een winnende strategie(?). Toch lijkt het heel eenvoudig een inzetstrategie aan te geven die op de lange duur tot winst leidt. We denken hierbij de achtereenvolgende spelen opgedeeld in spelcycli, waarbij we binnen een spelcyclus de inzet als volgt variëren: • start met een inzet 1 • zolang Verlies “verdubbel inzet” anders “stop” (uitkomst Winst). Onderstaand schema illustreert dit voor een willekeurige spelcyclus. speluitkomst

kans

inzet

uitbetaling

winst

W

p

1

2

1

VW

qp

1+2

4

1

2

VVW

q p

1+2+4

8

1

···

···

···

···

VV. . . VW

q j−1 p

··· Pj−1

2j

1

···

···

···

···

···

i=0

2i = 2j − 1

De winst voor een spelcyclus-uitkomst is steeds 1. Voorts is de kans dat een spelcyclus-uitkomst tot Winst leidt gelijk aan ∞ X j=0

q j p = 1.



De winst G per spelcyclus is dus met kans 1 gelijk aan 1. De speler wint dus altijd! Deze redenering is volkomen correct. Helaas, er is toch een afdoende tegenwerping te maken: er bestaan geen casino’s waar op deze manier roulette gespeeld kan worden. Ieder casino kent een maximum inzet. Bij Holland Casino’s met de minimum inzet 1 = f 10 correspondeert de maximum inzet 1000 met f 10000 (zie §2.1). De geformuleerde inzetstrategie is dan onjuist geformuleerd omdat we ook nog moeten vastleggen wat we doen als we het maximum dreigen te overschrijden. Voor verdere analyse nemen we aan dat we dan gewoon de spelcyclus stoppen: • start met inzet 1 • zolang (Verlies én verdubbelen mogelijk) “verdubbel inzet” anders “stop”. Voorts gaan we om de berekening eenvoudig te houden uit van een maximum inzet van 1023 = 210 − 1 = 2m − 1 met m = 10. Het spelcyclus-schema wordt dan: speluitkomst

kans

inzet

uitbetaling

winst

W

p

1

2

1

···

···

···

···

···

j

j

2 −1

2

1

···

···

···

···

q m−1 p

2m − 1

2m

1

0

−2m + 1

VV. . . VW

q

··· VV. . . VW VV. . . VV

j−1

q

p

m

m

2 −1

De eerste m cyclusuitkomsten geven winst en de laatste uitkomst geeft verlies: uitkomst

kans

winst

Winst

1 − q m ≈ 0,9987

1

Verlies

q

m

≈ 0,0013

−2m + 1 = −1023

De verwachte winst per spelcyclus is dus G = (1 − q m )(1) + q m (−2m + 1) = 1 − (2q)m = −0,306. Dit is niet gelijk aan 1, maar negatief en zelfs nog meer negatief dan de verwachte winst per spel bij een vast inzetbedrag 1. Spelen volgens deze strategie maakt het spel bijna tot een soort Russisch roulette. Met een grote kans wordt een klein bedrag gewonnen (geen kogel in de loop) en met een kleine kans wordt een groot bedrag zijnde het leven verloren (kogel in de loop)! We berekenen ook in dit geval de gemiddelde winst per inzet op de lange duur. Deze is gelijk aan de verwachte winst G per spelcyclus gedeeld door de


61

verwachte inzet B per spelcyclus. Reeds berekend is G = 1 − (2q)m . Uit het schema van de cyclusuitkomsten volgt: B=

m X

q j−1 p(2j − 1) + q m (2m − 1) =

j=1

1 − (2q)m . 1 − 2q

Blijkbaar geldt ook nu voor de gemiddelde winst per inzet op de lange duur G/B dat G/B = 1 − 2q = −1/37. Voorgaande analyse suggereert dat onder de voorwaarde van een maximuminzet de gemiddelde winst per inzet op de lange duur steeds gelijk is aan −1/37 voor iedere spelstrategie, hoe ook gekozen. Aangetoond kan worden dat dit inderdaad het geval is! Maar het bewijs hiervan is helemaal niet eenvoudig. Er zijn immers oneindig veel mogelijke strategieën en die kunnen niet één voor één gecheckt worden. De theorie van martingalen en stoptijden vormt het deelgebied van de kansrekening waarmee het bewijs geleverd kan worden. 2.4 De bank laten springen. Een speler mag dan in het nadeel zijn, maar toch is het in theorie mogelijk dat hij heel vaak wint en op die manier de bank laat springen. We willen inzicht krijgen in de kans dat dit gebeurt. Hiertoe nemen we aan dat de speler een kapitaal van a inzetten ter beschikking heeft en de bank een kapitaal van b inzetten. De som van de kapitalen is dus gelijk aan a + b. Voorts nemen we het eenvoudige geval dat de speler steeds simple speelt met inzet 1, zodat p = 18/37 zijn winstkans per spel is en q = 1 − p = 19/37 zijn verlieskans. We willen de kans πa,b dat de speler de bank laat springen berekenen (de zogenaamde ru¨ıneringskans van de bank). Dit lukt niet met de eenvoudige combinatoriek uit de elementaire kansrekening. De truc is tegelijk alle mogelijke ru¨ıneringskansen πi (i = 0, . . . , a + b) dat de speler een kapitaal i vergaard heeft in de beschouwing te betrekken! Voorts maken we gebruik van een elementaire rekenregel uit de kansrekening m.b.t. de berekening van een kans uit conditionele kansen: P (A) = P (B) · P (A|B) + P (B c )P (A|B c ) waarin B c het complement van B. Hierbij is P (A|B) de kans op gebeurtenis A gegeven dat gebeurtenis B optreedt. Laat de speler een kapitaal i vergaard hebben (1 ≤ i ≤ a + b − 1). Als A de gebeurtenis is dat de bank geru¨ıneerd wordt en B de gebeurtenis dat de speler de eerste spelronde wint, dan is πi = P (A), p = P (B), q = P (B c ). Onder het gegeven B wint de speler de eerste spelronde en heeft dan kapitaal i + 1. Deze speluitkomst heeft geen invloed op alle volgende speluitkomsten, zodat P (A|B) = πi+1 . Om dezelfde reden is P (A|B c ) = πi−1 . Substitutie geeft de betrekking πi = pπi+1 + qπi−1 , 1 ≤ i ≤ a + b − 1. Vanzelfsprekend gelden de randcondities π0 = 0, πa+b = 1.



Na te gaan is dat er precies één oplossing is: (p/q)a+b−i − (p/q)a+b , 0 ≤ i ≤ a + b. 1 − (p/q)a+b Substitutie van i = a en c = p/q(= 18/19) geeft de ru¨ıneringskans van de bank: πi =

πa,b =

cb − ca+b . 1 − ca+b

Op dezelfde manier valt de verwachte duur da,b (uitgedrukt in aantal spelronden) te berekenen. Beschouw weer meer algemeen de verwachte duur di bij een spelerskapitaal i (1 ≤ i ≤ a + b − 1). We maken nu gebruik van een elementaire rekenregel m.b.t. de berekening van een verwachting uit conditionele verwachtingen: E(X) = P (B)E(X|B) + P (B c )E(X|B c ). Laat X het aantal spelronden aangeven en definieer B als voorheen. Bij spelerskapitaal i is dan di = E(X), p = P (B), q = P (B c ). Onder het gegeven B wordt het kapitaal i + 1 en is er een spelronde bijgekomen zodat E(X|B) = 1 + di+1 . Om dezelfde reden is E(X|B c ) = 1 + di−1 . Substitutie geeft de betrekking di = pdi+1 + qdi−1 + 1, 1 ≤ i ≤ a + b − 1. Vanzelfsprekend gelden de randcondities d0 = 0, da+b = 0. Er is weer precies één oplossing die wordt gegeven door di =

i − (a + b)πi , 0 ≤ i ≤ a + b. q−p

Substitutie van i = a geeft da,b =

(1 − πa,b )a − πa,b b . q−p

We geven enkele numerieke invullingen voor Holland Casino’s, waarbij we het ter beschikking staande kapitaal op 10% van de jaarwinst stellen: f 50.000.000. Voorts nemen we aan dat een speler bereid is f 100.000 te riskeren. Als gespeeld wordt met de maximuminzet f 10000 dan is a = 10, b = 500 en dit geeft de ru¨ıneringskans πa,b = 7,6 × 10−13 . Dit risico kan het casino best lopen. De speler raakt dus vrijwel zeker zijn kapitaal kwijt. Zijn verwachte spelduur is da,b = 300, zodat hij wel een behoorlijke tijd aan de speeltafel zal doorbrengen. Als gespeeld wordt met de minimuminzet f 10, dan is de ru¨ıneringskans nog vele machten van 10 kleiner! Zelfs loopt Holland Casino’s nog nauwelijks risico als alle spelers tegelijk spelen. Gezamenlijk vertegenwoordigen zij een nagenoeg oneindig kapitaal van a = ∞ inzetten. Dit geeft wegens c < 1 dat π∞,b = cb . Substitutie van b = 500 geeft π∞,b = 1,8 × 10−12 . De ru¨ıneringskans wordt nauwelijks groter. Allesbepalend is het feit dat c < 1.


63

Voorgaand ru¨ıneringsprobleem wordt in de kansrekening vaak vertaald in termen van een stochastische wandeling: een wandelaar start op de reële rechte in een punt i en doet telkens een stapje met kans p naar rechts en met kans q naar links. Het idee laat laat zich op velerlei wijzen gegeneraliseren met allerlei toepassingsmogelijkheden. De theorie van stochastische wandelingen is daarmee een belangrijk deelgebied van de kansrekening. 2.5 Oneerlijk spel. De ru¨ıneringskansen in §2.4 zijn extreem gevoelig voor de verhouding c = p/q van de kansen p op winst en q op verlies. In het ideale geval dat alle 37 nummers dezelfde kans hebben, is c = 18/19. Maar wat gebeurt er als dit niet langer het geval is b.v. tengevolge van slijtage of fraude? Aan het eind van de vorige eeuw ontdekte William Jaggers, een Britse ingenieur, dat de roulettecilinders van het Grand Casino in Monte Carlo afwijkingen vertoonden die zo groot waren dat hij door in te zetten op de meest gunstige nummers de kansen in zijn voordeel kon be¨ınvloeden. Zo slaagde hij erin in korte tijd 1 12 miljoen francs te winnen voordat het casino-management de oorzaak kon opsporen en de cilinders liet vervangen. Laten we eens aannemen dat de afwijking zodanig is dat een geschikte set van 18 nummers leidt tot een c = p/q = 1,001. Wat worden dan de ru¨ıneringskansen in §2.4? Voor a = 10, b = 500 is nu πa,b = 0,0249 ofwel 2,49% en dit is zeker niet meer verwaarloosbaar. Voor a = ∞ vinden we wegens c > 1 zelfs dat π∞,b = 1, ofwel de bank gaat wis en zeker failliet hoe groot zijn kapitaal b ook is! 2.6 Holland Casino’s. In Holland Casino’s worden twee vormen van roulette gespeeld die bij simple voor spelers nog iets gunstiger zijn dan die genoemd in §2.2. De groep van 18 nummers bevat dan niet de nul. Als nul uitgeloot wordt, heeft de speler niet meteen zijn gehele inzet verloren. Bij Amerikaans roulette krijgt de speler bij nul de helft van zijn inzet terug. Bij een inzet 1 is dan zijn verwachte winst 18 1 1 1 18 ×1+ × (−1) + × (− ) = − ≈ −0,0135. 37 37 37 2 74 Dit is nog steeds negatief maar minder dan de waarde −1/37 ≈ −0,0270 van §2.2. Bij Frans roulette zijn de regels ingewikkelder. Bij nul gaat de inzet van de speler in de gevangenis (“en prison”). Als de volgende spelronde tot winst leidt, krijgt de speler ook zijn oorspronkelijke inzet weer terug. Echter, als de volgende spelronde tot verlies leidt, dan is hij ook zijn inzet in de gevangenis kwijt. Wat gebeurt er bij nul met een inzet in de gevangenis? Deze gaat dan “dubbel in de gevangenis”! Bij winst op de volgende spelronde, wordt de positie “dubbel in de gevangenis” teruggebracht tot gewoon “in de gevangenis”. Bij verlies of nul bij de volgende spelronde, gaat ook de inzet “dubbel in de gevangenis” verloren. Een hoger gevangenisniveau dan dubbel bestaat er in Holland Casino’s niet.



De vraag is nu wat bij Frans roulette de gemiddelde winst G per inzet op de lange duur is. Het antwoord is G = −0,0137. Daarom is voor spelers Frans roulette iets ongunstiger dan Amerikaans roulette, alhoewel het verschil minimaal is. Het is helemaal niet zo eenvoudig dit antwoord te verkrijgen. We geven de afleiding. We gebruiken dezelfde techniek als in §2.4 voor de berekening van de verwachte duur. Laat Gi de verwachte winst zijn die een bepaalde inzet oplevert als gestart wordt in de toestand i met interpretatie i = 0 “niet in de gevangenis”, i = 1 “in de gevangenis” en i = 2 “dubbel in de gevangenis”. Het gaat ons dan om G = G0 . Iedere spelronde heeft kans p = 18/37 op winst, q = 18/37 op verlies en r = 1/37 op de nul, zodat (vgl. §2.4)

G0 = p(1) + q(−1) + rG1

= p − q + rG1

G1 = p(0) + q(−1) + rG2

= −q + rG2

G2 = pG1 + q(−1) + r(−1) = pG1 − q − r.

Oplossen van dit stelsel van 3 vergelijkingen met de 3 onbekenden G1 , G2 , G3 geeft

G = G0 = −1 + 2p +

685 pr =− = −0,013704, 1 − pr 49987

en dit stemt overeen met het reeds gegeven antwoord. Het lukt niet Frans roulette gunstiger te maken dan Amerikaans roulette door hogere “in de gevangenis”-niveaus toe te staan. Zo leidt een maximum van “driedubbel in de gevangenis” tot G = −0,013701. Met hetzelfde aantal decimalen is dit ook al de waarde als geen enkele beperking wordt opgelegd (“oneindig vaak in de gevangenis”). Bovenstaande oplossingsmethode is mogelijk door gebruik te maken van het feit dat kansen op mogelijke uitkomsten van toestanden in volgende spelronden slechts afhangen van de huidige toestand en niet van de uitkomsten van toestanden daaraan voorafgaand. Het aantal toepassingen waarbij problemen deze structuur hebben is zeer groot. In de kansrekening staat dit deelgebied bekend als de theorie van Markov-ketens. Zonder overdrijving mag gesteld worden dat iedere voortgezette cursus kansrekening hierover iets zou moeten bevatten!


65

3. Mens-erger-je-niet 3.1 Spelbeschrijving. Mens-erger-je-niet is een over de gehele wereld bekend huiskamerspel. We geven kort de spelregels met 2 spelers I en II. Zij spelen met elk 2 pionnen (gebruikelijker is 4); laten we zeggen witte pionnen ( ) voor speler I en zwarte pionnen ( ) voor speler II. Figuur 1 geeft een schets van een verkleind bord met veldnummering en figuur 2 geeft een bepaalde spelsituatie op z’n bord. Het aantal bordvakjes is hier b = 12; op een normaal bord is dit b = 40). 12 11

1 13

10

2

14 9

3 14 8

4

13 7

5 6

Figuur 1 Doel van het spel is dat een speler zijn twee pionnen vanuit zijn eigen opzetvak over de bordvakjes als eerste in zijn eigen twee thuisvakjes krijgt. De verplaatsingen (in klokrichting) worden bepaald door het aantal ogen van een worp met een dobbelsteen. Als een speler 6 gooit behoudt hij zijn beurt, anders gaat de beurt naar de tegenstander. Indien het opzetvak niet leeg is moet bij het gooien van 6 opgezet worden. Opzetten betekent een pion vanuit het eigen opzetvak plaatsen op het eerste eigen bordvak (1 bij wit en 7 bij zwart). Als bij zetten een pion van een speler uitkomt op een bordvak waarop een pion van de tegenstander staat, dan wordt de laatste geslagen en in diens eigen opzetvak teruggeplaatst. Pionnen moeten steeds vooruit; alleen in de thuisvakjes mag teruggeteld worden. Het kan daarom voorkomen dat een speler niet aan zijn verplichting tot zetten kan voldoen. Dit kan ook gebeuren als een speler zijn eigen pion zou moeten slaan, hetgeen verboden is. We geven enkele voorbeelden aan de hand van de spelsituatie in figuur 2. Neem eerst aan dat de speler met wit ( ) de beurt heeft. Als hij 2 of 4 gooit bezet hij het laatste thuisvakje en heeft hij daarmee het spel gewonnen. Als hij 3, 5 of 6 gooit, kan hij niet zetten (bij 6 behoudt hij zijn beurt). Neem vervolgens aan dat de speler met zwart ( ) de beurt heeft. Als hij 3 gooit, slaat hij een witte pion. Als hij 6 gooit, moet hij zijn andere pion



12 11

1 13

10

2 14

9

3 14 8

4 13 7

5 6

Figuur 2 opzetten op zijn eerste bordvak; hij behoudt de beurt (als daarop al zijn andere pion zou staan, mag hij deze niet slaan en kan hij dus niet zetten). 3.2 Spelanalyse. De hamvraag bij dit spel is hoe de spelers hun winstkansen kunnen maximaliseren door de juiste pion te verzetten als hij een keuze heeft en wat deze kansen zijn. Beschouw eerst de situatie dat beide spelers al één pion op het hoogste thuisvakje hebben staan (in figuur 1 positie 14). Dan hebben beide spelers geen pionkeuze. De winstkans van wit (= verlieskans van zwart) ligt dan voor iedere bordsituatie vast. Het is echter een illusie te denken dat deze kansen door een simpele analytische uitdrukking zijn te geven. Dit is al niet mogelijk voor het verkleinde bord van figuur 1 met b = 12 bordvakjes, laat staan voor een normaal bord met b = 40 bordvakjes! Beschouw vervolgens de situatie dat speler II één pion op het hoogste thuisvakje heeft. Dan heeft speler II geen pionkeuze, maar speler I meestal wel. Zijn winstkans hangt dus af van zijn spelstrategie: welke pion kiest hij gegeven de bordsituatie en het aantal gegooide ogen? De beste keuze voor hem is uiteraard de strategie die in iedere spelsituatie waarin hij aan zet is zijn winstkans maximaliseert. Maar als het al zo moeilijk is winstkansen te berekenen, hoe moet dan ooit deze optimale strategie en de bijbehorende winstkansen gevonden worden? Beschouw tenslotte de algemene situatie dat beide spelers nog geen enkele pion in het hoogste thuisvakje hebben. De winstkans van I (verlieskans van speler II) hangt dan niet alleen af van de spelstrategie van I, maar ook nog van die van II. Het ergste dat I kan overkomen bij een bepaalde strategiekeuze is dat II deze keuze kent en de strategie kiest die de winstkans van I (de verlieskans van II) minimaliseert. Vanuit die overweging zal I er verstandig aan doen die strategie te kiezen welke deze (door II teweeggebrachte) minimale winstkans maximaliseert. We noemen de in deze zin optimale strategie van I


67

de maxmin-strategie. Met dezelfde argumentatie doet speler II er verstandig aan de minmax-strategie te kiezen: de strategie die zijn maximale verlieskans minimaliseert. Voor spelen zoals Mens-erger-je-niet is de winstkans van I altijd gelijk is aan de verlieskans van II als I zijn maxmin-strategie speelt en II zijn minmaxstrategie. Deze gemeenschappelijke kans heet de waarde van het spel. Er is evenwicht in de volgende zin. Speler II kan door het spelen van zijn minmaxstrategie verhinderen dat I een grotere winstkans heeft dan de spelwaarde, en speler I kan door het spelen van zijn maxmin-strategie verhinderen dat speler II een kleinere verlieskans heeft dan deze spelwaarde. De spelers behoeven daarvoor elkanders strategie ook helemaal niet meer te kennen! Dit is mooie theorie, maar hoe kan deze waarde en de bijbehorende optimale strategieën ooit bepaald worden? Bij de meeste bordspelen is dit gewoon niet mogelijk omdat het aantal in aanmerking komende strategieën veel te groot is. Met Mens-erger-je-niet op een echt bord met b = 40 bordvakjes lukt het nog juist met een goede PC. We laten dit in de volgende paragraaf zien. 3.3 Optimaal spel. Om het algoritme voor de berekening van winstkansen en bijbehorende optimale strategieën te kunnen beschrijven voeren we enkele notaties in. Beschouw de spelsituatie steeds op het moment dat juist met de dobbelsteen gegooid is. Op dat moment moet de aan de beurt zijnde speler zijn beslissing nemen. Deze spelsituatie valt dan te karakteriseren met s = (m, p11 , p12 , p21 , p22 , d). Hierin is m het nummer van de aan de beurt zijnde speler: m = 1 voor wit en m = 2 voor zwart. Voorts zijn p11 en p12 de bordposities van respectievelijk de voorste en achterste witte pion van speler I, dus er geldt 0 ≤ p12 ≤ p11 ≤ b + 2 en p12 < p11 als p11 > 0. De relatieve bordposities van speler II ten opzichte van het eigen opzetvak geven we op dezelfde manier aan met p21 en p22 en d is het gegooide aantal ogen. Als in figuur 2 speler I aan zet is en zojuist d ogen gegooid heeft, dan is de spelsituatie s0 = (1, 14, 11, 2, 0, d). De mogelijke beslissingen coderen we als 0 = geen zet mogelijk, 1 = zet de voorste pion en 2 = zet de achterste pion. De verzameling A(s) van mogelijke beslissingen hangt van s af. Voor voorgaande s0 van figuur 2 is A(s0 ) = {2} voor d = 1, 2, 4 en A(s0 ) = {0} voor d = 3, 5, 6. Pas als A(s) meer dan één element bevat is er een echt keuzeprobleem. Laat a ∈ A(s0 ) een mogelijke beslissing zijn in de spelsituatie s0 en j het aantal gegooide ogen na zetten (j = 1, . . . , 6). De nieuwe spelsituatie s1 wordt dan bepaald door s0 , a en j. We schrijven daarom s1 = s1 (s0 , a, j). Voor alle j hebben deze dezelfde kans. Bij s0 als voorheen geldt s1 = (2, 14, 12, 2, 0, j) als d = 1, s1 = (2, 14, 13, 2, 0, j) als d = 2 of 4 (het spel is beëindigd en I heeft gewonnen), s1 = (2, 14, 11, 2, 0, j) als d = 3 of 5 en s1 = (1, 14, 11, 2, 0, j) als d = 6.



Laat G(s) de winstkans van I (= verlieskans van II) aangeven. Bij optimaal spel van beide spelers zoals beschreven in §3.2 moet dan de volgende evenwichtsvergelijking gelden (voor alle mogelijke s0 ):

G(s0 ) =

 6 X    max G(s1 (s0 , a, j))/6 als m = 1,    a∈A(s0 ) j=1 6  X    min   a∈A(s0 ) G(s1 (s0 , a, j))/6 als m = 2. j=1

In principe volgen door oplossing van dit vergelijkingenstelsel de winstkansen G(s0 ) en de bijbehorende optimale beslissingen aopt = aopt (s0 ). Dit vergelijkingenstelsel valt numeriek op te lossen met een algoritme, dat nog een eenvoudige interpretatie heeft ook. Het aantal spelbeurten is eindig met kans 1 voor welke spelstrategieën dan ook. Definieer Gn (s0 ) als de winstkans van I bij optimaal spel als nog n beurten te gaan zijn en het spel daarna afgebroken wordt. Dan geldt:

Gn+1 (s0 ) =

 6 X    max Gn (s1 (s0 , a, j))/6 als m = 1,    a∈A(s0 ) j=1 6  X    min   a∈A(s0 ) Gn (s1 (s0 , a, j))/6 als m = 2. j=1

opt Er geldt dat Gn (s0 ) → G(s0 ) en bijbehorend aopt (s0 ) als n → ∞. n (s0 ) → a Uit G0 kunnen achtereenvolgens G1 , G2 , . . . berekend worden. Gestopt kan worden als |Gn+1 (s0 ) − Gn (s0 )| < ε voor alle s0 , waarin ε een van te voren opgegeven constante die de nauwkeurigheid bepaalt. De waarden G0 (s0 ) zijn eenvoudig te bepalen gegeven het aantal bordvakjes b. Voor een winstsituatie s0 = (∗, b + 2, b + 1, ∗, ∗, ∗) van speler I is G0 (s0 ) = 1 en voor een verliessituatie s0 = (∗, ∗, ∗, b + 2, b + 1, ∗, ∗, ∗) van I is G0 (s0 ) = 0. Voor alle andere situaties s0 kan G0 (s0 ) = 1/2 genomen worden (met als interpretatie dat met een worp met een geldstuk om de winst geloot wordt). Het idee van de iteratieve methode om de analyse te beginnen in de eindsituatie van het spel en dan achterwaarts terug te rekenen tot het begin van het spel is de basisgedachte van dynamische programmering. Dit is één van de meest toepassingsrijke deelgebieden van de besliskunde.

3.4 Numerieke uitkomsten. De in §3.3 beschreven methode is in een computer (PC) ingevoerd voor een normaal bord ter grootte b = 40. Het nummer van het eerste bordvak van speler II is dan 21. Het aantal mogelijke spelsituaties is gelijk aan 2×{1+ 21 (b+3)(b+2)}2 ×6 = 9806592. Voor een PC met een intern geheugen van 128 Mb en een vrije harde schijfruimte van 200Mb was dit nog juist haalbaar. Voor een nauwkeurigheid van ε = 10−10 zijn n = 192 iteratiestappen nodig.


69

Onderstaande tabel toont een numerieke uitkomst voor een bepaalde spelsituatie waarbij alle pionnen vrij kunnen bewegen en speler I aan zet is: m

p11

p12

p21

p22

d

aopt

G

1

8

1

31

26

1

1

0,3717

1

8

1

31

26

2

2

0,3861

1

8

1

31

26

3

1

0,5260

1

8

1

31

26

4

2

0,3918

1

8

1

31

26

5

2

0,5687

1

8

1

31

26

6

1

0,4197

Als speler I d = 3 gegooid heeft, is het optimaal zijn voorste pion te verzetten (aopt = 1) waardoor de voorste pion van speler II eraf gegooid wordt (p21 = 31 is bordpositie 11 en p11 = 8 is bordpositie 8) en als hij d = 5 gegooid heeft, zal hij door zijn achterste pion te verzetten de achterste pion van speler II eraf gooien. Dit verklaart de relatief hoge winstkansen van I voor deze d-waarde. De numerieke uitkomst voor de beginsituatie dat speler I het eerst gooit is m

p11

p12

p21

p22

d

aopt

G

1

0

0

0

0

<6

0

0,4889

1

0

0

0

0

=6

1

0,6225

We zien dat I iets in het nadeel is als hij de eerste maal geen 6 gooit (kans kleiner dan 0,5), maar hij is behoorlijk in het voordeel als hij dat wel doet. Door de kansen te middelen over de 6 mogelijke worpen vinden we de kans dat I wint voordat hij voor de eerste maal gegooid heeft: 0,5111. Speler I die begint heeft (bij optimaal spel van beide spelers) dus een gering voordeel. De numerieke uitkomst voor de situatie dat beide spelers één pion in het eindvakje hebben en de andere pion in het opzetvak, geeft grotere uerschillen: m

p11

p12

p21

p22

d

aopt

G

1

42

0

42

0

<6

0

0,4784

1

42

0

42

0

=6

2

0,7379

De optimale beslissingen aopt (s0 ) zijn weer te geven als een tabel met 9806592 ingangen (die voor II volgen ook uit die van I op grond van symmetrie). Voor praktisch spel is zo’n tabel niet bruikbaar. Eigenlijk zijn we dan al tevreden met een strategie die nagenoeg optimale beslissingen geeft en die te onthouden is door eenvoudige richtlijnen zoals



• • • •

sla altijd de tegenstander, verzet altijd de verste pion, passeer nooit een vijandelijke pion, bereik de thuisvakjes indien mogelijk.

Helaas, voorzover deze richtlijnen elkaar al niet tegenspreken, geven ze dikwijls ook nog de niet-optimale beslissing. Het vinden van een nagenoeg optimale strategie is helemaal niet eenvoudig en vereist een nadere uitgebreide analyse. En dan hebben we het hier nog maar over Mens-erger-je-niet met 2 pionnen en niet met 4 zoals gebruikelijker is. In dat geval is het aantal mogelijkheden zo groot dat de optimale oplossing niet meer met een PC te berekenen is. Het is dan nog veel lastiger een verstandige strategie te vinden. De meeste in de praktijk voorkomende spelen hebben de eigenschap dat het aantal mogelijke strategieën zeer groot is en dat er geen simpele manier is om een (nagenoeg) optimale oplossing te bepalen. Dit geldt niet alleen voor Menserger-je-niet met 4 pionnen, maar ook voor tweepersoonsspelen als schaken, dammen en go. In theorie is er een optimale oplossing voor beide spelers (de maxmin-oplossing voor speler I en de minmax-oplossing voor speler II), maar in de praktijk kunnen we deze niet bepalen. Voorgaande spelen worden wel aangeduid als spelen met volledige informatie, omdat in iedere fase van het spel beide spelers over alle informatie beschikken. Vrijwel alle kaartspelen zijn spelen met onvolledige informatie, omdat in de verschillende fasen van het spel de ene speler niet alle kaarten van de andere speler kent. Ook voor zulke tweepersoonsspelen met onvolledige informatie bestaan er optimale oplossingen in bovenbedoelde zin. Helaas gaat deze eigenschap verloren voor drie- en meer-persoonsspelen. De tak van wetenschap die zich met de analyse van spelen bezighoudt heet de speltheorie. Deze heeft zich langzamerhand zo ontwikkeld dat van een zelfstandig gebied gesproken mag worden, alhoewel er een zeer grote overlap met de kansrekening is. Literatuur 1. Ben van der Genugten, Marcel Das, Peter Borm, Behendig gokken in en rond het casino, Schoonhoven: Academic Service, 2001. 2. H.G. Dehling, J.N. Kalma, Kansrekening, het zekere van het onzekere, Utrecht: Epsilon Uitgaven, deel 36, 1995. 3. Christiaan Huygens, Van rekeningh in spelen van geluck, hertaald en toegelicht door Wim Kleijne, Utrecht: Epsilon Uitgaven, deel 40, 1998. 4. Henk Tijms, Spelen met kansen, Utrecht: Epsilon Uitgaven, deel 43, 1999.

Hoofdstuk V. Spelen met kansen. Ben van der Genugten

Recommend Documents