Faut-il appliquer la théorie des jeux combinatoire pour le jeu du chou-fleur ?
Il y a des questions qui empêchent de dormir (qui suis-je ? où vais-je ? est-ce la fin de la crise ? va-t-elle me rappeller ?), et il y a des questions qui empêchent vraiment de dormir. La question que je pose aujourd'hui fait partie de cette deuxième catégorie, puisque c'est pendant une insomnie qu'elle m'est apparue : peut-on appliquer la théorie des jeux combinatoires pour le jeu du chou-fleur ? Mon état de semi-sommeil m'a alors apporté une réponse inattendue : "oui, et ça ferait un bon article WTF sur le blog, en en attendant un vrai !".
Bref : quelle stratégie adopter pour gagner au jeu du chou-fleur ?
Je n'ai pas trouvé d'illustration du jeu du chou-fleur, alors à la place, j'ai mis une jolie photo d'un chou romanesco.
Le jeu du chou-fleur
Pour ceux qui n'ont jamais mis les pieds dans une cour de récréation, il faut savoir que le jeu du chou-fleur est un jeu où deux joueurs avancent tour à tour de la distance exacte d’un pied, le premier en disant "chou" et le suivant "fleur", et ainsi de suite. Le premier à écraser le pied de l’autre a gagné.
Dans ce jeu, seule la distance initiale entre les pieds des deux joueurs déterminera le gagnant du duel. Pour espérer gagner, c'est la distance de départ qu'il faudra négocier au mieux.
Notons d la distance de départ, lC la longueur des chaussures de Chou (le premier joueur à faire un pas), et lF celle de Fleur.
- Si d ∈ [0 ; lC[, Chou gagnera en un pas.
- Si d ∈ [lC ; lC + lF[, Fleur gagnera lors de son premier pas.
- Si d ∈ [lC + lF ; 2 lC + lF[, Chou gagnera lors de son deuxième pas.
Et ainsi de suite :
- Si d ∈ [k(lC + lF) ; k(lC + lF) + lC [, Chou gagnera lors de son (k+1)-ième pas
- Si d ∈ [k(lC + lF) + lC ; (k+1)(lC + lF) [, Fleur gagnera lors de son (k+1)-ième pas
Moralité : pour que Chou gagne, il faut que la distance soit dans un intervalle de type [k(lC+lF) ; k(lC+lF) + lC [. Un tel intervalle est de longueur lC. Autrement dit, si la distance est choisie au hasard, celui qui chausse du 42 aura l'avantage sur celui qui chausse du 35.
Ah, ça valait le coup de se creuser la tête pour avoir cette réponse...
Le jeu du chou-pomme
Le jeu du chou-fleur est très bien en l'état, mais souffre d'un gros défaut, à l'image d'une bataille ou d'un Mario Kart Wii : il n'y a pas de stratégie pour gagner, c'est que de la chance.
C'est pourquoi il a fallu inventer une variante : le jeu du chou-pomme. Deux règles s'ajoutent :
- Les grand "chou" (et les grand "pomme") sont autorisées : la longueur d'un pas peut être aussi grande que possible. Il y a donc deux type de pas, les "chou" et les grand "chou" (et leur équivalent pour Pomme).
- Interdiction de gagner avec un grand "chou" (ou un grand "pomme") : on ne peut écraser le pied adverse qu'avec un pas de distance minimale.
Là, le jeu devient intéressant, puisqu'il entre dans la catégorie des jeux impartiaux, comme le jeu des bâtonnets de Fort Boyard, le jeu de Nim, le Sprouts, le Chomp ou le quart de singe (on admettra que les joueurs ont des chaussures et des jambes de tailles équivalentes).
Ce qui est intéressant avec un jeu impartial, c'est qu'il existe toujours une stratégie de victoire pour l'un des deux joueurs. Pour trouver cette stratégie, il faut trouver quelles sont les situations gagnantes et les situations perdantes.
Prenons par exemple le jeu des bâtonnets de Fort Boyard. Vingt bâtonnets sont présentés, chaque joueur prend à son tour 1, 2 ou 3 bâtonnets. Le joueur qui prend le dernier bâtonnet perd.
- Si, à mon tour de jeu, il reste 2, 3 ou 4 bâtonnets, j'ai gagné : il me suffit de ne laisser qu'un bâtonnet.
- Si, à mon tour de jeu, il reste 6, 7 ou 8 bâtonnet, j'ai gagné : il me suffit de ne laisser que 5 bâtonnets. Puisque mon adversaire devra en laisser 2, 3 ou 4, cela revient à la situation précédente.
- Et ainsi de suite : je gagne si il reste 10, 11, 12 ou 14, 15, 16 ou 18, 19, 20 bâtonnets... Puisqu'il y a 20 bâtonnets au début, je suis sûr de gagner... si je commence à jouer ! Pour ce jeu, les situations gagnantes sont celles où il reste 4n+2, 4n+3 ou 4n+4 bâtonnets.
Dans le cas du chou-pomme, on peut chercher les situations gagnantes de la même façon. Notons l la longueur d'un pas (on supposera que l = lC = lF/P), et L la longueur maximale d'un grand pas (que l'on supposera strictement inférieure à 2J, J désignant la longueur d'une jambe (Cette remarque n'a aucune incidence sur la suite)). Chou fera le premier pas.
- Si d ∈ IFinal = [0 ; l[, Chou gagnera lors de son premier pas.
- Si d ∈ IP0 = [l ; 2l[, Pomme gagnera lors de son premier pas, puisque Chou ne peut pas gagner sur un grand "chou".
- Si d ∈ IG0 = [2l ; 2l + L[, Chou gagnera : il lui suffit de faire un grand "chou" de façon à ce que la distance restante soit dans l'intervalle IP0.
- Si d ∈ IP1 = [2l + L ; 2l + L + l[, Pomme dispose d'une stratégie gagnante. Quelle que soit la longueur du pas de Chou, la distance restera sera dans IG0, qui est une situation gagnante pour celui qui s'y trouve.
Il y a donc les situations gagnantes, de la forme IGk = [k(L+l) + 2l ; k(L+l) + 2l + L[. Le joueur qui s'y trouve peut toujours ramener son adversaire dans une situation perdante de la forme IPk = [k(L+l)+l ; k(L+l) + 2l[.
A nouveau, si la distance initiale est choisie au hasard, elle laisse un très net avantage à Chou !
Cas où L = 6l. Le bleu représente les position dans lequel il existe une stratégie gagnante, qui consiste à faire un pas pour revenir dans le rouge.
Ici, la distance initiale est d'environ 20 pas : Chou dispose d'une stratégie gagnate !
Il reste à envisager le cas où les deux joueurs n'ont pas des chaussures ni des jambes de la même longueur, mais je crois que j'ai encore du sommeil en retard...
Images :
Romanesco broccoli detail
.jpg){kind=link}