Tout jeu est-il trivial ?

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

Messages : 0

Inscription : 01 mai 2016 20:09

Profil de l'utilisateur : Élève de lycée

Re: Tout jeu est-il trivial ?

Message par siro » 03 janv. 2018 17:53

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.

Messages : 0

Inscription : 01 mai 2016 20:09

Profil de l'utilisateur : Élève de lycée

Re: Tout jeu est-il trivial ?

Message par siro » 03 janv. 2018 18:04

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.

Messages : 0

Inscription : 01 mai 2016 20:09

Profil de l'utilisateur : Élève de lycée

Re: Tout jeu est-il trivial ?

Message par siro » 03 janv. 2018 18:18

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.

Messages : 0

Inscription : 01 mai 2016 20:09

Profil de l'utilisateur : Élève de lycée

Re: Tout jeu est-il trivial ?

Message par siro » 03 janv. 2018 18:18

Dattier a écrit :
03 janv. 2018 18:16
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.

Messages : 0

Inscription : 22 mai 2017 12:59

Profil de l'utilisateur : Élève de lycée

Re: Tout jeu est-il trivial ?

Message par Jarjar666 » 03 janv. 2018 21:58

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

Messages : 294

Inscription : 27 oct. 2017 10:55

Profil de l'utilisateur : Professionnel

Re: Tout jeu est-il trivial ?

Message par Hibiscus » 03 janv. 2018 22:09

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..)
Masséna (PC*) -- X15 -- Spatial.

Messages : 0

Inscription : 22 mai 2017 12:59

Profil de l'utilisateur : Élève de lycée

Re: Tout jeu est-il trivial ?

Message par Jarjar666 » 04 janv. 2018 09:18

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.

Messages : 0

Inscription : 08 janv. 2018 13:29

Profil de l'utilisateur : Élève de lycée

Re: Tout jeu est-il trivial ?

Message par theN » 08 janv. 2018 13:58

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

Messages : 0

Inscription : 01 mai 2016 20:09

Profil de l'utilisateur : Élève de lycée

Re: Tout jeu est-il trivial ?

Message par siro » 08 janv. 2018 14:20

Il n'existe pas de stratégie gagnante au morpion 3x3... partant de là...
Chaque vénérable chêne a commencé par être un modeste gland. Si on a pensé à lui pisser dessus.

Messages : 0

Inscription : 08 janv. 2018 13:29

Profil de l'utilisateur : Élève de lycée

Re: Tout jeu est-il trivial ?

Message par theN » 08 janv. 2018 14:55

siro a écrit :
08 janv. 2018 14:20
Il n'existe pas de stratégie gagnante au morpion 3x3... partant de là...
Ah mais si, je crois me rappeler que le blog XKCD la décrivait intégralement il y a quelques années : http://www.morpion.net/xkcd/
mais le morpion est un jeu à égalités, donc la stratégie gagnante n'est pas du type que j'ai définie, c'est plutôt une stratégie de non-défaite :p

Verrouillé