|
| Résolution de échecs 5x5 par ka***d*154 le
[Aller à la fin] |
| Informatique | |
Avec un collègue nous avons résolu les échecs 5x5 (appelés Gardner Chess) : ce sont les échecs normaux qu'on joue sur un plus petit échiquier en retirant toutes les pièces de l'aile roi. Les pions ne peuvent avancer de deux cases et il n'y a pas de roque, toutes les autres règles sont conservées.
Bien que petit par rapport aux échecs normaux le nombre de positions légales est de l'ordre de celui du jeu de dame classique (10^19 en gros).
On a prouvé que la valeur théorique de ce jeu est "nul" c'est à dire que le jeu parfait débouche forcément sur une partie nulle.
Ce qui est amusant est que cette variante avait été jouée par correspondance durant les années 90 avec des résultats proches de ceux des échecs (blanc 40% de victoires, nulles 28% et Noirs 32% de gains). Ca se voit un peu dans notre preuve dans le sens où prouver la nulle pour les noirs est plus dur.
Ce qui est intéressant est la manière dont on la prouvé : on n'a pas cherché à énumérer tous les coups possibles ni même chercher les meilleurs. On s'est aidé d'une version de stockfish modifiée (qui peut nous trouver des mats en plus de 50 coups sur un si petit échiquier) qu'on aidait "à la main" en le poussant dans les bonnes lignes (y compris pour trouver les mats). Cette approche hybride homme-machine accélère les recherches de mats à un niveau incroyable.
Un autre point important est que notre preuve est lisible par des êtres humains (ce qui n'est pas le cas pour les dames dont la preuve a utilisé des centaines d'ordis sur dix ans et qui est trop énorme). On ne s'est servi de l'ordi que pour clore la discussion (quand une position est perdue on spécifie une distance max au mat alors qu'humainement c'est clair que c'est perdu : mais comme ça il n'y a pas de discussion possible).
Pour ceux que ça intéresse le lien de notre article qui contient les oracles pour forcer la nulle pour les blancs et les noirs. J'ai aussi fait un site Mini chess resolution qui regroupe des infos supplémentaires pour ceux que ça intéresserait : les parties parfaites en Gardner les ouvertures parfaites etc.
On s'attaque à Los Alamos chess (les échecs sans les fous sur 6x6) c'est quasiment certainement une nulle mais là la preuve sera plus subtile et plus longue. On va aussi s'essayer à prouver que des nulles de GM sont de "vraies nulles" (ou les parties de TCEC qui sont de bons candidats pour construire des oracles de nulles).
Il se pourrait qu'on ne soit pas si loin que ça de la décision du jeu d'échecs. Ca me semblait impossible il y a peu mais maintenant ce n'est plus le cas du tout.
|
|
|
Intéressant et merci de partager ce lien.
Mais il y a tout de même des choses comme "white is a piece up for nothing" qui sont convaincantes mais pas vraiment prouvantes mathématiquement ou j'ai raté quelque chose ?
EDIT : ok en lisant avec plus d'attention #47 signifie mat en 47. Donc si SF n'a pas de bug sur la résolution de mat ça semble effectivement ok.
Malgré tout il faudrait regarder attentivement la position sur un diagramme pour évaluer des phrases comme "White cannot progress wihtout giving a piece or moving d5 + after which the Black King blocks the position". En effet, il arrive parfois que juste bouger les pièces sans but apparent produise des résultats inattendus (on en voit des exemples sur TCEC avec de longues phases de manœuvre de dizaines de coups, ou avec les tablebases qui produisent des mats très long sans qu'un humain ait l'impression qu'il y ait progression quelconque).
Par contre pour le 6x6 et surtout le 8X8 tu t'emballes un peu à mon avis vu la structure de la preuve.
|
|
|
Quand je met un commentaire comme ça c'est pour l'humain. En fait la machine te certifie un mat en x coups dans ce genre de positions. Disons l'idée est qu'il est impossible de perdre (gagner est un plus) et que "ça se voit". Comme c'est effectivement subjectif suivant le niveau de la personne qui regarde on donne en plus la distance au mat calculée par la machine (dont les sources sont téléchargeables, vérifiables et éxécutables sur le site de Minichess).
Typiquement si les Noirs donnent un cavalier au premier coup on peut calculer la distance au mat tout de suite et d'un point de vue humain on voit bien qu'ils vont perdre. J'insiste sur le fait qu'on doit juste prouver que 1) Blanc ne perd pas et 2) Noir ne perd pas. Quand on fait un oracle pour Blanc prouver un mat est un plus car ça clot justement toute discussion sur le côté subjectif.
|
|
|
On vient de montrer que Mallet chess (c'est à dire la variante où les noirs ont dans l'ordre Tour, Fou, Roi, Dame, Fou et les blancs Tour, Cavalier, Roi, Dame, Cavalier) est un gain forcé pour les noirs (mat en 25). Par contre si on inverse et que ce sont les noirs qui ont les cavaliers c'est une nulle.
|
|
|
J'exhume ce post car je ne sais pas si la nouvelle suivante a été diffusée sur le forum.
La variante des échecs à qui perd gagne a été résolue en octobre 2016 et les blancs sont gagnants avec 1.e3. La "meilleure" défense pour les noirs est 1...b6 mais ne suffit pas à annuler.
La ligne la plus résistante a été 1.e3 b6 2. a4 e6 3. Ta3 Fxa3 4. Cxa3 Dh4 et finalement il a été montré que 5.a5 était gagnant, après avoir tenté de démontrer que 5.h3 l'était sans succès.
Bien sûr beaucoup de premiers coups blancs sont perdants (1.a3, 1.b4, 1.c3, 1.d3, 1.d4, 1.e4, 1.f3, 1.f4, 1.h3, 1.h4, 1.Nc3, 1.Nf3 entre autres).
http://magma.maths.usyd.edu.au/~watkins/LOSING_CHESS/LCsolved.pdf
La page de Fabrice Liardet
http://www.pion.ch/Losing/
|
|
|
Perso je pense vraiment que la résolution des échecs classiques est déjà à notre portée, aussi insensé que ça puisse paraître. Il faut trouver un moyen de réduire drastiquement le nombre de lignes à analyser en apprenant à la machine à identifier beaucoup de nulles certaines et de gains certains sans calcul et sans avoir à le faire manuellement (c'est extrêmement difficile mais je pense que c'est faisable). Je pense que la résolution du poker NLHE et PLO sera beaucoup plus difficile par contre, même si on a des outils déjà capables d'approcher de très près le GTO.
Bravo en tout cas pour ces résultats, impressionant!
|
|
|
Je n'y connais pas grand chose mais la piste que tu évoques me semble compliquée car on est très loin de pouvoir certifier une nulle ou un gain actuellement malheureusement, à part les mats forcés et les tables de fins de partie.
En revanche, je me demande s'il n'est pas possible de prouver quelque chose en modifiant un peu les règles du jeu. Imaginons par exemple un jeu où les blancs doivent mater ou prendre la dame noire pour gagner. Les noirs quant à eux doivent mater (comme dans le vrai jeu). Si on prouve que les blancs sur un jeu parfait sont incapables de gagner ce jeu, ils sont également incapables de gagner au vrai jeu ou je fais erreur ?
|
|
|
Oui j'ai également appris par hasard que le "qui perd gagne" a été "résolu". Au passage j'adore cette variante que j'ai étudiée à l'époque à l'aide du site de Fabrice Liardet que je connais personnellement. J'y joue sur lichess.
Par contre la résolution n'est pas complète, dans le sens ou il n'est pas complètement "tablebasé" mais toutes les défenses sur 1.e3 ont été percées. D'ailleurs l'implication humaine a aidé presque par hasard à accélérer la résolution avec ce 5.a5 entre autres. Il me semble qu'il y a 3 définitions du terme résolutions, selon qu'elles soient complètes comme une tablebase 6 pièces, ou non.
|
|
|
En effet il y a plusieurs types de résolution :
- ultra-faible : on connaît le résultat sur un jeu parfait mais on ne connaît même pas une façon de jouer parfaitement
- faible : on connaît le résultat sur un jeu parfait et on peut exhiber au moins une partie parfaite
- forte : dans chaque position possible, on connaît le jeu parfait( et bien sûr le résultat sur un jeu parfait).
Contrairement à ce qu'il pourrait sembler, la résolution ultra-faible (exemple jeu de Hex) est la plupart du temps la plus jolie car on arrive à prouver qui gagne par des arguments généraux sans savoir comment (et savoir comment est souvent du calcul brut d'intérêt limité).
|
|
|
@dan31: ok, mais tu risques d'avoir dépensé pas mal d'énergie pour rien, car si tu montres que les blancs sont capables de gagner (ou d'annuler?) ton jeu modifié (le plus probable?) tu ne pourras rien en déduire pour le jeu normal (à cause des sacrifices de dames), non?
Il y a une liste des jeux résolus sur Wikipedia
|
|
|
Et pour la variante du king of the hill / chess.com la machine dit quoi ?!
|
|
|
Abrobecker : tu as parfaitement raison dans le cas où les blancs gagnent la variante du jeu modifié. Par exemple la variante suivante : les blancs doivent effectuer une prise ou mater, les noirs doivent mater. cette variante est trivialement gagnante pour les blancs : 1.g3 xxx 2.Fg2 xxx 3.F prend quelque chose sur la grande diagonale. Et en effet, comme tu le dis, on ne peut rien en déduire sur le vrai jeu d'échecs.
En revanche il me semble que si les blancs ne sont pas capables de gagner une variante du jeu où l'objectif est plus facile à atteindre pour eux, alors ils ne sont pas non plus capables de gagner au vrai jeu. Et cela démontrerait que les noirs ont au moins la nulle au vrai jeu.
Ainsi, bâtir une variante du jeu qui permette de prouver cela pourrait faire avancer les choses si mon raisonnement est juste. Par exemple
- faire dame ou mater
- capturer la dame adverse ou mater
- capturer une pièce adverse ou mater
Il faudrait dans l'idéal trouver une variante à la fois simplifiante en terme de complexité du jeu afin de pouvoir effectuer les calculs, mais également où les blancs n'ont pas mieux que la nulle.
|
|
|
Ce fil m'a donné une idée de variante d'échecs improvisée aujourd'hui, mais qui nécessiterait une interface informatique, comme lichess. Je l'appelle échecs brouillard de guerre. Il pourrait se jouer avec 2 échiquiers réels (les 2 joueurs sont séparés, chacun sur un échiquier, jouant ses propres coups) et un "arbitre" qui "joue" (qui dévoile le brouillard/brouille le jeu adverse). Pas pratique en vrai, mais faisable.
L'idée est inspirée des jeux de stratégies en temps réel (étant un amateur du genre dont age of empires 2 conquerors que je repratique avec plaisir). Dans ces jeux de stratégies, chaque camp se développe sans voir ce que fait l'autre à moins qu'une unité ou bâtiment ouvre le champ de vision (souvent limité) du camp adverse, ce qui amène parfois un camp à jouer une stratégie faible mais qui est dangereuse si l'autre ne voit pas.
Ca peut être une stratégie immédiatement perdue si le contre a eu lieu, ou immédiat gagnante si l'autre n'a rien vu venir, on pourrait qualifier ça "all-in" en quelque sorte. A Starcraft 2 il me semble qu'ils appellent ça "cheese" en anglais. Mon autre source d'inspiration était une variante sur fics où on jouait sans jamais voir les pièces adverses.
Aux Echecs c'est comme si on tentait un mat du berger, sauf que la punition en cas de raté n'est pas si grave. A noter que dans "ma variante", tenter un mat du berger se révèle réellement tentant, car selon le début joué, on ne le voit pas venir, ce qui demande soit de jouer un coup rapide d'exploration, soit de jouer un début du style e3+Cf3.
Dans "ma variante", est brouillée toute case qui ne serait pas contrôlée. Ainsi un rapide g3+Fg2 pourrait révéler toute la grande diagonale jusqu'à que le fou rencontre un obstacle. Le pion b7 serait vu, mais pas la Ta8. On pourrait tout à fait se retrouver avec une "tâche aveugle" dans notre propre camp, avec une pièce adverse qui s'y cache. L'échec devrait être annoncé.
On pourrait imaginer un pouvoir qui permette à un joueur de révéler tout le jeu (à voir si on compte ça comme un coup, mais il faudrait éviter que ce soit utilisé comme astuce pour inverser le trait, sinon on peut dire que chaque joueur peut demander une fois chacun la révélation de l'échiquier, mais que ça le fait pour l'adversaire également (ou l'adversaire est au courant).
Il est possible que des finales gagnantes triviales deviennent un vrai casse-tête, un simple roi et tour contre roi pourrait devenir un jeu de cache-cache.
Qu'en pensez-vous?
|
|
|
Un peu un côté stratego je trouve :). Pourquoi pas, tu peux en faire une app mobile si tu penses bien le concept en détail. Il y a du potentiel. On voudra se développer sur des cases qui ne sont pas facilement "débrouillardées" par l'adversaire, etc..
Ca me semnble plus intéressant potentiellement que le récent "Choker" (une app mobile qui mélange échecs et poker, où on fait des tours d'enchèère en fonction de la main de pièces d'échecs que l'on reçoit, puis on place les pièces une par une et on joue - Hikaru est très fan, moi pas trop). Essaie de tester déjà un peu tel que présenté (sans pouvoir de révélation de l'échiquier, juste le "case contrôlée révéléee, case non contrôlée brouillard", vaut toujours mieux faire simple).
|
|
|
Je ne sais pas programmer mais si on y parvient (avec juste la règle des pièces cachées pour commencer) je jouerais avec toi volontier pour tester!
|
|
|
@dan31: tout à fait, si on résoud une variante plus simple pour les blancs en disant qu'il ne peuvent pas gagner, on a une grosse information sur le jeu standard. Mais ça me semble très improbable, d'ou mon commentaire sur l'énergie dépensée pour rien...
@ArKhein: ce ne serait pas le Dark Chess par hasard? On peut y jouer ici!
|
|
|
ouch.. Dur de trouver des idées de jeux originales de nos jours (comme pour bcp d'autres choses) :). La seule diff dans ce que Arkhein proposait c'est l'annonce de la mise en échecs.
|
|
|
ah sur l'appli on voit les cases où le roi n'a pas le droit d'aller, donc un peu différent de ce que décrit l'article de wikipedia, ça ressemble encore plus à ce que proposait Arkhein. Ca a pas l'air facile commme variante, j'ai rapidement gagné une pièce et je l'ai déroqué avec un Df7+, mais ensuite j'avais plus la moindre idée d où son roi était allé et j'ai commencé à perdre pièce après pièce et me suis fait laminer :).
Il semble qu'il faille être assez prudent et vraiment chercher à éclairer un max de cases adverses à distance avant de se commit en avançant des pièces.
|
|
|
Je me suis fait laminer dans mon premier essai. Je l'ai sousestimé. Par contre il n'arrivait pas à mater mon roi quasi nu, j'ai fini par l'aider en mettant mon roi sur des nouvelles cases au lieu de répéter. La deuxième partie j'ai trouvé un développement pas mal qui est prudent, mais c'est dûr d'avancer sereinement. La différence avec mon jeu imaginé, c'est qu'on verrait même pas le pion noir g4 si mon pion blanc est en g3. On verrait juste que g3 ne peut pas avancer. Et on verrait les pièces capturées dans les bords, comme dans une partie réelle, car là on doit s'en rappeller.
|
|
|
A part ça merci Abrobecker pour ce site, il est incroyable! J'ai testé le jeu d'échecs 5x5 contre l'IA, nulle rapide. Toujours pas réussi à gagner au darkchess mais j'ai été écrasant mais j'ai tout lâché et on peut dire match nul au final. J'aimerais essayer sur une meilleure interface contre un humain, et si possible avec le pion qui ne voit pas devant lui.
|
|
|
Ca y est j'ai battu l'IA de bon matin, après plusieurs essais je pense avoir trouvé plusieurs ouvertures/idées intéressantes. Le joueur noir se doit d'être encore plus prudent qu'en temps normal car il doit imaginer diverses attaques doubles potentielles...
|
|
|
@ArKheiN: de rien, c'est vrai que le site est extra. Un autre site nous propose (par exemple) de gagner cette partie. Moi j'y arrive pas... O_o
Le dark chess est vraiment fait pour être joué sur une interface informatique, par contre le kriegspiel peut être joué avec des humains. On y joue régulièrement lors de la rencontre des problémistes d'échecs.
|
|
|
ahah amusant comme exercice de jouer contre ordi avec RN en e4 :). Pas eu trop de mal quand même, mais il se défend bien évidement :)
|
|
|
J'ai réussi du premier coup en le mattant au 26ème mais j'avoue que j'ai failli le laisser filer après avoir sacrifié et échangé plusieurs pièces. Il est possible qu'on n'arrive pas à battre un SF11 sur ordi puissant en blitz à tous les coups.
|
|
|
Je l'ai maté en 10 coup sur un smartphone....après avoir raté bien 20 fois sur pc...
|
|
|
Je ne sais pas comment vous faites pour le mater si vite. Que j'essaye sur ordinateur ou sur mobile, quel que soit le mode de développement que je choisis, il parvient toujours à aller cacher son roi suffisamment pour que la partie dure bien plus longtemps.
J'arrive bien sûr à gagner, car pour cela il doit faire d'énormes concessions, matérielles (ça peut inclure une perte de dame en 12 coups) comme positionnelles si fortes qu'en faisant attention ça se gagne à la main. Mais on est bien loin d'un mat en 24, voire en 10 !
Après, j'ai sans doute toujours eu un jeu pas assez tranchant, avec des attaques plus stratégiques qu'hyper violentes, mais bon ...
Pourriez-vous nous dire à quoi ressemblent vos parties si rapidement terminées ?
Edit: Ah j'arrive maintenant à mater en 12 coups sur mon smartphone. En sacrifiant très vite un fou.
Et finalement 9 avec un coup sans échec qui accélère le dénouement.
|
|
|
Je me suis réveillé avec une nouvelle idée de variante sympa, en quelque sorte aussi inspirée de l'univers des jeux de stratégie en temps réel, ou des jeux de stratégie avec une action par "tour".
Contrairement à la variante dark chess, celle ci est assez facile à mettre en place en face à face, et programmable aussi en virtuel.
On pourrait appeler cette variante Chrono-chess ou en français un truc du style tempo-échecs.
Les règles du jeu d'échecs restent inchangées dans l'ensemble. Les 2 camps jouent en même temps leur coup prévu à^la limite du temps fixé (chronomètre de 2 minute par coups par exemple).
Idéalement il faudrait pouvoir l'écrire en cachette pour les cas de contestations si on a joué le coup physiquement après l'adversaire. Sur le web, ça serait un simple prémove.
Du fait de ce changement de règle, il en implique d'autres, il serait potentiellement possible de mater l'autre en même temps qu'on se fait mater, ça ferait un match nul. Les 2 camps pourraient donner échec en même temps, au coup suivant il faudrait simplement que chacun pare son échec.
Un cas bizarre pourrait être: l'un joue "a prend pion b5" tandis que l'autre a prévu ..b4. On ne peut bouger un pion qui se fait manger, on ne peut manger un pion qui bouge, il faut bien fixer une priorité, j'imagine à donner la priorité au mouvement de pion, et celui qui n'a pas pu capturer voit simplement son coup "annulé" comme s'il n'avait rien fait. Les pièces n'ont pas ce problème car seul le pion ne se déplace pas comme il capture. Par contre si la case n'est plus accessible à cause d'un obstacle, on peut imaginer que le coup empêché est annulé.
Il y a peut-être des situations possibles auxquelles je n'ai pas pensé qu'il faudrait fixer.
Ca peut donner des parties drôles.
|
|
|
@Arkhein
D'autre cas bizarre : un fou blanc en a4, un fou noir en e8, toutes les cases entre les deux fous sont vides. Les blancs jouent Fd7, les noirs Fb5. Les deux coups sont-ils valides ? Ou choisit-on un ordre de priorité (blanc puis noir, dans ce cas le coup noir est impossible)? Ou encore on se dit que comme les deux pièces se sont croisées en route, elles se sont échangées, et les pièces disparaissent ?
|
|
|
Ah oui voilà un cas auquel je n'ai pas pensé, et il y en a probablement d'autres. On pourrait dire que ça provoque un échange car donner la priorité à une couleur dénature un peu le principe je dirais. Autre possibilité, traiter le coup comme un double obstacle, annuler les 2 coups quand le coup initial est impossible pour les 2 camps.
|
|
|
et si les deux couleurs recommencent aux 2 coups suivants, nulle par triple annulation ? ;)
Bon je préfère limiter les cas d'annulation de coups, parce que sinon çà risque d'éterniser les parties (par exemple plusieurs annulations différentes successives)
|
|
|
très amusant de mater le roi en e4
bon en bullet j'en ai perdu un paquet quand même
Mais j'ai fini par trouver un mat en 12
|
|
|
et en 10
une anglaise
c4, Cf6
d4, Rf5
Dd3, Ré6
g3, Ca6
Cc3, b6
d5+, Rd6
Cb5, Rc5
Fe3, Rb4
Db3, Ra5
Da3#
c'est sympa. Merci Alain, tu as toujours des pépites à proposer
|
|
|
J'ai été plus long mais avec style (on dirait un gambit du nord qui s'est bien passé :P) :
1.d4 Rd5
2.c4+ Re6
2.d5+ Rd6
3.c5+ Rxc5
4.Fe3+ Rd6
5.Ff4+ e5
6.dxe6ep+ Rxe6
7.e4 Re7
8.Fc4 Re8
9.Cf3 Df6
10.Fe5 Dg6
11.Fxc7 Dxe4+
12.Fe2 Db4+
13.Cc3 Dxb2
14.Tc1 Fb4
15.Fe5 Rf8
16.o-o Cc6
17.Fd6+ Fxd6
18.Dxd6+ Cge7
19.Cd5 Dxa2
20.Fc4 Da5
21.Tfe1 g6
22.Df6 Tg8
23.Cxe7 Cd8
24.Cg6 Tg7
25.Cc6 Dxg5
26.Dxg5 Tg8
27.Cxd8 Rg7
28.Te7 Tf9
29.Cxf7 d6
30.Ce5+ Tf7
31.Txf7+ Rg8
32.dd8#
|
|
|
@ArKheiN: je n'ai pas tout compris de ta desription, mais cela m'a fait penser à Apocalypse de C.S. Elliott:
https://en.wikipedia.org/wiki/Apocalypse_(chess_variant)
Il y a une éternité (2008) j'avais commencé un programme en ligne de commande qui joue à ce jeu:
http://abrobecker.free.fr/chess/apocalypse.htm
@ricou: de rien! ;-)
|
|
|
Je n'avais pas vu ce fil :)
La première = Dark Chess en effet, jouable (en direct et par correspondance) sur mon site. Il y a deux options possibles, s'arrêter au mat où à la capture du roi - j'ai préféré cette dernière, comme sur Buho21. Pas eu de demandes pour l'autre version jusqu'ici...
La seconde correspond à celle que j'ai appelé Synchrone (Chess) : jouable également.
Au passage vous pouvez aussi jouer à Apocalypse sur vchess.club depuis quelques mois ;) Les règles de résolution des coups simultanés sont différentes, plus complexes pour Apocalypse.
|
|
|
Mat du roi en e4 sinon, après divers tatonnements :
1.Cc3+ Re5
2.d4+ Rf6
3.Fg5+ Rxg5
4.h4+ Rf6
5.Ce4+ Rg6
6.h5+ Rf5
7.g4+ Rxe4
8.Dd3+ Rd5
9.Fg2+ Rd6
10.Da3+ Re6
11.De3+ Rf6
12.De5#
|
|
|
10.Dg3+ Re6 11.De5# est mieux '^^
Stockfish ne prend pas le fou g5 pour éviter cette suite, et propose plutôt 3.Ce4+ Rg6 4.Cf3 f6 5.Ceg5! fxg5 6.Ce5+ interdisant la case f7, 6...Rf6 7.Df3+ Re6 8.Df7+ et mat rapide. Je me demande quel est le mat le plus court dans la position initiale. Sans doute +10 coups ?
|
|
|
J'ai un mat en 8 (enfin c'est pas vraiment moi, c'est le logiciel Ruffian) :
1 Cc3+ Re5
2 Cf3+ Re6
3 Cg5+ Rf6
4 e4 Cc6?
5 Df3+ Rg6
6 Df5+ Rh5
7 C*f7+ Rh4
8 g3#
|
|
|
