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

Problème ouvert (?) : auto-tamponneuses

Modifié (21 Jan) 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

  • Modifié (22 Jan)
    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.
  • 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$.
  • Tu ne decris toujours pas le match nul ?!
  • Pour $b=2$ et $r=1$, si Rouge commence, il me semble que c'est Rouge qui gagne, et pourtant $b>r$.
  • @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.
  • 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.
  • 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.
  • 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.
  • 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é.
  • Modifié (22 Jan)
    @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à :



  • Oui, je me suis trompé.
  • Modifié (23 Jan)
    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
  • Alors mon code me donne ça :

  • @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:
  • Modifié (25 Jan)
    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) ?
  • Modifié (25 Jan)
    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)$.
  • Modifié (25 Jan)
    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.
  • 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à.
  • Modifié (26 Jan)
    @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.
  • @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.
  • 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é?
  • Modifié (26 Jan)
    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!