Available nodes

 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 :
Image réalisée à partir du code de sigalor
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.

 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 :
num_vertices = 4
t = [[ 0 1 1 0 ]
     [ 1 0 1 1 ]
     [ 1 1 0 1 ]
     [ 0 1 1 0 ]]
o = [[ 1 0 0 0 ]
     [ 0 0 0 1 ]]
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 :
  • 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 :
for each player p
   p->initialize_graph(graph)
move = first_player->propose_opening()
if second_player->accept_opening(move) // 2nd player plays next
   first_player->initialize_color(BLACK)
   second_player->initialize_color(WHITE)
else // 2nd player refuses and 1st player plays next
   first_player->initialize_color(WHITE)
   second_player->initialize_color(BLACK)
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_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)    // ...
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.

#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 :
  • 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 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 .
En reconnaissant les positions de jeu intéressantes et en éliminant les positions inutiles, il devient possible d'implémenter des algorithmes d'exploration de l'arbre des possibilités comme le Min-Max et ses variantes.

 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)
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 triangulaire t, carrée c ou hexagonale h) (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.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.