Arduino Forum

International => Français => Réalisations et Projets Finis => Topic started by: fredjust on May 07, 2015, 02:35 pm

Title: Jeu d'échecs électronique ( ChessboARDuino )
Post by: fredjust on May 07, 2015, 02:35 pm
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

(https://dl.dropboxusercontent.com/u/70945788/ChessboARDuino.jpg)


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 (http://www.cpe95.org/spip.php?article887) pour activer l'interrupteur en étant sur une case.

Les diodes forment une matrice de 8 par 8 (http://www.cpe95.org/spip.php?article860) 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é (http://www.cpe95.org/spip.php?article787) mais ne correspondaient pas à mes besoins.
Les joueurs d'échecs ont des habitudes (http://www.cpe95.org/spip.php?article897) (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 (http://www.cpe95.org/spip.php?article873) (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 (http://www.cpe95.org/spip.php?article908).
Il reste à améliorer l'ensemble et à augmenter ses possibilités.

En cours de réalisation
- utiliser une carte NANO (http://www.cpe95.org/spip.php?article911) 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 (http://www.cpe95.org/spip.php?article900)

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 (https://www.youtube.com/watch?v=51b10w3nTS4) ou d'un aimant sous l'échiquier pour un effet fantôme (https://www.youtube.com/watch?v=dX37LFv8jWY)


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 (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  :D
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: tahitibob35 on May 07, 2015, 05:16 pm
Super idée !!
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: fredjust on May 11, 2015, 06:38 pm

le logo du projet  ;)

(https://dl.dropboxusercontent.com/u/70945788/ChessboARDuino.png)
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: bricoleau on May 12, 2015, 04:52 pm
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?

Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: Artouste on May 12, 2015, 04:57 pm
Bonjour
jolie realisation
dans ton enregistrement sur SD , tu prevois un timer en + , du genre millis() pour calculer le temps entre les coups ?
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: bricoleau on May 12, 2015, 06:09 pm
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




Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: fredjust on May 12, 2015, 08:43 pm
 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 (http://www.cpe95.org/spip.php?article898)
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 (http://famille-michon.fr/journalgeek/2011/12/21/retransmission-de-parties-dechecs-en-ligne/)

Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: bricoleau on May 12, 2015, 09:50 pm
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 (http://www.cpe95.org/spip.php?article873)

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é.
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: bricoleau on May 12, 2015, 09:59 pm
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 (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.
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: fredjust on May 12, 2015, 10:37 pm
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
http://fr.lichess.org/CvG1FcrQ#13 (http://fr.lichess.org/CvG1FcrQ#13)
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 (http://www.france-echecs.com/article.php?art=20150320122255948))
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: fredjust on May 15, 2015, 12:13 am
Premiers tests après avoir retourné les aimants des pièces noirs

90% de coup reconnu (http://www.cpe95.org/spip.php?article915)   :)

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

les 99% me semblent possibles ...
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: bricoleau on May 15, 2015, 02:22 pm
Tu fais suer  :smiley-twist:

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.
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: Artouste on May 15, 2015, 03:07 pm
Premiers tests après avoir retourné les aimants des pièces noirs
(http://www.cpe95.org/spip.php?article915)
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  ?
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: bricoleau on May 15, 2015, 04:04 pm
Cela s'appuie sur une constatation expérimentale de FredJust.

Explication ici (http://www.cpe95.org/spip.php?article909)

Il semble que l'inversion du champs magnétique s'accompagne d'une brève ouverture du contacteur
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: bricoleau on May 15, 2015, 04:16 pm
Esprit taquin, le retour  :D

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.
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: fredjust on May 15, 2015, 05:21 pm
Esprit taquin, le retour  :D

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 (http://www.cpe95.org/spip.php?article807) !

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  :smiley-confuse:  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 ...

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 :

(http://www.cpe95.org/IMG/png/Image2-2.png) (http://www.cpe95.org/spip.php?article908)

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  ;)
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: Artouste on May 15, 2015, 06:36 pm
Cela s'appuie sur une constatation expérimentale de FredJust.

Explication ici (http://www.cpe95.org/spip.php?article909)

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

ok , je comprend mieux :smiley-mr-green:

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
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: bricoleau on May 15, 2015, 07:48 pm
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.

Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: fredjust on May 15, 2015, 09:45 pm
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 (http://fr.wikipedia.org/wiki/Notation_Forsyth-Edwards)
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

(https://dl.dropboxusercontent.com/u/70945788/ChessboARD/thinking.gif)

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 :
(http://www.cpe95.org/IMG/png/glissement.png) (http://www.cpe95.org/spip.php?article908)
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
Quote
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

Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: fredjust on May 16, 2015, 10:34 am
visuellement cela donne ca :

(https://dl.dropboxusercontent.com/u/70945788/ChessboARD/anim.gif)

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
4. cette signature ne correspond pas => ON IGNORE
5. 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 ...

Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: fredjust on May 16, 2015, 11:40 am
encore une remarque (après l'édition de mes posts précédents)

Quote
Je pourrais aussi poursuivre sur la partie implémentation software sur arduino, mais là c'est déjà beaucoup pour aujourd'hui.
tout implémenter dans arduino est surement un beau défit mais je ne vois pas l'intérêt immédiat

car pour la retransmission sur vidéo projecteur un ordinateur relié a l'arduino sera nécessaire
donc autant tout lui faire faire
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: Artouste on May 16, 2015, 12:54 pm
encore une remarque (après l'édition de mes posts précédents)

tout implémenter dans arduino est surement un beau défit mais je ne vois pas l'intérêt immédiat

car pour la retransmission sur vidéo projecteur un ordinateur relié a l'arduino sera nécessaire
donc autant tout lui faire faire

bonjour
je raisonne captation , pas jeu d'echec
dans ton soft "scanneur" pourquoi tu n'introduit pas un hysteresis une fois detecté un changement de configuration ? (changement de l'image de l'echiquier)
n'enregistrer l'image "arrivée" qu'apres un temps de stabilisation ?
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: fredjust on May 16, 2015, 01:00 pm
n'enregistrer l'image "arrivée" qu'apres un temps de stabilisation ?
oui j'y ai pensé mais sur une fin de partie les coups peuvent s'enchaîner très très vite
je voulais éviter d'utiliser les temps
pas sur que les différents coups soient vraiment clairement séparable ainsi

Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: Artouste on May 16, 2015, 01:05 pm
oui j'y ai pensé mais sur une fin de partie les coups peuvent s'enchaîner très très vite
je voulais éviter d'utiliser les temps
pas sur que les différents coups soient vraiment clairement séparable ainsi


c'etait une simple suggestion pour "depolluer"
à l'echelle "electronique" meme tres tres vite cela reste neanmoins tres  relatif  :smiley-mr-green: 

avoir à traiter du "bruit" est tres souvent la premiere chose à eviter/evacuer dans un process quelconque :smiley-cool:
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: bricoleau on May 16, 2015, 06:42 pm
visuellement cela donne ca :

(https://dl.dropboxusercontent.com/u/70945788/ChessboARD/anim.gif)

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
Lorsque l'on ne peut plus avancer, il faut revenir en arrière en essayant de trouver un autre chemin.

1. position de départ
2. aucun coup blanc n'amène à cette signature, et aucune possibilité d'analyse en arrière => on ignore
3. l'algo considère que les blancs ont joué d2-d3 Le trait est maintenant aux noirs
4. aucun coup noir n'amène à cette signature. Analyse arrière, c'est à dire en considérant successivement les positions et traits précédents : aucun coup n'amène à cette signature => on ignore
5. aucun coup noir n'amène à cette signature. Analyse arrière : en revenant à la position avant d2-d3, il y a un coup possible permettant d'atteindre la nouvelle signature. L'algo révise alors son évaluation de l'étape 3 et considère que le coup joué est d2-d4 (au lieu de d2-d3). Le trait est maintenant aux noirs.

etc.
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: bricoleau on May 16, 2015, 08:26 pm
Le principe de l'algo, c'est :

Je recherche en avant
1) si je trouve, je garde le ou les coups candidats
2) si je ne trouve pas, je recherche en arrière
2a) si je trouve, j'ajuste la séquence de coups qui était envisagée jusqu'ici
2b) si je ne trouve pas, j'ignore la signature

La recherche arrière consiste à réévaluer les dernières positions connues, de la plus récente à la plus ancienne, et pour chacune d'elles voir s'il existe un coup candidat permettant d'arriver à la signature recherchée.

Pour optimiser la recherche arrière, on peut utiliser la signature de chaque position, comparée à la signature recherchée, pour limiter grandement les cas analysés.

Voilà pour la recherche arrière.

Maintenant, il y a aussi des subtilités dans la recherche avant, s'il existe plusieurs coups candidats aboutissant à la même signature. Chacun d'entre eux est conservé dans une liste de coups potentiels de même rang. Il peut donc y avoir une petite arborescence des possibles à gérer.

Cela implique aussi que la recherche arrière peut également devoir être appliquée non pas à une seule position supposée, mais à une liste de plusieurs positions candidates...
Mais toujours avec le même principe.

Pour l'instant, la seule faille que j'entrevois, concerne les doutes non levés sur une position de mat.
Par exemple :
Blancs : Ra1Tg1h1Dg6
Noirs : Rh8Tf8Pg7h7
Trait aux blancs : les deux mats possibles Dxg7 ou Dxh7 ont même signature.
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: bricoleau on May 16, 2015, 10:39 pm
Autre idée :

Quel que soit le programme de reconnaissance mis en oeuvre, il existe un moyen simple de le tester sur un très grand nombre de parties.

Tu pars d'une base de données de parties d'échecs (on en trouve contenant plusieurs millions de parties).
Export au format PGN
Une petite moulinette pour éliminer toutes les variantes / commentaires / annotations
Une seconde moulinette pour générer la série de signatures correspondantes, en introduisant de manière aléatoire des signatures intermédiaires, afin de reproduire toutes les manières de bouger physiquement les pièces (levers, glissades, prises carreau, etc.)
Ton programme de reconnaissance doit reconstituer les PGN d'origine.

En industrialisant le test comme ça, tu peux même organiser un concours de programmation, et voir qui peut proposer l'algo qui a le meilleur taux de reconnaissance.

Tiens si j'étais prof, ça ferait un chouette sujet de projet à donner à toute une promo.
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: fredjust on May 18, 2015, 04:57 pm
Hello

Les enregistrement de partie se sont bien déroulées pendant un tournoi officiel ce week end :

Photos et enregistrements bruts (http://www.cpe95.org/spip.php?article917)

l'inversion des aimants supprime effectivement le problème lors des prises
mais j'ai d'autres problèmes, je trouve des anomalies dans les enregistrements je cherche encore l'explication

l'affichage sur l'écran de contrôle + l'enregistrement sur la carte SD doit prendre plus de 10ms
et certains changements se superposent

encore merci pour l'idée d'algo je vais ré écrire mon code
par contre je pense partir de la disparition d'une pièce et non d'une position
(car je ne pense pas réussir à l'écrire autrement)

et introduire des signatures intermédiaires correspondant  au soulèvement des pièces cela devrait lever des doutes



Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: bricoleau on May 23, 2015, 07:51 pm
Salut

Encore une petite suggestion pour améliorer l'enregistrement de parties de tournoi : ce serait bien que les enregistrements de ta log soient horodatés

A posteriori, tu connais les horaires des rondes. Cela te permettra de savoir quelle sequence de coups correspond à quelle ronde.
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: fredjust on May 23, 2015, 09:29 pm
effectivement j'ai eu du mal a retrouver les bons enregistrements lors du tournoi car sur carte SD les fichiers n'ont pas de date par défaut

par contre si la sauvegarde se fait depuis un PC j'ai la date de création qui aide bien pour savoir si c'est bien une ronde et non une analyse

j'ai enregistré des blitz hier avec un PC aucun problème, et l'identification des coups est beaucoup plus simple
je suis en train de tout recoder pour pouvoir suivre en direct

autre évolution possible  du projet : gérer le tout avec un raspberry
il pourrait tout faire écouter l'échiquier traduire les coups et projeter la partie en vidéo ...
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: fredjust on Nov 18, 2015, 01:14 am
RE bonjour

me RE voila, et non le projet n'est pas mort

après une pause j'ai entrepris le codage de l'algo de reconnaissance proposé par Bricoleau

et j'obtiens 100% de reconnaissance sur les parties enregistrées correctement de bout en bout

c'est trop cool, détail sur mon nouveau site pour ceux que cela intéresse :

http://chessboarduino.org/?p=45

à bientôt
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: bricoleau on Nov 18, 2015, 10:44 am
Trop cool

Bravo

Je vais regarder ça de près
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: bricoleau on Nov 18, 2015, 11:49 am
Vraiment super.
Chapeau bas pour cette réalisation.

Et merci pour avoir cité tes sources  ;)

A quand un échiquier double sur le même principe, pour gérer le blitz à quatre ?
Là ça commencerait vraiment à devenir velu  ;D


Blague à part, voici quelques idées supplémentaires, histoire d'alimenter la centrifugeuse à neurones :

Ce qui serait super classe, c'est que quelques minutes après la partie, chaque joueur puisse repartir avec une version papier des coups joués, annotée en automatique par un blunder check.
Là tu marquerais les esprits.

Avec la reconnaissance temps-réel dans l'arduino (si tu ne t'en sors pas, fais moi signe), effectivement une interface DGT ouvre des portes.

Autre possibilité qui me semble attractive : transformer le chessboarduino en borne wifi, avec serveur web, pour permettre à tout un chacun à proximité de suivre facilement la partie sur smartphone ou tablette.
Cela pourrait aussi limiter les agglutinements autour des joueurs de la table 1, quand on n'a pas de retransmission sur écran géant.

Je mets de côté une pendule automatique, bien que facile à réaliser, car il y aurait un problème d'homologation pour être utilisable en tournoi officiel.
Dans le même ordre d'idée, si un arbitre peut suivre ou reconstituer une partie non notée grâce à ton système, il ne pourra pas y fonder ses décisions.
Perso je ne me lancerais pas dans des discussions avec la fédé sur ces points. Ca doit être aussi facile que de demander à Platini d'ajouter des caméras d'arbitrage sur les terrains de foot.
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: fredjust on Nov 19, 2015, 09:18 am
Je vais bientôt relier le chessboarduino a une tablette windows 8, enregistrement et reconnaissance en temps réel. J'ai pour projet de streamer en direct vidéo les blitz du club avec incrustation de l'échiquier et "commentaires en direct" de Dmitri komarov grâce au 2000 fichiers audio de l'extention dmitlichess (https://www.youtube.com/watch?v=ftNYlF7Wsvs)
Cela devrait attirer du monde sur le projet qui pour le moment reste toujours confidentiel.

Émuler le protocole DGT  serait un sacré grand bond pour le projet mais j'en suis loin
(c'est un peu frustrant de savoir que c'est tout a fait possible mais qu'il reste une montagne de code ...)

J'ai aussi pensé au Bluetooth pour l'envoi des coups vers les smartphones, le seul gros problème c'est que les smartphones sont interdits dans les salles de jeu pour des raisons de triche.
Et le règlement ne rigole pas si ton tèl émet un bruit au cours d'une partie officielle tu l'as perd sur le champs !

Je croix que les arbitres se sont basés sur l'enregistrement d'une partie par un échiquier DGT lors du dernier championnat du monde de rapide pour valider une demande de nulle pour 3° répétition.
Cela m'a vraiment surpris je ne pensais pas que c'était possible (faut que je retrouve la ref exacte EDIT:  blitz de départage 10''+10 Karjakin vs Eljanov (https://www.youtube.com/watch?v=0ol9wng_iwU) RE-EDIT en fait non il semble qu'un arbitre supervise la partie)

Cela avance quand même donc, la FFE a même repris mes idées d'améliorations pour les grilles américaines et les feuilles de match après mon passage sur le podcast fréquence diagonale (http://www.frequence.diagonaletv.com/2015/11/frequence-diagonale-n24-chessboarduino-et-grilles-dynamiques-avec-fred-just/)

Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: bricoleau on Nov 19, 2015, 11:43 am
Effectivement le Bluetooth n'est pas possible car les appareils électroniques sont interdits dans une salle de tournoi.
Autre inconvénient : cela nécessite d'installer un soft côté client.

C'est pour ça que je te proposais plutôt du wifi.
Cela permettrait de suivre la partie depuis une salle d'analyse à proximité de la salle de tournoi.
Y aurait même un côté sympa à pouvoir débattre / commenter la partie par petit groupe en live, chose que l'on ne peut pas faire dans la salle de tournoi (et pourtant, ça démange souvent...).

Et en plus l'accès client serait plus simple : ton échiquier agirait comme une borne wifi qui diffuse une page html contenant la position en cours. N'importe quel smartphone ou tablette pourrait y accéder nativement.

Par contre, côté serveur il y aura probablement un peu de grain à moudre.
Les capacités d'un arduino en tant que serveur web sont limitées (nombre de connexions). La faisabilité est incertaine et il faudra peut-être étoffer la solution (par ex passer par un serveur externe).
De surcroît, le temps passé à retourner la page html à chaque client pourrait nuire à l'activité de lecture des capteurs.

Ce dernier point risque d'ailleurs de se retrouver pour chaque nouvelle fonctionnalité que tu voudras ajouter à ton chessboarduino.

Il faudra peut-être en passer par l'assemblage de plusieurs modules arduino, chacun étant spécialisé dans une tâche. Cette option ne doit pas être écartée a priori : ce n'est pas très difficile à mettre en œuvre, cela facilite la mise au point et l'intégration, et une arduino pro mini coûte à peine 2€ en import chinois.

Si je pousse ce raisonnement, tu pourrais par exemple garder ton arduino nano en central, entourée de 4 arduino mini qui la déchargent :
- une dédiée au relevé permanent des capteurs
- une dédiée au décodage temps-réel des positions
- une dédiée à l'interface DGT
- une dédiée à l'interface wifi
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: fredjust on Nov 20, 2015, 04:12 pm
Oui effectivement, mais on en est pas là

pourquoi pas passer sur un raspberry pi 2 (si on a le droit de l'évoquer sur un forum Arduino ;-) )
on a toute la puissance qu'il faut et je croix qu'il y a aussi des ports E/S (combien ?)
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: bricoleau on Nov 20, 2015, 04:57 pm
Oui c'est l'autre option

Avec un raspi tu changes complètement de dimension (cpu, ram, etc.) car là tu as un vrai ordinateur qui tourne sous linux - j'en ai trois à la maison -

Côté batteries ça va aussi être une autre dimension, si tu veux que ton dispositif puisse tenir une journée entière.

A mon avis, ce n'est pas forcément mieux pour maîtriser au plus bas niveau tout ce qui a trait à l'électronique, un peu comme utiliser un char d'assaut pour écraser une mouche, mais c'est incomparable pour gérer tout ce qui va autour.

Tu pourrais par exemple laisser uniquement un arduino pour gérer la surveillance permanente de tes capteurs, et faire tout le reste au niveau du raspi, jusqu'à avoir une base MySQL dans laquelle tout serait enregistré, un serveur LAMP etc.

Ou carrément : virer tous tes capteurs et utiliser une webcam sur le raspi pour faire de la reconnaissance automatique de position. Là y a plus du tout d'électronique, plus d'échiquier connecté, juste du logiciel dans un dispositif posé à côté de l'échiquier avec une caméra.
L'apparence des éléments de base étant connue (échiquier, forme des pièces), il doit y avoir moyen d'arriver à analyser les images pour en extraire la position.
Mais c'est une voie radicalement différente de celle que tu as suivie jusqu'ici.
Et puis il faudrait renommer ton projet, revoir le logo, ...  :)
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: warolus on Dec 01, 2015, 12:52 am
WAROLUS         Eric
Rue du corbeau 3 c
7540         Rumillies
      Belgique
 
warolus@belgacom.net
 
https://sites.google.com/site/lesechecselectroniques
 
 
Rumillies, le 30 novembre 2015,

Bonjour,

Félicitations pour la reconnaissance correcte des coups joués sur votre ChessboARDuino.

Depuis quelques temps, l'idée m'est venue de réaliser un échiquier électronique,
celui-ci est évolutif et matériellement autonome.

Pour ma part, l'idéal est un échiquier et des pièces en bois avec une reconnaissance des mouvements automatique et une lecture du coup joué par le programme-application par LED.

Pour le matériel utilisé, plusieurs pistes :

L'échiquier et pièces en bois dimension +- 38x38 cms et le roi +- 8 cms de ht pour une utilisation confortable.
La reconnaissance des mouvements par le système utilisé sous le plateau
( Soluschess Berger et Mysticum ) reed et aimant me semble satisfaisante.
La lecture du coup joué par l'allumage de LED soit sur chaque case soit en coordonnées.
Pour recueillir les informations des capteurs et les transmettre une carte Arduino, teensy ou autre.
Ensuite pour faire tourner l'interface genre GUI, soit un raspberry py 2 avec un écran, soit une tablette Android, soit une tablette Windows, celle-ci incorporée dans le boitier, un peu comme ceci :
(https://dl.dropboxusercontent.com/u/46932715/echecs/attente/echiquier.jpg)
La réalisation la plus économique est avec une tablette Android 7"( 40 € ).
L'application Chess for android de Aart Bik fonctionne très bien avec une entrée clavier des coups joués émulé par l'échiquier sensitif.
Par contre reste la programmation de l'allumage des LEDs des coups joués par l'application.
L'écran (de la tablette) sert principalement pour choisir le moteur, le niveau , sauver la partie, etc...

Que pensez-vous d'une éventuelle coopération pour finir un prototype fonctionnel et peut-être ensuite tenter Kickstarter ?

PS pour le système avec caméra, lisez l'article évolution des échiquiers électroniques
sur  https://sites.google.com/site/lesechecselectroniques/ (https://sites.google.com/site/lesechecselectroniques/)


Salutations

Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: fredjust on Mar 12, 2016, 07:56 pm
Re bricoleau, regarde un peu comment ton algo fonctionne trop bien ;-)
et encore je ne vais qu'à un niveau de profondeur dans "l'arbre" !

https://www.youtube.com/watch?v=qVlQkGL-990 (https://www.youtube.com/watch?v=qVlQkGL-990)

warolus désolé je n'avais pas reçu la notification de réponse pour ton message je le découvre

a+
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: bricoleau on Mar 18, 2016, 04:15 pm
Bonjour

C'est vraiment très impressionnant.
Content d'avoir pu contribuer à l'atteinte de ce résultat.

Quand est-ce que tu intègres ça en temps réel dans un arduino ?

Dommage que nos zones de chalandise échiquéennes soient si distantes, je serais bien passé voir la bête de visu, mais mes passages en région parisienne sont trop brefs et occasionnels pour m'en donner l'opportunité.

Il n'est pas impossible que je me lance dans une réalisation similaire un de ces 4, dans le même contexte que le tiens (tournoi semi rapide annuel de mon club), mais en développant le côté communiquant du système.
Surtout, garde bien tous tes enregistrements bruts, car cela peut constituer une précieuse base de tests pour mettre au point du logiciel.
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: sammydilan on May 28, 2018, 04:27 pm
there is another very interesting in https://www.albertochueca.com and in addition he offers a very good chess guide...
Title: Re: Jeu d'échecs électronique ( ChessboARDuino )
Post by: Dewalih on Dec 26, 2018, 02:02 am
bon boulot. Pourrais je avoir un coup de main de votre part pour une réalisation similaire ?