IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Gérer les échecs (et mat)


Sujet :

Algorithmes et structures de données

  1. #1
    Membre chevronné
    Avatar de emixam16
    Homme Profil pro
    Chercheur en sécurité
    Inscrit en
    Juin 2013
    Messages
    333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Calvados (Basse Normandie)

    Informations professionnelles :
    Activité : Chercheur en sécurité

    Informations forums :
    Inscription : Juin 2013
    Messages : 333
    Points : 1 827
    Points
    1 827
    Par défaut Gérer les échecs (et mat)
    Bonjour,

    Je programme actuellement un petit jeu d'échecs (en C# avec XNA).

    Mon problème est que je n'arrive pas à gérer les échecs (et mat) dans ma boucle.

    Actuellement chaque pièce peut faire plusieurs mouvements "en théorie", c'est à dire si elle était la seule pièce sur le plateau.

    Quand une pièce est sélectionnée, pour chacun de ses mouvements théoriques, si le mouvement est possible en pratique (pas bloqué par une pièce quelconque sur le plateau) il est stocké dans une liste de mouvement. La pièce ne pourra bouger que dans les cases de cette liste.

    Le problème est pour le roi. En effet, il ne peut se déplacer que si la case ciblée n'est pas attaquable, c'est-à-dire qu'aucune pièce adverse ne peut pas se déplacer sur cette case. Cela implique de vérifier les déplacements de TOUTES les pièces adverses, y compris du roi. Or pour obtenir les déplacements du roi, on doit encore vérifier qu'aucune pièce n'attaque la case cible et ainsi de suite créant une récurrence infinie...

    Avez vous des idées pour gérer ce problème?

    Merci d'avance

  2. #2
    Membre expérimenté Avatar de 10_GOTO_10
    Profil pro
    Inscrit en
    Juillet 2004
    Messages
    885
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2004
    Messages : 885
    Points : 1 522
    Points
    1 522
    Par défaut
    Il n'y a pas de boucle infinie parce que le roi adverse n'a pas le droit de se mettre en échec, y compris en se mettant sur une case qui serait contrôlée par une autre pièce. Il faut donc :

    - Faire l'inventaire de tous les mouvements adverses possibles (quelles que soient les circonstances). J'en déduis toutes les cases contrôlées par l'adversaire.
    - Et de là je peux en déduire tous mes mouvements (ceux qui ne mettent pas mon roi en échec).

  3. #3
    Expert éminent sénior
    Avatar de Mat.M
    Profil pro
    Développeur informatique
    Inscrit en
    Novembre 2006
    Messages
    8 352
    Détails du profil
    Informations personnelles :
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Novembre 2006
    Messages : 8 352
    Points : 20 359
    Points
    20 359
    Par défaut
    Citation Envoyé par emixam16 Voir le message
    . Cela implique de vérifier les déplacements de TOUTES les pièces adverses, y compris du roi. Or pour obtenir les déplacements du roi, on doit encore vérifier qu'aucune pièce n'attaque la case cible et ainsi de suite créant une récurrence infinie...
    je ne sais pas jouer aux échecs je préviens tout de suite.. , programmer un jeu d'échecs ça doit pas être aussi facile..
    maintenant si tu veux vérifier les déplacements des pièces adverses , ça peut être un cas typique pour construire un arbre de décision.
    En mathématiques dans le domaine des probabilités ,par exemple si tu lances des dés , tu peux construire un arbre qui va te donner toutes les combinaisons possibles de tirages.
    Reste à voir si c'est une bonne solution.

  4. #4
    Membre actif

    Homme Profil pro
    autodidacte
    Inscrit en
    Mars 2011
    Messages
    95
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : autodidacte

    Informations forums :
    Inscription : Mars 2011
    Messages : 95
    Points : 207
    Points
    207
    Par défaut
    Citation Envoyé par 10_GOTO_10 Voir le message
    Il n'y a pas de boucle infinie parce que le roi adverse n'a pas le droit de se mettre en échec, y compris en se mettant sur une case qui serait contrôlée par une autre pièce. Il faut donc :

    - Faire l'inventaire de tous les mouvements adverses possibles (quelles que soient les circonstances). J'en déduis toutes les cases contrôlées par l'adversaire.
    - Et de là je peux en déduire tous mes mouvements (ceux qui ne mettent pas mon roi en échec).
    ...d'autant plus qu'il faut aussi tenir compte du roque du roi et donc:
    - mémoriser si le roi a déjà bougé, si la tour droite a bougé, si la tour gauche a bougé
    - évaluer à tout moment pour le roi s'il les deux cases à sa gauche et à sa droite sont attaquées, au cas où le roi n'aurait pas encore roqué (parce qu'en roquant le roi ne peut pas se mettre en échec, ni "passer" par une case menacée).

    PS: à tous, cette notion n'étant pas familière aux non-joueurs d'échecs, traiter correctement le cas du "pat" (aucun mouvement légal disponible), qui donne un résultat de nullité à la partie. L'évaluation de la position doit donc être adaptée pour ce cas précis et recherchée par l'algo pour le cas où, par exemple, un joueur ne disposerait plus que de son roi.
    Toujours à adapter le problème à la structure de la machine, mais se soigne pour faire l'inverse.

  5. #5
    Nouveau membre du Club
    Homme Profil pro
    Développeur Java
    Inscrit en
    Mai 2012
    Messages
    13
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur Java
    Secteur : Administration - Collectivité locale

    Informations forums :
    Inscription : Mai 2012
    Messages : 13
    Points : 33
    Points
    33
    Par défaut
    Citation Envoyé par emixam16 Voir le message
    il ne peut se déplacer que si la case ciblée n'est pas attaquable, c'est-à-dire qu'aucune pièce adverse ne peut pas se déplacer sur cette case.
    Désolé mais ce n'est pas équivalent.

    Pardon aux non joueurs d'échecs mais là c'est juste un point de règlement.

    Pose ton roi en A1 et celui de ton adversaire en A3. Aucuns de vous n'a le droit d'aller en A2 car vos deux rois attaquent A2 mais sans pouvoir y aller !

    De même, ton roi est toujours en A1, tu as un fou en A4. Ton adversaire a une tour en B3 et son roi en D1. Tu n'as pas le droit de mettre ton roi en B1 puisque la tour adverse contrôle la case (B1) alors même qu'elle ne peut y aller puisqu'elle est clouée par le fou !

    Donc faire la liste des cases contrôlées/attaquées et déterminer les mouvements possibles sont deux opérations distinctes.

  6. #6
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5 238
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5 238
    Points : 13 443
    Points
    13 443
    Par défaut
    Bonjour,

    je ne sais pas si c'est ce qu'a voulu dire lautrec1 mais, par le roque, le roi va sur une case qu'il ne contrôlait pas au tour d'avant.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  7. #7
    Membre chevronné
    Avatar de emixam16
    Homme Profil pro
    Chercheur en sécurité
    Inscrit en
    Juin 2013
    Messages
    333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Calvados (Basse Normandie)

    Informations professionnelles :
    Activité : Chercheur en sécurité

    Informations forums :
    Inscription : Juin 2013
    Messages : 333
    Points : 1 827
    Points
    1 827
    Par défaut
    Bonsoir,

    J'ai finalement résolu mon premier problème. L’échec est géré. Pour ceux que ça pourrait intéresser voici une solution.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
     
    foreach (Figure king in figures)
                    if (king is King)
                        foreach (Figure figure in figures)
                            if (figure.Color != king.Color)
                            {
                                InitMoves = GetMoves(figure);
                                for (int i = 0; i < InitMoves.Count; i++)
                                    if (InitMoves[i].MoveTo == king.Position)
                                    {
                                        CheckState.AddCheck();
                                        CheckState.IsChecked = king.Color;
                                        CheckState.CheckingFigurePosition = figure.Position;
                                }
                            }
    J'essaye maintenant de gérer vérifier qu'il n'y a pas d'échec et mat. J'ai un peu de mal a vérifier qu'aucune pièce (non collée) ne peut s'intercaler entre le roi
    et l'attaquant adverse. Si je n'y arrive vraiment pas je vous ferai signe

  8. #8
    Nouveau membre du Club
    Homme Profil pro
    Développeur Java
    Inscrit en
    Mai 2012
    Messages
    13
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur Java
    Secteur : Administration - Collectivité locale

    Informations forums :
    Inscription : Mai 2012
    Messages : 13
    Points : 33
    Points
    33
    Par défaut
    Bonjour,

    Que retourne ta fonction GetMoves(figure); ? Si c'est les coups possibles c'est pas bon.

    Pardon pour l'auto citation :

    Citation Envoyé par R. Daneel Olivaw Voir le message
    faire la liste des cases contrôlées/attaquées et déterminer les mouvements possibles sont deux opérations distinctes.
    Petit exemple :
    C'est aux blancs de jouer. Ils ont leur roi en B1 et un fou en A3. Les noirs ont une tour en B8 et leur roi en H8. Les blancs sont en échecs par la tour.
    Supposons qu'ils le parent par Fb2+.
    Le fou n'a aucun coup possible puisqu'il est cloué. Mais il fait néanmoins échecs au roi noir à l'autre bout de l'échiquier.

  9. #9
    Membre actif

    Homme Profil pro
    autodidacte
    Inscrit en
    Mars 2011
    Messages
    95
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : autodidacte

    Informations forums :
    Inscription : Mars 2011
    Messages : 95
    Points : 207
    Points
    207
    Par défaut
    Citation Envoyé par R. Daneel Olivaw Voir le message
    Que retourne ta fonction GetMoves(figure); ? Si c'est les coups possibles c'est pas bon.
    Je ne comprends pas très bien pourquoi.

    Une case attaquée est accessible par un mouvement légal (issu de getMoves idéalement). Il a un lien entre mouvement légal et case attaquée.
    Si le roi est sur une case attaquée, alors il est en échec.
    Toujours à adapter le problème à la structure de la machine, mais se soigne pour faire l'inverse.

  10. #10
    Nouveau membre du Club
    Homme Profil pro
    Développeur Java
    Inscrit en
    Mai 2012
    Messages
    13
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur Java
    Secteur : Administration - Collectivité locale

    Informations forums :
    Inscription : Mai 2012
    Messages : 13
    Points : 33
    Points
    33
    Par défaut
    Non, une case attaquée (pour les questions d'échecs au roi) n'est pas forcement accessible par un mouvement légal.

    Une pièce clouée ne peut pas bouger. Elle n'a donc pas de mouvement légal. Néanmoins, elle attaque des cases. Elle ne pourra pas y prendre des pièces lambdas puisque interdite de mouvement. Mais si le roi adverse s'y trouve il sera bel et bien en échec.

    Reprends l'exemple de mon post précédent après le coup Fb2+. Si le fou blanc bouge, le roi blanc en b1 est en échecs par la tour noire en b8. Le fou n'a donc pas de coup l'égal. En particulier, il ne peut aller nulle part sur la diagonal a1-h8. Mais il fait tout de même échec au roi noir qui est sur h8 et les noirs n'ont d'autre choix que de bouger leur roi ou de prendre le fou !

  11. #11
    Membre actif

    Homme Profil pro
    autodidacte
    Inscrit en
    Mars 2011
    Messages
    95
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : autodidacte

    Informations forums :
    Inscription : Mars 2011
    Messages : 95
    Points : 207
    Points
    207
    Par défaut
    Citation Envoyé par R. Daneel Olivaw Voir le message
    Une pièce clouée ne peut pas bouger. Elle n'a donc pas de mouvement légal.
    Je crois qu'on a tous les deux raison et qu'on a affaire à du vocabulaire particulier. Je suis donc allé chercher le règlement par curiosité.


    Article 3.9 des règles Fide :

    "The king is said to be 'in check' if it is attacked by one or more of the opponent's pieces,
    even if such pieces are constrained from moving to that square because they would then
    leave or place their own king in check. No piece can be moved that will either expose the
    king of the same colour to check or leave that king in check."

    Source:
    http://www.fide.com/images/stories/N...anual_2013.pdf

    Ce que j'en dis:

    1) une pièce clouée peut attaquer le roi (la règle le dit clairement: la pièce "attaque" le roi).
    2) Mais il est aussi vrai qu'elle ne peut pas bouger.

    Cela me fait penser qu'elle n'a qu'un seul mouvement possible éventuel : se rendre sur la case du roi.
    Toujours à adapter le problème à la structure de la machine, mais se soigne pour faire l'inverse.

  12. #12
    Nouveau membre du Club
    Homme Profil pro
    Développeur Java
    Inscrit en
    Mai 2012
    Messages
    13
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur Java
    Secteur : Administration - Collectivité locale

    Informations forums :
    Inscription : Mai 2012
    Messages : 13
    Points : 33
    Points
    33
    Par défaut
    Donc "elle ne peut pas bouger" mais "elle n'a qu'un seul mouvement possible éventuel : se rendre sur la case du roi" ?

    Je préfère dire qu'elle peut attaquer une case sans pouvoir y aller.

    Mais j'ai surtout l'impression de pinailler tel un arbitre qui ne veut pas que l'on prenne le roi en blitz !

    C'est d'autant plus bête que ma réaction à GetMoves(figure); était motivé (dans ma petite tête, pas dans mon poste) par des considérations algorithmiques !

    Revenons donc au cœur du forum.

    Supposons que GetMoves soit écrit pour répondre que la prise du roi adverse est possible même pièce clouée.

    Si l'on reprend mon exemple avec le fou blanc cloué en b2 mais que l'on place le roi noir en h7. Ce dernier n'est plus en échec. C'est au noir de jouer et l'on peut donc se poser la question de savoir si le roi noir a le droit d'aller en h8.

    La réponse est non. Il y serait en échec.

    Mais comment arriver à ce résultat ?

    Si tu demande à GetMoves si le fou peut aller en h8 la réponse sera non car il est cloué et que la case est vide.

    Donc tu dois simuler la présence du roi dans la case cible (sans oublier de l'enlever de h7 pour qu'il ne fasse pas barrage à une éventuelle tour ailleurs sur h) et appeler GetMoves sur chaque pièce adverse.

    Bref, si ton roi est au milieu de l'échiquier et qu'il peut aller sur 8 cases tu vas appeler GetMoves 8 fois par pièce adverse.

    ça va marcher. Mais c'est pas optimisé.

    Je préfèrerai une méthode vuParPieceAdverse qui marque toutes les cases "vues/attaquées" par les pièces adverses sans tenir compte des éventuelles clouages.

    Cette méthode spécifique serait sensiblement différente de GetMoves mais plus légère.

  13. #13
    Membre actif

    Homme Profil pro
    autodidacte
    Inscrit en
    Mars 2011
    Messages
    95
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : autodidacte

    Informations forums :
    Inscription : Mars 2011
    Messages : 95
    Points : 207
    Points
    207
    Par défaut
    Citation Envoyé par R. Daneel Olivaw Voir le message
    Je préfèrerai une méthode vuParPieceAdverse qui marque toutes les cases "vues/attaquées" par les pièces adverses sans tenir compte des éventuelles clouages.

    Cette méthode spécifique serait sensiblement différente de GetMoves mais plus légère.
    En effet, avec une implémentation avec un tableau[8][8] pour chaque camp, indiquant le nombre de fois où chaque case est contrôlée ?

    @R Daneel
    Pinailler, pinailler... Est-ce que après tout deux joueurs réguliers ne le font pas à chaque fois qu'ils parlent technique ??

    @emixam
    Le sujet n'est pas résolu. Est-ce que tout ça te parle ?
    Toujours à adapter le problème à la structure de la machine, mais se soigne pour faire l'inverse.

  14. #14
    Nouveau membre du Club
    Homme Profil pro
    Développeur Java
    Inscrit en
    Mai 2012
    Messages
    13
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur Java
    Secteur : Administration - Collectivité locale

    Informations forums :
    Inscription : Mai 2012
    Messages : 13
    Points : 33
    Points
    33
    Par défaut
    Sans doute mais à force de pinailler on risque de perdre l'auditoire. Voire le fil de la discutions.
    Pour ne pas perdre les lecteurs peu habitués à visualiser un échiquier voici quelques diagrammes associés à des idées amusantes.
    Trait au noir, le fou interdit Rh8 mais Fh8 est interdit car il est cloué et h8 et vide :
    Nom : roi_h8.jpg
Affichages : 1519
Taille : 54,5 Ko

    D'ailleurs que veut dire cloué ? On ne la pas définit clairement. Je propose donc une affirmation provocante :
    Il est possible qu'une pièce clouée puisse bouger.
    Je vois à travers mon écran ton aire dubitatif.
    Considère donc la position suivante (trait au blanc):
    Nom : clouage.jpg
Affichages : 1511
Taille : 16,1 Ko
    La tour ne peut pas se déplacer sur la ligne 2 car se faisant son roi serait en échec. On peut donc dire que ces déplacements sont interdits car la tour est clouée. Mais elle peut néanmoins se déplacer sur la colonne. Voir prendre la tour adverse et ce serait même conseillé.

    Donc, si on définit le clouage par :" une pièce est cloué si lorsque on l'enlève du jeu son roi est en échec" alors un clouage n'interdit pas tout les mouvements.
    C'est assez facile à coder mais pas très utile.
    Par contre si on définit le clouage par "tout mouvement de la pièce met son roi en échec" alors dans l'exemple la tour n'est plus clouée. C'est plus utile mais plus lourd à établir.

    Une autre position amusante que je souhaite soumettre :
    Nom : et_le_pion.jpg
Affichages : 1519
Taille : 16,6 Ko
    Les coups pour le pion blanc sont d3 et d4. Mais ils n'interdisent en rien au roi noir d'aller en d3 et d4 !
    Par contre ce pion interdit la case c3 au roi alors qu'il ne peut y aller !

    Digression : Le développeur java que je suis ne peut s'empêcher de se dire que ces positions sont les possibles sources d’intéressant tests unitaires.

    Ceci dit je viens de relire le premier message du fil. Le problème était "simplement" de déterminer les coups possibles pour toute pièce, roi compris.

    Je proposerais donc la procédure suivante valable pour toutes les pièces roi compris :

    • Faire la liste des cases possibles sans tenir compte des échecs (y compris pour les mouvements d'un roi)

    • Effectuer le coup.

    • Puis vérifier si le roi du joueur est échec.


    S'il l'est, le coup est impossible sinon le coup est jouable.

    ça résout en même temps la question des clouages et les déplacements du roi sur des cases menacées (attention néanmoins aux roques).

    Bien sur, les performances peuvent facilement être mises à mal.

    J'aime bien ton tableau [8][8] mais la mise à jour à chaque coup est délicate. Sans doute efficace, mais un éventuelle débeugage virera très vite à l'enfer.

    Autre avantage de cette façon de faire : le mat se résout de lui même. On en revient au règlement : le roi est en échecs et aucun coup (quelque soit la pièce) n'est légal car tous invalidé par le roi en échec à l'arrivé.

Discussions similaires

  1. [D5][SQL Server] Conserver des images dans la BDD
    Par FONKOU dans le forum Bases de données
    Réponses: 8
    Dernier message: 08/06/2008, 20h58
  2. [Frame] Gérer les composants
    Par chastel dans le forum Débuter
    Réponses: 4
    Dernier message: 07/05/2004, 18h57
  3. Gérer les clics sur les boutons
    Par cyberlewis dans le forum Windows
    Réponses: 4
    Dernier message: 08/02/2004, 16h34
  4. Comment gérer les espaces blancs?
    Par Lambo dans le forum XML/XSL et SOAP
    Réponses: 10
    Dernier message: 16/05/2003, 10h44
  5. gérer les jpg dans une fenetre directdraw???
    Par Anonymous dans le forum DirectX
    Réponses: 1
    Dernier message: 14/06/2002, 14h39

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo