A note on nontransitive dice

I am taking a course called Constraint Logic Programming this year. In this course we have a programming project to do. This year’s project is around non-transitive dice. I am a bit interested in the mathematics inside, so I did some research on this stuff. I found that many constraint programming models for nontransitive dice a bit too simple-minded. I found a new model for nontransitive dice that runs faster (at least on my box with gnu-prolog!). I would like to share it in the form of a readme.txt file I sent with my code to the prof. I also have a conjecture on nontransitive dice with highest winning probability.

Chinese reader may want to wait for the next post, roughly a Chinese version of this one.

* Begin of readme.txt

Gnu-Prolog Searcher of non-transitive dice
For Project of MPRI course “Constraint Logic Programming”
Author: fwjmath

========Content========
0. Convention
1. Usage
2. Explanation of check_dice/1
3. Constraint model of dice/3 and maxdice/3
4. Miscellaneous and extra (better) predicates
=======================

————-
0. Convention
————-

To make this file shorter, we adopt the abbreviation of “non-transitive dice” as “NTD”.

For a NTD set L, we note p(L) its winning probability. For two dice D1, D2, we note p(D1, D2) the probability that D1 wins D2.

——–
1. Usage
——–

The file dice.pl contains a piece of Gnu-Prolog that checks if a list represents a NTD set, finds a NTD set, and also finds such a NTD set with winning probability maximized.

There are 3 principle predicates in this piece of code.

– check_dice(L) checks if L represents a NTD set. L should be a list of list, each elements represents a die, as a list of face values of this die. When it succeeds, it prints the winning probability of this list, in rational form and in decimal form.

– dice(N,S,L) produces as L a NTD set of N dices all with S faces. When it succeeds, it also prints the winning probability of L, in rational form and in decimal form.

– maxdice(N,S,L) is the same with dice(N,S,L) with the winning probability maximized.

——————————
2. Explanation of check_dice/1
——————————

The predicate check_dice/1 is a translation of the definition of NTD in Gnu-Prolog. Please see comments in the code for details.

——————————————-
3. Constraint model of dice/3 and maxdice/3
——————————————-

To explain how dice/3 and maxdice/3 works, we start by the constraint model of NTD they rely on. We will first discuss a model for finding NTD set L of N dice with S faces with p(L) maximized.

We suppose that in a NTD set, faces are of integral value. Otherwise it can be rectified by ordering all face values then giving faces integral values with respect to this order.

In a NTD set, there may be faces with equal values K. We can differentiate these faces by giving distinct real values between K and K+1 to them. We can then rectify them back to integral value. It is clear that this operation only increases the winning probability. Therefore, we can suppose that each face of each die has different integral value from 1 to N*S.

Therefore, a NTD set L can be seen as a labeling l : [1..N*S] -> [1..N] of integers [1..N*S] with labels of integers [1..N], with the constraint that there are exact S integers with the same label. We now consider how to break symmetries.

For each die D in a NTD set L, there is a die D’ that wins D with highest probability. We can obtain a digraph from this relation: for each such D and D’, we add an edge from D’ to D. Ties are broken arbitrarily. This digraph has N nodes and N edges, and every node has in-degree 1. Every connected component has the form of a cycle with trees attached. Each edge (D,D’) corresponds to the probability p(D’, D) that D’ wins D.

It is easy to show that we can insert a die into a cycle without lowering the whole winning probability. Let D1 and D2 be two dice in the cycle with D1 pointing to D2. The probability that D1 wins D2 depends only on the relative order of face values of D1 and D2. We suppose that, from small to large, there are a_0 face values of D1, then b_0 face values of D2, then a_1 values of D1, etc. D1 wins D2 with probability:

p(D1, D2) = p((a_i), (b_i)) = (a_0 * b_0 + (a_0 + a_1) * b_1 + (a_0 + a_1 + a_2) * b_2 + …) / S^2

It is easy to show that p((a_i), (a_j)) + p((b_i), (b_j)) >= 2p((a_i), (b_j)), therefore, we can always inserts a die D between D1 and D2 corresponding to (c_i) equal to (a_i) or (b_i) such that p(D1, D) >= p((a_i), (b_j)) = p(D1, D2) and also p(D1, D) >= p(D1, D2). The whole probability does not decrease through this operation.

Therefore, in the NTD set L, we can just eliminate every die other than the cycle with highest winning probability, then insert all these dice back into this cycle. The graph is now a cycle, and p(L) does not decrease. To break the symmetry introduced by this operation, we can suppose that in L = {D_1, D_2, …, D_N}, we have D_{i+1} wins D_i, and D_1 wins D_N, and we can consider the winning probabilities between these pairs only.

Now we are back to the labeling representation l of L. For any n, if l(n) + 1 = l(n+1) mod N, by exchanging labels of n and n+1, p(L) does not decrease, since die (l(n)+1 mod N) wins more. If l(n) + 1 != l(n+1) mod N, exchanging them does not change p(L), then we will exchange them when l(n) > l(n+1). After this operation, the sequence l(1), l(2), …, l(N*S) is of form c_{1,0} 1s, c_{2,0} 2s, …, c_{N,0} Ns, c_{1,1} 1s, c_{2,1} 2s, etc. Therefore, to break the symmetry introduced by these two operations, we can suppose that l is of this form, and represent l by the bidimensional array (c_{i,j}), with \sum_j c_{i,j} = S for all i. We call this condition the summation condition.

We can see that, if c_{i,j} = 0, replacing c_{i-1,j} by 0 and c_{i-1,j+1} by c_{i-1,j} + c_{i-1,j+1} does not lower p(L). Similarly, if c_{i,j} = 0, replacing c_{i+1,j} by 0 and c_{i+1,j-1} by c_{i+1,j} + c_{i+1,j-1} does not lower p(L). Therefore, to break the symmetry introduced by these two operations, we can suppose that non-zero entries of (c_{i,j}) appears all consecutively in the order c_{1,0}, c_{2,0}, …, c_{N,0}, c_{1,1}, c_{1,2}, etc. We call this condition the helix condition.

We finally arrive to the model used in this piece of code. We represent L as (c_{i,j}) with 1 <= i <= N, 1 <= j <= S, since for a fixed i there can be at most S entries c_{i,j} > 0. Each die D_i is the list [c_{i,1}, c_{i,2}, …, c_{i,S}], and L is a list of these lists of dice. We then impose the helix condition and the summation condition onto these lists of dice as constraints, and use the finite domain solver to solve for maximum winning probability.

This is roughly the method used in this piece of code. Some extra constraints are also put in to improve solving efficiency. The model for finding NTD set maximizing winning condition can also be used as a model for finding arbitrary NTD set. Experiments show that this model is much more efficient than a much more naive model I implemented previously.

———————————————-
4. Miscellaneous and extra (better) predicates
———————————————-

Using maxdice(4,6,L), we rediscover Efron’s dice as a NTD set with maximal winning probability in less than 30s on an Intel Atom N450 @ 1.66GHz.

In testing, I observe a strange phenomenon in the result of maxdice. In the result of maxdice, each die consists of at most 3 different face values. I conjecture that imposing such a constraint does not change the solvability of this problem, and furthermore, it does not decreases the maximal winning probability. However, I cannot prove it.

To test this hypothesis, there are two predicates: dice_fake/3 and maxdice_fake/3. In these two predicates, the constraint that each die consists of at most 3 different face values is imposed. Existence of solution in dice_fake/3 and correctness of maxdice_fake/3 are not proved. However, in experiment, they always seem to succeed correctly, and much more efficient than the ones provided and proved previously. For example, on the same machine, maxdice_fake(4,6,L) rediscovers Efron’s dice in less than 1s; while dice(20,20,L) gives a resource error, dice_fake(20,20,L) succeeds in under 12s.

These “fake” predicates can be used as a pre-solver of the proved predicates. This is particularly useful for the predicate dice/3. However, for maxdice/3, since it has to search for the whole space, this may not be as useful as in the case of dice/3. But a certain boost can still be expected. The proved predicates boosted by “fake” predicates are called dice_boost/3 and maxdice_boost/3. In experiment, they are more efficient than dice/3 and maxdice/3, while the correctness is still assured. They can be seen as some kind of heuristic-guided search.

* End of readme.txt

As a sidenote, in fact the existence of NTD set in which each die consists of at most 3 different face values is easy to prove. Following the reasoning, we only need to construct a NTD set with 3 dice of s faces.

For s=2k+1>3, this is given by [c_{1,1}=1, c_{1,2}=2k], [c_{2,1}=k+1, c_{2,2}=k], [c_{3,1}=2k, c_{3,2}=1].

For s=2k>2, this is given by [c_{1,1}=1, c_{1,2}=2k-1], [c_{2,1}=k, c_{2,2}=k], [c_{3,1}=2k-1, c_{3,2}=1].

The case s=3 is trivial.

Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s