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 :
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.
![]() |
(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
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
Le nombre de reines par joueur, noté
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]
vautNO_DIR
ou0
s'il n'y a pas d'arête entre les deux sommetsi
etj
, - sinon
t[i][j]
prend une des valeurs de directions données dans le fichier dir.h, comprise entreFIRST_DIR
etLAST_DIR
, représentant la direction de l'arête allant du sommeti
au sommetj
.
Exemple de graphe : |
![]() |
|
Pour aller de 2 à 3 ,
il faut utiliser l'arête
t[2][3] == 7 qui est une arête DIR_EAST .
|
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 :
Le serveur joue le rôle d'entremetteur entre les joueurs. Il
commence par décider qui est le premier joueur,
nommé
Lorsque la partie se termine, le serveur appelle les
fonctions
- 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.
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 :
|
|
finalize
des deux joueurs. Au final,
l'ensemble de ces interactions correspond au pseudo-algorithme
suivant :
|
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 depuisqueen_src
, différente dequeen_src
; - le champ
arrow_dst
doit correspondre à une position libre et accessible en ligne droite depuisqueen_dst
, différente dequeen_dst
;
- le champ
- 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) :
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).
/ -- Base directory Makefile -- Global Makefile /src -- Source files /install -- Install directory (should be empty in the repository but for a .keep empty file)
./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éec
, donutd
, trèflet
ou en huit8
). 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 …
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 :
- une règle
build
qui compilera l'ensemble du code sans les tests, - 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.
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
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)
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. | La division est une division entière. |