Je ne sais pas ce qui se passe si le premier joueur se contente de placer le cavalier avant que le deuxième joueur ne le déplace . Ce problème semble bien plus compliqué que celui que je propose et je ne suis pas sûr qu'il admette une solution simple , mais pourquoi pas

Vasimolo

Bien sûr chacun joue dans le but de gagner et il est clair que le choix de la case de départ ainsi que du premier coup sont de véritables atouts même si je n'ai jamais dit qu'ils étaient déterminants

Vasimolo

En fait je n'ai pas de stratégie gagnante pour l'un ou pour l'autre , je sais simplement lequel va gagner s'ils jouent au mieux .

Vasimolo

Bonjours,
J'ai déja rencontré ce genre de problème.
En raisonnant par l'absurde et en considérant une partie gagné à tout les coup par le deuxième joueur, le premier joueur doit essayer de lui "piquer" sa partie optimale

Imaginons donc une partie optimale gagné par le deuxième joueur, notons 1,2,3... les positions successives du cavalier.

Déja pour simplifier faisons comme si le premier joueur pouvait choisir en plus son mode de déplacement lors du premiers coup (quitte à pivoter l'échiquier de 90° et les déplacements semblent intervertis).

L'idée est que le premier joueur place le cavalier à la position 2 de la partie optimale, et qu'il déroule la partie comme l'adversaire l'aurait fait, jusqu'à ce qu'il perde.

Mais aïe! la position 1 laissée vacante pourrait être exploiter par le deuxième joueur pour retourner la situation à son aventage. C'est embarrassant...

Sauf si la partie optimale commence dans un coin! Il n'y a que deux point d'accès pour se rendre dans un coin. L'un d'eux est la position 2, l'autre point d'entré implique un déplacement que seul le premier joueur peut effectuer. Si il en a occasion, le premier joueur peut même accélérer sa victoire en retourant danc le coin.


Conclusion : soit le premier joueur a une stratégie optimale partant d'un coin, soit il a une stratégie optimale partant d'un "point d'accès" à un coin.

Mathieu

L'idée est assez simple. Supposons que les coups 1,2,3 de ton exemple donnent une position perdante A à rouge. Alors je dis que si on "retire" le coup 1 (c'est-à-dire qu'on autorise à nouveau la case 1), puisque la case est noire, ceci ne peut qu'être favorable au joueur bleu et donc a fortiori cette position A' va être perdante pour le joueur rouge à qui c'est le tour de jouer. Ensuite vient le coup du quart de tour et du décalage de coups qui fait que le premier joueur peut refiler cette position perdante A' à l'autre joueur.

Supposons que les coups 1,2,3 de ton exemple donnent une position perdante A à rouge. Quoi que fasse rouge, bleu va trouver une suite de coups qui le mèneront à la victoire. Imaginons, qu'après le coup 3, on donne en plus la possibilité au joueur bleu de jouer une fois sur la case 1. Ceci ne peut lui nuire. Pour t'en convaincre, tu n'as qu'à te dire qu'il ignore cet avantage et qu'il s'interdit d'y jouer. Il est clair que cette situation A' est encore perdante pour rouge. Quoi qu'il fasse, bleu va trouver une suite de coups qui le mèneront à la victoire : disons qu'il fait les mêmes coups que ceux qu'il ferait à la suite de la position A. Cette position A' où la case 1 a été libérée est donc encore perdante pour le joueur rouge.

Maintenant en tournant l'échiquier et en considérant que c'est le premier joueur qui a joué les coups 2 et 3 de la position A, le deuxième joueur se retrouve exactement dans la position A'. Mais les rôles sont inversés. C'est à lui de jouer et il est dans une situation perdante.

Pour résumer :

Le premier joueur va gagner à chaque fois . En effet il n'y a pas de partie nulle et comme le jeu est parfaitement symétrique , si le deuxième joueur avait une stratégie gagnante le premier n'aurait qu'à la copier .

Que peut-on dire si le premier  joueur choisit uniquement la case de départ avant de laisser jouer le deuxième ?

Vasimolo

C'est un peu frustrant mais on ne dit rien sur la stratégie gagnante , on sait simplement qu'elle existe ce qui est déjà beaucoup

Vasimolo

Sûrement frustrant , mais si tu relis bien le problème tu verras qu'on ne demande pas de décrire une stratégie gagnante mais simplement de savoir si elle existe

Tu peux essayer d'expliciter une stratégie gagnante et une autre pour le deuxième problème mais je crains que ce soit un peu difficile

Vasimolo

Bon, après réflexion, je ne vois pas trop pourquoi on ferait une différence entre le 1er scénario (A pose et joue) et le second scénario (A pose seulement).
La démo de titoufred s'applique aussi dans ce cas, il me semble.

Sauf si avec tes trucs de graphe, il est possible de poser le pion sur une case "perdante"

Autrement dit si la stratégie gagnante dépend de la case de départ , on se fiche de l'option, sinon, tu as raison.

Exact, ça reste incertain. Le graphe d'une case et celui de sa suivante peuvent être différents, en plus (à cause de l'occupation ou de la libération de la 1ère case).