Sur le nombre de façons de gagner une partie d'échecs en n coups...

[invited68a324d]

Bonjour à tous!

Voilà, je me suis mis en tête mercredi de calculer le nombre de façon de gagner une partie d'échecs en n coups.
Je sais que c'est super complexe, mais bon, on peux toujours essayer!
Alors voilà: j'ai commencé par simplifier BEAUCOUP le jeu d'échec: je ne prend en compte que 12 pions qui ne peuvent avancer que d'1 case à la fois (voir doc joint).
Le joueur gagnant est celui qui parvient à amener 1 pion à l'autre extrémité du plateau...

J'ai donc considéré 8 cas différents de la position que peut avoir un pion de mon équipe (G=il y a 1 pion adverse à la diagonale gauche; D=il y a 1 pion adv. à la diagonale droite et M=il y a un pion adverse au milieu):

-RIEN (aucun pion), avec une probabilité de (53!/45!) sur (56!/48!)
-G uniquement, avec 1 proba de (8*53!/46!) sur (56!/48!)
-D uniquement avec la mme proba que G
-M uniquement avec la mme proba que G
-G et D uniquement avec la proba (6*53!/47!) sur (56!/48!)
-G et M uniquement avec la mme proba que GD
-D et M avec la mme proba que GD
-G et D et M avec la proba (336*53!/48!) sur (56!/48!)

et ensuite mon idée à été de désigner chaque case par une double coordonnée, c'est-à-dire d'assimiler mon échiquier à un plan complexe...ce qui me permet d'appliquer des fonctions à mes pions (qui sont désignés par des nombres de la forme: z=a+ib aves (a,b) des entiers naturels compris entre 1 et 8).

Mes fonctions sont les suivantes:

-Si on a: GD ou G ou D ou RIEN, on applique au nombre: f(z)=z+i
-Si on a: G ou GD ou GM ou GDM, on applique au nombre: g(z)=z+i-1
-Si on a: D ou GD ou DM ou GDM, on applique au nombre: h(z)=z+i+1

Après ça, mon but (intermédiaire) est de trouver la probabilité d'utiliser chaque fonction...
Et là, je bloque: vu que parfois pour les mmes situations (comme par exemple GD) on peut appliquer 2, voire 3 fonctions différentes, comment obtenir les probas pour chaque fonction (dont la somme doit valoir 1).
Faut il, par ex pour GD diviser chaque GD par 2 (GD apparaissant 2 fois) ?
Si qq1 as une idée, je suis preneuse !
Si vous voulez des précisions, je me tiens à votre disposition
-----

[invited68a324d]

Erreur dans mon précédent message:

"-G et D uniquement avec la proba (56*53!/47!) sur (56!/48!)"

[shokin]

Salut lucile972FDF,

Tu peux explorer diverses pistes : (on exclut aussi, pour simplifier, les abandons de partie, les résultats à l'amiable, etc.)

1. Combien de demi-coups (tu joues un demi-coup, ton adversaire joue un demi-coup, etc.) au minimum dure une partie ? (la personne qui commence peut gagner en 13 demi-coups [ceux de son adversaire compris], l'autre peut gagner en 14 demi-coups ; ou après 12 demi-coup, la partie ne peut pas être terminée, aucun gagnant)

2. Calculer ensuite les probabilités après 13 demi-coups : soit M le joueur qui commence la partie, N l'autre joueur, la probabilité que M gagne après demi-coups + la probabilité que la partie ne soit pas terminée = 1.

3. Calculer ensuite les probabilités après 14 demi-coups : s'il y a eu un 14ème demi-coup, cela signifie que M n'a pas gagné au 13ème demi-coup. De plus M ne peut pas gagner au 14ème demi-coup. Donc probabilité que N gagne + probabilité que la partie ne soit pas terminée = 1. [On pré-suppose, pour tout n naturel plus grand ou égal à 2, que si le n-ième coup est joué, le (n-1)ème coup a été joué et n'a donné lieu à aucun gagnant.

4. A un moment donné, à partir du m-ième demi-coup, la probabilité que la position des pions soit bloquée (6 pions contre 6 pions ; plus tard 5 pions contre 5 pions) ne sera plus nulle. Déterminer en combien de demi-coups au minimum peut-on arriver à une position bloquée (logiquement, ce sera un nombre pair). Calculer cette probabilité. Trucs : il existe des positions bloquées impossibles (analyse rétrograde) étant donné que chaque pion avance (ou mange) d'une case. Si une position est bloquée, en fait, le nombre de pions bloqués (forcément le même pour chaque joueur) détermine le nombre de demi-coups joués. Calculer le nombre de demi-coups, en fonction de x, selon le nombre de pions bloqués de chaque couleur (x pour M et x pour N).

5. Comme, dans ta position de départ donnée,

[inviteea028771]

Sauf que ces probabilités sont fausses, puisqu'un grand nombre de positions sont impossibles.

Par exemple il est impossible pour les pions de se retrouver en colonne 1 ou 8. Les pions B ou G ne peuvent donc pas avoir 3 pions en face d'eux


Et plus généralement, je pense qu'une approche probabiliste classique n'est pas la bonne (par contre une approche type méthode de monte-carlo serra sans doute efficace pour faire un programme fort).
En effet, il peut exister un jeu ou le joueur A ne gagne que 0.001% du temps alors que le joueur B gagne le reste du temps si on compte le nombre de parties possibles, mais ou le joueur A gagnera à 100% si la partie est entre deux vrais joueurs

[A voir en vidéo sur Futura]

[shokin]

Erreur de manipulation, je continue :

5. Comme, dans ta position de départ donnée, les pions de M et ceux de N sont situés, "par paires", sur les mêmes colonnes, les colonnes vides sont superflues. S'ils étaient sur des colonnes différentes, la donne aurait un peu changé : par exemple, les pions de M sur les colonnse A, B, C, D, E et F et les pions de N sur les colonnes A, B, C, F, G, H. Un pion ne peut sortir d'une colonne et entrer alors dans une autre colonne que si un pion adverse se trouvait dans cette dernière et juste "en face" de lui.

6. Déterminer les situations de nullité : pions bloqués forcément (il ne peut pas ne rester aucun pion sur le plateau ; et un joueur a l'obligation d'avancer un pion tant qu'il peut en avancer au moins un).

7. De manière générale, déterminer tous les types de situations impossibles (compte tenu de la position initiale et des règles du jeu que tu as définies), avec un peu d'analyse rétrograde : plus de 6 pions pour un joueur ; les 12 pions s'étant croisés sans se manger (ou chercher le nombre minimal de pions tel que cette situation est impossible) ; un pion sur une colonne initialement vide ; etc. Ces situations seront à exclure de notre supposition "tout est possible".

8. Distinguer les probabilités que, après n demi-coups, [le joueur M (celui qui a commencé) ait u pions ET le joueur N (l'autre joueur, celui qui joue les demi-coups pairs) ait v pions]. Rappelons qu'il ne peut pas y avoir 0 pion sur le plateau. Éventuellement déterminer s'il y a un nombre minimal de pion différent de 1 sur le plateau.

9. Déterminer le nombre maximal de coups que peut durer une partie. Il y en a un, étant donné qu'à chaque demi-coup, un des joueurs doit "avancer" un pion d'une ligne (par conséquent, une position ne peut pas se répéter au cours d'une même partie), étant donné aussi que la partie se termine automatiquement quand un pion a avancé de 7 cases, et que c'est la seule possibilité que la partie se termine gagnant-perdant. [Les situations d'égalité sont celles de blocage.]

Une autre idée de problème "pas trop compliqué" (quand même un peu plus ) serait d'ajouter au moins une autre pièce (roi, dame, tour, fou, cavalier, qui peuvent toutes faire aller-retour) pour chaque joueur, puis de définir n (nombre naturel non nul), dans les règles du jeu, tel qu'une position répétée n fois aboutit forcément à l'égalité. Peut-être le plus "simple" serait le cavalier, qui est obligé de changer de couleur de case à chaque demi-coup.

Une des choses qui changent la donne est aussi le fait d'avoir une pièce "sacrée" (appelez cela comme vous voulez), c'est-à-dire une pièce qui a l'obligation, si elle est menacée, de ne plus l'être au suivant demi-coup. L'impossibilité de respecter cette règle donne lieu au résultat gagnant-perdant (en l'occurrence, c'est le roi ; imaginez si ç'avait été la dame ! ; intéressant aurait été le cavalier). Le caractère "sacré"* de cette pièce a donné aussi lieu à l'existence du pat. (* combiné à l'existence d'au moins deux types de pièces aux mouvements différents ; une situation de pat n'est pas possible s'il n'y a que des rois sur un échiquier)

[invited68a324d]

Merci pour tous ces conseils!
J'ai une semaine très chargée, mais je vais bientôt les regarder en détail!