règles et programmation

[invite3f83ebdf]

Bonjour,
Je suis actuellement en première année en licence de mathématiques , le domaine de l'informatique me fascine et je viens proposer une reflexion personnelle afin que vous puissiez juger du domaine précis dans lequel la développer. Je considère la situation suivante: une partie d'échecs a lieu entre deux personnes, un observateur extérieur qui ignore le jeu est chargé d'en déduire les règles. Intuitivement, il semble évident qu'au bout d'un nombre n de parties cet observateur sera capable d'en déduire l'intégralité des règles. Ce processus peut-il être reproduit par un programme informatique avec succès ? Si oui, quelles sont les grandes lignes qui régissent le fonctionnement d'une telle démarche ? Enfin, quel est le domaine précis qui traite de ce type de situation ?

Je vous remercie d'avance pour toutes informations sur ce sujet.
-----

[pm42]

C'est ce qu'on fait en apprentissage automatique. Le deep learning a justement l'inconvénient de ne pas être capable de décrire les règles qu'il construit mais d'autres techniques fonctionnent.
La, je suis sur une tablette donc je ne peux pas chercher les références mais ça se trouve. On en parlait dans un Pour La Science récent je crois.

[invite3f83ebdf]

Je te remercie, qu'est-ce que tu entends par cet inconvénient, et pourrais-tu me l'expliquer avec mon exemple du jeu d'échecs ?

[azad]

Attention à ce qui est intuitif.
Aux échecs, si n parties peuvent sembler nécessaires pour en déduire toutes les règles, il peut se faire que n devienne très grand. Vraiment très grand !
Je pense à la limite qui fixe à trois le nombre de fois où la disposition des pièces peut être répétée à l’identique.
A la règle des 50 coups, pas évidente à détecter si aucun pion n’a bougé.
Le roque, lui même peut poser un problème à un observateur non averti.
La prise en passant aussi.
La règle de pièce touchée, pièce à jouer (sauf impossibilité) ce qui peut être accidentel, devrait être expliquée à l’observateur pour qu’il comprenne le mouvement forcé.
Bref n peut-être égal à quelques milliers assez facilement.

[A voir en vidéo sur Futura]

[pm42]

Je te remercie, qu'est-ce que tu entends par cet inconvénient, et pourrais-tu me l'expliquer avec mon exemple du jeu d'échecs ?

Si tu fais apprendre les échecs en faisant observer plein de parties à un réseau de neurones (ce qui n'est pas forcément faisable aujourd'hui, j'ai un gros doute), tu vas avoir un programme à la fin qui va savoir jouer et qui respectera les règles.
Mais ce sera codé "dans le réseau" et tu auras un "idiot savant" : en gros, tu ne pourras pas extraire les règles sous forme de phrases du genre "j'ai le droit de roquer si mon roi et ma tour n'ont pas bougé, qu'il n'y a aucune pièce entre les 2 et que mon roi ne passe pas par une case en échec".
Ce sera une boite noire.

Si tu veux apprendre à une IA certaines choses, ce n'est pas grave qu'elle fonctionne comme ça. Par exemple, pour bien conduire ou pour simuler une conversation, tu n'as pas besoin d'expliquer tout ce que tu fais avec des règles. C'est même éventuellement impossible.

Par contre, si tu veux une IA qui prend des décisions pour une banque, une assurance voire dans le domaine de la justice, ce n'est pas acceptable. Tu as besoin quelle soit capable de justifier ce qu'elle fait donc de donner les règles qu'elle a déduite de la masse de données qu'elle a avalée pour apprendre.
Donc il y a de la recherche sur ces sujets qui permettraient de faire ce que tu veux mais comme je disais, je pense qu'on en est loin mais je peux me tromper, ma connaissance du sujet est limitée.

[JPL]

Par contre c’est un gros problème si c’est utilisé pour le diagnostic médical car cette IA ne peut pas justifier les critères utilisés ni expliquer les règles.

[invite9dc7b526]

En observant des joueurs on voit facilement quels coups sont permis mais pas de façon évidente quels coups sont interdits. Pour deviner quels coups sont interdits il faut supposer que les joueurs sont parfaits (ils ne ratent jamais un coup qui leur donnerait un avantage). Mais même si cette hypothèse est à peu près correcte, il faut être capable d'analyser la situation des deux camps.

[pm42]

Par contre c’est un gros problème si c’est utilisé pour le diagnostic médical car cette IA ne peut pas justifier les critères utilisés ni expliquer les règles.

Exactement. Comme tous les sujets où une décision doit pouvoir être expliquée à des humains. Et là, c'est critique.

En observant des joueurs on voit facilement quels coups sont permis mais pas de façon évidente quels coups sont interdits. Pour deviner quels coups sont interdits il faut supposer que les joueurs sont parfaits (ils ne ratent jamais un coup qui leur donnerait un avantage).

J'ai du mal à voir le lien entre "coup autorisé/interdit" qui ne relève que des règles et que les débutants apprennent vite vs "coup qui donne un avantage et joueur parfait".

[invite9dc7b526]

ben si par exemple les blancs ont un pion en D3 et les noirs la reine en F5, si c'est aux blancs de jouer et que le pion ne prend pas la reine tu peux en inférer que le pion peut prendre une pièce sur la case adjacente en diagonale (si tu le sais déjà) mais pas à deux cases de distance, parce que si c'était possible et si les blancs jouent bien ils devraient prendre la reine, ce qui donne un gros avantage. Ce n'est pas une certitude mais c'est le propre de l'inférence que de ne pas être certaine. Si en revanche blancs joue comme un pied tu ne peux rien conclure.

[pm42]

Si en revanche blancs joue comme un pied tu ne peux rien conclure.

Donc tu prends 1 exemple sur 1 partie et tu en conclus quelque chose sur un apprentissage qui en nécessite des milliers ?
Et entre "si quelqu'un joue comme un pied" et "les joueurs doivent jouer parfaitement", il y a un univers...

C'est le propre des apprentissages sur des grosses bases d'exemples de finir par ignorer les erreurs et de ne pas avoir besoin de perfection.

[invite9dc7b526]

ce que je voulais dire c'est que les règles en gros c'est la liste des coups permis et la liste des coups interdits (plus la position initiale et quelques règles sur la fin de partie). Les coups permis on les connaît après avoir observé un certain nombre de parties. Les coups interdits on ne les voit pas bien sûr. Si un coup n'est pas joué on ne sait pas de façon simple si c'est parce qu'il est interdit ou parce que c'est un mauvais coup. Donc si un coup apporterait un avantage évident mais n'est pas joué on peut inférer qu'il est interdit, à la condition de supposer que le joueur joue bien (en tout cas pas trop mal).

[pm42]

Donc si un coup apporterait un avantage évident mais n'est pas joué on peut inférer qu'il est interdit

Encore une fois, cela n'arrivera pas sur une base de milliers de parties...

[invite9dc7b526]

qu'est-ce qui n'arrivera pas? et quid si on ne dispose pas de milliers de parties?

[pm42]

qu'est-ce qui n'arrivera pas?

Ce dont on parle depuis plusieurs messages.

et quid si on ne dispose pas de milliers de parties?

On ne sait pas faire d'apprentissage automatique dans ce cas.

[invite9dc7b526]

On ne sait pas faire d'apprentissage automatique dans ce cas.

justement ça pourrait être intéressant d'élaborer une heuristique pour le cas où on n'a pas beaucoup de données.

[pm42]

justement ça pourrait être intéressant d'élaborer une heuristique pour le cas où on n'a pas beaucoup de données.

Oui, je pense que tu devrais t'y mettre.

[bisou10]

justement ça pourrait être intéressant d'élaborer une heuristique pour le cas où on n'a pas beaucoup de données.

Au contraire, ca n'a de mon point de vue aucune valeur.
Il faut aussi que les joueurs soient parfait et connaissent toutes les régles, même les plus obscures (donc les appliquent). Mais comme le souligne pm42, si le nombre de parties observé est trés grand, ce n'est pas un souci.

[invite9dc7b526]

Au contraire, ca n'a de mon point de vue aucune valeur.

c'est peut-être parce que tu penses au jeu d'échec (pour lequel la question n'a aucun intérêt pratique puisqu'il suffit de lire un livre sur les échecs). Je pensais de mon côté à la situation générale de devoir deviner les règles que suivent des agents quelconques. Supposons par exemple qu'on ait à programmer un robot qui aura à interagir avec d'autres robots. Ces autres robots suivent certaines règles qui sont inconnues et notre robot ne peut pas attendre d'avoir accumulé des milliers d'observations des actions desdits robots avant d'agir lui-même.

[pm42]

Le vrai problème est que comme d'habitude, les raisonnements de forum de quelqu'un qui ne connaît rien au sujet n'ont aucune valeur voire sont "un peu à l'ouest".

[bisou10]

c'est peut-être parce que tu penses au jeu d'échec (pour lequel la question n'a aucun intérêt pratique puisqu'il suffit de lire un livre sur les échecs). Je pensais de mon côté à la situation générale de devoir deviner les règles que suivent des agents quelconques. Supposons par exemple qu'on ait à programmer un robot qui aura à interagir avec d'autres robots. Ces autres robots suivent certaines règles qui sont inconnues et notre robot ne peut pas attendre d'avoir accumulé des milliers d'observations des actions desdits robots avant d'agir lui-même.

J'ai des doutes sur la capacité d'arriver à un résultat fiable - voire un résultat tout court, ou un résultat à l'opposé de celui attendu. A mon avis ce cas n'est pas vraiment un principe de déduction par l'observation pour lequel la fiabilité du résultat sera sans doute directement liée au nombre d'observations.

[Patrick_91]

Hum, a mon humble avis, il ne faut pas confondre les "règles" de jeux et la stratégie pour gagner, cela n'a rien a voir.
Si on programme un jeu d’échec, on colle la suite de règles de jeux dans un tableau figé ainsi que le positionnement initial autorisé de chaque pièce et on vérifie chaque "mouvement" par rapport à cette table et "basta" ...
La on contrôle la bonne application des regles du jeux ...
Le coté heuristique ne peut concerner que le jeux et les stratégies de joueurs pour gagner ... il y en a une infinité mais je peux comprendre éventuellement
la tentative de classement et de reconnaissance entre différents types de joueurs (comportement et stratégies) afin d'optimiser pour gagner ... mais c'est un vaste programme ...

[invite9dc7b526]

Le vrai problème est que comme d'habitude, les raisonnements de forum de quelqu'un qui ne connaît rien au sujet n'ont aucune valeur voire sont "un peu à l'ouest".

il est certain que quand on se contente de critiquer les autres on ne risque pas trop de se fourvoyer.

je continue à penser que la question d'inférer les règles d'un jeu à l'aide d'informations limitées peut avoir des applications dans la vraie vie.

[Patrick_91]

Hello,

Les règles doivent être les mêmes pour les grands joueurs ou pour les novices , donc elles doivent être décrites comme base de travail sans quoi plus rien ne va. Le jeux d’échecs est précis sur ce point. Le moteur de jeux développé de façon heuristique sera certainement intéressant si c'est possible. Mais je ne vois pas ce que les regles de jeux viennent faire ici.
A plus

[pm42]

il est certain que quand on se contente de critiquer les autres on ne risque pas trop de se fourvoyer.
.

J'ai répondu factuellement à la demande du primo-posteur et à plusieurs de tes interventions. Cette remarque fait juste honneur à ton peudo.

je continue à penser que la question d'inférer les règles d'un jeu à l'aide d'informations limitées peut avoir des applications dans la vraie vie.

yaqafocon est le discours classique des gens qui ne connaissent pas le sujet, ne veulent pas apprendre mais donnent leur avis quand même.

[JPL]

Stop, merci !

[invite6c250b59]

une partie d'échecs a lieu entre deux personnes, un observateur extérieur qui ignore le jeu est chargé d'en déduire les règles. Intuitivement, il semble évident qu'au bout d'un nombre n de parties cet observateur sera capable d'en déduire l'intégralité des règles. Ce processus peut-il être reproduit par un programme informatique avec succès ? Si oui, quelles sont les grandes lignes qui régissent le fonctionnement d'une telle démarche ? Enfin, quel est le domaine précis qui traite de ce type de situation ?

Une première façon serait de copier les méthodes de description automatique d'images. Une autre serait de partir d'un réseau qui joue aux échec, puis d'explorer comment il construit sa décision via des méthodes oniriques (inceptionnistes). Une dernière serait d'utiliser une variante du reinforcement learning avec deux agents: un qui s’entraîne à jouer en self-play selon des règles choisies au hasard, et un qui s’entraîne à deviner les règles en regardant le premier jouer.

Dans tous les cas, azad a raison que le résultat ne sera possiblement pas parfait si on considère le problème *en toute généralité*. Exemple: si le réseau trouve comme règle 'chaque joueur joue deux coups de suite, une fois avec les noirs, une fois avec les blancs, et le vainqueur gagne entre 1 et 18 points selon la qualité de sa performance avec la couleur de son adversaire'... c'est une règle qui est possiblement aussi valide pour décrire les parties que la 'vrai' règle suivie et donc qu'il sera impossible d'écarter quelle que soit l'approche utilisée. Par contre si on laisse tomber le *en toute généralité*, alors on peut éventuellement avoir une solution unique en ajoutant des informations supplémentaires telles que: les intelligences qui ont créé le jeu préfèrent le combat à la coopération, et les règles simples aux règles compliquées, etc...

et quid si on ne dispose pas de milliers de parties?

Malgré l'accueil reçu c'est une question profonde. Sous une autre forme: que font les humains pour ne pas avoir besoin de [centaines de] milliers de parties pour apprendre à jouer aux échecs, ou apprendre à parler, ou apprendre à analyser une image?

[pm42]

Pour les échecs nous apprenons les règles directement pas par observation. Ce n'était pas la question ici.
Pour le langage et les images, nous avons un réseau de neurones en partie précablé par l'évolution. Et malgré cela cela nous prend pas mal de temps pour maîtriser les 2 tâches.
Pour la reconnaissance d'images un flux continu pendant des mois et pour le langage idem pendant un certain temps.

Si on voit les choses comme ça on pourrait argumenter que le cerveau humain a besoin d'un nombre élévé exemples.

[invite6c250b59]

https://www.youtube.com/watch?v=ersyQKAIMPI

[invite936c567e]

Bonjour,

Je considère la situation suivante: une partie d'échecs a lieu entre deux personnes, un observateur extérieur qui ignore le jeu est chargé d'en déduire les règles. Intuitivement, il semble évident qu'au bout d'un nombre n de parties cet observateur sera capable d'en déduire l'intégralité des règles.

Sans vouloir relancer la polémique, ce qui paraît intuitif pour un esprit mathématique, c'est qu'avec un nombre infini de parties on devrait pouvoir déduire l'intégralité des règles.

Le problème, c'est que dans la pratique, il existe aussi une infinité d'ensembles finis de parties qui ne permettent pas de déduire l'intégralité de ces règles. Jamais un observateur (sur un temps fini) qui ignore les règles ne peut avoir la certitude qu'il dispose de toutes les informations nécessaires à la détermination de l'ensemble de ces règles.

En d'autres termes, le but ne peut être atteint qu'avec de la chance, ou bien en trichant, en fournissant à l'observateur un ensemble de parties dont on sait qu'il lui permettra d'aboutir au résultat escompté.


La problématique n'est pas très différente de celle des sciences physiques, qui s'évertuent à découvrir les lois qui régissent notre monde en partant de son observation. Les règles qui sont déduites restent des hypothèses, qui peuvent sembler « bien marcher » à un moment donné, mais être par la suite remises en cause et rejetées ou affinées.

Ce processus peut-il être reproduit par un programme informatique avec succès ? Si oui, quelles sont les grandes lignes qui régissent le fonctionnement d'une telle démarche ?

Le processus peut être reproduit, avec un succès très relatif concernant la complétude des règles.

Les démarches peuvent être très différentes selon la façon dont on souhaite que le résultat s'exprime. Par exemple, on pourra demander à un réseau neuronal de reproduire le comportement d'un joueur d'échec (mais sans pouvoir l'expliquer), ou à un système d'analyse logique de produire sous une forme littéraire une liste des règles applicables (mais cela risque de vite devenir imbuvable).

La première question à se poser est donc : c'est pour faire quoi ?

[Patrick_91]

Bonsoir,

Je joue modestement aux échecs, j'ai une question:
Qu’appelez vous "règles" ?? et quel est l’intérêt de découvrir les règles du jeux en observant des parties ?? (meme en vue de programmation) à quoi cela pourrait il servir ?

A plus