Available nodes

 Quoridor

Le jeu de Quoridor est un jeu de société à deux joueurs, qui se joue sur un plateau à cases usuellement carrées séparées de chaque côté par de petites rigoles1. Un ensemble de joueurs s'affrontent de la manière suivante: leur objectif consiste à déplacer un pion de leur couleur d'une zone de départ à une zone d'arrivée. À chaque tour, ils peuvent choisir soit de déplacer leur pion sur une case voisine, soit de poser un mur dans une rigole afin de bloquer les déplacements entre deux cases. Le vainqueur du jeu est celui réussissant à faire rejoindre à son pion sa zone d'arrivée le premier.
(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. L'objectif de ce projet va consister à mettre en place des stratégies pour jouer aussi efficacement que possible au jeu de Quoridor et certaines de ses généralisations.

 Graphes de jeu

Cette section décrit les types de données servant de briques de base à la réalisation du sujet. Pour la suite, on supposera que les deux joueurs sont représentés par les entiers 0 (BLACK) et 1 (WHITE). Le joueur débutant la partie est décidé aléatoirement. Les définitions des coups et des graphes utilisés devront se conformer aux interfaces move.h et graph.h suivantes. Il est demandé de ne pas modifier ces en-têtes.
Les composants du graphe sont des matrices creuses définies par 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). La matrice t est une matrice d'adjacence de taille n*n représentant les arêtes du graphe:
  • t[i][j] vaut 0 s'il n'y a pas d'arête entre les deux sommets i et j,
  • il vaut 1 si le sommet j se situe au nord de i,
  • il vaut 2 si le sommet j se situe au sud de i,
  • il vaut 3 si le sommet j se situe à l'ouest de i,
  • il vaut 4 si le sommet j se situe à l'est de i,
Dans ce projet, les graphes sont supposés non dirigés, et sous-graphes de la grille carrée. La matrice o est une matrice 2*n codant sur chaque ligne les sommets du graphe appartenant au joueur correspondant (donc 0 ou 1). L'ajout de fonctions supplémentaires à cette interface est naturellement autorisé, bien que conseillé dans un fichier différent.
Exemple de graphe :
num_vertices = 4
t = [[ 0 4 2 0 ]
     [ 3 0 0 2 ]
     [ 1 0 0 4 ]
     [ 0 1 3 0 ]]
o = [[ 1 0 0 0 ]
     [ 0 0 0 1 ]]
Les conventions pour jouer sont les suivantes: les joueurs partent des positions leur appartenant, et gagnent dès qu'ils atteignent une position appartenant à leur adversaire.
Le sujet propose de travailler sur 3 graphes de formes différentes, avec des tailles variables. Comme on assure que les graphes sont des sous-graphes de la grille carrée, il est toujours possible d'associer à une arête l'arête opposée lorsqu'elle existe. Le nombre m est spécifié sur la ligne de commande et permet de spécifier la largeur du graphe.
Graphe carré c Graphe torique t, avec m multiple de 3 Graphe haché h, avec m multiple de 3 Graphe serpent s, avec m multiple de 5

Le nombre de murs donnés à chaque joueur en début de partie est le nombre d'arêtes du graphe divisé par 15, dont on prend la partie supérieure. Le jeu standard se jeu sur une grille carrée 9x9 avec 144 arêtes, ce qui donne 10 murs par joueur. Lorsqu'il s'agit de placer un mur sur le graphe, les murs ne peuvent être placés que d'une des manières suivantes:
  • un mur peut être placé sur les deux arêtes à l'est (resp. à l'ouest) de deux sommets en relation nord-sud;
  • un mur peut être placé sur les deux arêtes au nord (resp. au sud) de deux sommets en relation est-ouest.

 Coups possibles

Les règles du jeu de Quoridor sont décrites de manière très imagée dans ce lien. Par esprit de complétude, on rappelle quelques principes généraux qui s'appliquent pour les graphes généralisés décrits avant.
  • Pour le tout premier coup de la partie, le type du previous_move est fixé à NO_TYPE. C'est le seul coup possible ayant ce type. Un coup NO_TYPE (ou toute autre valeur différente de MOVE ou WALL) envoyé en milieu de partie est une erreur.
  • Initialement, les joueurs disposent d'un pion et d'un ensemble fini de murs. Le premier coup de la partie pour chaque joueur est un MOVE et consiste à placer son pion sur une des cases qui lui appartiennent dans le graphe (cf. matrice o).
  • A chaque tour de jeu après le premier tour, les joueurs peuvent soit choisir de déplacer leur pion (MOVE), soit de placer un mur s'il leur en reste un (WALL).
  • Un joueur qui choisit de se déplacer (MOVE) doit se déplacer sur une position adjacente dans le graphe de jeu. Il ne peut se déplacer à travers un mur. Si la position où il se déplace est occupée par un pion adverse, il peut sauter ce pion en se déplaçant deux fois dans la même direction (par exemple nord + nord). Si le second déplacement dû à un saut est impossible (pour cause de mur ou de "bord du monde", le 2nd déplacement peut être fait sur n'importe quelle arête voisine du pion adverse, sans revenir à sa position de départ.
  • Lors d'un MOVE, le struct move_t envoyé au serveur renseigne le champ m donnant la position d'arrivée. Le champ e est non utilisé. Les champs t et c doivent être renseignés correctement.
  • Un joueur qui choisit de placer un mur (WALL) ne peut le faire que s'il dispose encore de murs en main. Il doit le placer sur l'une des positions valides décrites plus avant. Les murs ne peuvent pas se recouvrir. Le placement d'un mur ne peut se faire s'il empêche l'un des joueurs de rejoindre au moins une case d'arrivée valide.
  • Lors d'un WALL, le struct move_t envoyé au serveur renseigne (entre autres) le champ e donnant la liste des deux arêtes occupées par le mur. Le champ m est non utilisé. Les champs t et c doivent être renseignés correctement.

 Description du projet

L'objectif du projet consiste à implémenter un ensemble de fonctions permettant de faire jouer deux joueurs à une partie de Quoridor. 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). La boucle de jeu devra suivre le pseudo-algorithme suivant :
start_player = random()
for each player p
    p->initialize(p == start_player ? BLACK : WHITE, graph, num_walls)
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(B, graph, 10)
david->initialize(W, graph, 10)

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

#include "move.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 color assigned to the player
 * - graph     : the graph where the game is played
 * - num_walls : the number of walls assigned to the player
 * PRECOND:
 * - `id` is either BLACK or WHITE
 * - `graph` is a heap-allocated copy of the graph where the game is
 *   played, that must be freed in the end
 * - `num_walls` is the number of edges of `graph` divided by 15,
     rounded up
 * - initialize has never been called before
 */
void initialize(enum color_t id, struct graph_t* graph, size_t num_walls);

/* Computes next move
 * PARAM:
 * - previous_move: the move from the previous player
 * 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 // _QUOR_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.
Pour les stratégies implémentables, quelques propositions :
  • un joueur choisissant aléatoirement ses coups parmi les coups possibles;
  • un joueur choisissant ses coups de façon à réduire la distance entre la position du joueur et la zone d'arrivée;
  • un joueur choisissant ses coups de façon à augmenter la distance entre la position du joueur adverse et sa zone d'arrivée;
  • un joueur réalisant l'une des ouvertures décrite dans la site QuoridorStrats;
  • une stratégie explorant les coups possibles en créant un arbre d'exploration (cf. par exemple les algorithmes de MinMax ou de Monte-Carlo).
  • une stratégie accélérant les stratégies précédentes en utilisant un algorithme d'apprentissage (en utilisant par exemple la bibliothèque FANN) 2 .

 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] ./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, torique t, hachée h ou serpent s ) (ex. -t h).
  • Les clients sont passés en paramètre dans l'ordre 1er joueur / 2nd joueur.
  • 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.

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.

 Contact

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

1.Oui, des rigoles, la langue française est un bonheur renouvelé à chaque seconde. Des goulottes si vous préférez. Avouez que vous ne lisez ces sujets que pour les notes de base de page.
2.Une telle stratégie a besoin d'une fonction d'évaluation un peu sérieuse, et donc ne pourra être envisagée qu'après avoir implémenté certaines des stratégies précédentes.