I'm a senior in computer science, and I have a hobby of taking on little projects that I find interesting. My current one is a Yahtzee optimal play solver. One would enter their current roll, and it would tell you if/what to hold onto and what to reroll (if any). It will then tell you what field to put your score in after the potential 2 re-rolls of varying sizes.
So far, I've come up with the following:
I realize calculating the probabilities for all possible configurations takes a lot of math, like "Probability of yahtzee if you can reroll twice" is about 1/29. But the probability with just one roll is 1/7776. Big difference. So I am going to write a simulation for ~1 billion random plays to see the (nearly accurate) odds of certain outcomes are after three rolls. So we can assume probabilities of outcomes are out of the way.
I plan to create something like this: Consider a very concrete non-ambiguous example of just numbers. Say your value is 20. If you reroll (in this particular way), you have a 30% chance at 30, a 25% chance at 20, a 35% chance at 5, and a 10% chance at 80. Expected net = E(gain) - E(Loss) = Sum E(val_i - val). So we have E(change/net) = .3*(30 - 20) + .25*(20 - 20) + .35*(5 - 20) + .10*(80 - 20) = 5.75. So odds are if we make the roll, we will get 25.75 instead of our current 20. This is awesome and works great for this nice simple case... but when we speak of yahtzee, it isnt so simple.
For instance, we have four of a kind for, say, 5's. We also have a 5's place on the scoreboard. So if we have a 30% chance at 4 of a kind, we also have a 30% chance at four 5's. The point i'm trying to make is that your percentages wont add up to 100%. You could normalize them, but then you run into the problem of reducing weight on "something you would pick if you got it" which lowers the expected net value. For instance, say you have 1 1 2 2 3. If you rerolled the 3 to a 1, a 1/6 chance, you could either take the 25 point full house or the 3 point 1's. If we normalized, it would have a < 1/6 chance for full house and < 1/6 for 1's, depending on how many other % are in this normalization. So we are weighting the full house less simply because a paralell case exhists, even though you would likely choose the full house and not the 3 1's (I hope i'm making sense and not just rambling...) .
Anyway, i would love if one of your brilliant minds could help me think of an elegant way to do this. That is, given a roll of 5 dice and one of the 31 possible ways to hold back dice and reroll the others, which of the reroll configurations should you do, or should you not reroll (the 32nd choice). This is the "high level' way of saying this.
The lower level version is "Given the 32 choices (31 ways to reroll, 1 way to not reroll), which will give you the optimal score?". I got the 32 from (5 choose 0) ways to reroll no dice + (5 choose 1) ways to reroll 1 dice, etc to (5 choose 5) ways to roll 5 dice.
I'm just looking for some insight on how to weight your decisions appropriately. My hunch is that you have to do a bit of tricky manipulation such that if you have overlapping cases, you take the maximal case? (Ie. Three 1's vs. a full house with 1 1 1 2 2 after rerolling the 3 in 1 1 3 2 2, you would take that chance multiplied by the full house value, and not put any weight to the 3 1's. This of course assumes we need both a FH and 1's. If you didn't need a full house, it wouldnt even be in the equation).
Thanks everyone who takes the time to read this :).
John
[Edit:]
Thanks again for your help. I'm pretty sure I know how to do this now, but I wanted to run it by you to make sure im not misunderstanding anything. I know that you cant fit the entire game tree, but im just writing this in general assuming we had infinite memory. I know i'd actually only be able to use this with some initial non-blank states.
Begin algorithm
We have 13 boxes, each with a certain number of states. When we make the tree, we start with all states initialized to "nothing", and simply proceed to do all possibilities of the states which gives us all possible end states when completed. Let us look at one such "leaf" node, which is at the end of a completed path through our tree.
In order to backtrack up the tree and give nodes values (scores), we start here. This nodes value is the sum of all scores in all boxes. To give its parent a value though, we set our value(score) to val := (val - stateScore) + (stateScore*probStateScore); This, from the parents point of view, takes away the guarenteed gain from that node state and changes it to the expected value (since we havent gotten that state yet, it is no longer a given but a probability). So if this nodes value is 300, and the gained score from its last choice was 50 with a probability of 10%, you would set your value to 250 + 5 = 255. Now, you parent takes the max of all its children and sets its own value to val := (max(children) - thisNodesStateScore) + thisNodesStateScore*probOfThisStateScore; By the time we get to the top, we have a set of nodes (first tier of the tree) with the optimal expected values should you pick them.
When playing the game, we may roll perhaps a 1 1 2 1 5. We can classify this as a 0 in any state, a 3 of a kind of ones = scoreState(10), 3 ones = scoreState(3), one 5 = scoreState(5), or one 2 = scoreState(2). We observe which of the values of these states is maximal, and choose that state. Continue until the end of the game.
End algorithm
If this is right, my question was how does the 3 rolls come into this? If you roll 1 1 2 15 and you have 2 rolls left, how do you give the optimal setup to hold and reroll based on the optimal values in the tree? Again, we can assume we know all probabilities of rolling a given setup. Thanks again, and I apologize that this question was so long and time consuming.
