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 14:35

Je propose de lancer une partie de ping-pong avec une machine, pour voir. C'est un jeu, après tout.

Plus sérieusement... c'est assez étonnant pour quelqu'un de votre niveau d'être aussi vague.

Vous appelez quoi "jeu" ? Temps polynomial ne veut pas nécessairement dire trivial, si les constantes sont absurdes. Qui plus est... on a encore aucune preuve de P = NP, donc un problème NP-difficile est tout sauf trivial dans l'état actuel de nos connaissances.
Chaque vénérable chêne a commencé par être un modeste gland. Si on a pensé à lui pisser dessus.

Messages : 3901

Inscription : 04 sept. 2005 19:27

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

Re: Tout jeu est-il trivial ?

Message par JeanN » 03 janv. 2018 14:45

Bon, en gros ta question est « reste t’il un jeu pour lequel l’humain est plus fort que la machine » ?
Je dirais non maintenant que les échecs et le go sont tombés...
Professeur de maths MP Lycée Sainte-Geneviève

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 15:03

JeanN a écrit :
03 janv. 2018 14:45
Bon, en gros ta question est « reste t’il un jeu pour lequel l’humain est plus fort que la machine » ?
Je dirais non maintenant que les échecs et le go sont tombés...
Simple remarque anecdotique, le shogi (variante japonaise des échecs, avec un peu plus de combinaisons/mouvements exotiques, et où le parachutage des pièces est possible) n'est pas (sauf erreur de ma part) encore tombé.
Selon ce que tu entends par 'jeu", il existe (encore japon, pardon..) des "énigmes" solides, auxquels aucune IA n'a été plus rapide que les experts.
(Exemple, deux boules attachées à un socle, un pilier en bois au milieu, une corde qui fait un noeud étrange et passe par un arceau, et faut faire passer un anneau d'une boule à l'autre. (indescriptible avec des mots, mais jusqu'ici les IA ont un peu de problèmes et creusent des possibilités que l'intuition humaine rejette plus rapidement ; évidemment en donnant à l'ia des temps de reflexes humains)*).

*Je n'ai pas la référence du papier, mais j'ai vu ça sur les "posters" du cmap.
Masséna (PC*) -- X15 -- Spatial.

Messages : 0

Inscription : 12 mars 2016 17:59

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

Re: Tout jeu est-il trivial ?

Message par donnerwetter » 03 janv. 2018 15:12

Dattier a écrit :
03 janv. 2018 14:50
En gros, je dis existe-t-il une interprétation du jeu d'échecs (qui pourrait s'apprendre en 1 jour) et qui si elle était connue d'un novice, le rendrait impossible à battre.
Non, avoir un gros niveau aux échecs c'est avant tout une compréhension du jeu donnée seulement par beaucoup (beaucoup) d'expérience - un peu comme avoir un gros niveau en maths je dirais.

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 15:14

Dattier a écrit :
03 janv. 2018 14:42
Comme on dit poser la bonne question, c'est y répondre, donc si j'avais la bonne question j'aurais eu aussi ma réponse.

La seule précision que je peux apporter c'est que les jeux dont je parle posséde un nombre fini de coup possible à chaque étapes pour chaque joueur, et chacun des 2 joueurs (à tour de rôle) peut en choisir une librement.
Que fais-tu si le nombre de coup possibles est grand, et inaccessible à une machine ? Par exemple choisir un nombre entre 1 et le nombre de Graham ?

Faut encore préciser.

(En fait, ta question c'est est-ce qu'il existe des jeux NP-difficiles voire au dessus ?) (Et même NP-difficile c'est pas suffisant vu la conjecture en cours. :mrgreen: )

Si on reformule ta question avec toutes les limitations soulevées : oui, tous les jeux obéissant à une complexité faible sont résolus plus facilement par la machine que l'homme. Pour des raisons évidentes de définition :mrgreen:
Dernière modification par siro le 03 janv. 2018 15:16, modifié 1 fois.
Chaque vénérable chêne a commencé par être un modeste gland. Si on a pensé à lui pisser dessus.

Messages : 2470

Inscription : 27 juil. 2016 19:38

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

Re: Tout jeu est-il trivial ?

Message par U46406 » 03 janv. 2018 15:14

Hibiscus a écrit :
03 janv. 2018 15:03
le shogi
ça vient de tomber tout récemment - en décembre :
https://en.wikipedia.org/wiki/Computer_shogi
https://en.wikipedia.org/w/index.php?ti ... on=history
« Occupez-vous d’abord des choses qui sont à portée de main. Rangez votre chambre avant de sauver le monde. Ensuite, sauvez le monde. » (Ron Padgett, dans Comment devenir parfait) :mrgreen:

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 15:19

Au temps pour moi, je n'avais pas suivi.
(M'en fiche, Masayuki Toyoshima a gagné une fois. :mrgreen: :mrgreen: )
Masséna (PC*) -- X15 -- Spatial.

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 15:20

Le problème de l'IA actuelle, c'est plus si elle peut vaincre un humain sur un jeu, mais au bout de combien de temps. S'il faut 10 ans pour computer tout le paradigme et avoir les bonnes stratégies, c'est pas intéressant.
AlphaZero a bien appris et rapidement, c'est le vrai progrès de l'IA récemment, beaucoup plus que de battre les autres IA : celle-ci génère ses propres données à analyser.

L'étape suivante, la plus difficile de toute, c'est comment extraire des règles en observant un jeu. C'est un métier à part entière, qui est compartimenté selon le système étudié (économie, biologie, droit, physique, starcraft, Magic, etc), et là je doute que l'IA converge de sitôt. A fortiori avec des règles qui peuvent bouger.

Le jour où une IA saura lire l'ensemble des documents de droit ou d'économie disponible et en tirer rapidement des lois phénoménologiques puis des décisions pour favoriser sa paroisse plus vite et plus fort qu'un humain (et que leur traitement sera automatisé), là je commencerai à sérieusement me faire du soucis.
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 16:51

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.

Mais il doit vivre dans sa bulle pour penser que c'est accessible à tout le monde. :mrgreen:
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 17:24

Le monde est rempli de génies qui n'ont jamais expliqué clairement et exhaustivement (du plus possible au moins) leurs idées... alors je ne doute pas qu'il ait inventé quelque chose (mais rien ne prouve que c'est une invention nouvelle... Grothendieck a inventé l'intégrale de Lebesgue avec quelques décennies de retard, ça n'était donc pas nouveau mais inventif), mais encore faudrait-il qu'il le développe clairement, avec tout l'espace nécessaire.

Sinon c'est juste du bluff, doué ou non en maths. :mrgreen:
Chaque vénérable chêne a commencé par être un modeste gland. Si on a pensé à lui pisser dessus.

Verrouillé