Tout jeu est-il trivial ?

Un problème, une question, un nouveau théorème ?

Modérateurs : JeanN, Michel Quercia

Avatar du membre
Dattier
Messages : 730
Enregistré le : ven. juil. 07, 2017 10:08 pm
Contact :

Re: Tout jeu est-il trivial ?

Message par Dattier » mer. janv. 03, 2018 6:47 pm

siro a écrit :
mer. janv. 03, 2018 6:24 pm
Sinon c'est juste du bluff, doué ou non en maths. :mrgreen:
CC bluff, oui je le pense aussi, c'est plus un gourou scientiste qu'autre chose, mais cela n'empêche que je suis sûr qu'il existe une manière de rendre les maths intelligibles au plus grand nombre.
Modifié en dernier par Dattier le mer. janv. 03, 2018 6:48 pm, modifié 1 fois.

Avatar du membre
Dattier
Messages : 730
Enregistré le : ven. juil. 07, 2017 10:08 pm
Contact :

Re: Tout jeu est-il trivial ?

Message par Dattier » mer. janv. 03, 2018 6:48 pm

siro a écrit :
mer. janv. 03, 2018 5:51 pm
En apprenant le langage mathématique (ce qui prend du temps, plus que dix heures) on peut rendre beaucoup de monde plus doué en maths qu'avec l'enseignement classique du collège/lycée.
Qu'appelles-tu le langage mathématique ?

Avatar du membre
siro
Messages : 2997
Enregistré le : dim. mai 01, 2016 8:09 pm
Classe : Cassandre

Re: Tout jeu est-il trivial ?

Message par siro » mer. janv. 03, 2018 6:53 pm

Bah je sais pas, c'est pas moi qui ait introduit la notion en premier, c'est toi en citant CC. :mrgreen:

Plus sérieusement, le langage c'est la structure de la pensée (c'est pas pour rien que gagner la bataille du langage est la mère de toutes les batailles dans un combat politique) et dès qu'on rajoute une nouvelle fonctionnalité au langage, on peut vite découvrir de nouvelles choses en maths. Dès que Descartes, Newton & co ont formalisé les maths un peu plus formellement, ça a amené plein de découvertes. De la même façon, dès que Bourbaki a introduit un catalogue "normalisé" de plein de notions (avec des définitions que tout le monde utilise aujourd'hui), ça a été adopté instantanément et ça a conduit à beaucoup de simplification de l'inutile et du redondant. (Paraît-il qu'avant Bourbaki, la définition de groupe c'était un peu selon l'humeur du moment. Je caricature un peu.)
Chaque vénérable chêne a commencé par être un modeste gland. Si on a pensé à lui pisser dessus.

Avatar du membre
Dattier
Messages : 730
Enregistré le : ven. juil. 07, 2017 10:08 pm
Contact :

Re: Tout jeu est-il trivial ?

Message par Dattier » mer. janv. 03, 2018 7:00 pm

siro a écrit :
mer. janv. 03, 2018 6:53 pm
Plus sérieusement, le langage c'est la structure de la pensée...
Et ce qui détermine l'évolution d'un langage c'est l'usage, la logique (ou le raisonnement en général) n'est rien d'autre qu'une modalité pour prendre des décisions de manières collectives.

Par exemple une discussion sur maths et usage

Avatar du membre
siro
Messages : 2997
Enregistré le : dim. mai 01, 2016 8:09 pm
Classe : Cassandre

Re: Tout jeu est-il trivial ?

Message par siro » mer. janv. 03, 2018 7:04 pm

Oui et non. En langage mathématique, ce sont les règles de logique qui structurent le langage (notamment la façon de nommer et définir un nouveau concept)... c'est nettement plus souple en langue naturelle (ce qui amène son lot d’ambiguïtés).
Chaque vénérable chêne a commencé par être un modeste gland. Si on a pensé à lui pisser dessus.

Avatar du membre
Dattier
Messages : 730
Enregistré le : ven. juil. 07, 2017 10:08 pm
Contact :

Re: Tout jeu est-il trivial ?

Message par Dattier » mer. janv. 03, 2018 7:12 pm

Le domaine d'étude des maths sont les jeux (qu'on appelle théorie), dans un jeu les ambïguités sont mortelles (elles peuvent entrainer la transgression d'une régle du jeu), le langage naturel dans le cadre d'un jeu devient le "langage des maths".

Avatar du membre
Dattier
Messages : 730
Enregistré le : ven. juil. 07, 2017 10:08 pm
Contact :

Re: Tout jeu est-il trivial ?

Message par Dattier » mer. janv. 03, 2018 7:16 pm

Bon bref, ce qui manque pour rendre les maths compréhensible du plus grand nombre, ce n'est pas le langage des maths, mais de donner les régles du jeu (maths).

Avatar du membre
siro
Messages : 2997
Enregistré le : dim. mai 01, 2016 8:09 pm
Classe : Cassandre

Re: Tout jeu est-il trivial ?

Message par siro » mer. janv. 03, 2018 7:18 pm

Oui mais d'une c'est pas un langage naturel au sens cognitif du terme (le cerveau EST conçu pour inférer en cas d’ambiguïté et c'est pour ça que les langages avec ambiguïté peuvent exister entre humains), de deux l’ambiguïté existe dans une preuve de maths, sauf pour les preuves totalement formelles, qui sont totalement illisibles.

Même si on peut établir des méthodes de rédaction de preuve à la fois écrits en langage (relativement) naturel ET qui permettent de lever une partie des ambiguïtés. Leslie Lamport a écrit une excellente conférence à ce sujet ("Rédiger une preuve au XXIe siècle"), dont le visionnage devrait être obligatoire pour tous les élèves au delà de la L3.
Chaque vénérable chêne a commencé par être un modeste gland. Si on a pensé à lui pisser dessus.

Avatar du membre
siro
Messages : 2997
Enregistré le : dim. mai 01, 2016 8:09 pm
Classe : Cassandre

Re: Tout jeu est-il trivial ?

Message par siro » mer. janv. 03, 2018 7:18 pm

Dattier a écrit :
mer. janv. 03, 2018 7:16 pm
Bon bref, ce qui manque pour rendre les maths compréhensible du plus grand nombre, ce n'est pas le langage des maths, mais de donner les régles du jeu (maths).
Vrai.

Le langage n'en est qu'une conséquence.
Chaque vénérable chêne a commencé par être un modeste gland. Si on a pensé à lui pisser dessus.

Avatar du membre
Dattier
Messages : 730
Enregistré le : ven. juil. 07, 2017 10:08 pm
Contact :

Re: Tout jeu est-il trivial ?

Message par Dattier » mer. janv. 03, 2018 8:13 pm

siro a écrit :
mer. janv. 03, 2018 7:18 pm
Leslie Lamport a écrit une excellente conférence à ce sujet ("Rédiger une preuve au XXIe siècle"), dont le visionnage devrait être obligatoire pour tous les élèves au delà de la L3.
Merci pour la ref : https://www.youtube.com/watch?v=k-i7y0R_-KE

Jarjar666
Messages : 52
Enregistré le : lun. mai 22, 2017 12:59 pm

Re: Tout jeu est-il trivial ?

Message par Jarjar666 » mer. janv. 03, 2018 10:58 pm

Le coup de alpha zéro qui bats stockfish est discutable.

Avatar du membre
Hibiscus
Messages : 1225
Enregistré le : ven. oct. 27, 2017 10:55 am
Classe : Bac a fleurs

Re: Tout jeu est-il trivial ?

Message par Hibiscus » mer. janv. 03, 2018 11:09 pm

A ce moment-là, dire qu'un truc du genre
GPS Team Cluster 797 ordinateurs 804 processeurs (3224 coeurs) 3272 GB de RAM arrive à battre un humain au Shogi (6victoires 1défaite),
C'est aussi (très) discutable à mes yeux.. (Quoique je n'ai aucune idée de la valeur de la réflexion humaine en termes informatiques..)
Lycée Masséna (Pcsi-PC*)
École polytechnique (X2015)
Université de Tokyo/Tohoku - Astrophysique

Jarjar666
Messages : 52
Enregistré le : lun. mai 22, 2017 12:59 pm

Re: Tout jeu est-il trivial ?

Message par Jarjar666 » jeu. janv. 04, 2018 10:18 am

Non ce que je dis c'est que stockfish n'avait pas ses tables, et que c'était une vielle version sur un vieux pc.

theN
Messages : 4
Enregistré le : lun. janv. 08, 2018 2:29 pm

Re: Tout jeu est-il trivial ?

Message par theN » lun. janv. 08, 2018 2:58 pm

Eh bien... le réponse à ta question, pour faire court, est oui *réponse soumises à condition* *l'auteur n'est pas responsable d'hypothèses tronquées* !

Et pour faire long (moyen plutôt :D ), je vais préciser ce que j'entends pas trouver un jeu non trivial :
je vais considérer un jeu à deux joueurs,au coup par coup, sans hasard aucun, pour lesquels les deux joueurs on toutes les informations sur la partie en cours, pour lequel à chaque étape de jeu il y an une nombre fini de coups jouables, qui peut être prouvé comme se terminant toujours en un nombre fini de coups, et dont il y a au final un gagnant et un perdant.

On peut montrer (sans aucune théorique autre que celle de ce qu'est une démonstration par l'absurde) qu'un tel jeu admet un stratégie gagnante pour un des deux joueurs (au moins), et par stratégie gagnant j'entends une liste de réponses pour le joueur qui lui permettent de -quel que soit la suite de coups de son adversaire - d'atteindre la victoire, sans faire l'hypothèse que l'adversaire joue parfaitement. je te laisse réfléchir à la preuve, cela devrai prendre entre dix minutes et une heure je pense, selon si tu pense aux bons objets. (perso, c'était plutôt une heure, mais bon... je suis pas très rapide d'habitude :lol: )

maintenant, le jeu de hex est un tel jeu (facile de vérifier les hypothèses) (je veux juste te donner un exemple d'un tel jeu, mais il y en a en fait plein d'autres que tu connais déja). Et on va regarder le problème algorithmique de résoudre un tel jeu, c'est à dire de trouver la(une) stratégie gagnante. Et bien, on connait (ou plutôt, on sait demander à nos ordinateur de trouver une telle stratégie rapidement) pour des grilles de jeu de 1*1 à 13*13. Mais au dessus, nos ordinateurs sont trop lents pour donner une réponse en un temps réaliste (par réaliste, j'entends moins d'un an de calcul continu, je suis assez large :p). Pourquoi si tôt ? Eh bien c'est parce que pour avoir une stratégie gagnante il faut à priori tester toutes les parties possibles (je te laisse montrer que dans le cas de ce jeu, des factorielles vont apparaître dans le nombre de parties possibles pour un plateau de taille n*n). En fait, il existe des algorithmes plus rapides même pour une recherche de stratégie parfaite, dont l'idée grossière est de regrouper les positions qui se ressemblent (en gros qui sont équivalentes) pour toutes les traiter d'un coup plutôt que de refaire tout le travail plein de fois...

Tu peux remarquer que pour plein de jeux célèbre on peut augmenter arbitrairement la taille du plateau de jeu (dames, hex, go). Et bien voilà la fin de ma définition d'un jeu "difficile" : un jeu qui vérifie les hypothèses susdites, et qui est à plateau extensible, est dit difficile s'il n'existe pas d'algorithme permettant de trouver une stratégie optimale avec une complexité polynomiale.

Ces définitions étant posées, je comprends ta question comme : existe t'il un tel jeu ?

la réponse est oui, c'est un théorème qui (merci Wikipedia : https://fr.wikipedia.org/wiki/EXPTIME) à été prouvé par Chandra Stockmeyer (et je ne te laisse pas la preuve en exercice, je suis gentil :lol: )

Et encore mieux : le go et les échecs en font (via une généralisation aux jeu à égalités) en font partie !!

Bon j'avoue j'ai triché un peu, je me suis limité aux recherches de stratégies parfaites pour un jeu... Et selon cette définition, le jeu d'échec 8*8 ou de go 11*11 n'ont pas été résolus non plus... mais la machine peut battre l'homme dessus !! C'est bien que cette définition n'est pas parfaite, elle demande un résultat parfait là ou un minimum local comme celui trouvé par AlphaZero sont déjà très bien !! Si on veut répondre à ta question, il faut réfléchir un peu plus que moi, feignant que je suis :D
Tu peut considérer que je n'ai traité qu'un cas particulier de ta question :D

Avatar du membre
Dattier
Messages : 730
Enregistré le : ven. juil. 07, 2017 10:08 pm
Contact :

Re: Tout jeu est-il trivial ?

Message par Dattier » lun. janv. 08, 2018 3:14 pm

Salut,

theN=CC ?

Cordialement.

Verrouillé

Qui est en ligne

Utilisateurs parcourant ce forum : J64_ThEr et 7 invités