# Programming Project

## 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.

The project is to program:

first in pure Prolog (GNU Prolog without any

`fd_`

predicate) 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 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.