Nontransitive Dice

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 whose probabilities 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!

Interesting Sets

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)

Source Code

Conclusions

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.