Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:

  1. 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.

  2. 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.

share|improve this question
    
a) The $32$ is $2^5$, since you can decide independently for each of $5$ dice whether to reroll it or not. (If some of the dice show the same number, some of these possibilities will be equivalent.) b) You're considering only a single play (including rerolls); but if you really want to play optimally, you have to consider the entire remaining game, since the decision which slot to use a result for depends on how likely it is that you'll be able to fill that slot in the future (and with how many points, and how that affects your chance of getting the bonus). –  joriki Feb 17 '13 at 10:34
    
your accounts have been merged. you should be able to comment and respond to comments now. –  Willie Wong Feb 17 '13 at 17:03
    
Thank you! I appreciate that! –  user2045279 Feb 17 '13 at 17:18
    
Thank you for the reply joriki. I thought I may have to get into game theory trees, but I was hoping this could just be nice probability :). That's fine, it is what it is, and to truly have optimal play you must consider all possibilities. On that note, I would like to clarify your calculation. A 1's slot may have zero, 1, 2, 3, 4, or 5. This is 6 states. I am not sure where you got 7 from. Likewise a 5's slot can have 0, 5, 10, 15, 20, or 25. –  user2045279 Feb 17 '13 at 17:19
    
If we use yahtzee bonuses, only 5 states should be possible, namely 0, one, two, three, and four since 5 is a yahtzee. Reducing the exponential base would be quite effective at reducing possible states. But I could be quite mistaken here about it being 5 or 6 instead of 7. 27 for three of a kind... there are 6 possible three of a kinds. 1 1 1, 2 2 2, 3 3 3, 4 4 4, 5 5 5, 6 6 6. There are two remaining numbers, having 36 possible combinations... Perhaps this is where you get the 27, I can not quickly verify 21 unique ways to roll 2 dice. –  user2045279 Feb 17 '13 at 17:20

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Please see the comments on my initial post for a question on clarification. Thanks again for your time :) –  user2045279 Feb 18 '13 at 4:41
    
@user2045279: If you want people to be notified of your comments, you have to either ping them (as I'm doing in this comment) or comment under one of their posts (as you did in that last comment). I've added an explanation how the numbers of states come about, including a slight correction because I'd failed to differentiate between zero and nothing for some of the slots. Your counts are way too high because you're counting the numbers of ways that these states can be reached by particular rolls of dice, whereas you need only the state, not how you got there. –  joriki Feb 18 '13 at 7:19
    
I had one last question (hopefully) that I put in my original post as an edit. It is my percieved high level algorithm for what we discussed. I was hoping you could tell me if im misunderstanding what you've told me and the little part about the rolls at the end. Thanks again very much for everything! –  user2045279 Feb 18 '13 at 23:28
    
@user2045279: It looks good on the whole, but your description of it in terms of making a tree, then backing up is very different from how I think about it. First, note that each state can be reached from many different states, so if you treat this as a tree and talk about the parent of a state, you're replicating each state very many times. I'd write a cached function (or e.g. in Sage you can declare a function such that it's automatically cached) which calls itself recursively for all possible successor states, then call it for the initial state to calculate the game value. –  joriki Feb 18 '13 at 23:57
    
@user2045279: Keywords you might want to look up for this are dynamic programming and memoizing. Regarding the rolls: You can also regard every intermediate state as having a certain expected value. That is, your cached function gives you the expected value of every possible final result of the current play; that allows you to determine the values of the results at the stage where you have one reroll left, by maximizing the expected value over all possible choices of rerolls; this you can do at each of the three reroll stages, and again you can organize it all as recursive function calls. –  joriki Feb 19 '13 at 0:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.