DP-recursie winst-maximalisatie dobbelstenen

[Iwiskunde]

Ik stootte onlangs op volgend vraagstuk:

"Er is een spelletje waarbij je 6 keer met een dobbelsteen mag gooien. Indien je stopt met het spelletje, win je (bv. een geldsom ) gelijk aan het aantal ogen van je laatste worp. Indien je tot de 6e worp gaat, win je dit aantal ogen. Indien je je winst wilt maximaliseren, wat is dan de optimale strategie? Gebruik DP-recursie"

Ik kon niet meteen een oplossing bedenken. Ik dacht dat de verwachte waarde bij elke worp gewoon 21/6 = 3.5 was en je dus zou moeten stoppen indien je hoger dan 3.5 hebt gegooid. Maar ik denk niet dat ik er zo ben.

Iemand die me verder kan helpen?

[CoenCo]

Volgens jouw theorie stop je dus ook als je met je eerste worp 4 gooit?
De kans dat ik in de overige 5 worpen minimaal een 5 of hoger gooi is 1-(4/6)^5= 87 procent.

De verwachtingswaarde van 1 worp is inderdaad 3,5.
Maar wat is de verwachtingswaarde van ‘het beste van 2 worpen’? Als je dat weet voor 2,3,4,5 of 6 worpen. Dan kan je die verwachtingswaarde steeds vergelijken met je huidige worp, en besluiten of je verder gaat met gooien.

[Iwiskunde]

Bedankt voor je reactie. Ik vrees echter dat ik nog niet helemaal volg in uw redenering. Hoe bereken je de verwachtingswaarde voor het beste van 2 worpen?

Ik dacht voor het recursievoorschrift aan het volgende:
de fase is aan welke ronde je gaat beginnen ( bv. de 5e worp )
en de toestand geeft het aantal ogen dat je in de vorige ronde hebt geworpen
Ik zou dan zo een achterwaartse recursie willen opstellen. Maar hiervoor heb ik dan nodig wat u de 'verwachtingswaarde van het beste van 2 worpen noemt' denk ik.
Een willekeurig voorbeeld; indien je aan de 3e worp gaat beginnen en net een 2 hebt gegooid zou ik het als volgt berekenen:
f₃(2)=max{winst indien stoppen, verwachte winst indien verder doen}
=max{2;......}
De '....' weet ik niet zo goed hoe te formuleren. Zou dit er bij een achterwaartse recursie als volgt uit kunnen zien:
1/6*f₄(1)+1/6*f₄(2)+....+1/6*f₄(6)
Of zie ik dit te simplistisch in?

Alvast bedankt

[RedCat]

Je zit goed met je achterwaartse recursie:

Als je 1 dobbelsteen mag rollen, dan gooi je naar verwachting (1+2+3+4+5+6)/6 = 3.50

Als je 2 dobbelstenen mag rollen, en je rolt bij de eerste:
- een 1: dan ga je door, want max{1, 3.5} = 3.5
- een 2: dan ga je door, want max{2, 3.5} = 3.5
- een 3: dan ga je door, want max{3, 3.5} = 3.5
- een 4: dan stop je, want max{4, 3.5} = 4
- een 5: dan stop je, want max{5, 3.5} = 5
- een 6: dan stop je, want max{6, 3.5} = 6
Naar verwachting scoor je zo met 2 dobbelstenen dus (3.5+3.5+3.5+4+5+6)/6 = 4.25

Hoe zit dit bij 3 dobbelstenen (wat zijn dan je beslissingen na de eerste worp)?

Kom je hiermee verder?

[Iwiskunde]

Hoe zit dit bij 3 dobbelstenen?

Hartelijk bedankt voor de uitleg. Als ik me niet vergis, is de verwachte winst bij 3 dobbelstenen dan gelijk aan 4.67?
Namelijk: (4.25+4.25+4.25+4.25+5+6)/6
Klopt dit?

[RedCat]

Ja, en zo verder t/m 6 worpen

[nienke.belgium]

Maak je hier geen gebruik van voorgaande recursie ipv achterwaarts want je begint toch niet met het berekenen van f6(i) maar van f1(i)?

En wat zou je hier als algmeen recursie voorschrift noteren.

Daarnaast vroeg ik me ook af wat de einduitkomst zou zijn

[nienke.belgium]

Ik heb gevonden dat de verwachte opbrengst bij het gooien van 6 dobbelstenen 5,27 is maar hoe gebruik ik dit nu om te antwoorden op de dp recursie of is dit het eind antwoord?

[RedCat]

Maak je hier geen gebruik van voorgaande recursie ipv achterwaarts want je begint toch niet met het berekenen van f6(i) maar van f1(i)?

Dat is inderdaad verwarrend.

Bij DP lossen we ingewikkelde problemen op door deze problemen om te zetten in eenvoudiger deelproblemen, en die deelproblemen recursief op te lossen totdat we de oplossing van het oorspronkelijke ingewikkelde probleem hebben.
In het engels: de bottom-up benadering die we bedoelen met "achterwaarts": je begint bij het eind, en eindigt bij het begin (= het oorspronkelijke probleem).
Dit in tegenstelling tot top-down benadering ofwel "voorwaarts", waar je begint bij de vraagstelling en vanaf daar toewerkt naar het antwoord.
Een bekend voorbeeld is de Fibonacci rij, waar we Fib(1000) ook het best bottom-up berekenen (zowel wat betreft rekentijd als geheugengebruik) in vergelijking met memoizatie en/of top-down.

Maar als we uitsluitend naar de recursie kijken, dan verloopt deze inderdaad wel voorwaarts:
van i=0 naar i=1 naar i=2, etc.

En wat zou je hier als algmeen recursie voorschrift noteren.

Kijk naar de tabel wat we gedaan hebben:
(w=aantal mogelijke worpen, o = aantal ogen met die worp)

Code: Selecteer alles

Score | w[0]  w[1]   w[2]     w[3]     ....
------+--------------------------------
o = 1 |  -     1     3.5     4.25
o = 2 |  -     2     3.5     4.25
o = 3 |  -     3     3.5     4.25
o = 4 |  -     4     4       4.25
o = 5 |  -     5     5       5
o = 6 |  -     6     6       6 
------+------------------------------
gem:  |  0    3.5    4.25    4.67    .....

De recursie = de manier waarop je de tabel invult:

Start (n=0):
gemiddelde met nul worpen = gemiddelde w[0] = 0
Recursie (n>0):
voor o = 1 .. 6:
Score(w[n],o) = max{ gemiddelde(w[n-1]), o }
gemiddelde w[n] = SOM( Score(w[n],o) ) / 6

[RedCat]

Ik heb gevonden dat de verwachte opbrengst bij het gooien van 6 dobbelstenen 5,27 is maar hoe gebruik ik dit nu om te antwoorden op de dp recursie of is dit het eind antwoord?

Dit (die 5.27...) is de winstverwachting bij optimale strategie.
Maar er wordt gevraagd naar "de optimale strategie", en dat is "wat we moeten beslissen per worp":

Als de uitkomst (= het aantal ogen) van w[n] groter is dan het het gemiddelde van w[n-1], dan stoppen, anders doorgaan.

[nienke.belgium]

oke dit maakt het duidelijk bedankt voor het antwoord!