Monday, January 21, 2013

Nontransitive Dice

Algorithm for finding all triplets of 6-sided 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)
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.

Source Code

https://github.com/plurSKI/diceFinder

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


For posterity's sake all the comments from my old site:

Sergio Giro said (2010-10-25 02:47:26):
Thanks for the pointer, I'll take a look.

While Googling, I found that the theorem referenced is in
http://www.jstor.org/pss/2974903, which derives it straighforwardly from the
Steinhaus-Trybula paradox (as far as I could see from the first page).

It's a pity that a lot of related papers are in old journals for which I don't
have electronic subscription, for instance:

H. STEINHAUS AND S. TRYBULA, On a paradox in applied probability

Thanks again

Gavin Black said (2010-10-25 02:47:00):
Sergio, there is a quick paper with some proofs available at:
http://www.edwardothorp.com/sitebuildercontent/sitebuilderfiles/nontransitivedic
e.doc

I would think types of proofs involving non-transitive sets would fall under the
category of combinatoric analysis. A good book or course in that subject would
probably give you the tools necessary to study it further.

Sergio Giro said (2010-10-25 02:46:38):
Hi,

I would like to read more about nontransitive dices, in particular (but not
exclusively) upper bounds for probabilities as, for instance, J. Siehler says
"It is a theorem that at least one of the probabilities must be less than
(\sqrt{5}-1)/2".

Any pointers will be greatly appreciated.

Best,
Sergio

Jim said (2010-10-25 02:46:10):
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).

Gavin Black said (2010-10-25 02:45:46):
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

J. Siehler said (2010-10-25 02:45:22):
Ah, I just noticed that all three sum to 100! That's a nice bonus.

J. Siehler said (2010-10-25 02:45:00):
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},

Gavin Black said (2010-10-25 02:44:35):
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

Em said (2010-10-25 02:44:07):
Aeron, I think those dice are Transitive!!!
(C doesn't beat A the majority of the time)

Gavin Black said (2010-10-25 02:43:44):
Thanks for the grammar catch, updated the post.

Tracy Hall said (2010-10-25 02:43:08):
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".

Gavin Black said (2010-10-25 02:42:37):
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.

Aeron said (2010-10-25 02:42:19):
(1,10,11,12,13,14)(2,3,4,15,16,17)(5,6,7,8,9,18)

Sum up as 61,57,53.
 

No comments: