Nontransitive Dice Finder -- /dev/random

Nontransitive Dice Finder

Overview

Nontransitive dice are sets of 3 or more dice, we will label D1,D2,...DN, such that P(D1 > D2) > .5, P(D2 > D3) > .5, ... P(DN-1 > DN), P(DN, D1). In other words dice that act like rock-paper-scissors, each dice has one that will beat it.

The original problem that got Chris and myself started on this was the God Einstein Oppenheimer Dice Puzzle which paints the numbers 1-18 on 3, 6 sided dice. The question we had is what is the list of all possible dice that solve this problem. It turns out to be a somewhat difficult program to conceive efficiently.

Number of total dice

It is important to first know how many total sets of 3 dice there are without considering which of those are nontransitive, since we will need to check every set, and we want to avoid repeats. We can treat the dice as unordered sets, since the ordering does not effect the probabilities. Note that ignoring the fact the sets are unordered greatly increases the cases we have to test:

Programming Considerations

The main goal of this program was to keep the execution time low, that means not checking repeated sets. The textual description of the algorithm is as follows:

The first dice is done by completing the following sequence:
- 1,2,3,4,5,6
- 1,2,3,4,5,7
- ...
- 1,2,3,4,5,18
- 1,2,3,4,6,7
- ...
- 1,14,15,16,17,18
- Note: We don't ever need to change the first number, more on that later
At the end of each sequence the same thing is performed for numbers 1-12
At the end of that the remaining numbers are placed on the third dice
These new numbers, 1-12, are hashed to correspond to the remaining 12 numbers after the first 6 were placed.
The transitive test is then performed for P(A)>P(B)>P(C)>P(A) and P(A)>P(C)>P(B)>P(A). If either is true it is in the set.
Note that leaving the first number always the same for the first 2 dice acts as the 3! divisor in above equation. It's easy to show this considering 3, 2 sided dice:

1,2; 3,4; 5,6
1,2; 3,5; 5,6
1,2; 3,6; 4,5
1,2; 4,5; 3,6
1,2; 4,6; 3,5
1,2; 5,6; 3,5
Note that the last 3 sets are repeats of the first 3 sets...so we really want half of them. Or the set where the first number of the second die always stays the same.
Note that each set of #,#; .. has 6 items each
Remaining start dice: 1,3; 1,4; 1,5; 1,6; 2,3; 2,4; 2,5; 2,6; 3,4; 3,5; 3,6; 4,5; 4,6;
Note: That all sets with the first number of the first dice is greater than one is a repeat. For example: 4,5; 1,2; 3,6; is a repeate of 1,2; 3,6; 4,5;
Total with repeats: 6*(5 + 4 + 3 + 2 + 1) = 90
But actual unique sets ignoring order is 6/2 * 5 = 15 = 90 / 6 = 90 / 3!

Download

dice.c -- Program to find all non transitive dice with 1-18 placed on them. Ended up at 28 SLOC :)

Conclusion

This was a fun little exercise that took a bit of initial experimentation to efficiently solve. Going through every permutation would have been near impossible since there would be 18! which is roughly 6.4 quadrillion sets. And then trying to get actual unique answers out of this would be horrendous. The total number of nontransitive dice with 1-18 uniquely placed on them ends up being 10,705 which was higher than expected.

Interesting Sets Of Dice

There are two sets, each containing both the lowest and highest possible face counts:
(1,10,11,12,15,16),(2,3,4,13,17,18),(5,6,7,8,9,14)
and
(1,2,6,15,16,17),(3,4,7,8,9,18),(5,10,11,12,13,14)
with the dice totaling (65,57,49) and (49,57,65) respectively.

There are 15 ways to get all dice to have a probability of 7/12, which is the highest probability you can get for all 3 dice:

(1,2,9,14,15,16)(3,4,5,10,17,18)(6,7,8,11,12,13)
(1,2,11,12,13,18)(3,4,5,14,15,16)(6,7,8,9,10,17)
(1,6,7,8,17,18)(2,9,10,11,12,13)(3,4,5,14,15,16)
(1,6,11,12,13,14)(2,3,4,15,16,17)(5,7,8,9,10,18)
(1,7,10,12,13,14)(2,3,4,15,16,17)(5,6,8,9,11,18)
(1,7,11,12,13,14)(2,3,4,15,16,17)(5,6,8,9,10,18)
(1,8,9,12,13,14)(2,3,4,15,16,17)(5,6,7,10,11,18)
(1,8,10,11,13,14)(2,3,4,15,16,17)(5,6,7,9,12,18)
(1,8,10,12,13,14)(2,3,4,15,16,17)(5,6,7,9,11,18)
(1,8,11,12,13,14)(2,3,4,15,16,17)(5,6,7,9,10,18)
(1,9,10,11,12,14)(2,3,4,15,16,17)(5,6,7,8,13,18)
(1,9,10,11,13,14)(2,3,4,15,16,17)(5,6,7,8,12,18)
(1,9,10,12,13,14)(2,3,4,15,16,17)(5,6,7,8,11,18)
(1,9,11,12,13,14)(2,3,4,15,16,17)(5,6,7,8,10,18)
(1,10,11,12,13,14)(2,3,4,15,16,17)(5,6,7,8,9,18)

Also of interest is that each optimal set contains at least one die with a sum of 57 which is the (sum(1 to 18))/3.

Comments(10) 2009-06-23 18:00:51

(2010-08-10 11:13:21) jim said:

The probabilities of the last item in your optimum list

(1,10,11,12,13,14)(2,3,4,15,16,17)(5,6,7,8,9,18)

are not 7/12.

These are equivalent to Rowett Dice

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

where P(A > B) = 7/12, P(B > C) = 7/12 and P(C > A) = 25/36.

It is true to say the probabilities are at least 7/12. The optimum set of three
non-transitive dice would have probabilities of at least 0.618 (golden ratio
conjugate).

(2010-05-24 00:41:44) Gavin Black said:

Interesting J. Siehler, there does seem that there may be a pattern to the
optimal dice sets. One of these years I'll have to generalize it to n-sided
dice and see what it comes up with.

(2010-05-11 17:37:38) J. Siehler said:

Ah, I just noticed that all three sum to 100! That's a nice bonus.

(2010-05-11 17:36:30) J. Siehler said:

I modified your program to search for interesting triples of 8-sided dice, and
came up with a unique set with A > B > C > A and a 39/64 probability in each
case. (There are three other solutions in which all three probabilities are >=
39/64). It is a theorem that at least one of the probabilities must be less
than (\sqrt{5}-1)/2 so it would be impossible to get all three probabilities >=
40/64. Here's the nice one:

A={1,2,3,16,18,19,20,21},
B={8,10,11,12,13,14,15,17} and
C={4,5,6,7,9,22,23,24},

(2010-04-06 14:02:53) Gavin Black said:

Em they are transitive since:

A beats C with a 20 / 36 chance
C beats B with a 28 / 36 chance
B beats A with a 21 / 36 chance

e.g. A > C > B > A

(2010-04-05 18:07:03) Em said:

Aeron, I think those dice are Transitive!!!
(C doesn't beat A the majority of the time)

(2010-03-22 01:18:00) Gavin said:

Thanks for the grammar catch, updated the post.

(2010-03-18 21:01:43) Tracy Hall said:

Nice work. I wondered whether it was possible to get better than the
usually-cited 5/9 probability, and this does better by 1/36. I also wondered
whether anyone had bothered to write the simple program that would examine all
possibilities.

Many mice but one mouse; many dice but one die. So actually it would read "at
least one die".

(2009-12-14 03:24:10) Gavin Black said:

You are correct, thanks for the catch. I updated it to say at least one dice in
a given optimal set has a sum of 57.

(2009-11-24 12:10:57) Aeron said:

(1,10,11,12,13,14)(2,3,4,15,16,17)(5,6,7,8,9,18)

Sum up as 61,57,53.

Add your comment:

Name:

Captcha) 31 - nothing + 5 =

Hardware

Math

Woodwork

Other

- Galvanic Etching Of Brass
Search

projects

no problem can withstand the assault of sustained thinking