Bonjour,

 Cliquez pour afficher

On numérote les pions de 1 à n en partant de la droite
On numérote les cases à partir de 0 (en partant de la droite)
2 pion s: Les bases sont deux pions collés (évident)

3 pions : Les bases sont pion 1 sur case c, c cases vides entre pion 2 et pion 3
A partir d'un position non base quelconque, si l'espace entre pion 2 et pion 3 est strictement plus grand que c, on rapproche pion 3 de pion 2 pour se ramener à l'égalité.
si l'espace entre pion 2 et pion 3 est strictement plus petit que c, on rapproche pion 1 de la droite pour se ramener à l'égalité.
Il est évident que l'on est obligé de sortir d'une base.

4 pions : Même chose mais c est le nombre de cases vides entre pion 1 et pion 2, et doit être égal  aux nombre de cases vides entre pion 3 et pion 4.
La démo est essentiellement identique à celle d'au dessus, le joueur ayant la stratégie gagnante ne touchant jamais au pion 1.

weierstrass

 Cliquez pour afficher

je crois comprendre ce que tu veux dire mais tout ça n'est pas très clair...

qu'appelles-tu "bases" ? une position gagnante ? perdante ?

si j'ai compris le raisonnement cela me semble correct pour 3 et 4 pions

à généraliser ...

Oui, je ne sais pas pourquoi je parle de bases, je voulais parler des sommets du noyau.

ah là d'accord... je comprends mieux

donc de ce qu'on appelle les situations perdantes finalement ...

Bonsoir,
Intéressant. Ça veut dire quoi la stratégie gagnante ?

Bonjour,
Un bon joueur de dames est confronté à ce genre de situation
en diagonale .

Ramanujan
Dans un jeu à stratégie gagnante, il y a deux joueurs. Chaque joueur joue à son tour et est forcé de jouer. Chaque coups mène le jeu à un différent état. Le nombre d'état atteignable (depuis la position de départ) est fini, et il ne peut y avoir de cycles. Les deux joueurs ont tout deux une connaissance parfaite de l'état du jeu. Dans ce cas, un théorème (assez facile à démontrer, et c'est un exercice intéressant) montre que l'un des deux joueurs a une stratégie gagnante, qui consiste à laisser sans cesse l'adversaire sur une position perdante quand viens son tour de jouer.

Par exemple, ici, les différents états sont toutes les positions possibles de pions sur la ligne. On peut naturellement representer ce état par un nombre binaire, en remplacant les pions par des 1 et les vides par des 0. Les états accessibles sont ceux représentés par un nombre binaire inférieur à celui qui représente l'état initial. On voit donc bien que le nombre d'états possibles est borné. De plus il ne peut y avoir de cycles, puisque chaque coup fait décroitre strictement la taille du nombre binaire représenté...

De manière mathématique, on peut représenter tout jeu de ce type comme un graphe, avec les différents états du jeu comme sommets, et des arcs allant d'un sommet à un autre si un coup valide est autorisé entre ces deux états. Le graphe obtenu (avec seulement les états admissibles) est un graphe fini orienté sans cycle. Les positions perdantes sont alors données par le noyau du graphe, c'est à dire un ensemble de sommet à la fois stable et dominant. (Le théorème cité précédemment consiste à prouver l'existence d'un noyau dans un  DAG -- directed acyclic graph )

Le noyau signifie donc que d'une position perdante, tout mouvement aboutit à une position non perdante (que l'on appelle gagnante), et de toute position gagnante, il existe un mouvement qui aboutit à une position perdante.

Par exemple, dans le célèbre jeu des allumettes, où on peut retirer 1,2 ou 3 allumettes, et on perd si on prend la dernière allumette, la stratégie gagnante est :
"les positions perdantes sont celles où le nombre d'allumettes est 4k + 1, k > 0"
En effet, de toute position perdante, que l'on prenne 1,2 ou 3 allumettes, le nombre d'allumettes restantes ne sera pas sous la forme 4k+1. De toute position gagnante (donc 4k, 4k+2 et 4k+3, k > 0), il suffit de retirer 3, 1 ou 2 allumettes selon les cas pour se ramener à un position perdante.

Une idée de généralisation:

 Cliquez pour afficher

On regarde un écart entre les pions  sur deux en partant de la gauche.
Pour avoir une position perdante il faut que le ou exclusif de ces écarts soit 0.

Bouger n'importe quel pions modifie ce ou exclusif et donc à partir d'une position perdante on ne peut aller que vers une position gagnante.

Si ce ou exclusif est plus grand que 0 alors il existe au moins un écart qu'on peut réduire pour pour le remettre à 0. Donc de n'importe quelle position gagnante on peut aller vers une position perdante.

Je pense que c'est bon

LittleFox

 Cliquez pour afficher

oui c'est l'idée... ce "ou exclusif en base 2 s'appelle aussi"nim-addition" introduite par Grundy, ou encore "addition sans retenue" en base 2.

Trop pointu pour moi, ça part dans la théorie avec les nombres binaires et les graphes, je laisse la main.

Rassure toi, il n'y a pas besoin de notion en théorie des graphes ou d'utilisation de nombres binaires pour résoudre ce problème particulier.
La théorie des graphes permet de modéliser les jeux à stratégie gagnante dans un cadre assez général, et l'utilisation des nombres binaires sert ici juste à montrer de manière élégante que le jeu est fini, mais on peut le montrer de manière beaucoup plus simple. (Le nombre de placements de pions sur la ligne, sans aucun au dela du dernier pion, est fini). C'est assez intuitif que chaque mouvement va un peu plus tasser les pions au bord, et qu'à un moment, on se retrouvera bloqué.

Si tu prends le jeu des allumettes, il n'y a pas besoin de théorie des graphes pour trouver la stratégie gagnante, qui est très simple. Il suffit juste de démontrer que le joueur jouant sur une position gagnante pourra sans problème bloquer l'autre joueur dans une position perdante. Pour trouver cette stratégie, il faut commencer par analyser les parties quand il y a peu d'allumettes et trouver la stratégie en déroulant les scénarios possibles. On voit alors facilement apparaitre un pattern, que l'on peut généraliser. Dans ce cas, c'est la même idée, commence à prendre des exemples petits pour voir comment cela se passe et généralise. (avec seulement 1 ou 2 pions, les stratégies gagnantes sont très très facile à trouver, commence par ça, ça te donnera l'intuition pour la suite)

m'ouais !
n'empêche que dans ce jeu à n pions, si tu ne connais pas l'addition exclusive binaire, t'es mal pour trouver le coup à jouer !
et ce qui est intéressant c'est ma démonstration ...

salut

un jeu très intéressant ... auquel je n'ai pas malheureusement pas le temps de m'impliquer ... pour cause de continuité pédagogique ...

pour compléter la réponse de weierstrass avec l'exemple de matheuxmatou :

le strict respect des règles montre que de droite à gauche :

le premier pion en position n ne peut se déplacer que de n - 1 positions : n - (n - 1) = 1
le deuxième pion en position m (m > n) ne peut se déplacer que de m - 2 positions : m - (m - 2) = 2
et ainsi de suite(en notant 1 la position la plus à droite)

donc il est évident que le nombre de déplacement est majoré par la somme des positions initiales des pions ... et donc que le jeu possède un nombre d'états fini ...

et qu'il y a donc toujours un gagnant !!!

PS : c'est du niveau primaire ...

par contre trouver une stratégie gagnante est d'un autre niveau ... mais uniquement de réflexion et ne nécessite pas du tout de connaissances ...

carpediem
effectivement avec 3 ou 4 pions, pas besoin de connaissances ...

par contre pour le cas général c'est plus velu

oui mais ces connaissances ne servent qu'à traduire élégamment (comme dit plus haut) l'algorithme du vainqueur (parce qu'en fait ce n'est qu'une question d'algorithme comme la plupart de ces types de jeu) comme par exemple la réponse de LittleFox et l'utilisation de sa fonction logique XOR ...

parce que on peut très bien proposer une solution naïve mais fastidieuse à rédiger ... il me semble ... comme le propose justement weierstrass en considérant de multiples si ... alors ...

pour le cas général ça me parait difficile de traduire uniquement avec des tests !

il me semble que si car les nombres de positions initiales (*) et d'états sont finis et que les cas de 3, 4 ou ... 10 pions permettront de généraliser même si ensuite il y a plus de pions car les situations des cas particuliers vont se retrouver dans les cas où n est plus grand ...

mais ça sera pénible à rédiger effectivement ...

(*) si m est la position du pion le plus éloigné et quel que soit le nombre de pions il n'y a qu'un nombre fini de positions initiales et les positions relatives de ces pions se retrouveront dans les situations à 3, 4, ... ou 10 pions qui suffiront pour généraliser ...

c'est un peu le même principe avec le théorème des quatre couleurs : on a montré qu'au-delà de ... 10^6 pays d'une carte on se ramenait à moins de 10^6 pays puis on a montré que dans ce cas là on savait faire ...

certes, mais la beauté d'une stratégie gagnante c'est de trouver un procédé qui permet sur un calcul immédiat de dire si la position est gagnante et si oui, de déterminer le coup à jouer.

Évidemment qu'il est possible de traiter tous les cas par algorithme mais ce n'est pas le sujet !

bien sûr mais au départ je n'étais intervenu que pour compléter la réponse de weierstrass ... et évidemment une solution élégante est toujours plus agréable et appréciable ...

Bon, j'ai trouvé le temps de me repencher un peu sur le problème et je me suis aperçu que mon raisonnement était complètement faux.

 Cliquez pour afficher

En groupant les pions deux par deux et en considérant les écarts, on se ramène à un jeu à stratégie gagnante ou il faut que les intervalles forment un XOR nul. Après avoir regardé la réponse de LittleFox, c'est bien ce qu'il a trouvé, bravo à lui!

@weierstrass
Ton raisonnement était juste et a été mon point de départ.
Simplement un xor nul entre deux nombres impose que ces nombres soient égaux

Ah oui, je suis bête, j'ai confondu 3 pions et 3 intervalles, donc effectivement mon raisonnement était juste, je ne m'était pas gouré...

bravo à vous