---
# System prepended metadata

title: Projet IA02 P21

---

# Projet IA02 P21
## Groupe 61 
## GHARBI Wassim MABILLE Lucas

## Lancement

Notre programme python se lance simplement à son appel : 
```bash=
C:\Users\Wass\Documents\UTC\GI02\IA02\projet-ia02>python3 .\generate_rules.py
```

Il n'a pas d'argument pour l'instant

## Explication

Voici le déroulé:
* Connexion au serveur
* Jusqu'à ce qu'il n'y plus de grille:
    * demande d'une grille
    * Creation de CNF pour que une case n'ait que exactement une grille
    * Jouer l'action suivante selon les reponses du serveur

## Decision de l'action suivante

On dispose de deux liste partagées par les fonctions:
*    next_guess : Case dont on est certain de l'animal (gophersat)
*    next_discover : Case qui n'est que un terrain (land) ou de la mer (sea) (gophersat)
*    unknown : Case dont on a pas d'information et voisine d'une case dont le prox_count a été pris en compte, ce sont les cases avec des points d'interrogations et dont on connait la nature (sea ou land)

Ces listes sont mises à jour à différentes parties du code.


Pour notre algorithme, nous avons décidé de jouer toutes les cases dont nous étions sûr de l'état avant d'essayer d'en déduire des nouvelles

Chaque requete au serveur provoque le traitement de la réponse correspondant afin d'ajouter les infos supplémentaires dans notre base de clauses

Une fois la réponse du serveur reçu:
* Si nos deux listes ,next_guess et next_discover, ne sont pas vide:
    * On continue de les vider en effectuant des guess et des discovers auprès du serveur
* Sinon:
    * On essaie de déduire grâce au solveur (on adapte le fichier DIMACS en fonction de ce qu'on cherche) de nouvelles cases à ajouter à nos listes next_guess et next_discover 
    * Si on ne trouve pas de dédutions on joue au hasard

Cet algorithme boucle jusqu'à ce que le serveur nous indique que la grille est gagnée ou perdue


## Construction de la base de clauses

Pour l'instant, nous avons implémenté 2 types de constructions:
* Les CNF "uniques" 
* Les CNF "prox_count"

Pour les règles uniques, c'est sensiblement identique à celle du TP avec le Soduku

Pou les règles "prox_count", on construit des CNF  pour chaque case selon les valeurs prox_count. Pour se faire, plusieurs stratégies ont été tenté

### Par implications
    
En sachant qu'une case possède k animal voisins, on arrive à cette forme:
    Soit L la liste des variables des voisins correspondant à l'animal
    Pour chaque combinaisons de C de taille k :
        [Ci] <--> non[Variable pas dans Ci]
        [Ci] <--> [Di]
    On lie chaque implication par des ET
    On simplifie ensuite chaque implication et on developpement pour faire ressortie des CNF
    
Pour Chaque implication, on retrouve ce modele:
* Elle se décompose en taille(L) CNF
    * k CNF de format : non[Ci] OU [Di][j]
    * (Taille(L) - k) CNF de format : non[Di] OU [Ci][j]

Au fur et à mesure, qu'on décompose en CNF les implicatons, on les développe avec la suivaite traité

### Par developpement de OU

Avec itertools, on calcule toutes les possibilités  que l'ou lie avec des OU. On developpe ensuite pour avoir un format CNF

### Adaptation de UNIQUE

Pour ne pas avoir à développer les OU, j'ai tenté d'adapter la fonction unique à une liste de CNF relié par des OU pour leur redonner le format CNF


Une fonction générale permet de traiter toutes les types d'infos que l'on peut recevoir (avec ou sans prox_count, animal)


## Modification pour la soutenance

Le jour de la soutenance, nous avons fait un confusion stupide. Pour les CNF "prox_count", nous avons lié les doubles implications avec des OU ou lieu de le faire avec des ET. (TD avec les filles du roi)

Malgré cela, il restait encore quelques problèmes. On a donc recommencé la conception logique : avec des at_most et at_least.



Apres cela, tout fonctionnait. Enfin notamment avec les grilles d'exemples sans crocodile.


Nous nous sommes rendu compte qu'il y avait un problème avec les regles CNF pour les nombres de voisins Crocodile : on generait des regles impossible à satisfaire. Donc notre algo déduisait tout (fonction search_deduction) car initialement la base de regles n'était pas cohérentes. 

Ainsi, on arrive à resoudre les cartes uniquement si on a pas de crocodile dans la grille.

Nous avons tenté d'arranger la chose en supprimant les regles impossibles de la BDC mais le programme était devenu bien trop long.

Notre difficulté a du à notre logique initial avec les variables propostionnelles. Il y a deux variable pour les croco (croco_land et croco_sea). Lors de la génération de combinaisons, certaines était donc insatisfiable

Le code est commenté de manière à comprendre notre logique



