Jeu d'échecs électronique ( ChessboARDuino )

Bonjour

Etant un joueur d'échecs amateur, j'ai toujours rêver d'avoir un véritable échiquier électronique relié en USB à un PC.
Cela existe mais ils coûtent environ 600 euros …

Je me suis donc lancé dans un projet arduino d’échiquier électronique, il fonctionne maintenant correctement

Mon but initial était de pouvoir enregistrer une partie d'échecs jouée entre deux humains sur un échiquier classique.

Les contraintes sont dans ce cas plus fortes que dans d’autres projets qui demandent seulement de pouvoir jouer contre l’ordinateur. Ce but étant maintenant atteint, voici une présentation de ce qui est réalisé.

Pour une question de coût, j’ai choisi d’utiliser de simples interrupteurs reed pour détecter la présence d’une pièce.
Ces interrupteurs se ferment lorsqu’ils sont soumis à un champ magnétique.
Les pièces sont munies d’aimant pour activer l’interrupteur en étant sur une case.

Les diodes forment une matrice de 8 par 8 ce qui permet de n’utiliser que 16 entrées digitales pour les 64 cases.
(sur le principe de la bibliothèque Keypad).

Certains projets utilisaient déjà ce procédé mais ne correspondaient pas à mes besoins.
Les joueurs d’échecs ont des habitudes (et des règles précises) lorsqu’ils déplacent les pièces, il n’est pas possible de leur demander de les changer pour permettre l’enregistrement.
Celui-ci doit être le plus transparent possible pour les joueurs.

La carte Arduino scanne plus de 50 fois par seconde la position de l’échiquier et au moindre changement, renvoie l’état de l’ensemble du plateau (actuellement vers le port série).
J’ai choisi pour le moment de faire le minimum de chose sur la carte, c’est un programme PC qui traite ensuite les données.

La transcription de la partie est actuellement possible à posteriori.
Il reste à améliorer l'ensemble et à augmenter ses possibilités.

En cours de réalisation

• utiliser une carte NANO et l'intégrer dans l'échiquier (à la place d'une MEGA)
• utiliser une carte SD pour l'enregistrement sans PC
• améliorer le programme de traduction de donnée
• écrire un programme pour jouer en temps réel contre un ordinateur

Evolutions possibles

• utiliser une liaison Bluetooth pour communiquer avec un PC ou une tablette
• émuler le protocole DGT pour rendre l'échiquier compatible avec les programmes l'utilisant
• déplacer les pièces de l'ordinateur à l'aide d'un bras mécanique ou d'un aimant sous l'échiquier pour un effet fantôme

Si vous voulez des détails n’hésitez pas à me poser des questions.
Vous pouvez trouver de nombreuses photos prisent en cours de réalisation sur le site de mon club d’échecs.
http://www.cpe95.org/spip.php?rubrique128
(on en cliquant sur les différents liens dans le texte)

Voila pour mon projet ChessboARDuino
je viens de trouver le nom

Super idée !!

le logo du projet

Chouette réalisation !

Tu arrives à un résultat satisfaisant, malgré le fait que chaque pièce ne soit pas précisément identifiée sur l'échiquier?

Comment gères-tu les cas de promotion d'un pion en aute chose qu'une dame?

Bonjour
jolie realisation
dans ton enregistrement sur SD , tu prevois un timer en + , du genre millis() pour calculer le temps entre les coups ?

Bon là je viens de me pencher un peu plus sur cette réalisation, qui mérite vraiment qu'on s'y arrête.

Franchement bravo

@Artouste : les video de démo montrent bien le principe d'enregistrement. Oui il y a forcément un timer qui permet d'horodater chaque mouvement détecté. Donc il sera forcément intégré à toute log sur carte SD.

Intellectuellement, je trouve que le plus attractif est l'analyse post-mortem des mouvements captés, pour reconstituer le fil de la partie et tous les coups joués.
Détecter les prises "carreaux", les glissades de pièces, éliminer les informations inutiles liées aux coups repris, etc.
Et comme il subsiste toujours des cas où il y a un doute sur la position (on connait seulement toutes les cases sur lesquelles il y a une pièce), l'intégration des règles du jeu peut lever la plupart des doutes : positions interdites, analyses des déplacements suivants, etc...
Il y aura toujours quelques cas marginaux où la levée de doute ne peut pas être automatique, mais on doit pouvoir les limiter au strict minimum.

Bon c'est vrai, cette partie là n'est plus de l'arduino.
Encore que, une fois toutes les règles d'analyse des mouvements définies et validées, un bon nombre d'entre elles devraient pouvoir être implémentées sur une arduino.
Cela permettrait une reconstitution quasi temps réel de la partie, sans PC
Probablement un peu chaud à faire au niveau soft, mais indubitablement un défi à relever ;D

**bricoleau ** c'est exactement cela tu as bien cerné les problèmes actuels et les évolutions possibles

je suis actuellement en pleine recherche d'un algorithme parfait qui reconnait les coups
à partir de toutes ces infos et c'est une grosse prise de tête.

Avec la première version de mon prog (façon usine à gaz)
j'arrive à reconstituer la partie même avec des prises carreaux et sans vérifier la validité des coup mais au moindre problème j'interviens manuellement, et encore trop a mon gout.
Surtout si le but est la reconnaissance en temps réel pour diffuser la partie sur un vidéoprojecteur ou sur internet ...

il y a un mois j'avais fait une vidéo pour expliquer la transcription
mais je viens de retourner les aimants sur les pièces noires ce qui devrait faire disparaître la totalité des prises carreaux et grandement facilité la reconnaissance des coups.
j'ai aussi écris un code donnant la liste des coups possibles pour chaque pièce.

Mon algo est donc complètement à revoir.

Les parties officielles sont théoriquement simple à suivre car les joueurs ne peuvent pas faire n'importe quoi, il y a des règles :

• "pièce touchée, pièce à jouer" (ou à prendre)
• reprendre son coup est interdit
• un coup illégal (constaté par l'adversaire) et la partie est perdue !
  cela qui limite les problèmes

j'ai testé l'échiquier de nombreuses fois avec les joueurs de mon club et les enregistrements parasites ne sont pas si nombreux que cela. Parfois une case s'allume à coté de la pièce que l'on prends mais rien de bien méchant

L'échiquier doit être placé à la première table lors d'un tournoi ce week end, avec enregistrement en autonomie sur carte SD (ce que les échiquiers DGT ne font même pas )
j'aurai alors 9 nouveaux logs pour tester le futur algo.

C'est pas simple mais je suis persuadé que l'on peut arriver à obtenir une reconnaissance quasi parfaite.

Faut donc que je réécrive entièrement la procédure de recherche des coups et je cale un peu
si le défit intéresse du monde je suis preneur de toutes aides/idées

PS1
Pour les promotions autre qu'en dame, c'est dans les règles mais je n'ai encore jamais vu cela en partie réelle ! et cela se produit lorsqu'il y a pat avec une dame on peut donc le "deviner"

PS2
les echiquiers DGT font un peut la meme chose mais avec comme infos supplémentaires le type de pièce sur chaque case : Retransmission de parties d’échecs en ligne

Arf, si seulement j'avais du temps à consacrer à ce projet...

C'est du softeux à 100%

Juste une "simple" fonction à écrire, pour passer d'une liste d'états de capteurs à une liste de coups d'une partie d'échecs, tel que très bien expliqué ici

Le genre de petite fonction qui nécessite un certain nombre de jours de travail de développement.

Et effectivement, vaut mieux être joueur d'échec de tournoi pour appréhender tout ce qui peut se passer sur un échiquier, et pondre l'algo de reconnaissance adapté.

fredjust:
PS1
Pour les promotions autre qu'en dame, c'est dans les règles mais je n'ai encore jamais vu cela en partie réelle ! et cela se produit lorsqu'il y a pat avec une dame on peut donc le "deviner"

Tiens, juste pour taquiner, une miniature avec sous-promotion en cavalier pour mater :
http://www.chessgames.com/perl/chessgame?gid=1075778

Bon d'accord, un algo de détection des sous-promotions intéressantes, par analyse des pat et mat, devrait traiter 99% des cas.

cela me rappelle que j'ai déjà placé une promotion cavalier en blitz
mais c'était sur une variante théorique du contre gambit albin connue jusqu'au bout

il n'y a même pas pat en cas de promotion dame ni mat avec promotion cavalier

statistiquement les promotions n'arrivent que dans 1.3% des parties (source)

Premiers tests après avoir retourné les aimants des pièces noirs

90% de coup reconnu

et ce avec mon ancien algo très linéaire qui ne vérifie pas la validité des coups

les 99% me semblent possibles ...

Tu fais suer

J'ai trop de trucs à faire en ce moment, mais je n'arrive pas à décrocher de ton sujet, qui est trop intéressant.

Pas moyen de ne pas y cogiter à temps perdu.

Bien sûr que tu peux monter à 99%.
Perso je parie même sur 100%, avec une reconnaissance temps réel implémentée dans l'arduino, en parallèle de la lecture des capteurs, sans le moindre besoin de levée de doute par un humain.
Ma seule interrogation est sur la suffisance de 2 ko de RAM. Peut-être qu'une mega reste nécessaire (8 ko RAM).

L'algo auquel je pense n'utilise même pas le délai entre chaque configuration des capteurs, ce qui le rend insensible à la vitesse des déplacements ou glissades.

fredjust:
Premiers tests après avoir retourné les aimants des pièces noirs

bonjour
J'ai du louper qq chose , mais c'est quoi cette histoire de retournement d'aimant ?
ils sont bien destiné à exciter de l'ILS "basiques" en contact NO ?

Cela s'appuie sur une constatation expérimentale de FredJust.

Explication ici

Il semble que l'inversion du champs magnétique s'accompagne d'une brève ouverture du contacteur

Esprit taquin, le retour

1. as-tu pensé à fabriquer plus de pièces magnétiques que nécessaire ?
   Par exemple pour les positions avec deux dames de la même couleur suite à promotion.
   Si non, le joueur d'échecs moyen va faire comme d'hab : il va retourner une tour déjà éliminée pour l'utiliser comme une dame, et à moins d'avoir un aimant collé sur le dessus, fini la reconnaissance.

2. que penses-tu d'une partie dont les premiers coups (certes ubuesques), seraient :
   1.Cf3 Cf6 2.Cd4 Cd5 3.Cf5 Cf4 4.Cg3 Cg6 5.Tg1 Tg8 6.Ch1 Ch8 7....

3. reprise de coup non lâché
   Par exemple : je glisse ma tour de d1 à d7, marque une pause de 2 secondes sans lâcher la pièce, avant de me raviser et de la glisser en arrière jusqu'à d2.

bricoleau:
Esprit taquin, le retour

1. as-tu pensé à fabriquer plus de pièces magnétiques que nécessaire ?

mon set de pièce contient une dame de plus que j'ai aussi équipé d'aimant mais c'est tout.
les échiquiers DGT à 600 euros ne font pas mieux et propose également qu'une dame de plus.

remarque : si tu déplace une tour retournée en diagonale c'est un coup illégal et cela peut te faire perdre la partie !

bricoleau:
2) que penses-tu d'une partie dont les premiers coups (certes ubuesques), seraient :
1.Cf3 Cf6 2.Cd4 Cd5 3.Cf5 Cf4 4.Cg3 Cg6 5.Tg1 Tg8 6.Ch1 Ch8 7....

bravo là tu fait planter mon programme actuel car une position "initiale" est obtenue donc fin de l'enregistrement et début de l'enregistrement de la partie suivante ...

bricoleau:
3) reprise de coup non lâché
Par exemple : je glisse ma tour de d1 à d7, marque une pause de 2 secondes sans lâcher la pièce, avant de me raviser et de la glisser en arrière jusqu'à d2.

oui j'y ai pensé ce coup est légal un joueur peut bouger sa pièce tant qu'il ne l'a pas lâchée
voir reprendre son coup dans certaines conditions (coup illégal non validé par l'appui sur la pendule)

cela s'est déjà produit :

si on ignore les temps entres les cases, ce mouvement n'est qu'un simple glissement c'est toujours la même pièce qui bouge cela ne devrait pas être trop embêtant à posteriori mais c'est a surveiller pour le direct (il faut peut etre décaler la retransmission d'un coup ou de 30 secondes)

je vais faire un post avec la logique de mon premier algo

mais pour le suivant il faut le faire par étape :

• on tente la méthode de reconnaissance simple
• si le coup n'est pas valide
• on tente une/les méthodes alternatives

on peut s’apercevoir un ou deux coups plus tard que l'on s'est planté et là ce risque d’être complexe de revenir en arrière tout en gardant l'incohérence en mémoire

j'attends les logs d'enregistrements de ce week end lors du tournoi en 15min pour commencer à écrire un nouvel algo
il y aura peut être encore des cas particuliers

Merci pour ton intérêt cela aide de discuter

bricoleau:
Cela s'appuie sur une constatation expérimentale de FredJust.

Explication ici

Il semble que l'inversion du champs magnétique s'accompagne d'une brève ouverture du contacteur

ok , je comprend mieux

dommage que les capteurs hall analogiques ne soient pas meilleur marché (il en faut 64) avec 6 magnetisations , ça permettrait de discriminer les pieces et la couleur par case

fredjust:
on peut s’apercevoir un ou deux coups plus tard que l'on s'est planté et là ce risque d’être complexe de revenir en arrière tout en gardant l'incohérence en mémoire

Ben justement, personnellement c'est par là que j'aurais tendance à creuser : un algo qui soit capable de se rendre compte qu'il est dans une impasse, et de revenir un peu en arrière pour prendre un meilleur chemin.

Voici comment j'aborderais le sujet de prime abord, quitte ensuite à l'adapter aux difficultés rencontrées :

En premier lieu, pour que la suite de mon propos ne soit pas ambiguë, dotons-nous d'un vocabulaire commun :

La position est à prendre au sens échiquéen du terme, c'est-à-dire que cela comprend l'ensemble des pièces bien identifiées avec leur emplacement, la couleur au trait, ainsi que les caractéristiques sous-jacentes (roque et/ou prise en passant autorisés, etc.).

La signature est la matrice 8x8 d’état des capteurs de présence d’une pièce sur chaque case.

On peut calculer la signature associée à une position.

L’inverse est justement l’objet du problème : reconstituer la position à partir d’une simple signature.
Plusieurs positions peuvent en effet avoir la même signature.

La position de départ d’une partie d’échecs est connue. L’objectif est donc d’analyser les variations de signature pour reconstituer le fil de la partie.
Par ailleurs, le postulat incontournable est que seuls des coups légaux sont joués sur l’échiquier.

Deux autres notions me semblent également intéressantes dans l’analyse des variations de signature :

Le poids d’une signature désigne le nombre de bits à 1, c’est-à-dire le nombre total de pièces présentes sur l’échiquier.
Il est intéressant de noter qu’en dehors d’un mouvement en cours pour déplacer une pièce, le poids ne peut aller qu’en décroissant. Et en cours de mouvement il ne peut augmenter que d’1 (disons 2 si le joueur soulève simultanément le roi et la tour lors d’un roque avant de les reposer, ce qui ne se fait normalement pas).

La distance entre deux signatures désigne le nombre de bits différents entre deux signatures.
Là aussi, il est intéressant de noter que cette distance ne peut excéder 2, entre les signatures de deux positions consécutives (4 dans le cas d'un roque)

Le principe général de l’analyse est de procéder par itérations successives, position après position, depuis la position de départ.

A partir d’une position, calculer tous les coups légaux et signatures théoriques associées, et les comparer à la signature réelle constatée sur l’échiquier. Plusieurs résultats sont possibles :

a) La signature réelle correspond à une et une seule signature théorique
Le coup joué et la nouvelle position sont alors bien identifiés

b) La signature réelle correspond à plusieurs signatures théoriques
Il y a alors ambiguïté sur la position.
Toutes les positions candidates sont mémorisées et les itérations suivantes seront basées sur l’analyse de l’ensemble de ces positions.
Dans la pratique, le nombre de positions candidates devrait être assez restreint, ce qui évitera toute explosion combinatoire.
Dans ces situations, la reconstitution temps réel de la partie pourra avoir un voire plusieurs coups de retard, qui seront rattrapés lorsqu’un nouveau coup lèvera l’ambigüité.

c) La signature réelle ne correspond à aucune signature théorique
Dans ce cas, l’analyse va remonter les itérations précédentes, à la recherche d’un nouveau chemin possible vers la nouvelle signature réelle.
Là aussi, le risque d’explosion combinatoire me semble maitrisé, grâce à la limitation des poids et distances de signature. Pas la peine de remonter jusqu’au début de la partie, on cherche des chemins courts.
Si aucun chemin n’est trouvé, le programme ignore la signature réelle et attend la suivante pour essayer de retomber sur ses pieds.

Ainsi :

• pour une glissade de pièce, par exemple une tour glissée de d1 à d4 : dans un premier temps, le programme va considérer que le coup joué est d1-d2, puis ne trouver aucun chemin sur un coup adverse amenant la libération de la case d2 et l’occupation de la case d3. La recherche va reprendre depuis la position précédente, et le programme va considérer que le coup joué est d1-d3. Et ainsi de suite jusqu’au bon coup d1-d4.

• pour un simple déplacement de pièce soulevée : la signature associée au moment où la pièce est en l’air sera ignorée (sauf si cette pièce a un mouvement possible de type prise, mais lorsqu’elle sera reposée l’analyse arrière invalidera cette prise).

• etc : décompose les mouvements d’un roque de toutes les manières possibles, le programme va rapidement retomber sur ses pattes.

Avec ces règles d’analyse, je n’arrive pas à identifier de cas où le programme échouerait à reconstituer 100% des coups légaux d’une partie.
Lorsque le joueur est en train jouer son coup, le programme va temporairement envisager des coups bizarres à chaque signature éphémère, mais je le vois toujours converger vers la bonne analyse.

La vitesse de déplacement n’entre pas en compte. Les joueurs peuvent faire des glissades sur 10 secondes, ou au contraire blitzer à mort en zeitnot, sans perturber le programme.
Et il n’y a même plus besoin de se soucier du sens de collage des aimants.

Les calculs peuvent également être optimisés avec quelques règles simples.
Par exemple, un coup des blancs ne peut pas entraîner la libération d’une case occupée par une pièce noire, et inversement. Ainsi, pas la peine d’évaluer les coups légaux d’un camp pour chercher une signature impliquant la libération d’une case occupée par une pièce du camp adverse.

Je pourrais aussi poursuivre sur la partie implémentation software sur arduino, mais là c’est déjà beaucoup pour aujourd’hui.

Waouh faut que je réfléchisse a tête reposée à tout cela
mais quelques remarques rapides

il existe une notation pour définir une position c'est la notation FEN
je l'utilise constamment pour stocker la position des pièces dans mon prog

lorsque tu dit on cherche l'ensemble des coups légaux, on peut normalement restreindre suivant la pièce qui se lève, car "un coup" commence toujours par une pièce qui se lève.

Soit elle est de la couleur du joueur au trait et on cherche les destinations possibles
Soit elle est de la couleur de l'adversaire et on cherche les pièces pouvant la capturer

mais j'ai du mal a voir comment gérer les coups glissés avec ta méthode

EDIT 1 Idées en vrac:

• ignorer les signatures ne correspondant à aucune position légale possible devrait permettre de "nettoyer" les enregistrements en supprimant les parasites
  Edit 2
• Ta méthode me semble géniale une vrai technique d'ordinateur alors que j'essayais de coder une réflexion (si une pièce se lève, si elle se déplace, si elle est au joueur au trait ...) qui n'aurait jamais pu gérer tout les cas possibles, la tienne me semble exhaustive c'est le 100% assuré

Edit 3

• une pièce se lève
• on liste toutes les destinations possibles et leur signature
• on enlève de la suite toutes les signatures qui ne sont pas dans la liste
• il y en a plus qu'une => mouvement trouvé
• il y en a plusieurs

• prend t on la dernière ?

j'ai déjà eu ce cas :

je l'ai traité comme un long glissement (tant que la pièce posée se relève juste apres ...)

et si d'autres signatures correspondent bien plus tard dans la partie ?

mais là je mélange les deux méthodes

EDIT 4

Par exemple, un coup des blancs ne peut pas entraîner la libération d'une case occupée par une pièce noire, et inversement. Ainsi, pas la peine d'évaluer les coups légaux d'un camp pour chercher une signature impliquant la libération d'une case occupée par une pièce du camp adverse.

Attention, Si ! car il est possible de prendre la pièce que l'on souhaite capturer avant de déplacer sa pièce sur cette case, dès qu'une pièce se lève on a soit la case de départ soit la case d'arrivée

si ce n'est pas un adoubement évidement (un joueur peut après avoir dit "j'adoube" recentrer une pièce à lui ou a son adversaire ce qui provoque une extinction allumage de la même case)
dans ce cas on ignore les 2 signatures

visuellement cela donne ca :

1. position initiale = 195.195.195.195.195.195.195.195
2. d2 s'éteint
3. d3 s'allume
4. d3 s'éteint
5. d4 s'allume => les blancs ont glissé le pion de d2 à d4
6. d7 s’éteint
7. d5 s’allume => les noirs ont joué d7-d5 en soulevant le pion
8. c2 s’éteint
9. c4 s'allume => les blancs ont joué c2-c4 en soulevant le pion
10. g8 s’éteint
11. g6 s'allume => les noirs posent leur cavalier g8 en g6
12. g6 s’éteint
13. f6 s'allume => et le glissent sur f6
14. d5 s’éteint => les blancs prennent le pion d5
15. c4 s’éteint => avec leur pion c4
16. d5 s'allume => qu'ils glissent en d5
    de 17. à 23. les noirs prennent le pion d5 et glissent leur cavalier f6 en d5

je réfléchi a voix haute ...
si je comprends bien ta méthode
on créé un genre d'arbre comme un moteur d'échecs qui cherche le meilleur coup

1. on génère les 20 coups possibles et leur signature
2. cette signature ne correspond pas => ON IGNORE
3. cette signature permet de supposer que le premier coup est d2-d3
   on génère l'ensemble des 20 réponses possibles noires et leur signature
4. cette signature ne correspond pas => ON IGNORE
5. cette signature ne correspond pas => ON IGNORE
   ...
   a partir d'un moment (quand ? soulèvement d'une pièce adverse ?) il faut invalider le coup d2-d3
   reprendre à partir de 4
6. cette signature ne correspond pas => ON IGNORE
7. cette signature permet de supposer que le premier coup est d2-d4
   on génère l'ensemble des 20 réponses possibles noires et leur signature ...