Discussion :

[Rumpel]

Hello,

Je voudrais savoir comment coder une position au jeu d'échec.
J'ai lu un article avec la clé de Zobrist, je n'ai pas compris grand chose, sauf qu'il y avait 13 possibilités pour chaque case (vide / 6 pièces différentes blanches - noires ) et qu'il fallait générer une clé aléatoire sur 32/64 bits.
Et à quoi elle sert cette clé ??

Humh merci de m'éclairer avec des mots simples svp.
Mon projet n'a pas pour vocation de coder une IA (vu que c'est une variante trop compliquée dérivé des échecs), mais juste reconnaitre si on répète 3 fois la même position par exemple ...

[okaparka]

Hello,

...reconnaitre si on répète 3 fois la même position par exemple ...

Bonjour,
La programmation de la règle du jeu dite de "partie nulle si une même position se répete 3 fois.. " requiert de coder chaque position enregistrée sur la feuille de match de telle façon que l'on puisse comparer si la position courante a déja été "vue" lors des coups précédents.

Pour que la comparaison soit rapide, _ notamment lorsque l'on est dans l'algo de recheche de la meilleur position suivante _ , il est de bon goùt de coder une position sous forme (par exemple ) d'un integer de 64 bits (plutot que de faire une boucle sur les 64 cases de l'echiquier pour examiner si chaque case de la position suivante contient la même piece que l'une des positions précédentes ...


Toutefois Un Integer 64 bits n'est pas suffisant car il ne permet pas de coder toute position de façon unique. Sauf si on se satisfait de ce que la probabilité que 2 positions différentes ( de la feuille de match) aient le même codage est très très faible. C'est le risque que la machine déclare à tort "partie nulle par répétition de coups"...
Pour ma part j'utilise un code à 192 bits ( 3 UINT64, soit 24 octets) qui permet de coder de façon biunivoque toute position. Démonstration
Comme dit, une case peut avoir 13 états ( 1 + 2*6) , soit 4 Bits au minimum
Il y a 32 Pieces max , donc 4 bits * 32 = 128 Bits
Il y a 64 cases et chacune est vide ou occupée , soit 64 bits
au total : 128 + 64 = 192 bits ( IA au stade du design)
NOTE ( les bits 14 et 15 libres me servent, avec quelques astuces , à coder le reste : roques, EP target Square, couleur ayant le trait)

NOTE : L'avantage du codage ZOBRYST, sur les autres formes de codage, est, en outre, de pouvoir générer le code Zobryst de la position suivante à partir de "XOR"(s) sur le code de la position précédente; et ce en fonction des cases de départ et d'arrivée de la piece jouée. (voir détails de l'algo sur le web...), d'où rapidité dans l'algo de génération de la position suivante à partir d'un "move" et de la position précédente ..

NOTE . De façon triviale on pourrait comparer les codes FEN des positions enregistrées depuis le début de la partie, toutefois les essais effectués par certains montrent des pbs de performances ( 50 caracteres alphanum pour un code FEN * 8 = 400 Bits...)

NOTE : Un codage sur 32 bits semble faible (selon les spécialistes..) car risque non négligeable de collisions de clés...

Au dela de la gestion de la problématique d'identification des répétitions de positions, l'enjeu d'un "bon" code est de pouvoir garder en mémoire vive des milliers ou millions de positions ... lors de la recherche du meilleur coup.

En esperant avoir éclairé la problématique....

cdlt

[davcha]

Comment tu codes la position d'une pièce au juste ?...

[okaparka]

Comment tu codes la position d'une pièce au juste ?...

La structure de Bits pour coder une position ou diagramme est la suivante :
Note : Dans ce qui suit , et par convention , les cases de l'echiquier sont numérotées de 1à 64 , par exemple case "a1" = 1 et case "h8" = 64

a) codage des cases occupées/vides sous forme d'un entier 64 bits noté E1
Bit i de E1 = 1 si case i est occupée , 0 sinon
Note : ici pour la clarté de l'exposé (?) les bits sont numérotés de gauche à droite de 1 à 64

b) codage du contenu de chaque case occupée sous forme d'un "nibble" de 4 bits
On a 6 figures de 2 couleurs différentes soit donc 12 valeurs de 1 à 12

On note I2 et I3 , les 2 entiers de 64 bits qui contiennent donc à eux deux 32 "nibbles" décrivant le code de chaque Piece.

Astuce : SI le Bit i de E1 est = 1 ET si ce bit i est le Nième bit à 1 en lisant E1 de i = 1 à 64 alors la case i de l'échiquier est occupée par une piece codée dans le "nibble" N ( N variant de 1 à 32 sur I2 et I3 )


Astuce : si les pieces sont codées de façon standard de 1 à 12 , ont peut utiliser les valeurs " 13","14","15" restantes du nibble pour coder : la couleur ayant le trait, la case de Prise en passant si elle existe, les Roques interdits
Exemple pour coder un pion qui peut etre pris en passant , ne pas utiliser le code du pion standard mais le code 13
Pour coder la couleur ayant le trait : utiliser code 14 , et pour le décodage : SI code = 14 existe alors c'est un ROI BLANC et Trait aux Blancs sinon le trait est aux Noirs, etc.

[Roland Chastain]

Bonjour !

Pour se représenter clairement l'ensemble des données à enregistrer, on peut s'appuyer sur la notation FEN, qui sert justement à noter les positions :

Notation Forsyth-Edwards

Un programmeur débutant (c'est mon cas) peut même se servir de ce format tel quel, c'est-à-dire enregistrer la position dans une simple chaîne de caractères.

C'est moins bien mais ça marche aussi !