Gérer les échecs (et mat)

Version imprimable

07/10/2014, 19h41
emixam16

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 ;)
07/10/2014, 20h56
10_GOTO_10

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).
07/10/2014, 22h55
Mat.M

Citation:

Envoyé par emixam16

. 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..:D , 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.
12/10/2014, 15h07
lautrec1

Citation:

Envoyé par 10_GOTO_10

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.
16/10/2014, 14h01
R. Daneel Olivaw

Citation:

Envoyé par emixam16

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.
16/10/2014, 14h25
Flodelarab

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.

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:

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

23/10/2014, 13h31
R. Daneel Olivaw

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

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.
23/10/2014, 14h18
lautrec1

Citation:

Envoyé par R. Daneel Olivaw

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.
23/10/2014, 15h07
R. Daneel Olivaw

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 !
23/10/2014, 16h41
lautrec1

Citation:

Envoyé par R. Daneel Olivaw

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.
23/10/2014, 18h08
R. Daneel Olivaw

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.
23/10/2014, 18h47
lautrec1

Citation:

Envoyé par R. Daneel Olivaw

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 ?? :zoubi:

@emixam
Le sujet n'est pas résolu. Est-ce que tout ça te parle ?
23/10/2014, 22h56
R. Daneel Olivaw

3 pièce(s) jointe(s)
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 :

Pièce jointe 159616

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

Pièce jointe 159617
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 :

Pièce jointe 159618
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é.