Théorie des jeu: Nim et Sprague-Grundy - Passe-science #49
ฝัง
- เผยแพร่เมื่อ 11 ต.ค. 2024
- Comment un jeu aux règles particulièrement simples se trouve au cœur de toute une famille d'autres jeux et nous permet de les résoudre? Découvrez le jeu de Nim et le théorème de Sprague-Grundy!
ERRATA: 14:48 Alice prend 2 bâtons (passe le tas de 4 à 2) et non 1 (c'est interdit) le reste ne change pas (les valeurs de Nim sont les mêmes la suite de la partie aussi)
Pour en savoir plus:
en.wikipedia.o...
en.wikipedia.o...
en.wikipedia.o...
oeis.org/A002188
Retrouvez Passe-science sur Utip, Tipeee, Twitter et Facebook:
utip.io/passes...
www.tipeee.com...
/ thomascabaret84
/ passescience.youtube
Musique:
"THE RIGHT MUSIC FOR VIDEO" HighTechCorporate
Flutey Funk - Kevin Macleod
Legend of One - Kevin Macleod
Two of Us - TH-cam Audio Library
www.musicscree...
Mix Kevin Macleod (Kerbal space program)
Beaucoup issu de youtube audio library me demander si j'en oublie.
![[DRIP] ‘CLIK CLAK’ PREVIEW](http://i.ytimg.com/vi/bcxkcOSbpac/mqdefault.jpg)
Petit errata: 14:48 Alice prend 2 batons (passe le tas de 4 à 2) et non 1 (car c'est interdit) le reste ne change pas.
Le plus utile pour soutenir la chaîne, et selon ma formule consacrée: partagez les épisodes qui vous plaisent aux personnes à qui ils peuvent plaire!
erratum pas errata, errata c le pluriel d'erratum
simple question... as-tu supprimé ou déréférencé la video sur l'incertitude quantique?
@@jackjack4504 Non, tout est la en theorie, cetait laquelle ? je parlais de quoi? d'intrication ? de determinisme ? de superposition d'état? (ces 3 la sont la) autres?
@@PasseScience l'indéterminisme je crois... tu évoques une experience avec un photon, qui évalue le chemin choisi par un photon
@@jackjack4504 Il y a une expérience qui ressemble à ce que tu decris, vers 8 minutes dans l'épisode sur le spin: th-cam.com/video/kRdJMxGNf4s/w-d-xo.html
passionnant de voir des souvenir d'enfance expliqué, analysé et réfléchi.
Toujours un travail fini au petit oignon(ou toute autre préférence culinaire de votre choix).
merci :)
L'idée de la valeur de Grundi permettant de ramener le jeu à un jeu dont tous les états sont atteignables est juste géniale :)
Conway a étudié les jeux de Nim ?! Pourquoi ne suis-je pas étonné ? Il était partout 😂
Super vidéo ! À 14:48, Alice triche ! Mais elle aurait pu retirer deux bâtons rouges pour passer de 2 à 1, donc c'est pareil.
Ha bien vu, il y avait une autre erreur dans le meme genre que j'ai vue et corrigée, j'ai loupé celle la. Oui disons qu'elle passe de 4 à 2 bâtons en en prenant 2 et le reste est bon. :)
Elle passe surtout de 9 à 2 au début, retirant ainsi 7 bâton d'un coup quand la limite est de 3....
D'ailleurs la valeur de grundy initial du premier tas est une coquille, c'est censé être 1 et non 9, alice peut donc retirer 3 baton pour tomber à un tas de 6 avec une valeur de grundy de 2, j'imagine que c'était l'idée de départ, mais il devait être tard au moment du montage de cette partie ;-)
@@SylouCool Non, le premier tas est la version classique comme expliqué, on prend autant de batons qu'on veut, et non sa valeur de grundy n'est pas une coquille mais est bien égale à la taille du tas comme expliqué également.
@@PasseScience Aux temps pour moi, je devais être trop fatigué quand j'ai regardé la vidéo ^^ Surement que le bandeau avec les deux exemple précédent m'a induit en erreur (surement aussi que je n'écoutai qu'à moitié... sorry)
des petits jeux sans intérêt (pour un joueur d'échecs ;-) à des considérations mathématiques passionnantes !
Merci de cette balade.
Je n'ai pas compris ce que signifie le jeu impartial ?
Par ailleurs vous auriez dû dire dès le début que Fort Boyart avait une version avec un seul tas où celui qui joue la dernière buchette et mort ça nous aurait aidé à comprendre les règles plus rapidement.
Il faut se creuser la tête un peu dans cette vidéo.
Ça signifie que tous les joueurs ont les mêmes actions possibles.
A l'inverse par exemple des échecs ou du morpion, où les actions possibles des deux joueurs sont différentes.
@@EkairosRL merci
XOR entre chaque jeu pour avoir la valeur du jeu global ?
16:40 il faut additioner les valeurs de Grendi en binaire sans faire de retenue (comme si on à des polynôme à coefficient dans Z/2Z)
C'est-à-dire qu'on effecture un bitwise xor de toutes les valeurs, en termes d'informaticiens.
oui il 'suffit' de remonter les positions de l'exemple détaillé pour s'en convaincre. Il est d'ailleurs pertinent d'avoir fini sur la position avec des valeurs de Grundi élémentaires 1,0,1 qui se combinent en une valeur de Grundi globale nulle.
Tjrs tellement bien.. merci infiniment
Pour l'opération je pari XOR bit par bit. Pour chaque bit on aura 0 si il y avait un nombre pair de 1 et 1 si c'était impair, donc si toutes les colonnes de bits étaient pairs alors on obtient 0, soit une position perdante comme voulu.
chapeau bas, tu as fais quels études ?
@@Gryffoon Thèse en informatique.
@@Lykrast ceci explique cela
@@Gryffoon et toi tu n'as pas fait de thèse en literature pour sûr
@@abdelledba3988 xpdrrr. Certes mais Je ne suis pas thesard
Bon, il va falloir que je regarde mieux en faisant des pauses et en "travaillant" un peu pour tout comprendre.
Merci à vous.
Je comprend pas. Si on peux prendre n'importe quel nombre de bâton par tas... Il suffit de prendre tout sauf 1 ou tout prendre...
Oui, s'il n'y avait qu'un tas au depart c'est ce qu'il faudrait faire (en fonction de la version) mais ca ne serait pas tres interessant et du coup le jeu devient plus subtile lorsqu'il n'y a pas qu'un tas au depart.
9:43 Pourquoi la valeur de grundy de 5 (et des nombres suivants) n'est pas 0 ? On ne peut pas atteindre 0 en retirant 1,2 ou 3 batons et il y a aucun entier positif plus petit que ça
Edit : ah ça y'est j'ai compris en fait il faut regarder le nombre de grundy atteint et pas juste le nombre de batons
Oui c'est ça, "ce qui importe c'est les valeurs" :)
@@PasseScience ahah cette réponse m'a tué :D
1:48 : Je connais ce jeu mais avec des pieces de monnaies, il y a un peu le hasard de la taille des pièces si pas le même nombre de pieces de chaque tailles.
je l'ai su 3 fois dans ma vie, mais j'ai encore oublié... je me rappelle juste qu'il y a un rapport avec un multiple de 4. (pour la variante à la fort boyard)
Salut
Est ce que tu préfères le poulet ou le poisson ?
Merci
Difficile à dire, en pratique je mange plus souvent du poisson, mais un bon poulet roti c'est le top.
Si je ne me trompe pas 3-2=1 3-3=0 4-2=2 4-3=1...donc la suite des nombres de Grundy est 0012001200 pour la version modifiée du jeu de nim ?
Je ne suis pas certain de comprendre à quoi correspondent les soustractions. Peut être il y a une confusion entre la taille des tas et la valeur de Grundy qui y correspond. La valeur de Grundy d'une position c'est la plus petite valeur de Grundy qui ne se trouve pas dans les valeurs de Grundy des positions qu'on peut atteindre (pas dans la taille des tas des positions qu'on peut atteindre).
On peut calculer des valeurs de Grundy pour tous les jeux impartiaux meme lorsque ceux ci ne font pas intervenir de tas (par exemple mon jeu avec les carrés grisés 2x2)
@@PasseScience ok je n'ai pas compris ce qu'était la valeur de Grundy mais la valeur de Grundy ne peut pas être là plus petite des valeurs de grundy qu'on ne peut atteindre
Il y a une auto référence que je ne saisi pas
@@jeanpaullamont C'est une définition par récurrence, la valeur de Grundy des positions terminales perdantes est 0 (par définition) et pour calculer la valeur de Grundy d'une position on a besoin d'avoir précédemment calculé les valeurs de Grundy des positions qu'on peut atteindre. Donc dans le cas de la variante ou on peut prendre 2 ou 3 bâtons, les positions avec 0 et 1 bâton ont des valeurs de Grundy = 0 (perdant car plus de mouvement possible) la position avec 2 bâtons ne permet d'atteindre que le tas vide qui a comme valeur de Grundy 0 (donc la plus petite qu'on ne peut pas atteindre est 1 ce qui nous donne donc la valeur de Grundy de cette position avec 2 bâtons). La position avec 3 bâtons ne permet d'atteindre que les positions avec 0 et 1 bâtons et qui ont toutes les deux une valeur de Grundy = 0 donc pour un tas de 3 bâtons la plus petites valeur de Grundy qui ne se trouve pas dans celles des positions qu'on peut atteindre est donc également 1, etc... On les calcule dans l'ordre en fonction: de celles précédemment calculées, de l'initialisation ( le fait que les positions terminales perdantes aient une valeur de Grundy = 0 par définition) et de notre définition par récurrence (plus petite valeurs de Grundy qui ne se trouve pas dans les valeurs de Grundy des positions qu'on peut atteindre). C'est plus clair?
@@jeanpaullamont essayez avec cette définition "le plus petit entier naturel en excluant toutes les valeurs de grundy atteignable" + le fait que cette valeur s'obtient par récurrence (on ne peut pas calculer une position indépendamment des précédentes, il faut dérouler tout le processus en partant du tas 0)
@@PasseScience ok je comprends mon erreur, j'ai confondu valeur de grundy et taille d'un tas, merci pour l'attention
Super sujet, super approche comme toujours
J'ai pas compris pourquoi les valeurs de Grundy était cyclique, je réessayerai avec plus de sommeil
Le jeu du morpion c'est pareil ?
Le morpion n'est pas un jeu impartial (les coups changent en fonction du joueur) donc ça ne s'applique pas, mais certainement beaucoup d'autres théorèmes s'appliquent :)
Petit commentaire sans méchanceté pour dire que la clarté des explications est a revoir
@@roseplayer92 A quel timestamp par exemple ? et vous proposez quoi comme alternative ?
19:55 il y a t il le poker dans ce livre ? >
9:36 normalement à partir de ce moment là, la plus petite valeur qu’on ne peut pas atteindre restera 0… Car on ne pourra plus atteindre 0 , et 0 restera la plus la plus petite valeur… 🤷♂️
On parle de la plus petite valeur de Grundy qui ne se trouve pas dans les positions qu'on peut atteindre, pas de la taille du tas.
@@PasseScience bas c'est toujours 0, non? la plus petite valeur qu'on ne peut pas atteindre sera toujours zero... L'énoncé ne serait pas plutôt "la plus GRANDE valeur de grundy que l'on ne peut pas atteindre"? Prenons la position 5 par exemple, il ne peut atteindre ni 0 ni 1 qui ont pour valeur de grundy 0 et 1 donc la réponse devrais être 0, mais vous dites que c'est 1, c'est donc la plus grande valeur non atteignable qui compte, non? Si on continue, 6 peut atteindre 5, 4 ou 3 mais pas 0, 1 ou 2 qui ont pour valeur de grundy 0 1 ou 2 donc la plus petite est encore 0 et la plus grande 2, vous choisissez 2 donc encore la plus grande.
...on verra si je comprends mieux par la suite...
EDIT : haaaa ok... c'est la plus petit valeur de grundy non atteignable PARMIS les valeur de grundy atteignable... non même dit comme ça c'est chelou... peut être "le plus petit entier naturel en excluant toutes les valeurs de grundy atteignable" là ouais on comprends direct.
@@SylouCool Moi aussi j'ai mis un petit moment à saisir. La définition donnée est correcte il s'agit bien de la plus petite VALEUR de GRUNDY non accessible. Depuis un tas de 6 bâtons avec une règle permettant de retirer 1, 2 ou 3 bâtons on peut atteindre les positions a 5, 4 ou 3 bâtons respectivement de VALEURS de GRUNDY 1, 0 et 3. 2 est donc la plus petite VALEUR de GRUNDY non accessible, c'est donc la VALEUR de GRUNDY associée à la position à 6 bâtons.
je ne comprends rien a ces explications, et je perds toujours a ce jeu !!
Ouaaah ça me brise les symétries ce truc.