---
tags: projet, SAT, démineur
---

[IA02] Projet Crocomine : les tigres 🐅, les requins 🦈 et les crocodiles 🐊
=================================================================

| Information | Valeur |
| :------------ | :------------- |
| **Auteurs** | Sylvain Lagrue ([[e-mail]](mailto:[e-mail]))|
| | Khaled Belahcene ([e-mail]) |
| **Licence** | Creative Common [CC BY-SA 3.0](https://creativecommons.org/licenses/by-sa/3.0) |
| **Version document** | 1.2.3 |

<span style="font-size: 10rem">🐅 🦈 🐊</span>

## 0. Historique du document

- 16/06/2011 (1.2.4) : changement du status quand il n'y a plus de carte
- 11/06/2021 (1.2.3) : ajout d'une section Mise à disposition de ressources
- 07/06/2021 (1.2.2) : ajout s'une section FAQ
- 31/05/2001 (1.2.1) : changement de nom `proxCount` -> `prox_count` dans le format de `Info`
- 31/05/2001 (1.2.0) : ajout des règles 11 et 12 + précision pour la règle 9
- 31/05/2001 (1.1.0) : première version de l'API
- 25/05/2021 (1.0.0) : version initiale du document

## 1. Présentation du projet

### Règles du jeu

On considère un monde 2D sous forme de grille de taille $m×n$ ($m$ lignes et $n$ colonnes). Les bords ne sont pas connectés.

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

## Exemple de monde


## 2. En pratique

### Travail demandé

On demande de réaliser un joueur artificiel capable de communiquer avec un serveur de jeu, de lui communiquer ses coups et de prendre en compte les informations fournies en retour, de manière à deviner l'emplacement de tous les animaux et de découvrir toutes les autres cases.

Il est très fortement suggéré d'utiliser un solveur SAT piloté à l'aide d'un programme écrit en Python. La partie réseau sera fournie.

### Contraintes

- Les étudiants sont organisés par binômes, sous le régime de la *communauté* (de la gloire comme de l'infamie). Il est fortement recommandé que les membres d'un même binôme partagent le même groupe de TP, afin de profiter au mieux de ces séances.
- Vous devez partager avec vos enseignants (rôle *reporter*) de TP le projet gitlab UTC **privé** avec des commits réguliers.
- Toute triche détectée (récupération de code sur Internet, plagiat, etc.), sera sanctionnée au mieux d'un 0 au projet (et donc de la perte de l'UV).
- Néanmoins, il est possible de trouver des techniques sur Internet, de discuter entre vous, etc.

### Évaluation

Différents classements seront proposés. Par exemple :

- Plus longue série de victoire (*streak*)
- Nombre total/moyen de cases/tigres/requins/crocodiles bien découverts
- Temps moyen de résolution
- Classements par taille/difficulté
- etc.

Ces différents classements rentrent en compte dans l'évaluation, avec une incidence beaucoup plus forte sur ceux se focalisant sur des incides de qualité.

## 3. API

*Work in progress*

### Les types de base

Status: str # "OK"|"KO"|"Err"|"GG"

- `"OK"` : l'action s'est bien passée
- `"KO"` : l'action s'est mal passée, vous avez perdu
- `"Err"` : l'action que vous demandez ne peut être réalisée
- `"GG"` : l'action s'est bien passée et vous avez fini la grille

Msg: str

Info: {
    "pos": [int, int], # (i, j) i < M, j < N 
    "field": str # "sea"|"land"
    "prox_count": (int, int, int) # (tiger_count, shark_count, croco_count), optional
}

Infos = List[info]

GridInfos: {
    "m": int,
    "n": int,
    "start": [int, int],
    "tiger_count": int,
    "shark_count": int,
    "croco_count": int,
    "sea_count": int,
    "land_count": int,
    "3BV": int,
    "infos": Infos # Optional
    
}

### Les actions

#### Demande une nouvelle grille/grille suivante

def new_grid() -> Status, Msg, GridInfos

Certaines informations sur certaines cases peuvent être données.

S'il n'y a plus de grille, le status est `Err`.

#### Découverte

def discover(i: int, j:int) -> Status, Msg, Infos

Si la case est un `(0,0,0)` (c.-à-d. pas de tigre, pas de requin et pas de crocodile),toutes les cases vides sont récursivement découverte et leur type donné. Dans tous les cas, le type de terrain de la case découverte est donné.

#### Deviner

def guess(i: int, j:int, animal: str) -> Status, Msg, Infos

`animal` est à choisir parmi `"T"`, `"S"`, `"C"` pour respectivement tigre, requin et crocodile.

Si le guess est faux, la grille est perdue. Sinon, le type de terrain de la case `(i,j)` est toujours donné.

#### Accord (facultatif)

def chord(i: int,j: int) -> Status, Msg, Infos

Fait un discover sur l'ensemble des cases contingentes qui n'ont pas été découvertes autour de `(i,j)`. Ne compte que pour une seule action.

### Exemple

*Work in progress*

## FAQ

### Quelle architecture pour le programme ?

* Vous devez réaliser un logiciel qui représente un joueur artificiel dialoguant avec un environnement artificiel via le réseau. Les composants liés à la communication (entrée et sortie) vous seront fournis.
* Concentrez-vous sur la réalisation du joueur artificiel. Représentez les règles du jeu et votre base de connaissances comme il vous convient. La traduction en entrée et en sortie depuis ou vers l’environnement artificiel peuvent être traités ensuite.
* N’hésitez pas à faire un usage abondant de la structure de dictionnaire, qui est à la fois souple et efficace en python.
* Pour convertir un problème SAT au format DIMACS, l’usage de dictionnaires pour convertir les variables propositionnelles en entier et réciproquement s’avère particulièrement pertinent (cf TP 2 et 3)
* Votre joueur pourra faire appel à un solveur SAT – on vous a fourni lors du TP 2 un exécutable de Gophersat, et lors du TP 3 une interface (sommaire) en Python vous permettant de dialoguer avec ce programme externe. Bien entendu, la modélisation du problème, l’encodage au format DIMACS, et le décodage de la réponse du solveur sont à votre charge.
* Les cartes typiques seront de taille inférieure à 1000 cases, mais certaines cartes seront grandes, par exemple 50x50. Assurez-vous que votre programme tienne la charge face à de tels mondes, quitte à prévoir une approche plus simple (voire simpliste) dans ce cas.

### Conseils pour la modélisation logique
* En ce qui concerne la modélisation, vous pourriez vouloir employer des contraintes du type « au plus $k$ variables parmi $x_1, …, x_n$ » ou « au moins $k$ variables parmi $x_1, …, x_n$ ». Nous avons traité en CM, TD et TP les cas $k = 0$, $k = 1$ et $k = 2$. Pour prendre en compte de plus grandes valeurs de $k$, il est possible de faire appel à la fonction `combinations` du module `itertools`…
* Il se peut que vous vous retrouviez dans une situation où vous ne parvenez à faire aucune déduction. Nous vous recommandons de vous munir d’un trèfle à quatre feuilles ou d’un fer à cheval avant de choisir votre prochaine action.

### Quelques précisions concernant nos attentes
* Nous évaluerons, à travers votre programme, votre niveau d’appropriation et de maîtrises des techniques et concepts vus en cours, TD et TP. Il n’est donc ni nécessaire, ni suffisant de réaliser un joueur excellent pour obtenir une bonne note.
* Ce n’est pas grave si vous ne faites pas toutes les cartes ! Personne ne pourra faire toutes les cartes, on veut des carte bien faites, pas des cartes bâclées.
* En particulier, nous attendons que vous fournissiez un joueur capable de jouer sur une carte 15x15 en un temps raisonnable sans commettre d’erreur grossière. Les raffinements, qui peuvent par exemple concerner la capacité à jouer rapidement, à prendre en compte l’information globale (en particulier, la proportion d’animaux par rapport à la taille du terrain), ou à adopter une stratégie sophistiquée lorsque la déduction est mise en défaut, constituent des bonus appréciés

## Mise à disposition de ressources (serveur, client et cartes)

* Crocomine est organisé suivant une architecture client-serveur. La partie qui vous incombe, le *joueur*, se situe côté client. Le jour de la soutenance, votre joueur se connectera via internet au serveur que nous aurons mis en place. En attendant, nous vous fournissons une version minimale du serveur, qui a vocation à être exécutée localement sur votre machine, afin de tester votre joueur.
* Le programme créant le serveur est disponible sur la page Moodle consacrée au projet, ainsi qu’un fichier contenant des cartes au format .croco et un script python permettant à un client de dialoguer avec le serveur (envoyer des requêtes *discover*, *guess* ou *chord*, et décoder les réponses du serveur).
* Il est recommandé que vous créiez un répertoire ``projet``, contenant des sous-répertoires ``projet/client/``, ``projet/serveur/bin/`` et ``projet/serveur/cartes/``.
* Le programme du serveur doit être lancé **avant** le client, depuis un processus/une fenêtre dédiée qui sera fermé(e) pour y mettre fin, via la ligne de commande. Sous Windows, la commande ``.\serveur\bin\crocomine-lite-beta3.exe`` doit être suivie de 2 arguments : le 1e indique le port de communication, par exemple ``:8000``, le 2e l’emplacement des cartes – par exemple ``.\serveur\cartes\``, ce qui donne:
``\projet> .\serveur\bin\crocomine-lite-beta3.exe ":8000" .\serveur\cartes\``
A la première éxécution, vous devriez recevoir une demande d'autorisation pour le pare-feu.
* Vous pouvez ensuite exécuter le client (``\projet> python ./client/exemple.py``), ou bien récupérer le code de l'exemple, avec les importations de packages et l'intégrer à votre joueur. Assurez-vous d'avoir le package ``requests`` installé (via pip3 ou conda, ou autre).
* Les ressources mises à disposition sont fonctionnellement complètes, mais pourront être modifiées à la marge pour corriger des bugs. Vous pouvez créer vos propres cartes, et même les partager entre vous !