Optimal Yahtzee (Dice roll) decisions: Probability and weighting choices 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. 
 A: As I wrote in a comment, if you're really going for optimal play, you need to consider the entire remaining game. The game has a finite but considerable number of possible states: There are $7$ different states for each of the $1$s through $6$s slots, $27$ different states for each of the three-of-a-kind, four-of-a-kind and chance slots, three binary states for full house and the two straights, and a count of yahtzees that you can probably safely limit to something like $0$ to $4$, for a total of $7^6\cdot27^3\cdot3^3\cdot6=375141013254$. That's a bit too much to keep in memory, but after two or three plays the number is reduced considerably and it becomes feasible to calculate the value of the remaining game by dynamic programming. That allows you to focus on a single play, since the later stages of the analysis tell you for every given final result of the current play which slot to use it for.
Assuming that you do know which slot to use which final result for, the problem you describe in the question (if I understand it correctly) isn't a problem. Every final result has a certain value, given by the maximum of all game values that would result from using it in the slots it can be used in, and you just need to optimize the expected value of these final result values; the probabilities of the final results add up to $1$, and the probabilities of getting a result that could be used for a particular slot are just a distraction; what counts isn't what slot a result could be used for but only which slot you actually will use it for in optimal play.
[Edit:]
The numbers of states come about as follows: In the slot for the $1$s, you may have entered anything from $0$ to $5$ $1$s, which makes six states, or you may not have entered anything yet, which makes seven. The slots for three-of-a-kind, four-of-a-kind and chance can contain any of the sums from $5\cdot1=5$ to $5\cdot6=30$, which makes $26$ states, or nothing, which makes $27$. The slots for full house and the two straights can each contain either nothing, zero, or the value of that slot, which makes $3$ states. The yahtzee count can in principle go up to the number of plays in the game, $13$, but I've never seen anyone roll more than $3$ yahtzees in a game, and I think it can be safely limited to $4$ or so; that makes five different states for the counts from $0$ to $4$, and one for nothing, which makes six.
