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 là.
Bitboards
- 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.
Description du projet
- 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.
standard
ou swap
). La boucle de jeu
devra suivre le pseudo-algorithme suivant :
|
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) // ... |
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
- 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.
/ -- Base directory Makefile -- Global Makefile /src -- Source files /install -- Install directory (should be empty on the repository)
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.
./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émarrageswap
, sinon le jeu se joue avec les règlesstandard
. - 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.
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. |