Répondre à la discussion
Affichage des résultats 1 à 26 sur 26

Rubik’s cube , Echec et mathématiques



  1. #1
    king_ae

    Rubik’s cube , Echec et mathématiques

    Bonjour
    Je suis un fun du rubik’s cube (le dé de couleur on doit ranger chaque couleur dans une face)
    Et du jeu d’échec. Le problème dans le cube c’est d essayer de la faire en un temps minime En naviguant sur internent j ai trouve qu il y a un algorithme mathématique qui permet a partir de n’importe quelle position initiale de le faire en temps optimale, alors je me demande est ce qu on peut pas trouver un algorithme (stratégie de jeu) qui permet de gagner a coup sur

    -----

    Images attachées Images attachées
    Le sot ne goûte pas plus la volupté que l'homme enrhumé n'apprécie les parfums de la rose Avicene

  2. Publicité
  3. #2
    matthias

    Re : Rubik’s cube , Echec et mathématiques

    On ne connait pas d'algorithme optimal pour le Rubik's cube. On sait juste que ça existe.

  4. #3
    Sylvestre

    Re : Rubik’s cube , Echec et mathématiques

    Citation Envoyé par matthias
    On ne connait pas d'algorithme optimal pour le Rubik's cube. On sait juste que ça existe.
    Salut,

    C'est d'ailleurs la même chose pour le jeu d'échec. On sait qu'il y a une manière de jouer optimale, mais personne ne la connait.

  5. #4
    yat

    Re : Rubik’s cube , Echec et mathématiques

    Citation Envoyé par king_ae
    Bonjour
    Je suis un fun du rubik’s cube (le dé de couleur on doit ranger chaque couleur dans une face)
    Et du jeu d’échec. Le problème dans le cube c’est d essayer de la faire en un temps minime En naviguant sur internent j ai trouve qu il y a un algorithme mathématique qui permet a partir de n’importe quelle position initiale de le faire en temps optimale, alors je me demande est ce qu on peut pas trouver un algorithme (stratégie de jeu) qui permet de gagner a coup sur
    Pour le cube, on raisonne étape par étape, et à chaque étape on connait les manipulations qui permettent de passer à la suivante dans tous les cas de figure. C'est donc une stratégie qui permet de gagner à coup sur. Quant à l'algorithme optimal, c'est différent : pour chaque position initiale, il existe au moins une séquence de mouvements menant au cube fini telle qu'aucune autre séquence ne puisse y mener en moins de mouvements. A part par la force brute on ne sait pas déterminer cette séquence optimale, et elle sera différente pour chaque position de départ.

    Pour ce qui est des échecs (mais je ne sais pas bien ou tu passes du cube aux échecs dans ta phrase), c'est différent : on a un adversaire, et au bout d'un moment la partie se termine, par une victoire une défaite ou un nul (Au cube, tant qu'on n'a pas gagné on n'a pas perdu non plus, à moins de déclarer forfait).
    S'il existait une stratégie optimale qui gagne à coup sur, alors il faut penser à ce qui se passe quand l'adversaire l'utilise : Il faut bien qu'un des deux perde ou que le march soit nul, donc aucune stratégie, même optimale ne permettra jamais de gagner à tous les coups.

    La complexité des échecs n'est pas le seul problème qui rende impossible une telle stratégie : rien qu'au morpion, on se rend compte qu'il n'en existe pas : même en conaissant parfaitement le graphe du jeu, la victoire dépend d'une erreur de l'adversaire. La stratégie optimale ne permet donc que d'éviter la défaite.

  6. #5
    Sylvestre

    Re : Rubik’s cube , Echec et mathématiques

    Citation Envoyé par yat
    La complexité des échecs n'est pas le seul problème qui rende impossible une telle stratégie : rien qu'au morpion, on se rend compte qu'il n'en existe pas : même en conaissant parfaitement le graphe du jeu, la victoire dépend d'une erreur de l'adversaire. La stratégie optimale ne permet donc que d'éviter la défaite.
    C'est vrai que je n'ai pas été suffisamment précis, toutefois il y a un théorème de théorie des jeux qui dit :"Dans tout jeu à deux joueurs à information complète et dont l'issue ne peut être que le gain ou la perte, il y a une stratégie soit pour le premier joueur, soit pour le second, permettant de gagner à toutes les parties de ce jeu".
    Dans le cas, où la partie peut se terminer par un nul, le théorème s'affaiblit en disant qu'un des deux joueurs possède une stratégie lui permettant toujours soit de gagner, soit de faire nul. C'est ce qui se passe pour le cas facile du morpion.

  7. A voir en vidéo sur Futura
  8. #6
    yat

    Re : Rubik’s cube , Echec et mathématiques

    Citation Envoyé par Sylvestre
    C'est vrai que je n'ai pas été suffisamment précis, toutefois il y a un théorème de théorie des jeux qui dit :"Dans tout jeu à deux joueurs à information complète et dont l'issue ne peut être que le gain ou la perte, il y a une stratégie soit pour le premier joueur, soit pour le second, permettant de gagner à toutes les parties de ce jeu".
    Dans le cas, où la partie peut se terminer par un nul, le théorème s'affaiblit en disant qu'un des deux joueurs possède une stratégie lui permettant toujours soit de gagner, soit de faire nul. C'est ce qui se passe pour le cas facile du morpion.
    Oui, c'est ça. Et comme tu le précises bien, une stratégie permettant de gagner avec certitude n'est valable que pour le premier ou le deuxième joueur, c'était bien là ma réserve. D'ailleurs, rien ne dit que pour les échecs il n'existe pas de stratégie qui permette d'assurer la victoire aux noirs ou aux blancs. Mais bon, même dans ce cas là c'est pas vraiment du "à coup sur", parce qu'il faut d'abord déterminer qui joue avec quelles pièces.

  9. Publicité
  10. #7
    Sylvestre

    Re : Rubik’s cube , Echec et mathématiques

    Citation Envoyé par yat
    Oui, c'est ça. Et comme tu le précises bien, une stratégie permettant de gagner avec certitude n'est valable que pour le premier ou le deuxième joueur, c'était bien là ma réserve. D'ailleurs, rien ne dit que pour les échecs il n'existe pas de stratégie qui permette d'assurer la victoire aux noirs ou aux blancs. Mais bon, même dans ce cas là c'est pas vraiment du "à coup sur", parce qu'il faut d'abord déterminer qui joue avec quelles pièces.
    En tout cas, si je connaissais cette stratégie parfaite, je n'aurais même pas peur de jouer contre le champion du monde. Parce que si j'ai la bonne couleur, alors je fais nul ou je gagne et si j'ai la mauvaise, j'attends que le champion fasse une "erreur" et me mette dans une position depuis laquelle je peux gagner avec la stratégie ultime. Je ne sais pas ce que tu en penses, mais à mon avis, même les meilleurs joueurs d'échecs sont très très loin de cette stratégie ultime et "donc" il doit être très rare qu'ils ne se "trompent" pas au moins une fois dans une partie.

  11. #8
    yat

    Re : Rubik’s cube , Echec et mathématiques

    Citation Envoyé par Sylvestre
    En tout cas, si je connaissais cette stratégie parfaite, je n'aurais même pas peur de jouer contre le champion du monde. Parce que si j'ai la bonne couleur, alors je fais nul ou je gagne et si j'ai la mauvaise, j'attends que le champion fasse une "erreur" et me mette dans une position depuis laquelle je peux gagner avec la stratégie ultime. Je ne sais pas ce que tu en penses, mais à mon avis, même les meilleurs joueurs d'échecs sont très très loin de cette stratégie ultime et "donc" il doit être très rare qu'ils ne se "trompent" pas au moins une fois dans une partie.
    Tout à fait d'accord.

  12. #9
    Baygon_Jaune

    Re : Rubik’s cube , Echec et mathématiques

    En l'occurence, il a été démontré que ce sont les Blancs qui disposent de la stratégie gagnante (Nulle ou victoire).
    « L'ennemi est bête : il croit que c'est nous l'ennemi alors que c'est lui ! » Desproges

  13. #10
    yat

    Re : Rubik’s cube , Echec et mathématiques

    Citation Envoyé par Baygon_Jaune
    En l'occurence, il a été démontré que ce sont les Blancs qui disposent de la stratégie gagnante (Nulle ou victoire).
    Je n'en avais pas idée ! Ca m'intéresserait de voir comment on peut démontrer une chose pareille... t'aurais pas un lien, ou simplement un peu plus d'infos ?

  14. #11
    Sylvestre

    Re : Rubik’s cube , Echec et mathématiques

    Citation Envoyé par Baygon_Jaune
    En l'occurence, il a été démontré que ce sont les Blancs qui disposent de la stratégie gagnante (Nulle ou victoire).
    Je suis moi aussi vraiment très intéressé par cette affirmation. Y a-t-il des articles là-dessus ?

  15. #12
    matthias

    Re : Rubik’s cube , Echec et mathématiques

    Citation Envoyé par Sylvestre
    En tout cas, si je connaissais cette stratégie parfaite, je n'aurais même pas peur de jouer contre le champion du monde. Parce que si j'ai la bonne couleur, alors je fais nul ou je gagne et si j'ai la mauvaise, j'attends que le champion fasse une "erreur" et me mette dans une position depuis laquelle je peux gagner avec la stratégie ultime. Je ne sais pas ce que tu en penses, mais à mon avis, même les meilleurs joueurs d'échecs sont très très loin de cette stratégie ultime et "donc" il doit être très rare qu'ils ne se "trompent" pas au moins une fois dans une partie.
    Je pense aussi que le meilleurs joueurs sont loin d'une telle stratégie, mais jusqu'à ce qu'on la trouve, ils peuvent jouer tranquilles
    Et c'est pas pour demain. Il me semble que la démonstration de l'existence d'une stratégie gagnante (ou menant au nul) est simple, il suffit de considérer l'arbre des possibilités (donc l'équivalent du minimax en informatique) mais il est clair qu'on ne pourra jamais déterminer la stratégie par cette approche.

  16. Publicité
  17. #13
    matthias

    Re : Rubik’s cube , Echec et mathématiques

    Citation Envoyé par Baygon_Jaune
    En l'occurence, il a été démontré que ce sont les Blancs qui disposent de la stratégie gagnante (Nulle ou victoire).
    Je crois qu'il y a eu un article dans pour la science il y a quelques années. Je ne me souviens pas s'ils abordaient la démonstration.

  18. #14
    Sylvestre

    Re : Rubik’s cube , Echec et mathématiques

    Citation Envoyé par matthias
    Je pense aussi que le meilleurs joueurs sont loin d'une telle stratégie, mais jusqu'à ce qu'on la trouve, ils peuvent jouer tranquilles
    Et c'est pas pour demain. Il me semble que la démonstration de l'existence d'une stratégie gagnante (ou menant au nul) est simple, il suffit de considérer l'arbre des possibilités (donc l'équivalent du minimax en informatique) mais il est clair qu'on ne pourra jamais déterminer la stratégie par cette approche.
    Oui, cela me semble certain. Je me demande quand même à quel point les grands maîtres en sont éloignés. Souvent, il arrêtent une partie lorsque l'un des deux estime avoir perdu. Mais, dans ce cas, est-ce qu'il a vu que l'autre a une manière de gagner à tous les coups depuis cette position ou bien est-ce plutôt du feeling que cela va mal se passer pour lui ?

  19. #15
    matthias

    Re : Rubik’s cube , Echec et mathématiques

    Citation Envoyé par Sylvestre
    Oui, cela me semble certain. Je me demande quand même à quel point les grands maîtres en sont éloignés. Souvent, il arrêtent une partie lorsque l'un des deux estime avoir perdu. Mais, dans ce cas, est-ce qu'il a vu que l'autre a une manière de gagner à tous les coups depuis cette position ou bien est-ce plutôt du feeling que cela va mal se passer pour lui ?
    Ils abandonnent souvent bien avant d'arriver à une situation on on pourrait prouver qu'il y a un mat en 5 coups pour l'adversaire. C'est beau l'expérience.

  20. #16
    king_ae

    Re : Rubik’s cube , Echec et mathématiques

    Citation Envoyé par matthias
    Ils abandonnent souvent bien avant d'arriver à une situation on on pourrait prouver qu'il y a un mat en 5 coups pour l'adversaire. C'est beau l'expérience.
    ect ce que a partir d'une situation donnée on peut prouver qu'on peut mater en n coup ( je parle pas des finales evidentes 2fou et roi contre roi , tour et roi contre roi ,etc.....)
    Le sot ne goûte pas plus la volupté que l'homme enrhumé n'apprécie les parfums de la rose Avicene

  21. #17
    matthias

    Re : Rubik’s cube , Echec et mathématiques

    Citation Envoyé par king_ae
    ect ce que a partir d'une situation donnée on peut prouver qu'on peut mater en n coup ( je parle pas des finales evidentes 2fou et roi contre roi , tour et roi contre roi ,etc.....)
    Si n n'est pas trop grand oui, il suffit d'étudier tous les coups possibles.
    Je pense que tu trouveras facilement des problèmes de mat en 5 coups (plus ça devient dur) sur internet. Certains programmes d'échecs genre Chessmaster proposent aussi quelques problèmes de ce genre.

  22. #18
    Toufou

    Re : Rubik’s cube , Echec et mathématiques

    Salut tout le monde,

    Sylvestre évoque la théorie des jeux dans un de ses postes.

    Je viens de lire "Le dilemme du prisonnier: Von Neumann, la théorie des jeux et la bombe" de W.Poundstone.

    Le problème, c'est qu'à la sortie de ce livre, je me demande si la théorie des jeux ne serait pas:
    - de dire ce que tout le monde sait dans une langue que personne ne comprend
    - une abstraction sans grand intéret du fait de l'hypothèse de rationnalité et de la subjectivité de l'utilité (au sens économique)

    Qu'en pensez-vous?

  23. Publicité
  24. #19
    Sylvestre

    Re : Rubik’s cube , Echec et mathématiques

    Citation Envoyé par Toufou
    Le problème, c'est qu'à la sortie de ce livre, je me demande si la théorie des jeux ne serait pas:
    - de dire ce que tout le monde sait dans une langue que personne ne comprend
    - une abstraction sans grand intéret du fait de l'hypothèse de rationnalité et de la subjectivité de l'utilité (au sens économique)
    C'est cool que tu l'ais lu, je l'ai lu aussi. A propos du fait que la théorie des jeux est une traduction de ce que tout le monde sait dans une langue incompréhensible, je ne crois pas que cela soit vrai. C'est un peu comme de dire que la loi de la gravitation est inutile puisque tout le monde sait que les objets tombent et que l'on a pas besoin de le dire avec une équation incompréhensible.

    C'est vrai que la théorie des jeux ne permet pas de faire de prédiction, mais elle a tout de même permis de faire beaucoup de choses. Par exemple, elle a permis de développer une théorie quantitative de l'économie. On peut maintenant utiliser des équations pour décrire des systèmes économiques. C'est sûr que cela ne permet pas de prédire le futur et de gagner beaucoup d'argent, mais cela permet tout de même de se protéger un peu contre les risques.

    Sinon, je pense que la théorie des jeux ne demande qu'à être développée. Si l'hypothèse de rationnalité des acteurs économiques n'est pas satisfaite, il faut essayer de trouver ce qui cloche et d'améliorer les choses. La théorie des jeux a toutefois le mérite de donner un cadre dans lequel on peut le faire.

  25. #20
    coreff

    Re : Rubik’s cube , Echec et mathématiques

    que se passerait il si il existait réellement une stratégie pour gagner a coup sur et que les deux joueurs l'appliquent??? est ce que le joueurs ayant joué le premier (donc le blanc) va gagner ou ets ce que le fait que l'autre applique aussi cette technique va supprimer des pions indispensables au bon deroulement de la stratégie.....

    perso je ne pense pas qu'il existe de stratégie ultime en matière de jeu, que l'on peu gagner a tout les coups.... sinon un algorithme assez puissant pourrait le simuler et la machine serait imbattable.... par ocntre je pense qu'un algorithme peut en fonction du jeu de l'adversaire effectuer toutes les simulations de coup possible et du coup prévoir sa stratégie en conséquence....

  26. #21
    matthias

    Re : Rubik’s cube , Echec et mathématiques

    Citation Envoyé par coreff
    que se passerait il si il existait réellement une stratégie pour gagner a coup sur et que les deux joueurs l'appliquent??? est ce que le joueurs ayant joué le premier (donc le blanc) va gagner ou ets ce que le fait que l'autre applique aussi cette technique va supprimer des pions indispensables au bon deroulement de la stratégie.....
    Tu n'as pas du tout lire attentivement. Il existe réellement une stratégie permettant non pas de gagner à tous les coups mais de gagner ou faire nul (pour les échecs). Une telle stratégie s'applique nécessairement à l'un des deux joueurs, pas aux deux (pour les échecs il semblerait que ce soit les blancs). Si le joueur ayant la stratégie "gagnante" s'en écarte un peu, il permet à son adversaire de se l'approprier.

    Citation Envoyé par coreff
    perso je ne pense pas qu'il existe de stratégie ultime en matière de jeu, que l'on peu gagner a tout les coups.... sinon un algorithme assez puissant pourrait le simuler et la machine serait imbattable.... par ocntre je pense qu'un algorithme peut en fonction du jeu de l'adversaire effectuer toutes les simulations de coup possible et du coup prévoir sa stratégie en conséquence....
    L'algorithme existe et donc la stratégie aussi. Par contre, pour les échecs on aura jamais suffisament de puissance de calcul pour lui permettre de fonctionner.

  27. #22
    Sylvestre

    Re : Rubik’s cube , Echec et mathématiques

    Citation Envoyé par coreff
    que se passerait il si il existait réellement une stratégie pour gagner a coup sur et que les deux joueurs l'appliquent??? est ce que le joueurs ayant joué le premier (donc le blanc) va gagner ou ets ce que le fait que l'autre applique aussi cette technique va supprimer des pions indispensables au bon deroulement de la stratégie.....
    Il n'est pas possible qu'il existe une stratégie gagnante (ou nulle) pour les deux joueurs. Cela existe seulement pour un seul d'entre eux, le premier ou le second.

    perso je ne pense pas qu'il existe de stratégie ultime en matière de jeu, que l'on peu gagner a tout les coups.... sinon un algorithme assez puissant pourrait le simuler et la machine serait imbattable.... par ocntre je pense qu'un algorithme peut en fonction du jeu de l'adversaire effectuer toutes les simulations de coup possible et du coup prévoir sa stratégie en conséquence....
    Je ne comprends pas ce que tu veux dire, j'ai l'impression que tu dis d'abord qu'il n'y a pas de stratégies possibles (malgré le fait que c'est un théorème démontré sans trop de difficultés en théorie des jeux) et ensuite tu dis qu'une machine pourrait simuler tous les coups (ce qui est une stratégie) pour gagner.
    EDIT : Doublé par Matthias

  28. #23
    Matmat

    Re : Rubik’s cube , Echec et mathématiques

    Bonjour ...

    Pour les echecs ,

    la stratégie de nulle ou de gain est complétement "théorisée" à partir du moment où il reste 5 pièces ou moins sur l'échiquier .
    un ordinateur a qui on a "inculqué" toutes cette théorie ne fait aucune erreur dés qu'il y a 5 pièces ou moins .

    Il y a encore beaucoup de positions à 6 pièces dont la stratégie gagnante ( ou de nulle ) n'est pas "théorisée" , encore moins pour les positions à 7 pièces , et de moins en moins pour les positions à de plus en plus de pièces ...

    Il existe aucune stratégie gagnante ( ou de nulle ) pour la position à 32 pièces initiale .

    Les plus grand champions ont en général beaucoup de mémoire et de connaissance de ses stratégie , il savent tout de suite quand ils se sont laissés menés bien malgré eux dans une position forcément gagnante pour l'adversaire et ils abandonnent ...
    donc en fait quand ils abandonnent ils ne se basent pas sur un calcul sur n coups où il y seraient Mat en n coups ... ils se basent sur leur connaissance de toute position "théoriquement" perdante pour eux : une position où l'adversaire ne peut plus faire d'erreur puisqu'il suffit à l'adversaire de jouer sans réfléchir en appliquant la "théorie" .
    Quand il y a partie nulle par accord mutuel c'est aussi pour la meme raison : ils se trouvent dans une position où la partie nulle est "théorisée" .

  29. #24
    matthias

    Re : Rubik’s cube , Echec et mathématiques

    Citation Envoyé par Matmat
    Il existe aucune stratégie gagnante ( ou de nulle ) pour la position à 32 pièces initiale .
    Stratégie gagnante 12ème
    Moteur
    Le fait de ne pas connaître de stratégie ne signifie pas qu'elle n'existe pas.
    Coupez
    Bon, j'espère que c'était la dernière prise.

  30. Publicité
  31. #25
    Matmat

    Re : Rubik’s cube , Echec et mathématiques

    Tout à fait Matthias mais je ne parlais pas de l'existence dans l'absolu ( ca n'est d'ailleurs pas le contexte du reste du message ) .

    le contexte de mon message était où en était la théorie des echecs , autrement dit où en est-on empiriquement de la connaissance des stratégies gagnantes dans le milieu des échecs de compétition .

    je suis tout a fait d'accord sur le fait qu'il en existe une dans l'absolu , je n'ai pas eu l'intention de le contester .

  32. #26
    matthias

    Re : Rubik’s cube , Echec et mathématiques

    Citation Envoyé par Matmat
    je suis tout a fait d'accord sur le fait qu'il en existe une dans l'absolu , je n'ai pas eu l'intention de le contester .
    Disons que je me suis emporté alors
    toutes mes excuses

Discussions similaires

  1. Machine a resoudre les rubik 's cube
    Par xnico31 dans le forum Électronique
    Réponses: 10
    Dernier message: 29/01/2009, 17h20
  2. Rubik 4X4
    Par ph.auo dans le forum Mathématiques du supérieur
    Réponses: 9
    Dernier message: 21/05/2008, 14h21
  3. cube.
    Par mistic dans le forum Mathématiques du collège et du lycée
    Réponses: 4
    Dernier message: 31/01/2007, 11h56
  4. cube
    Par stein_junior dans le forum Science ludique : la science en s'amusant
    Réponses: 25
    Dernier message: 13/12/2005, 17h50