Go Down

Topic: Jeu d'échecs électronique ( ChessboARDuino ) (Read 16723 times) previous topic - next topic

#15
May 15, 2015, 05:21 pm Last Edit: May 15, 2015, 05:29 pm by fredjust
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 !

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 :



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  ;)

Artouste

#16
May 15, 2015, 06:36 pm Last Edit: May 15, 2015, 06:39 pm by Artouste
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 :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

bricoleau

#17
May 15, 2015, 07:48 pm Last Edit: May 15, 2015, 07:55 pm by bricoleau
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.

Tutoriels arduino : http://forum.arduino.cc/index.php?topic=398112.0

#18
May 15, 2015, 09:45 pm Last Edit: May 15, 2015, 11:49 pm by fredjust
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
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


#19
May 16, 2015, 10:34 am Last Edit: May 16, 2015, 11:08 am by fredjust
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
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 ...


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

Artouste

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 ?

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


Artouste

#23
May 16, 2015, 01:05 pm Last Edit: May 16, 2015, 01:08 pm by Artouste
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:

bricoleau

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
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.
Tutoriels arduino : http://forum.arduino.cc/index.php?topic=398112.0

bricoleau

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.
Tutoriels arduino : http://forum.arduino.cc/index.php?topic=398112.0

bricoleau

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.
Tutoriels arduino : http://forum.arduino.cc/index.php?topic=398112.0

Hello

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

Photos et enregistrements bruts

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




bricoleau

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.
Tutoriels arduino : http://forum.arduino.cc/index.php?topic=398112.0

#29
May 23, 2015, 09:29 pm Last Edit: May 23, 2015, 09:30 pm by fredjust
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 ...

Go Up