Cyclic Dice Programming Project

Tue, Sep 12, 2017 Prolog

Subject

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 5/9
  • b beats c with probability 5/9
  • c beats a with probability 5/9

Such a set of dice is said to be nontransitive (the relation “beats with probability > 1/2” is not transitive). See Wikipedia for a longer description. In this project we will restrict ourselves to the case where the set is actually a cycle.

The project is to program:

  • first in pure Prolog (SWI Prolog without the clpfd library) a predicate able to check whether a sequence of dice is cyclic (each dice beats the following one) and printing the corresponding probabilities;

  • then, using Finite Domains constraints, a generator of cyclic dice sequences;

  • and finally a predicate finding a cyclic dice sequence for which the probability p such that for any die a in the set, it beat its successor b in the sequence, 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.

Programming Project Efron dice