Hex
Le jeu
de Hex
est un jeu de société à deux joueurs, qui se joue sur un plateau à
cases hexagonales dont les bords sont colorés aux couleurs des
joueurs, en alternant. Deux joueurs s'affrontent en sélectionnant à
chaque tour une case du tableau inoccupée, et en lui assignant sa
couleur. Le vainqueur du jeu est celui réussissant à connecter les
deux bords de sa couleur par un chemin de cases lui
appartenant :
De manière assez intuitive, il est possible de se rendre compte
qu'une partie de Hex se termine forcément avec un unique
vainqueur. Il s'agit néanmoins d'un résultat non trivial dont la
preuve est liée au théorème de Brouwer et accessible
dans cet article de D. Gale. Un argument assez
élégant (et non constructif) permet de montrer que le premier joueur
a toujours une stratégie gagnante, même si on ne sait pas l'exhiber
en général. En fait, S. Reisch a prouvé que le calcul d'une
stratégie gagnante sur un plateau arbirtraire était un
problème PSPACE-complet. L'objectif de ce projet va
consister à mettre en place des stratégies pour jouer aussi
efficacement que possible au jeu de
Hex. L'article suivant de V. Anshelevich fournit des
idées d'heuristiques à mettre en place pour le calcul de telles
stratégies.
Image réalisée à partir du code de sigalor |
Joueurs, coups et graphes
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 BLACK
est celui débutant la
partie. Les définitions des coups et
des graphes utilisés devront se conformer aux
interfaces move.h
et graph.h
suivantes.
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. Dans la majeure partie de ce projet, les
graphes sont supposés non dirigés. 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 : |
|
La condition de victoire dans un graphe
généralisé consiste à connecter l'ensemble des sommets du graphe
appartenant initialement à un joueur.
Le sujet propose de travailler sur 3 graphes de formes différentes,
avec des tailles variables. Le nombre m
est spécifié
sur la
ligne de commande et permet de spécifier la largeur du graphe.
Graphe hexagonal h |
Graphe carré c |
Graphe triangulaire t , m pair |
Description du projet
L'objectif du projet consiste à implémenter un ensemble de fonctions
permettant de faire jouer deux joueurs à une partie
de Hex. Le code sera décomposé en deux parties
distinctes :
Le démarrage dit de la "règle du gâteau" (pie
rule en anglais) consiste à demander au premier joueur de
produire un coup valide, puis à demander au second joueur s'il
accepte ce démarrage. S'il accepte, il continue la partie
normalement en jouant les blancs. Sinon, il joue les noirs, et le
premier joueur, qui peut alors jouer, joue les blancs. Ensuite, la
partie se déroule normalement.
Pour les besoins du jeu, le fichier
player.h
décrit l'interface à utiliser pour
communiquer entre client et serveur.
- 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.
|
Exemple de début de partie :
sophy->initialize_graph(graph) david->initialize_graph(graph) david->propose_opening(7) // start on tile '7' sophy->accept_opening(7) // return true sophy->initialize_color(W) david->initialize_color(B) sophy->play(7) // return 6 david->play(6) // return 4 sophy->play(4) // ... |
#ifndef _HEX_PLAYER_H_
#define _HEX_PLAYER_H_
#include <stdlib.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();
/* Returns a single move for an opening
* PRECOND:
* - a call to initialize_graph has been made
* RETURNS:
* - a correct move inside the graph
*/
struct move_t propose_opening();
/* Acceptation of the opening
* PARAM:
* - opening : a move inside the graph
* PRECOND:
* - a call to initialize_graph has been made
* - the move is valid with regard to this graph
* RETURNS:
* - a boolean telling if the player accepts the opening
*/
int accept_opening(const struct move_t opening);
/* Player graph initialization
* PARAM:
* - graph : the graph where the game is played
* PRECOND:
* - `graph` is a heap-allocated copy of the graph where the game is
* played, that must be freed in the end
* - initialize_graph has never been called before
*/
void initialize_graph(struct graph_t* graph);
/* Player color initialization
* PARAM:
* - id : the color assigned to the player
* PRECOND:
* - id is either BLACK or WHITE
* - initialize_color has never been called before
*/
void initialize_color(enum color_t id);
/* 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 // _HEX_PLAYER_H_
Il est demandé de respecter les principes suivants :
Pour les stratégies implémentables, quelques propositions :
- 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
degcc
) et chargeable de manière dynamique, en utilisant les fonctions de la familledlopen
, définies dansdlfcn.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.
- un joueur choisissant aléatoirement ses coups parmi les coups possibles;
- un joueur choisissant ses coups de façon à réduire la distance entre les composantes connexes du joueur;
- un joueur choisissant ses coups en fonction de l'heuristique dite "de Kirchhoff" mise en place au chapitre 3 de l'article d'Anshelevich (il pourra être nécessaire de calculer une base de cycles pour cela);
- un joueur choisissant ses coups en fonction de l'heuristique dite "des connections virtuelles" mise en place au chapitre 4 de l'article d'Anshelevich;
- 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) 1 .
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 fichier
/ -- Base directory Makefile -- Global Makefile /src -- Source files /install -- Install directory (should be empty in the repository)
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é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.
Le
Le serveur devra charger l'ensemble de ses clients de manière
dynamique en utilisant la syntaxe suivante :
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
./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 triangulairet
, carréec
ou hexagonaleh
) (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.
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.
- Lien vers la documentation;
- Documentation des matrices dans GSL;
- Documentation des matrices creuses dans GSL.
Contact
Pour toute information complémentaire, contacter : David RENAULT.
1. | 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. |