Programming Project

Subject

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

Then:

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.

The project is to program:

Project content

The result of the project should be a Prolog file (GNU-Prolog-compatible) 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.

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 GNU Prolog programmer to 10 hours maximum if you need to get used to Prolog, CLP, etc.

The two files have to reach Sylvain.Soliman@inria.fr before January 20th, 04:59:59 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.