# IA02 Projet

## Question à poser ?
- **On lance le code chez nous ou le prof le lancera depuis sa machine le jour du final ?**
- le prof va donner les informations dans la partie API de sujet cette semaine
- **Au lancement du jeu comment limiter le hasard puisque nous n'avons aucune information qui nous permet de déduire quoique ce soit**
- est ce que les voisins de la cellule de départ sont sans danger ou pas ?
- normalement ce n'est pas le cas, il peut y avoir des bombes dans les voisins donc le 1er coup est fait au hasard
- mon prof m'a conseillé d'utiliser l'indice 3BV pour réduire le hasard, pour choisir la solution la plus probable

- si ce n'est pas sans danger est ce que nous avons un nombre de vies pour ne pas perdre dès le 1er discover.
- normalement ce ne sera pas le cas

- ** Gérer le hasard ?**
- mon prof m'a conseillé d'utiliser l'indice 3BV pour réduire le hasard, pour choisir la solution la plus probable

- **Confirmer le rôle de chacune des fonctions (discover, guess, chord)**
- le prof va normalement donner cette semaine un exemple de déroulement du jeu

- **Temps moyen de résolution : temps en secondes ou le temps en nombre d'appel de fonctions**
- les deux, le prof rééquilibrera si notre connexion est instable

- **Comment représenter le nombre d'animaux en logique ? (CNF)**
- il faut faire des unique() puissance p pour obtenir une cardinalité
- Exemple avec deux éléments vrai
- P1 P2 P3
- non P1 -> P3 et P2
- P1 ou (P2 et P3)
- **P1 ou P1 et P1 ou P3**
- non P2 -> P2 et P3
- etc....
- Au total on aura 6 clauses je crois après simplification

- la réponse du prof ressemble bcq à ce que l'on avait vu hier je crois sur ce site : https://pwmarcz.pl/blog/kaboom/

- Il s'agit du type de unique que l'on a fait pour le sudoku sauf que les unique du sudoku était de puissance 1 cad on a 1 seul élément vrai alors que dans notre unique ici on peut avoir des unique puissance k avec k éléments vrai
- Cela ressemble aussi au codage de la coloration des graphes

- cela va engendrer une explosion des clauses mais ce n'est pas un problème en soit
- on pourra essayer de les minimiser (il existe un technique)

- **Comment exploiter l'information ternaire ?**
- mon prof attend des informations

## Ressources

### Cardinalité

Minesweeper in CNF (Berkeley University)
https://people.eecs.berkeley.edu/~daw/teaching/cs70-s05/Notes/lecture09.pdf

Minesweeper in CNF (Duke University)
https://courses.cs.duke.edu/cps102/spring05/notes/minesweeper.pdf

Efficient CNF encoding of Boolean cardinality constraints
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.458.7676&rep=rep1&type=pdf

Towards an Optimal CNF Encoding ofBoolean Cardinality Constraints
https://www.carstensinz.de/techreports/CardConstraints.pdf

Kaboom: an unusual Minesweeper
https://pwmarcz.pl/blog/kaboom/

Idea to optimize bruteforce
https://dev.to/krlove/creating-advanced-minesweeper-solver-using-logic-programming-2ppd

Idee de cardinalité:
https://sat-smt.codes/current_tree/equations/minesweeper/2_SAT/

Docu wolfram
https://reference.wolfram.com/language/guide/ConvertingBetweenExpressionsAndStrings.html

## Variables

On a donc cela : m * n * 4

Chaque cellule:
- Type d'env: terrestre ou aquatique.
- **ATTENTION on peut réduire aquatique à "non terre"**
- Type d'animal: tigres, requins, crocodiles

**On a donc au total 4 variables**

## Contraintes

Chaque cellule:
- Env : **atleast** (t ou a) et **atmost** (non t ou non a)
- **changer cela en conséquence**
- Animaux :
- atmost

           (non tr ou non r)
        et (non tr ou non c)
        et (non r ou non c)

- tigre que sur la terre

        non (a et tr)
        => non a ou non tr

- requin que dans l'eau

        non (t et r)
        => non t ou non r

- crocodile dans l'eau et sur terre

        pas de contrainte supplémentaire
        

## Règles

1. Une case est soit de type terrestre, soit de type aquatique.

2. On rencontre parfois des animaux dangereux : des tigres, des requins, et des crocodiles.

3. Les tigres vivent sur la terre ferme, les requins vivent dans l’eau, et les crocodiles sont capables de vivre sur ces 2 habitats.

4. Sur une même case, il ne peut y avoir qu’un seul animal.

5. Au départ est donné m, n, le nombre de tigres, le nombre de requins et le nombre de crocodiles, le nombre de terre et le nombre de mer et d’éventuelles statistiques sur la difficulté de la carte (ex. l’indice 3BV).

6. Pour limiter le hasard, une case de départ, sans danger, est également donnée.

7. Trois actions sont possibles : découvrir une tuile (discover), deviner un tigre, deviner un requin et deviner un crocodile (guess) et enfin de découvrir en une fois l’ensemble des cases non découvertes autour d’une case dont tous les animaux ont déjà été trouvés (chord).

- guess (cord x, cord y, type d'animaux)

8. Pour chaque case découverte, on aura un triplet représentant le nombre de tigres, de requins et de crocodiles ainsi que le type de la case. Si une case n’est entourée d’aucun animal, toutes ses cases adjacentes seront automatiquement découvertes (et ainsi de suite récursivement).

9. Toute erreur (par exemple un mauvais guess) entraîne la mort de l’explorateur et la fin de la carte.

10. La carte est gagnée lorque toutes les cases libres ont été découvertes et les animaux devinés correctment.

11. Lors d’une découverte de tuile, si tout s’est bien passé, vous êtes informés du type de terrain des cases adjacentes.

12. Lors d’une devinette, si celle-ci est juste, vous êtes informés du type de terrain de la case devinée.

## Pseudo Algo

discover() la case de départ

[
    [0000000000?000000],
    [00000?00000000000],
]

boucle jusqua fini:
    - transforme la grille actuelle => dimacs (t ou r ou c)
    - trouver les cellules à vérifier (les voisins des cellules découvertes)
    - Diviser en groupe
    
    - Pour chaque groupe:
        - Pour chaque combinaisons possibles:
            - Ajouter des CNFs correspondants
            - Lancer solveur
            [1] [2] [3]   [4] [5] [6]
            1    1   0    1    0   0
            0    1   1    0    1   1
            0    0   1    0    0   1
            1    1   1    1    0   1
            0    1   0    0    0   0
            
            2/5        prend =>1/5

## To do
- trouver une méthode pour coder les variables (cf s' inspirer du sudoku)
- mettre en place les contraintes
- commencer à modéliser la notion de hasard