Available nodes

 Le jeu des amazones

Le jeu des amazones est un jeu de territoire dans lequel deux joueurs cherchent à préserver leur capacité de mouvement tout en réduisant celle de leur adversaire. Il se joue traditionnellement sur un plateau d'échecs, sur lequel chaque adversaire dispose d'un certain nombre d'amazones. Pour jouer un tour, un joueur doit d'abord déplacer l'une de ses pièces, puis tirer une flèche sur une case vide qui devient par la suite inaccessible. Dans l'exemple suivant, les cases inaccessibles sont représentées par des murs :
(image tirée du site BoardGameGeek)

Bien que d'invention relativement récente (1988), ce jeu fait l'objet de nombreuses publications, démontrant sa richesse. En 2005, R. A. Hearn a montré dans un article plutôt lisible que le fait de décider le gagnant d'une partie d'amazones était PSPACE-complet, et donc faisait partie des problèmes les plus difficiles à résoudre dans un espace polynomial. Par ailleurs, M. Buro a aussi montré que le fait de déterminer le vainqueur d'une fin de partie était un problème NP-complet. Ces caractéristiques rendent ce jeu intéressant parce qu'elles assurent qu'il ne peut se résoudre de manière triviale. A côté de ces résultats académiques, il existe plusieurs travaux proposant des heuristiques de jeu, comme une fonction d'évaluation des positions, ainsi que des comparaisons d'algorithmes pour les fins de parties. Il est donc envisageable de produire des heuristiques variées pour approximer des stratégies optimales. C'est à ce type d'objectif que ce projet propose de s'attaquer.

 Graphes de jeu

Les plateaux de jeu utilisés pour jouer à une partie d'amazones seront codés avec des graphes. Pour la suite, on supposera que les deux joueurs sont représentés par les entiers 0 et 1.

Un graphe contient un nombre de sommets num_vertices (ou n pour simplifier). Les sommets du graphe sont identifiés aux entiers de 0 à n-1. Le graphe est représenté par une matrice d'adjacencet de taille n*n représentant les arêtes du graphe. Dans ce projet, les graphes sont supposés non orientés, mais nous utilisons les valeurs de la matrice pour indiquer les directions des arêtes.

  • t[i][j] vaut NO_DIR ou 0 s'il n'y a pas d'arête entre les deux sommets i et j,
  • sinon t[i][j] prend une des valeurs de directions données dans le fichier dir.h, comprise entre FIRST_DIR et LAST_DIR, représentant la direction de l'arête allant du sommet i au sommet j.
Exemple de graphe :
num_vertices = 4
t = [[ 0 7 5 0 ]
     [ 3 0 0 5 ]
     [ 1 0 0 7 ]
     [ 0 1 3 0 ]]
Pour aller de 2 à 3, il faut utiliser l'arête t[2][3] == 7 qui est une arête DIR_EAST.

Le sujet propose de travailler sur 4 graphes de formes différentes, avec des tailles variables. Comme on assure que les graphes sont des sous-graphes de la grille carrée, les 8 directions cardinales et diagonales sont aisément représentables. Le nombre m est spécifié sur la ligne de commande et permet de spécifier la largeur du graphe. Dans tous les cas, on demande à ce que m soit >=5 pour pouvoir placer les reines sur le plateau.


Le nombre de reines par joueur, noté num_queens, est fixé à 4*(m/10 + 1)1 de manière à ce que ce soit toujours un multiple de 4. Chaque joueur dispose du même nombre de reines, disposées sur le plateau comme indiqué sur les graphes. Les reines sont disposées sur les 4 côtés du graphe. Il y a un nombre pair de reines sur chaque côté. Sur un côté, la placement des reines est laissé libre, mais il doit être symétrique, et laisser un espace entre deux reines consécutives et entre les reines et le bord. Aussi le placement doit être le même sur chaque côté. Par exemple, si m=8, il y a num_queens=4 reines par joueur. Si m=10, il y a num_queens=8 reines par joueur.

 Serveur et client

L'objectif du projet consiste à implémenter un ensemble de fonctions permettant de faire jouer deux joueurs à une partie d'amazones. 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.
Clients et serveurs discutent à travers une même interface. Pour assurer une interopérabilité entre tous les clients et serveurs, cette interface est fournie et non modifiable. Elle est nommée player.h et décrit une liste de fonctions à implémenter pour un client désirant jouer à la partie. Afin de découper le code, il est aussi fourni un fichier dir.h fixant la manière dont sont codées les directions, un fichier move.h fixant la forme des coups entre les joueurs et un fichier graph.h fixant la structure de graphe (utilisant la GSL).
Le serveur joue le rôle d'entremetteur entre les joueurs. Il commence par décider qui est le premier joueur, nommé BLACK ou 0. Il prépare un graphe de jeu, ainsi que les positions des reines. Il transmet ces informations à chaque joueur en utilisant leur fonction initialize. Ensuite, il fait alterner les coups des deux joueurs en appelant leur fonction play. Cette fonction retourne un struct move_t indiquant le coup du joueur courant, constitué comme suit  :
struct move_t {
  unsigned int queen_src;
  unsigned int queen_dst;
  unsigned int arrow_dst;
};
  • un champ queen_src représentant la position de départ de la reine;
  • un champ queen_dst représentant la position d'arrivée de la reine;
  • un champ arrow_dst représentant la position de la flèche.
Lorsque la partie se termine, le serveur appelle les fonctions finalize des deux joueurs. Au final, l'ensemble de ces interactions correspond au pseudo-algorithme suivant :
start_player = random_or_config()
for each player p
    pcol = (p == start_player) ? BLACK : WHITE
    p->initialize(pcol, num_vertices, graph, num_queens, queens)
move = { -1, -1, -1 }
while true
   p = compute_next_player()
   move = p->play(move)
   if is_invalid(move)
      break
   if is_winning()
      break
for each player p
   p->finalize()
Exemple de début de partie :
sophy->initialize(B, 5, graph, 2, queens)
david->initialize(W, 5, graph, 2, queens)

sophy->play({-1, -1, -1})  // return {14, 0, 1}
david->play({14, 0, 1})    // return {46, 11, 7}
sophy->play({46, 11, 7})    // ...

 Coups possibles

Les règles du jeu sont décrites sur la page du jeu. Pour adapter les règles au projet, voici quelques précisions :
  • Pour le tout premier coup de la partie, la valeur du coup précédent est fixée à {-1, -1, -1}. C'est le seul moment de la partie où cette valeur apparaît, et est transmise au premier joueur.
  • Les coups renvoyés par les fonctions play sont censés être valides au sens suivant :
    • le champ queen_src doit correspondre à la position d'une reine appartenant au joueur courant;
    • le champ queen_dst doit correspondre à une position libre et accessible en ligne droite depuis queen_src, différente de queen_src;
    • le champ arrow_dst doit correspondre à une position libre et accessible en ligne droite depuis queen_dst, différente de queen_dst;
    Toute forme de coup incorrecte fait perdre le joueur l'ayant joué.
  • Les parties se font forcément en un temps fini, et il y a nécessairement un vainqueur à la fin. Le vainqueur est le dernier joueur à avoir pu jouer un coup correct. Pour aider aux tests, il est possible de configurer le serveur à ne jouer qu'un nombre fini de coups.

 Détails techniques

Pour les besoins du projet, le dépôt devra s'organiser autour de l'arborescence suivante (d'autres fichiers et répertoires peuvent s'y ajouter) :
    /               -- Base directory
     Makefile       -- Global Makefile
    /src            -- Source files
    /install        -- Install directory (should be empty in the repository but for a .keep empty file)
Le serveur de jeu devra, par l'intermédiaire d'options passées sur la ligne de commande permettre de configurer la partie, et en particulier sélectionner la forme du plateau (avec des graphes de tailles et de formes différentes).
./install/server -m [M] -t [T] ./install/player1.so ./install/player2.so
  • L'option -m permet de spécifier la largeur du plateau de jeu (comme spécifié à la section Graphes de jeu). Par exemple : -m 10.
  • L'option -t permet de spécifier la forme du plateau de jeu (grille carrée c, donut d, trèfle t ou en huit 8 ). Par exemple : -t 8.
  • Les clients sont passés en paramètre dans un ordre quelconque, c'est au serveur de déterminer leur ordre de jeu.
  • Les paramètres optionnels doivent pouvoir être placés dans n'importe quel ordre sur la ligne de commande, comme le permet la bibliothèque getopt.
  • D'autres paramètres peuvent évidemment être ajoutés au serveur de jeu pour le rendre plus flexible : choix de la graine aléatoire, choix du premier joueur …

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, ainsi qu'un nombre quelconque de clients sous la forme de bibliothèques partagées (fichiers .so).

 Makefile

Le fichier Makefile devra fournir : 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).

Pour permettre à l'exécutable de trouver de lui-même les bibliothèques nécessaires, il est demandé d'utiliser l'option --rpath du linker. La documentation donne quelques explications, la plupart du temps, il s'agira de passer les bonnes options au compilateur lors de l'édition de liens (avec une syntaxe d'une évidence trouble) :

LDFLAGS += -Wl,--rpath=${GSL_PATH}/lib

 dlopen

L'un des aspects de ce projet est de rendre les clients 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 et chargeable de manière dynamique par le serveur.
  • Les différents clients doivent compilés avec l'option -shared de gcc;
  • Le serveur doit pouvoir charger les clients de manière dynamique, en utilisant les fonctions de la famille dlopen, définies dans dlfcn.h. Il est possible de s'inspirer des instructions données dans la page suivante, qui contiennent, entre autres, un exemple complet d'utilisation.
Il est demandé d'implémenter au moins deux clients différents, i.e ayant des stratégies différentes. Il est aussi demandé de faire attention à éviter la duplication du code (en particulier pour les données du plateau de jeu). Remarquer que l'interface ne permet pas de communication dudit plateau entre client et serveur pendant la partie.

 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.La division est une division entière.