Het spel Six-Seven! begint met twee stapels waarin 6 en 7 munten liggen — een getallenpaar dat de jongerencultuur lijkt te zijn binnengedrongen met de elegantie van een baksteen die door een raam gegooid wordt. Onze welgemeende excuses als het feit dat ze hier verschijnen enige vorm van irritatie opwekt.

Het spel wordt gespeeld door twee spelers die afwisselend aan de beurt komen. De speler die aan de beurt is, gooit met een dobbelsteen. Als hij $$r$$ ($$1 \leq r \leq 6$$) werpt, dan moet hij tussen 1 en $$r$$ munten wegnemen uit één stapel die niet leeg is (of alle resterende munten als die stapel minder dan $$r$$ munten bevat). Bij een worp van 4 mag de speler bijvoorbeeld 1, 2, 3 of 4 munten wegnemen. De speler die de laatste munt wegneemt, is de verliezer.

Wat is de kans dat de speler die als eerste aan de beurt komt het spel wint, als we ervan uitgaan dat beide spelers een optimale strategie volgen?

Opgave

Breuk

Een breuk is een rationaal getal $$\frac{t}{n}$$ met teller $$t \in \mathbb{Z}$$ en noemer $$n \in \mathbb{Z}_0$$.

De normaalvorm van een breuk $$\frac{t}{n}$$ is de volledige vereenvoudigde versie van de breuk die een positieve noemer heeft. Om een breuk volledig te vereenvoudigen, moet je de teller $$t$$ en de noemer $$n$$ delen door hun grootste gemene deler. Als een breuk een negatieve noemer heeft, kan je zowel de teller als de noemer vermenigvuldigen met -1 (met andere woorden: als de breuk negatief is, dan staat het minteken bij de teller).

function ggd(a, b)
    while b ≠ 0
        t := b
        b := a mod b
        a := t
    return a

Definieer een klasse Breuk waarmee breuken $$\frac{t}{n}$$ kunnen voorgesteld worden. Een nieuwe breuk (Breuk) kan aangemaakt worden met de volgende alternatieven voor de argumenten:

• twee gehele getallen $$t \in \mathbb{Z}$$ (Number) en $$n \in \mathbb{Z}_0$$ (Number); dit stelt de breuk $$\frac{t}{n}$$ voor

• een geheel getal $$t \in \mathbb{Z}$$ (Number); dit stelt de breuk $$\frac{t}{1}$$ voor

• een string (String) van de vorm t/n met $$t \in \mathbb{N}$$ en $$n \in \mathbb{N}_0$$; dit stelt de breuk $$\frac{t}{n}$$ voor

• een string (String) van de vorm -t/n met $$t \in \mathbb{N}$$ en $$n \in \mathbb{N}_0$$; dit stelt de breuk $$\frac{-t}{n}$$ voor

• een breuk $$b$$ (Breuk) met teller $$t$$ en noemer $$n$$; dit stelt de breuk $$\frac{t}{n}$$ voor

Als er bij het aanmaken van een nieuwe breuk andere argumenten worden doorgegeven dan de hierboven opgelijste mogelijkheden, dan moet een Error opgeworpen worden met de boodschap ongeldige breuk.

Op een breuk $$b$$ (Breuk) met teller $$t$$ en noemer $$n$$ moet je minstens de volgende methoden kunnen aanroepen:

• Een getter (of objecteigenschap) teller die de teller (Number) teruggeeft van de normaalvorm van breuk $$b$$.

• Een getter (of objecteigenschap) noemer die de noemer (Number) teruggeeft van de normaalvorm van breuk $$b$$.

• Een methode toString waaraan geen argumenten moeten doorgegeven worden. De methode moet een string T/N (String) teruggeven, waarbij T en N resp. de teller en de noemer zijn van de normaalvorm van breuk $$b$$.

• Een getter (of objecteigenschap) abs die de absolute waarde van breuk $$b$$ teruggeeft: een nieuwe breuk $$\frac{|t|}{|n|}$$ (Breuk), waarbij $$|x|$$ de absolute waarde van geheel getal $$x$$ voorstelt.

• Een getter (of objecteigenschap) neg die de negatie van breuk $$b$$ teruggeeft: een nieuwe breuk $$\frac{-t}{n}$$ (Breuk).

• Een getter (of objecteigenschap) inv die de inverse van breuk $$b$$ teruggeeft: een nieuwe breuk $$\frac{n}{t}$$ (Breuk). Als de inverse breuk van $$b$$ niet bestaat, dan moet een Error opgeworpen worden met de boodschap ongeldige breuk.

• Een methode plus waaraan een argument moet doorgegeven worden waarmee een nieuwe breuk $$b'$$ (Breuk) kan aangemaakt worden. De methode moet het resultaat van de optelling $$b + b'$$ (Breuk) teruggeven.

• Een methode min waaraan een argument moet doorgegeven worden waarmee een nieuwe breuk $$b'$$ (Breuk) kan aangemaakt worden. De methode moet het resultaat van de aftrekking $$b - b'$$ (Breuk) teruggeven.

• Een methode maal waaraan een argument moet doorgegeven worden waarmee een nieuwe breuk $$b'$$ (Breuk) kan aangemaakt worden. De methode moet het resultaat van de vermenigvuldiging $$b \times b'$$ (Breuk) teruggeven.

• Een methode gedeeld waaraan een argument moet doorgegeven worden waarmee een nieuwe breuk $$b'$$ (Breuk) kan aangemaakt worden. De methode moet het resultaat van de deling $$\frac{b}{b'}$$ (Breuk) teruggeven. Als deze deling niet opgaat, dan moet een Error opgeworpen worden met de boodschap ongeldige breuk.

• Een methode max waaraan een argument moet doorgegeven worden waarmee een nieuwe breuk $$b'$$ (Breuk) kan aangemaakt worden. De methode moet een nieuwe breuk (Breuk) teruggeven die correspondeert met de grootste van de twee breuken $$b$$ en $$b'$$.

Als geen nieuwe breuk kan aangemaakt worden met het argument dat wordt doorgegeven aan de methoden plus, min, maal, gedeeld of max, dan moet een Error opgeworpen worden met de boodschap ongeldige breuk.

Winstkans

Schrijf een functie winstkans waaraan twee argumenten $$a, b \in \mathbb{N}$$ (Number) moeten doorgegeven worden. De functie moet de kans $$P(a, b)$$ (Breuk) teruggeven dat de speler die aan de beurt is in het spel Six-Seven! wint, als er aan het begin van de beurt $$a$$ munten in de linker stapel liggen, $$b$$ in de rechter stapel, en beide spelers een optimale strategie volgen.

Deze kans kan berekend worden met de recurrrente betrekking \[ P(a, b) = \frac{1}{6}\sum_{r=1}^{6}\max\!\left(\max_{1 \le k \le \min(r,a)}\bigl(1 - P(a-k,b)\bigr),\;\max_{1 \le k \le \min(r,b)}\bigl(1 - P(a,b-k)\bigr)\right) \] De stopvoorwaarde \[ P(0, 0) = 1 \] volgt uit de misère-regel ("wie de laatste munt wegneemt verliest"), want als er aan het begin van een beurt geen munten meer over zijn, heeft de tegenstander de laatste munt weggenomen en is hij dus verloren. Meer algemeen, als enkel de rechter stapel leeg is dan geldt voor $$a > 0$$ dat \[ P(a, 0) = \frac{1}{6}\sum_{r=1}^{6}\max_{1 \le k \le \min(r,a)}\bigl(1 - P(a-k,0)\bigr) \] en als enkel de linker stapel leeg is dan geldt voor $$b > 0$$ dat \[ P(0, b) = \frac{1}{6}\sum_{r=1}^{6}\max_{1 \le k \le \min(r,b)}\bigl(1 - P(0,b-k)\bigr) \]

Bij een recursieve implementatie van $$P(a, b)$$ moet dezelfde kans $$P(a', b')$$ meerdere keren berekenen voor $$0 \leq a' \leq a$$ en $$0 \leq b' \leq b$$. Om dat te vermijden, berekenen we achtereenvolgens alle $$P(a', b')$$ voor $$0 \leq a' \leq a$$ en $$0 \leq b' \leq b$$ in de volgende van de groene pijl in onderstaand schema: $$P(0, 0)$$ is gegeven, daarna bereken we achtereenvolgens $$P(0, 1), P(0, 2), \ldots, P(0, b)$$, daarna achtereenvolgens $$P(1, 1), P(1, 2), \ldots, P(1, b)$$, enzoverder tot we finaal $$P(a, b)$$ berekenen.

Verberg pijl

Als we alle tussenresultaten opslaan, dan kan elke kans $$P(a', b')$$ volgens de recurrente betrekkingen berekend worden op basis van kansen $$P(a'', b'')$$ die reeds berekend werden: er geldt altijd dat $$0 \leq a'' \leq a'$$, $$0 \leq b'' \leq b'$$ en $$(a'',b'') \neq (a', b')$$. Omdat geldt dat $$P(a', b') \equiv P(b', a')$$, moeten we ook enkel de kansen $$P(a', b')$$ berekenen waarvoor $$a' \leq b'$$.

Voorbeeld

> const breuk1 = new Breuk(2, 6)
> breuk1.teller
1
> breuk1.noemer
3
> breuk1.toString()
"1/3"
> breuk1.abs.toString()
"1/3"
> breuk1.neg.toString()
"-1/3"
> breuk1.inv.toString()
"3/1"

> const breuk2 = new Breuk(1, 2)
> breuk1.plus(breuk2).toString()
"5/6"
> breuk1.min(breuk2).toString()
"-1/6"
> breuk1.maal(breuk2).toString()
"1/6"
> breuk1.gedeeld(breuk2).toString()
"2/3"
> breuk1.max(breuk2).toString()
"1/2"

> const breuk3 = winstkans(6, 7)
> breuk3 instanceof Breuk
true
> breuk3.toString()
"5147/8748"
> winstkans(5, 8).toString()
"39281/69984"
> winstkans(9, 9).toString()
"20526139/45349632"