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 :
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.
(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
Le graphe contient un nombre de sommets
Le sujet propose de travailler sur 4 familles de graphes de formes différentes, avec des tailles variables. Le nombre
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 :
:
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 : |
|
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
etMAX_COLOR-1
au sens large. - Les couleurs associées aux positions de démarrage des deux joueurs sont forcément différentes.
- 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
:
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.
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 :
Pour les besoins du jeu, le fichier
player.h
décrit l'interface à utiliser pour
communiquer entre client et serveur.
- 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.
|
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) // ... |
#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
degcc
) et chargeable de manière dynamique, en utilisant les fonctions de la familledlopen
, définies dansdlfcn.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 :
Le fichier
/ -- Base directory Makefile -- Global Makefile /src -- Source files /install -- Install directory (should be empty in the repository but for a .keep file)
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écutablealltests
, 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
Le serveur devra charger l'ensemble de ses clients de manière
dynamique en utilisant la syntaxe suivante :
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
./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éec
, donutd
, hachéeh
ou toriquet
) (ex.-t h
). -
L'option
-c
permet de spécifier le nombre de couleurs utilisé dans la partie. Ce nombre est un entier compris entre2
etMAX_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.
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.
:
Ceci crée une matrice creuse d'entiers au
format :
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 :
Ceci crée une matrice creuse d'entiers au
format
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
.
- Lien vers la documentation;
- Documentation des matrices dans GSL;
- Documentation des matrices creuses dans GSL.
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);
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
}
}
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 efficacegsl_spmatrix_uint* csr = gsl_spmatrix_uint_compress(mat, GSL_SPMATRIX_CSR);
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. |