Manṣūba et Shatranj
![]() |
![]() |
Jeu de Shatranj (image Wikimedia) |
Jeu de dames chinoises (image Wikimedia) |
Mondes et relations
-
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
etHEIGHT
, de manière à ce que les positions puissent être arrangées surHEIGHT
lignes de largeurWIDTH
. Le nombre total de positions possiblesWORLD_SIZE
est défini comme le produitWIDTH*HEIGHT
. Les positions du monde sont indexées par un nombre entier compris entre0
etWORLD_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) |
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).
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.
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
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)
-
Écrire des méthodes pour transformer les positions et les directions en chaînes de caractères
Pour cela, il faut créer un fichiergeometry.c
qui implémente les deux fonctions*_to_string
dont les prototypes sont définis dansgeometry.h
. -
Créer des mondes et des relations
Lesdits mondes et relations doivent respecter (sans les modifier) les interfacesworld.h
etneighbors.h
spécifiées dans la section Mondes et relations. Il est conseillé de construire chaque objet séparément et d'écrire un exécutable testant son fonctionnement. -
Créer des ensembles de positions sous la forme d'un type abstrait de données.
Le sujet fait intervenir à plusieurs moments des listes de positions dans le monde : pour les positions initiales des joueurs, pour la liste courante des pièces dont ils disposent, ou pour la liste des mouvements disponibles pour une pièce. Écrire un type ensemble adapté pour ces différentes situations, en proposant une interface raisonnable. -
Calculer l'ensemble des mouvements possibles pour une pièce donnée.
Il est évidemment nécessaire d'utiliser les fonctions de l'interfaceneighbors.h
pour pouvoir faire ce calcul, en particulier lorsqu'il s'agit de "sauter" par dessus une autre pièce. -
Spécifier des positions de départ et des conditions de victoire pour les joueurs.
Il doit pouvoir être facile de changer les positions de départ des deux joueurs. Des programmes de test peuvent alors être réalisés, créant des positions de jeux variées, et vérifiant les coups réalisables depuis ces positions, et si elles sont (ou pas) gagnantes. -
Mettre en place la boucle de jeu.
Écrire le code nécessaire pour pouvoir réaliser une partie complète, et afficher le vainqueur sur la sortie standard. Le nombre de tours maximal d'une partie doit être paramétrable.
Achievement 1 : Mettons nous aux pièces
![]() |
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. |
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.
- 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
, ouSOUTH+SOUTH
). Le fait que la position intermédiaire soit occupée ou pas n'empêche pas le saut3.
Achievement 2 : Il faut avoir de bonnes relations
![]() |
![]() |
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
- 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.
Achievement 4 : Allons droit au coeur
Achievement 5 : Travaux d'intérêt général
- 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
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
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
Écriture du code
-
Le code devra être organisé en répertoires de la manière suivante :
Sans surprise, le répertoire
Makefile src/ src/geometry.h src/neighbors.h src/world.h tst/
src
correspond au code source, tandis que le répertoiretst
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 :
La version de base est considérée comme l'achievement 0, les autres achievements sont numérotés à partir de 1.git tag achiev0 # Create tag 'achiev0' git push --tags # Push tags on server git tag # List available tags
Les tags marquent les achievements réalisés, et suivent une syntaxe bien particulière, à savoirachiev[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 encoreachiev0.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.
getopt
(voirgetopt(3)
etgetopt_log(3)
). La page de manuel degetopt
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)
- un paramètre optionnel
-
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'environnementWIDTH
etHEIGHT
. Ainsi, la ligne suivante doit produire un exécutable jouant sur un plateau de taille 40 par 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.make WIDTH=40 HEIGHT=30
-
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 commandemake test
.
-
Une règle principale permettant de compiler l'exécutable
appelé
Contact
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. |