Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 03-01-2018 14:22:58

Dattier
Banni(e)
Inscription : 10-09-2017
Messages : 533
Site Web

Tout jeu est-il trivial ?

Salut,

Quand on voit l'aisance avec laquelle Alpha-Zero, avec une puissance de calcul moindre que son adversaire Stockfish, a gagné aux échecs, on peut se poser la question suivante :

tout jeu à 2 joueurs est-il triviale ?

C'est à dire tout jeu posséde-t-il une interprétation qui rende le jeu équivalent à un jeu trivial, c'est à dire dont les positions perdantes sont calculables en un temps polynomiale ?

Y-a-t-il un argument décisive (que je ne connais pas) et qui permette de répondre par la négative à cette question ?

Cordialement.


Raisonnement Exact : A est exacte si avec 10 exemples et pas de contre-exemples connus des concernés

Hors ligne

#2 03-01-2018 14:44:37

Yassine
Membre
Inscription : 09-04-2013
Messages : 1 090

Re : Tout jeu est-il trivial ?

Un article (en anglais) sur Wikipedia qui traite du sujet de la détermination des jeux.
Il n'y est cependant pas question de temps de résolution mais d'existence d'une stratégie gagnante.


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

#3 03-01-2018 14:54:24

Dattier
Banni(e)
Inscription : 10-09-2017
Messages : 533
Site Web

Re : Tout jeu est-il trivial ?

Je reformule ma question dans un cas précis :

Existe-t-il une interprétation du jeu d'échecs (qui pourrait s'apprendre en 1 jour) et qui si elle serait connue d'un novice, le rendrait impossible à battre ?

Si une telle chose n'existe pas, j'aimerais en savoir la justification.


Raisonnement Exact : A est exacte si avec 10 exemples et pas de contre-exemples connus des concernés

Hors ligne

#4 03-01-2018 15:32:28

tibo
Membre expert
Inscription : 23-01-2008
Messages : 1 097

Re : Tout jeu est-il trivial ?

Bonjour,

Le fait qu'un ordinateur soit capable de battre un humain ne signifie pas que le jeu est résolu (ie existence d'une stratégie gagnante).

En fait ce sont deux domaines des mathématiques différents.
Qu'un ordinateur batte un humain relève de l'intelligence artificielle.
Résoudre un jeu relève quand à lui de la théorie des jeux.
La frontière est perméable et ce sont deux domaines de recherche auxquels beaucoup de monde s'intéresse. Il y a des avancés presque chaque jour (surtout en IA), mais il faut être honnête, il reste encore beaucoup de questions auxquelles personne ne sait répondre (par exemple pour citer l'un des plus connu, P=NP est un des problèmes du millénaire encore non résolus).

À ma connaissance, les échecs n'est pas encore un jeu dont il existe une stratégie gagnante connue.
Idem pour le jeu de go. Un article d'il y a quelques mois a fait les gros titres, disant qu'un ordinateur battait pour la première fois un être humain au go. Depuis, beaucoup de progrès ont été fait et plus aucun humain n'est capable de battre un ordinateur à ce jeu. Mais on est très loin de résoudre le jeu de go !

Il y a plein de jeux dont on ne sait même pas si une stratégie gagnante existe !

Et même quand on trouve une stratégie gagnante à un jeu, elle est parfois inaccessible au cerveau humain.
Par exemple le puissance 4 est un jeu résolu. Mais il est très difficile pour un humain de l'apprendre (voire impossible).
Un autre exemple, le poker a été résolu il y a 2 ans sous des conditions encore très restrictives (Heads up Limit Hold'em), mais cette stratégie gagnante tient sur 11 Téra octets...

Bref, à ce jour personne ne peut répondre à ta question.
Existe-t-il une stratégie gagnante aux échec?
Intuitivement, j'ai envie de dire qu'une stratégie menant à pat existe. Menant à mat, j'en doute.
Et même si elle existe, il y a fort à parier qu'elle soit inapplicable par un être humain.

Dernière modification par tibo (03-01-2018 15:40:06)


A quoi sert une hyperbole?
----- A boire de l'hypersoupe pardi !

Hors ligne

#5 03-01-2018 16:13:02

Dattier
Banni(e)
Inscription : 10-09-2017
Messages : 533
Site Web

Re : Tout jeu est-il trivial ?

Ce qui me pousse à le penser :

1/Le fait qu'Alpha-Zéro avec une puissance de calcul moindre, batte un logiciel gourmand en calcul.

2/J'ai connu sur les-mathematiques.net, un type (que l'on prend là-bas pour une pointure) qui se ventait de pouvoir rendre bon en math n'importe qui et en 10 heures en lui apprenant ce qu'il appelle le langage mathématique.

C'est Christophe C


Raisonnement Exact : A est exacte si avec 10 exemples et pas de contre-exemples connus des concernés

Hors ligne

#6 03-01-2018 16:50:09

Yassine
Membre
Inscription : 09-04-2013
Messages : 1 090

Re : Tout jeu est-il trivial ?

@tibo :
voir ici une discussion sur le cas particulier des échecs.
Comme il l'indique, il y a une différence entre savoir si théoriquement, il existe une stratégie gagnante, et le fait d'avoir résolu le jeu (avoir trouvé la dite stratégie).
Pour les jeux finis (cas des échecs), il y a un théorème d'existence. Il est cependant de peu d'utilité pour trouver la stratégie.

Pour la cas d'Alpha-Zero, la discussion ne relève pas des mathématiques mais de l'informatique.
Alpha-Zero utilise des techniques de Monte-Carlo pour explorer l'arbre des parties, ce qui le rend moins sensible à l'"effet d'horizon" qui affecte Stockfish. Le Monte-Carlo implique qu'a un moment, le logiciel va explorer au "hasard" certaines branches, c'est à la fois sa force (informatique) et sa faiblesse (mathématique). Cf sur cet article sur Arxiv pour une discussion technique de la performance d'Alpha-Zero


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

Pied de page des forums