Quand échec et mat est impossible dans une position

10

Modifier Cette question n'est pas un doublon, comme mentionné dans mon commentaire. La question liée supposément en double ne répond ni à ma question n ° 1 ci-dessous, ni à la question n ° 3, ni à la question n ° 2, sauf si elle est mentionnée tangentiellement dans une réponse. La question liée concerne le matériel d'accouplement suffisant alors que ma question concerne les cas où le matériel peut être suffisant mais néanmoins échec et mat est impossible.


Les lois des échecs disent

1.5. Si la position est telle qu'aucun des deux joueurs ne peut éventuellement mater le roi de l'adversaire, la partie est nulle (voir article 5.2.2).

5.2.2. La partie est nulle lorsqu'une position est apparue dans laquelle aucun joueur ne peut mater le roi de l'adversaire avec une série de mouvements légaux. Le jeu se terminerait dans une «position morte». Ceci met immédiatement fin à la partie, à condition que le mouvement produisant la position soit conforme à l'article 3 et aux articles 4.2 à 4.7.

[Les articles 3, 4.2 à 4.7 traitent essentiellement des démarches légales.]

Ceci est intéressant car il ne semble pas évident que cette condition s'applique (bien que vraisemblablement rare dans les jeux réels!). Je pense que cela a dû être étudié avant. Je me demande:

(1) À quel point est-il difficile sur le plan du calcul de déterminer qu'aucune séquence de mouvements légaux ne se termine par échec et mat ? Existe-t-il un meilleur algorithme que la force brute?

(2) Connaissez-vous des exemples intéressants de postes où il est difficile pour un humain de dire si cette condition s'applique?

(3) Y a-t-il des exemples de jeux historiques où cette loi n'a pas été respectée parce que les joueurs et les officiels ne se rendent pas compte de la condition détenue? Particulièrement intéressant si le jeu ne s'est pas terminé par un match nul en raison de l'expiration du temps d'un joueur.

Inspiré par https://old.reddit.com/r/chess/comments/8ulfrt/using_fide_rules_if_white_runs_out_of_time_in/

(modifier) ​​Voir aussi cette question étroitement liée où la réponse acceptée a quelques autres exemples où il y a suffisamment de matière à accoupler, mais c'est impossible à partir de cette position.

usul
la source
Je doute qu'il y ait des positions difficiles pour l'homme de savoir s'il y a du maté possible ou non.
hoacin
2
@BrianTowers, cette question est étroitement liée, mais ce n'est pas un doublon. La question elle-même pose quelque chose de tout à fait différent. La réponse acceptée y touche le sujet mais ne traite pas vraiment de (1) - (3) sauf peut-être un peu de (2).
usul
@hoacin, je suis enclin à être d'accord, mais alors nous devrions être capables d'écrire des algorithmes rapides pour cela, non?
usul
1
Il y a la règle 9.3.2 les 50 derniers coups de chaque joueur ont été effectués sans mouvement de pion et sans capture. ce qui crée un tirage. Dans le fond de mon esprit, je me souviens d'une analyse informatique qui a montré un compagnon forcé dans plus de mouvements que cela. Une telle analyse est NP complète et donc aucun algorithme de temps polynomial n'a pu la trouver.
MaxW
1
Salut @fuxia, merci mais je ne suis respectueusement pas d'accord. (a) La question liée n'est un double d'aucune de mes questions. (b) Cette question a été parfaitement répondue dans une réponse courte et cohérente et tout a bien fonctionné - ou aurait été le cas sinon pour un marquage incorrect tardif comme double. (c) J'ai du mal à voir comment ces décisions de modération ou votre tentative de reproche améliorent le site en général ou cette question en particulier.
usul

Réponses:

7

Ce que vous demandez s'appelle "Dead Reckoning" dans le domaine des problèmes et des problèmes rétro.

(1) Je ne connais pas d'algorithme à part celui mentionné par zaifrun: la force brute. La raison en est que vous pouvez trouver des positions assez incroyables ...

(2) Découvrez de nombreux problèmes reposant sur Dead Reckoning sur le site Web d'Andrew Buchanan . Il existe également des bases de données de problèmes ( comme celle-ci ) où vous pouvez exécuter une recherche de «DR» dans la stipulation.

Un exemple concret dont je me souviens est celui-ci , que je reproduis ici. Par Andrew Buchanan, dans StrateGems 2002. Blanc pour bouger; quel a été le dernier mouvement dans cette position? (La position est morte, mais le dernier mouvement effectué doit provenir d'une position légale et en direct - il est donc uniquement déterminable.)

NN - NN

(3) Même les grands-maîtres ont techniquement fait des mouvements dans une position morte! Voir la page de François Labelle pour des exemples.

Remellion
la source
Pourquoi serait-il surprenant qu'un GM se déplace dans une position morte? Puisqu'une offre de tirage est censée être accompagnée d'un mouvement, je m'attends à ce qu'un MJ offre un tirage tout en effectuant un mouvement arbitraire. Si le joueur accepte le tirage, le dernier coup serait sans importance. Le MJ pourrait demander l'arbitre si l'offre de tirage est refusée, mais sinon pourquoi perdre le temps de l'arbitre?
supercat
Ce n'est pas surprenant, dans le sens où dans les jeux cités cela n'affecte pas le résultat du jeu. Cependant, c'est toujours (très techniquement) une violation des règles de faire n'importe quel mouvement (ou une offre de tirage) dans une position morte, car le jeu est déjà terminé à ce moment-là. Même les GM et les arbitres n'appliquent pas cela (bien que pratiquement parlant, ce n'est pas nécessaire non plus).
Remellion
Une fois un jeu terminé, je pense que tout ce qui se passera par la suite serait hors de propos, rendant toute question de légalité également hors de propos.
supercat
-4

Eh bien, c'est vraiment 3 questions, je ne suis pas sûr de répondre à tout ici.

Mais il existe un «algorithme» pour ce problème, mais il est NP complet, c'est essentiellement de la force brute, bien que vous puissiez faire quelques optimisations. Il s'agit essentiellement de l'algorithme de génération de base de table. Bien sûr, avec un grand nombre de pièces, cela devient difficile à appliquer, même pour une seule position.

Cette règle est fondamentalement là, vous pouvez donc réclamer un tirage dans des positions qui sont évidemment tirées comme évêque et roi contre roi seul sans pion et positions similaires.

zaifrun
la source
est les évêques sont de couleurs différentes, le compagnon est possible: k1K5 / b7 / 2B5 / 8/8/8/8/8 w - - 0 1, voulez-vous que je vous montre une séquence de mouvements légaux, qui peuvent se terminer en cette position?
lenik
Oui, mais je voulais dire 1 roi et évêque contre 1 roi. J'ai édité la réponse
zaifrun
Étrange affirmation qu'il est NP complet. Qu'est- nce que dans ce cas? Pouvez-vous expliquer comment vous pourriez réduire d'autres problèmes de NP à cela?
RemcoGerlich
@RemcoGerlich En particulier, c'est une erreur de catégorie d'appeler des algorithmes NP-complets, seuls les problèmes de calcul peuvent l'être. Le calcul d'une stratégie optimale pour les échecs généralisés sur un plateau n × n est cependant EXPTIME-complet. (Wikipedia donne la référence Aviezri Fraenkel and D. Lichtenstein (1981). "Computing a perfect strategy for n×n chess requires time exponential in n". J. Comb. Th. A (31): 199–214). La plupart des problèmes sur une carte 8 × 8 sont "triviaux" dans le contexte de la théorie de la complexité, car ils peuvent être résolus en temps constant. (même si cette constante est trop grande pour la résoudre dans la pratique)
Lézard discret