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