# Best Strategy for Dice Game?

1. Jul 17, 2012

### Graff

You play against three automated players who’s dice and actions are independent from you.
Rules:
-You MUST keep at least one die, but can keep as many as desired.
-A (1) and (4) are qualifiers, without both qualifiers you cannot score. These do not count towards your score.
-Reroll all unchosen dice and repeat.
-Game ends when all six dice are chosen.
-Score is the combined value of the four scoring dice. Ties are considered losses. Wins must beat all three other players.

Pretty simple. A perfect score is 24 with (6,6,6,6,1,4) in no particular order.
Now, can someone help me with proving a best strategy for this game?
Currently I do this:
-No qualifiers or (6) -> Take highest die
-One qualifier and any amount of (6)-> Take qualifier and up to two (6)
- Both qualifiers and one or fewer (6)-> Take (4) and (6) (if (6) is available)
-Both qualifiers and two or more (6)-> Take all (6) and both qualifiers
-(5) will only be kept if it's one of the last 2 dice.
-(4) will only be kept if it's the last die.

Is this strategy significantly better than the default auto players who do what’s listed below?
-Keep any and all qualifiers if needed.
-On any given roll, if you have both qualifiers, it will keep all (6).
-If you have only one of the qualifiers, it will keep a maximum of one (6).
-If you have no qualifiers, it will only keep the highest die roll.
-(5) will only be kept if it's one of the last 2 dice.
-(4) will only be kept if it's the last die.

If you can help me with the math, I would love to figure out the odds here. Thanks!

Examples:
-(6,5,6,6,4,5)
Keep (6,6,4) (roll)
-(2,2,5)
Keep (5) (roll)
-(4,6)
Keep (6) (roll)
-(2)
Does not meet qualifiers, game over. (ex: should I have done only (6,4) to start?)

-(2,3,4,2,4,1)
Keep (4) (roll)
-(1,1,3,1,4)
Keep (1) (roll)
-(5,6,2,1)
Keep (5,6) (roll)
-(3,4)
Keep (4) (roll)
-(4)
Score 19, lose to opponents who have scores of (21,17,20) (ex: should I have done only (6) instead of (5,6)?)

2. Jul 18, 2012

### chiro

Hey Graff and welcome to the forums.

I would say that your strategy is going to be based on conditional probability and finding a maximum probability for every situation depending on what happens in each role.

The first thing to do is to make the qualifiers and non-qualifiers distinct and have some kind of analog of a 'pay-off' for each situation.

Also because every dice roll is considered independent, this makes things a lot easier mathematically.

So we start out with six rolls. We then break up our rolls into non-qualifiers vs qualifiers. We will have two starting scenarios: getting only qualifiers, getting only non-qualifiers or both.

The first situation is easy to deal with: choose 1 qualifier and check the rest out. The second situation is different because we will consider that keeping so many dice will affect our chances of obtaining a qualifier, and the third choice will result in keeping the qualifier and then deciding how many other dice to keep.

So the first thing to consider is the distribution of all scores given that we have a qualifier. We have to consider that we get the situations with 5,4,3,2,1 and even 0 non-qualifiers.

Since all dice are independent, this makes things a lot simpler. For 1 non-qualifier we get our average to be (2+3+5+6)/4 = 4. We simply add as many of these as we want as they are independent (remember each dice roll is independent) and we will obtain the average score to be 4*N where N is the number of non-qualifiers given at least one qualifier. If N=0 the score is 0 even if we have a qualifier (all of them will be qualifiers).

So for 5 non-qualifiers our average score is 20, and for the rest its 16,12,8,4 and 0.

So the strategy for this game is to attempt to maximize the expectation of the later score given what we already have now, and this will be our strategy from then on, but of course we have to consider the above situations.

If we have all qualifiers, get one and then working on maximizing the expectation of the total score at each step. If no qualifiers then we will need to evaluate a pay-off situation. If a mixture, then keep one qualifier and then work on maximization of expectation at each selection step.

We can calculate the total expectation taking into account the qualifiers by setting the score to zero for that qualifier. This gives the expectation of a dice-roll (with qualifiers taken into account) of (0+2+3+0+5+6)/6 = 16/6 which is a little less than 3. This is not the same as the above because we are taking into account all situations not just ones with scoring.

Now here is the algorithm:

Given a situation, calculate all possible scenarios given the current number of dice taken from previous rolls for all possible selections currently in play with the requirement that at least once dice be taken in this current play.

Also calculate through all possibilities of getting at least one qualifier in the play taking into account whether you already have one (in which the probability is 1). If this is the case that you have one, ignore this component. If not, then your goal is to maximize getting a qualifier.

To understand when you want to get a qualifier or not, you will need to consider a payoff with respect to situations where you haven't got one or not depending on the possibilities available to you.

The number itself will depend on how many dice you already have primarily if you have not received a qualifier already since each dice roll is independent.

So to clarify: our strategy is clear once we have a qualifier, find the simulations that maximize expectation that are based on not only what we choose to select in the current round, but how many we select in the current round.

But if we don't have a qualifier, we have to decide whether going for a qualifier is better as opposed not to and this involves finding out the sweet spot for when this should take place.

Before I go on, I'll just get some feedback from you since this is a pretty lengthy post.

3. Jul 18, 2012

### haruspex

Another complication is that maximising expected score on the dice is not the same as maximising expected winnings. The more opponents you have to beat, the more important is to get a high score - good scores won't cut it.
Your perfect strategy depends on the strategy of the opponents. Assuming all players use perfect strategy (and the automata are not ganging up on you), that will involve finding a Nash equilibrium.
In short, it will be extremely hard to solve this analytically. Could try a bit of genetic programming.

4. Jul 18, 2012

### chiro

Well it is an optimization problem so under that premise he will always try and maximize his score. Because of the random nature (unless he knew the pseudo-random procedure) expectation is the best thing that can be used.

Also I agree about the strategy part, but for the moment it's probably better to firstly work in a situation where it's winner takes all where there is no co-operation especially if the situation he is talking about is AI based with no co-operation (which is heavily implied due to "automation").

The other players status doesn't affect the optimization routine due to independence. The strategies are the same for all players because they all get the same opportunities (unlike say a poker game where all players get access to a shared deck, these players get access to their own individual dice independent from every other players).

5. Jul 18, 2012

### haruspex

Maximising chance of winning is also an optimisation. Take a much simpler example: you and three others each get to roll a die, with the option of re-rolling once if you don't like the first result. Highest score takes the pot. Settling for a four would not be a good strategy since it's very likely the winning score will be a 5 or 6.

6. Jul 18, 2012

### chiro

Yes but in this game they need qualifiers, so at some point in the game the need to get a qualifier and the need to get a high-score will swing in one direction.

Lets just stick the OP's game and not anything else: The OP said that upon every roll at least one must be kept and that you need at least one qualifier to score. This means that there is an element of payoff involved with regards to qualifiers and scoring.

7. Jul 18, 2012

### haruspex

My simplified version was to demonstrate that maximising average score was unlikely to be optimal in the OP game, and perhaps not even fairly good. A possible approach is to start with any reasonable strategy, model that to find the average of the highest of three scores, then develop a strategy that gives a good chance of beating that.
To answer one specific question in the OP, given an initial roll of 633221, say, I would recommend only keeping the 6. There's a very good chance of getting another 1 at some point.

8. Jul 18, 2012

### chiro

Saying things like this are really misleading. You are making an intuitive argument that many people make when it comes to probability which is wrong.

In this game you are forced to keep at least 1 dice. The probability of getting any permutation of five dice is equally likely in a truly independent scenario.

Also how is not maximizing the expectation and taking into account the dynamic between qualifiers and scoring an optimal strategy?

Your idea of keeping the 6 is an 'intuitive' play but its not mathematical, and the OP wants something a bit more specific. You are assuming that you'll have a better shot at getting a 1, but probabilistically this is just not true and is very misleading to say the least.

9. Jul 18, 2012

### haruspex

Sorry, but I disagree with you on almost every point.
Not all combinations are equally likely if you ignore the order: 54321 (5! ways) is more likely than 54311 (5!/2 ways), but anyway I don't understand which of my statements you were referring to there.
Maximising average dice score is not the same as maximising expectation of outcome from playing the game. For the latter, you need to maximise the probability of getting the highest score. The number of players to beat matters. Extrapolate the game to thirty players - if you don't score 20 or better I doubt you've a realistic chance of winning.
My example of not keeping the 1 from 633221 was in direct response to a question in the OP. The reasoning is that you need to give yourself a good chance of some more 5s and 6s (and a 4). The risk of ending up without a 1 in consequence is small. Yes, it's intuitive, and may well prove wrong, but it's a possibility that needs to be considered.
As I said before, the only realistic approach I can see to the problem is a program that simulates the game millions of times and tunes the strategy.

10. Jul 18, 2012

### Hurkyl

Staff Emeritus
The goal is to win, not to get a high score. Don't make the common mistake of confusing the two!

So, what you really want the expected win ratio.

The other players' status does affect optimization. To maximize the expected win ratio, at any point in the game you have to play to beat what the opponents have. e.g. you'll favor low-scoring conservative play when you're ahead and high-scoring risky play when you're behind.

Even if you ignore how well your opponents are doing, I would be extremely surprised if the strategy that maximizes the expected score is the same as the strategy that maximizes the expected win ratio. (unless it turns out the automated strategies are very bad, but even then I'd still be mildly surprised)

Last edited: Jul 18, 2012
11. Jul 18, 2012

### Hurkyl

Staff Emeritus
As an example:

If you hold 1435 and have rolled 64
And one of your opponents have kept all of his dice: 134556

Then keeping both of your dice will maximize your expected score, but keeping just the 6 will maximize your probability of winning.

12. Jul 18, 2012

### Graff

1)Since all dice are independent, this makes things a lot simpler. For 1 non-qualifier we get our average to be (2+3+5+6)/4 = 4. We simply add as many of these as we want as they are independent (remember each dice roll is independent) and we will obtain the average score to be 4*N where N is the number of non-qualifiers given at least one qualifier. If N=0 the score is 0 even if we have a qualifier (all of them will be qualifiers).
-------
I wasn’t clear, but if you get a qualifier and then you choose that same qualifier again it goes in the scoring category. This is why if given the choice between a one and a four I always choose the four because if another four shows up it’s not as damaging as compared to if I had chosen the one and another one shows up.
-------
2) If we have all qualifiers, get one and then working on maximizing the expectation of the total score at each step. If no qualifiers then we will need to evaluate a pay-off situation. If a mixture, then keep one qualifier and then work on maximization of expectation at each selection step.
-------
Get one what?
As for the maximization of expectation, yes, this is where troubles arise. If you get good numbers but no qualifiers, score wise it’s better to take them but then you don’t have as many dice to go for any needed qualifiers.
-------
As for the rest of the post, I understand that there is a balance between getting qualifiers and choosing dice. That I what I need help with: Finding the balance.

I read about Nash equilibriums on Wikipedia, to be honest I don’t think there’s much use for that in the early die rolls seeing as there are so many other players and also many more dice rolls. The odds of ALL of the opponents doing something that will cause the strategy for best score to deviate significantly from the strategy of beating the opponents will be negligible. With exception are cases near the end with maybe one or two dice and options to roll them.
Example:
Qualifiers are met, one (4) die is left, you have the option of keeping it or rolling it.
Current score: 16, opponents have scores of (16, 15, 15)
If you keep it, you end at 20. Possible losing die rolls: Op1(4,5,6), Op2(5,6), Op3(5,6)
Or (3/6)*(4/6)*(4/6)= 22.2% chance of winning
Rolling it has a (3/6) chance of increasing/nothing your odds, for(4) (5)(6) respectively
(3/6)*(4/6)*(4/6)= 22.2% chance of winning, *(1/6)= 3.70% chance
(4/6)*(5/6)*(5/6)= 46.3% chance of winning, *(1/6)= 7.71% chance
(5/6)*(6/6)*(6/6)= 83.3% chance of winning, *(1/6)= 13.89% chance
Add them up and you get a 25.3% chance of winning if you roll, not even counting the tiny odds of rolling a (1),(2) or (3)
Whereas if you were going for top score instead of beating, there’s a 50/50 chance (excluding rolling a (4) again as score would not change) of doing just as much harm as good.

Yes, exactly. These players can’t help each other at all.

Right, but that simplified example is exactly what you are going to be dealing with in the later rounds. Not so much when you have six dice.

13. Jul 18, 2012

### Graff

I’m sorry, but you need TWO qualifiers to score. Both a (1) AND (4)

I don’t think I agree with that, even with a good chance of getting another (1) at some point you will likely not even have to take it. If you choose to leave it the only benefit would come if you got a scenario where choosing a (1) is your best option score wise (not even looking at whatever qualifiers you have), which is not at all likely but could possibly be less likely than the odds of not seeing a (1) again which leads to a null score. I don’t have the math to work out the probabilities though. So why not take it on the first roll instead of waiting it out?

Yes, that’s correct: I would like math here.

I don’t understand how what you are saying about the combinations relates to the odds of getting any number seeing as each die is independent from the others even in the same roll.

Just looking at your example… it’s for late in the game. My main concerns are for the beginning of the game where you have many choices. In the beginning I’m fairly positive that the strategy that maximizes the expected score is nearly the same as the strategy that maximizes the expected win, seeing as you don’t know or have minimal information about your opponents.

14. Jul 18, 2012

### chiro

Also just to clarify when I say maximize expectation, this is a conditional thing that depends on each roll scenario and also on what is kept, not an average without regard to any conditional information: it is a conditional expectation. The other thing is that this expectation has to take into account the payoff of qualifiers so it's not just "choose the highest number" strategy.

15. Jul 19, 2012

### Hurkyl

Staff Emeritus
I doubt that; I'm pretty sure the game doesn't go on long enough for "best average play" to be nearly optimal. The information is not minimal, you have two very significant pieces of information:
• You know you have three opponents
• You know their exact strategy

If we don't get to see what the others are rolling,
Anyways, the typical way to exactly solve a problem like this is as follows:

• Compute the probability that any particular opponent will have an ending score of N
• Compute the odds that any particular score will win.
• Compute the odds of winning giving any 5 frozen dice.
• Compute the optimal play given any 4 frozen dice and any pair of rolled dice.
• Compute the odds of winning given any 4 frozen dice.
• Compute the optimal play given 3 frozen dice and any triple of rolled dice.
• Compute the odds of winning given any 3 frozen dice.
• et cetera

Of course, when I say "any n frozen dice", the actual pips and ordering don't matter, just the total value and which qualifiers are present. Similar simplifications can be made regarding rolled dice. If you program it right, I think the actual computation will be under a second.

If you can see what your opponents have at any point in the game, you can just redo the above computation to figure estimate optimal play is at any point in time. This is still just an estimate, because the calculation doesn't take into account the fact you can do the calculation again once you see what your opponents have rolled.

I bet the game is exactly solvable without too much computation, but it would take more thought.

16. Jul 19, 2012

### Graff

It's the second rule; and yes I have put enough time and thought into this process to realize that I don't know HOW to take into account the payoff of the qualifiers.

What I meant by early on was literally early on. As in you have no clue as to what your opponents have, or they have maybe a die... how can it be possible for that information to significantly alter the plan for highest score? Obviously, yes you will have to eventually take into account the scores of your opponents but I'm talking about the first roll here.

Opponents:
You can see what they have already chosen but not what they have rolled. If you choose a die, they will all choose a die (in other words, you will always have the same number of dice chosen as them.) You can choose one die at a time even if you intend to take multiples and this will display each die choice of your opponents.

Ex:
(4,6,5,3,5,3)
Choose (4): Op1(1), Op2(4), Op3(1)
Then
Choose (6): Op1(4), Op2(1), Op3(4)
Now how does this little information about what the opponents have in making a decision at this point in time?
I'm left with (5,3,5,3)
Does anything done by my opponents lead to me choosing a (5) now? I don't think so...
-------
I know you all can see the big picture and have the gist of what needs to be done and I really appreciate the discussion, but I'm looking to get at the nitty gritty case by case scenario type things. I'll try to simplify it by using some example "problems."

1)You roll a (1,6,5,4,2,3) on your first roll.
Which dice do you choose for this roll?
Explain why.

2)You roll a (6,6,1,4,4,1) on your first roll.
Which dice do you choose for this roll?
Explain why.

3)You roll a (6,5,1,4,6,6) on your first roll.
Which dice do you choose for this roll?
Explain why.

4) You roll a (6,5,6,6,5,5) on your first roll.
Which dice do you choose for this roll?
Explain why.

17. Jul 19, 2012

### Hurkyl

Staff Emeritus
The explanation will be:
Because I did the computation I described and have an estimate of the odds of winning for any choice of dice to keep, so I chose the one with the best estimate.​
What the actual choice is will have to wait until (or if) I actually do the calculation.

18. Jul 19, 2012

### Hurkyl

Staff Emeritus
Your bot strategy is unclear, specifically the final two lines:

-(5) will only be kept if it's one of the last 2 dice.
-(4) will only be kept if it's the last die.​

I assume you mean the following:
If you have both qualifiers, then after following the previous rules this turn:
• If there are two dice left, keep all 5's
and then, if you have both qualifiers:
• If there is one die left and it's a 4, keep it

There appear to be omissions. If your bot has previously kept (5,5,6,3) and rolls a (1,6), your listed strategy tells it to keep both dice, when clearly you should only keep the 1.

19. Jul 19, 2012

### Hurkyl

Staff Emeritus
To demonstrate the general computational method, here is some python 3.2 code:

Code (Text):
from collections import defaultdict
from fractions import Fraction
import itertools

def _bot_dist(tot, h1, h4, left):
dd = defaultdict(Fraction)
ct = 6 ** left
rolls = defaultdict(int)
for roll in itertools.product(range(1,7), repeat=left):
rolls[tuple(sorted(roll))] += 1

for roll, reps in rolls.items():
rh1 = h1
rh4 = h4
rtot = tot
kept = 0
n4 = roll.count(4)
n6 = roll.count(6)
if not h1 and 1 in roll:
kept += 1
rtot += 1
rh1 = True
if not h4 and n4 in roll:
kept += 1
rtot += 4
rh4 = True
n4 -= 1
if rh1 and rh4:
kept += n6
rtot += n6 * 6
if rh1 + rh4 == 1:
if n6:
kept += 1
rtot += 6
if rh1 and rh4 and kept >= left - 2:
n5 = roll.count(5)
kept += n5
rtot += 5 * n5
if rh1 and rh4 and kept >= left - 1:
kept += n4
rtot += 4 * n4
if kept == 0:
kept += 1
rtot += max(roll)
dist = bot_dist(rtot, rh1, rh4, left - kept)
for key, value in dist.items():
dd[key] += reps * value / ct
return dd

def bot_dist(tot, h1, h4, left, cache = {}):
key = tot, h1, h4, left
if key in cache:
return cache[key]
if left == 0:
if h1 and h4:
val = { tot - 5 : Fraction(1) }
else:
val = { 0 : Fraction(1) }
elif left == 1 and not h1 and not h4:
val = { 0 : Fraction(1) }
else:
val = _bot_dist(tot, h1, h4, left)
cache[key] = val
return val

def best_of_3(state1, state2, state3):
d1 = bot_dist(*state1)
d2 = bot_dist(*state2)
d3 = bot_dist(*state3)
dd = defaultdict(Fraction)
for x in itertools.product(d1, d2, d3):
dd[max(x)] += d1[x[0]] * d2[x[1]] * d3[x[2]]
return dd

s = (0,False,False,6)

print("-----------------------")
print("Single Bot distribution:")
for key,value in sorted(bot_dist(*s).items()):
print(key, float(value))
print("-----------------------")
print("Best of 3 bots distribution:")
dd = best_of_3(s, s, s)
for key, value in sorted(dd.items()):
print(key, float(value))

This computes the probability distribution of the outcomes of bot play. The four arguments to the functions are:
• tot: The sum of all kept dice
• h1: Whether or not a 1 has been kept
• h4: Whether or not a 4 has been kept
• left: The number of dice left to roll

These can be computed from any position. Values are cached, so once you've run it for the full game, it will instantly return for any future function calls. Running the script gives the output

Code (Text):

Single Bot distribution:
0 0.31183877389415404
4 2.8880983979325174e-09
5 7.597144367606115e-08
6 8.492575962544584e-07
7 5.782019763746673e-06
8 2.8471086588826003e-05
9 0.00011601871137524525
10 0.00041209025512933773
11 0.0012468938552789603
12 0.0031953627424947616
13 0.007084764545441625
14 0.014019281487101605
15 0.024364474936225948
16 0.03720517278956893
17 0.05209435116901662
18 0.07697078231015148
19 0.09134789260618388
20 0.09371545530467242
21 0.10544990314275007
22 0.09603653072646737
23 0.06287948491033321
24 0.021987585390163593
-----------------------
Best of 3 bots distribution:
0 0.03032426914391705
4 8.425457121685544e-10
5 2.216317503219553e-08
6 2.477549417030637e-07
7 1.6868314616259175e-06
8 8.306993396826751e-06
9 3.386640188802764e-05
10 0.0001204948218662447
11 0.0003665310576940017
12 0.0009526778568417031
13 0.0021817919724946527
14 0.004606882483742413
15 0.008964244057182474
16 0.01620790321030364
17 0.028339100333747272
18 0.055578181859228
19 0.09056227699444393
20 0.12520548181729718
21 0.186093297251702
22 0.21684753586246636
23 0.1690821758688859
24 0.06452302442077826

20. Jul 19, 2012

### Graff

Wow!
That's perfect!
Thank you so much Hurkyl!
I'll have to look into how to use python now.
Is there any way to convert what you wrote out into a GreaseMonkey script so I can try it?