Un petit jeu de plateau

[Médiat]

Bonjour,

Je vous propose le jeu suivant :

Le "plateau de jeu" est constitué d'une liste finie de couples de nombres entiers naturels, par exemple : (14, 2) ; (23, 0) ; (2, 3)
Un "coup" consiste à choisir l'un de ces couples et à le remplacer par 3 couples en respectant la règle suivante :
(n, m) --> (n', m) ; (n, m') ; (n'', m'') où n' et n'' sont strictement plus petits que n, et m' et m'' sont strictement plus petits que m.
Comme il n'est pas possible de jouer à partir d'un couple dont l'une (au moins) des composantes est égal à 0, on supprime ces couples du plateau de jeu.
Le perdant est le joueur qui ne peut pas jouer (il n'y a plus de couples sur le plateau, après nettoyage).

Par exemple, en partant de l'exemple ci-dessus, que l'on remplace par (14, 2) ; (2, 3) (ce qui ne correspond pas à un coup d'un joueur, mais à un nettoyage du plateau de jeu.

En choisissant le couple (14, 2), on peut le remplacer par (10, 2) ; (14, 1) ; (10, 0)
Le plateau de jeu laissé à l'adversaire devient donc (nettoyage compris) : (10, 2) ; (14, 1) ; (2, 3)

Pour être plus précis je vous propose de démarrer par le jeu :

(10, 8) ; (3, 4) ; (5, 7)

A vous ...

PS, plusieurs joueurs peuvent jouer indépendamment les uns des autres
-----

[obi76]

Salut,

si j'ai bien compris, si on prend (10, 8) ; (3, 4) ; (5, 7), on peut en éliminer un d'office (par exemple en prenant (10,8) => (0,8), (10,0), (0,0)) ?

[Médiat]

Salut,

Oui, ce coup est valide, ce qui montre qu'un jeu avec un seul couple est gagnant, puisque le joueur qui doit jouer peut rendre un plateau vide et donc gagner.

[obi76]

Re,

mais à l'inverse, je pense commencer à voir la stratégie à adopter, il suffit de faire apparaître le maximum de 1, et après ça ne revient qu'à la parité du nombre de couples de nombre qu'il y a dès le départ (dès que quelqu'un y touche, il ne peut que disparaître). Me trompé-je ?

[A voir en vidéo sur Futura]

[Médiat]

Bonjour,

Si le plateau ne contient que des couples (1, 1), alors, je confirme que le gain ne dépend que de la parité du nombre de couples. Mais il y a beaucoup de partie qui ne passeront pas par une situation où il n'y a que des couples (1, 1).

Pour voir plus de situations intéressantes, je te propose de jouer ...

[obi76]

Pour voir plus de situations intéressantes, je te propose de jouer ...

C'est parti :

(10,8) (3,4) (5,7) => (2,8) (10,7) (7,1) (3,4) (5,7)

[Médiat]

Je vais noter de la façon suivante :

Ton coup : (10,8) (3,4) (5,7) => (2,8) (10,7) (7,1) (3,4) (5,7)
Mon coup : (2,8) (10,7) (7,1) (3,4) (5,7) ==> (2,8) (10,7) (7,1) (3,4) (2, 3)

[obi76]

(2,8) (10,7) (7,1) (3,4) (2, 3) ==> (2,8) (10,7) (3,4) (2, 3)

[Médiat]

(2,8) (10,7) (3,4) (2, 3) ==> (2,8) (2, 3) (3,4) (2, 3)

Voilà qui devrait donner une indication ...

[obi76]

Voilà qui devrait donner une indication ...

Je commence à voir mais je n'ai pas encore tout le truc en tête

(2,8) (2, 3) (3,4) (2, 3) ==> (2,8) (2, 3) (2,2) (2, 3)

[Médiat]

(2,8) (2, 3) (2,2) (2, 3) ==> (2,2) (2, 3) (2,2) (2, 3)

[obi76]

(2,2) (2, 3) (2,2) (2, 3) ==> (2,2) (2, 3) (2, 3) (on s'approche ^^)

[Médiat]

(2,2) (2, 3) (2, 3) ==> (2, 3) (2, 3) ( plus en plus proche )

[obi76]

Je vois un piège ^^
(2, 3) (2, 3) ==> (2, 2) (2, 3)

[Médiat]

(2, 2) (2, 3) ==> (2, 2) (2, 2)

[obi76]

(2, 2) (2, 2) ==> (1, 2) (2, 1) (2, 2)

[Médiat]

(1, 2) (2, 1) (2, 2) ==> (1, 2) (2, 1)

[obi76]

(1, 2) (2, 1) ==> (1,1) (1,1)(2,1)

PS : j'hallucine, même à ce stade il y a encore 31 solutions distinctes o_O
PS2 : j'ai perdu...

[Médiat]

PS2 : j'ai perdu...

Oui .

Si tu veux, je te propose de faire une autre partie, tu choisis la position de départ et qui commence (que des nombres en dessous de 15, sinon la partie peut durer longtemps), et pas une position ne présentant que des paires de couples identiques (sauf si tu commences ), puisque c'est une position clairement perdante, quoi que fasse le joueur qui reçoit cette position, l'autre joueur peut jouer en faisant systématiquement la même chose, jusqu'à ce que le premier ne puisse plus jouer.

[obi76]

Là, il y a une subtilité qui m'échappe, s'il y a des couples identiques je ne vois pas très bien en quoi ça implique nécessairement de perdre...

[Médiat]

Si je te fournis le plateau de jeu [(n, m) ; (n, m)], quoi que tu joues, cela reviendra à remplacer l'un des couples (n, m) par d'autre(s) couple(s), il me suffira de remplacer l'autre couple (n, m) par la même chose que toi, et tu seras à nouveau devant un plateau ne comportant que des paires de couples, et on recommence jusqu'à qu'il n'y en ai plus (et tu perds ).

[obi76]

D'accord ^^

je t'avoue que juste pour voir la portée du jeu, j'ai fais un petit programme rapide, juste pour compter le nombre de solutions, c'est assez impressionnant (d'un autre côté c'est assez logique)... Si on veut le faire évoluer pour essayer de faire une IA qui joue à ça, ça veut dire qu'en plus de regarder la parité du nombre d'itérations nécessaires pour arriver à un plateau nul, on peut supprimer les couples identiques. Tu confirmes ?

Cela dit je ne sais pas si je vais passer beaucoup plus de temps sur un programme comme ça ^^

Juste pour savoir, tu as d'autres types de stratégies en tête ?

[Médiat]

Oui, je confirme que l'on peut supprimer les couples identiques.

Ce qui est intéressant dans ce jeu c'est qu'il cache et illustre parfaitement une théorie mathématique ; connaissant la stratégie (rien de glorieux donc), je suis imbattable quelque soit la position initiale, si je peux choisir qui commence. Pour cette stratégie, nul besoin d'ordinateur (même si cela rend les choses plus faciles, mais pas d'exploration systématique d'un arbre des coups), il suffit de connaître la théorie mathématique qui se cache la-dessous, et dont je parlerai ici, succinctement quand l'ensemble des joueurs (c'est à à dire toi ) me le demandera, mais, bien sur cela brise la magie. Je posterai aussi un développement plus complet de cette théorie dans le forum Mathématiques du Supérieur (même si cela reste lisible par des lycéens un peu motivés).

[obi76]

Justement, je savais bien que tu avais en tête une méthode complète pour gagner, c'est pourquoi j'avais voulu te contrer avec un programme, mais je dois admettre que pour le coup, tu as bien choisi les règles (rapidement insimulable)

[Médiat]

Je dois admettre que je ne suis pas l'auteur des règles, j'ai juste adapté un jeu proposé par un grand mathématicien pour pouvoir jouer au travers d'ordinateurs (et sans avoir besoin d'une infinité de pièces, ce qui rend le jeu original difficilement commercialisable ).

PS : on aurait pu jouer avec des couples comprenant des ordinaux infinis , mais cela risque d'être long , mais néanmoins fini.

PPS : tu me préviens quand tu veux que je lève le voile.

[obi76]

Lève, lève

[Médiat]

Bonjour,
La théorie qui se cache sous ce jeu est tout simplement la théorie des jeux (étonnant, non ?) combinatoires impartiaux.
C'est à dire des jeux :
à deux joueurs
à information complète
sans intervention du hasard
tel que face à une situation donnée les deux joueurs aient les mêmes possibilités de jeu

Suivant cette définition le jeu d'échec n'est pas impartial (point 4).
Dans le cadre de cette théorie, on trouve deux théorèmes importants :
Le théorème de Zermelo : Dans un jeu combinatoire, soit l'un des joueurs a une stratégie gagnante, soit chacun des joueurs a une stratégie garantissant au moins le nul.
et
Le théorème de Sprague-Grundy : Tout jeu impartial est isomorphe à un jeu de Nim.
Un jeu de Nim est un jeu très simple : on dispose de plusieurs rangées d'allumettes (chaque rangée peut avoir autant d'allumettes que l'on veut),
Un coup dans ce jeu consiste à choisir une rangée et à retirer au moins une allumette (éventuellement toutes)
Le perdant est le joueur qui ne peut pas jouer.
Ce jeu a été rendu célèbre par le film d'Alain Resnais "L'année dernière à Marienbad", où les joueurs jouaient à partir de la situation (qui est perdante) :

   |
  |||
 |||||
|||||||

On peut associer à une rangée de n allumettes le nombre n. S'il y a plusieurs rangées, il faut faire la "somme de Nim" des valeurs de ces rangées, pour avoir la valeur du jeu.
Dans le jeu que j'ai proposé (et qui est une variante du jeu "Diminishing Rectangles" de Conway (encore lui)), pour évaluer une situation, il faut faire la "somme de Nim" des valeurs de chaque couples, et pour calculer la valeur d'un couple, il faut faire le "produit de Nim" des deux valeurs du couple.
Une situation dont la valeur est 0 est perdante, or à partir d'une situation de valeur 0, quelque soit le coup joué, la nouvelle valeur est différente de 0, et à partir d'une situation de valeur différente de 0, il est possible de rendre une situation de valeur 0.
Ce jeu est construit sur mesure pour correspondre au "produit de Nim".
Il suffit donc d'avoir les tables des deux opérations pour jouer une stratégie gagnante.
De plus ample détails sont disponibles dans le document Ensembles de Nombre dans les contributions des forumeurs : http://forums.futura-sciences.com/ma...ml#post3958180
chapitre "Théorie des ensembles ZF(C)", sous-chapitre "Nimbers"

[obi76]

Sans connaître tous ces termes, je sentais qu'il y avait un truc comme ça mais je n'ai pas réussi à le formaliser... Si je ne dis pas de bêtises c'est comme le jeu de Ford Boyard où il fallait enlever entre 1 et 3 battons (sur 21) chacun son tour et qu'il ne fallait pas enlever le dernier. La résolution de ce problème est triviale, j'ai essayer (sans succès) de le transposer ici... Dommage, je n'étais pas loin

[thequark]

Il y a une différence avec le jeu où on dispose des bâtonnets sur une table. Les deux adversaires enlèvent chacun leur tour 1, 2 ou 3 bâtonnets. Celui qui enlève le dernier bâtonnet à perdu.
(Cf. Fort Boyard pour les plus cultivés !)


<-- Mince ! Médiat écrit plus vite que moi !!

[Médiat]

Bonjour,

Pour le jeu de Fort Boyard, si j'ai bien compris, on peut associer la valeur (n - 1) modulo 4, à la position avec n allumettes.

Ce jeu est très simple, mais deviendrait plus compliqué si on partait de deux (ou trois, ou m) tas, et dans ce cas, il suffirait de faire la "Somme de Nim" de chacun des tas, pour avoir la valeur globale de la situation, et donc avoir une stratégie gagnante.

PS : C'est obi76 qui répond plus vite que son ombre et pas moi .