Available nodes

 Manṣūba et Shatranj

Un manṣūba (en Persan مَنصوبة selon Wikipedia, une bien jolie écriture) est un exercice de réflexion consistant à trouver comment mettre l'adversaire mat dans une partie de shatranj (شترنج), un ancestre perse des échecs1. Il existe de nombreux sites mettant en valeur de tels exercices de réflexion, comme par exemple Lichess pour le jeu d'échecs moderne. Et plus généralement, le principe de tels exercices peut s'appliquer de manière variée, dans des jeux comme les échecs (qu'ils soient persans ou martiens), les dames (qu'elles soient anglaises, brésiliennes, canadiennes, chinoises, russes ...), voire plus si affinités2. L'objectif de ce projet est de s'intéresser à ces jeux de plateaux avec des pièces qui se déplacent de manière plus ou moins loufoques, tout en remplissant des objectifs variés.
Jeu de Shatranj (image Wikimedia)
Jeu de dames chinoises (image Wikimedia)
Ce projet n'a pas pour but de résoudre des parties d'un jeu particulier. Il propose de réaliser un ensemble de structures de données et d'algorithmes permettant de jouer à des jeux un peu génériques, jeux qui, avec un peu de chance et de persévérance, pourraient ressembler aux références existantes. Néanmoins, puisqu'il faut bien commencer quelque part, le projet se base sur une version généralisée des Dames Chinoises.
À propos des achievements : ce sujet de projet est construit sur la notion d'achievement. Un achievement est un ensemble de fonctionnalités à développer pour le projet. Les achievements doivent être réalisés dans l'ordre, et de manière cumulative. Ils seront débloqués à chaque fois qu'au moins une équipe de projet aura rempli les conditions de l'achievement précédent et aura fait valider la chose par son encadrant. La version de base correspond à l'achievement initial. L'évaluation du projet est basée en partie sur le nombre d'achievements réalisés, et la version de base n'est pas forcément représentative du travail nécessaire pour atteindre la moyenne.

 Mondes et relations

Le plateau de jeu (en anglais board) dans lequel les joueurs s'opposent est composé de deux morceaux distincts :
  • Un monde (en anglais world) qui représente l'ensemble des positions (en anglais places) sur lesquelles les joueurs peuvent jouer. Le monde est caractérisé par deux constantes WIDTH et HEIGHT, de manière à ce que les positions puissent être arrangées sur HEIGHT lignes de largeur WIDTH. Le nombre total de positions possibles WORLD_SIZE est défini comme le produit WIDTH*HEIGHT. Les positions du monde sont indexées par un nombre entier compris entre 0 et WORLD_SIZE-1. Le monde est unique pour toute la partie.
  • Une relation entre les positions du monde. La relation indique comment les positions sont reliées entre elles, et dans quelles directions. Deux positions reliées entre elles sont dits voisines. Chaque position a un nombre maximal MAX_NEIGHBORS de voisins fixé à 8. A partir d'une position donnée, si on part dans des directions différentes, on atteint des voisins différents. Il est aussi possible de n'avoir aucun voisin dans une direction donnée. Par exemple, dans la grille carrée, toutes les positions ont des voisins dans les 4 directions cardinales, sauf sur les bords (3 voisins) et dans les coins (2 voisins).
Un monde Une relation (vue d'artiste)
Dans la version de base, le plateau de jeu est une simple grille 2D de dimensions WIDTH et HEIGHT. On considère deux joueurs avec les couleurs WHITE et BLACK. Chaque joueur dispose d'un ensemble de positions de départ de sa couleur sur le plateau au nombre de HEIGHT. Les pions du joueur BLACK (resp. WHITE) sont disposés initialement sur la première (resp. dernière) colonne du monde. Une position est dite libre si elle est incolore et sans pièce. Les joueurs jouent chacun à leur tour, l'ordre de jeu étant décidé aléatoirement. A chaque tour, un joueur déplace un de ses pions. Les pions peuvent se déplacer des manières suivantes :
  • Déplacement simple : en allant sur une position voisine au sens de la relation. Si la position en question n'est pas libre, le mouvement n'est pas possible.
  • Saut simple : en sautant par dessus un autre pion. Pour cela, le pion se translate deux fois dans la même direction. Si, pour une raison quelconque, il n'est pas possible de se translater deux fois dans la même direction (par exemple, la direction n'existe pas depuis la position intermédiaire, ou la position d'arrivée n'est pas libre), le saut est impossible.
  • Saut multiple : en répétant une suite de sauts simples, en nombre quelconque, amenant forcément à déplacer le pion (une suite de sauts qui revient au point de départ n'est pas considéré comme un déplacement).
Un joueur qui ne peut pas jouer le pion qu'il a choisi de jouer passe son tour. Au début de la partie, on fixe un nombre maximal de tours MAX_TURNS, valant par défaut 2*WORLD_SIZE. Il existe deux conditions de victoire, décidées en début de partie :
  • Victoire simple : le vainqueur est le premier joueur à atteindre avec l'un de ses pions l'une des positions de départ de l'autre joueur avant MAX_TURNS tours.
  • Victoire complexe : le vainqueur est le premier joueur à recouvrir avec ses pions l'ensemble des positions de départ de l'autre joueur avant MAX_TURNS tours.
Si aucun joueur n'a gagné avant MAX_TURNS tours, la partie est un match nul.

Les constantes géométriques définissant le monde sont fixées par un fichier geometry.h. Ce fichier ne doit pas être modifié (mais il est possible de modifier les constantes en utilisant la bonne commande de compilation). Les mondes doivent être implémentés en suivant une interface définie dans le fichier world.h. A noter que le type struct world_t est abstrait et ne peut être défini que dans un fichier world.c. Les relations doivent être implémentées en suivant une interface définie dans le fichier neighbors.h. Dans cette dernière, la fonction init_neighbors(int seed) sert à initialiser la relation en début de partie en fixant seed à 0, puis éventuellement à modifier la relation en milieu de partie. Au début, il est possible que cette fonction ne fasse rien.

 Base version

Pour valider la version de base du projet, il est demandé de produire un programme avec les caractéristiques décrites dans ce paragraphe.

Ledit programme doit mettre en place une boucle permettant de jouer une partie entre deux joueurs en suivant les règles précédemment énoncées. Toute décision impliquant plusieurs choix possibles sera prise de manière aléatoire. Le pseudo-algorithme de la boucle principale est le suivant :

w = world_init();
init_neighbors(0); // Use seed 0 at the beginning of a game
current_player = get_random_player();
while nobody has won:
  p = choose_random_piece_belonging_to(w, current_player)
  m = choose_random_move_for_piece(w, p)
  move_piece(w, m)
  current_player = next_player(current_player)
Le projet suggère la décomposition des tâches suivante :

 Achievement 1 : Mettons nous aux pièces

Tel qu'il est construit, le jeu offre des possibilités assez restreintes : toutes les pièces sont les mêmes, et ont les mêmes possibilités de mouvement. Or, dans le jeu de Shatranj comme dans de nombreux jeux de société, il existe plusieurs types de pièces différentes, ce qui autorise un peu de folie :
Pièces du jeu de Shatranj / Image tirée du James' History of Chess. De gauche à droite, un shah ou roi, un ferz ou conseiller, un alfil ou éléphant, un faras ou cavalier, un rukh ou tour, et un sarbaz ou pion.
Écrire le code permettant d'avoir plusieurs types de pièces en jeu. Pour cette partie du projet, il est autorisé de modifier la liste des pièces possibles dans geometry.h (mais uniquement l'énumération sort_t). Les pièces de types différents sont censées avoir des déplacements différents. Les positions de départ des joueurs sont laissées libre au programmeur, mais elles doivent être symétriques, à savoir que chaque joueur possède le même ensemble de pièces, et utiliser le plus possible de types de pièces existant. Il n'est pas demandé à ce que le positionnement des pièces elle-mêmes en début de partie soit symétrique.

Implémenter le mouvement d'une tour dont les déplacements sont les suivants :

  • Translation cardinale : la tour peut se déplacer d'autant de cases qu'elle désire dans les directions cardinales, tant qu'elle n'est pas bloquée par une autre pièce sur son chemin.
Implémenter le mouvement d'un éléphant dont les déplacements sont les suivants :
  • Saut semi-diagonal : l'éléphant peut se déplacer sur toutes les positions libres à partir de sa position en suivant deux directions cardinales (par exemple NORTH+EAST, ou SOUTH+SOUTH). Le fait que la position intermédiaire soit occupée ou pas n'empêche pas le saut3.
Les développeurs sont laissés libres d'implémenter d'autres types de pièces. Comme bonus pour des parties plus originales, ils peuvent aussi permettre de spécifier une manière de choisir les ensembles de positions de départ pour les joueurs.

 Achievement 2 : Il faut avoir de bonnes relations

Les jeux de société peuvent avoir des plateaux de jeu variés. Ainsi, les Dames Chinoises se jouent classiquement sur un pavage triangulaire avec un bord étoilé. Mais c'est un peu limitatif, car il existe une large variété de créer des plateaux un peu réguliers. Par exemple, il existe toute une famille de motifs de carrelage de salle de bain représentables par des pavages euclidiens (qui permettent donc de paver des rectangles et des salles de bains de taille plus ou moins arbitraires) :
Mais il existe des manières bien plus radicales de fixer les relations. Ainsi, dans le jeu Full Metal Planète, le niveau de l'eau change au fur et à mesure de la partie, modifiant la relation de jeu, et rendant certaines parties du plateau inaccessibles (ou au contraire facilitant certains accès), changeant ainsi radicalement les mouvements possibles et donc les stratégies de jeu.

Implémenter au moins 3 relations différentes, parmi lesquelles la grille classique et la grille triangulaire. Les autres relations implémentées sont laissées libres aux développeurs. Pour cet achievement, il est autorisé de modifier la valeur de MAX_RELATIONS dans le fichier neighbors.h. Le code utilisera la fonction init_neighbors pour modifier la relation de jeu. La relation sera initialisée aléatoirement en début de partie. Une relation n'est pas forcée d'utiliser la totalité des positions de jeu, il est toujours possible de faire que ces positions n'aient aucun voisin4. Une relation peut faire qu'une pièce n'ait aucun mouvement possible. Noter que pour chaque relation nouvellement créée, il faut définir des positions de départ pour chaque joueur.

Comme bonus, et pour pimenter l'action de jeu, tous les sqrt(MAX_TURNS), la relation change pour une autre qui soit différente et tirée au hasard. Noter que dans ce cas, les positions de départ peuvent changer entre le début et la fin de partie, et donc en particulier être temporairement inaccessibles si elles sont définies à la légère.

 Achievement 3 : Ne nous laissons pas prendre à revers

Le système de jeu actuel reste statique au sens où l'ensemble des pièces en jeu est statique : le plateau contient, du début à la fin de la partie, le même nombre de pièces. On propose de faire évoluer cela, en permettant à des pièces de capturer d'autres pièces. Concrètement, on ajoute deux mouvements possibles :
  • Capture simple : tout mouvement de la pièce qui se termine sur une case contenant une pièce d'une couleur différente capture la pièce en question. Celle-ci devient alors prisonnière. Il n'est pas possible de faire prisonnier une pièce se trouvant sur une des positions de départ d'un des joueurs.
  • Tentative d'évasion  : si une pièce est prisonnière, elle peut tenter de s'évader. L'évasion ne peut se faire qu'à la condition que la position où elle a été capturée soit libre. Ce mouvement réussit avec une probabilité de 50% tirée au hasard. S'il rate, la pièce reste prisonnière sans modification du plateau.
Il n'y a pas de limite au nombre de prisonniers qui peuvent être faits (hormis le nombre maximal de pièces initialement allouées aux joueurs). Les évasions doivent laisser une chance aux joueurs de gagner une victoire complexe même s'ils se font capturer leurs pièces.

 Achievement 4 : Allons droit au coeur

Ces déplacements aléatoires des pièces n'amènent pas à des parties très intéressantes. Vu que l'objectif d'un joueur est d'atteindre les positions adverses, faisons que les pièces se déplacent de manière à se rapprocher autant que possible de ces positions. Dorénavant, lorsqu'il est question de choisir le mouvement d'une pièce, il faut choisir aléatoirement l'un des mouvements qui la rapproche le plus possible d'une des positions adverses libres.

Les distances entre deux positions sont calculées avec les relations, en comptant le nombres de déplacements simples nécessaires pour transiter de la première position à la seconde.

Comme bonus, précalculer les distances à l'arrivée de toutes les cases pour les différents joueurs, de manière à ne pas avoir à les recalculer à chaque coup.

Comme bonus plus ardu, calculer les distances en fonction du nombre de coups nécessaires à la pièce pour transiter de la première position à la seconde (et donc pas seulement de déplacements simples).

 Achievement 5 : Travaux d'intérêt général

Dans son état, notre exécutable est devenu extrêmement générique, mais il n'y a pas vraiment de façon de contrôler toutes ses possibilités. Dans cet achievement, on propose de mettre en place un système de configurations permettant de définir les règles d'un jeu donné. Par exemple
  • une partie de dames chinoises se fera avec uniquement des pions, ayant des déplacements simples, à saut et à saut multiples, sur une grille triangulaire, sans possibilité de capture;
  • une partie d'échecs se fera avec des pièces d'échecs, pas de saut multiple, une grille carrée, et une possibilité de capture.5
Pour cela, on propose de construire ces configurations de la manière suivante : on décrit l'ensemble des mouvements d'une pièce à l'aide d'un ensemble de pointeurs de fonctions. Une pièce possède un ensemble de mouvements possibles parmi au plus MAX_MOVE_TYPES (valant 3), décrits à chaque fois par des pointeurs de fonctions. Par exemple, dans la version de base, une pièce a trois mouvements possibles : déplacement simple, saut simple et saut multiple. Une configuration définit une liste de pièces utilisées pour une partie, et pour chaque pièce ses mouvements possibles. Accessoirement, on demande à vouloir spécifier les conditions de victoire dans ces configurations, encore une fois avec des pointeurs de fonctions.

Implémenter de telles configurations, et permettre à votre exécutable de s'exécuter dans une configuration particulière en passant une option en ligne de commande, par exemple :

./project         # Should run a game with the rules described in the base version
./project -c 1    # Should run a game in the configuration labeled by "1"
  

 Achievement 6 : Courir plusieurs lièvres à la fois

Étendre les possibilités de jeu pour permettre de jouer à plus de deux joueurs. Le nombre maximal de joueurs est fixé à MAX_PLAYERS valant 5, et cette constante peut être modifiée dans geometry.h.

Le principal problème de cet extension vient de la manière de spécifier l'ensemble des positions de départ des différents joueurs. A partir de cet achievement, et plutôt que de laisser trop de liberté, on considère une nouvelle définition des positions de départ. L'ensemble des positions de départ d'un joueur sont définies comme les NUM_PIECES positions les plus proches d'une position initiale servant de graine initiale. Les graines sont réparties sur le plateau de manière à maximiser la distance minimale entre deux graines, comme dans le problème des dictateurs ennemis. Le projet fixe NUM_PIECES à HEIGHT. Il est possible qu'un plateau particulier empêche de trouver de telles positions de départ, auquel cas la partie ne peut être jouée.

Une extension de cet achievement consisterait à précalculer les positions des graines pour une famille de plateaux de jeu possibles, de façon à ne pas avoir à recalculer leur position à chaque fois.

 Achievement 7 : La question qui tue

Ecrire un algorithme permettant de générer des mansuba de manière à ce que l'adversaire ne puisse pas gagner. Toute latitude est laissée pour choisir des algorithmes efficaces permettant de générer des positions de jeu impossibles.

 Écriture du code

Le code écrit est censé respecter les standards de codage suivant :
  • Le code devra être organisé en répertoires de la manière suivante :
        Makefile
        src/
        src/geometry.h
        src/neighbors.h
        src/world.h
        tst/
    
    Sans surprise, le répertoire src correspond au code source, tandis que le répertoire tst doit contenir le code nécessaire aux tests. Les différents achievements devront être marqués dans le dépôt à l'aide d'étiquettes (ou tags) git. Ajouter une étiquette se fait avec les commandes suivantes :
    git tag achiev0    # Create tag 'achiev0'
    git push --tags    # Push tags on server
    git tag            # List available tags
    
    La version de base est considérée comme l'achievement 0, les autres achievements sont numérotés à partir de 1.
    Les tags marquent les achievements réalisés, et suivent une syntaxe bien particulière, à savoir achiev[0-9\.]+. Noter qu'une fois un tag mis sur le dépôt, il n'est plus possible de le modifier. Seul le code avec le dernier tag sera considéré pour le rendu final. S'il n'existe pas de tel tag, il sera considéré qu'il n'y a pas de code rendu. Un projet sans code rendu ne valide pas les projets. Afin de simplifier la vie, la syntaxe des tags autorise les tags suivants correspondant tous à l'achievement 0 : achiev0, achiev0.1 ou encore achiev0.1.2.3.4.
  • L'exécutable du projet doit se nommer project, doit pouvoir exécuter une partie du jeu décrit dans ce projet. En plus de cela, il doit pouvoir prendre comme paramètres optionnels :
    • un paramètre optionnel -s pour initialiser le générateur aléatoire.
    • un paramètre optionnel -t pour fixer le type de victoire (s déclare une victoire simple, c une victoire complexe).
    • un paramètre optionnel -m pour fixer le nombre maximal de tours.
    L'analyse de la ligne de commande se fera au moyen de la bibliothèque getopt (voir getopt(3) et getopt_log(3)). La page de manuel de getopt donne un exemple de code d'utilisation. Les exemples suivants donnent des idées sur les possibilités d'utilisation :
    ./project                   # No parameters, world WIDTH*HEIGHT, MAX_TURNS equal to 2*WIDTH*HEIGHT,
                                # random initialization of the RNG, simple victory condition
    ./project -s 156 -m 10 -t c # One optional parameter for MAX_TURNS (here 10),
                                # an optional parameter to set the victory type (here 'c' for 'complex')
                                # and an optional parameter to initialize the RNG (here 156)
    
  • Le dépôt doit contenir un fichier Makefile permettant de compiler et d'exécuter les tests. Pour cela, il devra comporter au moins les règles ci-après :
    • Une règle principale permettant de compiler l'exécutable appelé project décrit ci-avant. La règle doit permettre de paramétrer les tailles des mondes en passant deux variables d'environnement WIDTH et HEIGHT. Ainsi, la ligne suivante doit produire un exécutable jouant sur un plateau de taille 40 par 30 :
      make WIDTH=40 HEIGHT=30
      Le fichier Makefile fourni en exemple permet déjà de réaliser ce paramétrage. Il conviendra à chacun de comprendre comment il fonctionne ou de poser la question à un de ses encadrants.
    • Une règle test lançant l'ensemble des tests pour le dernier achievement réalisé. Il est tout à fait envisageable d'avoir plusieurs exécutables de tests différents, mais ils devront tous être lancés par la commande make test.
Un code qui ne compile pas est un code sans intérêt, et un code qui n'intéresse pas le responsable des projets est un code qui ne valide pas les projets.

 Contact

Pour toute information complémentaire, contacter : David RENAULT disponible aux séances d'encadrement le mardi et le vendredi.

1.Dans lequel, les pièces qui se déplacent en diagonale et qui ont été remplacées par des fous aux échecs étaient des éléphants.
2.'Votre kilométrage peut fluctuer' comme ne disent pas les anglais.
3.Ces éléphants sont particulièrement agiles.
4.Ce qui autorise par exemple d'écrire une relation réalisant un simple chemin entre les deux joueurs, par exemple pour tester des déplacements.
5.La capture définie à l'achievement 3, et pas la capture classique des échecs.