Problème ouvert (?) : auto-tamponneuses — Les-mathematiques.net The most powerful custom community solution in the world

Problème ouvert (?) : auto-tamponneuses

LucasLucas
Modifié (January 2022) dans Combinatoire et Graphes
Bonsoir
Voici un problème apparemment ouvert que j'ai découvert dans le merveilleux livre de I.Stewart : Professor Stewart’s hoard of mathematical treasures.
Le problème concerne le jeu de Dodgem (auto-tamponneuse en Français). Deux joueurs Bleu/Rouge s'affrontent sur un damier $(b+1)\times (r+1)$ comme celui-ci :

Le damier représente la configuration initiale. Bleu a $b$ voitures, Rouge en a $r$. On joue chacun son tour, Bleu peut avancer une voiture d'une case dans les directions gauche/haut/droite, Rouge dans les directions haut/droite/bas. Un joueur gagne lorsque 1) il a sorti toutes ses voitures du damier (par le haut pour Bleu, par la droite pour Rouge) OU 2) toutes ses voitures sont bloquées par l'adversaire.
La question est la suivante : pour $b>r$, est-ce que ce jeu est gagnant pour Bleu ou gagnant pour Rouge? Ce n'est pas évident car :

Avantages pour Rouge :
- Moins de cases à parcourir : $r(b+1)$ vs $b(r+1)$
- Moins de voitures, donc plus facile de réussir à se faire bloquer

Avantages pour Bleus :
- Plus de voitures, donc plus de choix à chaque étape, au moins au début.

On peut commencer par résoudre la conjecture suivante :

Conjecture : Pour tout $r$, si $b$ assez grand et que Bleu commence alors le jeu est gagnant pour Bleu.

Pour l'instant j'ai juste réussi à montrer que si $b \geq (r^3/3r)/2 +1$ il y a une stratégie qui fait que Bleu peut assurer le match nul.

Réponses

  • PetitLutinMalicieuxPetitLutinMalicieux
    Modifié (January 2022)
    Bonjour
    Et oui. Le fameux match nul, qui n'est jamais décrit dans tes règles. :)
    Peux-tu confirmer qu'on gagne quand on est bloqué ? C'est le contraire des dames.
    Soit on est bloqué et on gagne. Soit on n'est pas bloqué, et avec le moins de cases, on gagne.
  • LucasLucas
    Bonjour,

    oui on gagne si on ne peut faire aucun mouvement licite. 

    J’ai oublié de dire qu’un certain Desjardins a démontré dans les années 90 que le jeu aboutissait à nul pour $r=b=2$ et pour $r=b=3$. De mon côté avec l’aide de l’ordi j’arrive à montrer que le jeu est gagnant pour Bleu (peu importe qui commence) pour tous les cas $b>r$ quand $b\leq 4$ et $r\leq 2$.
  • ZgrbZgrb
    Tu ne decris toujours pas le match nul ?!
  • marcomarco
    Pour $b=2$ et $r=1$, si Rouge commence, il me semble que c'est Rouge qui gagne, et pourtant $b>r$.
  • LucasLucas
    @Zgrb : le match nul a lieu comme aux échecs lorsque les deux joueurs ont intérêt à répéter infiniment souvent les mêmes coups.

    @Marco : oui, j’ai dit une bêtise : dans ce cas Rouge gagne. Par ailleurs je me suis emballé, pour b=4 et r=3 mon code mouline et ne résout pas le jeu.
  • marcomarco
    Si le match est nul lorsque l'on se trouve deux fois dans la même configuration au cours de la partie, alors je trouve que le match est nul, lorsque $b=3$ et $r=2$ et que Bleu commence. Sauf erreur.
  • LucasLucas
    Hum… dès que j’ai mon code sous les yeux je regarde ce qu’il me dit précisément pour b=3 et r=2 mais ça me paraît bizarre ce nul.
  • ZgrbZgrb
    Un algo minimax avec élagage alpha-beta, en visitant en premier les noeuds qui font "avancer le jeu" (vers la droite pour r et vers le haut pour b) devrait être efficace pour ce jeu.
    Il reste à régler le cas des répétitions.
  • marcomarco
    J'ai utilisé une fonction de hachage pour mémoriser les configurations déjà jouées avant.
    @Lucas: Pour $b=3$ et $r=2$, si Bleu commence, quel premier coup jouer pour gagner ?
    Je  me suis peut-être trompé.
  • LucasLucas
    Modifié (January 2022)
    @Marco : merci de l'intérêt que tu portes à la question en tout cas! Mon code me donne les coups suivants pour démarrer :

    puis ceux-là :



  • marcomarco
    Oui, je me suis trompé.
  • marcomarco
    Modifié (January 2022)
    Et si après le premier coup des bleus (2,0)->(2,1), le coup des rouges est (0,1)->(1,1), quel est le deuxième coup des bleus ?
    C'est-à-dire que le début de partie est:
    2000
    2000
    0111
    2000
    2010
    0101

    2000
    0210
    0101
    Bleu=1
    Rouge=2
  • LucasLucas
    Alors mon code me donne ça :

  • marcomarco
    @Lucas : pardon pour le temps de réponse, j'avais fait une erreur dans mon programme. Par contre, pour $b=r=2$, je ne trouve pas que le match est nul, je trouve que c'est Bleu qui gagne, si Bleu commence. Le premier coup de Bleu étant:
  • bisambisam
    Modifié (January 2022)
    Pour faire avancer le schmilblick.
    J'ai l'impression que pour une position donnée (disons une application injective de $\{1,\dots,b+r\}$ dans $\{0,\dots,b\}\times \{0,\dots,r\}$ pour fixer les idées) il y a un moyen de savoir si c'est Rouge ou Bleu qui vient de jouer.
    Voyez-vous un invariant qui permettrait de justifier qu'une position donnée n'a pu être atteinte que si c'est Bleu qui vient de jouer (respectivement Rouge) ?
  • marcomarco
    Modifié (January 2022)
    Soit $(x_i,y_i)_{i=1, \dots, b+r}$ les coordonnées des pions, alors c'est Bleu qui vient de jouer si la parité de $\sum_{i=1}^{b+r}(x_i+y_i)$ est différente de la parité de $(1+2+\cdots+b)+(1+2+\cdots+r)$.
  • ZgrbZgrb
    Modifié (January 2022)
    J'ai peut être mal compris mais il me semble qu'il est possible d'avoir des positions identiques avec des joueurs différents qui viennent de jouer.
  • lourrranlourrran
    Effectivement, si une des auto-tamponneuses est sortie, on ne sait pas si elle est sortie après un nombre pair ou impair de mouvements. Et donc l'idée de la parité ne marche plus à partir de ce moment là.
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • LucasLucas
    Modifié (January 2022)
    @Marco : Ah zut mais c'est moi qui m'excuse je me suis également emmêlé la-dessus ! C'est pour r=b=3 et r=b=4 qu'on a des matchs nuls, désolé ! Pour r=b=2 j'ai comme toi.
    Par ailleurs si ton code nous donne ce qui se passe pour b=4,r=3 ça m'intéresse grandement !
    @bisam : Moi aussi j'avais espéré un critère simple pour savoir qui a commencé mais effectivement les voitures qui sont sorties nous font perdre de l'information.
  • marcomarco
    @Lucas : malheureusement, mon programme est trop lent pour $b=4,r=3$. Déjà, il ne calcule pas le cas $b=r=3$ en un temps convenable.
  • LucasLucas
    Ah tant pis! Sinon j'ai une question culturelle : comment tu fais pour utiliser les fonctions de hachage concrètement? C'est pour encoder efficacement les configurations j'imagine mais en quoi ça fait gagner en rapidité?
  • marcomarco
    Modifié (January 2022)
    J'avais pensé garder en mémoire les configurations dont le résultat (Bleu ou Rouge gagnant ou Nul) avait déjà été calculé. Comme cela, si le programme au cours du parcours de l'arbre, tombait plusieurs fois sur la même configuration, il n'avait pas à recalculer le résultat. Mais en fait, cela donnait un résultat erroné, à cause des parties nulles.
    Par exemple, la partie $C_1 \rightarrow C_2 \rightarrow C_3 \rightarrow C_4 \rightarrow C_3$ est une partie nulle , alors que $C_1 \rightarrow C_4 \rightarrow C_3$ n'en est pas une. Donc, on ne peut pas déterminer si $C_4$ est gagnant ou non, seulement en examinant la configuration $C_4$.
    ($C_1,C_2,C_3,C_4$ sont des configurations).
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!