Available nodes

 Coursidor

Le jeu de Quoridor est un jeu de société créé par Mirko Marchesi en 1997. Il se joue sur un plateau de jeu carré, avec deux joueurs possédant un pion initialement placé dans leur zone de départ. L'objectif de chaque joueur est d'atteindre une zone d'arrivée située usuellement du côté opposé du plateau. A chaque tour de jeu, un joueur peut choisir entre soit déplacer son pion d'une case, soit placer un mur limitant les mouvements possibles sur le plateau (dans le meilleur des cas, les mouvements de l'adversaire) sans jamais les bloquer complètement.
(image tirée du site jeuxdenim.be)

Le jeu a été longuement étudié, et a fait en particulier l'objet d'un mémoire de master par L. Glendenning en 2005, qui s'est intéressée à différents algorithmes de jeu, ainsi qu'à un autre document (résultat aussi probablement d'un master) de P.M.C. Mertens en 2006. Le site QuoridorStrats propose aussi des tutoriels et des exemples de stratégies. De manière assez intéressante et non triviale, le jeu de Quoridor ne termine pas forcément pour des joueurs optimaux, et peut conduire à des situations de match nul, comme discuté dans ce forum.
Ce projet propose d'implémenter une variante de Quoridor nommée Coursidor, dans laquelle on remplace l'objectif de traverser le plateau par la règle suivante : les deux joueurs ont pour objectif de parcourir le plateau pour passer sur un certain nombre de bases appelées objectifs, dans un ordre quelconque, à la manière du jeu de baseball. Le plus rapide à passer par l'ensemble des bases, puis à revenir à sa zone de départ, est déclaré vainqueur. Les joueurs peuvent toujours décider de placer des murs pour ralentir leur adversaire, tout en essayant de ne pas se ralentir trop eux-mêmes.

 Graphes de jeu

Le plateau de jeu de Coursidor est représenté par un graphe, ayant la propriété d'être sous-graphe du pavage triangulaire. Ces graphes sont représentés en mémoire par leur matrice d'ajacence, qui est implémentée comme une matrice creuse définie dans la GNU Scientific Library (cf. la section dédiée pour plus de détails). Le graphe contient un nombre de sommets num_vertices (ou n pour simplifier) et un nombre d'arêtes num_edges. La matrice d'adjacence du graphe, nommée t, est une matrice de taille n*n représentant les arêtes du graphe. Le graphe est supposé plongé dans le plan, de manière à ce que les arêtes ne puissent prendre que 7 directions possibles, à savoir NO_EDGE=0, NW=1, NE=2, E=3, SE=4, SW=5, et W=6. Une direction spéciale, WALL_DIR, indique la présence d'un mur. Plus précisément:
  • t[i][j] vaut NO_EDGE s'il n'y a pas d'arête entre les deux sommets i et j,
  • il vaut WALL_DIR si l'arête entre le sommet j et le sommet i est bloquée par un mur,
  • il vaut NW si le sommet j se situe au nord-ouest de i,
  • il vaut SW si le sommet j se situe au sud-ouest de i,
  • il vaut W si le sommet j se situe à l'ouest de i,
  • … et symétriquement pour les directions restantes.
Exemple de graphe :
(pas d'arête entre 1 et 2)
num_vertices = 4
t = [[ 0 3 4 0 ]
     [ 6 0 0 4 ]
     [ 1 0 0 3 ]
     [ 0 1 6 0 ]]
Le graphe sur lequel la partie est joué est non-dirigé. Ainsi, les directions des arêtes se correspondent deux à deux, de manière symétrique. Les directions des arêtes sont utilisées principalement pour aider au placement des murs sur le plateau de jeu.
Le sujet propose de travailler sur plusieurs plateaux de jeu de formes différentes, de taille variable spécifiée par un entier m. Le nombre m peut être fourni sur la ligne de commande et permet généralement de spécifier la largeur du graphe. Les plateaux de jeu disponibles pour les parties sont les suivants:
Graphe triangulaire (type T), avec m ≥ 2 Graphe cyclique (type C), avec m ≥ 3 Graphe troué (type H), avec m ≥ 6, m multiple de 3

Dans le jeu, il est possible de placer des murs pour empêcher les joueurs d'utiliser certaines arêtes. Chaque joueur dispose au début de la partie d'un certain nombre de murs. Le nombre de murs donnés à chaque joueur est le nombre d'arêtes du graphe divisé par 16, dont on prend la partie supérieure. Le jeu standard se jeu sur un graphe triangulaire de largeur 5 avec 156 arêtes, ce qui donne 10 murs par joueur. Les murs ne peuvent pas être placés de n'importe quelle manière sur le graphe. Un mur doit être placé sur deux arêtes consécutives d'un sommet du graphe, comme dans les exemples suivants:

Le placement d'un mur sur deux arêtes du graphe est équivalent au fait de retirer les deux arêtes du graphe.
Les graphes doivent être implémentés en utilisant les matrices définies dans la GSL. Comme la GSL n'implémente pas directement de structure de données de graphes, un des objectifs du projet est de définir une abstraction sous la forme d'une interface permettant de manipuler ces matrices comme des graphes (créer un graphe, ajouter une arête, …).

 Règles du jeu

Les règles du jeu de Quoridor sont décrites de manière très imagée dans ce lien. Les règles de Coursidor reprennent les mêmes principes de base.
  • Initialement, le plateau de jeu est choisi parmi les plateaux décrits dans la section précédente. Chaque joueur dispose d'un pion ainsi que d'un ensemble de murs. Les positions de départ du pion de chaque joueur sont fixées sur le plateau de jeu, et différentes. Le plateau de jeu définit aussi un ensemble de positions objectifs. Les positions des joueurs et des objectifs est assurée d'être symétrique. Il doit forcément exister au moins un objectif sur le plateau de jeu. Les objectifs ne peuvent pas être les positions de départ des joueurs.
  • Les deux joueurs sont représentés par les entiers 0 (BLACK) et 1 (WHITE). Le joueur 0 commence la partie.
  • L'objectif de chaque joueur est de déplacer son pion sur l'ensemble des sommets objectifs, puis de revenir à sa case de départ.
  • A chaque tour de jeu, le joueur produit un coup sous la forme d'une valeur de type struct move_t (les types sont décrits dans la partie suivante).
    enum player_color_t { BLACK=0, WHITE=1, NO_COLOR=2 }; // The colors of the players
    
    enum move_type_t { WALL=0, MOVE=1, NO_TYPE=2 };       // The possible types of moves
    
    typedef size_t vertex_t;                              // The ids of the vertices
    
    struct edge_t { vertex_t fr, to; };                   // An edge of the graph
    
    struct move_t {                                       // A move in the game, given by :
      enum move_type_t t;                                 // - its type
      enum player_color_t c;                              // - the color of the player issueing the move
      vertex_t m;                                         // - the id of a vertex in case of MOVE
      struct edge_t e[2];                                 // - the two edges for the wall in case of WALL
    };
    Le coup possède un champ de type enum move_type_t, qui spécifie le type du coup. Ce champ peut prendre les valeurs MOVE (pour un déplacement), WALL (pour le placement d'un mur), ou NO_TYPE pour décrire un coup invalide. Les coups valides sont les suivants:
    • Déplacement du pion (de type MOVE):
      Ce coup est caractérisé par la donnée de l'identifiant du sommet sur lequel le pion se déplace, placée dans le champ m. Les pions se déplacent uniquement sur des sommets qui dépendent de leur dernier mouvement :
      • si le déplacement se fait dans la même direction que le mouvement précédent, le pion peut se déplacer jusqu'à une distance 3 dans la même direction;
      • si le déplacement se fait dans une direction à 30° du mouvement précédent, le pion peut se déplacer jusqu'à une distance 2 dans la même direction;
      • sinon le déplacement se déplace sur un sommet voisin.

      Pour effectuer un déplacement, il faut que toutes les cases (arrivée, et cases intermédiaires en cas de déplacement d'une longueur ≥ 1) soient valides (i.e correspondent à une arête du graphe) et libres (i.e pas d'adversaire dessus). Tout objectif traversé par un déplacement (même long) sont considérés comme validés. Les déplacements ne peuvent jamais traverser les murs. Tant que le joueur ne s'est pas déplacé, il n'est possible de faire des déplacements qu'à distance 1. Le fait de poser un mur n'a pas d'incidence sur le mouvement précédent. Le champ e est non utilisé. Si plusieurs types de déplacements peuvent arriver sur la même case, pour calculer le dernier mouvement unitaire, on privilégie d'abord les mouvements en ligne droite, puis les sauts sur l'adversaire.
    • Saut par dessus l'adversaire (de type MOVE):
      Ce coup ne peut être réalisé que dans le cas où le pion de l'adversaire est adjacent au pion du joueur. Dans ce cas, celui-ci peut choisir de déplacer son pion en sautant par dessus l'adversaire. La position d'arrivée doit dans ce cas être une case adjacente à la position de l'adversaire, sans être la position de départ. Le champ e est non utilisé.
    • Placement d'un mur (de type WALL):
      Ce coup est caractérisé par la donnée des deux arêtes du plateau recouvertes par le mur, placées dans le champ e, à l'aide d'une structure struct edge_t[2]. Il ne peut être réalisé que si le joueur possède encore des murs à placer. Une fois le mur posé, les arêtes en question ne sont plus utilisables pour le reste de la partie. Le champ m est non utilisé. On impose que le champ fr soit le même pour les deux arêtes, et que les deux arêtes correspondent à deux directions consécutives sur le graphe à partir de fr (dans n'importe quel sens, par exemple NE et E, ou E et NE).
    Pour tous les coups joués, les champs t et c doivent être positionnés correctement.
  • Les pions des deux joueurs ne peuvent jamais occuper la même position. Deux murs ne peuvent jamais se chevaucher.
  • Le placement d'un mur ne peut se faire s'il empêche l'un des joueurs de rejoindre sa case d'arrivée ou n'importe lequel des objectifs par un chemin sur le graphe de jeu. Chaque joueur doit pouvoir continuer à jouer la partie, même après la pose d'un mur.
  • Le gagnant de la partie est le premier joueur à rejoindre sa case de départ après avoir parcouru tous les objectifs, c'est-à-dire avoir déplacé son pion sur toutes les cases d'objectifs au moins une fois.
  • Toute forme de coup invalide fait immédiatement perdre le joueur qui l'a joué.

 Serveur et client

L'objectif du projet consiste à implémenter un ensemble de fonctions permettant de faire jouer deux joueurs à une partie de Coursidor. 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.
Un certain nombre d'interfaces sont fournies pour le projet. Ces interfaces sont non modifiables:
  • Le fichier move.h décrit le format des coups joués dans la partie (discutés dans la section Règles du jeu).
  • Le fichier graph.h décrit le format des graphes utilisés comme graphes de jeu (discutés dans la section Graphes de jeu).
  • Le fichier player.h décrit la liste de fonctions à implémenter pour un client désirant jouer à la partie.
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 construit le plateau de jeu sur lequel la partie va se dérouler, et initialise les positions des joueurs et des objectifs. Le serveur transmet ensuite ces informations à chaque joueur en utilisant leur fonction initialize.

Après cela, 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. 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 :

first_player = random_or_config()
graph = make_graph()
for each player p
    player_col = (p == first_player) ? BLACK : WHITE
    p->initialize(player_col, graph)
current_move = { .t = NO_TYPE, .c = NO_COLOR }
while true
   p = compute_next_player()
   current_move = p->play(current_move)
   if is_invalid(current_move) or is_game_over()
      break
for each player p
   p->finalize()
Exemple de début de partie du point de vue du serveur :
sophy->initialize(B, graph)
david->initialize(W, graph)

sophy->play({.t=NO_TYPE,.c=NO_COLOR})
// -> returns {.t=MOVE,.c=B,.m=6}
david->play({.t=MOVE,.c=B,.m=6})
// -> returns {.t=MOVE,.c=W,.m=4}
sophy->play({.t=MOVE,.c=W,.m=4})

 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
    /test           -- Source files for the tests
    /install        -- Install directory (should be empty in the repository but for a .keep file)
Le serveur de jeu se présentera sous la forme d'un exécutable server installé dans le répertoire install. Il 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] [-M NB] ./install/player1.so ./install/player2.so

Les tests seront réalisés sous la forme d'un exécutable alltests qui doit lui aussi être installé dans le répertoire install. Il 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), et optionnellement un sous-répertoire tests contenant des exécutables test_*.

 Makefile

Le fichier Makefile devra fournir :
  • une règle build qui compilera l'ensemble du code sans les tests,
  • une règle build_tests qui compilera les tests,
  • une règle test qui exécutera les tests
  • 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 et test_*) à 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).

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 être 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)                               // The edges depends on the graph
    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.
for (unsigned int i = 0; i < csr->size1; i++) {           // Loop over all edges (nnz iterations, ie the non-zero values of csr)
    for (unsigned int k = csr->p[i]; k < csr->p[i+1]; k++) {
         unsigned int j = csr->i[k];                      // `j` is the index of the other extremity of the edge
                                                          // 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.