Programming Project

Subject – Cyclic dice

Consider a set of three dice, a, b and c such that

  • die a has sides {2, 2, 4, 4, 9, 9}
  • die b has sides {1, 1, 6, 6, 8, 8}
  • die c has sides {3, 3, 5, 5, 7, 7}

Then:

  • a beats b with probability 59
  • b beats c with probability 59
  • c beats a with probability 59

Such a set of dice is said to be nontransitive (the relation “beats with probability > 12” is not transitive). See Wikipedia for a longer description.

The project is to program:

  • first in pure Prolog (SWI Prolog without the clpfd library) a predicate able to check whether a set of dice is nontransitive and printing the corresponding probabilities;

  • then, using Finite Domains constraints, a generator of nontransitive dice set;

  • and finally a predicate finding a nontransitive dice set for which the probability p such that for any die a in the set, there exists a die b in the set which beats a with probability higher than p is (proven) maximal.

Project content

The result of the project should be an SWI Prolog file with commented code for the three parts and a short text file providing indications on the use of the program and its results.

The main content of the first part should be a predicate check_dice/1 taking as arguments a list of dice, each die being represented as a list of sides. This predicate should succeed and print out the probabilities on nontransitive sets and fail otherwise. For instance, the query check_dice([[2, 2, 4, 4, 9, 9], [1, 1, 6, 6, 8, 8], [3, 3, 5, 5, 7, 7]]). should succeed, whereas check_dice([[1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6]]). fails. The predicate should succeed for any number of sides, not just 6, and for sorted or non-sorted sides’ lists.

In the second part, one should provide a predicate dice/3 such that dice(N, S, L) generates a list L of N dice of S sides (with the same format as above) in a very short time. It is worth thinking about the domain to use for the values of sides.

In the third part, the same predicate will be modified in order to maximize the probability p. Note that it is worth thinking about the symmetries of the model and how to break them.

The time necessary to carry out this work should be from 30 min if you’re a seasoned Prolog programmer to 20 hours maximum if you need to get used to Prolog, CLP, etc.

The two files have to reach Sylvain.Soliman@inria.fr before October 8th, 11:30:00 PM CET (late submissions will be dismissed, and since e-mail is not reliable, it seems better to send your project before the deadline and to wait for a confirmation).

Any question about the project should be sent to Sylvain.Soliman@inria.fr, any thanks should go to Thierry.Martinez@inria.fr for the inspiration and first draft of this project.