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.
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.
![]() |
(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 :
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 :
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, …).
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]
vautNO_EDGE
s'il n'y a pas d'arête entre les deux sommetsi
etj
, - il vaut
WALL_DIR
si l'arête entre le sommetj
et le sommeti
est bloquée par un mur, - il vaut
NW
si le sommetj
se situe au nord-ouest dei
, - il vaut
SW
si le sommetj
se situe au sud-ouest dei
, - il vaut
W
si le sommetj
se situe à l'ouest dei
, - … et symétriquement pour les directions restantes.
Exemple de graphe : (pas d'arête entre 1 et 2) |
![]() |
|
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
) et1
(WHITE
). Le joueur0
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).
Le coup possède un champ de typeenum 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 };
enum move_type_t
, qui spécifie le type du coup. Ce champ peut prendre les valeursMOVE
(pour un déplacement),WALL
(pour le placement d'un mur), ouNO_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 champm
. 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 champe
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. -
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
- 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 champe
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 champe
, à l'aide d'une structurestruct 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 champm
est non utilisé. On impose que le champfr
soit le même pour les deux arêtes, et que les deux arêtes correspondent à deux directions consécutives sur le graphe à partir defr
(dans n'importe quel sens, par exempleNE
etE
, ouE
etNE
).
t
etc
doivent être positionnés correctement. - Déplacement du
pion (de type
- 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 :
:
Le serveur joue le rôle d'entremetteur entre les joueurs. Il
commence par décider qui est le premier joueur,
nommé
- 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 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.
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 :
|
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 :
Le serveur de jeu se présentera sous la forme d'un
exécutable
/ -- 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)
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 options
-t
et-m
permettent de spécifier le plateau de jeu. Le premier fixe le type de graphe sur lequel la partie est joué, et le second la taille de la maille. Si les options ne sont pas fournies, le partie se joue par défaut sur un graphe triangulaire (-t T
) et sur une maille de taille 6 (-m 6
).
Par exemple :-m 9 -t H
permettent de choisir le graphe troué de largeur 9. -
L'option
-M
permet de spécifier le nombre de tours maximal de la partie. Une partie qui a atteint ce nombre de tours sans vainqueur est une partie nulle. Par défaut, le serveur fait tourner la partie jusqu'à ce qu'il y ait un vainqueur. - 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 …
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écutablealltests
, et un nombre non spécifié de fichiers.so
ettest_*
) à l'intérieur du répertoire désigné, et - une règle
clean
qui supprimera les fichiers compilés et installés.
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
degcc
; -
Le serveur doit pouvoir charger les clients de manière
dynamique, en utilisant les fonctions de la
famille
dlopen
, définies dansdlfcn.h
. Il est possible de s'inspirer des instructions données dans la page suivante, qui contiennent, entre autres, un exemple complet d'utilisation.
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) // The edges depends on the graph
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.
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.