15
$\begingroup$

"I'm bored of riddles, I'm going to ask you a question about dice instead", says the Sphinx.

"Now, I've got this set of Efron Dice here. There's four dice, and they have these values on their faces:"

A: 4, 4, 4, 4, 0, 0
B: 3, 3, 3, 3, 3, 3
C: 6, 6, 2, 2, 2, 2
D: 5, 5, 5, 1, 1, 1

Efron's Dice

"So as I'm sure you can see, A beats B (with a 2/3 probability), B beats C, C beats D and D beats A, each with 2/3 probability."

"This works because I, the Sphinx, am a legendary magical animal, and so I can do weird things using the laws of probability."

"As a Sphinx, of course, this is very useful to me, because I can get my supplicant to choose a random die, and whichever one they pick I can always pick one that's better."

"But I'm tired of still losing 1/3 of the time! I want you to make me a set of dice where I'm even more likely to win!"

"If you can then I'll let you pass, if not then (as usual) I'll eat you for dinner."

Rules:

  • Die A must beat die B must beat die C must beat die D must beat die A, all with P(win) > 1/2. (This is because, whichever die the supplicant chooses, the Sphinx wants dinnertime to remain more likely than not).

  • There must be four dice in each set. Each die has six faces.

  • Each face of each die can contain any number from the set of integers 0-6. Numbers may be used more than once on each die.

  • For each set of dice, set P is 'better than' set Q if the Sphinx is more likely to win her game with it. The game is that the supplicant picks a random die and then the Sphinx picks her own die which is likely to beat the supplicant's die. Set P is a 'better' set than Q if the Sphinx is more likely to win her game with set P than she would be with set Q. First the supplicant chooses any die at random from the set, then the Sphinx chooses the die which is most likely to beat the supplicant's die.

  • If the Sphinx and the supplicant both roll the same number (a tie), then both parties roll again with the same dice.

  • For background info see Wikipedia: Nontransitive Dice

  • This is an open-ended challenge; the 'best' set of dice (the set with which the Sphinx is most likely to win her game) is the winning set.

  • Bonus credit if you can demonstrate that your set of dice is the best possible set.

Related (though not a duplicate): A first choice die

Improve this question
$\endgroup$
12
  • $\begingroup$ But P(win) > 1/2 using the set of dice you provided. Is this intended to be a trick question? $\endgroup$
    – Ian MacDonald
    Commented Aug 25, 2015 at 11:58
  • $\begingroup$ Hi @IanMacDonald - no, it's not a trick question, but if I haven't made it clear then I'll want to rephrase it. I'm asking for the set of dice which gives the Sphinx the highest probability of winning her game. I.e. asking for a set of dice which improves on the example given. $\endgroup$
    – A E
    Commented Aug 25, 2015 at 12:01
  • 2
    $\begingroup$ Nice question! And good to see you still around :-) $\endgroup$
    – Rand al'Thor
    Commented Aug 25, 2015 at 12:07
  • $\begingroup$ @IanMacDonald The set of dice provided aren't a valid solution though because of rule Each face of each die can contain any number from the set of integers 1-6 and the example set includes faces of value 0. $\endgroup$
    – Eborbob
    Commented Aug 25, 2015 at 13:53
  • 1
    $\begingroup$ How is p(win) calculated if the numbers on the two dice are not distinct? Or in other words, how are ties between the sphinx and the victim broken? Reroll? In favour of sphinx? In favour of victim? $\endgroup$
    – Peter Taylor
    Commented Aug 25, 2015 at 16:17

3 Answers 3

Reset to default
15
$\begingroup$

The post linked in rand al'thor answer optimized the worst case pick the visitor of the sphinx can make. But the question asked for the best average case.

A better solution in that case is:

A: 1,1,5,5,5,5
B: 2,2,2,2,6,6
C: 3,3,3,3,3,3
D: 4,4,4,4,4,4

B defeats A with a probability of $\frac{5}{9}$
C defeats B with a probability of $\frac{2}{3}$
D defeats C with a probability of $1$
A defeats D with a probability of $\frac{2}{3}$

On average that is a probability of $ \frac{1}{4} \cdot \frac{5}{9}+\frac{1}{4} \cdot \frac{2}{3}+\frac{1}{4} \cdot 1+\frac{1}{4} \cdot \frac{2}{3} = \frac{26}{36} > \frac{24}{36} = \frac{2}{3}$

I am not sure if $\frac{26}{36}$ is optimal or not.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Oho! The puzzle works after all. Hooray! :) $\endgroup$
    – A E
    Commented Aug 25, 2015 at 15:19
  • 2
    $\begingroup$ By exhaustion, $\frac{26}{36}$ is optimal. There are 119 equally good solutions. $\endgroup$
    – Peter Taylor
    Commented Aug 25, 2015 at 16:43
  • $\begingroup$ And incidentally, @AE, 10 of them don't involve 0s, so that change turns out to be extremely minor. $\endgroup$
    – Peter Taylor
    Commented Aug 25, 2015 at 16:49
  • $\begingroup$ @PeterTaylor, post the code and I'll upvote it! $\endgroup$
    – A E
    Commented Aug 25, 2015 at 16:56
  • 1
    $\begingroup$ wouldn't a 3/4 average probability be better? (111111, 222222, 333333, 444444) or am I missing something? Edit- nevermind, I just saw the requirement of winning on any choice with over 1/2 probability. $\endgroup$
    – vero
    Commented Aug 25, 2015 at 23:58
6
$\begingroup$

The optimal set of dice is

the set you've already found: Efron's dice.

This is proved, along with a considerably more general statement ($n$-sided dice instead of just 6-sided ones), in the article referred to in this post on MathOverflow.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Maybe a mistake in the rules, but the rules say Each face of each die can contain any number from the set of integers 1-6 and Efron's set includes values of 0. $\endgroup$
    – Eborbob
    Commented Aug 25, 2015 at 13:54
  • 1
    $\begingroup$ Aww, thats too bad really, I was all happy to have a 'logic' puzzle I understood and could attempt solving :( $\endgroup$
    – Spacemonkey
    Commented Aug 25, 2015 at 14:24
  • $\begingroup$ @Eborbob, you're right, see above. $\endgroup$
    – A E
    Commented Aug 25, 2015 at 15:20
  • $\begingroup$ @Spacemonkey, turns out it is possible to improve on Efron after all... $\endgroup$
    – A E
    Commented Aug 25, 2015 at 16:24
  • 3
    $\begingroup$ @AE Not entirely true.... With the Efron's dice there is always a 2/3 chance of winning. With the "better" set found in the other post, anybody who understands probabilities would most likely select A every time effectively limiting the Sphinx's chance of winning to 5/9... Tho re-reading I notice you said "choose a random die". I guess it depends whether or not they can make an informed decision... $\endgroup$
    – Warlord 099
    Commented Aug 25, 2015 at 21:08
5
$\begingroup$

Here's some python code which goes through all the possibilities, spitting out the best solution found so far. It takes a little while to run through everything, as you might expect. It seems to pause for a while, and then have sudden bursts of activity. It's probably somewhat slow simply because it's having to print so many solutions. Mine's been running for 20 minutes or so, and has converged onto a bunch of solutions with a score of 13/18 (as @Timbo found).

The logic of the code (for those who are interested is):

  1. Generate all the possible dice (there are 462 of them)
  2. For each dice, generate a list of dice that are "above" them (ie has a >50% probability that it beats it) - this is oneAway in the code.
  3. For each dice, generate a list of dice are are twoAway (using the above list).
  4. Using the above find all the dice that are 4 away from themselves (using the above) - there are 398 dice that do that.
  5. Using the above we can systematically go through all the loops of four.

It took more than an hour to run, partly because it went through all the results 4 times, which is an obvious improvement opportunity (edit - fixed that with the two discard lines near the bottom)! And in the end it found 11 results that matched the above solution:

115555 222266 333333 333334 13/18
115555 222266 333333 333344 13/18
115555 222266 333333 333444 13/18
115555 222266 333333 334444 13/18
115555 222266 333333 344444 13/18
115555 222266 333333 444444 13/18
115555 222266 333334 444444 13/18
115555 222266 333344 444444 13/18
115555 222266 333444 444444 13/18
115555 222266 334444 444444 13/18
115555 222266 344444 444444 13/18

Python Code:

import numpy as np
from fractions import Fraction
import itertools as it
from collections import defaultdict

class dice:
    def __init__(self,faces):
        self.faces = faces  #a numpy array of 6 numbers
    def beats(self,other):
        "probability that self beats other"
        if np.all(self.faces==other.faces): return (0,1)
        a = np.tile(self.faces,(6,1))
        b = np.tile(other.faces.reshape(6,1),6)
        return (np.sum(a>b),np.sum(a!=b))
    def __repr__(self):
        return "dice(%s)"%self.faces
    def __str__(self):
        return "%s%s%s%s%s%s"%tuple(self.faces)

def score(dice1,dice2,dice3,dice4):
    n1,d1 = dice2.beats(dice1)
    n2,d2 = dice3.beats(dice2)
    n3,d3 = dice4.beats(dice3)
    n4,d4 = dice1.beats(dice4)
    return Fraction(n1,d1*4)+Fraction(n2,d2*4)+Fraction(n3,d3*4)+Fraction(n4,d4*4)

print("Generating a list of dice...",)
allDice = []   
for a in it.combinations_with_replacement(range(1,7),6):
    allDice.append(dice(np.array(a)))
print("done! %d dice generated"%len(allDice))

print("Generating oneAway...",)
oneAway = defaultdict(list)
for dice1 in allDice:
    for dice2 in allDice:
        n,d = dice2.beats(dice1)
        if n*2<=d: continue
        oneAway[dice1].append(dice2)
print("done! %d dice available"%len(oneAway))

print("Generating twoAway...",)
twoAway = defaultdict(set)
for dice1 in allDice:
    for dice2 in oneAway[dice1]:
        twoAway[dice1].update(oneAway[dice2])
print("done!")

print("Generating fourAway...",)
fourAway = defaultdict(set)
for dice1 in allDice:
    for dice2 in twoAway[dice1]:
        fourAway[dice1].update(twoAway[dice2])
print("done!")

print("Generating candidates...")
candidates=[]
for dice1 in allDice:
    if dice1 in fourAway[dice1]:
        candidates.append(dice1)
print("done!",len(candidates))

print("Searching for results...")
maxScore=0
for dice1 in candidates:
    for dice3 in twoAway[dice1]:
        if dice1 not in twoAway[dice3]: continue
        for dice2 in oneAway[dice1]:
            if dice3 not in oneAway[dice2]: continue
            for dice4 in oneAway[dice3]:
                if dice1 not in oneAway[dice4]: continue
                s = score(dice1,dice2,dice3,dice4)
                if s>=maxScore:
                    maxScore = s
                    print(dice1,dice2,dice3,dice4,s)
    for a in oneAway: oneAway[a].discard(dice1)
    for a in twoAway: twoAway[a].discard(dice1)
print("done!")

Update: I noticed that the OP allows for 0-6, so adjusted the relevant line in the code and re-ran it. This yields additional solutions (for a total of 220), but still nothing better than 13/18:

004444 111155 222222 333333 13/18
004444 111155 222222 222223 13/18
004444 111155 222222 222233 13/18
004444 111155 222222 222333 13/18
004444 111155 222222 223333 13/18
004444 111155 222222 233333 13/18
004444 111156 222222 333333 13/18
004444 111156 222222 222223 13/18
004444 111156 222222 222233 13/18
004444 111156 222222 222333 13/18
004444 111156 222222 223333 13/18
004444 111156 222222 233333 13/18
004444 111166 222222 333333 13/18
004444 111166 222222 222223 13/18
004444 111166 222222 222233 13/18
004444 111166 222222 222333 13/18
004444 111166 222222 223333 13/18
004444 111166 222222 233333 13/18
004444 111155 222223 333333 13/18
004444 111156 222223 333333 13/18
004444 111166 222223 333333 13/18
004444 111155 222233 333333 13/18
004444 111156 222233 333333 13/18
004444 111166 222233 333333 13/18
004444 111155 222333 333333 13/18
004444 111156 222333 333333 13/18
004444 111166 222333 333333 13/18
004444 111155 223333 333333 13/18
004444 111156 223333 333333 13/18
004444 111166 223333 333333 13/18
004444 111155 233333 333333 13/18
004444 111156 233333 333333 13/18
004444 111166 233333 333333 13/18
004445 111166 222222 333333 13/18
004445 111166 222222 222223 13/18
004445 111166 222222 222233 13/18
004445 111166 222222 222333 13/18
004445 111166 222222 223333 13/18
004445 111166 222222 233333 13/18
004445 111166 222223 333333 13/18
004445 111166 222233 333333 13/18
004445 111166 222333 333333 13/18
004445 111166 223333 333333 13/18
004445 111166 233333 333333 13/18
004455 111166 222222 333333 13/18
004455 111166 222222 222223 13/18
004455 111166 222222 222233 13/18
004455 111166 222222 222333 13/18
004455 111166 222222 223333 13/18
004455 111166 222222 233333 13/18
004455 111166 222223 333333 13/18
004455 111166 222233 333333 13/18
004455 111166 222333 333333 13/18
004455 111166 223333 333333 13/18
004455 111166 233333 333333 13/18
004555 111166 222222 333333 13/18
004555 111166 222222 222223 13/18
004555 111166 222222 222233 13/18
004555 111166 222222 222333 13/18
004555 111166 222222 223333 13/18
004555 111166 222222 233333 13/18
004555 111166 222223 333333 13/18
004555 111166 222233 333333 13/18
004555 111166 222333 333333 13/18
004555 111166 223333 333333 13/18
004555 111166 233333 333333 13/18
005555 111166 233334 444444 13/18
005555 111166 233344 444444 13/18
005555 111166 233444 444444 13/18
005555 111166 234444 444444 13/18
005555 111166 244444 444444 13/18
005555 111266 333333 333334 13/18
005555 111266 333333 333344 13/18
005555 111266 333333 333444 13/18
005555 111266 333333 334444 13/18
005555 111266 333333 344444 13/18
005555 111266 333333 444444 13/18
005555 122266 333333 333334 13/18
005555 122266 333333 333344 13/18
005555 122266 333333 333444 13/18
005555 122266 333333 334444 13/18
005555 122266 333333 344444 13/18
005555 122266 333333 444444 13/18
005555 112266 333333 333334 13/18
005555 112266 333333 333344 13/18
005555 112266 333333 333444 13/18
005555 112266 333333 334444 13/18
005555 112266 333333 344444 13/18
005555 112266 333333 444444 13/18
005555 222266 333333 333334 13/18
005555 222266 333333 333344 13/18
005555 222266 333333 333444 13/18
005555 222266 333333 334444 13/18
005555 222266 333333 344444 13/18
005555 222266 333333 444444 13/18
005555 111166 333333 333334 13/18
005555 111166 333333 333344 13/18
005555 111166 333333 333444 13/18
005555 111166 333333 334444 13/18
005555 111166 333333 344444 13/18
005555 111166 333333 444444 13/18
005555 111266 333334 444444 13/18
005555 122266 333334 444444 13/18
005555 112266 333334 444444 13/18
005555 222266 333334 444444 13/18
005555 111166 333334 444444 13/18
005555 111266 333344 444444 13/18
005555 122266 333344 444444 13/18
005555 112266 333344 444444 13/18
005555 222266 333344 444444 13/18
005555 111166 333344 444444 13/18
005555 111266 333444 444444 13/18
005555 122266 333444 444444 13/18
005555 112266 333444 444444 13/18
005555 222266 333444 444444 13/18
005555 111166 333444 444444 13/18
005555 111166 222222 233334 13/18
005555 111166 222222 233344 13/18
005555 111166 222222 233444 13/18
005555 111166 222222 234444 13/18
005555 111166 222222 244444 13/18
005555 111166 222222 333333 13/18
005555 111166 222222 333334 13/18
005555 111166 222222 333344 13/18
005555 111166 222222 333444 13/18
005555 111166 222222 222223 13/18
005555 111166 222222 222224 13/18
005555 111166 222222 222233 13/18
005555 111166 222222 222234 13/18
005555 111166 222222 222244 13/18
005555 111166 222222 222333 13/18
005555 111166 222222 222334 13/18
005555 111166 222222 222344 13/18
005555 111166 222222 222444 13/18
005555 111166 222222 223333 13/18
005555 111166 222222 223334 13/18
005555 111166 222222 223344 13/18
005555 111166 222222 223444 13/18
005555 111166 222222 224444 13/18
005555 111166 222222 233333 13/18
005555 111166 222222 334444 13/18
005555 111166 222222 344444 13/18
005555 111166 222222 444444 13/18
005555 111166 222223 333333 13/18
005555 111166 222223 333334 13/18
005555 111166 222223 333344 13/18
005555 111166 222223 333444 13/18
005555 111166 222223 334444 13/18
005555 111166 222223 344444 13/18
005555 111166 222223 444444 13/18
005555 111166 222224 444444 13/18
005555 111166 222233 333333 13/18
005555 111166 222233 333334 13/18
005555 111166 222233 333344 13/18
005555 111166 222233 333444 13/18
005555 111166 222233 334444 13/18
005555 111166 222233 344444 13/18
005555 111166 222233 444444 13/18
005555 111166 222234 444444 13/18
005555 111166 222244 444444 13/18
005555 111166 222333 333333 13/18
005555 111166 222333 333334 13/18
005555 111166 222333 333344 13/18
005555 111166 222333 333444 13/18
005555 111166 222333 334444 13/18
005555 111166 222333 344444 13/18
005555 111166 222333 444444 13/18
005555 111166 222334 444444 13/18
005555 111166 222344 444444 13/18
005555 111166 222444 444444 13/18
005555 111166 223333 333333 13/18
005555 111166 223333 333334 13/18
005555 111166 223333 333344 13/18
005555 111166 223333 333444 13/18
005555 111166 223333 334444 13/18
005555 111166 223333 344444 13/18
005555 111166 223333 444444 13/18
005555 111166 223334 444444 13/18
005555 111166 223344 444444 13/18
005555 111166 223444 444444 13/18
005555 111166 224444 444444 13/18
005555 111166 233333 333333 13/18
005555 111166 233333 333334 13/18
005555 111166 233333 333344 13/18
005555 111166 233333 333444 13/18
005555 111166 233333 334444 13/18
005555 111166 233333 344444 13/18
005555 111166 233333 444444 13/18
005555 111266 334444 444444 13/18
005555 122266 334444 444444 13/18
005555 112266 334444 444444 13/18
005555 222266 334444 444444 13/18
005555 111166 334444 444444 13/18
005555 111266 344444 444444 13/18
005555 122266 344444 444444 13/18
005555 112266 344444 444444 13/18
005555 222266 344444 444444 13/18
005555 111166 344444 444444 13/18
015555 222266 333333 333334 13/18
015555 222266 333333 333344 13/18
015555 222266 333333 333444 13/18
015555 222266 333333 334444 13/18
015555 222266 333333 344444 13/18
015555 222266 333333 444444 13/18
015555 222266 333334 444444 13/18
015555 222266 333344 444444 13/18
015555 222266 333444 444444 13/18
015555 222266 334444 444444 13/18
015555 222266 344444 444444 13/18
115555 222266 333333 333334 13/18
115555 222266 333333 333344 13/18
115555 222266 333333 333444 13/18
115555 222266 333333 334444 13/18
115555 222266 333333 344444 13/18
115555 222266 333333 444444 13/18
115555 222266 333334 444444 13/18
115555 222266 333344 444444 13/18
115555 222266 333444 444444 13/18
115555 222266 334444 444444 13/18
115555 222266 344444 444444 13/18

Improve this answer
$\endgroup$
4
  • $\begingroup$ It looks nicer if you move the first line of output to the bottom. $\endgroup$
    – f''
    Commented Aug 28, 2015 at 18:15
  • $\begingroup$ You mean have the solutions below the code? $\endgroup$
    – Dr Xorile
    Commented Aug 28, 2015 at 18:51
  • $\begingroup$ I mean have "115555 222266 344444 444444" below "115555 222266 334444 444444". Anyway, those 11 results are all equivalent because the 4th die always beats the 3rd one, the only difference being how many rerolls it might take. $\endgroup$
    – f''
    Commented Aug 28, 2015 at 19:08
  • $\begingroup$ I see. That is a much prettier pattern. I've changed it. This was all just an attempt to brute-force the solution, rather than think about it. It was the easiest way to confirm that the solution given above was optimal. It means that the solution @Timbo found (presumably without a computer) was the best, and more or less the only one (barring a few cosmetic changes). Thanks for your comment. $\endgroup$
    – Dr Xorile
    Commented Aug 28, 2015 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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