Je tiens à dire que ce nouveau format où vous allez voir des chercheurs est vraiment passionnant, j’ai énormément de plaisir à les regarder, en plus on comprend tout :)
Super. En voyant l'annonce, je me suis dit "mais y a rien à dire sur le morpion, c'est tellement résolu", quand j'ai vu que la vidéo durait 20 minutes j'ai eu un doute, et au final y avait beaucoup de choses intéressantes à dire :D
J'ai tendance à préférer une vidéo d'une durée moyenne ou longue pour un sujet simple que des vidéos courtes ou moyennes sur des sujets assez complexes
Le morpion est bêbête, je vous propose le "super morpion", une grande grille 3x3 avec 9 petites grilles de morpion dans chaque case. On joue les petites grilles, et pour choisir laquelle jouer c'est la dernière position jouée (par l'adversaire), par exemple l'adversaire joue au centre d'une petite grille, vous devez jouer la petite grille du centre. Quand une petite grille est gagnée, le vainqueur dessine alors un gros rond ou une grosse croix dans la grande grille. Le vainqueur final est bien-sur celui qui gagne la grande grille. les règles ne sont pas très compliquées mais par contre ça rends la stratégie bien plus intéressante qu'une simple grille 3x3. voilà, c'est cadeau, amusez-vous bien :)
le deuxième joueur peu toujours garantir l’égalité en répondant sur la même petite grille à chaque coup avec une réponse de morpion normal. Et de même le premier joueur peut garantir l’égalité avec la même stratégie. Donc ce jeu est complètement analogue à 9 parties de morpion en simultané. A l’exception prête qu’il faut gagner MINIMUM 3 parties sur 9 pour espérer gagner la meta-partie. Si faire des égalités est ennuyeux, alors le super morpion est le plus ennuyeux des jeux.
@@raphaelnej8387 Les règles sont plus complexes que ça. On est obligé d'aller jouer sur la petite grille indiquée par le coup de l'adversaire, donc on ne peut pas forcément répondre au coup adversaire sur la même petite grille. Si on envoie son adversaire sur une autre grille, peut-être qu'ultérieurement on pourra compléter notre alignement avant que l'adversaire n'ai pu y répondre. Je connais cette variante sous le nom "ultimate tic-tac-toe" en.wikipedia.org/wiki/Ultimate_tic-tac-toe
Oh, un numberphile. Mais mais mais... Je comprends tout !!!!!! Et je suis pas crevé à la fin de la vidéo à pas savoir quelle langue je parle. J'adore ce format, le concept et super.
c'est chouette... contrairement au livre, c'est beaucoup plus court d'écrire un programme de morpion qui ne perd jamais (gagne ou nul) car par rotations et symétries on peut réduire beaucoup de coups par 2 ou par quatre (ex, démarrer dans un coin se réduit à un coup avec 4 rotations du plateau, pareil pour un côté et un seul coup au milieu donc au premier tour on ramène les 9 possibilités à trois)
@@alineparreau7103 j'ai plus les chiffres en tête, ca fait + de 30 ans que j'ai écrit le programme mais c'est plus ou moins ca... ca reste quand même plus confortable à écrire que les 362.880 combinaisons possibles si on n'enlève pas les coup gagnants avant le 9ème tour... Et si on se calque sur une stratégie humaine genre le centre est prioritaire et les coins valent plus que les côtés, etc. plutôt que de traiter chaque combinaison, on arrive à un programme très simpliste.
@@Jethro.Maloku-le.Rey.Kalsitran Exemple de programme: Joue chaque coup de manière à respecter ces règles, par ordre de priorité (dans le cas où plusieurs coups sont possibles, joue au hasard): - si deux de tes pions sont alignés avec une case vide, remplit la case vide - si l'adversaire a deux pions alignés avec une case vide, remplit la case vide - si le centre est libre, joue au centre - ne répond pas à un premier coup au centre par un deuxième coup sur le bord c'est pas la meilleure stratégie (puisque ça ne punit pas toujours les erreurs adverses), mais c'est une stratégie qui ne perd jamais (à moins d'une erreur de ma part, ce qui est très possible).
@@anneaunyme non, tu ne fais pas d'erreurs, l'ordre et les options me semblent en effet traduire la stratégie gagnante suivant une logique humaine, merci pour la suggestion 👍 et bravo pour le pseudo 😂
@@anneaunyme 1. Je joue dans le coin en bas à droite 2. Règle 3, tu joues au centre 3. Je joue le coin en haut à gauche 4. Tous les coups sont possibles, tu joues au hasard le coin en haut à droite 5. Je joue le coin en bas à gauche 6. Règle 2, tu joues bord gauche ou bord bas 7. Je joue l'autre bord et j'ai gagné :)
Question un peu bébête sur la situation en 5:10 mais le joueur avec les X a perdu uniquement parce que son objectif a été changé/rendu plus facile. Je m'explique : il avait 2 X en diagonale. Si au lieu de cherchait à bloquer les alignements de O il avait choisi de continuer à construire sa diagonale, il aurait eu 3 X avec 2 positions gagnantes, et le joueur 1 avait perdu... J'ai fait une erreur quelque part ?
Oui, c'est vrai ! Mais si les règles avaient été différentes, le rond aurait joué différemment. En fait il existe un argument qui justifie qu'on ne s'intéresse pas à la victoire des croix : le vol de stratégie. Puisqu'on considère que les 2 joueurs jouent parfaitement, s'il existe une stratégie qui permet au 2e joueur de gagner, alors le 1er peut l'adopter aussi, puisqu'avoir une pièce en plus sur le plateau lui procure un avantage stricte. À partir de cet argument, la plupart de la recherche s'oriente sur le premier joueur, pour gagner du temps. D'ailleurs si les stratégies de résolution de ces jeux t'intéressent, je t'invite à te renseigner sur les "jeux m, n, k", c'est une généralisation de ce concept !
A 5:16 , c'est presque de la triche de dire que les ronds ont gagné car ne peuvent pas etre bloqués par les croix, car si l'objectif des croix pouvait également inclure de gagner soi-même, comme c'est à son tour de jouer, il pourrait simplement aligner son coup en diagonal pour prolonger sa propre ligne (comme il est dit que le plateau est infini), et à ce moment là, pour le coup suivant des ronds, ils ne peuvent ni gagner, ni bloquer les croix. Donc enfait ce n'est pas "pour compenser l'aventage de ne pas commencer, en cas d'égalité c'est les croix qui gagnent", mais plutot "les croix n'ont pas comme objectif d'en aligner 4 mais simplement que les ronds ne le fassent pas".
Les échecs, le go, les dames ont leur littérature stratégique. Grâce à la science, le morpion a manifestement sa littérature stratégique. Ça me fait penser qu’il existe un jeu d’alignement de 5 qui s’appelle Yinsh qui mériterait amplement sa propre littérature tant il semble profond et mérite d’avoir un large public, tout comme ceux sortis dans la même série (appelée projet Gipf). Description : « YINSH est un jeu "turbulent" ! Les joueurs commencent la partie chacun avec 5 anneaux sur le plateau. Chaque fois qu'un anneau se déplace, il laisse un marqueur derrière lui. Les marqueurs sont blancs d'un côté, noirs de l'autre. Quand un anneau saute par-dessus une série de marqueurs, ceux-ci doivent être retournés, ce qui fait que leur couleur change constamment. Les joueurs doivent essayer de former des alignements de 5 marqueurs de leur couleur. Si un joueur réussit un tel alignement, il retire l'un de ses anneaux pour signifier sa réussite. Le premier joueur à retirer trois anneaux gagne la partie. En d'autres termes, chaque alignement réalisé vous rapproche de la victoire - mais vous affaiblit également, dans la mesure où vous jouez avec un anneau en moins. Problème épineux ! »
5:08 Faille ! Et si plutôt que d'empêcher les ronds de gagner les croix jouaient offensifs en en alignant une troisième croix ? Ce serait la victoire des croix.
Mais les règles ont été changées : le joueur croix ne cherche pas à aligner ses symboles, mais à empêcher le joueur rond d'aligner ses symboles 3:00 :)
@@fudjiM310 Je sais bien, mais à ce moment de la vidéo j'avais compris que l'objectif des croix n'était plus d'en aligner 4 mais *aussi* d'empêcher les ronds de le faire. Donc pour moi empêcher l'adversaire de gagner en gagnant avant devait être valide. En tout cas c'était rageant de voir que les croix devançaient les ronds mais s'empêchaient d'en aligner 4 en diagonale.
@@zephyr9016 je réponds avec le souvenir que dans la vidéo, quand on passe au tableau, notre présentatrice change deux règles : 1/ notre périmètre est possiblement infini et 2/ le deuxième joueur, pour gagner, doit uniquement empêcher la realisation par le premier joueur, d'une succession de symboles. C'est tout. Si ce deuxième joueur parvenait à aligner ses symboles, il ne gagnerait pas. Donc la meilleur défense c'est l'attaque n'a pas lieu d'être ici, car il ne peut gagner qu'en défendant.
Super intéressant! Le gomoku 6 ou 7 étant hors de portée d'une recherche rapide, je me suis demandé ce qui se passe si le but du premier joueur O est de construire un carré 2x2 au lieu d'un alignement. Réponse: X peut toujours l'en empêcher. La preuve est du même genre que pour les gomoku 9 et 8 en plus simple. (Beaucoup plus simple 😀)
C'est super intéressant ! Et j'imagine qu'il y a probablement un lien entre ces nombres (Rond gagne jusqu'à 5 mais probablement pas au-delà) et le nombre de dimensions du jeu (2 en l'occurrence). Si le jeu était sur 3 dimensions, Rond pourrait probablement gagner avec des alignements plus longs.
3 dimensions c'est trop petit pour un matheux, il faut y aller sur n dimensions. Pour n=1 on voit que trivialement c'est 2, n=2 entre 5 et 7, n=3 ? Le nombre de directions c'est 2, 8, puis 26, 80, 242, etc. C'est vachement dur de tout bloquer.
Super interessant comme sujet, par contre maintenant une question m'intrigue comment on passe d'un escalier à un H avec une étape... est-ce qu'il n'yaurait pas moyen de trouver la solution aux 6 et 7 en trouvant la formule qui modifie la configuration d'une étape à l'autre?
Bonjour, super vidéo, à la 5ème minute avec 4 symboles d'affilé, c'est le joueur avec les croix qui va gagner. Je m'explique : le joueur 1 a joué 3 fois et a 2 cercles alignés pendant que le joueur 2 a joué 2 fois et a 2 croix alignées, c'est au joueur 2 de jouer, il joue une 3ème fois une croix alignée avec les 2 précédentes. Le joueur 1 ne peux ni gagner avec ses lignes et diagonales de 2, ni bloquer la diagonale de 3 du joueur 2, le joueur 2 gagne donc.
Bonjour et merci pour votre message. En fait, à ce moment de la vidéo les règles du jeu ont été modifiées. Les croix cherchent juste à empêcher les ronds de faire un alignement, pas à en faire un eux-même. Dans cette variante, faire un alignement n'est pas gagnant pour les croix.
Intéressant mais avec une grille en 3 dimensions ça donnerait quoi ? Il serait amusant de découvrir quelles formes en 3D permettrait d'empêcher quels alignements de n ? Et pour le morpion classique en 2D à 5 cases (n=5) cela pourrait aussi avoir des applications en sociologie des organisations : par exemple comment empêcher des regroupements de plus de 4 personnes ou des cohésions groupales entre plus de 4 voisins en plaçant le plus efficacement possible un obstacle (une personne, un mur, une route, etc). Sur une foule, ça me paraît compliqué car elle est mouvante mais sur des habitations, on peut donc empêcher que 5 habitations soient continues, bon ça donnerait des routes un peu tordues mais théoriquement c'est possible du moins si tous les voisins possèdes un terrain de même taille. Pour les embouteillages et les parkings de voitures, cela pourrait peut-être aussi avoir des applications concrètes,
Je commence tout juste la vidéo, mais n'aurait-on pas pu économiser pas mal de papier en incluant un code pour faire une rotation et/ou une symétrie axiale du plateau ? J'admets que ça aurait été plus difficile d'inclure la partie "gagnante" pour le lecteur.
Chaud la remarque !! La démonstration serait plus simple à faire pour démontrer que X va gagner, donc sans doute, il doit gagner ! ... Alors qu'ils indiquent juste avant que pour 5, la démonstration est ultra laborieuse.
C'est parce que limiter X à bloquer O n'est pas juste une "simplification", mais un changement de règle. Le joueur O ne peut pas gagner en alignant lui-même 4 O, mais seulement en empêchant d'avoir 4 X. Sinon, je suis d'accord, dans cet exemple là, le joueur O ne pourrait pas jouer comme ça.
Je suppose qu'il suffit d'en trouver un qui marche, mais qu'il peut y en avoir d'autres. D'ailleurs, le pavage de 8 fonctionne aussi logiquement pour le 9 (qui peut le plus peut le moins)
Pour le cas n=6, mon intuition me dirait qu'il faut chercher un pavage "éclaté". Par exemple, est-ce qu'une grille 3x3, avec une case de séparation entre chaque ligne et chaque colonne ne pourrait-elle pas faire l'affaire ? Il suffirait de bloquer tous les "alignements" de cette figure, et ça on sait déjà le faire.
Pourquoi le nombre a partir duquel il n'y a plus de strategie gagnante serait plutôt 6, et non 8? Instinctivement et naivement 8 fairait plus de sens, étant donné qu'il y a 8 cases a coté de la case initiale.
Merci pour cette vidéo. Très intéressant ! Il y a certains points qui ne sont pas clair je trouve, même si X peut bloquer, finalement sur un plateau infini, personne gagne dans avec les règles énoncées. Le gomoku, le but de jeu est qu'un des deux joueurs alignent 5 pions, ce n'est pas les mêmes règles que dans la situation que vous présentez donc pas le même jeu.
On peut dire qu’on ne joue pas avec une grille infinie, mais qui tend vers l’infini (en gros, X gagne si peu importe la taille de la grille, O ne peut pas faire son alignement)
Bonjour, à ce moment là de la vidéo les règles du jeu ont été modifiées. Les croix cherchent juste à empêcher les ronds de faire un alignement, pas à en faire un eux-même. Dans cette variante, faire un alignement n'est pas gagnant pour les croix.
00:05:12 - C'est faux. C'est seulement valable avec votre règles où "X" ne cherche pas à gagner mais seulement bloquer "O". Dans la logique du jeu, il suffi que "X" place une autre croix à la suite (en diagonale) des 2 autres et c'est lui qui gagne.
5:04 -> Le joueur avec les croix a gagné, il joue 2 cases au dessus de l'alignement de 2 ronds et aligne trois croix avec 2 libertés. Mais je vois bien comment Rond peut forcer le gain si il joue mieux au 3eme coup. Rond joue en bloquant l'alignement de deux croix, 2 cases au dessus de son propre rond. Croix est obligé de jouer au milieu des deux ronds pour empecher un alignement de 3 ronds avec deux libertés. Rond joue dans le prolongement de son premier alignement, mais une case plus loin. croix est obligé de jouer au milieu pour empecher l'alignement gagnant. Rond joue au dessus de croix et a un alignement de 3 à deux libertés. Si bien sur on considère que croix peut gagner en bloquant rond ou en réalisant soi-même son objectif de faire un alignement, ce qui fait que Rond ne peut pas jouer n'importe comment non plus.
Bonjour, à ce moment là de la vidéo les règles du jeu ont été modifiées. Les croix cherchent juste à empêcher les ronds de faire un alignement, pas à en faire un eux-même. Dans cette variante, faire un alignement n'est pas gagnant pour les croix.
Super vidéo, les maths n'ont jamais fini de nous surprendre ! Si rond gagne en en alignant 7 : ne peut-on pas utiliser le modèle des H ? On remarque que pour en aligner 7, ROND doit obligatoirement passer par un centre de H, peu importe qu'on y aille en diagonale, verticale ou horizontale. Chaque cas de figure de 7 doit forcément passer par un centre à un moment. Ne pourrait-on pas alors ne jouer que les centres des H afin d'assurer une "victoire par blocage" à X ?
Sujet très intéressant !! Au timecode 5:18 : "[...] j'ai gagné, quoi que tu fasses [...]" Je vois pourtant deux positions gagnantes pour les X si on ne cherche pas à bloquer les O mais plutôt en cherchant à contre-attaquer: - si les X jouent en haut à gauche de la diagonale formée par les deux X déjà présents - si les X jouent en bas à droite de la diagonale formée par les deux X déjà présents Dans ces deux positions, les O ne pourront pas bloquer les trois X alignées avec une liberté à chaque extrémité de la diagonale.
Super intéressant, super vidéo ! Est-ce que l’on peut calculer l’épaisseur du livre qui donnerait toutes les coups possible dans une partie d’échecs….. Je crois qu’il n’y aurait pas assez d’arbres sur terre…..
@@AndreMalraux20341 Non, pas « malheureusement non résolu », mais au contraire heureusement non résolu, car il n’y aurait plus de plaisir ni charme à ce jeu dans lequel le hasard ne joue aucun rôle 😜.
@@mikaelderetour1933 Ha bon? Vous êtes donc capable; 15-20-30 coups à l'avance, d'élager à 100% toutes les branches menant à une défaite certaine?? Si les échecs avaient été résolu, par définition même, il n'y subsiterait plus aucuns hasard non?!
@@francoisduchene5676 C’est exactement ce que je voulais dire, l’arborescence des coups étant quasiment infinie, le livre aurait du mal à exister, au premier coups des blancs il y a 20 coups possibles, en réponses des noirs 20 coups également. Donc déjà 400 possibilités, évidemment pas toutes bonnes pour la stratégie du jeu mais elles existent, donc 400 pages, sur le principe du livre sur le morpion.
Je ne comprends pas pourquoi on arrive à faire 5 sur un plateau infini alors que sur un jeu correct on ne gagne pas dans un carré 3x3... Si on pave avec des carrés pour défendre, comment l'autre gagne ? Une subtilité m'échappe
Ce que je vais dire ne relève que d'une hypothèse, ce n'est rien de certain: De ce que j'ai compris, un pavage satisfaisant est un pavage où, où que tu place la règle, la ligne de 5 contiendra les mêmes cases d'une des formes. Sauf que si tu pave le plan infini en carrés Si tu pave le plan infini en carrés, tu te rendra compte que une règle de 5 carrés ne couvrira pas toujours les mêmes cases de chaque carrés, selon ou tu te place, donc que le pavage en carrés n'est pas satisfaisant (Par exemple, tu auras les cases A1, B2, C3 d'un carré, puis A1 et B2 d'un autre, mais si tu place la règle d'une manière, mais d'une autre façon, tu aura A2, B3 d'un carré, C1 d'un autre carré, puis encore A2 et B3 d'un autre carré) Puisque tu n'as pas les mêmes cases selon la position de la règle, même si Croix peut techniquement bloquer les alignements de 3 dans chaque carrés, Rond pourra toujours faire son alignement de 5, même si a aucun moment, il n'y aura 3 rond dans le même carré (Tu aura par exemple 2 dans un carré, un dans un autre, puis 2 dans encore un autre)
@@yugapillon1343, merci... Je partais du principe qu'une ligne de 5 était constituée sur deux carrés... c'est vrai en horizontal et vertical, pas forcément en diagonale
J'avais une question car si on prend le cas 9 où chaque rond est répondu avec une croix qui n'est jamais (si j'ai bien regarder) dans la même colonne que le rond venant d'être jouer. Alors ne serait-il pas possible de seulement faire une colonne d'entrée de jeu si notre adversaire suit à la lettre le schéma. Ou alors ceci n'a pas été spécifié car cela semblait logique et que dans la pratique la réponse autre que le schéma n'est pas un problème. Je ne sais pas si ça a été clair. Vous pouvez me demander si vous n'avez pas compris et j'essaierai de me faire mieux comprendre.
Lorsque rond va vouloir faire une colonne de 9, il y aura forcément un moment où il va devoir jouer dans la colonne de droite d'un H. On pourra alors le bloquer lorsqu'il va jouer dans cette colonne
En martinique on a une version sans limite mais faut aligner 4. et c'est vrai que le jeu change vraiment. "ti points ti croix". On y joue des tout petit et Rond gagne pas forcément
Je me demande si c'est possible de participer au recherche genre si jamais on trouve des choses, est ce qu'on peut envoyer nos démonstrations, quand j'étais au collège j'ai résolu le tic tac toe 3x3 juste en essayer toute les combinaisons possibles et j'ai eu les mêmes résultats que vous pour les alignements de 3 et 4 signes sur un plateau illimité. J'ai pas chercher plus loin mais j'ai aussi résolu comme vous les débuts et j'aime trop réfléchir et me creuser la tête sur des jeux de stratégie du coup si c'est possible de participer ou d'envoyer des démonstrations j'aimerais en envoyer avec grand plaisir
Au club de go, quand on a envie de varier, on joue souvent au gomoku et au Ninuki-renju (que j'appelais par erreur Gomoku - voir Wikipedia). Ces deux variantes me semblent plus intéressantes que le morpion-5 présenté ici.
À 5:10 il suffit de mettre la croix dans la continuité des deux première pour bloquer l'adversaire avec une brochette de trois en diagonal. La stratégie est donc pas vraiment valable...
Bonjour, à ce moment là de la vidéo les règles du jeu ont été modifiées. Les croix cherchent juste à empêcher les ronds de faire un alignement, pas à en faire un eux-même. Dans cette variante, faire un alignement n'est pas gagnant pour les croix.
Pour l'approche par pavage connexes, les tuiles ne peuvent pas contenir de droite de taille supérieure à n, où n est le nombre que l'on essaie d'aligner. Donc le pavage est inclu dans un carré n par n. Il y a donc moins de 2^(n^2) pavage à tester. En utilisant la symétrie par rotation, on peut déjà diviser par 4 le nombre de pavage à tester. Pour n=6, ça fait 2^36/4=2^32~=4e9, avec les ordinateurs modernes on peut facilement tout tester en quelques minutes au plus. Pour n=7, ca demande un peu de plus de réflexion mais la contrainte d'etre un pavage va pouvoir réduire drastiquement le nombre de cas. Pour les pavages plus généraux, on doit pouvoir montrer de façons assez simple qu'on peut se contenter de regarder localement, par la nature local de "etre aligner".
Je dis peut etre des bêtises mais c'est pas parce que on ne peut pas placer une droite de taille supérieure à n qu'on a le droit de se placer dans un pavage de n par n. Par exemple pour n=3, croix peut gagner à tous les coups dans un pavage de 3×3. Alors que rond gagne dans un pavage infini.
Sinon, on peut même encore diviser le nombre de cas à tester, puisqu'on peut faire des symétries axiales (Horizontale, diagonales et verticale). On peut encore le diviser par 4
5:10 je ne suis pas d'accord. Dans l'hypothese ou le quadrillage est infini, les croix peuvent gagner si ils continuent leur diagonale. En effet ils auront 3 croix alignées avec 1 case libre de chaque coté
5:15 Le joueur peut jouer en diagonale vu que la grille est ''infinie'' donc théoriquement il met une croix en diagonale, il en aligne trois et c'est imbattable pour les ronds
Bonjour, à ce moment là de la vidéo les règles du jeu ont été modifiées. Les croix cherchent juste à empêcher les ronds de faire un alignement, pas à en faire un eux-même. Dans cette variante, faire un alignement n'est pas gagnant pour les croix.
Après, est ce qu'on peut vraiment dire que X gagne? En soit c'est pas vraiment une stratégie victoire ou égalité, c'est plus une stratégie "au pire égalité". Du coup les stratégies de X montrent juste qu'à partir d'un certain nombre d'éléments à aligner en même temps, il n'y a pas de stratégie gagnante, et que la meilleure stratégie est une stratégie d'égalité, mais qui ne peut pas gagner, et donc, dans le cadre d'un jeu infini, ça signifie que si les deux joueurs ne font pas d'erreur et ne se trompent pas, les parties sont infinies, puisque sur un plateau infini, sans victoire, il n'y a pas de fin à la partie. Du coup je ne sais pas si on peut vraiment dire que X a une stratégie gagnante. En fait, ce qu'on peut voir, c'est surtout que qu'importe le nombre d'éléments à aligner, si O ne fait pas d'erreur, il ne peut pas perdre, puisque soit il gagne, soit il y a une égalité sur une partie infinie. Est ce que ma réflexion est bonne? Ou je suis à côté de la plaque? :p
La réflexion me semble très intéressante ! Le premier point est qu'en effet, ce qu'on appelle "X gagne" dans les nouvelles règles ressemble à "ex aequo" dans les règles de base. Le problème des règles de base, dans ce cadre d'étude, c'est qu'on n'aime pas tellement les égalités. On veut un gagnant et un perdant. C'est pour ça (au moins en partie) que les règles sont modifiées. Le deuxième point, c'est que le deuxième joueur ne pourrait pas avoir de stratégie gagnante avec les anciennes règles. Pour s'en convaincre, il suffit de supposer que c'est le cas, et voir que ça entraîne le fait de donner une stratégie gagnante pour le premier joueur : - en tant que premier joueur, je joue un coup n'importe où, et je l'oublie (virtuellement). - je fais comme si mon adversaire démarrait la partie, et j'applique la stratégie gagnante en tant que deuxième joueur. L'idée, c'est que le O que j'ai placé au début ne pourra jamais me gêner (je limite les actions de mon adversaire, et si ma stratégie me disait de jouer ici, vu que c'est déjà fait, j'aurais juste à jouer autre part et à oublier (toujours virtuellement) ce coup. Évidemment, c'est raconté un peu rapidement ici, mais c'est le même principe que pour le jeu de hex. Mickaël Launay l'a montré en vidéo il y a quelques années : "Théorie du jeu de Hex 3 (Stratégie gagnante pour le premier joueur)".
je me suis toujours dit que les jeux sans aléatoire avait des stratégies gagnantes et une fois celle-ci découverte le jeux serait "cassé" j'attends donc avec impatiente le jour où on trouvera la stratégie gagnante des échecs ! même si bonne chance si on veut l'imprimer ou la retenir
Tu risques d'attendre longtemps, environ 580 ans au mieux. En effet, le mathématicien Claude Shannon a calculé le nombre de parties d'échecs, qui est de l'ordre de 10¹²⁰. Or, en considérant que la puissance des supercalculateurs les plus puissants du monde continue d'augmenter de manière exponentielle comme ce fut le cas ces 60 dernières années (chose qui n'est pas du tout acquise en raison des probables limites physiques), on trouve que, l'année où le supercalculateur le plus puissant du monde aura la puissance suffisante pour ne mettre "que" 100 ans à faire 10¹²⁰ opérations élémentaires (précisément: opérations en virgule flottante) est... 2504. Date à laquelle il faut ajouter les 100 ans de calcul, dans le cas où le dictateur du monde de 2504 est un fan d'échec et est prêt à sacrifier 100 ans du meilleur supercalculateur et la monstrueuse quantité d'énergie nécessaire à le faire tourner juste pour résoudre les échecs, et on arrive à l'an 2600 environ.
@@lesubtil7653 intéressant mais une fois le premier super-ordinateur conçu la technologie continuera de progresser donc le temps de calcul se réduira de plus en plus
Euh..... à 5:09 elle annonce qu'elle a gagné alors que c'est faux o_O C'est au joueur croix de jouer, qui peut aligner en diago une troisième croix, avec aucun blocage nulle part, là où le joueur rond n'a qu'un "triangle" de 2 ronds alignés au max. Je suis pas allé plus loin dans la vidéo tellement ça me semble aberrant qu'elle impose son "là j'ai gagné" et qu'elle ne laisse pas le joueur croix placer son pion où il le souhaite !
Bon je m'auto-réponds, j'ai vu la vidéo en entier. Je n'avais pas compris que la règle pour le joueur croix était seulement de bloquer rond. C'est étrange d'en faire un jeu à règles asymétriques, quand même le jeu de go dans sa forme actuelle ne l'est pas. Y a-t-il des exemples de jeu à règles asymétriques ? Le reste de la vidéo était très intéressant ceci dit.
Pour quelle raison le livre a une erreur ? C'est juste pour que l'être humain puisse le battre ? Donc ce livre est en soi un casse-tête (qui consiste à chercher la faille unique) ?
9:51 Ca n'est pas la peine d'expliquer comment bloquer les quatre alignements dans le H puisque le H est contenu dans une grille de morpion 3x3 normale et qu'on sait déjà comment bloquer l'adversaire au morpion normal 😉
C'est une bonne remarque mais je pense que c'est parfois mieux de réexpliquer certaines choses plutôt que de dire " on sait déjà faire " ou quelque chose comme ça. On comprend mieux !
Ça ne marche pas si on raisonne comme ça car si on regarde deux H qui sont "emboîtés" l'un au dessus de l'autre, leurs carrés 3*3 associés se chevauchent : ils ont deux cases communes. Donc si les ronds jouent dans l'une de ces deux cases communes, on ne peut pas répondre à la fois dans les deux carrés 3*3. On est obligé de prendre un coup de retard sur l'un de ces deux carrés et dans ce cas là, les ronds peuvent assez facilement l'emporter sur ce carré.
@@Micmaths A ce moment là de la preuve, on étudie une sorte de "jeu auxiliaire" qui se passe dans un H (un seul) et qui est très facile, plus facile que le morpion 3x3, donc on est tout de suite convaincu qu'on va gagner à coup sûr !
@@estebanziatao Effectivement, mon argument précédent n'était pas bon. En fait le problème vient du fait que les règles dans le H ne sont pas les mêmes que celles du morpion classique : X ne gagne pas s'il fait un alignement de 3, il ne gagne que s'il empêche O de faire un tel alignement. Par exemple, si dans le H il fallait bloquer les deux barres verticales et non pas seulement celle de droite, alors X ne pourrait pas empêcher O de faire un alignement. Pourtant, on pourrait tout autant penser que c'est facile puisqu'il s'agit également d'un jeu "contenu" dans le morpion classique.
Super ,quand je pense que des gens hyper intelligent ,qui sont essoufflé juste en restant debout 4minutes ,prennent le temps de se demander qui gagnerais sur un morpion à 6 ,je suis heureux
Bonjour, à ce moment là de la vidéo les règles du jeu ont été modifiées. Les croix cherchent juste à empêcher les ronds de faire un alignement, pas à en faire un eux-même. Dans cette variante, faire un alignement n'est pas gagnant pour les croix.
5:16 ... "J'ai gagné"... Je crois bien que non ! car si les X décident d'aligner un troisième en diagonale au lieu de défendre, alors IL A GAGNÉ (quoi que vous fassiez) :) !
Bonjour, à ce moment là de la vidéo les règles du jeu ont été modifiées. Les croix cherchent juste à empêcher les ronds de faire un alignement, pas à en faire un eux-même. Dans cette variante, faire un alignement n'est pas gagnant pour les croix.
Ok, c'est sûr qu'avec des cases en plus , celui qui commence gagne toujours. Le but au morpion est de créer 2 lignes tout en bloquant l'adversaire. Il tente d'aligner ses 3 motif alors qu'on le double sur le fil du rasoir. Voilà tout. Si vous prenez 4 cases, il faut aligner 4 motifs, là d'accord.
Lorsqu’on était au secondaire (Lycée du Québec), on jouait au S-O-S, une grille infinie mais il fallait utilisé le symbole de l’autre pour gagner et faire un SOS. Ça ressemble un peu à votre principe.
Ce n’est pas le même jeu que le morpion. Ici, le but de X c’est de bloquer l’autre. Qu’il fasse un alignement ne sert à rien, son but c’est de bloquer l’autre
A la 5.17 min vous dites : j'ai gagné ! en fait, si au lieu de chercher obstinément à vous bloquer, le joueur construit son jeu, il suffit qu'il joue sur la diagonale des deux croix déjà en place et la partie est terminée: vous avez perdu...
Mais les H, ils n'existent pas. On peut décaler le pavage en H à droite, à gauche, en haut, en diagonale et ça donne un autre pavage de H. Jouer "au centre du H", ça ne veut rien dire. Ou alors, on peut dire que le premier coup est toujours au centre de ce qui va devenir un H, et on pave en H le reste en fonction de ça ?
Oui, le pavage en H n'existe que dans la tête du joueur croix qui s'en sert pour appliquer sa stratégie. Peu importe le décalage de ce pavage, il faut juste que croix décide où il le place en début de partie et n'en change plus. A priori, le joueur rond n'a pas à être au courant de ces H, mais même s'il le savait il ne pourrait rien faire pour gagner (tout au plus il pourrait être un peu plus embêtant en visant les centres des H).
Je tiens à dire que ce nouveau format où vous allez voir des chercheurs est vraiment passionnant, j’ai énormément de plaisir à les regarder, en plus on comprend tout :)
Super. En voyant l'annonce, je me suis dit "mais y a rien à dire sur le morpion, c'est tellement résolu", quand j'ai vu que la vidéo durait 20 minutes j'ai eu un doute, et au final y avait beaucoup de choses intéressantes à dire :D
J'ai tendance à préférer une vidéo d'une durée moyenne ou longue pour un sujet simple que des vidéos courtes ou moyennes sur des sujets assez complexes
@@phenix36trmui.
En fait, quel que soit le sujet traité, ce que j’adore, c’est l’ambiance de chacune de ces vidéos ! Remarquable travail. Merci 👌
C'est vraiment trop trop bien. Je vais me régaler des vidéos de la chaîne bonus.
Toujours passionnantes les vidéos du Myriogon. Bravo
Ses cercles sont exceptionnels
Bravo, c'est passionnant, par contre vous ne produisez plus de vidéos ? Ce serait dommage :(
Le morpion est bêbête,
je vous propose le "super morpion", une grande grille 3x3 avec 9 petites grilles de morpion dans chaque case. On joue les petites grilles, et pour choisir laquelle jouer c'est la dernière position jouée (par l'adversaire), par exemple l'adversaire joue au centre d'une petite grille, vous devez jouer la petite grille du centre. Quand une petite grille est gagnée, le vainqueur dessine alors un gros rond ou une grosse croix dans la grande grille.
Le vainqueur final est bien-sur celui qui gagne la grande grille. les règles ne sont pas très compliquées mais par contre ça rends la stratégie bien plus intéressante qu'une simple grille 3x3. voilà, c'est cadeau, amusez-vous bien :)
Ça existe d'ailleurs en jeu vidéo sur itch
le deuxième joueur peu toujours garantir l’égalité en répondant sur la même petite grille à chaque coup avec une réponse de morpion normal. Et de même le premier joueur peut garantir l’égalité avec la même stratégie. Donc ce jeu est complètement analogue à 9 parties de morpion en simultané. A l’exception prête qu’il faut gagner MINIMUM 3 parties sur 9 pour espérer gagner la meta-partie.
Si faire des égalités est ennuyeux, alors le super morpion est le plus ennuyeux des jeux.
@@raphaelnej8387 le plus ennuyeux des jeux c'est le mikado
@@raphaelnej8387 Les règles sont plus complexes que ça. On est obligé d'aller jouer sur la petite grille indiquée par le coup de l'adversaire, donc on ne peut pas forcément répondre au coup adversaire sur la même petite grille. Si on envoie son adversaire sur une autre grille, peut-être qu'ultérieurement on pourra compléter notre alignement avant que l'adversaire n'ai pu y répondre. Je connais cette variante sous le nom "ultimate tic-tac-toe" en.wikipedia.org/wiki/Ultimate_tic-tac-toe
@@nicolasgarland9872 c’est pas ce jeu qui a été proposé par fabien
Oh, un numberphile.
Mais mais mais... Je comprends tout !!!!!! Et je suis pas crevé à la fin de la vidéo à pas savoir quelle langue je parle.
J'adore ce format, le concept et super.
C'est ce qu'on appelle la preuve par 9. Super vidéo sinon (comme toujours). Je suis juste fan.
c'est chouette... contrairement au livre, c'est beaucoup plus court d'écrire un programme de morpion qui ne perd jamais (gagne ou nul) car par rotations et symétries on peut réduire beaucoup de coups par 2 ou par quatre (ex, démarrer dans un coin se réduit à un coup avec 4 rotations du plateau, pareil pour un côté et un seul coup au milieu donc au premier tour on ramène les 9 possibilités à trois)
Oui, c'est vrai pour le début, mais il reste quand même environ 350 positions de jeu différentes quand on ne compte pas les symétriques.
@@alineparreau7103 j'ai plus les chiffres en tête, ca fait + de 30 ans que j'ai écrit le programme mais c'est plus ou moins ca... ca reste quand même plus confortable à écrire que les 362.880 combinaisons possibles si on n'enlève pas les coup gagnants avant le 9ème tour...
Et si on se calque sur une stratégie humaine genre le centre est prioritaire et les coins valent plus que les côtés, etc. plutôt que de traiter chaque combinaison, on arrive à un programme très simpliste.
@@Jethro.Maloku-le.Rey.Kalsitran
Exemple de programme:
Joue chaque coup de manière à respecter ces règles, par ordre de priorité (dans le cas où plusieurs coups sont possibles, joue au hasard):
- si deux de tes pions sont alignés avec une case vide, remplit la case vide
- si l'adversaire a deux pions alignés avec une case vide, remplit la case vide
- si le centre est libre, joue au centre
- ne répond pas à un premier coup au centre par un deuxième coup sur le bord
c'est pas la meilleure stratégie (puisque ça ne punit pas toujours les erreurs adverses), mais c'est une stratégie qui ne perd jamais (à moins d'une erreur de ma part, ce qui est très possible).
@@anneaunyme non, tu ne fais pas d'erreurs, l'ordre et les options me semblent en effet traduire la stratégie gagnante suivant une logique humaine, merci pour la suggestion 👍
et bravo pour le pseudo 😂
@@anneaunyme
1. Je joue dans le coin en bas à droite
2. Règle 3, tu joues au centre
3. Je joue le coin en haut à gauche
4. Tous les coups sont possibles, tu joues au hasard le coin en haut à droite
5. Je joue le coin en bas à gauche
6. Règle 2, tu joues bord gauche ou bord bas
7. Je joue l'autre bord et j'ai gagné :)
Je découvre la chaîne avec cette vidéo et c'est passionnant ! La chercheuse est super pédagogue bravo à elle :)
j'ai pas tout compris mais globalement c'est génial, bravo, c'est puissant.
Ce nouveau format est tellement génial !
Merci
à 5:16 quand elle dit qu'elle a gagné c'est faux nan ? si il met une croix dans la diagonale ou il en a 2 il gagne enfin de ce que j'ai compris
Elle est géniale cette chaîne
Question un peu bébête sur la situation en 5:10 mais le joueur avec les X a perdu uniquement parce que son objectif a été changé/rendu plus facile.
Je m'explique : il avait 2 X en diagonale. Si au lieu de cherchait à bloquer les alignements de O il avait choisi de continuer à construire sa diagonale, il aurait eu 3 X avec 2 positions gagnantes, et le joueur 1 avait perdu...
J'ai fait une erreur quelque part ?
Oui, c'est vrai ! Mais si les règles avaient été différentes, le rond aurait joué différemment. En fait il existe un argument qui justifie qu'on ne s'intéresse pas à la victoire des croix : le vol de stratégie. Puisqu'on considère que les 2 joueurs jouent parfaitement, s'il existe une stratégie qui permet au 2e joueur de gagner, alors le 1er peut l'adopter aussi, puisqu'avoir une pièce en plus sur le plateau lui procure un avantage stricte. À partir de cet argument, la plupart de la recherche s'oriente sur le premier joueur, pour gagner du temps. D'ailleurs si les stratégies de résolution de ces jeux t'intéressent, je t'invite à te renseigner sur les "jeux m, n, k", c'est une généralisation de ce concept !
@@Jonhfing647 Merci pour les infos ! ^^
A 5:16 , c'est presque de la triche de dire que les ronds ont gagné car ne peuvent pas etre bloqués par les croix, car si l'objectif des croix pouvait également inclure de gagner soi-même, comme c'est à son tour de jouer, il pourrait simplement aligner son coup en diagonal pour prolonger sa propre ligne (comme il est dit que le plateau est infini), et à ce moment là, pour le coup suivant des ronds, ils ne peuvent ni gagner, ni bloquer les croix. Donc enfait ce n'est pas "pour compenser l'aventage de ne pas commencer, en cas d'égalité c'est les croix qui gagnent", mais plutot "les croix n'ont pas comme objectif d'en aligner 4 mais simplement que les ronds ne le fassent pas".
Encore une très bonne vidéo
j'aime beaucoup ce format! Évidemment on pense à Numberphile, Et bien un Numberphile à la Française me réjouit! Vivement de futurs épisodes!
Les échecs, le go, les dames ont leur littérature stratégique. Grâce à la science, le morpion a manifestement sa littérature stratégique.
Ça me fait penser qu’il existe un jeu d’alignement de 5 qui s’appelle Yinsh qui mériterait amplement sa propre littérature tant il semble profond et mérite d’avoir un large public, tout comme ceux sortis dans la même série (appelée projet Gipf).
Description : « YINSH est un jeu "turbulent" ! Les joueurs commencent la partie chacun avec 5 anneaux sur le plateau. Chaque fois qu'un anneau se déplace, il laisse un marqueur derrière lui. Les marqueurs sont blancs d'un côté, noirs de l'autre. Quand un anneau saute par-dessus une série de marqueurs, ceux-ci doivent être retournés, ce qui fait que leur couleur change constamment. Les joueurs doivent essayer de former des alignements de 5 marqueurs de leur couleur. Si un joueur réussit un tel alignement, il retire l'un de ses anneaux pour signifier sa réussite. Le premier joueur à retirer trois anneaux gagne la partie. En d'autres termes, chaque alignement réalisé vous rapproche de la victoire - mais vous affaiblit également, dans la mesure où vous jouez avec un anneau en moins. Problème épineux ! »
5:08 Faille ! Et si plutôt que d'empêcher les ronds de gagner les croix jouaient offensifs en en alignant une troisième croix ? Ce serait la victoire des croix.
Mais les règles ont été changées : le joueur croix ne cherche pas à aligner ses symboles, mais à empêcher le joueur rond d'aligner ses symboles 3:00 :)
@@fudjiM310 Je sais bien, mais à ce moment de la vidéo j'avais compris que l'objectif des croix n'était plus d'en aligner 4 mais *aussi* d'empêcher les ronds de le faire. Donc pour moi empêcher l'adversaire de gagner en gagnant avant devait être valide. En tout cas c'était rageant de voir que les croix devançaient les ronds mais s'empêchaient d'en aligner 4 en diagonale.
@@fudjiM310 "la meilleure défense c'est l'attaque, et là comme elle l'a expliqué c'est la seule manière de défendre
@@zephyr9016 je réponds avec le souvenir que dans la vidéo, quand on passe au tableau, notre présentatrice change deux règles : 1/ notre périmètre est possiblement infini et 2/ le deuxième joueur, pour gagner, doit uniquement empêcher la realisation par le premier joueur, d'une succession de symboles. C'est tout. Si ce deuxième joueur parvenait à aligner ses symboles, il ne gagnerait pas. Donc la meilleur défense c'est l'attaque n'a pas lieu d'être ici, car il ne peut gagner qu'en défendant.
@@fudjiM310 très bien mais dans ce cas j’aurais trouvé ça plus clair de dire que la partie ne s’arrête pas si le deuxième joueur aligne 4 croix 😕
Cool, des réponses argumentées à une question que je me suis déjà posée quelques fois. Merci !!!
Super intéressant!
Le gomoku 6 ou 7 étant hors de portée d'une recherche rapide, je me suis demandé ce qui se passe si le but du premier joueur O est de construire un carré 2x2 au lieu d'un alignement. Réponse: X peut toujours l'en empêcher. La preuve est du même genre que pour les gomoku 9 et 8 en plus simple. (Beaucoup plus simple 😀)
C’est ultra intéressant ! J’ai envie d’acheter le livre ^^
Génial et super clair en plus. C'est fou qu'à partir d'un jeu aussi con que le morpion on aboutisse à des questions non résolues en 2022. ;)
J'ai adoré cette épisode, merci continuez comme ça ^^
J’me suis perdu sur TH-cam et j en suis content
C etait très intéressant 🧐
Excellent format ! Ça fait très Numberphile mais version française.
C'est super intéressant ! Et j'imagine qu'il y a probablement un lien entre ces nombres (Rond gagne jusqu'à 5 mais probablement pas au-delà) et le nombre de dimensions du jeu (2 en l'occurrence). Si le jeu était sur 3 dimensions, Rond pourrait probablement gagner avec des alignements plus longs.
3 dimensions c'est trop petit pour un matheux, il faut y aller sur n dimensions. Pour n=1 on voit que trivialement c'est 2, n=2 entre 5 et 7, n=3 ?
Le nombre de directions c'est 2, 8, puis 26, 80, 242, etc. C'est vachement dur de tout bloquer.
J'adore le format
Super interessant comme sujet, par contre maintenant une question m'intrigue comment on passe d'un escalier à un H avec une étape... est-ce qu'il n'yaurait pas moyen de trouver la solution aux 6 et 7 en trouvant la formule qui modifie la configuration d'une étape à l'autre?
C'était absolument génial, merci :)
Bonjour, super vidéo, à la 5ème minute avec 4 symboles d'affilé, c'est le joueur avec les croix qui va gagner. Je m'explique : le joueur 1 a joué 3 fois et a 2 cercles alignés pendant que le joueur 2 a joué 2 fois et a 2 croix alignées, c'est au joueur 2 de jouer, il joue une 3ème fois une croix alignée avec les 2 précédentes. Le joueur 1 ne peux ni gagner avec ses lignes et diagonales de 2, ni bloquer la diagonale de 3 du joueur 2, le joueur 2 gagne donc.
Bonjour et merci pour votre message. En fait, à ce moment de la vidéo les règles du jeu ont été modifiées. Les croix cherchent juste à empêcher les ronds de faire un alignement, pas à en faire un eux-même. Dans cette variante, faire un alignement n'est pas gagnant pour les croix.
@@LeMyriogon pourtant gagner en premier cest empêché les ronds de gagner non x) ?
Mais c’est incroyable
A 5:13, Croix a juste a mettre sa croix dans l'alignement et il fait echec au Rond, donc je comprends pas trop l'intérêt d'étendre
Top ! Faut que j'en parle en club. :)
Merci !
Bravo ! Merci.
Intéressant mais avec une grille en 3 dimensions ça donnerait quoi ? Il serait amusant de découvrir quelles formes en 3D permettrait d'empêcher quels alignements de n ? Et pour le morpion classique en 2D à 5 cases (n=5) cela pourrait aussi avoir des applications en sociologie des organisations : par exemple comment empêcher des regroupements de plus de 4 personnes ou des cohésions groupales entre plus de 4 voisins en plaçant le plus efficacement possible un obstacle (une personne, un mur, une route, etc). Sur une foule, ça me paraît compliqué car elle est mouvante mais sur des habitations, on peut donc empêcher que 5 habitations soient continues, bon ça donnerait des routes un peu tordues mais théoriquement c'est possible du moins si tous les voisins possèdes un terrain de même taille. Pour les embouteillages et les parkings de voitures, cela pourrait peut-être aussi avoir des applications concrètes,
Je commence tout juste la vidéo, mais n'aurait-on pas pu économiser pas mal de papier en incluant un code pour faire une rotation et/ou une symétrie axiale du plateau ?
J'admets que ça aurait été plus difficile d'inclure la partie "gagnante" pour le lecteur.
Chaud la remarque !!
La démonstration serait plus simple à faire pour démontrer que X va gagner, donc sans doute, il doit gagner !
...
Alors qu'ils indiquent juste avant que pour 5, la démonstration est ultra laborieuse.
Tu limites X à bloquer O. Mais si X veut gagner, à 5'02, il suffit d aligner une 3ème X et 0 ne peut plus gagner.
Oui j’ai vu ça direct moi, donc 0 perdu déjà aux 4 pions alignés
c'est exactement ce que j'ai pensé directement, sur 3 ronds ok il avait perdu, mais sur 4, la tout s'inverse si il met la croix comme tu le dis.
C'est parce que limiter X à bloquer O n'est pas juste une "simplification", mais un changement de règle. Le joueur O ne peut pas gagner en alignant lui-même 4 O, mais seulement en empêchant d'avoir 4 X.
Sinon, je suis d'accord, dans cet exemple là, le joueur O ne pourrait pas jouer comme ça.
exactement, mais je crois qu'elle posait comme préalable que les croix essaient juste de bloquer les ronds, pas d'arriver à en aligner 4 en premier
@Pou Let définition même du complexe de supériorité
Mais c'est trop intéressant ! Et oui, on veut voir les bonus !
Superbe, passionnant et clair !
Comment détermine-t-on le pavage en fonction du nombre d'alignements?
Je suppose qu'il suffit d'en trouver un qui marche, mais qu'il peut y en avoir d'autres.
D'ailleurs, le pavage de 8 fonctionne aussi logiquement pour le 9 (qui peut le plus peut le moins)
Pour le cas n=6, mon intuition me dirait qu'il faut chercher un pavage "éclaté". Par exemple, est-ce qu'une grille 3x3, avec une case de séparation entre chaque ligne et chaque colonne ne pourrait-elle pas faire l'affaire ? Il suffirait de bloquer tous les "alignements" de cette figure, et ça on sait déjà le faire.
J'ai hâte de voir la taille d'un livre similaire pour les dames, les échecs, puis pour le go.
mais c'est vraiment incroyable
Merci pour cette vidéo amusante. Ça donne envie de revisionner Wargames ^_^
Pourquoi le nombre a partir duquel il n'y a plus de strategie gagnante serait plutôt 6, et non 8?
Instinctivement et naivement 8 fairait plus de sens, étant donné qu'il y a 8 cases a coté de la case initiale.
Merci pour cette vidéo. Très intéressant !
Il y a certains points qui ne sont pas clair je trouve, même si X peut bloquer, finalement sur un plateau infini, personne gagne dans avec les règles énoncées.
Le gomoku, le but de jeu est qu'un des deux joueurs alignent 5 pions, ce n'est pas les mêmes règles que dans la situation que vous présentez donc pas le même jeu.
On peut dire qu’on ne joue pas avec une grille infinie, mais qui tend vers l’infini (en gros, X gagne si peu importe la taille de la grille, O ne peut pas faire son alignement)
5:11 si il met un x qui continue il a gagner le mec ça lui fait double choix nnn ?
Bonjour, à ce moment là de la vidéo les règles du jeu ont été modifiées. Les croix cherchent juste à empêcher les ronds de faire un alignement, pas à en faire un eux-même. Dans cette variante, faire un alignement n'est pas gagnant pour les croix.
00:05:12 - C'est faux. C'est seulement valable avec votre règles où "X" ne cherche pas à gagner mais seulement bloquer "O".
Dans la logique du jeu, il suffi que "X" place une autre croix à la suite (en diagonale) des 2 autres et c'est lui qui gagne.
Inattendu et très intéressant 👍
Est ce que l'on est gagnant si, et seulement si, on applique ces règles pour "empêcher" l'autre, sans soi même finaliser l'alignement gagnant ?
5:04 -> Le joueur avec les croix a gagné, il joue 2 cases au dessus de l'alignement de 2 ronds et aligne trois croix avec 2 libertés. Mais je vois bien comment Rond peut forcer le gain si il joue mieux au 3eme coup. Rond joue en bloquant l'alignement de deux croix, 2 cases au dessus de son propre rond. Croix est obligé de jouer au milieu des deux ronds pour empecher un alignement de 3 ronds avec deux libertés. Rond joue dans le prolongement de son premier alignement, mais une case plus loin. croix est obligé de jouer au milieu pour empecher l'alignement gagnant. Rond joue au dessus de croix et a un alignement de 3 à deux libertés. Si bien sur on considère que croix peut gagner en bloquant rond ou en réalisant soi-même son objectif de faire un alignement, ce qui fait que Rond ne peut pas jouer n'importe comment non plus.
Génial ! merci beaucoup pour cette vidéo ! existe t-il une théorie poussée sur le Gomoku, voir une etude sur les stratégies ?
Jai pas capté a 5:04
La situation nest elle pas en faveur des croix !? Puisquil suffit quil mette une croix dans la diagonale et hop cest gagné 😂
Bonjour, à ce moment là de la vidéo les règles du jeu ont été modifiées. Les croix cherchent juste à empêcher les ronds de faire un alignement, pas à en faire un eux-même. Dans cette variante, faire un alignement n'est pas gagnant pour les croix.
Savez-vous où je peux me procurer le même livre pour les échecs ?
Cool 👍
Super vidéo, les maths n'ont jamais fini de nous surprendre !
Si rond gagne en en alignant 7 : ne peut-on pas utiliser le modèle des H ?
On remarque que pour en aligner 7, ROND doit obligatoirement passer par un centre de H, peu importe qu'on y aille en diagonale, verticale ou horizontale. Chaque cas de figure de 7 doit forcément passer par un centre à un moment.
Ne pourrait-on pas alors ne jouer que les centres des H afin d'assurer une "victoire par blocage" à X ?
Mais si ROND joue lui-même dans un centre, alors on est embêté. :)
Sujet très intéressant !!
Au timecode 5:18 : "[...] j'ai gagné, quoi que tu fasses [...]"
Je vois pourtant deux positions gagnantes pour les X si on ne cherche pas à bloquer les O mais plutôt en cherchant à contre-attaquer:
- si les X jouent en haut à gauche de la diagonale formée par les deux X déjà présents
- si les X jouent en bas à droite de la diagonale formée par les deux X déjà présents
Dans ces deux positions, les O ne pourront pas bloquer les trois X alignées avec une liberté à chaque extrémité de la diagonale.
Comme faisait remarquer quelqu'un d'autre dans les commentaires, le but des X est de bloquer O, pas de faire pareil que O
Comme quelqu'un dans les commentaires plus a dit la c'est plus du morpion mais un dérivé
Super intéressant, super vidéo !
Est-ce que l’on peut calculer l’épaisseur du livre qui donnerait toutes les coups possible dans une partie d’échecs….. Je crois qu’il n’y aurait pas assez d’arbres sur terre…..
Le jeu des échecs n'a toujours pas été résolu malheureusement.
Les dames oui par contre !
@@AndreMalraux20341 Non, pas « malheureusement non résolu », mais au contraire heureusement non résolu, car il n’y aurait plus de plaisir ni charme à ce jeu dans lequel le hasard ne joue aucun rôle 😜.
@@mikaelderetour1933 Ha bon? Vous êtes donc capable; 15-20-30 coups à l'avance, d'élager à 100% toutes les branches menant à une défaite certaine?? Si les échecs avaient été résolu, par définition même, il n'y subsiterait plus aucuns hasard non?!
@@francoisduchene5676 C’est exactement ce que je voulais dire, l’arborescence des coups étant quasiment infinie, le livre aurait du mal à exister, au premier coups des blancs il y a 20 coups possibles, en réponses des noirs 20 coups également. Donc déjà 400 possibilités, évidemment pas toutes bonnes pour la stratégie du jeu mais elles existent, donc 400 pages, sur le principe du livre sur le morpion.
Je ne comprends pas pourquoi on arrive à faire 5 sur un plateau infini alors que sur un jeu correct on ne gagne pas dans un carré 3x3... Si on pave avec des carrés pour défendre, comment l'autre gagne ?
Une subtilité m'échappe
Ce que je vais dire ne relève que d'une hypothèse, ce n'est rien de certain: De ce que j'ai compris, un pavage satisfaisant est un pavage où, où que tu place la règle, la ligne de 5 contiendra les mêmes cases d'une des formes.
Sauf que si tu pave le plan infini en carrés
Si tu pave le plan infini en carrés, tu te rendra compte que une règle de 5 carrés ne couvrira pas toujours les mêmes cases de chaque carrés, selon ou tu te place, donc que le pavage en carrés n'est pas satisfaisant
(Par exemple, tu auras les cases A1, B2, C3 d'un carré, puis A1 et B2 d'un autre, mais si tu place la règle d'une manière, mais d'une autre façon, tu aura A2, B3 d'un carré, C1 d'un autre carré, puis encore A2 et B3 d'un autre carré)
Puisque tu n'as pas les mêmes cases selon la position de la règle, même si Croix peut techniquement bloquer les alignements de 3 dans chaque carrés, Rond pourra toujours faire son alignement de 5, même si a aucun moment, il n'y aura 3 rond dans le même carré (Tu aura par exemple 2 dans un carré, un dans un autre, puis 2 dans encore un autre)
@@yugapillon1343, merci...
Je partais du principe qu'une ligne de 5 était constituée sur deux carrés... c'est vrai en horizontal et vertical, pas forcément en diagonale
J'avais une question car si on prend le cas 9 où chaque rond est répondu avec une croix qui n'est jamais (si j'ai bien regarder) dans la même colonne que le rond venant d'être jouer. Alors ne serait-il pas possible de seulement faire une colonne d'entrée de jeu si notre adversaire suit à la lettre le schéma.
Ou alors ceci n'a pas été spécifié car cela semblait logique et que dans la pratique la réponse autre que le schéma n'est pas un problème. Je ne sais pas si ça a été clair. Vous pouvez me demander si vous n'avez pas compris et j'essaierai de me faire mieux comprendre.
Lorsque rond va vouloir faire une colonne de 9, il y aura forcément un moment où il va devoir jouer dans la colonne de droite d'un H. On pourra alors le bloquer lorsqu'il va jouer dans cette colonne
En martinique on a une version sans limite mais faut aligner 4. et c'est vrai que le jeu change vraiment. "ti points ti croix". On y joue des tout petit et Rond gagne pas forcément
Je me demande si c'est possible de participer au recherche genre si jamais on trouve des choses, est ce qu'on peut envoyer nos démonstrations, quand j'étais au collège j'ai résolu le tic tac toe 3x3 juste en essayer toute les combinaisons possibles et j'ai eu les mêmes résultats que vous pour les alignements de 3 et 4 signes sur un plateau illimité. J'ai pas chercher plus loin mais j'ai aussi résolu comme vous les débuts et j'aime trop réfléchir et me creuser la tête sur des jeux de stratégie du coup si c'est possible de participer ou d'envoyer des démonstrations j'aimerais en envoyer avec grand plaisir
Au club de go, quand on a envie de varier, on joue souvent au gomoku et au Ninuki-renju (que j'appelais par erreur Gomoku - voir Wikipedia). Ces deux variantes me semblent plus intéressantes que le morpion-5 présenté ici.
au jeu des échecs existent aussi plein de variantes dérivées: à quatre, Yalta, circulaire, tridimensionnel,.... On pratique pour se distraire
18:18 "c'est pour ça qu'on pense..." bah non au contraire ça fait plutôt penser que puisqu'on trouve pas, ça doit être des ronds.
À 5:10 il suffit de mettre la croix dans la continuité des deux première pour bloquer l'adversaire avec une brochette de trois en diagonal. La stratégie est donc pas vraiment valable...
Bonjour, à ce moment là de la vidéo les règles du jeu ont été modifiées. Les croix cherchent juste à empêcher les ronds de faire un alignement, pas à en faire un eux-même. Dans cette variante, faire un alignement n'est pas gagnant pour les croix.
Pour l'approche par pavage connexes, les tuiles ne peuvent pas contenir de droite de taille supérieure à n, où n est le nombre que l'on essaie d'aligner.
Donc le pavage est inclu dans un carré n par n. Il y a donc moins de 2^(n^2) pavage à tester. En utilisant la symétrie par rotation, on peut déjà diviser par 4 le nombre de pavage à tester.
Pour n=6, ça fait 2^36/4=2^32~=4e9, avec les ordinateurs modernes on peut facilement tout tester en quelques minutes au plus.
Pour n=7, ca demande un peu de plus de réflexion mais la contrainte d'etre un pavage va pouvoir réduire drastiquement le nombre de cas.
Pour les pavages plus généraux, on doit pouvoir montrer de façons assez simple qu'on peut se contenter de regarder localement, par la nature local de "etre aligner".
Je dis peut etre des bêtises mais c'est pas parce que on ne peut pas placer une droite de taille supérieure à n qu'on a le droit de se placer dans un pavage de n par n. Par exemple pour n=3, croix peut gagner à tous les coups dans un pavage de 3×3. Alors que rond gagne dans un pavage infini.
Sinon, on peut même encore diviser le nombre de cas à tester, puisqu'on peut faire des symétries axiales (Horizontale, diagonales et verticale). On peut encore le diviser par 4
Si on a n=6 on a aussi n=7 (bloquer 6 rond suffis à en bloquer 7)
merci a toi jeune padwan
Tellement intéressant
5:10 je ne suis pas d'accord. Dans l'hypothese ou le quadrillage est infini, les croix peuvent gagner si ils continuent leur diagonale. En effet ils auront 3 croix alignées avec 1 case libre de chaque coté
Sauf que le but des croix n'est pas d'aligner 5 croix mais de bloquer le rond
Incroyable, après le morion on veut le puissance 4 , je parle en tant que fanatique dû puissance 4
Est-ce qu'elle joue au go ? Il y a certaines expressions qu'elle utilise qui sont les mêmes qu'au jeu de go !! Je serai trop content de savoir
Et non ! Mais ma mère y a beaucoup joué...
C'est donc ça qu'on appelle la preuve par croix !
Stylé
5:15
Le joueur peut jouer en diagonale vu que la grille est ''infinie'' donc théoriquement il met une croix en diagonale, il en aligne trois et c'est imbattable pour les ronds
Bonjour, à ce moment là de la vidéo les règles du jeu ont été modifiées. Les croix cherchent juste à empêcher les ronds de faire un alignement, pas à en faire un eux-même. Dans cette variante, faire un alignement n'est pas gagnant pour les croix.
Après, est ce qu'on peut vraiment dire que X gagne? En soit c'est pas vraiment une stratégie victoire ou égalité, c'est plus une stratégie "au pire égalité". Du coup les stratégies de X montrent juste qu'à partir d'un certain nombre d'éléments à aligner en même temps, il n'y a pas de stratégie gagnante, et que la meilleure stratégie est une stratégie d'égalité, mais qui ne peut pas gagner, et donc, dans le cadre d'un jeu infini, ça signifie que si les deux joueurs ne font pas d'erreur et ne se trompent pas, les parties sont infinies, puisque sur un plateau infini, sans victoire, il n'y a pas de fin à la partie. Du coup je ne sais pas si on peut vraiment dire que X a une stratégie gagnante. En fait, ce qu'on peut voir, c'est surtout que qu'importe le nombre d'éléments à aligner, si O ne fait pas d'erreur, il ne peut pas perdre, puisque soit il gagne, soit il y a une égalité sur une partie infinie.
Est ce que ma réflexion est bonne? Ou je suis à côté de la plaque? :p
La réflexion me semble très intéressante !
Le premier point est qu'en effet, ce qu'on appelle "X gagne" dans les nouvelles règles ressemble à "ex aequo" dans les règles de base. Le problème des règles de base, dans ce cadre d'étude, c'est qu'on n'aime pas tellement les égalités. On veut un gagnant et un perdant. C'est pour ça (au moins en partie) que les règles sont modifiées.
Le deuxième point, c'est que le deuxième joueur ne pourrait pas avoir de stratégie gagnante avec les anciennes règles. Pour s'en convaincre, il suffit de supposer que c'est le cas, et voir que ça entraîne le fait de donner une stratégie gagnante pour le premier joueur :
- en tant que premier joueur, je joue un coup n'importe où, et je l'oublie (virtuellement).
- je fais comme si mon adversaire démarrait la partie, et j'applique la stratégie gagnante en tant que deuxième joueur.
L'idée, c'est que le O que j'ai placé au début ne pourra jamais me gêner (je limite les actions de mon adversaire, et si ma stratégie me disait de jouer ici, vu que c'est déjà fait, j'aurais juste à jouer autre part et à oublier (toujours virtuellement) ce coup.
Évidemment, c'est raconté un peu rapidement ici, mais c'est le même principe que pour le jeu de hex. Mickaël Launay l'a montré en vidéo il y a quelques années : "Théorie du jeu de Hex 3 (Stratégie gagnante pour le premier joueur)".
je me suis toujours dit que les jeux sans aléatoire avait des stratégies gagnantes et une fois celle-ci découverte le jeux serait "cassé" j'attends donc avec impatiente le jour où on trouvera la stratégie gagnante des échecs ! même si bonne chance si on veut l'imprimer ou la retenir
Tu risques d'attendre longtemps, environ 580 ans au mieux. En effet, le mathématicien Claude Shannon a calculé le nombre de parties d'échecs, qui est de l'ordre de 10¹²⁰. Or, en considérant que la puissance des supercalculateurs les plus puissants du monde continue d'augmenter de manière exponentielle comme ce fut le cas ces 60 dernières années (chose qui n'est pas du tout acquise en raison des probables limites physiques), on trouve que, l'année où le supercalculateur le plus puissant du monde aura la puissance suffisante pour ne mettre "que" 100 ans à faire 10¹²⁰ opérations élémentaires (précisément: opérations en virgule flottante) est... 2504. Date à laquelle il faut ajouter les 100 ans de calcul, dans le cas où le dictateur du monde de 2504 est un fan d'échec et est prêt à sacrifier 100 ans du meilleur supercalculateur et la monstrueuse quantité d'énergie nécessaire à le faire tourner juste pour résoudre les échecs, et on arrive à l'an 2600 environ.
@@lesubtil7653 intéressant mais une fois le premier super-ordinateur conçu la technologie continuera de progresser donc le temps de calcul se réduira de plus en plus
Euh..... à 5:09 elle annonce qu'elle a gagné alors que c'est faux o_O C'est au joueur croix de jouer, qui peut aligner en diago une troisième croix, avec aucun blocage nulle part, là où le joueur rond n'a qu'un "triangle" de 2 ronds alignés au max. Je suis pas allé plus loin dans la vidéo tellement ça me semble aberrant qu'elle impose son "là j'ai gagné" et qu'elle ne laisse pas le joueur croix placer son pion où il le souhaite !
Bon je m'auto-réponds, j'ai vu la vidéo en entier. Je n'avais pas compris que la règle pour le joueur croix était seulement de bloquer rond. C'est étrange d'en faire un jeu à règles asymétriques, quand même le jeu de go dans sa forme actuelle ne l'est pas.
Y a-t-il des exemples de jeu à règles asymétriques ?
Le reste de la vidéo était très intéressant ceci dit.
Pour quelle raison le livre a une erreur ? C'est juste pour que l'être humain puisse le battre ? Donc ce livre est en soi un casse-tête (qui consiste à chercher la faille unique) ?
Cool c'est comme Numberphile en français :)
9:51
Ca n'est pas la peine d'expliquer comment bloquer les quatre alignements dans le H puisque le H est contenu dans une grille de morpion 3x3 normale et qu'on sait déjà comment bloquer l'adversaire au morpion normal 😉
C'est une bonne remarque mais je pense que c'est parfois mieux de réexpliquer certaines choses plutôt que de dire " on sait déjà faire " ou quelque chose comme ça. On comprend mieux !
@@Amarylliskamta Oui c'est vrai !
Ça ne marche pas si on raisonne comme ça car si on regarde deux H qui sont "emboîtés" l'un au dessus de l'autre, leurs carrés 3*3 associés se chevauchent : ils ont deux cases communes. Donc si les ronds jouent dans l'une de ces deux cases communes, on ne peut pas répondre à la fois dans les deux carrés 3*3. On est obligé de prendre un coup de retard sur l'un de ces deux carrés et dans ce cas là, les ronds peuvent assez facilement l'emporter sur ce carré.
@@Micmaths A ce moment là de la preuve, on étudie une sorte de "jeu auxiliaire" qui se passe dans un H (un seul) et qui est très facile, plus facile que le morpion 3x3, donc on est tout de suite convaincu qu'on va gagner à coup sûr !
@@estebanziatao Effectivement, mon argument précédent n'était pas bon. En fait le problème vient du fait que les règles dans le H ne sont pas les mêmes que celles du morpion classique : X ne gagne pas s'il fait un alignement de 3, il ne gagne que s'il empêche O de faire un tel alignement.
Par exemple, si dans le H il fallait bloquer les deux barres verticales et non pas seulement celle de droite, alors X ne pourrait pas empêcher O de faire un alignement. Pourtant, on pourrait tout autant penser que c'est facile puisqu'il s'agit également d'un jeu "contenu" dans le morpion classique.
Super ,quand je pense que des gens hyper intelligent ,qui sont essoufflé juste en restant debout 4minutes ,prennent le temps de se demander qui gagnerais sur un morpion à 6 ,je suis heureux
5:15 c'est faux il a juste à continué sa ligne comme ca il en fait trois il y a une double menace est tu a perdu
Bonjour, à ce moment là de la vidéo les règles du jeu ont été modifiées. Les croix cherchent juste à empêcher les ronds de faire un alignement, pas à en faire un eux-même. Dans cette variante, faire un alignement n'est pas gagnant pour les croix.
Sur l'alignement en 4 ,
croix pouvez gagné, regarder bien.
Pourquoi ce nom degueulasse pour ce jeu ? Désolé si c'est évoqué dans la vidéo je n'écoutais pas, je jouais au puissance 4
5:16 ... "J'ai gagné"... Je crois bien que non ! car si les X décident d'aligner un troisième en diagonale au lieu de défendre, alors IL A GAGNÉ (quoi que vous fassiez) :) !
Bonjour, à ce moment là de la vidéo les règles du jeu ont été modifiées. Les croix cherchent juste à empêcher les ronds de faire un alignement, pas à en faire un eux-même. Dans cette variante, faire un alignement n'est pas gagnant pour les croix.
@@LeMyriogon Ah très bien :) Alors dans ce cas là OUI -->. "J'ai gagné" ;)
Dinguerie
Toutes ces références à Hunter x Hunter avec le Gomoku, le pavage de H, les croix etc qui font HxH, c’est beau
Ok, c'est sûr qu'avec des cases en plus , celui qui commence gagne toujours. Le but au morpion est de créer 2 lignes tout en bloquant l'adversaire. Il tente d'aligner ses 3 motif alors qu'on le double sur le fil du rasoir. Voilà tout. Si vous prenez 4 cases, il faut aligner 4 motifs, là d'accord.
5:20 il pouvait gagner si il continué avec sa diagonal
Lorsqu’on était au secondaire (Lycée du Québec), on jouait au S-O-S, une grille infinie mais il fallait utilisé le symbole de l’autre pour gagner et faire un SOS. Ça ressemble un peu à votre principe.
Pour l'alignement de 4,si les croix qui étaient en défense lors des 2 premiers tours avait attaqué au 3eme tour en plaçant en diagonal, il gagnait.
Tu parles du moment à 5:00 ? Oui, je suis d'accord ! Les croix sont complètement gagnantes !
Ce n’est pas le même jeu que le morpion. Ici, le but de X c’est de bloquer l’autre. Qu’il fasse un alignement ne sert à rien, son but c’est de bloquer l’autre
on peut montrer qu'il y a une stratégie pour empêcher le joueur 1 d'aligner 5 ronds en ligne ou en colonne sur une grille infinie
en autorisant pas les diagonales alors ?
@@alineparreau7103 exact
A la 5.17 min vous dites : j'ai gagné ! en fait, si au lieu de chercher obstinément à vous bloquer, le joueur construit son jeu, il suffit qu'il joue sur la diagonale des deux croix déjà en place et la partie est terminée: vous avez perdu...
Mais les H, ils n'existent pas. On peut décaler le pavage en H à droite, à gauche, en haut, en diagonale et ça donne un autre pavage de H. Jouer "au centre du H", ça ne veut rien dire. Ou alors, on peut dire que le premier coup est toujours au centre de ce qui va devenir un H, et on pave en H le reste en fonction de ça ?
Oui, le pavage en H n'existe que dans la tête du joueur croix qui s'en sert pour appliquer sa stratégie. Peu importe le décalage de ce pavage, il faut juste que croix décide où il le place en début de partie et n'en change plus.
A priori, le joueur rond n'a pas à être au courant de ces H, mais même s'il le savait il ne pourrait rien faire pour gagner (tout au plus il pourrait être un peu plus embêtant en visant les centres des H).
Il faudrait publier la version Go :D