Echec non borné

[Médiat]

Bonjour,

Je vous propose aujourd'hui un petit jeu aux règles très simples :

Le plateau de jeu est un échiquier 1/4-infini, c'est à dire que cet échiquier s'étend infiniment vers la droite et vers le haut (pour fixer les idées), mais qui posséde une case en bas à gauche que nous identifierons par ses coordonnées (0, 0).


Déroulement du jeu :

1. l'un des joueurs choisit une case différente de (0, 0) et y dépose une Reine (à cause de sa façon de se déplacer)
2. alternativement, chaque joueur prend la reine et la déplace au choix :
   1. horizontalement, d'autant de cases qu'il veut, mais exclusivement vers la gauche
   2. verticalement, d'autant de cases qu'il veut, mais exclusivement vers le bas
   3. diagonalement, d'autant de cases qu'il veut, mais exclusivement vers le bas à gauche
3. la partie s'arrête quand un joueur pose la Reine sur la case (0, 0) et alors il a gagné.

Je vous propose de commencer une partie en choisissant une case, sous la forme d'un couple (n0, m0), avec n et m entiers positifs et inférieurs à 10000 (et je conseille même inférieurs à 1000 pour que la partie ne dure pas trop longtemps), je répondrais par un couple (n1, m1) correspondant à un coup valide, etc.


Le but n'est, évidemment pas de savoir qui va gagner, mais de découvrir la stratégie gagnante ...


PS : le coup (n0, m0) --> (n1, m1) est valide si :

n1 = n0 et m1 < m0
ou
m1 = m0 et n1 < n0
ou
m1-n1 = m0-n0 et n1 < n0

-----

[vgondr98]

Je commence avec (n947,m749).

[Médiat]

Bonjour,

Merci de tenter le coup et désolé de n'avoir pas répondu plus tôt (pas connecté)

Je reprends la totalité de la partie
(947, 749) Vous
(518, 320) Moi (J'ai soustrais 429 à chaque coordonnée (déplacement diagonal))

[PlaneteF]

Bonsoir,

Juste une petite remarque de terminologie du jeu d'échecs en Français, où l'on parle de la "dame" plutôt que de la "reine" ; D'ailleurs dans la notation dite "algébrique" on la note "D". Par contre en Anglais on emploie le mot "queen" avec comme notation "Q".

Cordialement

[A voir en vidéo sur Futura]

[interferences]

Bonsoir,

C'est bien beau de déplacer la dame mais il ne me semble pas qu'il y ait de stratégie gagnante...

Au revoir

PS : Ah j'ai ptet loupé le PS. ^^

[interferences]

Re,

 Cliquez pour afficher

Si j'explicite le PS

n1 = n0 et m1 < m0

= On a le droit de descendre verticalement.

m1 = m0 et n1 < n0

= On a le droit d'aller vers la gauche horizontalement.

n1 = n0 et m1 < m0
ou
m1 = m0 et n1 < n0

= On a le droit de descendre à gauche en diagonale.

m1-n1 = m0-n0 et n1 < n0

= On a le droit de descendre à droite en diagonale.

C'est un jeu d'allumette 2D

[interferences]

PS : Mais si un joueur se borne à faire des coups horizontaux, il est sûr de ne pas perdre non ?

Dame (518, 320)-->(316, 320).

[Médiat]

Dame (518, 320)-->(316, 320)

Mon coup : (6, 10) (diagonal)

[interferences]

Dame (518, 320)-->(316, 320)

Mon coup : (6, 10) (diagonal)

Dame (6, 2) vertical

PS : Sinon, j'ai dis des bêtises la dernière fois.

[Médiat]

Bonjour,
(6, 2) --> (1, 2) (horizontal)

[interferences]

Re,

Bien joué tu as gagné...j'ai mal calculé.
Je croyais pouvoir faire dame (2,1) ^^'.
Il aurait fallut que j'aille en (6,1), si tu avais été en (2,1) j'aurais été en (1,2).

[Médiat]

Bonjour,

Je me répète, mais le jeu ici ne consiste pas à gagner ou perdre, mais à réfléchir à une stratégie gagnante

Sinon, si j'avais joué en (2, 1), vous n'auriez pas pu jouer en (1, 2), ce n'est ni un mouvement horizontal, ni vertical ni diagonal (vers le bas gauche)

[minushabens]

 Cliquez pour afficher

je dirais que celui qui commence doit mettre la dame sur l'une des diagonales juste au-dessous ou juste au-dessus de la diagonale principale (i.e. les cases (n,n-1) ou les cases (n,n+1)). L'autre joueur ne peut gagner en un coup et quoi qu'il fasse on peut toujours ramener la dame sur l'une de ces diagonales (en fait toujours sur la même si l'on veut). On finit par arriver à l'une des cases (2,1) ou (1,2) qui sont gagnantes.

[Médiat]

Bonjour minushabens,

 Cliquez pour afficher

Si vous jouez en (n, n+1), je joue en (1, 2) et si vous jouez en (n, n-1), je joue en (2, 1), dans les deux cas vous perdez

[Tryss]

C'est une variante du jeu de nim non?

[Médiat]

Bonjour,

Oui, effectivement.

[lper]

Bonjour Médiat,

depuis le temps !

Je me creuse la tête en essayant de trouver une suite dans les combinaisons gagnantes, est-ce que néanmoins ma grille est juste, au moins j'aurais tenté de faire avancer le schmilblick.

 Cliquez pour afficher

echec.PNG

[Médiat]

Bonjour lper

depuis le temps !

Effectivement d'ailleurs en Juin 2012 j'avais écrit :

Bonjour lper (ravi de te revoir ici, tu devrais venir plus souvent).

Je persiste et signe

Je me creuse la tête en essayant de trouver une suite dans les combinaisons gagnantes, est-ce que néanmoins ma grille est juste, au moins j'aurais tenté de faire avancer le schmilblick.

Oui elle est bonne, il ne reste plus qu'à trouver la fonction (au sens informatique du terme) qui à partir d'une position donne le bon coup à jouer, s'il existe.
[

[Amanuensis]

Oui elle est bonne

Merci de valider le fichier, pour élargir la liste de ceux qui peuvent le voir.

[vgondr98]

Pour moi la stratégie gagnante consiste à mettre la dame directement en position (y2,x1).
Ainsi Médiat ne pourra jouer que (y2,x0), (y1,x0), (y1,x1) ou (y0,x1).
Je trouve également qu'il est plus clair de remplacer les lettres n et m par y et x qui sont beaucoup utilisé dans les graphiques.
Il faudrait je pense que la position de départ soit donnée aléatoirement en évitant les cas où y ou x=0 et où y=x.

[Médiat]

Pour moi la stratégie gagnante consiste à mettre la dame directement en position (y2,x1).

C'est effectivement une position gagnante, mais que jouez-vous si je commence et que je place la dame en position (10001, 16181) ?


Je précise qu'avec la position ci-dessus, vous pouvez gagner.

[lper]

Je persiste et signe

Merci c'est gentil !
Je suis souvent à te lire en tout cas.

 Cliquez pour afficher

Faut-il utiliser Fibonacci pour reproduire la suite :
0,3,8,11,16,21,24,29,32,37,42, ....
ces valeurs correspondent à la position centrale entre les deux valeurs gagnantes.

[Médiat]

 Cliquez pour afficher

Oui, il y a un rapport avec la suite de Fibonacci

[_Goel_]

Bonjour,
Pour moi, la réponse est simple :

 Cliquez pour afficher

en jouant au mieux, tout joueur jouant sur les cases (n, 2n-1) ou (2n-1, n) a gagné, quoi que joue son adversaire.
Démonstration :
Partir de la fin : pion en (1,1) => cela élimine la grande diagonale la colone 1 et la ligne 1.
Donc on veut que l'adversaire joue FORCEMENT en colone1/ligne1/diagonale
Donc il faut forcément poser sa dame en (2,3) (ou son symétrique par rapport à la Grande Diagonale)
donc ces 2 positions supplémentaires éliminent de la même manière leurs lignes, colones et diagonales respectives
et ainsi de suite

En ce qui concerne la méthode pour gagner, si la dame est bien placée en (a,b) avec b > a (et en éliminant le cas trivial b=a !)

 Cliquez pour afficher

on a plusieurs cas :
- b>2a-1 => descendre de colonne jusqu'à ce que b = 2a-1
- a<b<2a-1 => 2 cas
...● sinon, si a impair : descendre jusqu'à ce que b = (a+1)/2
...● sinon, si b impair : aller à gauche jusqu'à ce que a = (b+1)/2
......● sinon, (a et b pair) : aller en diagonale de n cases avec n=2a-b-1

[Médiat]

Bonjour,

Pour moi, la réponse est simple :

 Cliquez pour afficher

en jouant au mieux, tout joueur jouant sur les cases (n, 2n-1) ou (2n-1, n) a gagné, quoi que joue son adversaire.

Donc vous pourriez jouer en (2, 3), auquel cas je jouerais en (2, 1) et vous avez perdu.

[lper]

C'est effectivement une position gagnante, mais que jouez-vous si je commence et que je place la dame en position (10001, 16181) ?

 Cliquez pour afficher

Moi perso je jouerai bien en (9999,16179).

[lper]

Bon j'avoue avoir un peu triché en retrouvant la formule(somme de deux formules) selon mes valeurs, je la mets en toute humilité en espérant avoir une démonstration.

 Cliquez pour afficher

nombre d'or phi (φ ) (d'où le rapport avec Fibonacci)

Merci en tout cas Médiat pour ce jeu, je vais pouvoir m'en mettre plein les poches avec les copains.

[Médiat]

 Cliquez pour afficher

Moi perso je jouerai bien en (9999,16179).

Bonjour,

 Cliquez pour afficher

Début d'explication, applicable à d'autres jeux :

Je pose l'ensemble des positions jouables à partir de la position
Je rappelle que la fonction est définie par :
= le plus petit entier qui n'appartient pas à

Soit la fonction définie par

On peut vérifier facilement que :



Par construction on peut facilement montrer que :



Ces deux dernières relations permettent de construire une stratégie gagnante (pour le joueur qui commence).

[Médiat]

 Cliquez pour afficher

nombre d'or phi (φ ) (d'où le rapport avec Fibonacci)

 Cliquez pour afficher

Effectivement, la position est gagnante (ainsi que la position symétrique).
Il existe des démonstrations sur le net (recherche sur Wythoff game), si j'ai le temps (pas aujourd'hui en état de cause) j'en posterais un sketch.

[lper]

Bonjour,

merci encore Médiat de nous faire découvrir ces merveilles mathématiques, en l'occurrence cette forme de pouvoir qu'a ce nombre d'or ! Et dire que certains se posent encore la question sur l'utilité des maths...