5
$\begingroup$

Assuming you have 5 fair dice and up to 3 re-roll attempts (during which you can re-roll any dice, as per standard Yahtzee rules) what is the probability of succesfully rolling a "Small Straight" (aka 1-2-3-4, 2-3-4-5, or 3-4-5-6)? Also, what is the probability of rolling a "Large Straight" (aka 1-2-3-4-5 or 2-3-4-5-6)?

In either case, assume the following rules for keeping and re-rolling dice:

  • Keep exactly one of each 2, 3, 4, and 5 result
  • Only keep a 1 or 6 result if it is already part of a Small Straight or Large Straight

Unfortunately I'm quite unfamiliar with even basic probability problems let alone something with this level of complexity, and online research hasn't helped much. I'm much more comfortable backing into probabilities by simulating roll outcomes like this in Python, though I've hit a wall with those efforts as well for straights in particular, even with these defined rules. Would deeply appreciate some help.

Thanks!

$\endgroup$
3
  • 1
    $\begingroup$ Welcome to MSE. You'll get a lot more help if you show that you have made a real effort to solve the problem yourself, even if you haven't made much progress. What are your thoughts? What have you tried? How far could you get? Where are you stuck? This question will likely be closed if you don't add more context. Please respond by editing the question body. Clarifications don't belong in the comments. $\endgroup$
    – saulspatz
    Commented Feb 19, 2021 at 21:57
  • $\begingroup$ You said you are comfortable with Python, so what are your simulation results? Note that the state space is at most $6^{5+3}\approx 1.6 \times 10^6$ (list out all strings of 5 rolls plus max 3 re-rolls), so should be doable by brute force. $\endgroup$ Commented Feb 19, 2021 at 23:14
  • $\begingroup$ Hi there! Unfortunately I haven't yet been able to do any actual simulation of this question since, as I mentioned, I've hit a proverbial wall (aka the limits of my personal Python knowledge). I have succesfully simlated simply rolling x number of die faces in 3 tries, but I haven't been able to account for the sequence of numbers required to roll any kind of straight. I've basically been treating each die face as a unique object rather than a number and programmed simple keep rules for these faces accordingly (using a straightforward brute force approach as you recommended!). $\endgroup$
    – Foobz
    Commented Feb 20, 2021 at 17:40

1 Answer 1

1
$\begingroup$

(I have edited the answer)

Large Straight

Let me see if I got the strategy rules right. Does the following simulation code (in Python) model the situation correctly?

import random

keepers = set([2,3,4,5])

def simuLS(doPrint=False):
    kept = set()
    for roundI in range(3):
        ds = [random.randint(1, 6) for _ in range(5-len(kept))]
        for d in ds:
            if d in keepers: kept.add(d)
        if 1 in ds and all(x in kept for x in [2,3,4]):
            kept.add(1)
        if 6 in ds and all(x in kept for x in [3,4,5]):
            kept.add(6)
        gotLS = len(kept)==5
        if doPrint:
            print ("Rolled", ds)
            print ("Kept are ", kept)
            print ("Got LS: ", gotLS)
        if gotLS: return True
    return False

#Let's see how it goes
#simuLS(doPrint=True)

simuN = 10000
p = sum(1.0 for _ in range(simuN) if simuLS())/simuN
print (float(p))

The output is around 0.24.

Are you familiar with Markov chains? We can construct a Markov chain with states all the combinations of the keeper-numbers $\{1,2,3,4,5,6\}$ at most of length 4 and having 1 or 6 only if 2,3,4 and 3,4,5 are present respectively. We also have one absorbing state 'LS' that means we have gotten a large straight. We can calculate the transition probabilities by brute force by considering all possible rolls of the not kept dice (there are 5 - length of the state of them) and seeing what additional keepers we got or did we in fact get a LS. I wrote the following code in SageMath, since it handles matrices and rational numbers without any efforts.

import itertools

keepers = set([2,3,4,5])

states = [tuple(S) for S in Subsets(range(1,7)) if len(S)<5 and
          (1 not in S or all(x in S for x in [2,3,4]))
          and (6 not in S or all(x in S for x in [3,4,5]))]
startState = tuple() #the empty set
targetState = 'LS' #have gotten large straight
states.append(targetState)
stateToInd = {s: i for i,s in enumerate(states)}
startI = stateToInd[startState]
targetI = stateToInd[targetState]
mat = matrix(QQ, len(states))

for i1,s1 in enumerate(states[:-1]): #don't do for the LS-state
    d = 5-len(s1) #how many dice are (re-)thrown
    s1Set = set(s1)
    p = 1/6**d #probability for each outcome
    for xs in itertools.product(*[range(1, 7) for _ in range(d)]):
        s2Set = s1Set.union(set(xs)&keepers)
        if 1 in xs and all(x in s2Set for x in [2,3,4]): s2Set.add(1)
        if 6 in xs and all(x in s2Set for x in [3,4,5]): s2Set.add(6)
        
        if len(s2Set)==5: #got LS
            mat.add_to_entry(i1, targetI, p)
        else:
            s2 = tuple(sorted(s2Set))
            mat.add_to_entry(i1, stateToInd[s2], p)
mat.add_to_entry(targetI, targetI, 1) #absorbing state

#look at the transition matrix
print (len(states))
print (states)
show(mat)

#print ([sum(row) for row in mat]) #sanity check

sol = (mat**3)[startI][targetI]
print (sol, "=", float(sol))

You can run Sage code online: Sage Cell Server

The output is $\frac{295073737}{1224440064} = 0.24098667274578822$.

I'm not sure the grouping together of states, that I mentioned in my answer before editing, can be done anymore, since now the transitions to the states containing 1 or 6 depend on what we already have. At least not for all same-size-groups. Anyhow, we have a $19\times 19$-matrix, so it is doable.

Small Straight

We can use the previous Markov chain also here:

startRow = (mat**3)[startI]
endsForSmall = [stateToInd[s] for s in states if len(s)>=4] + [targetI]
smallSol = sum(startRow[j] for j in endsForSmall)
print (smallSol, "=", float(smallSol))

Answer: $\frac{2966131613}{4897760256} = 0.605609800799527$

For simulation:

import random

keepers = set([2,3,4,5])

def simuSS(doPrint=False):
    targets = [(1,2,3,4),
               (2,3,4,5),
               (3,4,5,6)]
    kept = set()
    for roundI in range(3):
        ds = [random.randint(1, 6) for _ in range(5-len(kept))]
        for d in ds:
            if d in keepers: kept.add(d)
        if 1 in ds and all(x in kept for x in [2,3,4]):
            kept.add(1)
        if 6 in ds and all(x in kept for x in [3,4,5]):
            kept.add(6)
        gotSS = any(all(x in kept for x in y) for y in targets)
        if doPrint:
            print ("Rolled", ds)
            print ("Kept are ", kept)
            print ("Got SS: ", gotSS)
        if gotSS: return True
    return False

#Let's see how it goes
#simuSS(doPrint=True)

simuN = 10000
p = sum(1.0 for _ in range(simuN) if simuSS())/simuN
print (float(p))
#--> 0.60
$\endgroup$
5
  • $\begingroup$ Thanks for the comprehensive response! The Python code looks totally correct when simulating the keep 2-3-4-5 rule and keep 1 or 6 if part of large straight rule. However, I was hoping it would keep 1 or 6 if it was already part either type of straight (including small). This seems more in keeping with an intuitive straight rolling strategy in a yahtzee-style game. I'm assuming this change would require swapping out the gotLS check with a more general "gotStraight" check, though it would go beyond just checking length. I'll try to adapt the code, though I'd love your thoughts on this too! $\endgroup$
    – Foobz
    Commented Feb 20, 2021 at 17:31
  • 1
    $\begingroup$ @Foobz Ahaa, I see. I edited my answer (both the simulation and Markov chain code). Yes, we get a bigger probability with this strategy! $\endgroup$
    – ploosu2
    Commented Feb 20, 2021 at 18:31
  • $\begingroup$ Incredible! This code is clean and your answer is exhaustive and easy to follow (and seems exactly correct). Thank you so very much for your response--I plan on spending time dissecting the code's structure and syntax so I can adapt it to other similar questions in the future, but for now I consider this problem solved. Thanks again! $\endgroup$
    – Foobz
    Commented Feb 21, 2021 at 4:17
  • $\begingroup$ @Foobz No problem. One minor modification that came to my mind is that you could, if you have kept 1234 and a 5 comes up, change 1 into 5 (and similarly a 6 to 2) because open ended is better. This only effects LS, of course. Also, I think now we can use the same Markov chain to calculate the small straight. Just sum the startI-row entries for all states which are already a small straight. We get 0.6056098. $\endgroup$
    – ploosu2
    Commented Feb 21, 2021 at 7:01
  • $\begingroup$ I just realized that those modifications have no effect: in those situations we already get a large straight! $\endgroup$
    – ploosu2
    Commented Feb 21, 2021 at 7:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .