Tp-6-echecs

TP - Le roi des jeux, le jeu des rois

Bienvenu à ce TP au sujet des du jeu d'échecs dont nous allons explorer diverses facettes liées à la programmation.

En termes de programmation, voici quelques notions que ce TP couvre:

  • formatage de chaînes de caractères
  • parsing de chaînes de caractères
  • transformation d'une lettre en son code ASCII et vice-versa (encodage de caractères)
  • mise en forme de chaînes de caractères avec la méthode format de la classe str
  • dictionnaire: parcours, création, ...
  • l'utilisation de la fonction range en conjonction avec for notamment

Il n'est, bien entendu pas nécessaire de savoir jouer pour faire ce TP (programmer, oui), mais n'hésitez pas à vous lancer au cas où cela vous intéresse. Des ressources pratiques pour apprendre les règles se trouvent par exemple ici et vous pouvez rejoindre l'équipe de l'ESIG sur Lichess, quelque soit votre niveau : https://lichess.org/team/esig-chess.

I. La légende des origines

Le jeu d'éches est vieux et il existe plusieurs légendes concernant son origine. Voici la légende du Brahmane Sissa, selon un article wikipédia:

La légende la plus célèbre sur l'origine du jeu d'échecs raconte l'histoire d'un roi légendaire des Indes (appelé Balhait ou Shihram suivant les versions de la légende) qui cherchait à tout prix à tromper son ennui. Il promit donc une récompense exceptionnelle à qui lui proposerait une distraction qui le satisferait. Lorsque le sage Sissa, fils du Brahmane Dahir, lui présenta le jeu d'échecs, le souverain, enthousiaste, demanda à Sissa ce que celui-ci souhaitait en échange de ce cadeau extraordinaire. Humblement, Sissa demanda au prince de déposer un grain de riz sur la première case, deux sur la deuxième, quatre sur la troisième, et ainsi de suite pour remplir l'échiquier en doublant la quantité de grain à chaque case. Le prince accorda immédiatement cette récompense en apparence modeste, mais son conseiller lui expliqua qu'il venait de signer la mort du royaume car les récoltes de l'année ne suffiraient à s'acquitter du prix du jeu. En effet, sur la dernière case de l'échiquier, il faudrait déposer 263 graines, soit plus de neuf milliards de milliards de grains (9 223 372 036 854 775 808 grains précisément), et y ajouter le total des grains déposés sur les cases précédentes, ce qui fait un total de 18 446 744 073 709 551 615 grains (la formule de calcul est alors 264-1) ou bien plus de 1 000 fois la production mondiale de 2012 ou alors, 31 fois le PIB mondial de 2014 au prix du grain de riz actuel en France !

Votre première tâche consiste à créer une fonction avec un nom pertinent dans un fichier historique.py qui affiche le nombre de grains présents sur chaque case de l'échiquier ainsi que la somme des graines de toutes les cases. Sachez qu'un échiquier possède 8 lignes et 8 colonnes.

Contraintes:

Sortie attendue:

Case 1: 1.000e+00 (1)
Case 2: 2.000e+00 (2)
Case 3: 4.000e+00 (4)
Case 4: 8.000e+00 (8)
Case 5: 1.600e+01 (16)
Case 6: 3.200e+01 (32)
Case 7: 6.400e+01 (64)
Case 8: 1.280e+02 (128)
Case 9: 2.560e+02 (256)
Case 10: 5.120e+02 (512)
Case 11: 1.024e+03 (1024)
Case 12: 2.048e+03 (2048)
Case 13: 4.096e+03 (4096)
Case 14: 8.192e+03 (8192)
Case 15: 1.638e+04 (16384)
Case 16: 3.277e+04 (32768)
Case 17: 6.554e+04 (65536)
Case 18: 1.311e+05 (131072)
Case 19: 2.621e+05 (262144)
Case 20: 5.243e+05 (524288)
Case 21: 1.049e+06 (1048576)
Case 22: 2.097e+06 (2097152)
Case 23: 4.194e+06 (4194304)
Case 24: 8.389e+06 (8388608)
Case 25: 1.678e+07 (16777216)
Case 26: 3.355e+07 (33554432)
Case 27: 6.711e+07 (67108864)
Case 28: 1.342e+08 (134217728)
Case 29: 2.684e+08 (268435456)
Case 30: 5.369e+08 (536870912)
Case 31: 1.074e+09 (1073741824)
Case 32: 2.147e+09 (2147483648)
Case 33: 4.295e+09 (4294967296)
Case 34: 8.590e+09 (8589934592)
Case 35: 1.718e+10 (17179869184)
Case 36: 3.436e+10 (34359738368)
Case 37: 6.872e+10 (68719476736)
Case 38: 1.374e+11 (137438953472)
Case 39: 2.749e+11 (274877906944)
Case 40: 5.498e+11 (549755813888)
Case 41: 1.100e+12 (1099511627776)
Case 42: 2.199e+12 (2199023255552)
Case 43: 4.398e+12 (4398046511104)
Case 44: 8.796e+12 (8796093022208)
Case 45: 1.759e+13 (17592186044416)
Case 46: 3.518e+13 (35184372088832)
Case 47: 7.037e+13 (70368744177664)
Case 48: 1.407e+14 (140737488355328)
Case 49: 2.815e+14 (281474976710656)
Case 50: 5.629e+14 (562949953421312)
Case 51: 1.126e+15 (1125899906842624)
Case 52: 2.252e+15 (2251799813685248)
Case 53: 4.504e+15 (4503599627370496)
Case 54: 9.007e+15 (9007199254740992)
Case 55: 1.801e+16 (18014398509481984)
Case 56: 3.603e+16 (36028797018963968)
Case 57: 7.206e+16 (72057594037927936)
Case 58: 1.441e+17 (144115188075855872)
Case 59: 2.882e+17 (288230376151711744)
Case 60: 5.765e+17 (576460752303423488)
Case 61: 1.153e+18 (1152921504606846976)
Case 62: 2.306e+18 (2305843009213693952)
Case 63: 4.612e+18 (4611686018427387904)
Case 64: 9.223e+18 (9223372036854775808)
Total : 1.845e+19 (18446744073709551615)

II. Représenter des positions avec la notation FEN

Il existe différentes manière de représenter des positions ou des parties d'échecs. Une position est une configuration particulière de pièces sur l'échiqier. Comme les ordinateurs n'ont pas (encore) beaucoup de facilité d'interpréter rapidement des informations visuelles avec précision, il existe différentes manières de noter des positions, selon les besoins.

La notation FEN est l'une des plus répandue. Il s'agit d'un standard compris par la quasi-totalité des logiciels d'échecs.

Par exemple, l'éditeur de position gratuit de lichess.org permet de modifier graphiquement une position et voir la notation FEN correspondante. Il est également possible d'importer une position sous forme de FEN.

Voici une URL vers la position initiale: https://lichess.org/editor/rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR_wKQkq-_0_1

Lisez l'article Wikipédia qui explique les détails de cette notation. Nous allons dans un premier temps ignorer les informations en fin de chaîne qui correspondent à des règles un peu plus avancées du jeu (roque, capture en passant, compteur de coups) et nous concentrer uniquement sur le placement de pièces ainsi que l'indication de la couleur qui va jouer le prochain coup.

Validation d'un enregistrement FEN

Complétez le fichier positions.py: écrivez et testez une fonction qui valide la première partie d'un enregistrement FEN (sans les informations complémentaires). En particulier, les dimensions 8x8 de l'échiquier et le pièces sont limitées à celles qui existent (pions, fous, tours, cavaliers, dames et rois).

Bien sûr que la fonction retourne une valeur de type booléen et qu'il faut produire des sorties pertinentes depuis le programme principal.

La méthode prédéfine split peut servir ici.

Exemples d'enregistrements valides:

Exemples d'enregistrements invalides:

  • rnbqkbnr/pppppppp/8/8/8/8/PPPPPZPP/RNBQKBNR w KQkq - 0 1
  • rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKNR w KQkq - 0 1 (manque un fou blanc)
  • 8/8/5k1/6qK/8/8/8/8 w - - 0 1 (manque une case à la troisième ligne)
  • 8/8/5k2/6qK/8/8/8 w - - 0 1 (manque une ligne)
  • 8/8/5k2/7qK/8/8/8/8 w - - 0 1 (4ème ligne trop longue)
  • rnbqkbnr/ppppppppp|8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
  • r1bqkbnr/pppp1.0ppp/2n5/4p3/2B1P3/5N2/PPPP1PPP/RNBQK2R b KQkq - 3 3
  • rnbqkbnr/pppppppp/8/8/10/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

Représentation 2D (à la console)

Sur la base d'un enregistrement FEN, nous allons maintenant produire un affichage "graphique" à la console (avec des prints).

Exemples de sorties produites:

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
r n b q k b n r
p p p p p p p p
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
P P P P P P P P
R N B Q K B N R

8/8/5k2/6qK/8/8/8/8 w - - 0 1
. . . . . . . .
. . . . . . . .
. . . . . k . .
. . . . . . q K
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .

r1bqkbnr/pppp1ppp/2n5/4p3/2B1P3/5N2/PPPP1PPP/RNBQK2R b KQkq - 3 3
r . b q k b n r
p p p p . p p p
. . n . . . . .
. . . . p . . .
. . B . P . . .
. . . . . N . .
P P P P . P P P
R N B Q K . . R

Représentation sous forme de liste

Il est également possible de représenter une position sous forme de liste.

Une possibilité est d'utiliser une liste de 64 éléments et représenter chaque case vide par None et chaque pièce par un numéro.

Voici une dictionnaire qui montre comment un symbole FEN est représenté dans la liste (nous conseillons de l'utiliser):

{'1': None, '2': None, '3': None, '4': None, '5': None, '6': None, '7': None, '8': None,
            'p': 16, 'r': 13, 'n': 15, 'b': 14, 'q': 12, 'k': 11,
            'P': 26, 'R': 23, 'N': 25, 'B': 24, 'Q': 22, 'K': 21}

Une difficulté est l'ordre de représentation. Dans la notation FEN, nous commençons par les lignes du côté des noirs (en haut) de l'échiquier. Notre liste, en revanche, doit commencer par les lignes en bas de l'échiquier (du côté des blancs). Selon la notation algébrique expliquée par le diagramme ci-dessous, nous pouvons dire que FEN représente les cases dans l'ordre a8, b8, ..., h8, a7, ..., h7, ..., a1, ... h1 alors que dans la liste l'ordre sera a1, ..., h1, a2, ..., h2, ..., a8, ..., h8.

Échiquier avec notation algébrique (_Wikipédia_)

Voici des exemples:

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
r n b q k b n r 
p p p p p p p p 
. . . . . . . . 
. . . . . . . . 
. . . . . . . . 
. . . . . . . . 
P P P P P P P P 
R N B Q K B N R 

devient:

[23, 25, 24, 22, 21, 24, 25, 23, 26, 26, 26, 26, 26, 26, 26, 26, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, 16, 16, 16, 16, 16, 16, 16, 16, 13, 15, 14, 12, 11, 14, 15, 13]

8/8/5k2/6qK/8/8/8/8 w - - 0 1
. . . . . . . . 
. . . . . . . . 
. . . . . k . . 
. . . . . . q K 
. . . . . . . . 
. . . . . . . . 
. . . . . . . . 
. . . . . . . . 

devient:

[None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, 12, 21, None, None, None, None, None, 11, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]

r1bqkbnr/pppp1ppp/2n5/4p3/2B1P3/5N2/PPPP1PPP/RNBQK2R b KQkq - 3 3
r . b q k b n r 
p p p p . p p p 
. . n . . . . . 
. . . . p . . . 
. . B . P . . . 
. . . . . N . . 
P P P P . P P P 
R N B Q K . . R 

devient:

[23, 25, 24, 22, 21, None, None, 23, 26, 26, 26, 26, None, 26, 26, 26, None, None, None, None, None, 25, None, None, None, None, 24, None, 26, None, None, None, None, None, None, None, 16, None, None, None, None, None, 15, None, None, None, None, None, 16, 16, 16, 16, None, 16, 16, 16, 13, None, 14, 12, 11, 14, 15, 13]

Ecrivez donc une fonction fen2list qui prend en paramètre un enregistrement FEN et qui retourne une liste selon le format décrit.

Conseils:

  • Utilisez le dictionnaire donné dans cet énoncé ainsi que le dictionnaire DICT_SYMBOLE_NBCASES du fichier fourni.
  • Utilisez le slicing pour parcourir la liste contenant les lignes du FEN dans l'ordre inverse.

Représentation sous forme de dictionnaire

Nous avons vu que les listes ne sont pas forcément pratique, car beaucoup d'espace est occupé par la valeur None.

Une autre représentation est sous forme de dictionnaire où nous avons des entrées uniquement pour les cases où se trouve une pièce.

Un exemple de ce genre de dictionnaire est proposé dans un tutoriel d'Openclassrooms. Nous allons utiliser ce format, sauf qu'à la place d'écrire "tour blanche", nous utiliserons les symboles FEN correspondants ("R" dans l'exemple).

Voici pour nos exemples (constatez en particulier la représentation succincte de la deuxième position):

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
r n b q k b n r 
p p p p p p p p 
. . . . . . . . 
. . . . . . . . 
. . . . . . . . 
. . . . . . . . 
P P P P P P P P 
R N B Q K B N R 
[23, 25, 24, 22, 21, 24, 25, 23, 26, 26, 26, 26, 26, 26, 26, 26, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, 16, 16, 16, 16, 16, 16, 16, 16, 13, 15, 14, 12, 11, 14, 15, 13]
{('a', 1): 'R', ('b', 1): 'N', ('c', 1): 'B', ('d', 1): 'Q', ('e', 1): 'K', ('f', 1): 'B', ('g', 1): 'N', ('h', 1): 'R', ('a', 2): 'P', ('b', 2): 'P', ('c', 2): 'P', ('d', 2): 'P', ('e', 2): 'P', ('f', 2): 'P', ('g', 2): 'P', ('h', 2): 'P', ('a', 7): 'p', ('b', 7): 'p', ('c', 7): 'p', ('d', 7): 'p', ('e', 7): 'p', ('f', 7): 'p', ('g', 7): 'p', ('h', 7): 'p', ('a', 8): 'r', ('b', 8): 'n', ('c', 8): 'b', ('d', 8): 'q', ('e', 8): 'k', ('f', 8): 'b', ('g', 8): 'n', ('h', 8): 'r'}

8/8/5k2/6qK/8/8/8/8 w - - 0 1
. . . . . . . . 
. . . . . . . . 
. . . . . k . . 
. . . . . . q K 
. . . . . . . . 
. . . . . . . . 
. . . . . . . . 
. . . . . . . . 
[None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, 12, 21, None, None, None, None, None, 11, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
{('g', 5): 'q', ('h', 5): 'K', ('f', 6): 'k'}

r1bqkbnr/pppp1ppp/2n5/4p3/2B1P3/5N2/PPPP1PPP/RNBQK2R b KQkq - 3 3
r . b q k b n r 
p p p p . p p p 
. . n . . . . . 
. . . . p . . . 
. . B . P . . . 
. . . . . N . . 
P P P P . P P P 
R N B Q K . . R 
[23, 25, 24, 22, 21, None, None, 23, 26, 26, 26, 26, None, 26, 26, 26, None, None, None, None, None, 25, None, None, None, None, 24, None, 26, None, None, None, None, None, None, None, 16, None, None, None, None, None, 15, None, None, None, None, None, 16, 16, 16, 16, None, 16, 16, 16, 13, None, 14, 12, 11, 14, 15, 13]
{('a', 1): 'R', ('b', 1): 'N', ('c', 1): 'B', ('d', 1): 'Q', ('e', 1): 'K', ('h', 1): 'R', ('a', 2): 'P', ('b', 2): 'P', ('c', 2): 'P', ('d', 2): 'P', ('f', 2): 'P', ('g', 2): 'P', ('h', 2): 'P', ('f', 3): 'N', ('c', 4): 'B', ('e', 4): 'P', ('e', 5): 'p', ('c', 6): 'n', ('a', 7): 'p', ('b', 7): 'p', ('c', 7): 'p', ('d', 7): 'p', ('f', 7): 'p', ('g', 7): 'p', ('h', 7): 'p', ('a', 8): 'r', ('c', 8): 'b', ('d', 8): 'q', ('e', 8): 'k', ('f', 8): 'b', ('g', 8): 'n', ('h', 8): 'r'}

Écrivez donc une fonction qui transforme une représentation liste en représentation dictionnaire.

Conseil futé:

  • Créez un dictionnaire "inverse" pour trouver le symbole FEN qui correspond à une symbole dans la liste (soit à la main, ou mieux par programmation). Bien entendu qu'il ne sera pas possible de dire à quel symbole correspond None, étant donné qu'il y a plusieurs possibilités.

Conversions diverses

Ecrivez les fonctions de conversions restantes (vous pouvez réutiliser tant que possible le code déjà produit):

  • FEN -> dictionnaire
  • dictionnaire -> FEN
  • dictionnaire -> liste
  • liste -> FEN

Testez avec les exemples précédents.