Available nodes

 Gomoku

Le jeu de Gomoku (aussi appelé Renju) est un jeu de plateau se jouant sur un plateau de Go traditionnel. Deux joueurs alternent en plaçant sur la grille des pions blancs et noirs. Le gagnant est le premier réussissant à aligner au moins 5 pions de sa couleur sur le plateau (free-style gomoku).

Source : Wikipedia

En dépit de la simplicité apparente de ses règles, le jeu de Gomoku est d'une grande complexité (cf. par exemple ce lien). Il a été prouvé que le jeu possédait dans sa forme la plus classique une stratégie gagnante pour le premier joueur (cf. la thèse de L. V. Allis (1994), Searching for Solutions in Games and Artificial Intelligence). Le but de ce projet consiste à écrire un ensemble d'outils permettant de jouer au Gomoku et de comparer différentes stratégies de jeu. Différents types de stratégies de jeu sont discutées ici ou .

 Bitboards

Le bitboard est une structure de données utilisée pour représenter les états de jeux de plateaux classiques (échecs, go, reversi, …). L'idée générale consiste à représenter un bit de données par case du plateau, et d'agréger l'ensemble de ces données dans une seule structure. Ensuite, il s'agit de tirer parti des opérateurs booléens classiques (cf. par exemple ici) pour obtenir des opérations très performantes. En utilisant des entiers sur 128 bits, il est possible de jouer sur des plateaux de taille allant jusqu'à 11 par 11. Le document Bitboard Methods for Games détaille un ensemble de stratégies classiques pour tirer parti de ce type de structure de données :
  • représenter l'état d'un plateau de jeu après un certain nombre de coups,
  • calculer la liste des coups possibles à partir d'un tel état,
  • reconnaître une fin de partie, ou plus généralement une position de jeu gagnante,
  • calculer une heuristique permettant de déterminer la qualité d'une position de jeu.
En reconnaissant des 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.

 Description du projet

L'objectif du projet consiste à implémenter un ensemble de fonctions permettant de faire jouer deux joueurs à une partie de Gomoku. 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. L'un des clients doit implémenter une stratégie dérivée de Min-Max.
  • 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 taille du plateau (pour des tailles variant au moins entre 5 et 11), de choisir le premier joueur et de choisir le type de démarrage de partie (standard ou swap). La boucle de jeu devra suivre le pseudo-algorithme suivant :
moves = first_player->propose_opening(size)
if second_player->accept_opening(size, moves) // 2nd player plays next
   first_player->initialize(size, BLACK)
   second_player->initialize(size, WHITE)
else // 2nd player refuses and 1st player plays next
   first_player->initialize(size, WHITE)
   second_player->initialize(size, BLACK)
while true
   p = compute_next_player()
   m = p->play(last_n(moves))
   if is_winning()
      break
   enqueue(m, moves)
for each player p
   p->finalize()
Exemple de début de partie :
david->propose_opening(10)
moves = [ {(5,5),B}, {(6,5),W}, {(5,6),B} ]
sophy->accept_opening(10, moves) // return true

sophy->initialize(10, W)
david->initialize(10, B)

sophy->play(moves, 3)    // return {(6,6),W}
moves.enqueue({(6,6),W}) // [{(5,5),B},{(6,5),W},{(5,6),B},{(6,6),W}]
david->play(moves, 4)    // return {(4,6),B}
moves.enqueue({(4,6),B})
sophy->play([{(6,6),W}, {(4,6),B}], 2) // ...
Le démarrage standard consiste à faire démarrer les deux joueurs sur un plateau vide, le premier joueur jouant avec les pièces noires. Le démarrage swap demande au premier joueur de produire une séquence de trois coups valides (noir-blanc-noir), puis demande au second joueur s'il accepte cette séquence de jeu. 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.

La fonction play prend en paramètre un tableau représentant les coups joués depuis son dernier coup. S'il s'agit du premier appel à la fonction pour ce joueur, le tableau contient la liste de tous les coups depuis le début de la partie. Les 3 coups des séquences de démarrage ne sont pas considérés comme joués par un joueur particulier, même s'ils ont une couleur.

En plus du code, il est demandé :

  • Une évaluation des qualités des différents clients proposés.
  • Une évaluation des qualités des différentes ouvertures, (afin de confirmer ou d'infirmer les évaluations laconiques fournies pour les règles du Renju)

 Détails techniques

Pour les besoins du jeu, les fichiers suivants (move.h et player.h ) décrivent l'interface à utiliser pour communiquer entre client et serveur.
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.
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 on the repository)
Le fichier Makefile devra fournir :
  • une règle build qui compilera l'ensemble du code,
  • une règle test qui exécutera les tests,
  • une règle install qui copiera les exécutables à l'intérieur du répertoire désigné, et
  • une règle clean qui supprimera les fichiers compilés et installés.
Le serveur devra charger l'ensemble de ses clients de manière dynamique en utilisant la syntaxe suivante :
./install/server -n [N] -o ./install/player1.so ./install/player2.so
  • L'option -n permet de spécifier la taille du plateau de jeu (ex. -n 10).
  • L'option -o, si elle est passée en paramètre, active les règles de démarrage swap, sinon le jeu se joue avec les règles standard.
  • 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.
L'exécutable doit afficher uniquement du texte sur la sortie standard.
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 un exécutable nommé server, et des clients sous la forme de bibliothèques partagées (fichiers .so). Toute personne faisant une remarque procédurière sur les procédures du sujet se verra infliger un blâme1

1.Pas besoin de donner de nom, mon zèle amusé disparu.