Available nodes

 Flood

Les jeux de flood-filling1 comme OpenFlood ou FloodIt se jouent sur un graphe connexe, où les sommets sont colorés avec un nombre fini de couleurs. Chaque joueur possède un sommet de départ, et contrôle l'ensemble connexe des sommets de la même couleur que son sommet de départ (ensemble possiblement réduit au seul sommet de départ). À chaque tour de jeu, il choisit une couleur, et recolorie tous les sommets de sa zone de contrôle avec cette nouvelle couleur, conquérant ainsi de nouveaux sommets. L'image suivante décrit une partie en cours sur une grille carrée:
(image tirée du jeu OpenFlood)

Selon les règles, le jeu peut se jouer seul, auquel cas l'objectif consiste à recouvrir le plateau en le moins de coups possible, soit à plusieurs, auquel cas il faut conquérir une certaine proportion du graphe de jeu sans conquérir les cases de l'adversaire. La version à un seul joueur a été largement étudiée, faisant en particulier l'objet d'un article par Clifford et. al. en 2012 prouvant que le calcul du nombre optimal de coups pour gagner sur une grille carrée était NP-difficile. Le problème a ensuite été considéré sur des familles de graphes plus larges, dans cet article. Plus récemment, un survey () rend compte de la richesse et de la difficulté du problème dans des familles de graphes plus larges. Alternativement, le jeu a aussi été analysé dans un article de Fleischer et. al. lui aussi de 2012 () dans sa version à plusieurs joueurs, montrant que sa résolution était PSPACE-complète.
L'objectif de ce projet va consister à mettre en place des stratégies pour jouer aussi efficacement que possible à la variante à plusieurs joueurs (appelée par la suite "Flood") dans la suite, et certaines de ses généralisations.

 Graphes de jeu

Dans cette section sont spécifiés le format des graphes pouvant servir de plateaux de jeu pour jouer à une partie de Flood. Pour la suite, on supposera que les deux joueurs sont représentés par les entiers 0 et 1. Les définitions des coups et des graphes utilisés devront se conformer aux interfaces color.h et graph.h suivantes. Il est demandé de ne pas modifier ces en-têtes.
Le graphe contient un nombre de sommets num_vertices (ou n pour simplifier). La matrice t est une matrice d'adjacence de taille n*n représentant les arêtes du graphe. Cette matrice est une matrice creuse de type gsl_spmatrix_uint défini dans la GNU Scientific Library (cf. la section dédiée pour plus de détails). Dans ce projet, les graphes sont supposés non dirigés.

L'ajout de fonctions supplémentaires à cette interface est naturellement autorisé, bien que recommandé dans un fichier différent.

Exemple de graphe avec sa coloration :
num_vertices = 4
t = [[ 0 1 1 0 ]
     [ 1 0 0 1 ]
     [ 1 0 0 1 ]
     [ 0 1 1 0 ]]

// Le tableau `colors` n'est pas dans le graphe
colors = [ RED BLUE BLUE GREEN ]

Le sujet propose de travailler sur 4 familles de graphes de formes différentes, avec des tailles variables. Le nombre m est spécifié sur la ligne de commande et permet de spécifier la largeur du graphe. Les positions de départ des deux joueurs sont indiquées sur les graphes, en bleu (joueur 0) et rouge (joueur 1). Il est évidemment possible de faire jouer sur d'autres graphes, mais tous les serveurs devront pouvoir jouer sur au minimum ces quatre familles.
Graphe carré c Graphe donut d, avec m multiple de 3 Graphe haché h, avec m multiple de 3 Graphe torique t

Chacun des graphes précédents doit, avant de commencer une partie, être coloré. Une coloration est une fonction attribuant à chaque sommet d'un graphe une couleur de type enum color_t, et vérifiant aussi les propriétés suivantes:
  • Les couleurs des sommets sont comprises entre 0 et MAX_COLOR-1 au sens large.
  • Les couleurs associées aux positions de démarrage des deux joueurs sont forcément différentes.
Il est demandé à ce que les colorations soient des fonctions qui puissent s'appliquer de manière générique à un graphe (et donc pas de colorations propres à un graphe fixe). Le sujet ne définit pas de colorations, mais il demande à ce qu'il en existe au moins deux, et il suggère:
  • une coloration cyclique en fonction du numéro des sommets
  • une coloration aléatoire
  • une coloration mettant en jeu des blocs de sommets colorés de la même couleur et connexes, de manière à réduire significativement le diamètre du graphe des couleurs. Par exemple dans la figure suivante des segments ont été tracés (en noir) pour créer artificiellement des "ponts" permettant de conquérir rapidement des sommets éloignés:
Chaque joueur reçoit au début de sa partie une liste de couleurs interdites qu'il n'a pas le droit de jouer. Chaque joueur possède le même nombre de couleurs interdites. Au delà de cette règle, cet ensemble de couleurs est laissé libre. En particulier il peut être vide, ou être le même que celui de son adversaire (ou pas). Évidemment, s'il contient trop de couleurs interdites, les parties risquent de se terminer très rapidement.

 Déroulement d'une partie

Les règles du jeu de Flood à deux joueurs sont décrites dans l' article cité en introduction. Mais comme le sujet se permet quelques libertés par rapport à cet article séminal (en particulier en choisissant d'élargir la famille de graphes possibles), on pose quelques principes généraux qui s'appliquent de manière générique:
  • Le joueur débutant la partie est décidé aléatoirement. Pour des raisons de test, il pourra être intéressant de pouvoir spécifier le premier joueur par une option de la ligne de commande.
  • Les couleurs des positions de départ des deux joueurs sont forcément différentes. Il s'agit d'une règle devant être assurée par le serveur pour respecter une partie valide.
  • Un joueur ne peut jamais prendre la couleur de l'autre joueur si, en faisant cela, il capturerait la position de départ de l'autre joueur. Il ne peut pas non plus jouer une de ses couleurs interdites.
  • Si un joueur joue une couleur valide (au sens de la règle précédente), celle-ci doit forcément lui faire gagner de nouvelles cases. En particulier, un joueur ne peut jamais prendre la couleur dont ses cases sont actuellement coloriées, et il doit forcément prendre une couleur adjacente à la zone qu'il contrôle.
  • Si il considère que c'est impossible ou contre son intérêt de jouer, un joueur peut décider de ne pas jouer de couleur (NO_COLOR), auquel cas on considère qu'il passe son tour.
  • La partie s'arrête une fois que les deux joueurs ont joué NO_COLOR à deux tours consécutifs. Le gagnant est celui qui contrôle le plus de cases. En cas d'égalité, la partie est déclarée nulle.
Si un joueur ne respecte pas les règles à son tour de jeu, il est immédiatement déclaré perdant, et son adversaire gagne la partie.

 Description du projet

L'objectif du projet consiste à implémenter un ensemble de fonctions permettant de faire jouer deux joueurs à une partie de Flood. Le code sera décomposé en deux parties distinctes :
  • Un ensemble de clients implémentant tous une interface commune, gérant leur propre plateau de jeu et jouant chacun selon leur objectif propre. Ces clients sont censés être automatiques : ils doivent décider d'un coup à jouer à l'aide d'un algorithme, sans intervention extérieure.
  • Un serveur de jeu organisant une partie, faisant jouer chaque client à son tour en lui envoyant les coups joués par son adversaire, enregistrant le coup du client à son tour et notifiant les clients de la fin de la partie.
Le serveur de jeu devra, par l'intermédiaire d'options (décrites dans la partie Détails techniques) permettre de sélectionner la forme du plateau (avec des graphes de tailles et de formes) et la façon de le colorer. La boucle de jeu devra suivre le pseudo-algorithme suivant :
start_player_id = random();
other_player_id = 1 - start_player_id
graph = // ...
graph_colors = // ...
forbidden_colors = // ...
for each player p
    p->initialize(p == start_player_id ? 0 : 1, graph,
                  graph_colors, forbidden_colors)
while true
   p = compute_next_player()
   move = p->play(move)
   if is_winning()
      break
for each player p
   p->finalize()
Exemple de début de partie :
sophy->initialize(0, graph, colors, forbidden)
david->initialize(1, graph, colors, forbidden)

sophy->play(NO_COLOR) // return BLUE
david->play(BLUE)     // return RED
sophy->play(RED)      // ...
Pour les besoins du jeu, le fichier player.h décrit l'interface à utiliser pour communiquer entre client et serveur.
#ifndef _FLOOD_PLAYER_H_
#define _FLOOD_PLAYER_H_

#include "color.h"
#include "graph.h"

/* Access to player informations
 * RETURNS:
 * - the player name as an [a-zA-Z0-9 -_]* string
 */
char const* get_player_name();

/* Player initialization
 * PARAM:
 * - id        : the id assigned to the player
 * - graph     : the graph where the game is played
 * PRECOND:
 * - `id` is either 0 or 1
 * - `graph` is a heap-allocated copy of the graph where the game is
 *   played, that must be freed in the end
 * - `colors` is a heap allocated copy array associating to each vertex
 *   id a color, that must be freed in the end
 * - `forbidden` is an array of color sets, one for each player,
 *   specifying the forbidden colors for each player (one per id)
 * - initialize has never been called before
 */
void initialize(size_t id, struct graph_t* graph,
                enum color_t* colors,
                struct color_set_t forbidden[NUM_PLAYERS]);

/* Computes next move
 * PARAM:
 * - previous_move: the move from the previous player. If this is the
 *   first move of the game, `previous_move` is equal to NO_COLOR.
 * RETURNS: - the next move for the player.
 */
struct move_t play(struct move_t previous_move);

/* Announces the end of the game to the player, and cleans up the
   memory he may have been using.
 * POSTCOND:
 * - every allocation done during the calls to initialize and play
 *   functions must have been freed
 */
void finalize();

#endif // _FLOOD_PLAYER_H_

Il est demandé de respecter les principes suivants :
  • Les différents clients doivent être interopérables entre équipes de projets. A cet effet, il est demandé que chaque client soit compilé sous la forme d'une bibliothèque partagée (option -shared de gcc) et chargeable de manière dynamique, en utilisant les fonctions de la famille dlopen, définies dans dlfcn.h. Il sera possible de s'inspirer des instructions données ici.
  • Il est demandé d'implémenter au moins deux clients différents en terme de stratégie utilisée.
  • Il est demandé de faire attention à éviter la duplication du code (en particulier pour les données du plateau de jeu). Remarquer que l'interface interdit toute communication dudit plateau entre client et serveur pendant la partie.

 Détails techniques

Pour les besoins du projet, les fichiers devront être organisés de la manière suivante dans le dépôt :
    /               -- Base directory
     Makefile       -- Global Makefile
    /src            -- Source files
    /install        -- Install directory (should be empty in the repository but for a .keep file)
Le fichier Makefile devra fournir :
  • une règle build qui compilera l'ensemble du code,
  • une règle test qui compilera les tests, sans les exécuter
  • une règle install qui copiera les exécutables (un exécutable nommé server, un exécutable alltests, et un nombre non spécifié de fichiers .so) à l'intérieur du répertoire désigné, et
  • une règle clean qui supprimera les fichiers compilés et installés.
Le Makefile doit pouvoir prendre une variable GSL_PATH qui indique le répertoire où est installée la bibliothèque libgsl.so. Par exemple :
GSL_PATH=/net/ens/renault/save/gsl-2.6/install make
Cette variable pourra prendre des valeurs différentes selon les machines sur lesquelles le code sera compilé (en particulier la forge). Il incombe à l'utilisateur du code (en particulier à la forge) de faire que les bibliothèques soient accessibles lors de l'exécution du programme. Par exemple :
LD_LIBRARY_PATH=/net/ens/renault/save/gsl-2.6/install/lib ./server -m 10
Le serveur devra charger l'ensemble de ses clients de manière dynamique en utilisant la syntaxe suivante :
./install/server -m [M] -t [T] -c [C] -a [A] -f [F] ./install/player1.so ./install/player2.so
  • L'option -m permet de spécifier la largeur du plateau de jeu (ex. -m 10).
  • L'option -t permet de spécifier la forme du plateau de jeu (grille carrée c, donut d, hachée h ou torique t ) (ex. -t h).
  • L'option -c permet de spécifier le nombre de couleurs utilisé dans la partie. Ce nombre est un entier compris entre 2 et MAX_COLOR (ex. -c 4 pour une partie à 4 couleurs).
  • L'option -a permet de spécifier l'algorithme de coloration utilisé. Il est demandé à ce que les algorithmes de coloration soient numérotés à partir de 0. (ex. -a 1 pour le 2nd algorithme de coloration).
  • L'option -f permet de spécifier le nombre de couleurs interdites pour chaque joueur. (ex. -f 1 pour 1 couleur interdite).
  • Les clients sont passés en paramètre dans un ordre quelconque par défaut.
  • Les paramètres optionnels doivent pouvoir être placés dans n'importe quel ordre sur la ligne de commande.
Le serveur doit afficher
uniquement du texte sur la sortie standard et potentiellement la sortie d'erreur. Aucune interaction avec l'utilisateur n'est censée se produire (en dehors des paramètres passés à la ligne de commande).

L'exécutable alltests doit être compilé avec -lgcov et exécuter tous les tests présents dans le code. En particulier, il servira d'outil de mesure de la couverture des tests avec gcov.

Tout exécutable ou autre fichier non indispensable au projet (fichiers temporaires, fichiers objets, fichiers de logs …) stocké à l'intérieur du dépôt verra la personne ayant initié le premier commit se voir infliger un blâme. De la même manière, après avoir exécuté la règle make install, le répertoire install doit contenir exactement deux (2) exécutables nommés server et alltests, et des clients sous la forme de bibliothèques partagées (fichiers .so).

 GSL

La GNU Scientific Library est une bibliothèque C et C++ permettant de faire des calculs numériques. Dans le cadre de ce sujet, elle fournit des implémentations de matrices denses et creuses, ainsi que des algorithmes de résolution de systèmes linéaires. Malheureusement, elle ne fournit pas d'algorithmes de graphes, ce qui laisse toute latitude pour les implémenter.
La version 2.6 est la version miminale pour compiler et exécuter le projet. Une version de cette bibliothèque est installée sur les machines de l'école dans le répertoire /net/ens/renault/save/gsl-2.6/install.
Pour créer une matrice creuse avec la GSL, il suffit de faire:
gsl_spmatrix_uint *mat = gsl_spmatrix_uint_alloc(n, n);
for (each edge from i to j)
     gsl_spmatrix_uint_set(mat, i, j, 1);
Ceci crée une matrice creuse d'entiers au format COO (Coordinate Storage). Comme les graphes considérés ont des degrés faibles, cette façon de faire permet de stocker efficacement leurs matrices d'ajacence. Mais, si on désire itérer sur les arêtes des graphes, il est nécessaire de faire:
// Loop over all pairs of vertices (n*n iterations)
for (unsigned int i = 0; i < mat->size1; i++) {
    for (unsigned int j = 0; j < mat->size2; j++) {
      if (gsl_spmatrix_uint_get(mat, i, j) == 1)    // Select only the edges in the matrix
        // Do something for the edge from i to j
    }
  }
Il n'est pas difficile de se rendre compte que cette manière de faire est alorithmiquement inefficace: pour trouver les voisins d'un sommet i du graphe, il faut parcourir toute la ligne i de la matrice d'adjacence. Heureusement, la bibliothèque GSL permet de convertir la matrice précédente dans un format plus efficace:
gsl_spmatrix_uint* csr = gsl_spmatrix_uint_compress(mat, GSL_SPMATRIX_CSR);
Ceci crée une matrice creuse d'entiers au format CSR (Compressed Row Format) dans laquelle les indices des valeurs non nulles de la matrice sont stockés consécutivement dans un tableau.
// Loop over all edges (nnz iterations, ie the non-zero values of csr)
  for (unsigned int i = 0; i < csr->size1; i++) {
    for (unsigned int k = csr->p[i]; k < csr->p[i+1]; k++) {
      unsigned int j = csr->i[k];
      // Do something for the edge from i to j
    }
  }
Pour le sujet, il est demandé à ce que les matrices utilisées soient toutes au format CSR. Si les matrices sont dans des formats différents, cela rendra les clients et les serveurs non interopérables. Pour vérifier le format de la matrice mat, il suffit d'appeler la fonction gsl_spmatrix_uint_type(mat) (qui renvoie une chaîne de caractères "COO" ou "CSR").

 Contact

Pour toute information complémentaire, contacter : David RENAULT.

1.Le terme français le plus proche pourrait sembler être celui d'"inondation", mais il est aussi possible de voir directement ce jeu comme la version ludique d'une famille d'algorithmes de coloration de graphe.