Home

1 Une maladie foudroyante pour l`un, un accident stupide pour l

1. 0 52 sx 0 48 ma tre 0 25 non ma tre 0 25 a 50 x Ka As RAM 0 27 0 PZ e4 Inon maitre maitre Non maitre 0 2 4 75 A vou AS Contrat Chute du As r ussi contrat se 0 92 6 0 89 0 89 0 55 45 Contrat 92 ma tre INon ma tre TEUSSI non ma tre aoe l AS 0 25 y Na Contrat Chute dul 4 94 OU amp r ussi contrat Ase Ase AS X 0 92 0 92 rer LK 0 24 vo ror Ase Contrat Ase 0 55 45 EA 45 r ussi ma tre non maitre 0 24 4S 6 0 24 0 76 mag Fa a ma tre Non ma tre ma tre Non ma tre ma tre non ma tre ma tre non ma tre Contrat Chute du Contrat J r ussi F4 contrat r ussi g Contrat Chute dul Contrat Chute du Chute du Contrat Chute du Contrat r ussi contrat r ussi contrat contrat Tussi contrat sa 0 92 0 92 Figure 1 simulation du raisonnement avec SYMOR 5 Conclusion Les id es donn es dans cet article sont une premi re tape pour allier les avantages des m thodes du type syst me expert par l utilisation de connaissances d claratives et ceux offerts par les algorithmes de recherches arborescentes Elles se r sument dans l utilisation de connaissances plus ou moins abstraites l
2. for i l i lt CoupsPossibles O0O 1 i JoueCoup Position CoupsPossibles i valeur Quiescence profondeur 1 beta alpha DejoueCoup if valeur gt Best Best valeur return Best 2 5 Le coup nul Un coup nul null move consiste changer le tour de jeu ce qui est quivalent pour un joueur a passer son tour Le coup nul est un coup l gal au jeu de Go o un joueur peut passer c est m me de cette fa on que la fin de partie est d cid e lorsque les deux joueurs passent cons cutivement Aux Echecs par contre ce n est pas un coup l gal et il existe un petit nombre de positions pour lesquelles cela pourrait tre utile Ce sont les positions de Zugzwang le premier joueur qui joue dans une position de ce type a perdu L heuristique du coup nul permet de d tecter des coups inutiles et de gagner du temps en ne d veloppant pas des arborescences inutiles On suppose que jouer le coup am liore la position pas de Zugzwang Toutefois cette heuristique peut parfois masquer une arborescence qui si elle avait t explor e aurait changer le r sultat de l Alpha B ta Contrairement aux coupes de l Alpha B ta qui ne changent pas le r sultat du MiniMax les coupes dues au coup nul peuvent changer le r sultat de I Alpha B ta Le joueur joue deux coups de suite et effectue une recherche a un profondeur inf rieure Si le r sultat de la recherche est inf rieur alp
3. Table 1 R sultats pour ggvl 15 Algorithm Total time Number of nodes of problems Preventip3 1s 15 20 836387 78 47 10000N Preventip3 1s 18 60 870938 77 78 ip3 1s 10000N 34 13 42382 88 19 Table 2 R sultats pour gev2 Algorithm Total time Number of nodes of problems Preventip3 1s 65 61 449987 65 28 10000N Preventip3 1s 74 25 483390 65 28 ip3 1s 10000N 21 13 27283 73 61 Table 3 R sultats pour ggv3 Des tests ont aussi t effectu s pour voir l volution de l algorithme quand plus de temps lui tait donn Les gains sont alors encore plus grands par rapport l Alpha B ta Algorithm Total Number of nodes of problems time Preventip3 10s 635 2 4607171 79 17 100000N 0 ip3 10s 100000N 63 57 81302 90 28 Table 4 R sultats pour ggv2 avec plus de temps et de n uds Algorithm Total Number of nodes of problems time Preventip3 10s 726 4 4319840 70 83 100000N 0 ip3 10s 100000N 23 97 33936 73 61 Table 5 R sultats pour ggv3 avec plus de temps et de n uds Des tests ont aussi t effectu s pour tester l int r t de l heuristique du coup nul Ces tests se r v lent concluants puisque le temps de recherche est inf rieur Toutefois l utilisation de l heuristique du coup nul enl ve la propri t de preuve l algorithme Les r sultats
4. else if valeur gt Best niveaux pairs on maximise Best valeur return Best 2 1 Le NegaMax Plut t que de tester si on est un niveau pair ou impair pour savoir si on cherche maximiser ou minimiser l valuation on peut inverser le signe des valuations chaque niveau et toujours chercher maximiser On a alors l algorithme NegaMax define PROFMAX 4 Ne marche que pour les niveaux pairs define INIFNI MAXINT int NegaMax char Position int profondeur int valeur Best i N char PositionSuivante 100 if profondeur PROFMAX return Evaluation Position N TrouveCoupsPossibles Position PositionSuivante Best INFINI for i 0 i lt N itt valeur NegaMax PositionSuivante i profondeur 1 if valeur gt Best Best valeur return Best 2 2 L algorithme Alpha Beta La coupure alpha se fait aux niveaux Min Elle est bas e sur l observation que si la valeur d un niveau Min est plus petite que la valeur du niveau Max sup rieur quelques soient les valeurs des n uds suivants le niveau Min ils ne changeront pas la valeur du niveau Max sup rieur Exemple Coupes alpha La coupure b ta est la coupure sym trique de la coupure alpha pour les niveaux Max Exemple MIN Coupes b ta MAX 3 9 MOO Propri t lorsque le minimax trouve un coup en n n uds l alpha b ta tro
5. 15 6 23 2 Tel D ou s il y a une solution elle sera obtenue en multipliant une solution au probl me pr c dent par 2 Je vais plut t m int resser 1000 0 4 Je multiplie 2 par 27 2 900 est trop petit Je vais multiplier les nombres obtenus par des nombres un peu grands ou un peu plus petits que 1000 Pour commencer on conna t 2 1024 et 2 900 On obtient ainsi 2 900 7199 x 10 trop petit Ke 2 1014 120 x 10 trop grand 2 6 1004 336 x 10 trop grand 2 994 6464 x 10 trop petit 245 998 959 x 10 trop petit 212 1003 2905 x 10 trop grand 211662 1002 246 x 10 gt trop grand 2 1 1001 2026 x 107 trop grand 22562 1000 16041 x 10 OK Dot 2000 32 x 1068 Remarques les calculs ont t faits avec une calculette sans les puissances de 10 bien s r mais ils sont faisables la main Tue a ee at je n tais pas assur e d arriver une solution en un temps manuel raisonnable le probl me pour 7 aurait pu tre r solu par la m me m thode en partant de 8 et en multipliant par 1024 etc Solution du Monde Pour 7 les auteurs partent de 64 et multiplie 4 fois par 1024 On a la solution Pour 2000 ils se contentent de dire que la r ponse est oui mais la justification n est pas simple elle fait appel a un passage aux logarithmes d cimaux on montre qu il existe
6. AND1 2OR1 2 ORI AND1 gt ORI AND2 gt OR2 AND2 ORI 2AND1 2 ORI AND1 gt OR2 AND1 gt OR2 AND2 ORAND1 2 ORI AND1 gt OR2 AND2 ORI 2ANDORI1 2 ORI AND1 gt OR2 AND1 gt OR1 AND2 gt OR2 AND2 ORAND1 2AND1 2 ORI AND1 gt ORI AND2 gt OR12 ANDI gt OR2 AND2 4 2 R sultat Exp rimentaux Les exp riences ont t effectu es sur un Pentium 266 MHz On peut voir qu un algorithme g n ral et ind pendant du jeu permet des gains substantiels c est le OR2 2AND1 2 Il ne d pend que des d finitions des jeux ip pour l largissement ce qui est une heuristique tr s g n rale Le temps de recherche est pratiquement divis par deux par rapport a l algorithme sans largissement 18 Algorithm Time Nodes Problem OR2 2AND2 2 18 1 4809 99 12 3 OR1 2AND2 2 7 6 2667 99 12 7 OR2 2AND1 2 12 8 4291 99 12 AND1 2OR1 2 2 2 2576 99 12 6 OR1 2AND1 2 2 3 3044 99 12 8 ORAND1 2 12 1 12730 99 12 OR1 2ANDOR1 2 2 3 2913 99 12 ORANDI 2ANDI 2 112 1 2587 99 12 3 Table 7 R sultats pour ggv1 Algorithm Time Nodes Problems OR2 2AND2 2 62 9 30182 86 81 6 OR1 2AND2 2 47 9 19096 86 11 9 OR2 2AND1 2 32 6 28008 86 81 2 AND1 2OR1 2 39 7 19721 86 11 4 OR1 2AND1 2 37 1 24244 87 50 5 ORAND1 2 39 5 119566 87 50 7 OR1 2ANDOR1 2 35 9 123450 87 50 9 ORAND1 2
7. 2 1 Rubrique AFFAIRE DE LOGIQUE du journal Le Monde du lundi dat mardi Ces probl mes sont de difficult tr s in gale Certains se r solvent en quelques minutes D autres ont demand beaucoup d efforts pour tre r solus avant la parution de la solution le lundi suivant Pour l un d eux enfin section 4 1 seuls le cas particulier facile et la formule dans le cas g n ral taient trouv s au bout d une semaine aussi bien par moi m me que dans la solution du Monde qui apr s la formule ajoutait Il semblerait qu on ne puisse pas faire mieux si des lecteurs peuvent le prouver qu ils nous crivent Une deuxi me semaine de recherche m a t n cessaire pour finir de d montrer qu on ne pouvait pas faire mieux 2 2 Championnats des jeux math matiques et logiques 22 finales 1999 et 2000 La r solution des probl mes de ces jeux est tr s diff rente dans un premier temps puisqu il s agit de r soudre en trois heures douze probl mes de difficult s a priori croissantes et qu il faut donner en guise de r ponse le nombre de solutions pour chaque probl me et deux des solutions ventuellement une seule ou z ro Il faut donc g rer correctement son temps non seulement r soudre les probl mes mais aussi valuer le nombre de solutions ne pas faire d tourderies ni dans la r solution ni dans la recopie des solutions Dans un deuxi me temps on a tout le loisir de reprendre les probl mes ch
8. J ai donc recommenc une recherche avec cependant les informations suivantes il y a une solution en 3 pes es on peut conclure sur le sens de l erreur la solution de JMF comporte certainement une part de combinatoire Je d marre avec 474 4 et j utilise la notation suivante bille qui ne peut tre que bonne ou trop lourde bille qui ne peut tre que bonne ou trop l g re bille dont on ne sait rien b bonne bille Cette premi re pes e conduit donc bbbbbbbb ou bien bbbb Pensant que le premier cas est r solu je m int resse au deuxi me et j essaie de m langer par exemple peser T Divers essais infructueux Combinatoire me conduit r fl chir un algorithme que l on pourrait avec quelques heuristiques d velopper la main Qu est ce que je ferais si je devais crire un programme Je l crirais r cursif avec comme param tres le nombre de de de et de b Il faudrait alors crire une descente un arr t La descente ne me semble pas simple du moins si on imagine qu on l ex cutera la main Je cherche plut t l arr t on a une seule bille ou une seule ou juste avant l arr t Je cherche les situations o l on peut conclure en une seule pes e Je trouve condition qu il y ait au moins un b Je trouve aussi et condition qu il y ait au moins 2b on p se T bb je trouverai mie
9. valuation de l int r t de faire un essai prenne plus de temps que de faire cet essai lui m me De fa on g n rale il ne faut pas faire de monitoring dans des situations o les essais devront de toutes les fa ons tre faits le temps pass au monitoring doit tre bien plus faible que le temps pass faire les essais qu il permettrait d conomiser Nous allons maintenant montrer comment ces id es ont commenc d tre impl ment es dans la nouvelle version de MALICE le module du syst me MACISTE Pitrat 96 qui est un r solveur g n ral de probl mes inspir du syst me ALICE Lauri re 76 78 2 Formulation d un probl me dans MALICE Le formalisme dans lequel les probl mes sont nonc s est bas sur celui d ALICE Quatre classes principales d informations d finissent une famille de probl mes auxquelles peuvent s ajouter les donn es particuli res chaque probl me de la famille SOIT d finit des constantes des vecteurs des matrices des ensembles I commence par le type CONSTANTE VECTEUR MATRICE ENSEMBLE suivi du nom de la variable qu il d finit puis ventuellement d un moyen de calculer cette valeur Pour cela on peut utiliser les expressions MACISTE d finissant un nombre ou un ensemble S il n y a pas de d finition le syst me demandera la valeur pour chaque probl me pos TROUVER d finit une correspondance entre un ensemble de d part El et un ensemble d arriv e
10. 2 T bb ne marche pas car il reste 22 T bbb ne marche pas car on ne peut finir avec Cette id e est fausse marche aussi bien que en une pes e mais peu importe pour la suite Id e prendre une sorte d interm diaire On en prend alors 3 compl t s par un b soit T 2b si quilibre on p se restant en une 3 pes e sinon on a ou qui est r solu en une 3 pes e 105 On a finalement une solution on p se T 229 on a on a on p se on p se T b on a on a on a ona T bb Tb T bb ITb gt lt gt gt lt gt lt gt lt Une petite pr cision semble n cessaire quand on p se T en cas de d s quilibre la pi ce fausse se trouve soit parmi les deux du plateau le plus lourd soit le du plateau le plus l ger les trois autres pi ces tant bonnes On se retrouve donc avec mais ce ne sont pas ceux d aucun des plateaux pr c dents Les id es fortes ont t les deux suivantes se r sout en une pes e peut tre obtenu en pesant T 2b Ce sont certainement des id es dont je me souviendrai et je pourrai maintenant retrouver cette solution m me dans longtemps contrairement la solution du Monde JI est en effet plus utile et plus facile de m moriser les points clefs d une solution plut t que la totalit des tapes De nombreuses variantes existent avec les m mes id
11. F B F C F D F E si les valeurs des l ments A B C D et E sont positifs et inf rieurs 10 si de plus ils sont en disjonction ou bien AMA pour F vaut 1 la r gle pr c dente s appliquera si la fonction INF est capable d utiliser les disjonctions En effet le premier membre vaut au moins 1 2 3 4 soit 10 alors que le deuxi me membre vaut au plus 9 Cette r gle a enfin une action CONTRADICTION qui indique que le sous probl me en cours n a pas de solution D crivons maintenant plus rapidement une r gle R2 un peu plus complexe Nous avons d abord la d finition des types des variables CONTRAINTE R TERME X 121 TERME Y TERME Xj et les ensembles d instanciations possibles Xe UNDESFILS R Y AUTREFILS R X Xie ARGUMENTS X Nous avons ensuite la condition MATCHE X SOMMEIX X2 Xn qui indique que le terme X est la somme de n termes n tant quelconque sup rieur a 1 Nous avons alors une action qui est la cr ation d une nouvelle contrainte CONTRAINTE Xi lt SUP Y INF SOMMEIX Xo Xi 1 Xir1 Xn Cette nouvelle contrainte est beaucoup plus simple que la pr c dente puisqu elle ne comporte que le terme Xi de la contrainte initiale le deuxi me membre de la contrainte est en effet une constante Par exemple si la contrainte R est F A 3 F B F C F D F E 7 si les valeurs de F A F C et F D sont sup rieures ou gales 1
12. Pour faire plus propre il faudrait prendre k 4 et trouver directement a Je reviens alors sur le brouillon et la d couverte de l erreur a t laborieuse car je v rifiais tout sauf le passage de 10 27R R 84 Remarque L histoire du num rateur plus simple que le d nominateur peut sembler stupide puisqu il ne 1 1 a s agit que de proportions Ecrire a aai devrait tre analogue Pas tout fait il me semble alors que montrer que l quation a une racine n gative donc une seule racine acceptable est un peu plus compliqu et je laisse ce fait v rifier en me disant que j ai bien fait de faire le choix inverse En fait quelques mois plus tard je suis all e un peu vite il y a bien une racine liminer mais c est soit parce qu elle est n gative soit cas k lt 1 dans la version r dig e plus haut parce qu elle est sup rieure 1 4 Id es fausses et bonnes id es On verra comment des id es fausses ont pu conduire malgr tout de bonnes id es et comment dans la recherche de propri t s pertinentes des raisonnements incomplets ou inexacts ont t repris jusqu la mise au point de la bonne propri t On verra galement l importance des essais des cas simples et des dessins 4 1 Potins et comm res Le Monde 14 mars Affaire de Logique Probl me n 163 Chacune de ces cinq comm res conna t un potin croustillant qu elle voudrai
13. ajhyp A C app D M rajouter que C est sur la m diane IG 164 memoriser app_CS7 H J K M m moriser que ce fait provient des faits no H J et K et a t obtenu par la r gle app CS7 memoriserExpl obligatoire C est le centre de gravit du triangle I E F donc il appartient la m diane issue d JT cad La droite Ty Gy M Ymemoriser le mod le explicatif instanci avec les bonnes valeurs de variables 2 D duction tout venant regle A centreGraviteDeduction B milieu A C D E F E milieu de CD centreGravite A G C D H I H centre de gravit de GCD droite A J G E K J GE hyp A H app J L Argos ne sait pas que H app GE ajhyp A H app J M rajouter que H app GE memoriser centreGraviteDeduction F I K M memoriserExpl obligatoire H est le centre de gravit du triangle G C D donc il appartient a la m diane issue d G cad l droite G Ey I Jz M 3 R gle de cr ation regle A centreGraviteDeductionCreation B milieu A C D E F centreGravite A G C D H I distincts G E not droite A J G E K La droite GE n existe pas pour Argos creerDroite A G E L M cr er la droite GE creePar centreGraviteDeductionCreation F I M me moriser les conditions de la cr ation Annexe5 Enonc en
14. ce qui donne l quation 5 2 Touch coul Le Monde 3 juin Affaire de Logique Probl me n 175 Le jeu de bataille navale se joue sur un damier Une flotte comporte un porte avions 4 cases deux cuirass s 3 cases trois croiseurs 2 cases et quatre sous marins 1 case deux navires distincts ne peuvent se toucher m me par un coin Pouvez vous en respectant ces r gles placer deux flottes compl tes dans un quadrillage de 10 cases sur 10 D A A A Des premiers essais montrent qu un flotte occupe la moiti du quadrillage mais qu on ne peut pas mettre la deuxi me flotte sans toucher la premi re Rapidement je remplace les navires de n cases par des blocs de 2x n 1 cases pol La contrainte de ne pas se toucher dispara t et il faut consid rer un quadrillage de 11x11 Un rapide calcul montre que chaque flotte occupe 10 8x2 6x3 4x4 60 cases et qu il faut donc placer un total de 120 cases dans un quadrillage de121 cases Il n y a donc qu un case en trop Premi re id e regarder les diff rentes fa ons d obtenir 11 avec les longueurs et les largeurs des blocs 11 5 4 2 5 3 3 5 2 2 2 4 3 2 2 3434342 et aussi 10 qui concernera les deux lignes horizontale et verticale o se trouve la case vide 10 5 3 2 44442 3 3 2 2 Un d compte des diff rentes possibilit s n est pas jug assez contraint Je m int resse alors la
15. la valeur du poids le plus grand moins une constante d acceptation de choix fix e au d part Plus cette constante est grande plus le nombre de coups envisag est important plus les chances d envisager le meilleur coup sont grandes et en contrepartie plus le co t d exploration est grand D une fa on analogue lorsque le syst me a d cid de poser une hypoth se sur un type d v nement il limine tous ceux dont la probabilit est inf rieure une constante de s lection des v nements Plus cette constante est grande plus le nombre de situations envisag es est grand Le syst me n est donc pas amen envisager des situations trop improbables 3 5 Remont e de l information et d sactivation des n uds La remont e de l information est r alis e sur un principe similaire au B pour les hypoth ses de type choix du syst me La borne inf rieure resp borne sup rieure de la fonction d valuation d un noeud dont les arcs sortant sont des choix est obtenue en prenant le maximum de la borne inf rieure resp borne sup rieure des situations r sultantes de ces choix La borne inf rieure resp sup rieure d un noeud dont les arcs sortant sont des v nements probabilis s est calcul e comme la somme des produits de la probabilit de chaque arc par la borne inf rieure resp sup rieure des situations r sultantes Comme pour le B lorsque l esp rance pessimiste d un choix C1 est meilleure que l esp rance optimi
16. partir de chaque configuration en hypoth se pour ne pas introduire trop d objets mais quand m me ceux qu il faut Par exemple si un triangle quilat ral est en hypoth se que doit on cr er Apr s discussion aupr s d experts du domaine on indique que les trois c t s et les trois angles au sommet ont m me mesure L appel de conjectures en fonction du but est un moyen d introduire de bons objets en cours de d monstration Mais ceci doit reposer sur des heuristiques de cr ation donn es par l expert ou d couvertes par le syst me 10 2 Comment charger les bonnes r gles Il faut impl menter la d marche de l expert c est dire l extraction des configurations pr gnantes qui sautent aux yeux de l expert Il faut constituer un tiquetage de la figure au sens de JM Bazin Bazin 93 Il faut mieux cerner l implication d une r gle en fonction de la conjonction de concepts pr sents En quoi par exemple la pr sence des deux concepts quilat ral et orthogonalit va t elle influer sur le chargement des r gles La typologie de r gles devrait prendre en compte la conjonction de plusieurs concepts L ensemble des r gles pourrait tre structur selon un mod le hi rarchique Mais peut on r ellement fabriquer un tel 155 mod le qui impl menterait vraiment la d marche de l expert 10 3 Ordonner les r gles dynamiquement Comment l expert sent il qu il est sur une mauvaise piste Ce n
17. r pondre cette question leur examen d Initiation la programmation On consid re la fonction enti re f n n Vn 2 o d signe la partie enti re Pour tout entier a si l entier n parcourt l intervalle 1 a fn atteint a a en sautant exactement a entiers crire un programme Pascal qui demande l utilisateur de fournir une valeur de a et affiche les valeurs enti res que f n ne prend pas Pourriez vous d terminer les valeurs saut es par la fonction f n directement par un raisonnement math matique On trouve facilement que les valeurs saut es sont tous les carr s On trouve moins facilement que le saut a lieu pour le passage de p p p p 1 Je n ai pas gard de protocole de la recherche mais un id e fausse sur la r partition des racines carr es des nombres compris en p et p l m a beaucoup g n e Je pensais na vement cause de l image mentale de la courbe vx qu il y en avait beaucoup plus dont la partie d cimale tait sup rieure 2 que inf rieure On a en effet les variations suivantes en consid rant les nombres de la forme n p a compris entre p et p 1 et en remarquant que vn 4 est l arrondi l entier le plus proche de n a 0 7 p T pits T p 2p 1 n P 7 pp T ou T pT pty vn p aT p 1 2 H ptl vVn p p Z ptt pt gt p p p p On constate qu il y a p nombres entiers dont
18. tre humain raisonne il peut tre utile de l observer Apr s une auto observation de quelques mois pendant la r solution d une vingtaine de probl mes cet article d crit et analyse les recherches effectu es essaie de comprendre ce qui a conduit aux bonnes id es et essaie de montrer comment m me ce qui tait faux ou pourrait sembler inint ressant a pu aider progresser vers les solutions Mots cl s auto observation r solution de probl mes logique jeux math matiques puzzles 1 Introduction Les m thodes utilis es en Intelligence artificielle dans la r solution automatique de probl mes peuvent tre tr s diff rentes de celles utilis es par l tre humain et sont parfois beaucoup plus efficaces On peut aussi choisir au contraire de d finir des m thodes imitant le comportement de l tre humain par exemple pour faire de la simulation ou si la machine doit dialoguer avec l tre humain ou lui expliquer sa r solution On peut aussi s inspirer de ce que fait l tre humain en particulier de ses heuristiques et de son expertise si l on ne conna t pas de m thodes pour r soudre certains probl mes N anmoins ceci est galement difficile car on ne conna t pas bien ces heuristiques et cette expertise qui sont en grande partie inconscientes Un expert n est souvent pas capable de communiquer sa propre expertise froid Pour cela il doit sans que cela soit toujours suffisant tre mis en sit
19. 8 l ments prises dans Un Jeu de 52 Cartes Construction 1 l ment tel que la hauteur est As 2 l ments tels que la hauteur est Roi 2 l ments tels que la hauteur est Valet 3 l ments tels que la hauteur n est pas dans Valet Roi As Effacer la Solution BRAVO Votre Solution est correcte Figure 1 24 Dans la suite de l article l exercice suivant Avec un jeu de 52 cartes combien y a t il de mains de 8 cartes contenant exactement as 2 rois et 2 valets sera utilis pour illustrer nos propos Cet nonc est un nonc pris dans un livre d exercices il signifie combien y a t il de mains de 8 cartes contenant exactement as exactement 2 rois et exactement 2 valets et 3 cartes qui ne sont ni as ni roi ni valet Le mod le conceptuel que nous avons d fini pour repr senter le domaine des d nombrements est d crit dans Tisseau et al 00 1 Tisseau et al 00 2 Dans le cas du jeu de 52 cartes chaque carte est repr sent e en utilisant deux attributs couleur et hauteur La figure 1 nous montre l aspect de la machine apr s construction d un l ment de l univers des mains de 8 cartes A partir de cette construction et dans cette machine le nombre de configurations possibles est le produit des possibilit s 4 chaque choix Il faut bien voir que cette image n est que l aspect final de la r ponse et ne montre pas les diff rents l ments d i
20. Un syst me g n ral de jeu de cartes un domaine int ressant pour l IA Rapport de recherche LIP6 1999 014 Lauri re 96 Lauri re J L propagation de contraintes ou programmation automatique Rapport LAFORIA 96 19 Nunn 00 Nunn J Secrets of Practical Chess Eds Gambit 2000 p 1 66 Pastre 00 Pastre D Chemins d tourn s id es fausses et bonnes id es Actes colloque Berder 2000 Parchemal 88 Parchemal Y SEPIAR un syst me base de connaissances qui apprend utiliser efficacement une expertise Th se de l Universit Paris 6 1988 Pitrat 00 Pitrat J La mise en place du monitoring dans MALICE Actes colloque Berder 2000 Pitrat 99 Pitrat J une exp rience de monitoring Rapport de recherche LIP6 1999 014 53 Combinaison d hypoth ses dans les probl mes solution complexe m thode a posteriori contre m thode a priori Tristan PANNEREC Tristan Pannerec lip6 fr R sum L utilisation de raisonnement hypoth tique dans les syst mes de r solution de probl mes pose la question fondamentale du contr le des hypoth ses d velopp es Cette question s accentue encore lorsque la r solution porte sur des solutions complexes optimiser et que les hypoth ses correspondent des choix sur le contr le de cette r solution En particulier les solutions obtenues selon diff rentes hypoth ses doivent alors tre combin es pour obtenir la solution finale Dans ce papier nous proposons deux m thodes b
21. aboutir Une fois la solution trouv e il serait alors ais de trouver la justification la plus simple et la plus l gante telle que celle que l on trouve dans les livres Actuellement les syst mes d intelligence artificielle cherchent aller droit au but ou au moins le plus directement possible Peut tre serait il n cessaire pour les faire progresser de leur apprendre naviguer parmi les id es fausses et le chemins d tourn s L tourderie est le propre de l homme C est un d faut que les machines n ont pas Nous avons quelquefois des difficult s parce que nous sommes trop savants et nous ne voyons pas les choses simples Pour le moment les machines peuvent nous surpasser dans ces situations 113 Mais le jour o elles seront aussi savantes que nous elles auront sans doute les m mes difficult s Enfin en dehors des domaines pour lesquels nous sommes devenus experts nous ne pouvons nous souvenir longtemps que de ce qui nous a marqu en particulier de ce qui nous a sembl tr s important ou particuli rement int ressant Le souvenir de quelques points cl s est plus utile que la m morisation d un grand nombre d tapes M me si les capacit s m moire d une machine sont sans commune mesure avec les n tres il faudrait apprendre aux syst mes d intelligence artificielle d gager les points importants des raisonnements 10 R f rences Farreny 87 Farreny H Ghallab M El ments
22. comme grand alors que dans d autres il est petit Un autre aspect approfondir est celui des exp riences Le syst me devra tre capable 129 de lancer des essais en comparant ce que donnent deux m thodes Cela aidera choisir celle qui conduit aux meilleures performances dans des cas o les connaissances du syst me sur la th orie de la r solution de probl mes ne lui permettent pas de trancher Un autre type d exp rience est de faire des essais en ratissant plus large que d habitude par exemple en acceptant de faire des essais que l on s interdirait de faire en temps normal En effet si l on ne se permet pas de rel cher les contraintes on fait toujours la m me chose et l on ne se rend pas compte qu il existe des situations o des m thodes consid r es comme inappropri es peuvent tre en r alit les meilleures Il faut se donner la chance d avoir parfois de bonnes surprises d avoir du succ s 1a o l on ne s y attend pas Si l on a un comportement d expert qui va droit la solution sans examiner d autres chemins on risque de se fixer sur des maxima secondaires Une fois un probl me r solu un syst me peut se payer le luxe de voir s il n y avait pas d autres choses faire dans les p riodes o on ne lui a pas donn de t che pr cise 7 Le m tamonitoring Le but du monitoring est de faire gagner du temps au syst me Il est donc hors de question qu il passe un temps
23. droite b o orthog droite a c longueur a c 15 longueur a 0 3 longueur f 0 3 longueur b 0 6 droite a g et droite b f sont des droites parall les g est sur la droite droite f h CONCLUSIONS 1 calculer longueur a b 2 calculer longueur b c 3 droite a b orthog droite b c 4 h fc est un triangle rectangle en h 5 droite a b et droite f h sont des droites parall les 6 ba f est un triangle isoc le en b 7 ab f g est un losange DEMONSTRATION r ponse la question no 1 Onaba 2 0a 2 bo0 2 car le triangle o b a est rectangle en o Commeab ab bo bo ao ao alorsab rac 3 3 6 6 3 rac 5 r ponse a la question no 4 Le point h est sur le cercle de diam tre f c donc le triangle f c h est rectangle en h r ponse la question no 2 o appartient au segment ac doncac ao t oc Commeac ao oc alorsoc 15 3 12 Onabc 2 0c 2 b0 2 car le triangle o b c est rectangle en o Commebc bc bo bo oc oc alorsbc rac 12 12 6 6 6 rac 5 r ponse a la question no 3 Le fait a b 3 rac 5 a t d duit d apr s la question 1 Le fait b c 6 rac 5 a t d duit d apr s la question 2 ac 2 225 bc 2 ba 2carac 15bc 6 rac 5 etba 3 rac 5 Onaca 2 ba 2 cb 2 donc le triangle b c a est rectangle en b 161 Les droites b c et b a sont perpendiculaires car le triangle b c a est rectangle en b les droites a b et b c sont perpendiculaires par sym trie r
24. pouvoir d terminer l impact d une hypoth se sur la valeur d une solution et sur les autres hypoth ses 4 3 Forces et faiblesses De m me que dans la partie pr c dente les performances de la m thode d crite dans cette partie d pendent du degr de d pendance existant entre les hypoth ses 4 3 1 Temps de calcul Dans le cas d hypoth ses ind pendantes le temps de calcul n cessaire avec la m thode a priori est sup rieur celui de la m thode a posteriori m me avec le m canisme de gestion des hypoth ses ind pendantes que nous avons d crit En pratique cela ne p nalise gu re la m thode a priori car la diff rence n est pas norme et les hypoth ses sont de toute fa on rarement ind pendantes En ce qui concerne les hypoth ses d pendantes cas normal de fonctionnement la m thode d crite dans cette partie est largement plus rapide en th orie car le programme ne perd pas de temps avec un tat interm diaire les solutions des hypoth ses tudi es s par ment qui est souvent inutilisable Les r sultats exp rimentaux devront confirmer cette th se 4 3 2 Qualit des solutions obtenues En terme de qualit les solutions obtenues avec des hypoth ses ind pendantes sont bien s r rigoureusement identiques En ce qui concerne les cas normaux o les hypoth ses ne sont pas ind pendantes la seconde m thode fournit en th orie des solutions de meilleure qualit surtout s
25. t vraiment utiles la preuve les concepts ayant t introduits et utilis s les concepts figurant dans la partie conclusion les objets ayant t n cessaires et ayant t cr s en cours de preuve la raison pour laquelle on les a cr s et ce quoi ils ont servi puis la dur e de la d monstration Il va alors mettre jour ses connaissances strat giques Il rajoute des liens entre les r gles utiles et les concepts de la conclusion sauf s ils existaient d j Il m morise donc que telle r gle est une r gle utile pour montrer tel l ment de conclusion Chaque r gle poss de un poids mesurant son importance par rapport un concept conclusif donn Ce poids est lui aussi mis jour pour chaque r gle ayant t utile Ceci va alors permettre une mise jour des strat gies existantes pour d montrer tel ou tel type de conclusion Par exemple si telle r gle a t utile pour montrer qu un triangle tait quilat ral son poids est augment de 1 Ceci pourra entra ner un changement de l ordre des r gles dans la liste correspondant la strat gie pour montrer qu un triangle est quilat ral 8 2 Discussion et probl mes Le but de cet apprentissage est bien s r de mod liser les m canismes d apprentissage de l humain Un travail norme reste faire Comment g n raliser une technique partir d un ou plusieurs exercices r solus de la m me fa on Comment le syst me pourrait il s ape
26. tait aussi m me pour une auto observation difficile de trouver le temps de passer toutes ces heures et ces journ es tranquillement assise devant mon bureau avec papier crayon pour tout noter et magn tophone pour enregistrer une r flexion voix haute Je devais au contraire profiter de tout moment o mon esprit n tait pas occup par une autre t che pour r fl chir quelquefois avec la possibilit de griffonner quelques quations ou quelques dessins d autres fois purement mentalement Je faisais n anmoins l effort d s que possible et chaque fois que cela tait n cessaire de noter rapidement par crit ce que j avais fait ou envisag et pourquoi le cheminement de ma pens e m me si les id es ou les techniques employ es n avaient pas abouti m me si ce qui avait t fait ou envisag ne semblait pas int ressant Je ne dispose donc pas de protocoles compl tement d taill s mais de r sum s qui donnent une bonne id e de mes recherches On trouvera dans cet article des r sum s de ces r sum s dans lesquels j ai essay de d gager les points importants de mes recherches qui m ont conduit ou ne m ont pas conduit des solutions sans omettre les impasses ni les grosses b tises On verra d ailleurs et c est un ph nom ne qui m a sembl important et qui a donn le titre de l article qu c t des stupidit s impardonnables et sans int r t il y a des erreurs ou des inexactitudes qu
27. 3 5 8 et 17 les timbres restant formant toujours un ensemble d un seul tenant Pouvez vous reconstituer ce carnet en pla ant la plus petite des quatre valeurs de coin en haut et a gauche L exemple de la figure ci dessous ne convient pas car il est impossible d obtenir les sommes 7 10 12 15 24 27 et 32 1 2 3 5 8 17 R solu de mani re combinatoire et apr s pas mal de cafouillages J ai m me plusieurs reprises cru que le probl me tait impossible On num re les nombres autres que 1 2 3 5 8 17 qui ne peuvent s obtenir que d une seule fa on 4 1 3 7 2 5 12 1 3 8 15 2 5 8 et les compl mentaires 32 29 24 qui peuvent s obtenir de deux fa ons 6 1 2 3 1 5 9 1 3 5 1 8 10 2 6 2 3 5 13 2 3 8 5 8 14 16 17 18 et les compl mentaires 111 qui peuvent s obtenir de trois fa ons 11 Remarques qui n ont t faites qu apr s un long moment de recherche pour les ensembles de d composition unique il faut que l ensemble et son compl mentaire soient connexes pour les autres il suffit qu un des ensembles soit connexe et que le compl mentaire d un ensemble le m me ou un autre le soit aussi sauf pour 18 gal son compl mentaire pour lequel il suffit qu un des ensembles ou son compl mentaire soit connexe 8 4 Les sauts A partir d un sujet d examen Les tudiants de DEUG de Paris 5 ont eu
28. 6 Construction automatique des r gles 6 1 Principe de construction Il s agit de faire construire par le syst me de fa on automatique des r gles de diff rents types partir de connaissances donn es de fa on d clarative par un utilisateur ARGOS va alors pouvoir construire automatiquement a partir d une m me connaissance math matique des r gles de type d duction d marche en avant d duction en fonction du but cr ation d objet manquant et des r gles de condition suffisante de la conclusion 6 2 D marche 6 2 1 Donner un nom la r gle Il faut donner un nom la r gle en fonction du type voulu des concepts pr sents et de ce qu elle va faire ceci pour am liorer le confort de l utilisateur expert qui veut relire sa base de r gles A partir du concept centre de gravit par exemple seront fabriqu es automatiquement des r gles qui d duiront des propri t s partir d un centre de gravit existant et d autres qui si les conditions sont r unies dans la base de faits rajouteront que tel point est un centre de gravit Des r gles de cr ation d objets manquants seront aussi construites ainsi que des r gles de condition suffisante de la conclusion sortes de raccourcis guid s par le but 6 2 2 Constituer le corps de la r gle Il faut que la r gle v rifie la pr sence des objets n cessaires Il faut constituer la partie condition n cessaire l application de la r gle Il
29. Dans cet article nous inventorions les diff rentes cat gories d erreurs dans la machine ConstructionEnsemble Nous proposons une m thode de conception des interfaces p dagogiques qui s appuie sur la gestion des erreurs Nous indiquons ensuite comment nous r alisons la gestion des erreurs dans cette machine 23 2 La machine ConstructionEnsemble Les machines permettent pour chaque classe de probl me de construire un l ment de l ensemble d nombrer en suivant la m thode constructive puis partir de cette construction de compter le nombre d l ments de cet ensemble Tisseau et al 00 1 Tisseau et al 00 2 Les exercices de la machine ConstructionEnsemble sont du type Soit un ensemble donn le r f rentiel compter le nombre de configurations contenant X l ments de ce r f rentiel l ensemble des configurations est appel univers et satisfaisant certaines contraintes Les contraintes sont de la forme exactement X1 l ments appartenant au sous ensemble R1 du r f rentiel exactement X2 l ments appartenant au sous ensemble R2 du r f rentiel etc Les sous ensembles Ri tant tous disjoints deux deux Machine Construction Ensemble OI X Exercice n 2 Main de 8 cartes 1 As 2 Rois 2 Valets Avec un jeu de 52 cartes construire une main de 6 cartes contenant exactement 1 As 2 Rois et 2 Valets Prahl ma n 21 Changer Exercice Solution Univers L ensemble des parties
30. Sciences et techniques ducatives Vol 3 n 2 1996 159 Annexe Exemple d exercice r solu avec questions enchain es Enonc en fran ais Soient a o f c 4 points align s dans cet ordre avec ao of 3 ac 15 Soit b un point tel que ob 6 et bo L ac Le cercle de diam tre fc coupe la droite bc en h g est le point d intersection de la droite hf avec la parall le la droite bf passant par a 1 Calculer les longueurs ab et bc 2 Montrer que ab L bc 3 Montrer que le triangle hfc est rectangle en h 4 Montrer que ab fh 5 Montrer que le triangle baf est isoc le 6 Montrer que abfg est un losange b figure a C Enonc donn au syst me alignesOrd a o f c get cercleDiam f c cercle et h estDans cercle inter droite b c et droite b o orthog droite a c et longueur a c egal 15 et longueur a o egal 3 et longueur f o egal 3 et longueur b o egal 6 et droite a g paralleles droite b f et g app droite f h gt calculer longueur a b et calculer longueur b es et droite a b orthog droite b c et trRect h Ey c et droite a b paralleles droite f h et isocele b a f ct losange a b f g Preuve r dig e du th or me HYPOTHESES DE DEPART les points a o f et c sont align s dans cet ordre 160 cercle est le cercle de diam tre fc h est l intersection de cercle et droite b c
31. acmf est un rectangle Enonc donn au syst me et utilisant la notation fonctionnelle equilateral a b c et milieu a m b et milieu b d m et projeteOrthog d droite b c f gt rect a c m f 136 figure d 3 2 Analyse de l nonc et limination des symboles fonctionnels Le syst me extrait les concepts triangle quilat ral milieu projet orthogonal droite en hypoth se et rectangle en conclusion Le syst me donne un nom dr la droite bc et range le fait que dr est le nom de bc en m moire pour un traitement ult rieur 3 3 S lection et chargement automatique des r gles ad quates dans un certain ordre Une typologie des r gles ayant t construite automatiquement existe exprimant des liens entre concepts et r gles construites Argos a lui aussi tiss au fil des exercices r solus un r seau compl mentaire de liens de ce type Il conna t par apprentissage un certain nombre de r gles ayant d j servi d couvrir des rectangles et il les a rang es en fonction de leur fr quence d utilisation pour constituer une strat gie Il va alors construire la liste des r gles actives en fonction de cette typologie l aide des concepts ayant t extraits de l nonc puis lancer la recherche Le triangle quilat ral abc est introduit les milieux et le projet orthogonal f Il faut aussi introduire le quadrilat re acmf et certains l ments susceptibles d tre utiles
32. effectuer un remplacement celui ci peut chouer au cours de l ajout du nouveau choix impossibilit de trouver un chemin par exemple Comme pendant la r solution d un probl me normal le syst me revient en arri re pour effectuer un autre m ta choix Lorsqu il arrive la fin du sch ma le syst me value alors la solution obtenue et peut d cider de remettre en question des m ta choix pour tenter d am liorer cette solution La principale difficult de ce sch ma r side dans les instructions SuppChoix et AjoutChoix Ces instructions doivent r percuter les modifications de solution sur les situations associ es et toutes les variables d tats doivent tre mises jour sans les recalculer compl tement D autre part il est difficile pour le syst me de trouver des retours arri res int ressants partir d une premi re solution car peu de liens existent entre les m ta choix et la valeur de la solution obtenue 3 4 Forces et faiblesses de l approche a posteriori Afin de comparer l approche d crite dans cette partie avec celle qui sera d crite dans la partie suivante nous tudierons les caract ristiques de chacune en terme de rapidit d ex cution et de qualit de solution obtenue 3 4 1 Temps de calcul L id e sous jacente de l approche a posteriori est de r duire la complexit du probl me par une d composition Le fait de tester les hypoth ses ind pendamment
33. la d monstration Ceci permettrait une plus grande souplesse au niveau de la mise jour de la base de connaissances d explication et une maintenance de celle ci par un utilisateur n ayant aucune connaissance du fonctionnement interne du syst me Pour l instant le syst me s appuie sur l expert en ce qui concerne la construction de l explication Il poss de cependant un dictionnaire lui permettant de traduire en fran ais tous les pr dicats internes d duits et il est capable d aller rechercher la d finition d un nom interne pour une r gle plus g n rale o ne serait pas sp cifi la nature des objets utilis s 4 3 1 Gestion des pr dicats sym triques ou de d nomination fonctionnelle multiple On accepte que dans la preuve le parall logramme acmf apparaisse certains endroits sous la d nomination acmf et d autres sous la forme facm par exemple Ceci ne doit pas entra ner de surcharge cognitive trop forte pour le lecteur car celui ci a la figure sous les yeux et voit instantan ment qu il s agit du m me objet Une droite re oit un nom interne partir de deux points et ce nom sera syst matiquement retranscris sous la forme droite a b m me si ce n est pas vraiment avec ces deux points qu on veut l utiliser 4 3 2 Gestion des implicites Dans une r daction type tout n est pas justifi noir sur blanc Il y a des implicites qui d pendent du contrat didactique pass entre le professeur et les l
34. tats est int ressante conceptuellement car universelle elle n apporte rien de plus car le parcours exhaustif d un graphe d tat est en g n ral totalement hors de port e d une quelconque machine Si l tre humain consid re souvent diff rentes alternatives pour trouver une solution seule une infime partie des tats possibles du graphe reste tudi e C est ce constat qui a motiv l introduction d heuristiques et de connaissances pour diriger de mani re efficace la recherche de la solution Le principe est d valuer a priori les chances de succ s d une branche Malheureusement il est en g n ral Voir Pearl 84 pour une pr sentation compl te 58 impossible de trouver des heuristiques parfaites pour un probl me c est dire conduisant la solution quelle que soit l instance du probl me C est pourquoi les heuristiques ne permettent pas de faire l conomie d une exploration partielle du graphe d tats Le probl me qui se pose est alors d explorer intelligemment ce graphe d tats pour trouver les solutions de la mani re la plus efficace qui soit Ce probl me peut se r sumer par la question d sormais classique quel tat suivant dois je consid rer En fait face l incroyable combinatoire que pr sente la plupart des probl mes de d cision complexe l expert humain raisonne rarement au niveau des choix de base qui constitueront la solution Au lieu de cela il r fl chit
35. une pr sentation de la m tacognition Voir Pitrat 91 Pitrat 00 et Pollock 89 pour l utilisation du monitoring dans les syst mes d Intelligence Artificielle 70 ooo ab es Trace du raisonnement dans une approche a priori Figure 12 Comparaison des traces des deux approches d crites dans le cas de deux chois abstraits C et C deux possibilit s h1 h2 et h1 h2 hx signifie que l on se place dans le cas o l on n utilise pas la possibilit x n gation de hx 4 2 1 Faut il continuer dans la voie actuelle A travers cette question le syst me est face un probl me classique du monitoring qui consiste anticiper les r sultats des voies de recherche pour viter de s acharner dans une impasse ou de perdre trop de temps sur des choses peu importantes voir Pitrat 00 Pour cela il doit tout d abord disposer d un encadrement du r sultat attendu la borne sup rieure permet de savoir si une bonne solution peut tre trouv e dans cette voie Si elle est inf rieure des r sultats d j obtenus par d autres voies il n est videmment pas n cessaire de continuer La borne inf rieure permet quant elle d estimer la probabilit de trouver une solution int ressante dans la voie de recherche actuelle Cette probabilit peut en effet influer sur la d cision par exemple si la meilleure solution obtenue a une valeur de 100 les 71 encadrements 0 110 et 10
36. Duma J Design principles for a system to teach problem solving by modelling Lecture Notes in Computer Science N 1839 ITS 2000 Springer Verlag Montr al 2000 37 Contr le du raisonnement hypoth tique en environnement incertain et incomplet le jeu de l ascenseur Fabrice KOCIK doctorant de l universit Paris 6 directeur de th se Jacques Pitrat R sum Les m thodes arborescentes classiques bas es sur le min max sont souvent tr s co teuses et aboutissent une combinatoire importante L alpha beta et ses optimisations r solvent en partie uniquement ce probl me Dans tous les cas les explications fournies par les syst mes utilisant de tels algorithmes sont difficilement compr hensibles et reposent sur des hypoth ses concernant la strat gie des autres joueurs Pour r soudre tous ces probl mes il est n cessaire d avoir un syst me qui raisonne au niveau meta d une fa on plus labor e Nous proposons ici d am liorer les techniques arborescentes avec la prise en compte dans la recherche arborescente de connaissances plus abstraites d v nements incertains probabilis s et aussi avec l utilisation de connaissances imparfaites pour la fonction d valuation bas es sur les notions de n cessit et de plausibilit Une grande importance dans le contr le sera donn aux connaissances a priori Mot cl s Arbre de recherche probabilit contr le syst me expert incertain 1 Introduction Deux probl mes
37. En effet chaque choix abstrait rencontr plusieurs possibilit s sont disponibles et le syst me doit s lectionner la plus int ressante Cela peut tre celle qui a le plus de chance d tre pr sente dans la solution finale pour viter d avoir revenir dessus a posteriori ou celle qui est la plus rapide tudier pour limiter l espace de recherche De m me que pour la question pr c dente le syst me doit disposer pour chaque possibilit d un encadrement du r sultat anticip et d un encadrement du temps de recherche n cessaire N anmoins l encadrement du r sultat attendu est fondamentalement diff rent car il se fait ici d apr s le choix l estimation est a priori alors qu il se faisait d apr s la solution d j obtenue estimation a posteriori dans la question pr c dente Cette estimation est obtenue d apr s les connaissances du syst me sur le domaine par exemple il est bon d attaquer les pi ces les plus faibles de l adversaire et d apr s le pass du raisonnement Ainsi si la possibilit envisag e a d j t test e dans une autre voie de recherche et n a pas fonctionn l int r t de cette possibilit sera diminu Au contraire certains choix peuvent tre faits automatiquement s ils ont bien fonctionn dans une autre voie A ce m canisme de s lection il convient d ajouter un m canisme de gestion des hypoth ses ind pendantes qui utilise de nouv
38. J Pitrat Monitorer la recherche d une solution Actes de Berder 1999 Bernat 94 P Bernat CHYPRE un exemple pour l enseignement de la g om trie Th se 158 Universit Henri Poincar Nancy 1994 Melis 99 E Melis et Uri Leron A Proof Presentation Suitable for Teaching Proofs Artificial Intelligence in Education SP Lajoie and M Vivet Eds IOS Press 1999 Luengo 99 Vanda Luengo A Semi Empirical Agent for Learning Mathematical Proof Artificial Intelligence in Education SP Lajoie and M Vivet Eds IOS Press 1999 Koedinger 99 V Aleven Kenneth R Koedinger Karen Cross Tutoring Answer Explanation Fosters Learning with Understanding P 199 206 Artificial Intelligence in Education SP Lajoie and M Vivet Eds IOS Press 1999 Nicaud 99 JF Nicaud D Bouhineau C Varlet Anh Nguyen Xuan Towards a product for teaching formal algebra P207 214 Artificial Intelligence in Education SP Lajoie and M Vivet Eds IOS Press 1999 Nguyen Xuan 99 Anh Nguyen Xuan Anne Bastide JF Nicaud Learning to solve polynomial factorization problems By solving problems and by studying examples of problem solving with an intelligent learning environnement Artificial Intelligence in Education SP Lajoie and M Vivet Eds IOS Press 1999 Horacek 99 Helmut Horacek Presenting Proofs in a Human Oriented Way CADE 16 Atomated Deduction 1999 Py 96 Dominique Py Aide la d monstration en g om trie le projet Mentoniezh
39. a au plus deux a al et a2 qui connaissent tous les potins de A Idem pour B Il faut au moins n 1 a 2 b 2 2 2n 3 pour compl ter 3 cas la connexit n appara t qu au n 1 p appel apr s na appels chez A et ng chez B Il y a au plus 2n4 2 comm res de A connaissant tous les potins de A et au moins a 2n 2 ne les connaissant pas Il y a donc apr s le n 1 na ng appel entre al et b1 n 1 p Xa au moins a 2n4 2 comm res a qui il manque au moins un potin de A et tous ceux de B sauf had appels plane ventuellement a qui conna t des potins de B p nA nB Ya au plus 2na 2 comm res qui connaissent tous les potins de A et aucun potin de B sauf ventuellement une a1 soit 2n4 1 connaissant tous les potins de A et aucun de B et une connaissant tout Idem pour B Il faut donc compl ter a 1 ou a comm res de B et b 1 ou b comm res de B Un m me 89 appel peut compl ter la fois deux comm res de VA et Yg couples compl mentaires mais chaque comm re de XA et Xp n cessite un appel Il faut donc au moins a 2n4 2 a 2n8 2 sup 2na 1 2n8 1 n 3 2 inf na ng pour compl ter Au total il faut donc n 1 na ng n 3 2 inf na ng 2n 4 sup na ng inf na ng gt 2 n 4 La r daction a t laborieuse mais il m a sembl tenir la bonne id e La r daction d finitive plus concise et plus livresque ne comporte plus que le 3 cas le 1 et le 2 en tant des cas particuliers On
40. a qu une seule variable dans la contrainte et on gagne du temps en n essayant pas cette r gle dans tous les cas o elle ne s applique pas Mais si elle peut s appliquer il faut l appliquer rapidement 4 L ordre d arr t Il indique qu il est inutile de poursuivre l ex cution d une s quence Cela est seulement utile quand on a une sous s quence issue d un test et que l on ne d sire pas revenir la s quence principale Par exemple apr s avoir fait l examen pr c dent d une contrainte contenant une seule variable on met un ordre d arr t parce que l on a tir tout ce que l on pouvait de cette contrainte et il est inutile voire n faste de faire davantage d essais avec cette contrainte 126 Actuellement ces ensembles de s quences d actions sont d finis pour des groupes de probl mes manuellement Mais le but long terme est qu ils soient d termin s a priori en examinant les caract ristiques du probl me partir de sa d finition formelle et am lior s partir de ce que le monitoring a observ au cours des premi res r solutions de probl mes de la famille Le syst me se comportera de plus en plus comme un expert au fur et mesure qu il construira des s quences d actions de plus en plus efficaces 5 Impl mentation du syst me MALICE re oit l nonc d un probl me et les ensembles d ordres ex cuter pour chaque v nement qui peut se produire enl ve
41. align s MERS dans cet ordre dans cet ordre init 3 init 4 b mil a m m mil b d objet initial No init 5 1 40E 01 3 40E 01 n ud d velopp ailleurs RTGOTE ARAIQNE abc aigu d veloppement d un n ud jaune cr ation d objet par une r gle heuristique Annexe3 Exemple d objet cr ici le point h par le syst me pour les besoins de la preuve et la fa on dont le syst me l introduit dans l explication Enonc en fran ais activit 2 ex no3 p 217 Terracher seconde Hachette dition 94 ABC est un triangle Le point I est le pied de la bissectrice issue de A Sur une figure sont indiqu s U et V les projet s orthogonaux se I sur AB et AC En calculant de deux fa ons chacune des aires aire AIB et aire AIC montrer que IB IC AB AC th222 ENONCE donn au syst me triangle a b c et bissInt b a c droite a i et i app droite b c et projeteOrthog i droite a bj u et projeteOrthog i droite a c v gt longueur i b longueur i c egal longueur a b longueur a c HYPOTHESES DE DEPART les trois points a b c forment un triangle bissInt b a c droite a i i est sur la droite droite b c u est le projet orthogonal de i sur la droite ab 163 v est le projet orthogonal de i sur la droite ac CONCLUSION d montrer 1 longueur i b longueur i c longueur a b longueur a c DEMONSTRATION Soit h le projet orthogonal du point a sur la droite bc objet i
42. aucune autre id e dans un premier temps Puis j ai l id e d observer les cons quences du d placement du point M as Pour simplifier d abord le long du segment MA on pourra ensuite A 91 d composer un d placement en deux sous d placements le long de MA et MB Si MM d MA augmente ou diminue de d MB augmente ou diminue de d cos al o al angle AMB MB augmente ou diminue de d cos AMC soit d cos 01 02 o A2 angle BMC On arrive ainsi une variation de d multipli par 1 cos AMB cos AMC cos AMD cos AME ou A 1 cos al cos 1 2 cos a1 a2 3 cos 1 a2 03 a4 c Avec petit raisonnement sur les signes selon que les angles sont aigus ou BD obtus Pour un d placement quelconque de M on aura cos O0 cos a0 a1 cos H0 a14 02 cos H0 a1 02 03 cos H0 a1 02 03 a4 avec O0 angle M MA Il reste donc a montrer que cette somme est nulle Je remarque que ces angles sont apres les angles du pentagone ol Evaluer cette somme est imm diat mais je n ai pas eu tout de suite la bonne id e simple Ces angles ne sont pas quelconques puisque les c t s sont gaux En fait deux angles sont quelconques et les autres sont fonctions de ces deux angles On va donc essayer de les calculer Une premi re relation est simple a B y Il faut une autre quation pour tout conna tre en fonction de aet B Des calculs compliqu s suivent en utilisant la formule do
43. aux autres erreurs jug es instructives Nous affirmons que la conception d une interface p dagogique doit reposer sur une analyse pr alable des erreurs possibles et nous proposons une m thode de conception fond e sur ce principe Nous illustrons cette m thode dans le contexte d interfaces pour r soudre des exercices de d nombrement Nous avons r pertori et cat goris les erreurs possibles ce qui n est pratiquement r alisable que si l on se fixe d abord un cadre pr cis une classe de probl mes une m thode de r solution et un mod le conceptuel rendant la r solution quivalente l dition d un objet structur Cela permet d identifier les concepts autour desquels doit tre organis e l interface et qui vont correspondre aux boutons de validation propos s l l ve Nous montrons ensuite comment impl menter la gestion des erreurs l aide d un agent p dagogue Mots cl s interfaces p dagogiques erreurs m thode de conception EIAO d nombrement 1 Introduction Le projet Combien a pour but de d finir une m thodologie de conception de diff rents composants d un EIAO Environnement Interactif d Apprentissage avec Ordinateur Pour valider nos r flexions nous r alisons un EJAO pour l apprentissage des d nombrements Les exercices correspondant sont de la forme Etant donn s des ensembles servant de r f rentiels compter dans un certain univers les l ments v rifian
44. c demi diagonales de m me longueur 4 2 2 Exemple de d veloppement d un n ud D veloppement d un n ud Ceci est un extrait du graphe le graphe complet est en annexe 2 etiquette 57 long2 long fils 57 init 4 fils 57 19 fils 57 54 fils 57 8 provientDe 57 triangleRectangleDeduction etiquette init 4 milieu b d m etiquette 19 dr2 orthog dr fd L bc etiquette 54 longueur seg6 long2 mf long2 etiquette 8 longueur seg long smb long hyp 0 segment m b seg 7 hyp 0 segment m f seg6 53 hyp 0 droite b c dr init 1 hyp 0 droite f d dr2 16 L explication fournie sera alors mf mb car les droites fd et bc sont 139 perpendiculaires et m est le milieu du segment bd en effet dans un triangle rectangle le milieu de l hypot nuse est le centre du cercle circonscrit 19 init 4 54 fd L bc m mil b d mf long2 Un commentaire li au niveau de l utilisateur peut tre associ a la r gle et donne une explication compl mentaire Une m me r gle peut avoir plusieurs commentaires diff rents suivant le niveau de classe On n explique pas de la m me fa on une connaissance math matique au coll ge et au lyc e par exemple Il y a possibilit de demander au syst me une r daction dans un certain esprit en pr cisant des domaines prioritaires On sait bien qu un m me probl me
45. case vide qui peut tre consid r comme un bloc suppl mentaire de une case placer il s agit alors de recouvrir enti rement le quadrillage 97 On s aper oit facilement qu elle ne peut se situer ni dans un coin ni sur un bord car on ne pourrait pas l entourer avec les autres blocs On la met donc distance des bords et on regarde comment on peut l entourer Il semble n cessaire de proc der de la fa on suivante J essaie alors de compl ter ce sous ensemble 5x5 par un quadrillage 6x6 et par un 6x11 et je m int resse aux blocs de 6 c est dire 4 2 ou 3 3 ou 2 2 2 J en mets 3 dans le 6x6 et essaie de remplir des 11x2 dans le 11X6 Je n y arrive pas et m aper ois que c est impossible car je mwai plus assez de 3 Il manque toujours 1 pour obtenir 11 En effet il faut un impair il y a un seul 5 et je n ai plus de 3 Ceci est vrai quel que soit l endroit o l on place le 5x5 tant donn le nombre de lignes horizontales et verticales compl ter J exploite alors l id e de la parit pour r soudre le probl me de d part de la fa on suivante En consid rant la case vide comme un bloc 1x1 placer il faut obtenir 22 fois la somme 11 Les seuls impairs sont un 5 largeur 2 2 flottes trois 3 largeur 2 2 flottes un 1 largeur 1 2 sens On ne pourra alors obtenir que 1X2X2 3x2x2 1x2 18 sommes impaires Le probl me est donc impossible L id e
46. ces programmes certaines des informations figurant dans la d finition de la r gle mais pas forc ment toutes par exemple quand on envisage d envisager une r gle on ne met pas les actions qui sont effectu es quand toutes les conditions sont satisfaites De m me on ne met que les conditions que l on peut valuer sans utiliser les variables qui peuvent tre cr es avec des valeurs multiples par les expressions d instanciation parce qu elles sont d finies comme l ments d un ensemble ce qui tait le cas de X pour la r gle R2 Par contre quand on veut envisager un essai on inclut les expressions qui permettent de d finir toutes les variables n cessaires Comme les programmes ainsi cr s peuvent d cider de stocker le nouvel essai le syst me y inclut aussi le calcul de la valeur des priorit s associ s ENVENV ou a ENVISAGE selon les cas Par exemple si l on conna t un n ud D on aura les contraintes qui contiennent ce 127 n ud en ajoutant RE CONTRAINTES D Dans le cas de ENVISAGE on a besoin de d finir la valeur de toutes les variables qui seront n cessaires pour l ex cution par exemple la valeur de l expression valeur de X pour la r gle R2 c est dire qu il faudra aussi ajouter une expression permettant de d finir X en balayant les l ments de la somme cela est inutile pour le cas ENVENV qui ignore la variable Xi C est pour cela que l on y gagne s rier les examens le cas
47. consid rable faire un choix qui ne fera gagner qu un temps minime Il faut donc que le monitoring soit contr l comme le r solveur de probl mes il doit tre lui m me monitor Nous devons toutefois carter le risque d une ascension infinie des niveaux m ta Nous utilisons d abord les m mes m thodes pour monitorer la r solution d un probl me et pour monitorer le monitoring on a donc ainsi un seul fichier de m taconnaissances Mais nous les restreignons dans le cas du m tamonitoring de fa on viter s rement d y passer un temps Par exemple nous pouvons limiter les risques de d rives en interdisant dans le cas du m tamonitoring toute possibilit de changer les s quences d actions d finies au d part Il est utile de faire des propositions de changements mais elles ne seront pas utilis es automatiquement pour changer les m ta expertises elles serviront seulement aider l utilisateur qui souhaite changer certaines s quences de m tamonitoring quand le monitoring fonctionne mal Dans le cas du m tamonitoring les v nements ne sont plus la d couverte d une nouvelle contrainte ou l enl vement d un lien possible Ils sont l apparition d une surprise par exemple l chec d une m thode reconnue comme s re ou la constatation que l utilisation des cons quences d un v nement demande un temps bien plus grand que ce qui est pr vu ou habituel Pour chaque v nement de monitoring comme
48. d abord sur des choix abstraits de haut niveau qui lui permettent ensuite de limiter le nombre de possibilit s concr tes envisager Par exemple dans un jeu de strat gie il se demandera tout d abord s il doit plut t attaquer ou d fendre Dans le premier cas il pourra ensuite r fl chir la zone la plus prometteuse pour une offensive Il n aura plus alors qu consid rer les mouvements qui permettent d attaquer cette zone et ignorera tous les autres Pour pouvoir transmettre une expertise humaine un syst me il faut donc que celui ci puisse travailler sur des choix abstraits Ces choix se rajoutent dans le graphe d tats en le contraignant cf Figure 4 mais ne feront pas partie de la solution finale qui ne comprend que les choix concrets Dans ce papier nous ne nous int resserons qu la gestion des choix abstraits et non celle des choix concrets La fa on dont le syst me prend des d cisions concr tes est en effet pr sent e en d tails dans Pann rec 00 Nous supposerons donc qu en fonction des choix abstraits effectu s le syst me g n re l ensemble des choix concrets d finissant la solution associ e Choix abstrait 2 choix 2 choix P21 P21 P22 3 choix 3 choix 3 choix 3em choix P31 P32 P32 P32 P31 P32 O WO Figure 4 Graphe d tats avec choix abstraits 59 2 4 Le raisonnement hypoth tique Dans le syst me MARECHAL les possibilit s associ es a
49. de l nonc en cas de conclusion conjonctive construction des pr dicats de v rification des hypoth ses et des objets nomm s v rification de non pr sence du fait d duire ajout de la partie action et m morisation nom de la r gle hypoth ses dont provient le nouveau fait d duit et mod le explicatif R gles de type cr ation o certains des objets n cessaires sont absents d finir les objets que l on pourra cr er en cours de preuve concepts objets cr ables constituer la m me partie condition que dans les r gles de d duction sauf pour la v rification des objets n cessaires la r gle v rifiera la pr sence de tous les objets sauf un pour lequel la non pr sence donnera comme partie action sa cr ation m moriser la r gle qui a amen cette cr ation et les conditions de la cr ation R gles de condition suffisante pour chaque concept d ductible par une d monstration on balaie l ensemble des propri t s et pour chaque propri t o figure une conclusion d ductible on fabrique une r gle de condition suffisante 148 6 4 Exemples de r gles construites L exemple pr c dent donnera les r gles suivantes crites en fran ais pour leur lisibilit voir annexe4 D duction si G est centre de gravit de ABC avec I mil B C et que le syst me ne sait pas que G est sur la droite AI alors rajouter ce fait et m moriser la raison de son apparition Condition suffisante si on v
50. de mettre le syst me en mode apprentissage ce qui va consister charger la suite toutes les autres r gles priori plus loign es de l exercice en cours Le moteur d inf rences entre alors en action et va chercher instancier successivement chacune des r gles ayant t plac es dans la liste des r gles actives dans l ordre o elles se pr sentent en recommen ant au d but chaque fois que l une d entre elles se d clenche L utilisateur peut avoir s il le d sire donn un temps de recherche maximum pour l exercice Il peut avoir donn pour chaque r gle charg e un temps de recherche maximum au del duquel si la r gle d passe ce temps le syst me d cale la r gle dans la liste des r gles actives 2 3 D ductions du syst me Un nonc est crit sous la forme H et Hp et et Ha gt Ci et C2 et et Cg Le syst me l aide de r gles proc de un d coupage de l nonc et commence structurer la base de faits selon le principe de Muscadet qui correspond aussi la d marche du math maticien La base de faits se structure en une partie Hypoth ses o vont se rajouter tous les faits d duits partir des hypoth ses initiales par application des r gles charg es et d une partie Conclusions o figurent toutes les conclusions d montrer Chacune d elles sera mise vrai si le fait correspondant est d duit par l application d une r gle D autres r gles vont a
51. des deux c nes Ils peuvent alors constater que le c ne de Mathilde est deux fois plus haut que celui de Mathias Quelle est la valeur de l angle du secteur d coup par Mathilde arrondi au degr le plus proche Pour d ventuels calculs on prendra 2 236 pour J5 2 646 pour JT 3 317 pour NUL Mathilde 3 306 pour V13 et 3 1416 pour 7 Mathias Recherche Il s agit d valuer le rapport des hauteurs h et h des deux c nes sachant que l on veut avoir 2 Il est imm diat que l on a h R 100 et h R 100 o R et R sont les rayons des cercles de base licni D autre part la circonf rence du cercle de base est gale la longueur de l arc de cercle du secteur d angle ot Si on exprime en radians on a2mR 10Q0et27R 10 22 Q On pourrait peut tre exprimer Q autrement qu en radians on pourrait peut tre ne pas consid rer ce 10 qui n est pas significatif mais je crois gagner du temps en fon ant brutalement En liminant amp puis R on arrive facilement une quation du second degr en R pas tr s sympathique R 4 22 17 1 300 Connaissant R on trouverait a Je tire un trait et je recommence je vais plut t chercher directement une quation en amp Je fais alors une grosse erreur d tourderie de 100 2mR je tire R au lieu de Sa Sa T Cela conduit une quation du 4 degr en a J abandonne 83 J ai repris ce probl
52. des pas de d duction o intervient cette connaissance En utilisant les traces d exercices avec cr ation d objets ou non il faudrait que le syst me d couvre automatiquement de nouvelles propri t s et heuristiques de cr ation d objets qui resserviraient dans des circonstances analogues et rajouteraient automatiquement de nouveaux th or mes Mais comment Argos va t il juger de la qualit de ce qu il va retenir La communaut des math maticiens met souvent bien longtemps pour reconna tre l importance de tel ou tel th or me 12 BIBLIOGRAPHIE Bazin 93 J M Bazin GEOMUS un r solveur de probl mes de g om trie qui mobilise ses connaissances en fonction du probl me pos Th se universit Paris 6 Pastre 84 D Pastre MUSCADET Un syst me de d monstration automatique de th or mes utilisant connaissances et m taconnaissances en math matique Th se d tat Paris VI 1984 Pastre 89 D Pastre MUSCADET an automatic theorem proving system using knowledge and metaknowledge in mathematics Journal of Artificial Intelligence 38 p 257 318 1989 Pastre 93 D Pastre Volume 8 No 3 4 p 425 447 1993 Pastre 99 D Pastre Le nouveau MUSCADET et la TPTP Problem Library Actes de Berder 1999 Pintado 94 M Pintado Apprentissage et d monstration automatique de th or mes Th se Paris 6 1994 Pitrat 90 J Pitrat M taconnaissances futur de l intelligence artificielle Editions Herm s 1990 Pitrat 99
53. deux entiers K et n tels que K lt n log 2 lt K log 1 005 C est parce que log 2 n est pas un nombre 109 fractionnaire que c est toujours possible Alors 2 x 10 lt 2 lt 2001 x 10 c est dire 2n 1 commence par 2000 Le th or me plus g n ral auquel il est fait allusion est le suivant Pour tout r el r pour tout il existe des entiers m et n tels que n lt m r lt n c est dire n n lt r lt m m n nn n n na f Je connais et je sais d montrer que lt r lt mais ici le d pend du d nominateur il m m diminue au fur et mesure que le d nominateur augmente et je n arrive pas d montrer ce r sultat J interroge des math maticiens de mon UFR Plusieurs ne voient pas comme a sans r fl chir Enfin deux math maticiens entament un dialogue que l on peut r sumer ainsi R 1 oui et a marche m me avec n oui mais pas avec quelconque a se fait avec des fractions continues c est le th or me de Hurvitz on le trouve dans Solutions to the theory of numbers par Hardy Right 1 5 pour c est v5 a vient des fractions continues n n L un d eux se d cide s int resser mon probl me plus simple On consid re l ensemble E n r n e N qui est inclus dans 0 1 o E x est la partie enti re de x Cet ensemble est discret ou infini On divise 0 1
54. deux sous ensembles A et B de cardinaux a et b l ments connexes reli s par un appel qui rend l ensemble connexe a et b tant au moins gaux 2 Plusieurs cas sont envisag s 88 1 cas la compl tude et la connexit sont me obtenues au n 1 appel entre al et bl qui n 1 bl B connaissent tout Il y a exactement deux a qui issent tout de A Id B L l La connaissent tout de A Idem pour B Le couple ere oi l a2 b2 est compl mentaire Il faut au moins a 1 appels b 1 appels a 2 b 2 1 a 1 a 1 1 n 3 pour compl ter Quelques remarques importantes se pr cisent d monstrations par r currence pour qu une comm re connaisse tous les potins il faut au moins n 1 appels Il y a alors au moins deux comm res connaissant tous les potins Si cette propri t arrive me exactement au n 1 appel il y en a exactement deux Si cette propri t arrive au n 1 p appel il y en a au plus 2p 2 si une comm re conna t tous les potins le graphe est connexe La r ciproque n est pas vraie la connexit peut arriver avant qu une seule comm re connaisse tous les potins Pour que le graphe soit connexe il faut au moins n 1 appels _ n 1 appel peut conduire la fois la connexit et la compl tude Intuitivement c est l optimal Mais ce n est pas n cessaire voir plus loin 2 cas le n 1 appel a0 b0 apporte la connexit mais pas encore la compl tude Il y
55. emp cher un autre remplacement Sur la situation gauche de la Figure 8 on suppose que les pi ces 37 et 53 mouvements blancs doivent tre remplac es pour tre utilis es dans une autre solution Les pi ces 35 et 47 peuvent a priori remplacer indiff remment ces deux pi ces mais en pratique sion remplace la pi ce 53 par la pi ce 35 mouvements gris la pi ce 37 ne peut plus tre remplac e par la pi ce 47 car celle ci n a plus de chemin valide on suppose que les unit s se d placent ici de deux cases au maximum Sur la situation droite de la Figure 8 la pi ce 35 peut remplacer les pi ces 37 ou 47 Si l on choisit de remplacer 37 la pi ce 47 peut ne plus tre rempla able par une autre pi ce et l annulation de son mouvement peut conduire a Les num ros des pi ces sont affich s en bas droite de chacune d elles 64 d grader fortement la solution Il faut alors se demander si la pi ce 37 ne pouvait tre remplac e par une pi ce diff rente de 35 ou si l annulation de son mouvement n est pas moins pr judiciable que celui de 47 Il n existe videment pas de m thode pour obtenir directement la meilleure solution dans tous les cas Seules des heuristiques plus ou moins imparfaites peuvent guider le raisonnement et elles n cessitent souvent des retours en arri res Mais ces retours arri res doivent tre limit s au maximum car l exploration exhaustive des possibilit s serait beaucoup trop longue Le nombre d
56. en fran ais qui soit adapt e son niveau math matique Nous remercions Fabrice Kocik et Tristan Pann rec qui ont parfaitement pris en charge l organisation mat rielle de ce colloque Merci aussi Fabrice Kocik qui s est charg de l dition de ces actes Jacques Pitrat Des Optimisations de l Alpha B ta Tristan Cazenave Laboratoire d Intelligence Artificielle D partement Informatique Universit Paris 8 2 rue de la Libert 93526 Saint Denis France cazenave ai univ paris8 fr R sum Nous passons en revue les principales optimisations apport es l algorithme Alpha B ta Nous pr senterons tout d abord le minimax puis le n gamax ensuite l Alpha B ta lui m me Nous voquerons ensuite les optimisations classiques comme l approfondissement it ratif les tables de r futations la quiescence l ordonnancement les coups nuls les fen tres nulles les tables de transpositions Nous en viendrons alors a d crire nos propres optimisations qui permettent des gains tr s cons quents la recherche abstraite de preuves et l largissement it ratif Mots cl s Alpha B ta recherche abstraite de preuve largissement it ratif 1 Introduction Nous nous int ressons l optimisation de la recherche arborescente et plus particuli rement des arbres Min Max Les techniques d velopp es pour cette sorte d arbre peuvent se r v ler directement utiles ou tre la source d autres id es pour des syst mes
57. es Je signale galement une id e qui m a t donn e par Jean Yves Lucas apr s la premi re pes e concluant sur que l on num rote 1 2 3 4 567 8 on p se bbb5 T 4678 On obtient ainsi des informations la fois sur les pi ces 4 et 5 qui ont t chang es et sur les pi ces 123 qui ont t remplac es par bbb Si la balance penche gauche on a 678 si elle penche droite 4 57 s il y a quilibre 1 23 On m a aussi indiqu que ce probl me tait analys dans Farreny 87 qui est un livre que je pensais pourtant bien conna tre mais j avais oubli que ce probl me y figurait Il illustre en effet le choix heuristique d un sous probl me dans un arbre ET OU La th orie de l information conduit choisir le sous probl me qui apporte le plus d information Appliqu ce probl me pour 8 pi ces les auteurs montrent que le meilleur choix au d part est de mettre 106 3 pi ces sur chaque plateau Cette m thode permet d crire un programme qui r soudra le probl me pour un nombre quelconque de pi ces Et c est certainement cette m thode qu a appliqu e Jean Marc Fouet et qui l a conduit une solution longue deux pages mais dont on est s r qu elle aboutira 7 D formation professionnelle ou M tar solution de probl me mal pos Dans l exemple suivant tonn e de trouver deux solutions j ai tout simplement abandonn un peu de rigueur dans l interpr ta
58. est pas qu une question de temps pass trop long dans une certaine direction qui oriente l expert dans une autre direction Comment lui vient il une nouvelle id e La possibilit d ordonner les r gles dynamiquement va influer sur l efficacit du d monstrateur Certaines r gles importantes pour la d monstration plac es loin sont oblig es d attendre que toutes les r gles pr c dentes ne puissent plus s appliquer pour entrer en action Un moyen de r gler ce probl me est la possibilit d appeler des conjectures avec cr ation d objet partir de r gles v rifiant la pr sence de conditions particuli res favorables en fonction du but Dans l exemple d taill cela serait d appeler la conjecture b mil f c voir section 3 1 10 4 Cr ation d objets en cours de d monstration Il s agit l du principal probl me en DAT La cr ation d objets pour le math maticien n a pas le m me co t que pour le syst me Pour ARGOS les r gles de cr ation sont plac es la fin et sont des jokers si le d monstrateur ne d duit plus rien probl mes d explosion combinatoire Comment apr s avoir d montr un th or me ayant n cessit des cr ations d objets le syst me peut il apprendre des heuristiques de cr ation qui lui feraient gagner du temps lors d autres exercices du m me type 10 5 Rep rer les l ments cl s d une d monstration Dans l exemple le verrou faire tomber est de
59. explication 1 Introduction Ce syst me est con u partir du syst me Muscadet Pastre 84 r crit en langage Prolog Pastre 99 de nom Puscadet ou Muscadet version 2 Il est ainsi possible gr ce la bivalence du langage Prolog d exprimer les connaissances de fa on d clarative et de faire du proc dural quand cela est n cessaire en particulier il devient possible d appeler des proc dures de calcul ce qui est parfois n cessaire en g om trie Il est destin une utilisation en EIAO pour permettre un l ve de lyc e d am liorer son intuition et d tayer sa recherche en lui permettant de proposer des conjectures v rifiables dans les limites des comp tences d Argos par le syst me partir d un nonc donn Il est 132 aussi destin aux professeurs en leur permettant d exprimer les connaissances math matiques ainsi que des savoir faire heuristiques sur un th me donn de fa on d clarative et de concevoir des exercices s y rapportant De plus un gros effort d explication est requis pour ce syst me Il appara t en effet difficilement concevable qu un d monstrateur r solve des exercices et d montre des th or mes sans que les preuves puissent tre lisibles et v rifiables par un humain Dans cet article apr s de br ves remarques g n rales nous montrerons le fonctionnement g n ral et nous l illustrerons par un exemple d taill Nous montrerons ensuite comment le syst me recons
60. fran ais Soit abcd un trap ze avec ab cd Les droites ad et bc se coupent en o Soient i et j les milieux respectifs des segments ab et cd 1 Montrer que les points o i et j sont align s indication on pourra consid rer l homoth tie de centre o envoyant a en d 2 Montrer que les triangles cio et dio ont la m me aire th221bis niveau premi re S ENONCE donn au syst me trapeze a d c b et o estDans droite a d inter droite b c et milieu a b 1 et milieu d c j et hom o a d hom gt aire c i o egal aire d i o et j app droite o 1 165 HYPOTHESES DE DEPART adc b est un trap ze o est l intersection des droite a d et droite b c i est le milieu du segment ab j est le milieu du segment dc hom est l homoth tie de centre o envoyant a en d LISTE DES CONCLUSIONS d montrer 1 aire c i o egal aire d i 0 2 jest sur la droite droite o i DEMONSTRATION r ponse une conjecture ai bicari mil a b aire c i b aire d i a car les deux triangles ont chacun un sommet c et d sur dc etibi a align s sur a b parall le dc donc ils ont la m me hauteur avec i b 1 a comme base r ponse a une conjecture aire o i b aire o i a car les deux triangles ont un sommet commun o et i b i a align s avecib ia r ponse a la question no 1 aire 0 i c aire o i d car aire o i b aire o i a et aire o c b aire o d a r ponse a la ques
61. gi aux jeux ip le seul coup qui peut modifier une intersection vide au Go est de jouer dessus Toutes les intersections vides utilis es pour d finir un jeu gi sont donc des coups possibles du jeu ip associ Un jeu ip est associ a l ensemble des coups qui peuvent pr venir un jeu gi Ces ensembles abstraits de coups sont trouv s automatiquement par Introspect mais le code engendr est tr s volumineux Il serait int ressant de d velopper des outils permettant de d finir plus simplement avec des programmes plus concis ces ensembles 3 2 R sultats Exp rimentaux Les test comparatifs de l Alpha B ta et de la recherche de preuve abstraite ont t fait sur des ensembles de probl mes standards Kano 1985a b 1987 sur un ordinateur muni d un processeur K6 2 450 MHz Prevent ip3 1s 10000N correspond l Alpha B ta utilisant toutes ses optimisations stopp au bout d une seconde ou de 10000 n uds La fonction de s lection des coups est la m me que celle de la recherche abstraite de preuve l exception pr s que les d finitions de jeux ne sont pas utilis es pour s lectionner encore plus les coups Prevent ip3 ls revient au m me sans la barri re des 10000 n uds ip3 1s 10000N est l algorithme de recherche abstraite de preuves Algorithm Total time Number of nodes of problems Preventip3 1s Lo 109117 99 12 10000N Preventip3 1s borg 109117 99 12 ip3 1s 10000N 11 82 10340 99 12
62. id e tr s simple des aires n est pas apparue En ce qui concerne la solution trouv e on remarque que c est l id e fausse je ne peux pas avoir amp 1 O2 qui a conduit conduit la bonne id e il faut se concentrer sur cette somme 1 02 la faire appara tre directement 5 Chemins d tourn s et bonnes id es On verra dans le premier probl me un raisonnement g om trique absolument pas n cessaire mais qui a conduit aux bonnes relations alg briques Dans le deuxi me probl me la bonne id e de la parit n est apparue qu l occasion d un sous probl me simple mais cette id e est bonne pour le probl me initial et la d composition en sous probl mes est inutile Enfin dans le troisi me on voit appara tre des configurations plus complexes que n cessaire 5 1 La grande famille Le Monde 11 avril Affaire de Logique Probl me n 167 Le patriarche de cette famille a eu des enfants des petits enfants des arri re petits enfants et m me des arri re arri re petits enfants Tous sont vivants en bonne sant et sont venus souhaiter sans leurs conjoints l anc tre son anniversaire Des chaises ont t install es en carr il y a autant de chaises dans chaque rang e que de rang es de chaises et elles sont toutes occup es lorsque l anc tre se rassoit la fin de son discours Chose extraordinaire toutes les personnes r unies sauf bien s r les arri re arri re petit
63. la combinaison apr s avoir tudi les hypoth ses alors que la seconde fait les deux en m me temps Le but de ce papier tant de comparer ces deux m thodes la suite de l article sera consacr e d crire et tudier chacune d elle 3 Combinaison a posteriori Face au probl me de la combinaison des hypoth ses les m thodes classiques de raisonnement hypoth tique doivent tre compl t es et soutenues par des m canismes sp cifiques Dans la m thode a posteriori d crite dans cette partie le raisonnement est principalement compl t par une phase de combinaison des solutions obtenues par le raisonnement hypoth tique 3 1 Principe de l approche a posteriori Dans l approche que nous avons baptis e a posteriori le syst me commence par tudier ind pendamment chaque hypoth se pour un choix abstrait donn Il va donc poser comme hypoth se la premi re des diff rentes possibilit s et continuer son raisonnement sous cette hypoth se Une fois les cons quences d termin es le syst me revient au niveau du choix et recommence avec une nouvelle hypoth se Ce faisant le syst me va conserver une trace des hypoth ses envisag es et des cons quences valu es sous la forme d un arbre chaque n ud de cet arbre correspond un choix abstrait et chaque branche une possibilit pour ce choix Lorsque toutes les hypoth ses ont t valu es le syst me passe alors en phase de combinaison o il va c
64. la d monstration Ceci est r alis gr ce des r gles traduisant l expertise du domaine Lorsque le math maticien construit la figure il est d j en train de faire des d ductions et introduit donc les objets de fa on dynamique Le syst me n a pas cette possibilit et doit donc introduire une liste minimale d objets L introduction d autres objets ne se fera que si Argos n a plus rien d duire ceci par les r gles de type cr ation ou l occasion d appels de conjectures S il existe une strat gie pour montrer que acmf est un rectangle et si le syst me est dans une situation d j rencontr e les r gles correspondantes vont se d clencher et la d monstration va tre acc l r e Si les r gles appelant des conjectures ont t charg es et si le syst me rep re des configurations incompl tes ou situation propice susceptibles de faire avancer vers le but alors elles se d clencheront en cr ant ventuellement 157 de nouveaux objets Dans l exercice propos le syst me sait qu il doit montrer que acmf est un parall logramme et il sait aussi que b mil a m il pourra donc lancer si l utilisateur a s lectionn l option correspondante la conjecture pour montrer que b mil c f Ces appels de conjecture sont donc en g n ral guid s par le but Ceci est un moyen d introduire dynamiquement des objets un peu comme le fait le math maticien quand il construit la figure 3 4 D ductions par instan
65. la partie d cimale est inf rieure 1 2 et autant 112 dont la partie d cimale est sup rieure 2 Si on consid re les nombres r els il y en a plus dont la partie d cimale est sup rieure 72 mais par beaucoup le rapport est en effet gal CRT pee 2 Sil y en a 3 fois plus entre 0 et 1 et 40 de plus entre 1 et 4 il y en a p 14 4pH d ja moins de 10 en plus entre 25 et 36 Cela veut dire que la courbe ressemble tr s vite a une droite Ces remarques conduisent alors rapidement a une solution rapide du probl me mais elle n a t obtenue qu apr s plusieurs autres plus laborieuses a 0 ae p gow p l Y 2p 1 n p YF p p id p p l A p vn Do ae ee p l Vn 1 p gt p N pii P prl IntVn pp T p 2p lt p2p 2 p 1 p l On constate que l on saute p 2 p 1 p 1 9 Conclusion Ces analyses mettent en vidence que les probl mes ont rarement t r solus directement mais la plupart du temps apr s de nombreux essais t tonnements dessins cas particuliers La rigueur dans le d tail n est pas indispensable dans un premier temps Ce qui est important par contre c est de manipuler les objets math matiques et une id e m me inexacte permet de manipuler donc de progresser On voit aussi qu entre le plus court chemin vers la solution et des impasses sans espoir il y a des raisonnements inutilement compliqu s qui permettent aussi d
66. le suivent et qui 11 constitue sa r futation On a ainsi les s quences de coups qui sont jug e les meilleures pour les deux joueurs une profondeur donn e L heuristique consiste essayer les coups de la table de r futation en premier dans l arborescence Ce sont ceux qui ont le plus de chances d tre les meilleurs puisqu ils taient les meilleurs la profondeur pr c dente Or on a vu qu essayer les meilleurs coups en premier permet de maximiser le nombre de coupes Alpha B ta et donc de minimiser le temps de recherche 2 8 Le coup qui tue et l heuristique de l historique L ordre dans lequel on consid re les coups a une grande influence sur l efficacit de l algorithme Alpha B ta Un coup qui marche beaucoup mieux que les autres coups du m me niveau dans un sous arbre a de bonnes chances de bien marcher dans un autre sous arbre On va donc essayer ce killing move en priorit dans les sous arbres suivants Cette heuristique est utilis e dans de nombreux programmes de jeux entre autres Deep Blue et GoTools r solution de probl mes de vie et de mort au jeu de Go En g n ral les programmes d Echecs utilisent cette heuristique en m morisant le meilleur coup ou les deux meilleurs coups pour chaque profondeur de recherche Une g n ralisation des coups qui tuent est l heuristique de l historique history heuristic Schaeffer 83 89 Une note est mise jour pour chaque coup l gal rencontr da
67. m diane issue de A c est dire la droite AT Savoir faire associ savoirFaire centreGravite Pour montrer qu un point G est sur une m diane du triangle ABC montrer que c est le centre de gravit Exemple2 propriete general obligatoire reciproquePythagore si BC AC AB alors le triangle ABC est rectangle en A On a BC AC AB donc le triangle ABC est rectangle en A savoir faire associ savoirFaire reciproquePythagore Pour montrer qu un triangle ABC est rectangle en A montrer que BC AC AB Exemple3 propriete calculVectoriel obligatoire seconde vectDroiteMilieux si I mil A B et J mil A C alors vect IJ 1 2 vect BC Puisque I mil A B et J mil A C alors vect I 1 2 vect BC Exemple4 propriete general fin anglesCorrespondants si AB CD et D O B et C O A alors les angles OAB et OCD sont correspondants les angles OAB et OCD sont correspondants car AB CD et D O B et C O A En effet ainsi B A et D C sont de m me sens 5 2 M canismes et heuristiques de v rification Chaque type d objet d fini comme concept g n re s il n en existe pas une proc dure de recherche de la pr sence d un tel objet dans la base de faits C est ce niveau que sont g r es les propri t s de sym trie Des heuristiques de recherche peuvent tre rajout es par l expert qui v rifieront certaines conditions
68. m me de r currence On construit le triangle suivant sur la ligne n on inscrit successivement le nombre de N zigzag se terminant par 1 par 2 par 3 par n Pour n 1 1 Pour n 2 0 1 Pour n 3 1 1 0 Pour n 4 0 1 2 2 On obtient chaque nombre de la ligne 5 en ajoutant tous les nombres de la ligne 4 qui se trouvent sa droite Pour n 5 5 5 4 2 0 100 En effet il y a autant de 5 zigzag se terminant par 1 que de 4 zigzag en d calant les chiffres d une unit Il y a autant de 5 zigzag se terminant par 2 que de 4 zigzag se terminant pat 2 3 ou 4 en d calant les chiffres partir de 2 d une unit etc De m me on obtient chaque nombre de la ligne 6 en ajoutant tous les nombres de la ligne 5 qui se trouvent cette fois 4 sa gauche Pour n 6 0 5 10 14 16 16 Le total de la sixi me ligne vaut bien 61 Plus g n ralement si n est impair la ligne se termine par 0 et si n est pair elle commence par 0 On obtient les nombres de la ligne n 1 en ajoutant successivement et alternativement de droite gauche puis de gauche a droite les nombres de ligne n Algorithmique astucieux Comment en avoir eu l id e 6 Peut on compter sur la m moire On verra deux exemples o la m moire a imm diatement permis de r soudre le probl me soit par r flexe soit parce que la solution repose sur une id e se trouvant dans un travail particuli rement int ressant dont je
69. m me qui doit assurer automatiquement le respect des conditions de validit associ es Par exemple si une condition de validit non instructive sp cifie qu un nombre x doit tre un nombre entier compris entre 1 et 5 l interface pourra offrir l l ve un menu avec les cin 2 28 valeurs 1 2 3 4 5 pour la saisie de x plut t qu un champ de texte o l l ve dite librement un texte quelconque Notons que cette configuration de l interface pour satisfaire les conditions de validit peut tre dynamique si une condition sp cifie que x doit tre un entier compris entre 1 et y et que l l ve a saisi y le menu pour x sera mis jour pour comporter la liste des entiers de 1 y 4 3 Aspects dynamiques et interactifs La saisie de la solution par l l ve est vue comme une t che d dition d une structure arborescente Avec les structures que nous consid rons cette t che n est pas atomique ni imm diate Elle passe par diff rentes tapes qui permettent d engendrer la structure compl te petit petit incr mentalement Pour tenir compte de cet aspect nous avons construit des interfaces qui prennent en compte les erreurs de fa on incr mentale Cela est adapt au type de t che demand mais aussi et surtout cela permet de profiter le mieux possible des instants o l l ve est dans une situation d apprentissage optimale c est dire au moment o il commet des erreurs L i
70. me plus tard t te repos e et de t te Je fais d abord quelques simplifications c est un des avantages du travail de t te on est forc de simplifier 1 au lieu de 10 1 dm si l on veut mais aucune importance Q pourcentage de la circonf rence au lieu de la valeur en radians pour ne plus avoir de 1 on a tout simplement R a et R 1 a rapport k au lieu de 2 pour pouvoir v rifier des valeurs triviales 0 1 rapport inverse pour avoir un d nominateur plus sympathique que le d nominateur soit I R H a 1 R l a 2 h 2 K J arrive une quation simple du second degr k7 1 a 2 a k 0 On voit l int r t des simplifications Une v rification donne bien pour k 0 a 0 erreurs vit es pour k 0 a 1 v rifications faciles pourk 1 a Autre avantage du travail de t te comme on n est jamais absolument s r de son calcul on amp J fait des v rifications Il y a une racine positive l k4 k 4 1 Qa gt _ _ _ __ Ra de nouveau v rification pour k 0 1 avec k 2 ts fs de t te encadrement de V13 entre 3 et 4 puis entre 3 6 et 3 7 d o entre 0 87 et 0 9 soit un peu plus d un dixi me de tour pour 1 o Ayant retrouv papier crayon et avec les donn es du texte 13 3 606 je trouve amp 0 8687 soit en degr s 313 Non le du texte est aigu j ai interverti les deux c nes la r ponse est 1 amp 47
71. me souvenais tr s bien Dans un autre exemple la m moire n a servi rien parce que je n avais pas moi m me trouv la bonne id e dans le pass et que les points cl s n avaient pas t d gag s Maintenant que j ai r solu moi m me avec difficult ce probl me je pense que je me souviendrai longtemps des points cl s 6 1 Le carr inscrit Le Monde 28 mars Affaire de Logique Probl me n 165 Il n y a qu une fa on d inscrire un carr dans un triangle ABC de telle sorte que deux des sommets soient sur AB un troisi me sur AC et le quatri me sur BC Sauriez vous tracer un tel carr l aide d une construction g om trique simple Je me souviens imm diatement que c est un probl me de construction r solu par le programme de la th se de Buthion 1975 au moyen d une m thode tr s int ressante utilisant les transformations g om triques et en particulier l homoth tie 19 3000 instructions Fortran 68 r gles plusieurs modules sp cialis s dont un module homoth tie 141 probl mes propos s 119 succ s 101 On dessine un carr respectant les contraintes sauf une un des sommets du carr n est pas sur le triangle Par une homoth tie dont il faut trouver le centre et le rapport on transforme ce carr dans le carr cherch La raison pour laquelle je m en souviens si bien tient sans doute au fait que j ai t impressionn e par le
72. moiti est bonne 2 on recommence avec 272 2 ou 1T1 4 3 puis avec 1T1 2 4 enfin on p se une des billes du paquet de 2 dans lequel on sait que se trouve la fausse pi ce avec une bonne pi ce Si c est elle on sait de plus si elle est plus lourde ou plus l g re Si non on sait que c est l autre sans savoir si elle est plus lourde ou plus l g re il faut une 5 pes e pour conclure Ce raisonnement marcherait aussi pour16 billes On a l impression qu avec seulement 12 on pourrait faire mieux et surtout on n exploite pas l information recueillie en cas de d s quilibre d un c t il ne peut y avoir qu une plus lourde de l autre qu une plus l g re D o une id e qui semble meilleure un tiers sur chaque plateau et un tiers restant 474 4 103 S il y a quilibre on ramen au probl me pour 4 et on d masque la fausse pi ce en 2 pes es sinon on doit consid rer le probl me pour 8 pi ces mais en sachant qu on a une lourde parmi 4 ou 1 l g re parmi 4 autres N anmoins je n avais pas pu faire mieux Le Monde donnait une solution en 3 pes es et je me souvenais que je l avais trouv e compliqu e Je ne me souvenais pas si je l avais analys e ou si j avais remis l analyse plus tard et oubli e Je ne me souvenais pas si l on pouvait conclure coup s r si la fausse pi ce tait lourde ou l g re Et je ne me souvenais absolument pas de la dite solution
73. ne se d composent pas en somme de deux nombres gt 1 cad l ensemble des comm res ne peut pas tre partag s en deux sous ensembles dans lesquels on 90 trouvera deux comm res connaissant tout de leur sous ensemble Des id es fausses ont ainsi conduit aux bonnes id es quelquefois simplement en pr cisant le raisonnement entrevu Id es fausses Bonnes id es d coupage en deux morceaux 2 et 4 particuliers 4 cause de 2 Mais ce qui est important car mauvais c est 1 D coupage n cessaire n 4 4 puis n 2 2 puis D coupage a b a gt l b gt 1 La compl tude est la propri t essentielle puis La connexit est la propri t la plus La connexit aussi et elle doit arriver i eae a a compl tude en m me temps que la compl tude puts 4 2 Invariant pentagonal Le Monde 15 f vrier Affaire de Logique Probl me n 159 Le pentagone convexe ci dessous a ses cinq c t s gaux leur longueur est un m me nombre a A un point M int rieur au pentagone on associe MA MB MC MD ME somme des distances de M aux cinq c t s du pentagone ou leurs prolongements Sauriez vous expliquer pourquoi cette valeur ne d pend pas du choix du point M La propri t est elle conserv e si le pentagone a cinq angles gaux sans que les c t s le soient Ce probl me a une solution imm diate voir la fin mais je n en ai pas eu l id e ni m me
74. particuli res de la pr sence du concept 1 Par exemple le but plg N A B C D Q les majuscules repr sentant des variables recherchera la pr sence d un parall logramme ABCD avec les variables partiellement compl tement ou pas du tout instanci es Le but est atteint si on a en hypoth se l une des huit fa ons de traduire que ABCD est un parall logramme 144 2 memeSens N A A1 B B1 Q v rifie si les vecteurs AA1 et BB1 sont de m me sens dans certaines conditions concr tes comme par exemple la situation de la figure ci O dessous 3 centreGravite N A B C G Q recherchera un centre de gravit B Voici un exemple de recherche d instanciation de ia partie condition d une r gle rajoutant qu un centre de gravit est sur chaque m diane R gle utilis e En fran ais Si I mil B C G est le centre de gravit du triangle ABC J est la droite AT et si on ne sait pas que I est sur la droite AT alors rajouter l hypoth se qu il y appartient Dans la syntaxe du syst me r gle g n r e automatiquement regle A centreGraviteDeduction B milieu N B C I F SI mil B C centreGravite N A B C G Q G centre de gravit de ABC droite N J A I K J AT not hyp N G app J L on ne sait pas que G e AT ajhyp N G app J M Srajouter que G AT memoriser centreGraviteDeduction F Q K M memoriserExpl obligatoire H Test 1l centr d gravit
75. pas de prime abord m me au yeux de l expert devant la figure l tat brut Il doit cr er k le milieu de a b langle adk les droites kd et ek et en plus il devrait penser lui m me introduire la r flexion d axe la m diatrice de ad Quelles heuristiques de cr ation d objet va t il pouvoir apprendre qui pourront lui tre utile dans d autres situations semblables sans pour cela g n rer d explosion combinatoire dans tous les autres cas C est un probl me ouvert qui n a pas de solution satisfaisante pour le moment On peut seulement lui donner par exemple l heuristique suivante Si un triangle est isoc le si le milieu d un c t autre que la base existe alors cr er son sym trique par rapport a l axe de sym trie Ceci pourra servir souvent Mais on ne peut pas 152 cr er de fa on syst matique tout axe de sym trie d une figure donn e Pourtant l expert a toujours ces consid rations pr sentes et pr tes servir 9 Utilisation d ARGOS en EIAO 9 1 Probl matique En quoi le syst me peut il aider un l ve progresser dans l art de chercher et r soudre un exercice de g om trie Il va de soi que fournir une preuve r dig e m me obtenue automatiquement d un exercice donn n a que peu d int r t d un point de vue p dagogique Il faut donner la possibilit l l ve de construire lui m me sa solution et d en construire une r daction On sait d ailleurs que la principal
76. pour hypoth se la conjonction des deux hypoth ses combiner Il n y a alors plus ind pendance dans l tude des hypoth ses et cela nous conduit l approche a priori qui est pr sent e dans la quatri me et derni re partie de ce rapport 4 Combinaison a priori Pour r soudre le probl me de la combinaison d hypoth ses nous avons vu dans la partie pr c dente qu on pouvait utiliser une approche bas e sur l tude des hypoth ses ind pendamment les unes des autres et sur une phase de combinaison a posteriori Dans cette partie nous allons d crire puis analyser l approche oppos e qui consiste tudier les combinaisons des hypoth ses en m me temps que ces hypoth ses sont envisag es Pour ce faire celles ci ne seront plus envisag es ind pendamment les unes des autres Cette deuxi me approche est actuellement en cours d impl mentation dans le syst me MARECHAL pour remplacer celle de la partie pr c dente 4 1 Principe Le principe de l approche a priori consiste donc combiner les hypoth ses lors de leur tude En th orie le syst me passe ainsi en revue toutes les possibilit s de combinaisons selon une exploration combinatoire Cela signifie que dans la trace de raisonnement g n r e chaque choix abstrait sera repr sent par un sous arbre et non par un n ud simple comme c tait le cas dans l approche pr c dente cf Figure 12 On voit tout de suite que la trace est b
77. pr sente la partie du cours dont il a besoin le cours correspondant la classe de la machine Ainsi tout moment de l utilisation de notre interface l l ve peut interroger au moyen du bouton le le syst me et obtenir soit le cours soit l explication d utilisation de la machine soit l explication de l erreur qui vient de lui tre signal e Dans nos machines chaque contexte de validation est associ un bouton le Associ chaque machine il y aura donc un cours distribu r parti et pr sent par n cessit et opportunit De cette fa on une m me notion pourra tre pr sent e de fa on diff rente selon le contexte Les figures 7 et 8 montrent au moment de la validation de l univers les aides propos es l l ve respectivement du point de vue du cours et du point de vue de l interface 34 aa Au sujet de l Univers Math matiques H Interface is 2 Rois 2 V 2 main de amp ca L univers est l ensemble des configurations parmi lesquelles on choisit celles qu on veut Dans cette machine l univers est toujours l ensemble des parties n l ments d un ensemble E ts prises dans On vous demande de donner n et E Voici un exemple d Univers l ensemble des parties 4 l ments d un jeu de 32 cartes Figure7 ER Au sujet de l Univers Math matiques Pour d finir un univers il faut donner deux informations un nombre n qu on choisit dans un menu un ensemble E qu on choi
78. prouver que b mil f c Comment un syst me informatique pourrait il rep rer ces n uds de difficult s pour se focaliser sur eux et faire de bons appels de conjecture Ceci pourrait aussi aider pour la preuve r dig e et ne pas placer tous les n uds de d veloppement sur le m me plan 10 6 Interactions homme machine Pour une utilisation en EIAO il faut aussi envisager une interface conviviale avec construction de la figure qui permette au professeur de donner les connaissances au syst me sans efforts particuliers et l l ve de poser ses probl mes confirmer ses id es explorer les diff rentes d ductions possibles partir de l nonc donn et avoir une explication sur tout fait d ductible Il faudrait en particulier que partir d un nonc livresque le syst me aide l l ve extraire les hypoth ses donn es et lui permette d crire l nonc sans avoir un 156 certain langage d expression des connaissances apprendre Un syst me de menus d roulants avec bo tes de dialogue et messages d erreurs ou de confirmation devra lui permettre d introduire les objets en n ayant sa charge que l instanciation concr te de ceux ci 11 Bilan partiel et perspectives 11 1 Bilan Apr s une premi re version o la base de r gles avait t crite la main test e et mise au point sur des exercices niveau lyc e la deuxi me version avec construction automatique de r g
79. que les essais n ont pas tre d finis tout de suite Les X ne sont consid r s que quand on envisage la r gle pas quand on envisage de l envisager Il suffit donc de compter les variables dans la contrainte foyer et de placer l examen approfondi une tape ult rieure qui sera d autant plus proche que le foyer contient peu de variables Des priorit s d finies en utilisant le nombre de variables d une contrainte sont fr quentes on pr f re toujours les contraintes qui ont peu de variables E contient un seul l ment permettant de calculer la variable Q qui est le nombre de 125 variables apparaissant dans R Cela signifie que l on va envisager la r gle R2 avec pour valeur de la variable R de cette r gle la nouvelle contrainte engendr e que la priorit pour l envisager sera lev e si elle ne contient que deux variables et tr s basse si elle en contient 6 la fonction CARVAR calculant le nombre de variables diff rentes apparaissant dans l expression qui est son argument Si la contrainte a une seule variable ou plus de six variables la r gle R2 ne l examinera pas du tout puisque la priorit ne sera pas d finie Quand on ex cute un ordre on met en attente d ex cution les essais ainsi d termin s chacun avec leur priorit P qui est valu e en tenant compte ventuellement des expressions qui sont dans l ensemble E L utilisation d un ordre ENVENV se fait donc en deux temps d abord une
80. r gles de condition suffisante de la conclusion permettant de conclure rapidement si un crit re suffisant de la conclusion est utilisable dans la base de faits Il charge ensuite la ou les listes de r gles appel es strat gies ayant t constitu es partir de toutes les r solutions d exercices de m mes buts que l exercice en cours ARGOS doit maintenant charger les r gles qu il juge utile pour la d monstration et qui n ont pas encore t choisies Ce sont les r gles obligatoires avec la terminologie Muscadet En fonction des concepts pr sents en hypoth se il charge des r gles de d marche en avant Ces r gles extraient de la figure toutes les configurations pr gnantes sans tre guid es par le but Pour les concepts figurant en conclusion il cherche celles de d marche en fonction du but Le d monstrateur peut ensuite charger les r gles appelant une conjecture Ces r gles se d clenchent si le syst me d tecte des configurations incompl tes et int ressantes en fonction 134 de ce qu il y a d montrer Ceci est une option que peut choisir un utilisateur et il doit alors l indiquer au syst me Le syst me va charger enfin des r gles un peu plus dangereuses de cr ation d objets dont la pr sence n est pas vue comme n cessaire par simple analyse de l nonc mais qui sont susceptibles de servir l application de r gles utiles pour l exercice en cours Un utilisateur a la possibilit s il le d sire
81. s agit de rendre le d monstrateur suffisamment robuste pour qu il puisse servir en EIAO Il appara t n cessaire de cr er une interface utilisateur sur poste fixe ou par internet pour pouvoir vraiment tester cette robustesse et v rifier l int r t p dagogique que peut apporter un tel syst me Il est possible de guider pas pas la recherche d un l ve en partant du but partir d une preuve d couverte par ARGOS car partir de la conclusion on peut d velopper la preuve niveau par niveau On peut imaginer la possibilit de faire construire la figure 157 automatiquement par un couplage avec des logiciels comme GEOPLANW ou CABRI GEOMETRE par exemple Il faut impl menter des m thodes d apprentissage correspondant au savoir faire de l expert qui reconna t dans l exp rience pr sente des situations ant rieures d j rencontr es Dans une situation analogue on mettra en uvre des techniques semblables Ceci devrait permettre une meilleure s lection des r gles et des liens entre concepts et r gles applicables Un travail reste faire au niveau de l explication Il appara t essentiel de consid rer la t che d explication comme une t che de r solution de probl me part enti re Il faudrait que pour chaque connaissance rajout e dans la base le syst me soit capable de mettre jour automatiquement les r gles d utilisation de cette connaissance et les r gles permettant de donner des explications dans
82. thode tabou Th se de universit Paris 6 1997 Lobjois 99 Lobjois L Probl mes d optimisation combinatoire sous contraintes vers la conception automatique de m thodes de r solution adapt es chaque instance Th se de l ENSAE 1999 Pitrat 91 Pitrat J An intelligent system must and can observe his own behavior Cognitiva 90 pages 119 128 Elsevier Science Publishers 1991 Pitrat 99 Pitrat J Une exp rience de monitoring Rapport de recherche LIP6 1999 014 1999 Pitrat 00 Pitrat J Monitorer la recherche d une solution Actes du colloque Intelligence Artificielle de Berder pages 3 15 rapport interne LIP6 n 2000 002 2000 Pollock 89 Pollock J L OSCAR a general theory of rationality Journal of Experimental Artificial Intelligence vol 1 pages 209 226 1989 Schiex et al 97 Schiex T Fargier H et Verfaillie G Probl mes de satisfaction de contraintes valu s Revue d Intelligence Artificielle 11 3 pages 339 373 1997 Van Laarhoven et al 88 Van Laarhoven P et Aarts E Simulated annealing Theory and applications Kluwer 1988 76 Chemins d tourn s id es fausses et bonnes id es Dominique Pastre Crip5 Universit Ren Descartes Cet article est d di la m moire de Jean Marc Fouet R sum Dans le but d am liorer les syst mes d intelligence artificielle il peut tre int ressant d imiter le raisonnement humain Pour essayer de comprendre comment l
83. tude des situations les plus probables et prometteuses en priorit l tude des situations floues en priorit sur les situations claires dans le but d obtenir une description du monde en pr vision totalement claire Elles permettront de limiter la combinatoire en contr lant la recherche arborescente en largeur et en profondeur d avoir un meilleur contr le du temps faciliter l explication des solutions engendr es Apr s l application effective de ces id es sur le jeu de l ascenseur dans un premier temps nous pensons qu il faudra pousser plus loin la mise en place de m ta raisonnements intelligents pour le contr le de raisonnements de base par 52 la prise en compte du co t de d veloppement des arborescences la prise en compte des r gles du jeu une plus grande flexibilit sur le type d hypoth ses poser en particulier par un choix du niveau d abstraction du raisonnement Nous voyons en effet dans 4 3 que le raisonnement d un tre humain devient de plus en plus abstrait au fur et mesure de l avanc e en profondeur dans l arbre de recherche pour lesquelles les situations ont de moins en moins de chances de se produire r ellement 6 Bibliographie Berliner 79 Berliner H The B tree search algorithm a best first proof procedure Artificial Intelligence 12 1 p 23 40 Cazenave 00 Cazenave T Des optimisations de l alpha beta Actes colloque Berder 2000 Kocik 99 Kocik F
84. ve d avancer dans son apprentissage Pour chaque validation on tablit la liste des erreurs possibles et pour chacune d elles les informations apporter l l ve On a choisi ici de ne pas signaler d erreur pendant la saisie dans la zone On attend que l l ve ait valid sa r ponse Cela comporte un aspect s curisant pour lui cela signifie qu on ne l observe pas pendant son activit de saisie et qu on reconna t qu il est normal que celle ci puisse comporter des essais au brouillon des fautes de frappe et d inattention Par contraste cela souligne l importance accord e au concept valid Le nombre d l ments auxiliaires obtenir pour autoriser la validation ne doit pas tre trop grand Le d coupage en parties validables est un garde fou qui permet l l ve de ne pas s enferrer dans une succession d erreurs qui rendraient le diagnostic et les corrections trop compliqu s ou m me infaisables Par exemple nous avons choisi de faire valider l univers ensemble des mains de 8 cartes qui est compos d un r f rentiel et d un cardinal de fa on ce que l l ve ne puisse pas continuer s il n a pas choisi les bons ensembles de d part Le parcours est balis par les validations Dans notre machine par rapport la structure d crite figure 4 on a choisi de ne faire valider l l ve que le choix de l exercice celui de l univers de la construction et de chaque sous partie 5 3 Cho
85. voit alors que l optimal correspond au fait que le n 1 na ng appel conduit la fois la compl tude et la connexit comme attendu sinon aurait pris 2n4 2 au lieu de 2n4 1 dans le calcul mais qu il n est pas n cessaire que na ng 0 il peut suffire que na np Exemple avec na npg 1 n 8 a b 4 Cet exemple m avait chapp au d but de la recherche quand je cherchais recoller des sous ensembles de 4 je pensais qu il tait en 2n 3 Autre remarque le d coupage en n 2 2 ou n 4 4 n est pas toujours n cessaire pour avoir l optimal mais sans doute seulement pour n lt 4 Exemple n 6 a b 3 J ai souvent oubli dans les raisonnements que si une comm re connait tous les potins d un sous ensemble elles sont deux a tout connaitre On voit aussi que si a ou b 1 on n a pas l optimal En effet si a 1 na 0 il faut pour me compl ter apr s le n 1 ng appel au moins b 2 ng 2 2 ng 1 b 1 n 2 soit au total au moins n 1 ng n 22 gt 2n 3 Ceci par contre avait t per u d s le d but la comm re isol e voir r currence doit appeler la premiere et la derni re Derni re remarque si on avait a 2n4 2 lt 0 on remplacerait a 2n 2 par 0 et 2n4 2 par a et on ne pourrait qu augmenter la borne Finalement le nombre exceptionnel n est ni 2 ni 4 mais 1 et n 1 3 sont particuliers l optimal n est pas 2n 4 car ils
86. 0 110 ne seront pas quivalents Pour anticiper le r sultat le syst me se base sur l valuation de la solution partielle courante et sur les possibilit s d augmentation ou de d gradation venir Cette estimation est un point tr s d licat car il n est pas facile de pr voir les possibilit s venir Le syst me doit galement disposer d un encadrement du temps n cessaire pour terminer l exploration de la voie courante Si le gain anticip semble faible a priori la perspective d une recherche encore longue pourra conduire stopper l exploration de cette voie C est donc partir de la confrontation de ces deux encadrements aux r sultats d j obtenus et au temps de recherche encore disponible que le syst me va prendre la d cision de continuer dans la voie de recherche actuelle ou au contraire de chercher une autre voie de recherche Naturellement le syst me ne dispose pas toujours de ces informations d encadrement ou le temps d obtention de celles ci peut tre trop lev pour que leur d termination soit syst matique Dans ces cas le syst me continue alors par d faut la voie actuelle En outre l action de changer de voie est co teuse et doit donc s effectuer avec parcimonie uniquement lorsque le syst me est s r de sa d cision 4 2 2 Comment continuer dans la voie actuelle Si le syst me d cide de continuer dans la voie de recherche courante il doit alors d terminer comment le faire
87. AND1 2 45 8 19544 85 42 5 Table 8 R sultats pour ggv2 19 Algorithm Time Nodes Problems OR2 2AND2 2 41 4 21226 78 67 3 OR1 2AND2 2 30 0 15526 77 33 3 OR2 2AND1 2 23 7 22647 81 33 0 AND1 2ORI1 2 2351 ILO 73 77 33 8 OR1 2AND1 2 20 6 116281 81 33 8 ORANDI 2 25 1 113206 78 67 1 OR1 2ANDOR1 2 21 8 18106 80 00 5 ORANDI 2ANDI 2 32 7 13844 74 67 4 Table 9 R sultats pour ggv3 5 Conclusion L optimisation de l alpha b ta est encore un sujet de recherche active Notamment en ce qui concerne la recherche s lective Nous avons d crit les optimisations usuelles de l alpha b ta ainsi que deux optimisations tr s efficaces pour les jeux a but simple et avec un grand facteur de branchement Les volutions futures de l Alpha B ta peuvent venir de plusieurs horizons l ajout automatique de connaissances une s lectivit accrue une plus grande rapidit pour les optimisations d j existantes l utilisation d informations incertaines et probabilistes ainsi qu une possible liaison avec des algorithmes de recherche en meilleur d abord Enfin de nombreuses autres optimisations sont sans doute possibles et plus particuli rement dans les jeux avec un grand nombre de coups possibles comme le Go ou le Phutball De plus l utilisation de techniques proches de celles de l alpha b ta peuvent tre la source d id es dans des domaines connexes
88. BN 4 8182 0230 4 1987 Marsland 00 Marsland T A Bj rnsson Y From Minimax to Manhattan Games in AI Research pp 5 17 Edited by H J van den Herik and H lida Universiteit Maastricht ISBN 90 621 6416 1 2000 Meseguer 98 Meseguer P Walsh T Interleaved and Discrepancy Based Search Proceedings ECAI98 ed H Prade John Wiley amp Sons Ltd Chichester England ISBN 0 471 98431 0 1998 Schaeffer 00 Schaeffer J Search Ideas in Chinook Games in AI Research Edited by H J van den Herik and H lida Universiteit Maastricht ISBN 90 621 6416 1 2000 Thomsen 01 Thomsen T Lambda search in game trees with application to go CG 2000 LNCS 2001 21 Gestion des erreurs dans une interface p dagogique Groupe COMBIEN Duma J Giroire H Le Calvez Ee Tisseau G Urtasun M2 R sum Une interface p dagogique de r solution de probl mes doit permettre un l ve utilisateur de formuler une solution a un probl me qui lui est pos mais surtout d exploiter au mieux cette activit pour augmenter ses connaissances et ses capacit s Dans une telle interface la gestion des erreurs commises par l l ve ne concerne pas uniquement l aspect ergonomique et fonctionnel comme dans toute interface mais rel ve en premier lieu d une d cision p dagogique Il faut d finir quelles erreurs seront rendues impossibles commettre de par la structure m me de l interface et comment r agir p dagogiquement
89. E2 Nous pouvons d finir le type de la correspondance fonction 117 injection bijection Nous pouvons aussi indiquer que la valeur d un degr sur l ensemble de d part ou d arriv e est connu DMI et DMA sont les degr s minimaux et maximaux pour l ensemble de d part et AMI et AMA sont ceux pour l ensemble d arriv e La plupart du temps ces degr s d coulent du type de la correspondance par exemple pour une fonction DMI DMA I alors que AMI et AMA ne sont pas d finis Les types de correspondances ne sont qu une fa on commode de d finir plusieurs de ces degr s en une fois aussi ces types disparaissent ils une fois que l on a indiqu au syst me la valeur des degr s qui les caract risent CONTRAINTE d finit une contrainte du probl me Nous pouvons avoir des contraintes qui sont des expressions math matiques mais aussi des g n rateurs de contraintes qui engendrent un ensemble de contraintes qui changera selon les autres donn es du probl me SACHANT est li une des correspondances d finies pr c demment Cet ordre peut d finir un graphe ou des cliques de disjonction Nous pouvons d finir un graphe en indiquant explicitement les liens possibles entre les l ments de l ensemble de d part et ceux de l ensemble d arriv e Par exemple pour le Cavalier d Euler on peut choisir d avoir une bijection de l ensemble des cases d part sur l ensemble des cases arriv e le graphe indique al
90. ENVENV tant bien moins co teux que le cas ENVISAGE La combinatoire est plus restreinte que dans la version pr c dente de MALICE puisque les nombreuses r gles permettent de r duire la taille de l espace de recherche l aide de nouvelles contraintes Mais surtout la m tacombinatoire est diminu e de fa on appr ciable car on s lectionne les essais de fa on plus stricte puisque l on a plus de possibilit s pour indiquer comment les choisir Enfin on a une explication et une m ta explication de ce que l on a fait ce qui sera pr cieux pour avoir un monitoring et un apprentissage efficaces Le syst me est rapide puisque toutes les r gles sont compil es sous autant de formes que le besoin s en fait sentir La seule partie interpr t e est l encha nement de l ex cution des ordres li s l apparition d un v nement Cela ne p nalise gu re le syst me car alors que l ex cution d un ordre peut demander pas mal de temps le temps d interpr tation est n gligeable Il est int ressant d interpr ter car la m ta expertise de monitoring pourra ult rieurement changer dynamiquement l ordre de l interpr tation en d cidant de supprimer certains essais d en examine d autres prioritairement de transformer un ENVISAGE en ENVENV ou le contraire etc Le syst me trouve ainsi les solutions des probl mes plus rapidement qu avec l ancienne version de MALICE qui limitait d j s rieusement la m tacombi
91. NNES 1 NC SOIT ENSEMBLE RETENUES 0 NC SOIT ENSEMBLE CHIFFRES 0 9 118 SOIT ENSEMBLE VALRET 0 SUB NL 2 SOIT ENSEMBLE ARGUMENTS 1 PRED NL SOIT ENSEMBLE LETTRES SET A LJ Ie LIGNES Je COLONNES A LJ SOIT CONSTANTE NL SOIT CONSTANTE NC SOIT MATRICE A LIGNES X COLONNES LETTRES TROUVER FONCTION R RETENUES VALRET TROUVER INJECTION F LETTRES CHIFFRES AVEC R 0 0 AVEC R NC 0 AVEC SOMME R J SIGMA F A I J le ARGUMENTS SOMME F A NL J PRD 10 R PRED J POUR Je COLONNES AVEC F A LJ 40 POUR Ie LIGNES Je COLONNES A LJ NONEX Ke COLONNES K lt J A LK L ordre de d finition des l ments n a aucune importance On d finit les ensembles de lignes et de colonnes dont les tailles sont NL et NC qui seront lus pour chaque nouveau probl me Il y a une retenue de plus que de colonne pour que la formule d finissant la contrainte d addition sur une colonne soit toujours applicable Les valeurs des retenues sont d finies comme tant au plus le nombre de lignes moins 2 ceci n est pas indispensable si on lui donnait une limite moins stricte comme NL MALICE liminerait sans aucune difficult les valeurs sup rieurs la limite pr c dente Les arguments repr sentent les l ments que l on additionne La matrice rectangulaire A devra tre lue pour chaque nouveau probl me L ensemble des lettres est form des l ments de cette matrice qui ne sont p
92. Une maladie foudroyante pour l un un accident stupide pour l autre Martial Vivet et Jean Marc Fouet nous ont quitt s au cours de l ann e 1999 2000 Parmi les plus anciens ils taient en 1974 Caen au premier colloque d Intelligence Artificielle ils ont non seulement particip de nombreux autres colloques mais se sont aussi charg s plusieurs reprises d en organiser et de nous accueillir dans leur universit au Mans ou Lyon Ils ont marqu les colloques et les r unions d quipe par la qualit de leur travaux leur rigueur leur enthousiasme leur dynamisme et leur souvenir y restera toujours attach Ces actes leur sont d di s Sommaire MIN PRODUCTION sa SR EC nt Etes 3 Jacques PITRAT DES OPTIMISATIONS DE L ALPHA BETA ccccccccccccccsccccccccccccccccccccccccccccccccccccces Tristan CAZENA VE GESTION DES ERREURS DANS UNE INTERFACE PEDAGOGIQUE secsssssssssssesseees 22 Groupe COMBIEN Duma Jacques Giroire H l ne Le Calvez Fran oise Tisseau G rard Urtasun Marie CONTROLE DU RAISONNEMENT HYPOTHETIQUE EN ENVIRONNEMENT INCERTAIN ET INCOMPLET LE JEU DE L ASCENSEUR ccccccccscccccccccccccscccscccseees IO Fabrice KOCIK COMBINAISON D HYPOTHESES DANS LES PROBLEMES A SOLUTION COMPLEXE METHODE A POSTERIORI CONTRE METHODE A PRIORI cccccscccccccccccccscccscccseees D 4 Tristan PANNEREC CHEMINS DETOURNES IDEES FAUSSES ET BONNES IDEES cssssssssssssssccecssssees 7 Domi
93. a t dans Newell et Simon 72 Le lecteur souhaitant plus de pr cisions sur les graphes d tats et les algorithmes de recherche associ s pourront se reporter n importe quel ouvrage g n ral sur l Intelligence Artificielle 57 fonction des probl mes les n uds de ce graphe peuvent repr senter des abstractions diff rentes tat anticip d un jeu apr s une suite de coups connaissances partielles du fonctionnement d un m canisme dans un probl me de diagnostic etc Les arcs correspondent des tapes du processus de r solution Pour les probl mes qui nous int ressent ici chaque n ud sera associ une d cision et repr sentera une solution partielle Les arcs repr senteront les diff rentes possibilit s de choix un instant donn de la construction et pointeront vers les d cisions suivantes dont les possibilit s d pendent des d cisions pr c dentes Dans un tel graphe chaque feuille constitue une solution potentielle cf Figure 3 Le but est alors de trouver le chemin qui conduit la meilleure solution possible i 1 choix possibilit du __ pu 1 choix 2 choix 2 choix P21 P22 P21 P22 3 choix 3 choix 3 choix 3 choix P31 P32 P31 P32 p31 P32 P31 p32 aO OO 0G OQ Figure 3 Repr sentation d un probl me solution complexe par une recherche dans un graphe d tat 2 3 N cessit de choix abstraits Naturellement si la formalisation en graphe d
94. abilis s 3 1 Recherche arborescente dans les jeux n joueurs information incompl te structure temporelle variable Nous proposons d adapter les algorithmes de recherche classiques l ensemble des jeux plus complexes information incompl te multi joueurs structure temporelle variable La recherche arborescente offre en effet une grande robustesse du fait de la projection dans le futur du syst me La premi re modification sera l introduction d hypoth ses abstraites comme type de n ud de l arbre Le syst me pourra ainsi consid rer des choix abstraits choix strat giques ou des v nements abstraits ex je ne remporte pas le pli au lieu de JoueurX remporte le pli La pr cision du raisonnement s en trouve l g rement diminu pour un gain important sur le co t de recherche Il est de plus plus proche de celui de l tre humain La deuxi me modification propos e issue de la premi re est la repr sentation des choix adverses travers les v nements probabilis s Ce choix est n cessaire partir du moment o le syst me devient capable de consid rer des v nements abstraits pouvant comporter la fois de l information concernant l tat du monde et des choix de l adversaire Par exemple aux Le terme gain dans une situation S est utilis en th orie de la d cision Associ une fonction d utilit qui peut tre l identit ce gain correspond ce que nous appelons ici valuation d
95. actitudes sans cons quence sur le raisonnement 3 1 La famille Septime Jeux math matiques finales 1999 Monsieur et Madame Septime ont sept enfants n s curieusement tous les sept un 7 juillet Chaque ann e pour leur anniversaire Madame Septime offre chacun un g teau comportant autant de bougies qu il a d ann es Jean Septime le plus jeune se souvient qu il y a cinq ans il y avait au total deux fois moins de bougies que cette ann e Combien de bougies seront allum es cette ann e R ponse 35 Non Il y en avait bien 35 il y a cing ans mais on demande combien il y en a cette ann e 70 C est une erreur qu une machine ne ferait pas Raison de l erreur le calcul se fait naturellement partir du nombre d il y a cinq ans plut t que l inverse Pour qu une r ponse soit correcte il ne suffit pas de r soudre le probl me il faut aussi r pondre exactement la question pos e 80 3 2 Embrouille sur la feuille de matches Jeux math matiques 2 finales 2000 Pendant les derniers matches avant la finale de la coupe de basket nous avons bien vu dans les tribunes un espion de notre future quipe adverse Il notait notre technique habituelle Il nous faut perturber les rep res qu on a pu prendre Nous avons donc d cid de redistribuer nos cinq maillots num rot s de fa on qu aucun de nous ne porte son num ro habituel De combien de mani re pouvo
96. appara tre plusieurs morceaux de 4 complets car il faudra recompl ter sauf le premier C tait une id e fausse voir plus loin Importance de 2 et 4 en fait 4 est important car 2 2 Id e forte le samedi c est 2 qui est important travail avec n 2 d une part 2 d autre part puis on connecte la comm re A des n 2 qui conna t tout des n 2 au moins n 3 appels et une des 2 autres n 1 appels pour avoir la premi re comm re qui conna t tout et elles sont deux pas D pt D et on complete le reste soit n 2 compl ter soit a priori n 2 mais il y a un couple compl mentaire qui se compl te en un seul appel C et D d o seulement n 3 appels soit au total n 3 1 1 n 3 2n 4 Confusion fr quente dans le raisonnement entre essayer de faire au mieux et montrer qu on ne peut pas faire mieux Pour montrer qu on ne peut pas faire mieux il faut montrer qu on ne peut pas compl ter en moins de n 3 appels J y arrive si l appel qui rend la premi re comm re compl te est bien le n 1 car il y a alors un seul couple compl mentaire y p p 87 Et si l appel qui rend la premi re comm re compl te tait plus tard soit n 1 p il pourrait y avoir plusieurs couples compl mentaires L id e de couple compl mentaire semble importante Il faut aussi envisager que l appel qui rend la premi re comm re compl te n est pas entre un sous ensemble de n 2 et un de 2 Raisonnements un peu confus cert
97. ar r volutionnaire dont la zone de d tection qui couvre galement l ext rieur du b timent est un pentagone identique tournant autour d un sommet situ au centre du Pentagone Quel est au maximum le pourcentage de la surface du Pentagone couvert par la zone de d tection du radar en gris sur la figure On prendra si besoin est 2 236 pour V5 et on arrondira l entier le plus proche La premi re des choses faire est d valuer les angles et B 27m 3m Ona 5 et B 5 C est l mentaire mais beaucoup d erreurs pour ce calcul et un temps d raisonnable pour trouver p le jour des Jeux Beaucoup de dessins mais le dessin correct suivant n a t trouv que plus tard OB est perpendiculaire au c t du Pentagone A En valuant la surfaces des petits triangles on voit Que la position AOB correspond au maximum et le pourcentage est donc 1 5 5 30 82 3 4 Les deux c nes Jeux math matiques 12 finales 2000 Mathilde et Mathias sont au coll ge Leur professeur a donn chaque groupe de deux l ves un disque de papier de 20cm de diam tre La consigne est de d couper le disque en deux secteurs et d en faire deux c nes en rapprochant les bords coup s Chacun s affaire en suivant son bon plaisir Ainsi Mathilde a d coup un secteur et elle donne la partie restante Mathias voir figure Soigneusement du papier adh sif est coll pour achever la mise en forme
98. as es sur des capacit s de monitoring pour aborder ce probl me et pr sentons une comparaison de ces deux m thodes d un point de vue th orique Mots cl s raisonnement hypoth tique combinaison d hypoth ses optimisation construction de solutions complexes r solution de probl mes 1 Introduction L utilisation de raisonnement hypoth tique dans les syst mes d Intelligence Artificielle est apparue tr s t t dans l histoire de cette discipline tout en prenant des formes diverses Du backtracking classique en r solution de probl me aux algorithmes alpha beta des jeux les exemples ne manquent pas Le principe est de palier un manque d information en tudiant les diff rentes valeurs possibles pour d terminer ensuite une solution au probl me pos Le probl me r current est le contr le de ce mode de raisonnement car les hypoth ses sont souvent nombreuses et ne peuvent tre tudi es syst matiquement Mais selon le type d hypoth se g r e le probl me peut diff rer grandement Or dans la plupart des travaux effectu s ce sujet les hypoth ses portent sur des donn es du probl me ou des donn es de la solution Lorsque l on cherche utiliser des hypoth ses sur la mani re de r soudre le probl me les voies explorer la fa on de construire la solution ou d une mani re plus g n rale sur des m ta choix permettant de contr ler et diriger la r solution le probl me de la gestion d
99. as d erreurs internes Ces cat gories internes faisant intervenir une m thode de r solution externes nous semblent g n rales pour un EIAO 4 La d finition et la gestion des erreurs Pour sp cifier l interface une fois que les erreurs ont t r pertori es et cat goris es il faut 27 d cider quand et comment les d tecter les signaler et les expliquer 4 1 Cadre conceptuel structure diter Nous nous pla ons dans le cadre suivant les interfaces p dagogiques que nous consid rons sont des outils offerts un l ve pour exprimer la solution de probl mes d une classe particuli re dans un domaine particulier cette solution pouvant tre formalis e comme instance d une certaine structure arborescente pr d finie Cette structure n est pas enti rement fig e certains n uds peuvent tre polymorphes leur classe peut tre choisie parmi plusieurs classes diff rentes ou contenir une valeur multiple de cardinal non sp cifi a priori une liste d l ments D autre part cette structure est dimension humaine le nombre de n uds et de niveaux qu elle comporte permet l dition de ses instances par un l ve interactivement travers une interface qui permet d en remplir les champs Il faut noter que la th orie d un domaine d tude donn ne fournit pas automatiquement une telle structure Celle ci est inventer chaque fois qu on a l intention de cr er une inter
100. as des blancs On doit trouver deux correspondances d une part une fonction R qui d finit la valeur des retenues et d autre part une injection F donc DMI DMA AMA I entre les lettres de la cryptaddition et les nombres compris entre 0 et 9 Notons que si la taille de l ensemble des lettres est gal 10 on aura une bijection mais c est MALICE de d couvrir et d utiliser cette contrainte suppl mentaire qui indique que le AMI de la correspondance F vaut aussi 1 Nous avons enfin les contraintes D abord deux valeurs initiales des retenues qui valent 0 pour les valeurs extr mes Nous avons ensuite un premier g n rateur de contraintes qui cr e une contrainte par colonne Chacune traduit la r gle de l addition avec des retenues la somme de la retenue de la colonne pr c dente et des valeurs des lettres des op randes pour cette colonne est gale la lettre du r sultat plus dix fois la valeur de la retenue de la colonne Un deuxi me g n rateur de contraintes traduit le fait que la lettre situ e au d but de chaque ligne ne doit pas avoir la valeur 0 il cr e donc une contrainte par ligne Des exemples classiques de cryptadditions sont SEND MORE MONEY DONALD GERALD ROBERT 119 AIN AISNE DROME MARNE SOMME La deuxi me de ces cryptadditions conduira une bijection car elle a dix lettres diff rentes MALICE trouve la solution et en montre l unicit en faisant seulement deux choix binaires Pour la t
101. ation des travaux de JM Bazin Bazin 93 et Miguel Pintado Pintado 94 et cherche entre autre produire des preuves compr hensibles par un humain Il s inscrit parmi les travaux actuels en DAT Explication et EIAO comme par exemple Projet Mentoniezh de D Py Py 96 Cabri Euclide de V Luengo Luengo 99 PROVERB par H Horacek Horacek 99 ou bien encore les travaux d Erika Melis Melis Uron 99 La sp cificit du travail r sulte dans le fait que le syst me est capable de r soudre un exercice de g om trie d affiner ses strat gies de recherche l issue de la r solution d un nouvel exercice et de produire automatiquement une preuve r dig e en fran ais adapt e un certain nombre de d siderata de l utilisateur Le syst me est capable en pr sence de certaines situations classiques de faire des appels internes de conjectures partir de r gles pour aller rechercher et d duire des informations non pr sentes dans la base de faits 133 Il est aussi possible de faire fonctionner ARGOS partir d un exercice donn comme outil de v rification de conjectures propos es par un l ve partir de l observation de la figure l l ve pouvant introduire de nouveaux objets ou non Si la conjecture est v rifi e le syst me peut renvoyer l l ve une explication restreinte ou globale de celle ci Une utilisation du syst me comme compagnon d apprentissage est en cours de mise au point Nous allons maintenant d tailler les
102. avec ces s quences d ordres il faut lui donner la capacit de les engendrer automatiquement Il faudra aussi tre capable de faire du m tamonitoring de fa on ne pas perdre trop de temps faire du monitoring 1 Principes du syst me Un syst me intelligent doit avoir des m taconnaissances compil es pour des raisons d efficacit et des m taconnaissances d claratives pour des raisons de commodit Il suffit donc qu il ait la possibilit de compiler les m taconnaissances d claratives qui lui sont donn es ou qu il a trouv es lui m me Les m taconnaissances compil es correspondent au comportement d expert et les m taconnaissances d claratives sont utiles dans le cas o l on n est pas encore expert Notons que d avoir des m taconnaissances compil es ne signifie pas que l on r sout combinatoirement le probl me car une m taconnaissance indique seulement quelles connaissances il est bon d utiliser faire de la combinatoire n tant qu une connaissance particuli re D autres connaissances peuvent tre des moyens plus directs d arriver la solution Les m taconnaissances compil es correspondent plut t une r solution m tacombinatoire du probl me o l on a pr vu la succession des essais et o l on fait tous ceux qui sont autoris s Mais cela n entra ne pas l examen syst matique de ce qui se passe pour toutes les combinaisons de valeurs possibles des variables Comme pour les tr
103. ciations de r gles Que fait alors le syst me Puisque le triangle fbd est rectangle en f alors mf mb Le syst me d duit alors que a b m et d sont align s dans cet ordre car on a une succession de milieux que abe est aigu puis que f b et c sont align s dans cet ordre On a alors mbf 60 car abe et mbf sont des angles oppos s par le sommet Le syst me aura d cr er l angle mbf Donc mbf est un triangle quilat ral car il est isoc le avec un angle de 60 degr s On en d duit donc que bf bm et donc b milieu f c Ceci tait le point important prouver acmf est alors un parall logramme ayant ses diagonales de m me longueur donc un rectangle 4 Graphe et preuve r dig e d un th or me 4 1 Obtention du graphe de d monstration Tous les faits obtenus successivement par le d monstrateur sont class s par ordre chronologique et ont un num ro d apparition Pour chaque fait nouveau d duit on m morise les hypoth ses d j pr sentes dans la base de faits qui ont permis son mergence On peut donc remonter partir de chaque conclusion partielle obtenue jusqu aux hypoth ses initiales ayant permis son mergence L arbre de d monstration est alors la r union de tous les sous arbres obtenus pour chaque l ment de la conclusion globale On r cup re aussi les noms d objets ayant servi dans la preuve pour pouvoir dans la r daction remplacer des noms barbares par la notation fonctionnelle du math maticie
104. comme la satisfaction de contraintes ainsi que l a montr la r utilisation d Iterative Broadening Ginsberg 1992 par Meseguer et Walsh Meseguer et Walsh 1998 pour la satisfaction de contraintes 20 6 Bibliographie Breuker 99 Breuker T Memory versus Search in Games PhD thesis Maastricht 1999 Cazenave 98 Cazenave T Metaprogramming Forced Moves Proceedings ECAI98 ed H Prade pp 645 649 John Wiley amp Sons Ltd Chichester England ISBN 0 471 98431 0 1998 Cazenave 99 Cazenave T Intelligence Artificielle Une Approche Ludique Notes de cours 1999 Cazenavel 00 1 Cazenave T Generating Search Knowledge in a Class of Games submitted http www ai univ paris8 fr cazenave papers html 2000 Cazenave 00 2 Cazenave T Iterative Widening Workshop of the 2000 computer Olympiad Londres 2000 Cazenave 01 Cazenave T Abstract Proof Search Proceedings of the Computer and Games 2000 conference publi e en LNCS 2001 Ginsberg 92 Ginsberg M L Harvey W D Iterative Broadening Artificial Intelligence 55 2 3 pp 367 383 1992 Ginsberg 97 Ginsberg M Partition Search AAAI 97 Kano 85 Kano Y Graded Go Problems For Beginners Volume One The Nihon Ki in ISBN 4 8182 0228 2 C2376 1985 Kano 85 Kano Y Graded Go Problems For Beginners Volume Two The Nihon Ki in ISBN 4 906574 47 5 1985 Kano 87 Kano Y Graded Go Problems For Beginners Volume Three The Nihon Ki in IS
105. d intelligence artificielle Herm s 1987 Pastre 78 Pastre D Observation du math maticien aide l enseignement et la d monstration automatique de th or mes Educational Studies in Mathematics 9 1978 461 502 Chi 81 Chi M Feltovitch P Glaser R caracterization and representation of physics problems by experts and novices Cognitive Science 5 1981 121 152 Pitrat 99 Pitrat J Monitorer la recherche d une solution Colloque Intelligence Artificielle Berder 1999 et rapport de recherche LIP6 2000 002 3 15 Schoenfeld 85 Schoenfeld A Mathematical Problem Solving Academic Press 1985 114 La mise en place du monitoring dans MALICE Jacques Pitrat CNRS LIP6 Universit Pierre et Marie Curie R sum Pour r soudre un probl me on dispose d un ensemble de r gles qui transforment son nonc jusqu ce que l on trouve directement la solution ou qu une approche combinatoire soit envisageable Un expert dispose de m taconnaissances compil es pour utiliser judicieusement de telles r gles un des r les du monitoring est justement de construire ces ensembles de m taconnaissances pour chaque famille de probl mes en examinant comment le syst me r sout les probl mes Nous d crirons le langage proc dural mis en uvre dans MALICE pour donner ces m taconnaissances et nous en montrerons des exemples d application la d finition de l utilisation de r gles Maintenant que le syst me fonctionne
106. de g om trie peut tre r solu par des outils tr s diff rents g om trie des configurations vectorielle analytique barycentrique ou autre Certains types de probl mes par exemple des probl mes d alignement en seconde peuvent tre d j re traduits en utilisant la g om trie vectorielle ou analytique L utilisateur sugg re au syst me sans garantie de succ s d ailleurs une preuve d un certain type en lui demandant de charger en premier les r gles d un certain domaine ARGOS va alors filtrer les strat gies pour ne garder que les r gles des domaines choisis 4 3 Probl mes rencontr s au niveau de l explication Il n existe pas de r daction universelle d une preuve Toute explication s adresse un public donn qui est plus ou moins comp tent ou r ceptif sur le sujet Le probl me central est donc de d finir ce qui va tre dit comment on va le dire et ce qui ne sera que sugg r ou pass sous silence Ceci rel ve d une autre expertise que l expertise math matique Il faut donc dissocier le module d monstration de th or me du module explication et r daction de la preuve qui n cessite des connaissances d un autre ordre Il 140 faut bien se persuader que la t che d explication est une t che de r solution de probl me au m me titre que la DAT On peut imaginer qu ARGOS produise une explication de la preuve d un th or me en suivant la m me d marche que celle lui permettant de trouver
107. de l importance au choix les plus hauts tout en favorisant le d veloppement des meilleurs choix a priori d un m me niveau L int r t du d veloppement d un noeud est alors fonction de ces trois notions et donn par la formule Imprecision n Probabilite n k InteretAPriori n o k est une constante 45 La premi re terme de la somme Imprecision n Probabilite n correspond la pr cision maximum qu il est possible de gagner sur l valuation du choix principal en continuant d velopper le n ud Le syst me aura donc tendance ne pas d velopper les situations trop improbables Le second terme permet de prendre en compte les connaissances a priori et guider la recherche vers les choix les plus prometteurs 3 3 Le choix du type d hypoth se Alors que pour la plupart des jeux classiques a 2 joueurs le d roulement du jeu est fix une fois pour toute par l alternance des coups de chacun des joueurs il n en est pas de m me pour la majorit des jeux de cartes Kocik 99 montre comment repr senter la structure temporelle de cette famille de jeux Le d roulement d un tour de jeu est g n ralement d pendant du d roulement suivant Alors que la situation initiale du monde est rendue partiellement inconnue par le syst me dans les jeux de cartes l utilisation d arcs relatifs des v nements abstraits rendue n cessaire par cette incompl tude des informations cf 3 1 dans une recherche arborescente ajou
108. diff rentes tapes de r solution 2 1 Lecture et analyse de l nonc Le syst me va lire un nonc donn au syst me sous forme d implication puis en extrait les concepts pr sents en hypoth se et en conclusion De plus dans le m me temps il proc de l limination de certains symboles fonctionnels pour leur donner des noms internes Argos r cup re aussi les souhaits de l utilisateur quant au d roulement de la recherche et au type de preuve r dig e voulue niveau de pr cision et niveau scolaire L utilisateur a ainsi la possibilit de param trer le syst me Il peut d finir des domaines prioritaires induisant la preuve dans tel ou tel sens auquel cas les r gles d autres domaines seront d cal es il peut interdire les r gles d un ou plusieurs domaines comme par exemple les r gles de trigonom trie tr s sp cifiques et alourdissant la recherche 2 2 S lection et chargement des r gles ad quates dans un certain ordre Le syst me va alors constituer une liste de r gles en fonction des concepts pr sents des connaissances math matiques dont il dispose et des strat gies connues relatives aux diff rentes conclusions demand es Il charge en premier les r gles universelles n cessaires ind pendamment de tout nonc manipulation logique de l nonc sortie du syst me coh rence au niveau des objets et r gles n cessaires quel que soit l nonc puis les r gles d introduction des objets initiaux les
109. difficilement v rifiable par ce dernier m thode qu il qualifie d ailleurs souvent de non l gante Elle comporte n anmoins l avantage d tre robuste et g n rale Nous prenons en compte ici des connaissances d claratives provenant d un syst me expert pour guider la recherche arborescente dans des jeux informations incompl tes multi joueurs d roulement variable pour lesquels une fonction d valuation est difficile d terminer Ce type de jeu tr s complexe rend n cessaire l utilisation d une telle technique qui devrait allier robustesse et compr hensibilit pour une faible complexit ou du moins une complexit contr l e Nous pensons que c est par l tude de ce type de jeux complexes et non pas des probl mes jouets que l intelligence artificielle doit se tourner jonglant entre les connaissances du monde facilement mod lisables et une complexit importante Nous donnons dans 2 les principes de la recherche arborescente dans les jeux en particulier les jeux information compl te deux joueurs et somme nulle Ces m thodes inadapt es pour les jeux informations incompl tes seront ensuite adapt es et am lior es dans 3 Nous verrons enfin dans 4 leur application au jeu de l ascenseur 2 Arborescences Nous pr sentons un type de raisonnement largement utilis dans les syst mes actuels pour la r solution de probl me surtout les jeux savoir les recherches arborescentes 2 1 Recherche arboresce
110. du triangle G C D donc il appartient a la m diane issue de G cad la droite G E M A partir de la situation g n rique du corps de la r gle ci dessus le syst me va chercher instancier la partie condition de la r gle dans la base de faits situation g n rique situation concr te A b 145 En supposant que le syst me sache d j que k est le milieu de cd le premier pr dicat de la r gle I mil B C sera instanci par k mil c d Il y a alors appel du sous but suivant centreGravite 0 A c d G Q partiellement instanci Si en hypoth se le fait que g est centre de gravit du triangle bcd figure sous la forme hyp 0 centreGrav c b d g 23 alors la proc dure de recherche va chercher v rifier l une des 3 6 fa ons d exprimer ce fait hyp 0 centreGrav A c d G Q chouera ainsi que hyp 0 centreGrav A d c G Q etc jusqu hyp 0 centreGrav c A d G Q qui donnera une r ponse positive avec le jeu d instanciations A b G g et Q 23 5 3 Proc dures de calcul Tout objet mesurable longueur aire angle g om trique etc a parmi ses attributs une valeur exacte donn e par hypoth se d duite ou inconnue Les relations num riques liant ces diff rentes grandeurs s expriment sous forme d hypoth ses ayant t d duites ou comme donn es initiales Une r gle peut appeler des proc dures de calculs si l une des grandeurs non encore affect e est calculable
111. e S Nous utilisons dans ce papier indiff remment les 2 termes 43 jeux de cartes lorsqu on d cide pour une situation donn e d envisager le cas o le syst me est ma tre remporte un pli ou ne l est pas on fait une hypoth se la fois sur la disposition possible des cartes pour qu un autre joueur remporte le pli il faut qu il ait les cartes ad quates et la fois sur le choix des autres joueurs ce n est pas parce qu un joueur poss de une carte plus forte celle du syst me qu il la jouera forc ment De plus repr senter le choix des autres joueurs par des v nements probabilis s permet la prise en compte d un mod le de l adversaire explicite D s lors o le syst me fait de la planification sur des v nements abstraits le syst me raisonne sur le long terme avec un manque d informations de plus en plus grand Pour cette raison nous garderons une repr sentation de la fonction d valuation bas e sur 2 valeurs une valeur optimiste et une valeur pessimiste Le syst me est ainsi capable d avoir une information de pr cision sur sa fonction d valuation sur laquelle il pourra s appuyer pour contr ler sa recherche Le contr le de la recherche arborescente passe par quatre tapes La premi re tape est le choix du n ud d velopper la deuxi me le choix du type d hypoth se poser la troisi me le choix des valeurs tudier pour la fonction choisie dans l tape pr c dente la derni re tant la remon
112. e combinaisons de m ta choix possibles est en effet exponentiel en fonction du nombre de pi ces concern es et l valuation de chaque combinaison est co teuse Or le nombre de combinaisons d hypoth ses que doit tudier le syst me est lev et la construction d une solution combin e doit donc tre rapide Figure 8 Exemples de mauvais choix de remplacement 3 3 Impl mentation de la phase de combinaison Ce probl me interne de recherche de compatibilit poss de donc toutes les caract ristiques des probl mes externes auxquels s adresse le syst me MARECHAL e N cessit de coordonner des choix interd pendants dans un but d optimisation e Pas de m thode directe e Recherche exhaustive trop co teuse e Possibilit d heuristiques imparfaites n cessitant d ventuels retours arri res Dans un tel contexte il est alors tr s int ressant d utiliser la r flexivit pour appliquer le syst me la r solution de ce m ta probl me qu est la recherche de solutions compatibles Cela permet de faire l conomie d un m canisme sp cifique et de disposer de toute la puissance du syst me retours arri re intelligents recherche contr l e etc Cela permet en outre de rendre les m ta choix conscients et de fournir la m thode de r solution sous une forme plus d clarative L ascension infinie des niveaux m ta est emp ch e simplement en interdisant au syst me l utilisation du raisonnement
113. e d cision d investissement on investit son capital le temps d analyse l o on esp re avoir le meilleur b n fice on cherche le plus d information possible Un autre m canisme de selective deepening est utilis dans Deep Blue Il analyse la structure de l arborescence pour savoir si une branche de l arbre d velopp est uniforme ou pas Ainsi une branche dans laquelle beaucoup de coups sont bons est consid r e comme ayant une valuation s re Alors qu une branche pour laquelle 1 seul coup parmi 30 est bon est consid r e comme peu s re Deep Blue d veloppe alors plus que les autres la partie de l arborescence qui ne contient qu un seul bon coup sur 30 On peut consid rer les valuations utilis es pour activer le selective deepening comme des m ta fonctions d valuation 2 4 2 Recherche de Quiescence Un exemple de proc dure de recherche de quiescence est donn ci dessous La fonction TrouveCoupsPossibles ne selectionne que les coups li s a la quiescence captures et promotions A chaque feuille de l arborescence Alpha Beta principale on appelle la fonction quiescence pour valuer la position int TableauCoups PROFMAX NB_COUPS_MAX char Position TAILLE_ POSITION int Quiescence int profondeur int alpha int beta int valeur Best i N int CoupsPossibles TableauCoups profondeur Best Evaluation beta alpha N TrouveCoupsPossibles Position CoupsPossibles
114. e difficult des l ves est de bien organiser leur pens e m me si en g om trie se surajoute aussi le fait d avoir la bonne id e qui fera avancer vers la solution 9 2 Que peut faire l l ve fonctionnalit s d Argos L l ve commence par donner l nonc au syst me Il a ainsi un travail de lecture et d analyse de l nonc livresque pour en extraire les hypoth ses et ce qu il faut d montrer puis lance la recherche de solution s par ARGOS Pendant le temps de la recherche d une solution l utilisateur pourra construire la figure avec un logiciel de construction g om trique Geoplan ou Cabri par exemple ou la main Ceci lui permettra de v rifier exp rimentalement ses intuitions Apr s examen de la figure l l ve peut en toute libert mettre des conjectures en introduisant ou pas des objets nouveaux qu il peut soumettre Argos Le syst me va alors v rifier si la conjecture mise est d j pr sente dans la base comme un fait d duit Sinon il va lancer une recherche avec comme l ment de conclusion la question de l l ve plus d ailleurs la conclusion de l exercice si celle ci n a pas t obtenue par la seule comp tence du syst me Ceci peut permettre une sorte d change entre la machine et l utilisateur L l ve peut ensuite si la conjecture est prouv e en obtenir une explication compl te partir des hypoth ses initiales ou bien seulement au premier niveau pour lui donner des id es ma
115. e la r gle R2 il faut consid rer chacune des deux valeurs possibles de X terme qui contient une SOMME puis chacun des l ments de cette somme Cela peut n cessiter beaucoup de temps et il vaut mieux se demander rapidement d abord quand cela vaut la peine de le faire L ordre ENVENV permet de diff rer ces calculs co teux quand ils risquent de ne pas avoir un int r t lev si cela se trouve on ne les examinera jamais parce que l on aura trouv la solution sans eux Mais il faut bien alors deux priorit s P est celle de l examen approfondi des modalit s d ex cution de la r gle et PP est celle l ex cution r elle de la r gle Les arguments R et A sont d finis comme pr c demment mais P indique la priorit avec laquelle on va envisager et non plus ex cuter l essai et E d finit ventuellement des variables apparaissant dans P PP indique avec quelle priorit on va ex cuter l essai et EE contient des expressions utiles pour valuer PP Voici une nouvelle d finition de l ordre qui indique comment utiliser la r gle R2 quand le foyer est une nouvelle contrainte ENVENV R2R COND Q 2 ELEVE Q 3 ASSEZELEVE Q 4 MOYEN Q 5 BAS Q 6 TRESBAS Q CARVAR R PROG COND Q 2 ELEVE Q 3 ASSEZELEVE Q 4 MOYEN Q 5 ASSEZBAS Q 6 TRESBAS COND M gt 1 MS8 1 M gt 8 2 0 Q CARVAR R M FACTEUR X Nous voyons que l examen sera bien plus rapide dans le cas ENVENV puisque X n y appara t pas et
116. e le nombre de coups l gaux par tour et n la profondeur de la recherche Cet algorithme devient donc rapidement inutilisable lorsque le nombre de coups l gaux est important c est pourquoi des optimisations de cet algorithme ont t r alis es 2 1 2 L alpha beta L alpha beta est une optimisation du min max il permet d effectuer de nombreuses coupes dans l arbre par l limination de recherches certainement a priori infructueuse car aboutissant assur ment une valuation moins bonne Coupe alpha Si l avancement de la recherche permet de conclure de fa on certaine qu un coup l gal C1 est pr f r par le syst me un autre coup l gal C2 alors il est inutile de continuer le d veloppement de C2 Cette constatation g n rale appliqu e au min max c a d sous la condition que l autre joueur raisonne de fa on similaire produit les coupes alpha Si un coup C1 d un niveau max choix du syst me est valu C1 et qu un coup C2 1 coup l gal de niveau min imm diatement inf rieur un coup C2 de m me niveau que C1 est valu f C2 1 lt C1 alors il est inutile d explorer plus avant le C2 C1 tant pr f r C2 Il est en effet facile de montrer que C2 lt f C1 Coupe beta De fa on similaire la coupe beta repose sur la constatation g n rale que si l avancement de la recherche permet de conclure de fa on certaine qu un coup l gal C1 est pr f r par l autre joueur un autre coup l gal C2 i
117. e permettant Argos de ne conclure qu avec la r gle correspondante Le syst me recherchera toutes les r gles concluant sur le type de but voulu et ne chargera que la r gle associ e au savoir faire voulu Ceci va videmment diminuer les chances de succ s pour le syst me 9 3 Exp rimentation Cette fa on de travailler a t test e sur le mode le on particuli re avec la restriction qu il n existe pas encore d interface permettant l l ve de rentrer ses donn es et questions sans avoir respecter une certaine syntaxe par exemple par le biais de bo tes de dialogue o il ne reste plus qu instancier les variables Ceci alourdit la d marche de l apprenant et suppose une motivation forte La pr sence du professeur est indispensable pour guider l l ve et l aider formuler les hypoth ses de l exercice et ce qu il y a d montrer On ne peut imaginer pour l instant une utilisation en autonomie qu avec une grande pratique de la part de l utilisateur 9 4 Transformer l l ve en Expert Il s agit bien s r d un souhait l gitime mais de l ordre de la prospective Il est connu que l on ne ma trise vraiment bien un sujet que quand on a l enseigner ou l expliquer aux autres On est alors oblig de synth tiser d aller l essentiel de trier la connaissance et surtout d tre actif et l initiative de ce qui va se faire On peut imaginer qu partir de la classe de quatri me l l ve lui m me se constr
118. e pourra plus tre consid r e car l hypoth se qu il faudrait remettre en question ne fait plus partie de l ensemble des hypoth ses actuelles Les hypoth ses de non utilisation de possibilit sont dites n gatives alors que les hypoth ses d utilisation sont dites positives Hypoth se Nouvelle voie remise en cause de recherche point de retour 4 2 Ancienne voie 1 de recherche LT D but du Fin de l ancienne Ancienne raisonnement voie de recherche Figure 14 Exploration combinatoire par retour arri re Pour trouver le bon point de retour le syst me calcule un int r t d annulation pour chaque hypoth se positive actuelle Cet int r t sera d autant plus grand que l hypoth se aura g n la suite du raisonnement et eut un impact n gatif ou faible sur la valeur de la solution finale 73 Par exemple si une hypoth se conduit utiliser des pi ces qui auraient t utiles plus loin dans le raisonnement et qu elle n a pas un impact b n fique sur la solution son annulation sera a priori tr s int ressante Selon le temps de r flexion restant le syst me va ensuite d terminer un niveau d int r t minimum de remise en cause Le point de retour sera alors l hypoth se la plus r cente dont l int r t est sup rieur au niveau de remise en cause Si une telle hypoth se n existe pas le raisonnement est conclu par la phase de s lection La difficult consiste donc ici
119. eau le pass du raisonnement pour acc l rer la recherche Si par exemple le programme a d j d velopp l arbre de la Figure 13 et d termin que 1 b tait pr f rable b tout en tant ind pendante de a il pourra directement appliquer 1b dans l hypoth se 1a et se contenter de recopier la solution partielle correspondante 1b sans recommencer cette partie de raisonnement 72 Figure 13 Gestion d hypoth ses ind pendantes 4 2 3 Faut il explorer une autre voie La question d une nouvelle voie est la plus importante des trois questions de contr le C est en effet elle qui va diriger la recherche combinatoire par l interm diaire d un m canisme de retour arri re chaque fois que le programme termine une voie de recherche par arr t pr matur ou non il lui faut en effet d terminer quel niveau du raisonnement il va remonter pour explorer une nouvelle voie c est dire quelle hypoth se il va remettre en question Sur le sch ma de la Figure 14 les cercles repr sentent les moments du processus de raisonnement pendant lesquels le syst me a pos une hypoth se Au point 1 il d cide de changer de voie de recherche et remonte au point 2 o il pose comme hypoth se la n gation de la pr c dente 1 e qu il ne faut pas utiliser la possibilit de choix pr c demment retenue Cela le conduit alors sur une nouvelle voie de recherche 3 Naturellement cela signifie que la voie 4 n
120. eaucoup plus fournie et en pratique il est n cessaire de limiter l exploration de m me qu il tait n cessaire de limiter le nombre de combinaisons envisager dans l approche pr c dente Le syst me utilise donc des m canismes de contr le pour explorer intelligemment une partie de l arbre comme nous allons le voir dans la sous partie suivante 69 4 2 Impl mentation Si l exploration de la voie actuelle n est pas termin e Faut il continuer dans la voie actuelle Comment faut il Doit on explorer une continuer l exploration nouvelle voie de la voie actuelle RETOUR SELECTION CONTINUATION ET FIN ARRIERE Figure 11 Algorithme g n ral de contr le du raisonnement hypoth tique Le contr le du raisonnement hypoth tique fait partie des capacit s de monitoring d un syst me C est en effet une activit de niveau m ta qui partir de l tude du raisonnement d j effectu guide l ex cution de la suite du raisonnement Dans le syst me MARECHAL ce monitoring se mat rialise travers trois questions que se pose en permanence le syst me comme le montre l algorithme g n ral de contr le pr sent sur la Figure 11 Cet algorithme est ex cut chaque nouveau n ud dans la trace de la Figure 12 La suite de cette sous partie discute chaque question en particulier S Voir Pitrat 99 pour une tude du monitoring chez les tres humains et plus g n ralement Flavell 76 pour
121. eiller on ne peut pas tout observer Les m thodes utilis es par SEPIAR Parchemal 88 seront une source d inspiration Quand tout se d roule normalement on examine de moins pr s ce qui se passe par contre quand la solution a l air d tre plus lointaine que pr vu il devient utile de commencer faire des statistiques sur l utilisation des r gles Le syst me doit se rendre compte que l utilisation d une certaine r gle en g n ral consid r e comme utile conduit toujours un chec dans le cas pr sent On peut imm diatement en limiter l utilisation au cours de la r solution mais il est plus difficile d en tirer des conclusions g n rales pour les probl mes futurs car pour cela il faut comprendre pourquoi une r gle en g n ral utile a un r le n faste dans certaines circonstances Pour cela le syst me devra avoir une th orie de la r solution de probl mes et pouvoir tablir des propri t s du type la r gle RS est int ressante pour les probl mes o il y a peu de contraintes et o chaque variable a moins d une dizaine de valeurs possibles Le syst me devra utiliser des m thodes de d monstration de th or mes dans des environnements o les lois sont tr s incertaines C est comme cela que j ai suppos qu il valait mieux appliquer la r gle R2 des termes o la variable est multipli e par un nombre le plus grand possible Mais que veut dire un nombre grand Dans certains cas 9 est consid r
122. el on a ajout un lien certain ou la nouvelle contrainte La valeur de ce foyer est souvent utilis e dans l interpr tation d un ordre Il existe quatre types d ordres 1 L ordre indiquant d envisager d appliquer une r gle ENVISAGE R A P E On envisage d ex cuter la r gle R la variable A qui figure dans la r gle R a pour valeur le foyer L expression P d finit la priorit avec laquelle on va ex cuter ult rieurement cet essai Elle 123 peut contenir des variables en particulier la variable A mais aussi contenir n importe quelle autre variable d finie dans la r gle R Il est de plus possible de d finir d autres variables par des expressions qui figurent alors dans l ensemble E Un exemple simple de tel ordre est ENVISAGE R6 S MOYEN qui dit d appliquer la r gle R6 avec une valeur de la priorit MOY EN la variable S est une variable de la r gle R6 qui aura comme valeur le foyer Par exemple si l v nement tait la cr ation d une contrainte S aura pour valeur cette contrainte s il tait la d couverte d une nouvelle borne sup rieure pour un n ud de d part D d une correspondance la valeur de S sera alors ce n ud D Cet essai est mis en attente et sera ex cut quand on aura fini d effectuer tous les essais dont la priorit est sup rieure MOYEN Ici l ensemble E est vide Donnons un exemple un peu plus complexe bas sur la r gle R2 que nous avons vue plus hau
123. elle qui sera effectivement jou e 60 pour le raisonnement hypoth tique En effet dans les probl mes solutions simples c est dire o il n y a qu un seul choix faire un choix abstrait n possibilit s engendrera n hypoth ses ce qui est facilement g rable En revanche dans les probl mes solutions complexes un tel choix engendrera 2 hypoth ses puisque les possibilit s ne sont pas mutuellement exclusives Plusieurs possibilit s peuvent tre s lectionn es en m me temps comme par exemple le fait d attaquer plusieurs endroits la fois Le syst me doit donc rapidement faire face une explosion combinatoire et deux approches sont alors possibles La premi re consiste tudier les n possibilit s ind pendamment les unes des autres puis tudier leur combinaison Cela signifie que les solutions partielles correspondantes chaque hypoth se devront tre combin es pour obtenir une solution globale Deux solutions partielles peuvent alors tre incompatibles a priori car les choix concrets qu elles contiennent entrent en conflit typiquement une pi ce ne peut avoir deux chemins de d placement diff rents mais pourtant leur combinaison peut tre possible et int ressante si on les modifie plus ou moins on parlera alors d affaiblissement ou de d gradation d une solution partielle En effet si vi et v2 sont les meilleures valeurs possibles pouvant tre obtenues sous les hypoth ses h
124. en tre la fen tre est ajust e INFINI valeur si on choue vers le bas ou valeur INFINT si on choue vers le haut 2 10 La fen tre minimale La variation principale La fen tre nulle En poussant cette id e jusqu au bout on obtient l id e de la fen tre nulle Cela consiste appeler l alpha b ta avec une fen tre valeur valeur 1 sachant que la fonction d valuation est enti re avec des diff rences d valuation minimales de un point Les arbres d velopp s sont alors plus petits et on peut ajuster vers le haut ou vers le bas la valeur en fonction de ce que retourne l arbre Il a t montr que cet algorithme qui associ aux tables de transposition s appelle MTD f d veloppe les feuilles de l arbre dans le m me ordre qu un algorithme en meilleur d abord qui a t prouv meilleur qu alpha b ta SSS 2 11 Les Tables de Transposition Une table de transposition sert stocker les positions d j rencontr es dans une table de hachage Lorsqu on rencontre une position on commence par v rifier si elle a d j t vue Pour cela on a un probl me de m moire coder la position sur 32 ou 64 bits De plus la rapidit de codage est importante La m thode la plus fr quemment utilis e est le hachage de Zobrist on associe un nombre al atoire pour chaque position de pi ce possible et pour le joueur qui a la main Au Go cela revient a avoir 2 nombres al atoires par intersection couleur qui j
125. en intervalles de longueur lt e Alors il existe deux entiers diff rents m et m2 tels que E m r et E m2 r appartiennent au m me intervalle soit 0 lt E m r E m2 r lt Il existe alors n et nz tels que 0 lt m r n m r n2 lt Et on a le r sultat en prenant m m m2 et n n1 n2 Remarque j avais eu l id e de prendre les parties fractionnaires de n r mais je voulais tout prix les faire se rapprocher directement de 0 Ici on prend la diff rence de deux proches 8 2 Une multiplication Jeux math matiques 2 finales 2000 Dans cette multiplication le chiffre 7 appara t une fois et une seule Ainsi chaque toile repr sente un chiffre de 0 9 diff rent de 7 De plus l criture d aucun nombre ne commence par 0 Quel en est le r sultat 110 x 7 x x x Des techniques type ALICE conduisent rapidement la solution Mais il y a beaucoup de chiffres inutiles je fais plut t intervenir dans les in galit s le premier nombre entier et les r sultats interm diaires entiers des multiplications en utilisant leurs nombres de chiffres 8 3 Le carnet de timbres Jeux math matiques 1 finales 2000 Il est possible d obtenir toutes les sommes enti res de 1 36 en d coupant un ou plusieurs timbres dans un carnet de timbres rectangulaire de deux timbres sur trois portant les valeurs 1 2
126. en prise Elle est utilis e par Deep Blue pour savoir si une position est valuable ou si on doit continuer la d velopper Une position stable a une valuation en laquelle on peut avoir confiance alors qu une position instable est mal valu e Deep Blue utilise ce m canisme de quiescence pour continuer de d velopper les positions basses de l arbre jusqu des positions stables Les options de quiescence couramment utilis es dans les programmes d Echecs sont les coups de capture les coups de promotion sauf quand le Roi est en Echec On peut aussi utiliser l lagage de futilit lorsqu on d veloppe les positions instables si la valeur de la position est inf rieure alpha V alors seuls les captures et les checs sont consid r s 2 4 1 Selective deepening Si un coup semble int ressant on continue a chercher a une plus grande profondeur que la profondeur habituelle Si un coup semble mauvais on arr te de chercher a une profondeur plus petite que la profondeur habituelle Par exemple si Chinook analyse un coup qui perd 3 pions plut t que de continuer a analyser la position jusqu une profondeur 10 il va r duire son analyse seulement 5 coups l avance en faisant l hypoth se qu il y a de bonnes chances que le coup soit tr s mauvais Par contre si le programme joue un coup qui parait tr s bon il augmentera la profondeur de l analyse de 10 12 coups l avance D apr s J Schaeffer c est un
127. ent on lui donne une explication sur ses erreurs et quel type d explication donner A partir de ces r flexions nous avons d fini une m thode de conception de nos interfaces p dagogiques qui nous semble g n rale 29 5 Une m thode conception dirig e par les erreurs La m thode de conception dirig e par les erreurs d une interface p dagogique que nous proposons comporte un certain nombre d tapes d crites ci dessous D finir la structure diter Choisir les l ments validables Choisir les possibilit s de modification donn es l l ve Choisir le moment de signalement des erreurs d tect es D finir les explications et les aides Figure 3 5 1 D finir la structure diter Nous avons vu qu une interface p dagogique est un diteur de structure arborescente Le travail que nous avons fait pr c demment nous a permis de d finir un mod le du domaine du d nombrement y compris des probl mes et des solutions A partir de ce mod le nous d finissons les structures diter pour les diff rentes machines correspondant aux diff rentes classes de probl mes Dans le cas de la machine ConstructionEnsemble la structure diter est celle de la figure 4 L l ve choisit son exercice et construit sa solution Exercice un Exercice Solution une Solution Univers un UniversParties R f rentiel unR f rentiel Cardinal unEntier Construction une ConstructionDePartie S
128. er que le probl me n a pas de solution si l on montre que tous les choix permis conduisent une contradiction 3 Les r gles qui permettent de r soudre un probl me Un probleme est r solu en utilisant les connaissances qui permettent d atteindre la solution en cr ant de nouvelles contraintes en d couvrant une contradiction en liminant des liens possibles d un l ment de d part ou d arriv e d une correspondance en trouvant des liens certains pour un de ces l ments etc Il existe pour cela un certain nombre de r gles elles sont g n rales car valables pour n importe quel probl me mais elles peuvent tre sans int r t pour certains de ces probl mes Quand on les donne au syst me elles ne contiennent que l indication de ce qui est n cessaire pour qu on ait le droit de les appliquer mais pas de m taconnaissances sur leur mode d emploi comme des indications sur les situations o il est bon de les appliquer ni sur celles o il ne faut pas les utiliser non parce que ce serait ill gal mais parce que cela ne servirait rien Nous allons prendre pour exemple une r gle que nous appellerons R1 qui exprime que si l on a une contrainte de la forme X Y et si une borne sup rieure de X est inf rieure 120 une borne inf rieure de Y on a alors une contradiction Nous d finissons d abord des l ments qui peuvent appara tre dans la r gle CONTRAINTE R TERME X TERME Y Nous i
129. es humains Schoenfeld 85 Pitrat 991 le monitoring est essentiel pour diriger de fa on souple le comportement d un syst me d Intelligence Artificielle et pour viter de faire syst matiquement une r solution m tacombinatoire Il doit tout superviser en 115 examinant r guli rement le d roulement de ce qui se passe m me quand on utilise des connaissances compil es Gr ce au monitoring l Le syst me ne tourne pas en rond Il se rend compte quand il fait toujours la m me chose dans ce cas il change une des actions pour sortir de la boucle Il remarque si un essai est ou non proche d un r sultat int ressant Si l on sait que X est inf rieur 10 trouver que X est inf rieur 10000 montre que l on tait loin du but Par contre trouver que X est inf rieur 11 n apporte pas davantage mais cela montre que l essai valait la peine d tre tent Il voit que l on red couvre des r sultats d j obtenus pas exemple on recr e une contrainte que l on avait d j trouv e Il se rend compte d une mauvaise surprise Il s attendait un succ s alors que l on n aboutit rien Cela se produit plus souvent en utilisant des m taconnaissances compil es o l on croit que la m thode suivie doit mener la solution mais il lui arrive parfois d chouer Il se rend compte d une bonne surprise D apr s ses pr visions on avait peu de chances de r ussir et po
130. es hypoth ses comporte alors de nombreux aspects sp cifiques 4 Nous utiliserons plut t dans la suite de ce papier le terme de choix abstrait pour d signer ces choix de contr le Le terme de m ta choix sera r serv aux choix concernant l annulation ou la modification de choix 54 Cette question s est rapidement pos dans le syst me MARECHAL qui permet de construire des solutions complexes pour des probl mes d optimisation et qui utilise intens ment des choix abstraits Une premi re m thode a alors t impl ment e pour r pondre ce probl me A posteriori celle ci ne s est pas r v l e totalement satisfaisante et une seconde m thode bas e sur une philosophie oppos e est en cours d impl mentation Le but de cet article est donc de pr senter et comparer ces deux m thodes pour d terminer dans quels cas elles sont int ressantes Pour cela nous commencerons dans la seconde partie de ce papier par pr senter plus en d tail le probl me pos en abordant d une mani re g n rale la construction de solution complexe et le raisonnement hypoth tique Les deux parties suivantes seront ensuite consacr es la description des deux m thodes que nous nous proposons de comparer Chacune de ces deux parties tudiera les avantages et inconv nients respectifs des m thodes 2 Construction de solutions complexes et raisonnement hypoth tique Le syst me que nous construisons baptis MARECHAL est un
131. essentiellement se posent la r alisation d un syst me g n ral de r solution de jeux Il est possible de s attacher traiter l apprentissage de connaissances a priori partir des r gles du jeu ou a posteriori par une tude des parties d j jou es Le second domaine de recherche est l utilisation des connaissances qu elles soient apprises par le syst me ou donn es par un expert L apprentissage est n cessaire pour la r alisation d un syst me autonome Mais quoi serviraient les connaissances apprises si celui ci est incapable de les utiliser correctement et efficacement Les deux principales m thodes cognitives pour la r solution du jeu en JA sont d une part le syst me expert par l emploi de connaissances conseils sur les choix effectuer donnant directement et de fa on plut t r active situation connaissances gt d cision la d cision prendre D autre part des algorithmes de recherche arborescente font une valuation des coups l gaux partir de l valuation d un tr s grand ensemble de situations pr dites par d roulement des r gles du jeu sur l ensemble des choix et v nements possibles du syst me et de ses adversaires 38 La premi re m thode offre l avantage d tre facilement explicable l tre humain car bas e sur des connaissances provenant d experts humains La seconde m thode reposant sur une exploration trop grande pour la m moire court terme de l tre humain est en g n ral
132. est roi ou hauteur est roi ET couleur n est pas noire A ce niveau les erreurs possibles concernant l attribut sont attribut inexistant pour le r f rentiel de l exercice masse pour une carte ou valeur erron e pour un attribut hauteur 2 dans un jeu de 32 cartes Une premi re erreurs sur SE est de d finir pour SE l ensemble vide 2 cartes de couleur pique et de couleur rouge Les autres erreurs sur une seule tape font intervenir des sous ensembles qui ne font pas partie d une solution correcte de l exercice r soudre L l ve d finit la contrainte 26 2 cartes de hauteur dame alors que l on attend 2 valets ou 2 rois ou bien il d finit la contraintes 2 cartes de couleur rouge alors que l on attend 2 c urs Les erreurs que l on vient de d crire correspondent une tape isol e Certaines erreurs apparaissent lorsque l on consid re l ensemble des tapes Il peut y avoir d une part des erreurs sur la somme des nombres d finis chaque tape Il y a deux types d erreurs des incoh rences et des incorrections Les incoh rences sont internes la solution de l l ve il a d fini les mains de 8 cartes pour l univers et de 10 cartes ou de 3 la fin des tapes Les incorrections sont externes par rapport la solution de l l ve Sa solution est coh rente mais ne correspond pas une solution de l exercice r soudre Il a d fini les mains de 5 cartes pour l univers et a bien d fini les tapes p
133. et ho et si v1 et V2 sont des valeurs sous optimales v1 lt vi et v2 lt v2 pouvant tre obtenues sous ces deux m me hypoth ses de telle sorte que les solutions partielles sont non conflictuelles alors on pourra avoir v1 v2 gt v1 et v1 v2 gt v2 Un tel exemple est montr sur la Figure 5 o le syst me a trouv trois zones int ressantes pour une offensive Comme il n y a pas de conflit entre la troisi me hypoth se et les deux autres celle ci pourra tre tudi e ind pendamment Par contre la premi re hypoth se entre a priori en conflit avec la seconde car certaines pi ces sont utilis es dans les deux cas Il faut donc dans ce cas chercher si une solution combin e existe Si le nombre de pi ces en conflit est faible par rapport au nombre de pi ces utilis es pour les deux offensives il est probable que les deux offensives pourront tre construites en se partageant les pi ces en conflit La combinaison de ces deux offensives moins puissantes sera alors certainement plus int ressante qu une seule des deux Figure 5 Exemple de conflit de ressource entre hypoth ses 61 La seconde approche consiste accepter d tudier en th orie les 2 combinaisons de possibilit s tout en contr lant cette tude pour ne parcourir en pratique qu un nombre raisonnable de solution Ces deux approches diff rentes ont t baptis es respectivement a posteriori et a priori car la premi re g re
134. eur int alpha int beta int valeur Best i N char PositionSuivante 100 if profondeur PROFMAX return Evaluation Position N TrouveCoupsPossibles Position PositionSuivante Best INFINI for i 0 i lt N itt valeur NegaAlphaBeta PositionSuivante i profondeurt1 beta alpha if valeur gt Best Best valeur if Best gt alpha alpha Best if alpha gt beta return Best return Best 2 4 L effet d horizon approfondissement s lectif et quiescence Il y a deux inconv nients au fait qu on doive fixer une profondeur maximum Le premier tant que le programme ne peut pr voir les effets d un coup une profondeur d passant la profondeur maximum Le second est que cela introduit des effets pervers dans les choix du programme le programme fera toutes les menaces qu il peut et qui sont pourtant inutiles pour repousser au del de son horizon un v nement qui lui est d favorable C est ce qu on appelle l effet d horizon le programme repousse les v nements d favorables au del de son horizon La solution utilis e dans Deep Blue comme parade l effet d horizon est d utiliser une m ta 8 fonction d valuation qui n value pas la position mais plut t qui value le type de la position Cette m ta fonction d valuation value si une position est stable essentiellement s il reste des pi ces
135. eur ou quivalent pour lui qu un choix alternatif C2 alors il est inutile d tudier C2 2 1 4 Les jeux n joueurs Les algorithmes pr c dents ne peuvent s appliquer des jeux n joueurs Leur adaptation n joueurs peut para tre dans un premier temps ais l alternance des coups se faisant sur n joueurs plut t que 2 On obtiendrait ainsi un algorithme min min max pour un 41 jeu 3 joueurs et dans le cas g n ral un algorithme min n 1 max Cependant la grande majorit voir la totalit des jeux plusieurs joueurs fait intervenir les participants dans des relations plus complexes que celles suppos es jusqu ici En effet un algorithme min n 1 max pose implicitement l hypoth se que les autres joueurs sont non seulement des adversaires pour ce dernier mais en plus sont tous en coop ration pour la r alisation d un unique but faire perdre le syst me Dans les faits les jeux offrent au contraire une plus grande vari t de relations entre les participants le seul but commun dont on peut tre absolument certain dans l ensemble est que chacun joue pour lui m me ceci n implique pas forc ment qu il joue contre le syst me ni contre tous les autres 2 1 5 Les jeux information incompl te Pour les jeux information incompl te le probl me se complexifie de nouveau En effet les coups l gaux chaque tour des joueurs adverses ne sont pas connus Aux jeux de cartes par exemple il n est pas possible e
136. eurs et s il y en a elles doivent tre d tect es et signal es le plus t t possible avec des explications Ici on peut introduire volontairement la possibilit pour l l ve de commettre des erreurs on peut d cider de ne pas les signaler tout de suite ou de ne pas les expliquer 33 compl tement Actuellement dans la machine ConstructionEnsemble les erreurs sont signal es d s qu elles sont d tect es 5 5 Explications et aides Lorsqu une erreur est signal e on peut d cider de ne pas expliquer tout de suite l l ve pourquoi il y a une erreur Il peut tre plus p dagogique de lui laisser chercher la cause de l erreur Cependant il ne faut pas qu un l ve se sente bloqu ou qu il ne comprenne pas C est pourquoi nous avons d cid de donner l l ve la possibilit d avoir des explications sur son erreur en interrogeant le syst me par un bouton D autre part l l ve ne doit jamais tre bloqu dans l utilisation d une machine Nous avons donc pr vu une aide contextuelle afin de lui expliquer tout instant ce que le syst me attend de lui Il nous a sembl alors logique de rassembler aide contextuelle dans le maniement de la machine et explication sur l erreur qui vient d tre signal e dans une m me bo te de dialogue comportant plusieurs onglets De la m me fa on l l ve a besoin d aide contextuelle sur le d nombrement Cette bo te de dialogue comporte aussi un onglet d nombrement qui lui
137. eut montrer que G AI avec I mil B C et que G est centre de gravit du triangle ABC alors mettre le sous but correspondant a vrai et m moriser pourquoi Cr ation si G est centre de gravit de ABC avec I mil B C et que la droite AI n existe pas pour le syst me alors la cr er et m moriser les conditions de cr ation 7 Appels de conjectures en cours de preuve Le syst me a la possibilit d appeler des conjectures guid es par le but en cas de configurations incompl tes permettant d avancer vers une des conclusions partielles a prouver Un exemple de r gle appelant une conjecture se trouve dans la section 7 3 7 1 Que se passe t il en cas d appel De nouveaux concepts sont introduits et des objets cr s en fonction de ce que demande la conjecture Il y a chargement de nouvelles r gles et r ordonnancement car le syst me reconstruit une nouvelle liste de r gles actives Pour l instant tout fait d duit au sein de la conjecture ainsi que les objets cr s sont conserv s par la suite Si la conclusion finale est prouv e en milieu de conjecture alors le syst me sort et la d monstration est termin e Une conjecture prouv e appara t comme un nouveau fait d duit et on a m moris le sous arbre ayant permis son mergence Si il y a chec lors d un appel on reprend le fonctionnement global avec ventuellement appels d autres conjectures Si Argos a eu besoin de faire appel une conjecture p
138. eux entre le temps perdu faire de la combinatoire et celui faire de la m tacombinatoire 4 Le langage proc dural de r solution de probl mes Un expert r sout g n ralement un probl me en allant directement la solution une fois qu il a identifi le type du probl me J ai voulu simuler ce comportement en donnant un langage dans lequel on d finit des plans de r solution d une famille de probl mes Dans une premi re tape je construis ces plans mais le langage dans lequel ils sont crits devra permettre ult rieurement au syst me soit de les modifier soit d en cr er de nouveaux Ce langage permet d indiquer au syst me la fois quelles actions il doit consid rer et dans quel ordre il devra les ex cuter Pour chaque type d v nement on d finit une s quence d ordres Un v nement peut tre la cr ation d un lien certain entre un n ud de l ensemble de d part et un n ud de l ensemble d arriv e la destruction d un lien possible entre deux tels n uds la cr ation d une nouvelle contrainte la d termination de la valeur d un degr pour une des correspondances etc De plus pour initialiser le processus une s quence particuli re doit s ex cuter au d but de la r solution d un probl me Pour chaque s quence sauf celle d initialisation on appelle foyer de l v nement l l ment sur lequel a port l v nement par exemple le n ud de l ensemble d arriv e auqu
139. ez soi de r soudre ceux qu on avait pas r ussi r soudre et de d couvrir les fautes que l on a faites dans quelques autres on est aid par cela par la diff rence entre le score obtenu et le nombre de probl mes que l on croyait avoir r solus correctement Pour les probl mes 2000 je dispose des brouillons complets que je m tais impos e cette ann e de faire proprement sans m langer les probl mes 79 2 3 Page Web de Jean Marc Fouet http www710 univ lyon1 fr fouet Dir_lic_mai TP puzzles html C est la source d un des probl mes section 6 3 qui est assez classique et que j avais d j eu l occasion de rencontrer On verra pourquoi la m moire m a t de peu de secours et pourquoi je pense qu elle me sera utile dor navant 3 Le b tisier Dans cette section on ne trouvera que des probl mes des Jeux math matiques o le temps limit m a permis de ne pas oublier quelques grosses erreurs Les probl mes 3 1 3 3 et 3 4 montrent des tourderies stupides le probl me 3 2 un raisonnement faux car trop rapide Dans le probl me 3 4 une grosse tourderie initiale a t difficile trouver c est souvent le cas des erreurs des plus grossi res Dans ce m me probl me on verra comment des simplifications et des v rifications sur des cas particuliers simples ont aid la r solution comment une petite erreur a t trouv e apr s le r sultat ainsi que quelques petites inex
140. face p dagogique destin e un certain type d l ves poss dant certaines connaissances et en fonction d un certain niveau d approfondissement et d expertise vis C est ce que nous avons d faire pour les d nombrements 4 2 Validit d une solution erreurs La validit d une solution est d finie par une conjonction de conditions de validit portant sur la structure Une erreur est d finie comme tant une violation d une de ces conditions de validit On peut ainsi distinguer des types d erreur correspondant aux conditions de validit une erreur est de tel type si elle viole telle condition On peut assigner chaque type d erreur un int r t p dagogique lorsque l l ve commet une erreur et qu on la lui signale quel b n fice peut il en retirer du point de vue de la compr hension des concepts du domaine de l identification des difficult s et de l apprentissage de m thodes de r solution Suivant les buts p dagogiques vis s une erreur pourra tre jug e instructive ou non Les erreurs non instructives sont consid r es comme des diversions hors sujet qui encombrent le chemin vers l apprentissage vis Cela ne signifie pas qu elles sont sans importance th orique mais simplement qu elles loignent trop du but particulier choisi Il est bon alors que l interface soit con ue de telle fa on que ces erreurs ne puissent pas appara tre Cela revient dire que c est le syst me lui
141. faut introduire un test de non r p tition de la r gle puis constituer la partie action et m morisation pour le graphe de la preuve ainsi que son explication 147 6 2 3 Optimisation de l ordre des sous buts et mise au point finale Pour qu une r gle puisse s appliquer de fa on optimale l ordre des sous buts est tr s important Il faut par exemple placer les configurations rares ou sp cifiques en premier pour instancier le plus t t possible la r gle avec les bonnes variables D autre part il faut qu une variable soit instanci e avant que l on puisse l utiliser Il faut aussi ma triser le retour arri re Il a donc fallu d finir une hi rarchie dans la recherche des conditions d application v rification prioritaire configuration v rification de base appel de proc dures de calcul Chaque r gle construite est aussi associ e un ou plusieurs domaines elle peut tre ventuellement associ e un savoir faire et elle va tre typ e en fonction des concepts pr sents dans son corps en partie hypoth se ou conclusion ceci en vue du chargement de r gles adapt es l exercice donn 6 3 Diff rents types de r gles Le syst me construit des r gles d duction tout venant tr s proche de la propri t math matique tous les objets n cessaires doivent tre pr sents dans la base de faits Voici la d marche de construction r cup ration des objets nommables au sein de la propri t d coupage
142. gnalement les explications et la r ponse la demande de validation de l l ve Le p dagogue transmet alors ses d cisions la machine qui va les mat rialiser pour l l ve Tout p dagogue est repr sent par une structure qui contient la machine laquelle il est associ la session et les diagnostics La session comporte toutes les informations li es l exercice r soudre en particulier la solution du syst me et s enrichit de la solution de l l ve au fur et mesure de sa construction au moyen de la machine Il y a autant de diagnostics que de conditions de validit Chacun d entre eux est repr sent par un bool en valeur de la condition de validit et une liste d erreurs ventuellement vide La figure 9 montre la structure du p dagogue ConstructionEnsemble associ e la machine ConstructionEnsemble cf 2 Machine une MachineConstructionEnsemble Session une SessionCE Diagnostics Diagnostic Valeur Boolean Erreurs Erreur Figure 9 Dans cette architecture le p dagogue g re les erreurs en r pondant aux demandes de validation de l l ve que la machine lui transmet Pour cela il interroge le domaine et prend des d cisions qu il communique la machine La gestion des erreurs est donc bien programm e part ce qui nous donne une grande souplesse qui permettra de personnaliser cette gestion en fonction de l l ve 36 7 Conclusion Dans le projet Combien nous c
143. ha alors le coup n est pas tudi plus profond ment On utilise un facteur de r duction R pour choisir la profondeur de recherche du coup nul Si 10 on est dans un n ud pour lequel on s appr te faire une recherche de profondeur P la profondeur de la recherche associ e au coup nul sera P R On choisit en g n ral R 2 ou R 3 2 6 L approfondissement it ratif L approfondissement it ratif commence par effectuer une recherche de profondeur 1 puis recommence avec une recherche compl te profondeur 2 et continue ainsi faire des recherches des profondeurs de plus en plus grandes jusqu ce qu une solution soit trouv e Puisqu une telle recherche n engendre jamais un n ud tant que les n uds de profondeurs plus petites n ont pas t engendr s elle trouve toujours la solution la plus courte De plus si l algorithme se termine une profondeur d sa complexit en espace est en O d c est dire lin aire en fonction de la profondeur de recherche A priori l approfondissement it ratif perd beaucoup de temps dans les it rations pr c dant la solution Toutefois ce travail suppl mentaire est g n ralement beaucoup plus petit que la derni re it ration S il y a n coups possibles en moyenne pour chaque position le nombre de positions la profondeur d est n Le nombre de n uds la profondeur d 1 est de n pour la d 1 it ration et chaque n ud est engendr deux fois une fois
144. herchons formaliser au maximum nos r flexions pour qu elles soient ensuite utilisables dans d autres contextes Nous avons ainsi introduit une m thode de conception d interfaces p dagogiques partir des erreurs L utilisation de la conception objet nous permet d impl menter nos r flexions de fa on tr s d clarative Nous avons ainsi un cadre g n ral de construction des syst mes machines p dagogues qui nous permet de faire des exp rimentations de nos diff rentes r flexions Nous d finissons actuellement partir de cette m thode la machine ConstructionListe 8 Bibliographie Choplin and al 98 Hugues CHOPLIN Arnaud GALISSON Sarah LEMARCHAND Hyperm dias et p dagogie comment promouvoir l activit de l l ve Actes du quatri me colloque Hyperm dias et apprentissages pp 87 98 J F Rouet et B de la Passardi re eds 1998 Le Calvez et al 97 Le Calvez F Urtasun M Tisseau G Giroire H Duma J Les machines construire des interfaces pour apprendre une m thode constructive de d nombrement Actes des S mes Journ es francophones EIAO pp 49 60 M Baron P Mendelsohn J F Nicaud eds Herm s 1997 Tisseau et al 00 1 Tisseau G Giroire H Le Calvez F Urtasun M Duma J Principes de conception d un syst me pour enseigner la r solution des probl mes par la mod lisation RFIA 2000 pp 121 130 Paris 2000 Tisseau et al 00 2 Tisseau G Giroire H Le Calvez F Urtasun M and
145. hypoth tique sur les m ta choix Un tel 65 mode de raisonnement serait d ailleurs inadapt ici Au lieu d crire un m canisme interne pour rechercher des solutions compatibles nous avons donc fourni au syst me un sch ma de r solution Au moment de son appel les variables a et b contiennent les num ros des deux solutions partielles rendre compatibles Le sch ma est constitu de deux phases comme le montre la Figure 9 une phase d analyse et une phase de choix La premi re phase est une phase d analyse au cours de laquelle le syst me r pertorie les choix en conflit puis d termine a priori les possibilit s de remplacement et d annulation pour ces choix en calculant pour chacun un int r t Pour cela le syst me fait appel une proc dure d analyse interne AnalyseIncomp Cette proc dure produit un ensemble de faits de la forme Remplacement Sit c d f e g ou Annulation Sit c d e Les premiers permettent d indiquer que le choix d de la situation c peut tre remplac par le choix e f est la ressource en conflit dans le choix d et g la ressource quivalente dans e Les seconds indiquent qu il est possible de supprimer le choix d de la situation c f contenant toujours la ressource en conflit dans le choix d recherche du meilleur compromis de situation compatible partir des situations incompatibles Sa et Sb Appel AnalyseIncomp Sa b remplaceme
146. i le temps de recherche est lev Elle peut en effet parcourir plus syst matiquement l espace des possibilit s alors que la m thode a posteriori ne peut atteindre qu une partie restreinte de cet espace M me avec un temps plus court la m thode a priori fournie des 16 Une hypoth se tant la s lection d une possibilit pour un choix abstrait elle engendre des choix concrets et conduit donc une modification de la solution courante i e ajout de mouvement dans le cas d un jeu de strat gie 74 solutions plus coh rentes L encore les r sultats devront confirmer ces affirmations 4 3 3 Conclusion sur la comparaison des deux m thodes En conclusion on peut affirmer que la m thode a priori est meilleure que la m thode a posteriori sauf dans le cas particulier d hypoth ses fortement ind pendantes o elle est l g rement plus lente Ces deux m thodes tant donc compl mentaires on pourrait penser utiliser l une ou l autre selon la circonstance En pratique cela n est pas envisageable car il est impossible de savoir a priori si deux hypoth ses sont ind pendantes ou non Ce sont en effet les cons quences des hypoth ses qui entrent en conflit et le raisonnement doit avoir eu lieu pour pouvoir tudier ces cons quences 5 Conclusion Dans ce papier nous avons montr que la combinaison d hypoth ses tait incontournable dans les probl mes d optimisation soluti
147. i n ont certes pas conduit la solution mais des id es qui elles ont conduit la solution Il ne s agit donc pas de r dactions de preuves les plus courtes les plus simples les plus l gantes possible qui seraient donn es s il ne s tait agi que de donner les solutions des probl mes et elles ne doivent pas tre consid r es comme des mod les de preuves ce n tait pas le but Outre l lagage de tout de qui n est pas n cessaire directement la preuve un travail de simplification et de clarification de notations serait alors faire Apr s avoir donn l origine et le contexte des probl mes analys s section 2 les grosses b tises dont je suis coupable section 3 j analyserai des probl mes pour lesquels de 17 devant une table ou plus inconfortablement dans le m tro ou pendant une r union qui tra ne en longueur 18 en marchant ou avant de m endormir 78 premi res id es se sont r v l es fausses mais ont n anmoins conduit de bonnes id es section 4 et des probl mes dans lesquels les bonnes id es sont apparues apr s des chemins d tourn s et inutilement compliqu s section 5 On verra galement des cas o la m moire a jou un r le positif et des cas o elle n a servi rien section 6 Enfin d autres probl mes seront voqu s rapidement en sections 7 et 8 2 Sources des probl mes Les probl mes analys s proviennent des trois origines suivantes
148. il reste 1234 a placer soit a4 5 possibilit s si4enbas_ ou bien a gauche et le suivant est 5 ou 6 et dans chaque cas a4 5 possibilit s ou bien au milieu entour de 5 et 6 2 possibilit s et il reste 123 a placer soit 3 gauche a3 2 possibilit s soit 1 gauche et 2 a droite 3 1 3 possibilit s Au total 36 5 2 5 2 2 3 61 Difficilement g n ralisable pour n 7 a devrait encore aller mais pour n 8 par exemple si 5 est en bas il faut envisager deux parmi 678 c t Pour n plus grand ce sera encore pire Enfin une bonne id e plut t que de s int resser ce qui pourrait tre en haut ou en bas regarder ce qui est n cessairement en haut soit 6 et remplir gauche et droite par 12345 si 6 est le 2 un quelconque parmi 12345 a gauche 5 possibilit s et une 4 zigzag droite avec ce qui reste a4 5 possibilit s soit 5 5 25 possibilit s si 6 est le 4 deux parmi 12345 droite C3 10 possibilit s et une 3 zigzag droite avec ce qui reste a3 2 possibilit s soit 10 2 20 possibilit s si 6 est le 6 as 16 possibilit s pour le reste 1 Soit au total 25 20 16 61 possibilit s a Cha a4 C2 az a2 C3 ds ag Et c est facilement g n ralisable an jee ai an i 1 i 1parpasde2 soit pour n 7 a7 Ch ay as ge a3 a3 Ceas ay 6 1 16 20 2 2 6 16 1 272 L algorithme du Monde c est bien un algorithme et pas seulement une formule
149. in la bonne id e qui consiste consid rer al 1 les angles ext rieurs qui sont gaux aux Qi de tout l heure 01 02 est gal langle orient du 1 c t avec le 3 Les sommes des angles consid r es sont les angles d un des c t s avec successivement tous les autres Les cosinus multipli s par la longueur commune a sont les projections des vecteurs c t s sur l un d eux celui ci contribuant pour a et la somme 1 cos al cos a1 amp 2 cos a1 2 3 cos a1 2 3 a4 est bien nulle puisque la somme des 5 vecteurs c t s est nulle O1 2 03 q4 93 On peut aussi faire directement le cas du d placement MM quelconque en projetant sur une droite perpendiculaire MM En ce qui concerne la deuxi me question avec des angles gaux je pensais d abord que la r ponse tait non Mais de ce qui pr c de je d duis imm diatement que la r ponse est oui en consid rant un pentagone r gulier inscrit dans le cercle trigonom trique et en projetant la somme des vecteurs c t s sur l axe des x La r ponse du Monde est d une simplicit telle que je regrette de ne pas l avoir trouv e L aire du pentagone est la somme des aires des cinq triangles de sommet M La suite est alors triviale Par contre la r ponse la deuxi me question est moins simple que la mienne on part du pentagone r gulier et on le d forme Conclusion Il est difficile de savoir pourquoi l
150. ir atteindre ceci sous l hypoth se que l autre joueur suit un raisonnement analogue au syst me une profondeur n 1 Autrement dit il existe au moins une succession de n 2 choix du syst me partir de la situation S telle que quels que soient les choix de l adversaire toutes les situations une profondeur n r sultantes auront pour valuation pessimiste une valuation pessimiste sup rieure ou gale l valuation pessimiste de S et la valeur pessimiste de S est la plus grande satisfaisant cette contrainte D un autre c t il n existe aucune succession de n 2 choix du syst me partir de la situation S telle que la plus petite des valeurs optimistes des situations de profondeur n r sultantes de chacun des n 2 choix de l adversaire correspondants soit strictement sup rieure la valeur optimiste de S et la valeur optimiste de S est la plus grande satisfaisant cette contrainte Les deux id es du B que nous retenons principalement pour la suite du papier sont que les deux valuations optimiste et pessimiste procurent une information non seulement sur l valuation de la situation mais aussi sur l impr cision de cette valuation les conditions des coupes alpha beta ont t adapt es a des fonctions d valuation de nature diff rente la r gle importante d tablissement des coupes de l alpha beta est donc la r gle g n rale d j mentionn e en 2 1 2 si un choix CI du syst me est assur ment meill
151. is l obliger quand m me trouver et r diger de lui m me Si par exemple dans un exercice l l ve a demand pourquoi le point i est milieu de ab Argos pourra par exemple lui r pondre que c est parce que ajbc est un parall logramme et que i est l intersection des diagonales ou toute autre indication du m me type Le syst me est param trable et pourrait l tre par exemple par un professeur qui voudrait faire travailler ses l ves dans cet esprit sans 153 que l l ve puisse avoir une r ponse compl te mais seulement partielle Cette dynamique o l on cherche rendre actif l l ve devrait permettre d aiguiser sa d marche heuristique alors que celui ci abandonne souvent ses id es en cours de route par manque de confiance en soi Pour un type de conclusion donn e l l ve peut demander au syst me une liste de savoir faire permettant de la d duire Voici un exemple de genre de savoir faire qu il pourrait obtenir en demandant comment faire pour montrer qu un triangle ABC est rectangle en A Pour montrer qu un triangle ABC est rectangle en A montrer que BC 2 AC 2 BA 2 ou montrer que AB L AC ou montrer que ABC ACB 90 etc L utilisateur peut demander une preuve dans un certain esprit analytique configurations vectoriel transformations etc en faisant charger d abord les r gles du domaine correspondant comme expliqu dans 1 1 Il peut demander une preuve reposant sur un certain savoir faire en n
152. isir les possibilit s de modification donn es l l ve Il y a plusieurs fa ons de permettre l l ve de revenir sur ce qu il a fait Avant validation simplement en saisissant une nouvelle valeur l annulation d un seul item ou en annulant toutes les informations en cours de saisie dans le contexte valider Apr s validation l l ve peut vouloir modifier un l ment qui a t valid Dans ce cas l se pose le probl me du contexte restituer l l ve Suivant les cas on peut pr remplir 32 l diteur avec les informations venant de l l ment annul ou on peut pr senter un diteur vide C est un choix d ergonomie Cela peut aussi tre un choix p dagogique fond sur le co t d une annulation Si annuler demande un gros travail pour saisir nouveau un l ment l l ve y r fl chira deux fois la prochaine fois qu il devra valider L annulation d un l ment annule tout le sous arbre issu de cet l ment Actuellement voici les choix de correction explicite qui ont t faits Changer exercice apr s validation efface l exercice Changer Univers apr s validation efface l univers Effacer tape avant validation Modifier une tape de la liste des tapes apr s validation permet de l diter Modifier construction permet de l diter Figure 6 5 4 Choisir le moment de signalement des erreurs d tect es Contrairement ce q
153. iter d tre envisag es Une autre difficult rencontr e en r solution de probl mes est le cas o l on a des solutions pour plusieurs sous probl mes il faut composer ces solutions qui sont en g n ral partiellement incompatibles pour d finir la solution globale Le syst me MARECHAL qui joue des war games a un module pour composer ainsi des solutions partielles Par ailleurs le syst me MALICE qui est le r solveur g n ral de probl mes de MACISTE monitore la recherche de la solution pour en am liorer l efficacit La mise en uvre de ce m canisme de monitoring montre la n cessit d inclure un m tamonitoring pour viter que le syst me ne perde trop de temps monitorer cette recherche Il est enfin toujours utile de comprendre comment les tres humains se comportent lors des activit s que nous avons de la peine faire effectuer par un syst me d IA Aussi Dominique Pastre a t elle observ le comportement humain pendant la r solution d une grande vari t de probl mes aussi bien math matiques que de type casse t te Nous nous int ressons galement aux applications de PIA l enseignement Le groupe Combien montre comment un syst me d enseignement peut g rer les erreurs de l l ve en utilisant une interface p dagogique adapt e Par ailleurs le syst me ARGOS s attache a produire une explication claire des exercices qu il a r solus de fa on pouvoir donner l l ve une preuve
154. itude que a doit marcher en alternance avec l id e que cela repose sur un th or me difficile de th orie des graphes Puis impression que mon raisonnement doit marcher j attends lundi pour voir si ou bien la solution est celle que j entrevois et comment elle est expliqu e ou bien la solution repose sur une id e simple que je n ai pas vue Lundi solution du Monde on parvient communiquer en 2 N 4 appels Il semblerait qu on ne puisse pas faire mieux si des lecteurs peuvent le prouver qu ils nous crivent Reprise des raisonnements sur le nombre de couples compl mentaires et sur leur disparition en fonction des appels Je n arrive pas pr ciser mon raisonnement Introduction de la notion de cha ne de couples compl mentaires et de cycle Exemples Say a 3 5 couples mais 4 compter comme 3 3 couples compter comme 2 Introduction de la notion de couples isol s difficiles compter x Je m aper ois que dans la configuration 4 fondamentale il n y a pas 2 couples compl mentaires mais 4 Id e d introduire le nombre de sommets impliqu s dans des couples compl mentaires et de diviser par 2 On retrouve bien 2 dans le dessin pr c dent C est toujours aussi confus abandon proche Puis id e de la connexit obtenue galement en au moins n 1 appels qui peut arriver avant la compl tude J abandonne alors l id e de d couper avec un morceau de 2 ou de 4 On consid re plut t
155. l l ve On rencontre souvent ce probl me en p dagogie tous les concepts de la th orie ne sont pas mettre au m me niveau Pr senter explicitement certains concepts l l ve trop t t lui compliquerait les choses et l emp cherait de se concentrer sur l essentiel Ici par exemple on souhaite que l l ve retienne qu une solution est form e d un univers et d une construction celle ci tant une liste d tapes Pour chacun de ces concepts on doit introduire un mot qui le d signe pour l l ve le mot tape correspond au concept de SousPartie de la structure une d finition et des exemples Les concepts non validables ne sont pas forc ment explicit s l l ve Il faut alors que l interface les rende vidents Pour cela on utilisera le langage naturel une m taphore des structures graphiques etc Ainsi dans la structure ci dessus l l ve ne valide pas chaque l ment de la SousPartie L interface lui fait remplir une phrase trous l aide de menus 31 Warto iz ls aaa His fi Effacer cette tape le veux 2 x l ments v rifiant Nouvelle Propri t Supprimer une Propri t f la hauteur x est Roi M est fl est i _ EES Ajouter l tape tels que ja haute wy a hauteur es Figure 5 La validation de l l ment peut donner lieu a des signalements d erreurs instructives Ce sont les erreurs qui permettent l l
156. l adapt que des intentions adverses dans un jeu de strat gie comme le pr voit la th orie des jeux Lorsque les hypoth ses portent sur des concepts contr lables la phase de s lection consiste simplement choisir la solution de gain maximal Pour les concepts incontr lables le m canisme est diff rent car la solution finale doit maximiser l esp rance de gain d apr s la r partition de probabilit estim e sur les possibilit s test es L un des probl mes du syst me est alors de d terminer cette r partition de probabilit Il r fl chira par exemple au coup le plus probable de l adversaire dans un jeu de strat gie la probabilit qu un adversaire ait une carte plus forte dans un jeu de carte etc Dans la suite de ce rapport nous nous focaliserons sur les hypoth ses portant sur les choix abstraits du syst me c est dire sur des hypoth ses contr lables N anmoins les m thodes d crites sont adaptables aux hypoth ses incontr lables 2 5 Probl matique du raisonnement hypoth tique dans le syst me MARECHAL Si les choix abstraits permettent en th orie de mieux contr ler la recherche d une solution leur gestion dans le cadre de solutions complexes pose en pratique de nouveaux probl mes 10 Nous parlons ici de jeux simultan s Dans le cas de jeux altern s comme les checs les intentions adversaires peuvent tre consid r es comme contr lables puisque l on peut d terminer en th orie c
157. l est inutile de continuer le d veloppement de C2 Si un coup C1 d un niveau min choix de l adversaire est valu f C1 et qu un coup C2 1 est valu f C2 1 lt C1 alors il est inutile d explorer plus avant le coup C2 L alpha beta est strictement quivalent au min max du point de vue de la solution obtenue Son am lioration est uniquement un gain de complexit En particulier il est bas lui aussi implicitement sur l hypoth se que le joueur adverse utilise un raisonnement du m me type que lui 40 2 1 3 Le B Le principe original sur lequel repose le B Berliner 79 est l utilisation de 2 nombres pour repr senter l valuation d une situation un nombre optimiste et un nombre pessimiste La remont e de ces valuations est r alis e selon un principe analogue au min max A travers les arcs min la valeur optimiste resp pessimiste du n ud p re est obtenue par l application de l op rateur min sur l ensemble des valeurs optimistes rep Pessimistes de ses n uds fils A travers les arcs max la valeur optimiste resp pessimiste du n ud p re est obtenue par l application de l op rateur max sur l ensemble des valeurs optimistes rep Pessimistes de ses n uds fils La valeur optimiste d un n ud correspond la valeur que le syst me est assur de r aliser une profondeur n dans la situation repr sent e par le n ud la valeur pessimiste la valeur que le syst me est certain de ne pouvo
158. le jeu de l ascenseur nous proposons dans un premier temps les m tar gles suivantes qui malheureusement sont la fois trop rigides et trop sp cifiques ce jeu du fait qu elles r sultent de la fusion d un ensemble de m tar gles g n rales qu il reste encore d couvrir 46 D un autre c t elles pr sentent l avantage d tre op rationnelles rapidement Conseils sur les hypoth ses de type Choix du syst me Si N est un n ud de l arborescence N contient un ensemble de conseils de poids p positif ou n gatif sur un choix de type C du syst me Le choix du type C n a pas encore t d termin dans N pl est le poids le plus lev de cet ensemble Alors il est bon p1 de poser une hypoth se sur ce type de choix partir de la situation N Cette m tar gle est d clenchable aussi bien pour des choix strat giques que tactiques partir du moment o des conseils au niveau du raisonnement de base ont permis de conclure sur l int r t de ces choix Conseils sur les hypoth ses de type Ev nement Si N est un n ud La carte pos e par Moi moi tant le joueur simul par le syst me est connue pour un pli P Le fait que Moi a remport le pli P ou non n est pas connu dans N Alors il est bon de poser l hypoth se sur le fait que Moi remporte le pli P ou non partir de N Si N est un n ud L ouvreur d un pli P n est pas Moi dans N La couleur demand e du pli P n est pas connue dans N Alors il e
159. les re d montre progressivement les m mes th or mes en fonction des connaissances fournies au syst me Le d monstrateur d montre environ 250 th or mes en g om trie des configurations niveau lyc e parall logrammes triangles milieux cocyclicit angles g om triques ou orient s Thal s Pythagore etc en calcul vectoriel g om trie analytique et transformations planes Les exemples proviennent pour la plupart de livres de secondes Terracher Hachette Secondes par exemple ou ont t propos s pour certains par des coll gues de math matique Les temps de d monstrations sont in gaux suivant les types d exercices et bien entendu suivant la fa on dont sont ordonn es les r gles actives Pour fixer les id es la plupart sont obtenues en moins d une minute sur un PC 200 Mz Le nombre de r gles construites est actuellement d environ 1200 et augmente en fonction des nouvelles connaissances fournies par l utilisateur Le d monstrateur d montre tous les th or mes figurant dans les th ses de Pintado Pintado 94 et Bazin Bazin 93 mais en prenant plus de temps en g n ral pour ceux de Pintado 94 la base de connaissances est peut tre plus grande Les temps de r solutions sont am lior s sensiblement par le chargement de strat gies apprises guid es par le but mais il manque l apprentissage automatique d heuristiques de cr ations ce qui bloque souvent le d monstrateur dans ses recherches 11 2 Objectifs Il
160. lisateur de d cider s il y a lieu de les impl menter Pour arriver supprimer l intervention humaine il faudra passer au stade sup rieur celui du m tam tamonitoring qui v rifierait que les changements propos s ne sont pas trop dangereux qui surveillerait de pr s ce qu ils donnent et qui aurait des garde fous simples et s rs pour contr ler l ensemble du fonctionnement du syst me 8 R f rences Lauri re 76 Lauri re J L Un langage et un programme pour noncer et r soudre des probl mes combinatoires Th se de l Universit Paris6 1976 Lauri re 78 Lauri re J L A Language and a Program for Stating and Solving Combinatorial Problems Artificial Intelligence 10 1978 29 127 Lauri re 96 Lauri re J L Propagation de contraintes ou programmation automatique Rapport LAFORIA 96 19 1996 Lenat 83 Lenat D EURISKO A Program that Learns New Heuristics and Domain Concepts Artificial Intelligence 21 1983 61 98 Parchemal 88 Parchemal Y SEPIAR un syst me base de connaissances qui apprend utiliser efficacement une expertise Th se de l Universit Paris 6 1988 Pitrat 96 Pitrat J Implementation of a Reflexive System Future Generation Computer Systems 12 1996 235 242 Pitrat 99 Pitrat J Une exp rience de monitoring Rapport de recherche LIP6 1999 014 1999 Schoenfeld 85 Schoenfeld A Mathematical Problem Solving Academic Press 1985 131 ARGOS Un D m
161. lors introduire les objets li s l nonc et pouvant tre utiles la preuve Une r gle s applique si sa partie condition est instanci e et alors la partie action se d clenche et rajoute la plupart du temps un fait nouveau qui devient alors une nouvelle hypoth se utilisable Il y a aussi m morisation des faits et de la r gle ayant permis son mergence ainsi que d un mod le explicatif instanci de cette d duction Ceci va permettre le filtrage de la base pour r cup rer le graphe de la d monstration et en donner une explication 2 4 Sortie du syst me Lorsque toutes les conclusions partielles ont t prouv es le syst me sort sur un succ s et indique que l exercice a t r solu Si par contre le temps de recherche maximum donn par l utilisateur a t d pass ou si le moteur est arriv au bout de la liste des r gles actives sans qu aucune ne puisse s appliquer le syst me sort sur un chec et va chercher un autre nonc pour recommencer 135 2 5 R cup ration du graphe de d monstration Si le th or me a t d montr une proc dure sp ciale filtre la base de faits pour ne conserver que les d ductions utiles la d monstration du th or me et r cup re les noms internes de tous les objets dont on aura besoin pour produire une r daction de la d monstration compr hensible par un l ve de lyc e ou de coll ge Le syst me sauvegarde aussi toutes les d ductions faites et les explicati
162. main de 56 cartes prises dans un jeu de 52 cartes et nombre incorrect c est dire ne correspondant pas l nonc du probl me main de 9 cartes alors que l nonc de l exercice parle de mains de 8 cartes 25 3 Machane Conshuctron Ensemble Exercice m Z Main de 0 cartes 1 As 7 Rois 2 Valats Avec un jeu de 52 cartes construite une main de 6 cartes comerant exactement 1 As 2 Rois et 2 Valais 7 Frames n 71 Charger E nencice Univers gt j L ersemble des parties 48 l ments prises dans Lindan de 57 Caries Charger Unes J Constuchon ouvelle Etay i tape 2 l ments tels que la hauteur est Ror 3 l ments tele que la hauteur n est pas dans Valet Roi As l ment tel que la hauteur est Ag 2 l ments tels que la hauteur asi valet Figure 2 Au niveau de la d finition des contraintes dans la solution il y a chaque tape d finition du nombre d l ments de la configuration sur lesquels porte la contrainte et la d finition du sous ensemble SE auquel ils doivent appartenir A chaque tape propos du nombre des l ments on retrouve les m mes sortes d erreurs que pour le nombre d l ments dans une configuration nombre impossible 14 c urs dans un jeu de 52 cartes et nombre incorrect 2 as alors que l nonc de l exercice parle de mains contenant exactement 1 as La d finition de SE se fait l aide de s lection sur les attributs hauteur
163. ment d un lien possible ajout d un lien certain cr ation d une nouvelle contrainte d termination de la valeur de AMI pour une correspondance etc Il traduit en programmes les r gles avec leurs modes d emploi ainsi d finis par les ordres Cela conduit plusieurs programmes pour la m me r gle Par exemple pour la r gle R2 nous pouvons d cider d envisager de l envisager quand on a une nouvelle contrainte R On cr e alors trois programmes l un pour quand on envisage de l envisager un pour quand on l envisage et qui d termine toutes les situations o on pourra l ex cuter et un pour quand on l ex cute effectivement Mais on peut aussi d cider de s y int resser quand la borne sup rieure d une des variables figurant dans l expression Y va tre chang e car cela va diminuer peut tre la valeur de SUP Y On va peut tre aussi vouloir envisager de l envisager puis de l envisager d o deux nouveaux programmes celui o on l ex cute tant le m me que pr c demment Mais on peut aussi vouloir la consid rer quand la borne inf rieure d une des variables apparaissant dans X est augment e car cela va augmenter la valeur de INF SSOMME X X2 Xi Xi 1 Xn Si nous envisageons de l envisager puis l envisageons cela fait encore deux nouveaux programmes soit au total sept programmes li s a cette unique r gle Naturellement ces programmes sont engendr s automatiquement On inclut dans
164. mettant une prise de d cision D une mani re similaire aux algorithmes bas s sur le min max les valuations des n uds feuilles de l arbre sont remont es travers chacun des arcs pour les arcs choix du syst me l op rateur max est appliqu pour les arcs v nements un calcul d esp rance est r alis 42 La valeur d un n ud quelconque est donc l esp rance de l valuation des situations pouvant r sulter de l ensemble des choix du syst me maximisant cette esp rance Le syst me est assur dans une situation S de pouvoir obtenir une esp rance du gain au moins gale l valuation de S et cette valuation est la plus grande 3 Le contr le de la recherche arborescente pour les jeux information incompl te n joueurs structure temporelle variable Nous proposons ici la r alisation d un syst me bas sur une recherche arborescente des possibilit s inspir du B de Berliner pour lequel la fonction d valuation est accompagn e d une m ta fonction d valuation Nous verrons en particulier comment cette m ta connaissance peut tre utile pour le contr le du d veloppement Contrairement l volution des algorithmes actuels pour lesquels l ensemble des connaissances sur les bons coups jouer r side dans la fonction d valuation nous accorderons une grande importance aux conseils donn s a priori les r actions des autres joueurs seront mod lis s comme des v nements ext rieurs prob
165. n Si la droite ab a comme nom dr1 on pourra remplacer dans la trace r dig e dr1 par la notation plus int ressante ab On fait de m me pour les longueurs les angles etc 138 4 2 Obtention de la preuve r dig e 4 2 1 Preuve compl te A partir du graphe le syst me construit automatiquement une preuve r dig e en fran ais respectant la chronologie des d ductions Voici la preuve obtenue en passant sous silence des faits semblant vidents sur la figure c est un choix de l utilisateur de ne pas demander leur explication car Argos a d lui les v rifier et un extrait du graphe avec la d finition des objets utilis s expliquant comment a t obtenu le cha non d explication en gras preuve fd orthog bc car fest le projet orthogonal de d sur la droite b c m f m b car mest le milieu de b d et le triangle f b d est rectangle en f Onaab cb car le triangle a b c est quilat ral par hypoth se On a angleGeom a b c 60 car le triangle a b c est quilat ral par hypoth se Les angles g om triques a b c et m b f sont oppos s par le sommet donc ils ont m me mesure Puisque m b m f et angleGeom m b f 60 alors le triangle m b f est quilat ral Puisque le triangle b m f est isoc le en b alors b m b f b est le milieu de c f car c b et f sont align s et b c b f a c m f est un rectangle car ses diagonales se coupent en leur milieu b donc c est un parall logramme et a m c f car a b b
166. n e minimisation de la longueur des pistes non prot g es des parasites maximisation de la longueur de la piste d quipotentiel 0 masse etc 56 La recherche d une solution complexe optimale est classiquement connue sous le terme de VCSP Valued Constraint Satisfaction Problem voir par exemple Schiex et al 97 Lobjois 99 en recherche op rationnelle Ce cadre ne permet malheureusement pas d utiliser une expertise du domaine pour guider la recherche Or la r solution des probl mes soumis au syst me MARECHAL n cessite une expertise de r solution car l espace de recherche est trop grand pour tre consid r dans sa globalit Ce cadre n est en outre pas adapt aux probl mes ayant peu de contrainte dure et des contraintes molles difficilement exprimables et calculables De m me les techniques de recherche locale de la recherche op rationnelle se sont r v l es inutilisables en pratique cause de la complexit de la g n ration des solutions et de leur valuation Ces techniques de recherche locale comme le recuit simul Van Laarhoven et al 88 la m thode tabou Glover 89 Glover 90 ou les algorithmes g n tiques Goldberg 89 consistent produire une ou plusieurs solutions simples puis am liorer celles ci par modifications successives Pour cela on d termine pour chaque solution courante l ensemble des solutions proches voisinage et on calcule une fonction de pr f rence pour s lectio
167. n g n ral de conna tre les cartes de la main de ses adversaires et par l m me l ensemble de leurs choix possibles Il serait possible d adapter les algorithmes de recherche arborescente en consid rant dans un premier temps toutes ou une grande partie des distributions possibles Le jeu engendr par chacune de ces distributions est alors un jeu information compl te qu il est possible de r soudre par les m thodes pr c dentes Le meilleur coup jouer est celui qui maximise l esp rance de la fonction d valuation sur l ensemble des distributions test es Outre le fait que nous risquons alors de devoir faire face une grande complexit en utilisant cette technique elle repose l encore sur des hypoth ses qu il est difficile de consid rer comme satisfaisantes on consid re en effet que chaque joueur y compris le syst me conna t toutes les cartes de tous les autres et qu il raisonne l encore l aide d un algorithme de type min max 2 2 Arbres de d cision Nous avons d ja mentionn que les arbres pr sent s en 2 1 permettaient de ne repr senter qu un ensemble de probl mes tr s restreint tr s pr cis ment les jeux 2 joueurs somme nulle information compl te sans hasard tour altern Les arbres de d cision dans l incertain permettent de combler cette lacune par l introduction de nouveaux types d arcs repr sentant des v nements incertains Ces v nements gt arcs sont probabilis s per
168. natoire C est normal puisqu il est m taguid de fa on bien plus stricte par les successions d ordres li s a chaque v nement La difficult est de les donner Il est admissible de les donner manuellement dans la phase de mise au point du syst me Mais la m thode n aura tout son int r t que quand ces s quences seront d termin es automatiquement par le syst me lui m me 6 D veloppements futurs Maintenant que le syst me fonctionne avec les m taconnaissances donn es manuellement et un monitoring statique et pr vu l avance il faut lever ces limitations Le syst me devra d abord tre capable de d terminer automatiquement les s quences d actions entreprendre apr s chaque v nement en tenant compte des r gles connues et de l nonc formel du probl me r soudre Il devra aussi pouvoir s affranchir de cet ordre s il lui para t maladroit il aura galement noter des surprises parmi ce qui s est pass de fa on les utiliser ult rieurement pour apprendre de meilleures s quences d actions 128 J ai d j fait quelques exp riences pour d couvrir comment construire des s quences d actions Elles sont bas es sur l examen des r gles En effet la d cision d utiliser une r gle d pend de l importance de ses cons quences des conditions qui permettent son d clenchement du co t de son ex cution et de ses chances de succ s Il est facile de d terminer de fa on gros
169. ncr mentalit est prise en compte en d composant le traitement des erreurs en diff rents sous traitements qui eux m mes sont ex cut s en plusieurs occurrences diff rents moments Ces sous traitements sont la d tection d une erreur qui est une proc dure interne au syst me silencieuse car elle n est pas visible par l l ve son signalement par exemple l affichage d un message pour l l ve il y a une erreur et son explication Dans notre EIAO nous voulons pouvoir choisir pour chaque erreur le moment o on la d tecte celui o on la signale et celui o on l explique Cela contraste avec d autres EIAO o le travail de l l ve n est valu que lorsqu il valide la solution finale de l exercice Pour les erreurs int ressantes il faut d cider quel moment elles sont d tect es Le fait de les d tecter n implique pas d en faire part l l ve c est un choix p dagogique que de d terminer le moment du signalement de cette erreur et donc si l l ve peut ou non continuer bien qu ayant commis une erreur Il faut ensuite d cider comment se manifeste le signalement on peut refuser de valider sa proposition soit en ayant un bouton qui reste gris soit en indiquant que la proposition n est pas valide ou bien on peut indiquer qu il y a une erreur sans autre explication et le laisser continuer s il le d sire pour qu il d couvre quelle est cette erreur Enfin il faut d cider quel mom
170. ndiquons ensuite des ensembles d instanciations possibles qui d crivent les liens entre ces l ments Cela permet de les d terminer les uns partir des autres Xe UNDESFILS R Y AUTREFILS R X UNDESFILS R a pour valeur l ensemble des termes qui d pendent de la connective principale de l expression R deux si la connective est binaire Si la connective est binaire AUTREFILS R X a pour valeur le terme de R qui n est pas X Nous avons aussi des conditions pour que l on ait le droit d appliquer la r gle ici COPRI R EQ COPRI R ayant pour valeur la connective principale de l expression R qui doit donc ici tre l galit Rappelons que dans MACISTE les objets constants ont leur nom pr c d du caract re dans le cas o ils pourraient tre pris pour une variable Une deuxi me condition est SUP X lt INF Y SUP X a pour valeur une borne sup rieure de l expression X et INF Y une borne inf rieure de l expression Y Il n est pas n cessaire que ce soient les meilleures bornes possibles tout d pend de la qualit des expertises qui vont les d terminer Plus elles sont pr cises et plus la r gle aura des chances de s appliquer S il y a beaucoup de variables une d termination tr s pr cise peut s av rer trop co teuse D terminer la m thode que l on utilisera pour valuer ces bornes est d ailleurs une d cision de monitoring Par exemple consid rons la contrainte F A
171. ne faut pas tout retenir savoir s lectionner ce que l on r examinera par la suite est une t che importante 116 L apprentissage n est qu une des phases de la r solution de probl mes dont il est indissociable C est au cours de la r solution que l on trouve la plupart des l ments qui permettront ensuite d am liorer les performances il est m me possible d apprendre pendant la r solution d un probl me de fa on pouvoir en utiliser les r sultats imm diatement La r flexivit doit intervenir au cours du monitoring En effet il ne faut pas que le syst me passe son temps examiner ce qu il faudrait mieux faire sans rien faire effectivement Le monitoring doit lui m me tre monitor afin de ne pas passer un temps excessif dans les activit s de monitoring Le m me m canisme de monitoring doit tre appliqu dans tous les cas y compris aux activit s d apprentissage et de monitoring Le syst me doit donc faire du m ta monitoring ou monitoring du monitoring Il doit en particulier Ne pas perdre du temps faire trop de monitoring dans une situation o cela ne sert rien de vouloir mieux choisir les essais faire par exemple quand il vaut mieux tout examiner le plus vite possible Evaluer le co t d un essai peut tre tr s co teux La connaissance de la valeur de ce m ta co t peut aider limiter le temps pass valuer les caract ristiques d un essai Il ne faut jamais que l
172. nique PASTRE LA MISE EN PLACE DU MONITORING DANS MALICE 2 ccccccccscccccsscccceceeee L LS Jacques PITRAT ARGOS UN DEMONSTRATEUR QUI RESOUT DES PROBLEMES DE GEOMETRIE EXPLIQUE CE QU IL FAIT ET AFFINE SES STRATEGIES DE RESOLUTION EN APPRENANT A PARTIR DES EXERCICES DEJA TROUVEG scccssssssssssseseseseseseees 132 Jean Pierre SPAGNOL Introduction L quipe M taconnaissances du LIP6 ainsi que des chercheurs d EDF se sont r unis du 13 au 15 septembre 2000 dans l le de Berder Nous avons r uni dans ce rapport le texte de quelques unes des interventions qui y ont t faites La r solution de probl mes est au c ur de PIA puisque presque toutes nos activit s nous demandent de r soudre un probl me Il est souvent n cessaire de d velopper une arborescence particuli rement dans les jeux La proc dure alpha b ta permet d en limiter beaucoup la taille tout en n liminant que des branches qui ne conduiront certainement pas la solution Tistan Cazenave fait le point sur les diff rentes am liorations qui ont t apport es cet algorithme Fabrice Kocik d veloppe une autre approche pour le cas o les informations dont on dispose sont impr cises ou inconnues en particulier dans le cas des jeux de cartes o l on ne conna t pas les cartes des adversaires Il faut savoir monitorer le d veloppement de l arborescence en ne consid rant pas les branches dont la probabilit est trop faible pour m r
173. nnant la longueur d un c t en fonction des angles d un triangle retrouv e avec quelque effort En voici quelques exemples o les oi d signent maintenant les angles du pentagone AA 2 sin AL Ve AoA2 4 sin 2 2 2 cos al 2 0A3 4 sin F s n s n a AoA3 4 sin 1 4 sin Al sin Al 02 On a aussi AoA3 4 sin ut 2 2 cos 04 En galant les deux expressions de AvA3 92 on a la relation qui manque D autres calculs faux de t te m ont conduit des expresssions de la forme gt ane a a3 etc J en conclus que je suis sur une mauvaise voie m me si th oriquement le calcul est possible je n aurai pas une expression simple que je pourrai calculer H faut absolument faire appara tre les sommes O1 02 1 02 03 etc Il y a confusion avec les ai de tout a l heure mais c est sans importance puisque ce sont les m mes x pr s et leur donner le m me nom aide plut t y voir clair En fait contraitrement ce que je pensais en reprenant par curiosit les calculs plus tard on peut faire appara tre 1 02 car ApA3 s crit aussi 3 2 cos 1 2 cos 2 2 cos a1 02 d o 1 cos O4 cos a1 cos O2 cos 1 02 2 1 Avec la m me relation entre a0 l et 03 on a cos 03 cos 1 cos Q1 02 03 04 cos 2 03 04 2 On n est pas encore au bout de nos peines Bl Concentr e sur les sommes des Qi en particulier sur 1 02 j ai enf
174. nner la meilleure transition a priori La philosophie des recherches locales est d utiliser une fonction de pr f rence simple et d effectuer beaucoup de cycles Dans le probl me qui nous int resse il est impossible de trouver une telle fonction et la g n ration d un voisinage serait en outre beaucoup trop longue De plus la d finition m me de proximit entre solutions pose un probl me deux solutions structurellement proches 2 X Cer 7 peuvent en effet conduire a des valeurs tr s diff rentes 2 2 Formalisation par un graphe d tat Dans les probl mes d optimisation solutions complexes la construction d une solution suppose d effectuer une s quence de d cisions Ces probl mes peuvent alors tre repr sent s par une recherche de chemin dans un graphe d tats La notion de graphe d tats permet de formaliser la plupart des probl mes d optimisation et de satisfaction de contraintes En Pour une pr sentation des techniques de recherche locale et une mise en parall le avec la r solution de probl mes en IA on pourra se reporter Grolimund 97 7 Par certain cot les approches que nous d crivons plus loin peuvent s apparenter au principe de recherche locale mais avec une philosophie inverse qui consiste obtenir directement la meilleure transition effectuer par un raisonnement long et complexe afin de minimiser le nombre de cycles Une pr sentation des graphes d tats appar
175. ns l arbre de recherche A chaque fois qu un coup est reconnu comme le meilleur dans une recherche sa note est ajust e d un montant proportionnel la profondeur du sous arbre explor On ajoute gProfondeurMaxP 4 Ja note du meilleur coup p tant la profondeur laquelle a t essay le coup On ordonne les coups tester dans l Alpha B ta en fonction de leur note J Schaeffer a montr que l heuristique de l historique associ e aux tables de transposition est responsable de 99 des r ductions de recherche dans l Alpha B ta Schaeffer 89 2 9 La recherche aspirante Plut t que d appeler l Alpha Beta avec des valeurs initiales de INFINI pour alpha et INFINI pour beta on peut lui permettre de couper plus de branches si on augmente resp diminue la valeur initiale de alpha resp beta Si la valeur finale trouv e est comprise entre les alpha et beta initiaux le r sultat sera tout de m me juste bien que l on ait coup plus de branches inutiles qu avec des valeurs infinies La recherche aspirante permet de r gler les valeurs initiales pour alpha et beta en prenant en compte les r sultats de la recherche pr c dente Au d but de chaque it ration les valeurs maximales resp minimales sont initialis es avec les valeurs remont es de l it ration 12 pr c dente additionn es resp diminu es de la valeur d un pion Si la recherche choue les valeurs ne sont pas comprises dans la f
176. ns nous effectuer cette redistribution R ponse en 4 minutes le jour des Jeux il me reste le brouillon suivant 5 maillots 1 4 possibilit s 4x3x2 24 2 3 3 2 1 perm 5 120 C est faux l ancien num ro du 2 peut tre gal celui qu on a donn au 1 Un raisonnement correct a t fait plus tard d abord directement avec des maillots initiaux abcde 1 joueur 4 possibilit s par exemple b 2 joueur ou bien a celui du 1 il reste c d e distribuer soit 2 possibilit s ou bien un autre parmi 3 par exemple c soit bc alors ane joueur ou bien a il reste d e distribuer une seule possibilit ou bien d ou e 2 possibilit s et le reste est impos Finalement on a 4x 2 3x 1 2 44 Comme je ne suis pas bien s re je fais un deuxi me raisonnement avec les compl mentaires Apr s quelques t tonnements soient a le nombre de possibilit s pour n maillots et c le compl mentaire on a a n c Ch n Ant Co an2 Cy ang tee Cyt ay 1 Rem a 0 Alors on retrouve avec a 0 ci 1 amp 1 a 1 c3 4 a3 2 c4 15 a4 9 cs 76 as 44 81 3 3 Le radar du Pentagone Jeux math matiques finales 2000 Le si ge de l tat major de l arm e des Etats Unis est un b timent en forme de pentagone r gulier dit le Pentagone Les services secrets viennent d y installer un rad
177. nsid rer que les coups simples pour une premi re recherche et s ils ne marchent pas envisager des coups moins standards Pour cela on d finit des ensembles de coups abstraits S1 S2 Cc Sn L largissement it ratif consiste faire une recherche avec approfondissement it ratif pour S1 Si elle choue recommencer avec S2 ainsi de suite jusqu Sn ou jusqu ce que le temps imparti soit coul Au niveaux ET de l arbre de preuve il est naturel de d finir les ensembles de coups abstraits partir des d finitions de jeux Les coups S1 aux n uds ET appel s AND1 seront donc les 17 coups ipl et ip2 alors que les coups de S2 appel s AND2 seront les coups ipl ip2 et ip3 Au n uds OU S1 OR1 sera l ensemble des libert s de la cha ne capturer et S2 OR2 tous les coups int ressants y compris les libert s L largissement des coups peut se faire dans diff rents ordres nous avons test ceux ci OR2 2AND2 2 C est l algorithme original sans largissement it ratif Les coups OR2 sont utilis s au n uds O et les coups AND2 aux n uds ET ORI 2AND2 2 L algorithme commence avec une recherche utilisant les ensembles OR1 et AND2 et si la recherche choue il en effectue une autre avec les ensembles OR2 et AND2 OR2 2AND1 2 L algorithme commence avec une recherche utilisant les ensembles OR2 et AND1 et si la recherche choue il en effectue une autre avec les ensembles OR2 et AND2
178. nt TantQue MeilleurFait Remplacement Sit c d f Se g Option RL Sf RL g Faire SuppChoix c d AjoutChoix Sc e SupprimeFait Annulation Sit 0 1 Sf annulation TantQue MeilleurFait Annulation Sit c d Se RL Se Faire SuppChoix c d Figure 9 Sch ma de r solution pour la recherche de solutions compatibles Voir Pann rec 00 pour la description des formes de connaissance utilis es par le syst me MARECHAL 66 Au cours de la seconde phase le syst me se sert des informations produites par la phase d analyse pour effectuer les m ta choix Il commence par remplacer au maximum les choix en conflit D s qu il choisit un remplacement il supprime le choix en conflit ajoute le choix de substitution et supprime les possibilit s d annulation concernant la ressource en conflit En effet si le choix est remplac le conflit est r solu et une annulation n est plus n cessaire Dans la premi re boucle TantQue RL f et RL g indique que les ressources en conflits sont galement des ressources locales au niveau de la boucle Ainsi si un remplacement concernant la ressource f est effectu en utilisant un choix concernant la ressource g les autres possibilit s de remplacement pour f et g sont supprim es Un choix ne doit pas en effet tre remplac plusieurs fois et un choix ne peut remplacer plusieurs choix simultan ment A chaque fois que le syst me cherche
179. nt possible les coupes Lorsque la fonction d valuation est donn e par deux bornes ces coupes pourront tre obtenues en r duisant l impr cision sur cette fonction de telle sorte que la borne inf rieure de la fonction d valuation de la situation engendr e par un des choix principaux devienne plus grande que toutes les bornes sup rieures des choix alternatifs C est pourquoi Le premier objectif est la r duction de l impr cision sur la fonction d valuation des situations engendr s par chacun des choix principaux Le second objectif est la r duction de cette impr cision en priorit sur les choix les plus prometteurs Nous d finissons donc La probabilit d un noeud n la probabilit de la situation correspondant n sachant que le syst me a voulu y parvenir Si Pere n N NoeudChoix n Probabilite N p Alors Probabilite n p Si Pere n N NoeudEvenement n Probabilite N p1 ArcEntrant n a Probabilite a p2 Calcul p3 p1 p2 Alors Probabilite n p3 L impr cision d un n ud la diff rence entre la valeur optimiste et la valeur pessimiste de la fonction d valuation associ e ce n ud L int r t a priori d un n ud n la somme des int r t des choix permettant d aboutir n pon d r par 9 Profondeur du choix la profondeur d un choix C correspondant au nombre de choix ayant t fait sans l arbre avant C Cette pond ration permet de donner
180. nte dans les jeux Nous rappelons bri vement le principe des algorithmes de recherche arborescente classique utilis s dans les jeux savoir le min max et l alpha beta Nous exposons aussi rapidement les am liorations moins connues propos es par Berliner dans son B Cazenave 00 fait un tour plus complet des algorithmes de ce type 2 1 1 Le min max Le min max est l algorithme de base des recherches arborescentes dans les jeux 2 joueurs somme nulle information compl te Il consiste en une exploration exhaustive jusqu une certaine profondeur des situations pouvant tre engendr es partir de la situation actuelle La recherche peut tre repr sent e par un arbre dont les n uds correspondent chacune de ces situations les arcs de niveau impair aux choix possibles coups l gaux du syst me et les arcs 39 de niveau pair aux coups l gaux de l adversaire Les n uds feuilles sont valu s par le syst me l aide d une fonction d valuation Les valeurs sont ensuite remont es en appliquant l op rateur min pour une propagation sur des arcs correspondant aux choix de l adversaire et l op rateur max pour les choix du syst me Le min max est bas sur l hypoth se que le joueur adverse utilise un raisonnement du m me type que lui savoir un min max de m me fonction d valuation une profondeur n 1 o n est la profondeur du min max initial La complexit du min max est de l ordre de Kn o K repr sent
181. nteraction qui ont permis la g n ration de cette r ponse boutons menus etc Ceux ci apparaissent et disparaissent dynamiquement en fonction de l tat d avancement de la r ponse 3 Les erreurs dans la machine ConstructionEnsemble Dans toute machine la premi re chose que fait l l ve est de choisir l exercice r soudre Celui ci fait partie de la classe de probl mes associ e la machine Il y a ensuite deux grandes phases dans le travail de construction la d finition de l univers et ensuite les diff rentes tapes qui correspondent aux contraintes de s lection La figure 2 montre un tat de la machine o l exercice a t choisi et valid l univers aussi ainsi que certaines tapes de la construction Mais la construction elle m me n a pas encore t valid e Nous avons dress un inventaire des erreurs possibles dans ces deux phases pour les cat goriser et d cider de leur traitement Dans la suite de cet article nous donnons les cat gories d erreurs pour la machine ConstructionEnsemble en les illustrant sur l exercice de la figure 2 Dans la d finition de l univers il faut pr ciser le r f rentiel et le nombre d l ments de chaque l ment de l univers c est dire de chaque configuration Les erreurs possibles portent donc sur un mauvais choix du r f rentiel ou une erreur dans le nombre d l ments de la configuration Cette derni re erreur peut tre de deux sortes nombre impossible
182. ntroduit par Argos 2 aire i c a c a iv ic ah puisque ce sont deux fa ons de calculer l aire du triangle partir des deux hauteurs i v et ah ic ah ac ivdoncic ac iv ah aire a i b 1 2 ib ah car h est le projet orthogonal de a sur la droite i b formule de l aire d un triangle i est un point de la bissectrice int rieure de l angle g om trique b a c donc il est quidistant des deux droites ba et ca donciu iv aire i a b 1 2 a b i u car u est le projet orthogonal de i sur la droite a b formule de l aire d un triangle Puisqueab iv 2 aire iab ib ah alorsab iv ib ah ab iv ib ahdoncab ib ah iv Puisqueab ib ah iv ac ic alorsab ib ac ic Ona ab ib ac ic doncib ic ab ac Annexe4 Exemple de r gles construites 4 partir d une m me propri t propriete general obligatoire centreGravite centreGravite A B C G et milieu B C 1 gt G app droite A I G est le centre de gravit du triangle A B C donc il appartient la m diane issue de A cad la droite A I 1 Condition suffisante regle A app_CS7 B eltConclSym A C app D on veut montrer une appartenance milieu A E F G H G est le milieu de EF centreGravite A I E F C J C est le centre de gravit de IEF droite A D I G K D est la droite IG not hyp A C app D L Argos ne sait pas que C appartient IG retractl eltConclSym A C app D
183. on ou alors dupliquer 95 14 r PSE 12 a Ou alors consid rer un carr de c t b et le compl ter Le rectangle bxb est trop grand je le coupe en deux b 1 b 2 Je consid re le cas ou b est impair ce que je sais et je prends b un rectangle de c t bA Je pourrai ainsi en compl tant le carr de b PEL obtenir bt b 302 by 1 qui est trop 2 4 2 4 b 1 petit Je m int resse au rectangle juste un peu plus grand de c t s b b l etb L L Sa surface est bf b 2 1 2 2 2 4 reste Shay b gt placer pour occuper au moins b b l Adui 3b2 b 5 gt 24 b T On en d duit que 4 b 42 b a soit b gt 2 b 3 lt 0 On trouve alors que b ne peut tre que 1 ou 3 Seul 3 convient Si on se savait pas que b est impair on peut faire un raisonnement analogue pour b pair avec b au lieu de bot et on trouve que ne peut tre que 0 6 Raisonnement formel Finalement ce que j ai fait c est simplement comparer w b ly et c b b b b 1 b On savait d j que Be c En levant au carr on obtient D2_b_3 lt Q qui ria lt 0 qui est la 3 4 m me in quation que pr c demment On peut m me faire encore plus court 96 ae B lt o bt b b b 1 lt la derni re in galit est stricte sauf si b 0 bat 22 b 2 b 3 0 c est dire b 3 Sinon b 0 et c 1 solution trivale non retenue On en d duit que si b 0 c ne peut tre gal qu b
184. on complexe Nous avons alors d crit et compar sur le plan th orique deux m thodes permettant de r pondre ce probl me de combinaison La conclusion de cette comparaison est que la m thode consistant combiner les solutions au cours de leur construction est globalement la meilleure tant au niveau de la rapidit que de la qualit des solutions obtenues Celle ci est donc en cours d impl mentation dans le syst me MARECHAL pour remplacer la pr c dente Les objectifs court terme sont d obtenir des r sultats exp rimentaux qui valideront la comparaison th orique r alis e Naturellement le point important de cette m thode r side dans le m canisme de contr le et dans les heuristiques qui s y trouvent Ce m canisme n est pas encore optimal et les perspectives long terme consistent donc le compl ter et l am liorer 6 Bibliographie De Kleer 86 De Kleer J An Assumbtion based TMS Artificial Intelligence 28 p 127 162 1986 Glover 89 Glover F Tabu search Part 1 ORSA journal on computing vol 1 3 p190 206 1989 Glover 90 Glover F Tabu search Part 2 ORSA journal on computing vol 2 1 p4 32 1990 Goldberg 89 Goldberg D Genetic algorithms in search optimisation and machine 75 learning Addison Wesley 1989 Grolimund 97 Grolimund S Apprentissage de connaissances de contr le pour l optimisation combinatoire int gration du raisonnement partir de cas dans la m
185. onne une restriction tr s s v re sur les valeurs de V qui est inf rieur ou gal 1 alors que V lt 13 est bien moins contraignant 2 L ordre indiquant que l on peut envisager d envisager une r gle ENVENV R A P E PP EE Le travail se fait maintenant en deux tapes et chacune a sa propre priorit on regarde d abord s il y a lieu d envisager de faire l essai ce qui d termine une premi re priorit P celle d envisager l essai Quand on fait plus tard cet essai effectivement on d terminera une 124 nouvelle priorit PP qui sera celle d ex cuter r ellement la r gle Le but est de ne pas passer beaucoup de temps imm diatement pour consid rer l int r t de faire un essai plus tard s il y a de grandes chances que cet essai n ait qu un int r t moyen alors que l examen pr cis de chacun des essais qu il entra ne est co teux C est en particulier ce qui se passe avec la r gle R2 pr c dente qu il vaut mieux d finir avec ENVENV En effet envisager d appliquer une r gle est souvent une op ration assez co teuse en elle m me car on peut tre amen chercher la valeur de certains arguments Par exemple si l on veut savoir si l on va valuer une contrainte modulo un certain nombre il faut d terminer quels nombres on va consid rer il peut y en avoir plusieurs qu il faudra trouver et en plus pour chacun on devra calculer la priorit de l essai De m me dans l exemple d
186. ons correspondantes en vue d une analyse de la r solution et une utilisation ventuelle en mode conjecture l ve 2 6 Production automatique de la r daction en fran ais de la d monstration A partir du graphe de la d monstration ARGOS va construire une preuve r dig e en fran ais adapt e l utilisateur La proc dure de construction de l explication va parcourir l arbre de preuve en profondeur et va descendre jusqu aux hypoth ses initiales Chaque n ud ayant une explication rentrant dans le cadre des d sirs de l utilisateur sera expliqu une fois et simplement rappel e si elle sert dans une autre branche de preuve Chaque n ud de l arbre est d velopp ou non gr ce au mod le explicatif fourni par l expert et instanci avec les bonnes variables en fonction du type de preuve d taill e ou non et du niveau scolaire pr cis s par l utilisateur Le syst me peut y adjoindre si cela a t pr vu par l expert ayant donn les connaissances un commentaire explicitant dans un langage proche de l l ve et de son niveau d tude pourquoi cette conjonction d hypoth ses a permis cette d duction 3 Illustration par un exemple d taill L exemple suivant est issu de Pintado 94 3 1 Enonc Enonc livresque Soit abc un triangle quilat ral m et d deux points tels que b soit le milieu du segment am et m le milieu du segment bd Soit f le projet orthogonal de d sur la droite bc Montrer que
187. onstrateur qui R sout des Probl mes de G om trie Explique ce qu il Fait et Affine ses Strat gies de R solution en Apprenant partir des Exercices d j Trouv s Jean Pierre Spagnol Crip5 Universit Paris5 rue des saints p res http www math info univ paris5 fr spaj math info univ paris5 fr R sum L objectif de cette recherche est la conception d un syst me base de connaissances capable de r soudre de fa on automatique des exercices de g om trie niveau coll ge ou lyc e Le syst me est ensuite capable de filtrer la base des faits d duits pour en produire partir du graphe de la d monstration une solution r dig e en fran ais adapt e au niveau de la classe consid r e Apr s chaque exercice r solu ARGOS met jour un certain nombre de strat gies en analysant la d monstration qu il a produite Dans cet article nous d crivons un certain nombre des techniques mises en uvre construction automatique de r gles op rationnalisant les connaissances donn es de fa on d clarative apprentissage de strat gies de r solution possibilit d appels de conjectures en cours de d monstration r daction de preuve en fran ais Con u partir du syst me Muscadet Argos essaye d en garder l esprit qui est bas sur le principe de la d duction naturelle Ce syst me est destin une utilisation en EIAO Mots cl s DAT apprentissage automatisation du raisonnement math matique EIAO
188. onstruire une solution sur la base des informations recueillies lors des tests des hypoth ses Il y a donc ici deux phases totalement distinctes cf Figure 6 la phase d valuation qui tudie les hypoth ses ind pendamment les unes des autres et g n re une trace de son ex cution et la phase de d cision a posteriori qui permet de construire la solution d apr s les r sultats obtenus Par rapport un raisonnement hypoth tique classique il s agit donc de rajouter une nouvelle tape entre l valuation et la s lection finale Les phases d valuation et de s lection tant classiques nous ne d taillerons dans la suite de cette partie que la phase de combinaison 62 Q Phase de 7 K Phase de raisonnement gt o O combinaison hypoth tique r a construction valuation o o o o Trace du raisonnement Jo fiza 00 Solution Ensembles de finale solution Figure 6 Principe de l approche a posteriori 3 2 Phase de combinaison Cette phase consiste tudier les combinaisons possibles d hypoth ses puis choisir la solution finale parmi les meilleures combinaisons et les meilleures feuilles de l arbre des hypoth ses Naturellement toutes les combinaisons ne peuvent tre tudi es en g n ral Le syst me s lectionne celles qui lui paraissent les plus int ressantes a priori il teste les combinaisons des meilleures hypoth ses en priorit Mais pour une combinaison donn e i e
189. ors pour chaque case les cases accessibles par un d placement de Cavalier Si le graphe n est pas d fini explicitement tous les liens entre les l ments des deux ensembles sont possibles Un des buts de la r solution est de trouver des liens certains parmi les liens possibles entre les l ments des ensembles de d part et d arriv e Cela se fait souvent en montrant que des liens possibles doivent tre limin s parce qu ils ne peuvent certainement pas tre certains Nous pouvons aussi indiquer l existence de cliques de disjonction entre les l ments de l ensemble de d part Cela signifie que si un l ment d une clique a un lien certain avec l l ment A de l ensemble d arriv e les autres l ments de cette clique ne pourront tre associ s cet l ment A Bien entendu il est inutile d utiliser une clique quand AMA vaut 1 car tous les l ments de l ensemble de d part sont automatiquement dans la m me clique Ce langage est tr s proche de celui de ALICE dont certaines possibilit s comme la recherche d une solution optimale n ont toutefois pas encore t impl ment es A titre d exemple donnons l nonc qui d crit une formulation g n rale possible des probl mes de cryptaddition Cette forme utilise des retenues mais il est parfaitement possible de d finir dans le m me formalisme bien d autres formulations du m me probl me SOIT ENSEMBLE LIGNES 1 NL SOIT ENSEMBLE COLO
190. oue Ko Le hachage de la position est le XOR de tous les nombres pr sent sur la position Au Echecs on a 12 nombres al atoires par case un par pi ce diff rente 4 nombres pour les droits de roques 8 nombres pour les captures en passant 1 pour la couleur qui joue Soit 64 12 4 8 1 781 nombres al atoires Il y a deux avantage a utiliser le XOR pour coder une position Le XOR est une op ration tr s rapide sur les bits La valeur de hachage d une position peut tre calcul e incr mentalement 3 La Recherche Abstraite de Preuves La recherche abstraite de preuve est un algorithme qui d montre efficacement des th or mes dans les jeux Il permet des gains de temps appr ciables sur l Alpha B ta avec toutes ses optimisations de plus il renvoie toujours des r sultats exacts ce que ne garantit pas l Alpha 13 B ta dans le cas des jeux o les coups sont s lectionn s chaque n ud La recherche de preuve abstraite permet de s lectionner les coups avec confiance 3 1 Les Ensembles de Coups Abstraits Les coups qui permettent de changer l issue d une recherche peuvent tre facilement trouv s lorsque le but est presque atteint Toutefois lorsque le but n est plus un ou deux coups cela devient plus difficile Nous traiterons dans cette section de la s lection de l ensemble complet des coups possibles utiles examiner lorsque le but ne peut pas tre directement atteint Par exemple si une cha ne de pier
191. our 5 cartes alors que dans l exercice on demande des mains de 8 cartes Il peut y avoir d autre part des erreurs sur la d finition des diff rents SE La m thode constructive implique pour cette machine que les SE soient disjoints L erreur consiste avoir des SE non disjoints le SE d fini par hauteur est as et celui d fini par couleur est rouge M me pour un exercice aussi simple on constate qu il existe un grand nombre d erreurs possibles mais aussi qu il appara t une cat gorisation vis e p dagogique possible En r sum nous avons distingu trois cat gories d erreurs Des erreurs purement internes qui sont d tectables sans prendre en compte une solution de l exercice et ne font pas intervenir la m thode constructive Nous avons utilis pour elles les termes impossible ou incoh rent Nous pouvons les consid rer comme des erreurs d inattention Des erreurs qui font intervenir la m thode constructive et qui sont internes C est l utilisation de SE non disjoints pour la machine ConstructionEnsemble Ces erreurs sont d licates expliquer car elles correspondent des conditions uniquement impos es par la m thode et dont l l ve ne pourra voir la raison d tre que plus tard au moment de compter Pour lui elles peuvent pr senter un caract re arbitraire Des erreurs dites externes elles proviennent de la comparaison des solutions correctes et de la solution propos e par l l ve ne comportant p
192. our d montrer il l indique dans la r daction de la preuve comme une sorte de question interm diaire un lemme qu il a d montrer avant de s attaquer l exercice proprement dit voir Annexes 149 7 2 Probl mes Un appel de conjecture est une d marche typiquement heuristique Cet appel doit tre fait au bon moment Trop t t et c est l chec trop tard a ne sert plus rien Il ne faut pas que le d monstrateur s gare Il appara t utile de supprimer les r gles de cr ation d objet lors d un appel de conjectures et de n accepter que des r gles de cr ation cibl es en fonction de la conclusion Un math maticien ne fait pas un appel de conjecture par hasard D s le codage de la figure il en met Il fonctionne par exemple par analogie Il a d j rencontr une situation similaire et il essaye de voir si sur le probl me du moment cela va fonctionner de la m me fa on C est en fonction de son exp rience qu il fera tel ou tel choix Comment acqu rir la certitude de celui qui voit sur la figure et qui il ne manque que le cheminement d ductif 7 3 Exemple de r gle appelant une conjecture Exemple en fran ais Si on veut montrer que ABCD est un parall logramme rectangle carr ou losange si le milieu d une des diagonales existe d j et qu un appel de conjecture pour montrer que c est le milieu de l autre n a pas d j t lanc alors essayer de montrer que c est au
193. ousParties ConstructionSousPartie Cardinal unEntier Filtre unFiltre Propri t s 0 1 ou 2 Propri t s IdentificateurAttribut Appartenance Comparateur estVrai Domaine ValeurCible IdentificateurPredicat Figure 4 30 Essayons de voir comment partir de la d claration ci dessus on peut faire des choix y p dagogiques et ergonomiques qui conduisent l interface finale Le premier choix concerne les l ments valider 5 2 Choisir les l ments validables Nous appelons l ment validable une partie de la structure arborescente dont l dition se manifeste l cran dans une zone identifiable comportant un bouton valider s appliquant toute la zone A l int rieur de la zone en cours de saisie toutes les informations sont modifiables et annulables volont Mais lorsque l l ve clique sur le bouton valider il signifie par l qu il assume tous les choix qu il a faits dans la zone et celle ci est alors fig e avec les informations saisies il appara t cependant ventuellement un bouton annuler qui permettra de revenir sur la saisie plus tard Le choix des l ments validables rel ve de la p dagogie choisie en fonction du domaine et de la m thode de r solution que l on veut faire utiliser A partir du travail sur nos interfaces nous avons relev quelques crit res de choix L l ment valider correspond un concept qu on veut rendre visible
194. partir d une de ces relations Exemple La r gle construite partir de la propri t ci dessous traduisant la relation de Pythagore rajoutera si elle s applique une relation num rique propriete general obligatoire pythagore si le triangle ABC est rectangle en A alors BC AC AB On a BC AC AB car le triangle ABC est rectangle en A La r gle issue de ci dessous exprim e ici un niveau de g n ralit sup rieur car on ne pr cise pas la nature des objets qui sont tout de m me des grandeurs mesurables calcule alors L1 car L et L2 ont une valeur exacte connue propriete general obligatoire valeurExacte si L L2 LI et L mesure Le et L2 mesure Le et le r sultat du calcul rac Le Le2 est Res alors L1 mesure Res L1 Res car L L2 L1 et L Le et L2 Le2 et donc L1 rac Le Le2 Puisque la relation L L2 L1 figure en hypoth se et que deux grandeurs sont instanci es alors la r gle app le une proc dure de calcul qui va renvoyer dans la variable Res la valeur exacte du calcul rac Le Le2 L explication d un tel pas de raisonnement va n cessiter de la part d ARGOS une recherche des noms internes des objets longueurs pour permettre la construction d une phrase pouvant tre par exemple celle ci d pendant des choix explicatifs 146 de l expert ab 2 rac 3 car bc 2 ab 2 ac 2 et be 3 rac 2 et ac rac 6 et donc ab rac 3 rac 2 2 rac 6 2
195. peuvent alors tre faux En pratique d apr s les r sultats exp rimentaux cela n a toutefois pas l air de diminuer ses performances 16 Algorithm Book Totaltime nodes Preventip3 1s 10000N ggv 13 34 69582 98 25 NM Preventip3 1s 10000N ggv2 66455 518398 77 08 NM Preventip3 1s 10000N ggv3 301 50 230724 65 28 NM ip3 1s 10000N NM gevl 10 58 9401 99 12 ip3 1s 10000N NM ggv2 31 57 39220 88 89 ip3 1s 10000N NM gev3 16 93 20902 73 61 Table 6 Results with null move forward pruning 3 3 Conclusion sur la recherche abstraite de preuve La recherche abstraite de preuve a deux grands avantages sur l Alpha B ta classique ses r sultats sont fiables et il sont calcul s plus rapidement Avec les m mes contraintes de temps elle r sout plus de probl mes et l algorithme r agit mieux que l Alpha B ta l augmentation des capacit s CPU Cet algorithme marche pour un grand nombre de jeux Les seuls inconv nients tant de d finir une m thode pour trouver les ensembles de coups abstraits associ s chacun des jeux 4 L Elargissement It ratif 4 1 L algorithme La recherche s lective consiste ne regarder qu une partie des coups possibles Un probl me des algorithmes de type Alpha B ta est l ordonnancement des coups on veut essayer en priorit les coups qui simplifient la situation et qui marchent souvent L largissement it ratif consiste ne co
196. plex Hypothesis handling 55 d crit plus en d tail dans Pann rec 00 Dans ce probl me chaque pi ce dont le nombre varie de 30 120 donne lieu une d cision et il y a autant de possibilit s pour chacune qu il y a de mouvements envisageables par pi ce en moyenne de l ordre de 10 L objectif peut tre de d truire l adversaire occuper une position du terrain ou minimiser le nombre de pi ce perdue La difficult principale r side dans la taille de l espace de recherche et dans la complexit des r gles de transition entre les tats successifs du jeu ce qui rend tr s difficile une valuation pr cise des solutions ie Gane es eid Special Don Help Figure 2 Saisie d cran du jeu de r flexion servant d application au syst me MARECHAL Un autre exemple de probleme d optimisation a solutions complexes est le placement de composants lectroniques sur un circuit imprim en fonction du sch ma de raccordement Dans cette application le syst me doit faire un choix par composant avec une infinit de possibilit s pour chaque choix car les composants peuvent tre plac s n importe o sur un espace continu L objectif est d obtenir une configuration viable pas d intersection entre des pistes d quipotentiels diff rentes qui optimise de nombreux crit res minimisation du nombre de straps entre les couches minimisation de la place si la dimension de la plaque n a pas t don
197. ponse la question no 5 Le fait h f c est un triangle rectangle en h a t d duit d apr s la question 4 Les droites h f et hc sont perpendiculaires car le triangle h f c est rectangle en h Le fait les droites b c et ab sont perpendiculaires a t d duit d apr s la question 3 Les droites f h et a b sont parall les car b c est perpendiculaire a b et f h est perpendiculaire bc les droites a b et fh sont parall les par sym trie r ponse la question no 6 Ona ao fo comme ayant la m me valeur exacte 3 Onabf 2 0f 2 bo2 car le triangle o b f est rectangle en o Comme bf bf bo bo ao ao alorsbf rac 3 3 6 6 3 rac 5 Le fait a b 3 rac 5 a t d duit d apr s la question 1 Ona ab bf comme ayant la m me valeur exacte 3 rac 5 b f ba donc le triangle b fa est isoc le en b b a f est un triangle isoc le en b par sym trie r ponse la question no 7 Ona ao fo comme ayant la m me valeur exacte 3 Onabf 2 o0f 2 bo0 2car le triangle o b f est rectangle en o Commebf bf bo bo ao ao alorsbf rac 3 3 6 6 3 rac 5 Le fait a b 3 rac 5 a t d duit d apr s la question 1 Ona ab bf comme ayant la m me valeur exacte 3 rac 5 Le fait les droites fh et ab sont parall les a t d duit d apr s la question 5 Puisque ga bf et gf b a alors on en d duit que gab fest un parall logramme c t s oppos s parall les deu
198. pour l it ration finale une fois pour l avant derni re it ration Le nombre de n uds engendr est donc de n 2n 3n 4n dn Ce qui est en O n Sin est assez grand le premier terme est nettement plus grand que les autres c est donc la derni re it ration qui prend la plus grande partie du temps Par rapport la recherche en largeur d abord l approfondissement it ratif engendre n n 1 fois plus de n uds Si on consid re l asymptote l approfondissement it ratif est un algorithme de recherche optimal aussi bien en temps qu en espace Les algorithmes de recherche en profondeur d abord ont un autre avantage important sur les algorithmes en meilleur d abord ou en largeur d abord il permettent d utiliser moindre co t des informations incr mentales sur la position L ordre de recherche des positions permet de conna tre les informations sur la position avant le coup qui a men cette position On peut utiliser ces informations pour recalculer plus rapidement les propri t s d une position en ne calculant que la diff rence avec la position pr c dente induite par le coup 2 7 Les tables de r futation Une heuristique qui fonctionne bien avec l approfondissement it ratif est de retenir chaque it ration la suite de coups optimaux calcul s par l Alpha B ta en r ponse chaque coup la racine Chaque coup la racine est donc associ une s quence de coups qui
199. premi re estimation indique la priorit d envisager de faire l essai ou de l liminer totalement Quand on en vient plus tard cette priorit on cr e un ou plusieurs essais bien d finis qui ont chacun leur propre priorit On ex cutera chacun d entre en fonction de cette derni re priorit Avoir un premier filtre vite de perdre du temps d terminer imm diatement les arguments et l int r t de multiples essais qui de toutes les fa ons ne sont certainement pas tr s int ressants 3 L ordre de test Cet ordre est un ensemble de conditions qui indiquent d ex cuter une certaine s quence d actions si toutes les conditions sont vraies Ces conditions utilisent la variable dont la valeur est le foyer Quand on a ex cut toutes les actions de cette sous s quence on revient la s quence principale Par exemple quand on a une nouvelle contrainte on regarde si elle ne comporte qu une variable Si cela est le cas on ex cute une r gle qui regarde pour toutes les valeurs possibles de cette variable si elles rendent la contrainte vraie ou fausse en les substituant successivement Si pour une des valeurs possibles la contrainte est fausse on limine cette valeur comme possible C est ainsi que si la contrainte est F A lt 4 on liminera les liens possibles entre le n ud correspondant A et les n uds d arriv e correspondants 0 1 2 et 3 Ceci n est bien videmment utile que s il n y
200. puis d tudier les combinaisons permet de diminuer la complexit du probl me le probl me initial m choix se d compose en n sous probl mes de m choix chacun pour tout i lt n m lt m La phase de raisonnement proprement dite tests des hypoth ses s en trouve donc largement r duite Le probl me est de savoir si le sur co t introduit par l adjonction d une phase de combinaison est 13 2 f oy g Voir Pann rec 00 pour les m canismes de retour arri re sur les choix concrets 67 inf rieur au gain sur la phase de raisonnement proprement dite Ce sur co t d pend en fait du degr d ind pendance entre les hypoth ses Lorsque les hypoth ses sont ind pendantes les unes des autres cas d offensives deux endroits loign s de la carte ne faisant pas intervenir les m mes pi ces le sur co t est quasi nul Il n y a alors pas de conflit entre les solutions partielles et leur combinaison est donc triviale Dans ce cas l approche a posteriori est donc tr s int ressante en terme de rapidit de calcul Par contre lorsque les hypoth ses sont fortement d pendantes cas d offensives proches et faisant donc intervenir les m mes pi ces nous avons vu que la r solution de la combinaison des solutions partielles tait un m ta probl me au moins aussi difficile que le probl me de base En pratique les hypoth ses sont rarement ind pendantes et le sur co t induit par la phase de combinaison est
201. que Le choix actuel pour donner les connaissances au syst me est le suivant L utilisateur va structurer les connaissances comme il l entend et indiquer la fa on dont lui m me expliquerait les d ductions correspondantes obtenues par application de chaque propri t exprim e 5 1 Connaissances du domaine et leur explicitation Les connaissances fournies au syst me sont de deux ordres les propri t s math matiques classiques exprim es diff rents niveaux de g n ralit des heuristiques de cr ations d objets conditionn es ou non par le but Voici un exemple de propri t Si G est le centre de gravit du triangle ABC alors il est situ sur chaque m diane exprim e dans la syntaxe d ARGOS par centreGravite A B C G et milieu B C I gt G app droite A I Voici un exemple d heuristique de cr ation Si ABCD et EBFD sont deux parall logrammes distincts alors cr er le milieu de leur diagonale commune traduite par le pr dicat heuristique plgAyantDiagCommune plg A B C D et plg E B F D et distincts A E gt creer milieu B D _ F Les connaissances sont donn es avec leur mod le explicatif sous forme de pr dicats dont voici quelques exemples Exemplel propriete general obligatoire centreGravite si G est le centre de gravit du triangle ABC et I mil B C alors G AD 143 G est le centre de gravit du triangle ABC donc il appartient la
202. qui d veloppent d autres formes d arbres comme les d monstrateurs de th or mes les r solveurs de probl mes ou les syst mes de satisfaction de contraintes L algorithme Minimax et ses am liorations est utilis dans la plupart des jeux deux joueurs somme nulle et information compl te Cet algorithme a t propos il y a plus de cinquante ans par von Neumann et Morgenstern Neumann et Morgenstern 1944 pour trouver un coup aux Echecs Alan Turing Turing 1953 a propos des strat gies de recherche bas es sur le principe du Minimax et une am lioration importante fut l alpha Beta Une forme affaiblie d Alpha B ta est apparue dans les premiers programmes d Echecs comme NSS de Newell Shaw et Simon Newell et al 1958 On se place maintenant dans le cadre des jeux a deux joueurs L algorithme MiniMax ses variantes et am liorations sont utilis s dans la majorit des programmes de jeux deux joueurs somme nulle et information compl te 2 Am liorations usuelles du Minimax On rappelle qu une fonction d valuation prend en entr e une position dans un jeu et donne en sortie une valuation num rique pour cette position L valuation est d autant plus lev e que la position est meilleure Si une fonction d valuation est parfaite il est inutile d essayer de pr voir plusieurs coups l avance Toutefois pour les jeux un peu complexes comme les Echecs on ne conna t pas de fonction d valuation pa
203. r solveur g n ral de probl mes d optimisation solutions complexes Dans cette partie nous verrons quoi correspond ce type de probl me et pourquoi ils n cessitent l utilisation de raisonnement hypoth tique et de combinaison d hypoth ses 2 1 Les probl mes d optimisation solutions complexes Par probl me solutions complexes nous entendons tout probl me de coordination de choix pour atteindre un objectif donn Cela signifie que le syst me doit construire une solution compos e d un ensemble de choix interd pendants Nous utiliserons indistinctement les termes de choix et de d cision pour repr senter la s lection d une possibilit parmi l ensemble des possibilit s initiales d un choix donn Plus formellement soit E1 E n ensembles de la forme E e i 1 Cini E1 En repr sentent les d cisions prendre et ei 1 Cini les possibilit s pour la d cision i Une solution potentielle sera un n uplet e1j1 enjn La solution finale doit tre optimale au sens o elle permet de maximiser un crit re ou d atteindre le plus s rement ssible l objectif fix De nombreux exemples de tels probl mes existent Pour d velopper le syst me MARECHAL nous nous appuyons sur un jeu de strat gie qui consiste programmer le d placement de pi ces diverses sur un terrain quadrill La Figure 2 montre une saisie d cran de ce jeu qui est 5 Monitoring based Autonomous Reasoning Engine for Com
204. r cet As Il faudra donc jouer I As au ler pli ouvert ou tenter de prendre la main avec l As le plus t t possible en coupant dans une autre couleur afin d ouvrir tout de suite avec l As Ou jouer le plus tard possible l Ase en esp rant que les atouts des autres joueurs soient tomb s au moment ultime Strat gie tr s risqu e et peu ma tris e du fait de l impossibilit de prendre la main avec une autre carte que l As et donc de faire tomber volontairement les atouts 4 4 Simulation de raisonnement avec SYMOR Nous donnons la Figure 1 le type d arborescences que le syst me SYMOR serait susceptible de donner La fonction d valuation est une estimation de la probabilit que le joueur simul r ussisse son contrat lorsque celui ci est assur de le r aliser la situation est valu e 1 lorsqu il est assur de le chuter elle est valu e 0 Les valeurs interm diaires correspondent une mesure du hasard Les bornes inf rieures et sup rieures de ces probabilit s mesures de n cessit et de plausibilit donnent une information sur le manque de pr cision sur cette mesure du hasard 51 Annonce 2 y
205. r comment l exercice a t r solu A partir des hypoth ses de d part ARGOS a pu d duire tape par tape ce qu il fallait d montrer Comment justifier chaque cha non interm diaire La proc dure de base est celle de l explication d un fait d duit intervenant dans la d monstration L expertise d explication doit donner en fonction du profil de l utilisateur un certain nombre de conseils Doit on expliquer le fait ou non Quel commentaire doit accompagner la donn e des faits ayant permis mergence de celui ci Comment doit on enchainer les diff rentes tapes de la preuve Comment articuler les diff rents cha nons du raisonnement reconna tre des pas de d ductions du m me type c est le de m me du math maticien et de fa on plus g n rale viter les redondances qui lassent le lecteur Comment structurer la r daction en faisant ressortir les l ments essentiels 4 3 4 Conclusion Le but ultime est de produire des traces r dig es qui retranscrivent fid lement l arbre de d monstration mais avec la plus grande conomie de moyens possible et en fonction du public auxquelles elles s adressent Ceci n cessite des connaissances sp cifiques que le syst me doit utiliser pour construire automatiquement son explication 142 5 Expressions des connaissances Le principe est d exprimer les connaissances de fa on d clarative dans une syntaxe proche du langage math mati
206. r une annonce gale 2 ou a 3 avec une pr f rence tout de m me accrue pour la premi re proposition Joueurl envisage maintenant de v rifier sa premi re intuition en tudiant le choix annonce 2 en essayant d estimer le mieux possible ses chances de r ussite L As est assez bien prot g par le 6 si bien que s il d cide de ne pas faire le pli avec l As il est tr s probable qu il r ussisse Au contraire Joueurl n a aucun contr le sur le R dont le comportement d pend uniquement de la distribution et de la volont des autres joueurs Joueurl consid re donc qu il est raisonnable de jouer le R le plus t t possible afin de lever l incertitude sur la r alisation d une lev e avec cette carte Si le RY est maitre la difficult pour Joueurl sera d viter de r aliser un pli avec l As Au contraire si le RY est coup ou remport par l Asw Joueur s efforcera de se d fausser de son As ce qui ne devrait pas 50 poser de probl mes dans le mesure o le seul cas d favorable est celui o est jou e 2 fois avant qu il ne soit ouvert 2 fois aussi n importe laquelle des autres couleurs en particulier si v est ouvert de nouveau Mais revenons sur le cas o le R n est pas ma tre Joueurl d sirant alors faire le pli avec l As a le choix entre 2 strat gies jouer le plus t t possible l Ase pour limiter les chances de d fausse des autres joueurs et donc minimiser la probabilit qu ils puissent coupe
207. rcevoir que plusieurs solutions sont du m me type 151 Comment d couvrir des sch mas d utilisation d une propri t qui pourraient d boucher sur la construction automatique de nouvelles r gles partir d une connaissance donn e Comment l tre humain classifie t il et r organise t il ses connaissances apr s la recherche d un nouvel exercice Il faut donc fournir au syst me des m ta connaissances de contr le au sens de J Pitrat Pitrat 90 qui lui permettent de monitorer ses actions d apprentissage Pitrat 99 Il faut que le syst me soit capable de juger de la qualit de ce qu il apprend Pintado 94 Exp rimentalement on constate une am lioration du d monstrateur apr s apprentissage quand il n a pas eu besoin de cr er des objets nouveaux en cours de preuve Dans le cas contraire comme les r gles de cr ation sont en bout de liste de r gles actives on ne note aucune am lioration apr s apprentissage Il manque au syst me des strat gies de cr ation d objets bien cibl es en fonction du but Voici un exemple d exercice posant probl me au niveau de l apprentissage car n cessitant beaucoup de cr ations d objets non imm diates Exemple Soit abd un triangle e le milieu de bd et d le milieu de bc et ab dc Montrer que les angles g om triques ead et dac sont gaux Figure b d C Pour montrer que cad dac ARGOS va devoir cr er des objets qui n apparaissent
208. res au jeu de Go peut tre captur e en 5 coups nous voulons trouver tous les coups abstraits qui sont susceptibles d emp cher cette cha ne d tre captur e Un coup abstrait est un coup qui est d fini en utilisant des propri t s abstraites des cha nes ou du damier comme par exemple la libert d une cha ne Nous utiliserons des noms pour les diff rents tats de jeux Le nom des jeux est suivi par un nombre qui indique le nombre minimal de coup que l attaquant doit jouer pour atteindre le but Un jeu qui peut tre gagn si l attaquant joue est appel gi Un jeu ou le d fenseur doit jouer un coup pour ne pas tre battu est appel ip Un jeu gagn pour l attaquant est appel g Un jeu est toujours associ un joueur et dans le cas des jeux gi et ip des coups de ce joueur utilis pour d finir Les d pendances entre jeux Cette figure donne les d pendances entre les diff rents jeux Un jeu peut tre d fini en utilisant les jeux d indice inf rieurs Par exemple le jeu g1 pour Blanc est d fini par le jeu est ipl pour Noir et tous les coups ip am nent des jeux gil pour Blanc 14 gil for White glfor White gi2 for White g2for White gi3 for White ip1 for Black ip2 for Black ip3 for Black Exemples de jeux La figure ci dessus donne des exemples de jeux pour le jeu de la prise Un exemple de la fa on dont les coups abstraits pour un jeu sont trouv s est par exemple le passage des jeux
209. rfaite On am liore donc un programme si partir d une bonne fonction d valuation on lui fait pr voir les cons quences de ses coups plusieurs coups l avance L hypoth se fondamentale du MiniMax est que l adversaire utilise la m me fonction d valuation que le programme Notre but est de trouver le coup qui maximise la fonction d valuation alors que le but de l adversaire est de choisir le coup qui minimise la fonction d valuation Or les deux adversaires jouent chacun leur tour et en g n ral c est le joueur ami qui joue en premier puisqu on cherche le meilleur coup jouer pour le joueur ami On va donc choisir les coups maximisant aux niveaux pairs et les coups minimisant aux niveaux impairs de l arborescence si on fait l hypoth se que le premier niveau est le niveau 0 Algorithme MiniMax sachant qu on appelle MiniMax Position 0 pour trouver le meilleur COUP define PROFMAX 5 Marche pour tous les niveaux define INIFNI MAXINT define odd a a 6 amp 1 int MiniMax char Position int profondeur int valeur Best i N char PositionSuivante 100 if profondeur PROFMAX return Evaluation Position N TrouveCoupsPossibles Position PositionSuivante Best INFINI for i 0 i lt N i valeur MiniMax PositionSuivante i profondeur 1 if odd profondeur niveaux impairs on minimise if valeur lt Best Best valeur
210. roisi me NC NL 5 elle a la propri t d tre aussi vraie si on met les num ros de d partements 1 2 26 51 80 mais elle a malheureusement trois solutions Au d part on connait un certain nombre de liens possibles entre chaque l ment de l ensemble de d part d une correspondance et certains l ments de l ensemble d arriv e de cette m me correspondance On progresse vers la solution en tablissant des liens certains entre les l ments de l ensemble de d part et les l ments de l ensemble d arriv e L limination de liens possibles est tr s utile par exemple si l on sait que DMI le degr minimum pour l ensemble de d part vaut 1 et qu il ne reste plus qu un seul lien possible alors ce lien est certain Plus on a de degr s connus et plus ces m thodes sont capables d liminer des possibilit s et de trouver des certitudes d montrer qu une injection est en r alit une bijection augmente ainsi consid rablement l efficacit de ces m thodes Le probl me est r solu quand on a trouv des liens certains entre les l ments des ensembles de d part et d arriv e de toutes les correspondances qui respectent les degr s les graphes et les cliques ventuellement d finis et qui donnent la valeur VRAI toutes les contraintes On peut vouloir chercher toutes les solutions ou s arr ter la premi re solution trouv e il suffit de pr ciser son choix au syst me On peut aussi prouv
211. rrectement avec des connaissances g n rales l utilisation de ces connaissances devient r ellement probl matique d s lors que les connaissances prodiguant des conseils notre disposition sont contradictoires et o une fonction d valuation de la situation est tr s difficile mettre au point 49 La n cessit se fait ressentir de d velopper des arborescences plus ou moins pr cises et limit es dirig es par les conseils a priori 4 2 Pr sentation de l exemple Jeu de 52 cartes 4 couleurs 4 v et 13 hauteurs As R D V 10 9 8 7 6 5 4 3 2 Main du Joueur1 a 4 v R As6 As Atout 8 Ouvreur Joueur1 Nombre de joueurs 4 Le Joueur1 est le joueur simul par le syst me 4 3 Le raisonnement L As amp tant la carte d atout la plus forte du jeu Joueurl r alisera 1 pli certainement avec cette carte Le 44 et le 6 tant des cartes tr s basse il est quasi certain qu elles ne pourront conqu rir une lev e m me si les joueurs y compris Joueurl font tout dans ce sens L Ase est la carte la plus forte sa couleur le R l est tr s probablement aussi _ il y a de grandes chances pour que l Asw soit dans le talon Vu le faible nombre de cartes dans les mains des joueurs il est fort probable que pour chacune de ces couleurs il existe au moins un des autres joueurs qui ait une coupe La r alisation des plis avec le Rw et l As est donc tr s incertaine Joueurl h site donc pou
212. s enfants encore en bas ge ont eu le m me nombre d enfants Combien Soit b le nombre d enfants et c la longueur du carr on doit avoir 94 1 b b b b c 1 Je trouve rapidement une solution la main b 3 et c 11 Je v rifie la calculette qu il n y a pas d autre solution jusqu b 10 ce qui est raisonnable comme maximum pour b 2 J essaie des calculs tr s compliqu s avec des factorisations des parit s des descentes Sans succ s Je trouve juste que b doit tre impair 3 Avec des caculs modulo 2 4 3 10 je trouve juste que b doit tre impair ou multiple de 4 et que c doit tre congru 1 ou 5 modulo 10 4 J essaie des encadrements Ayant en t te que b 5 b b i c est dire est compris entre b b et b b 1 utilis dans un probl me r solu peu de temps auparavant probl me n 10 et en partant de bf lt c lt b 1 ou mieux de b 1 lt lt b 5 eten majorant ou minorant par les entiers les plus proches on trouve Pe hee 1 lt e lt b b b t ay Dei li e b 719 508 b b Je cherche mieux encadrer avec quelque chose de la forme b 5 par exemple b Ne r ussissant pas j abandonne cette voie 5 Jai alors l id e d un raisonnement g om trique en pensant la d monstration g om trique de Dei n gt 2i 1 n 1 mais pour 1 b b b b il faudrait une 4 dimensi
213. s en poss dent si un joueur ne poss de pas de la couleur demand e il peut jouer n importe quelle carte de sa main c est dire ou bien couper jouer atout ou bien se d fausser carte qui n est ni atout ni de la couleur demand e La carte la plus forte du pli est le plus fort atout le plus haut pos si au moins 1 atout a t jou la carte la plus haute dans la couleur demand e sinon 4 1 2 Originalit s Le jeu de l ascenseur est un jeu qui offre une grande palette de situations diff rentes et n cessite la mise en oeuvre d un grand nombre de m canisme de raisonnement Le nombre de joueurs le nombre de cartes du talon initial le nombre de cartes distribu es et par cons quent le nombre de cartes dans le talon apr s distribution le jeu avec et sans atout sont autant de param tres montrant cette diversit Mais sa grande originalit par rapport aux autres jeux de lev es et la large majorit des jeux en g n ral est la difficult engendr e par le fait que les joueurs doivent r aliser un nombre de lev es bien pr cis Il en r sulte que certaines parties se d roulent avec une volont globale de l ensemble des participants de maximiser le nombre de plis remport s _ le jeu est alors de type qui gagne gagne alors que d autres parties n cessitent de faire attention de ne pas r aliser trop de lev es _ le jeu est de type qui perd gagne Alors qu il est possible pour beaucoup de probl mes de jouer co
214. sayer de trouver un chemin remplissant les deux fonctions pr vues ou remplacer la pi ce dans l une des solutions par une autre pi ce allant au m me endroit Par exemple sur la Figure 7 les situations de gauche et du milieu sont incompatibles pour noir car elles utilisent toutes deux les pi ces 13 et 21 Dans les deux cas la pi ce 13 est utilis e pour contrer la pi ce 37 Pour rendre les solutions compatibles on peut envoyer la pi ce 13 droite de la pi ce 7 mouvements gris de la situation de droite car cet endroit elle attaque la pi ce 37 dans les deux situations Pour la pi ce 21 le mieux est de la remplacer par la pi ce 23 dans la situation centrale Cela d grade un peu la solution car la pi ce 23 est moins forte mais cette d gradation n est pas grave car l attaque blanche sera toujours en chec La situation de droite montre la combinaison des deux solutions obtenues Figure 7 modification de solutions incompatibles par remplacement Lorsque ces moyens ne suffisent pas on peut simplement supprimer l un des deux chemins en conflit mais on risque alors de d grader fortement la solution Cette m thode ne doit donc tre utilis e qu en dernier recours Au total le syst me doit faire un ensemble de m ta choix portant sur le remplacement ou l annulation de choix La difficult du probl me r side dans le fait que ces m ta choix sont d pendants les uns des autres Le remplacement d un choix peut ainsi
215. se pi ce et dire si elle est plus lourde ou plus l g re 6 4 et http www710 univ lyon1 fr fouet Dir_lic_mai TP puzzles html On a douze pi ces onze bonnes et une fausse et une balance une balance qui indique quilibre ou d s quilibre pas qui donne une mesure La fausse pi ce est plus lourde ou plus l g re que les vraies En trois pes es d terminer la fausse pi ce et dire si elle est plus lourde ou plus l g re L nonc de Jean Marc Fouet comporte de plus en note de bas de page Ce probl me est tr s dur il n y a ma connaissance pas d astuce pour le r soudre Ma solution prend deux pages c est pourquoi je ne vous propose pas de zone pour donner la v tre Mais m me si vous ne trouvez pas je pense que le fait d y r fl chir est bon pour les neurones J avais cherch r soudre le probl me du Monde quelques mois avant de trouver le texte de Jean Marc sur sa page Web Je n avais pas trouv mieux que 4 pes es pour d masquer la fausse pi ce sans pouvoir dire dans tous les cas si la pi ce est plus lourde ou plus l g re une pes e suppl mentaire serait alors parfois n cessaire Mon raisonnement proc dait simplement par dichotomie 1 on laisse la moiti 6 et on met sur chaque plateau de la balance la moiti 3 de l autre moiti soit notation 313 6 Selon qu il y a quilibre ou non la fausse pi ce se trouve dans une des moiti s 6 billes l autre
216. si re les cons quences d une r gle en l examinant cr ation d une contrainte limination de liens possibles cr ation de liens certains d couverte d une contradiction Il est plus difficile mais possible de les d terminer avec plus de pr cision par exemple de voir qu une r gle cr e une contrainte d galit lin aire contenant quatre variables Il est galement possible d valuer le co t de l ex cution d une r gle a partir de celui d l ments de base comme de normaliser une contrainte ou de d terminer la borne sup rieure d une expression il faut naturellement tenir compte de la taille des ensembles que l on parcourt Le plus difficile est d valuer a priori les chances de succ s d appliquer une r gle car cela d pend beaucoup des caract ristiques et des donn es de chaque probl me C est l que le monitoring dynamique peut tre tr s utile Une fois que l on conna t les cons quences les conditions le co t et les chances de succ s d une r gle il doit tre possible de d finir une m ta expertise g n rale pour d terminer les v nements o elle doit tre d clench e et les priorit s qui y sont associ es L apprentissage doit ensuite adapter cette d cision initiale en fonction de ce qui a t observ au cours du monitoring Une difficult du monitoring dynamique est le probl me de l attention que doit on regarder Il faudra choisir quelles anomalies on va surv
217. si elles sont en disjonction et si la valeur de F E est inf rieure ou gale 9 on aura la nouvelle contrainte 3 F B lt 9 7 1 2 3 soit 3 F B lt 10 ou enfin F B lt 3 Remarquons qu il est utile de cr er une deuxi me famille de conditions qui sont de nature heuristique Mais alors ce ne sont plus des connaissances mais des m taconnaissances puisqu elles restreignent les cas o il est bon d appliquer la r gle On a le droit d appliquer la r gle si elles sont fausses mais cela risque d tre inutile Pour la r gle R2 nous pouvons avoir comme condition de ce type qu il n y ait qu une seule variable dans l expression Xj En effet la contrainte engendr e indique qu une expression est inf rieure ou gale une constante La nouvelle contrainte donnera ainsi une bonne sup rieure dans le cas o il y a une seule variable ce qui permet souvent d liminer plusieurs liens possibles alors qu une in galit avec plus d une variable serait moins facile utiliser On ne gardera pour ex cution ult rieure que les essais qui correspondent une expression X ayant au plus une variable Remarquons que le cas o il n y a pas de variable peut aussi tre int ressant car il peut conduire une contrainte dont la valeur sera FAUX ce qui donnera alors une contradiction Actuellement les conditions heuristiques d une r gle sont donn es au syst me mais elles devront ult rieurement
218. simple et puissante de la parit n est pas venue tout de suite mais en travaillant sur un sous ensemble de blocs placer celui ci tant un sous probl me du probl me initial issu d un premier raisonnement finalement inutile La solution du Monde est beaucoup plus l gante Elle est galement plus simple en un certain sens puisqu on reste sur une grille 10X10 et qu on raisonne sur les bateaux de n cases et non sur des blocs de 2X n 1 cases Si on divise la grille en 25 carr s de deux cases sur deux on remarque qu aucun de ces carr s ne peut abriter d l ments provenant de deux navires diff rents Les porte avions et les cuirass s des deux flottes occupent chacun dans le meilleur des cas deux de ces carr s ce qui en mobilise au moins 12 Les 14 98 autres bateaux en mobilisent au moins un chacun D ow la n cessit de 26 carr s pour 25 disponibles 5 3 Zigzag num rique Le Monde 4 avril Affaire de Logique Probl me n 166 Avec les chiffres de 1 6 on peut fabriquer des nombres zigzag Ces nombres que nous appellerons des 6 zigzags ont 6 chiffres qui vont d abord croissant puis d croissant puis croissant Par exemple 231546 est un 6 zigzag Combien existe t il de zigzags Pour les sp cialistes On peut tendre le probl me aux suites zigzag des n premiers nombres entiers les nombres vont d abord croissant puis d croi
219. sit galement dans un menu Interface Rois 2 V n de 8 ca ses dans On d finit ainsi comme univers l ensemble des parties de E an l ments Une fois n et E choisis votre r ponse est valid e puis v rifi e Une fois votre r ponse accept e l univers est d fini Vous pourrez le corriger tout moment en appuyant sur le bouton Changer Univers Figure 8 35 6 Vers une conception impl mentation Nous abordons la phase de r alisation de la prise en compte des erreurs Nos avons choisi les concepts valider A chacun d entre eux est associ e une condition de validit La condition de validit s exprime par une conjonction de conditions Quand l l ve clique sur le bouton valider associ au concept la condition de validit correspondante est examin e Si elle n est pas v rifi e cela veut dire qu il y a une ou plusieurs erreurs Celles ci sont alors m moris es sous la forme d une liste d objets Chacune des erreurs contient les informations n cessaires son explication Pour r aliser ceci nous avons associ chaque machine un agent p dagogue Son r le est de g rer les erreurs Le p dagogue demande la partie experte du syst me le test des diff rents l ments de la condition de validit Il d tecte si il y a une erreur ou pas et dans le cas o il y en a il va les analyser puis prendre les d cisions de r action vis vis de ces erreurs Ces d cisions concernent le moment du si
220. ssant puis croissant Sauriez vous construire un algorithme permettant de les d nombrer Enum ration des 6 zigzags Je remarque que l on retrouve des sous ensembles de 4 zigzags un renommage pr s Je recommence en utilisant explicitement les 4 zigzags et je corrige une erreur Je cherche les 5 zigzags je les utilise pour les 6 zigzags et je corrige une autre erreur Soit a le nombre de n zigzags on a a2 1 a 2 a3 5 a4 16 a 61 Cas g n ral que signifie un algorithme Une relation de r currence Je ne vois rien d autre g gt q g g En regardant la construction pour n 5 et 6 je trouve en regardant les zigzags commen ant par 1 2 n 1 a5 a4t A4 a3 a3 A3 at ayt a4 a a 16 ag ast as a4 agt azt a3 2 aat a4 ast as as a3 2 a4t a4 61 a7 aot ag a6 a4 29227 2 ast as Je n arrive pas g n raliser Nouvelle id e je m int resse aux couples mal plac s Non g n ralisable Nouvelle id e regarder ce qui est en haut et en bas apr s un raisonnement facile pour n 4 et 5 et avec les remarques suivantes pour n 6 99 123 en bas et 456 en haut 3 D 36 possibilit s on ne peut pas avoir deux parmi 123 en haut ni deux parmi 456 en bas si un parmi 123 en haut alors un parmi 456 en bas 6 ne peut pas tre en bas si 5 en bas il ne peut tre qu a gauche car seul 6 est plus grand que lui
221. ssi le milieu de l autre diagonale Traduction interne regle N conjecture _ appelConjecture non N plg A B C D eltConcl N rect A B C D eltConcl N losange A B C D N carre A B C D eltConcl eltConcl r milieu N A C I _ not milieu N B D I1 _ not conj_traite N milieu B D I assert conj_traite N milieu B D I Xa By Sp milieu N B D I _ not milieu N A C I _ not conj_traite N milieu A C I assert conj_traite N milieu A C I X A Y C S crire ce message sur le brouillon de recherch ecrirel comme I est milieu d une des diagonales montrons 150 que l mil X Y pour montrer que A B C D est un parall logramme conjl N milieu X Y I _ On peut envisager la possibilit de construction automatique d une telle r gle a partir d nonc s d claratifs du type ci dessus Un utilisateur math maticien pourra ainsi exprimer des heuristiques qui pourront tre transform es en r gles automatiquement par le syst me 8 Apprentissage 8 1 En quoi le syst me devient il diff rent apr s avoir r solu un exercice Apr s avoir r solu un exercice ARGOS accomplit un certain nombre de t ches automatiquement Il constitue tout d abord une base de donn es contenant les r gles qui se sont d clench es celles qui ont
222. st bon de poser une hypoth se partir de N sur la valeur de la couleur demand e Le d clenchement de ces r gles aboutit sur un ensemble de conseils sur le type d hypoth se poser qu il est n cessaire d agr ger Le conseil r sultant de poids maximal indique la m ta d cision prendre Ces m tar gles sont suffisantes pour une premi re approche de la r solution des probl mes du jeu de l ascenseur Nous verrons comment elles s appliquent dans la partie 4 4 3 4 Le m ta choix des valeurs Une fois que le syst me conna t le type d hypoth se poser il lui reste encore m ta consid rer les instances consid rer Une premi re approche serait de consid rer l ensemble des valeurs possibles le syst me envisagerait toutes les cartes autoris es jouer pour un pli donn il envisagerait les 2 cas syst matiquement o il remporte le pli ou ne le remporte pas et aussi les cas o la couleur 47 demand e prend chacune des valeurs possibles des 4 couleurs L intelligence de l tre humain semble cependant r sider en grande partie dans sa capacit s lectionner les coups et les situations sur l ensemble des situations possibles Nous proposons donc ici d utiliser des connaissances d claratives pour s lectionner celles que le syst me sera amen envisager A partir de l ensemble des conseils sur un choix du syst me nous liminons tous les coups dont le poids du conseil est inf rieur un seuil gal
223. ste d un choix alternatif C2 alors le choix C1 est assur ment meilleur que le choix C2 D apr s la r gle g n rale donn e en 2 1 2 le syst me conclue qu il est inutile de d velopper les n uds issus du choix C2 4 Application un exemple d taill du jeu de l ascenseur Nous montrons sur un exemple tir du jeu de l ascenseur une application des id es pr sent es pr c demment 4 1 Bref rappel des r gles du jeu de l ascenseur Afin de mieux comprendre cet exemple un rappel des r gles du jeu de l ascenseur est 48 n cessaire 4 1 1 R gles du jeu Le jeu de l ascenseur est un jeu de cartes de la famille des jeux de lev es 2 joueurs ou plus Apr s distribution d une partie ou de la totalit du talon l ensemble des joueurs ces derniers doivent annoncer le nombre de lev es ou plis qu ils croient pouvoir r aliser avec le jeu en main un atout couleur des cartes les plus fortes tant fix par la distribution Le jeu de la carte se d roule ensuite de fa on classique chaque joueur joue une carte et une seule par pli l ouvreur celui qui entame du ler pli est le joueur suivant le donneur le joueur ma tre d un pli celui qui a pos la carte la plus forte ouvre le pli suivant l ouvreur peut jouer n importe laquelle des cartes qu il a en main la carte jou e par l ouvreur d termine la couleur demand e couleur de cette carte les autres joueurs doivent fournir la couleur demand e s il
224. sup rieur au gain de la phase de raisonnement proprement dite 3 4 2 Qualit des solutions obtenues fe m P tt edad Sel RAR Fe gt N s s cal EE RD IN jojo fo KER zz Pe N Pee es ere Figure 10 Exemple de combinaison qui modifie profond ment les structures de la solution Nous avons vu que la combinaison a posteriori de deux solutions partielles tait un probl me difficile En pratique la m thode bas e sur la r flexivit que nous avons impl ment e ne permet pas en g n ral d obtenir des solutions optimales car la solution combin e ne peut souvent pas se d duire des deux solutions partielles Par exemple sur la Figure 10 les structures des deux solutions partielles de gauche ne se retrouvent pas dans la solution finale de droite Cette derni re est unique car aucune autre solution ne permet de prendre les deux A 14 pi ces noires simultan ment 14 Dans cet exemple les cases gris es sont infranchissables et toutes les pi ces blanches se d placent de deux cases La pi ce blanche centrale est suppos e plus forte que les autres 68 La m thode pr sent e dans cette partie qui consiste construire la solution finale partir des deux solutions partielles ne peut donc s appliquer dans ces cas Si on cherche compliquer la m thode de combinaison pour pallier ce probl me on tombe in vitablement sur la n cessit de recommencer le raisonnement en prenant
225. t Elle indique que si l on a une contrainte R de la forme SOMME Xi X2 XnJ Y alors on an nouvelles contraintes possibles Xi lt SUP Y INF SSOMME X Xo Xi 1 Xir1 Xn La priorit P d envisager un de ces essais par exemple celui correspondant essai qui cr e une borne sup rieure pour l expression X figurant dans la somme sera PROG COND Q 2 ELEVE Q 3 ASSEZELEVE Q 4 MOYEN Q 5 ASSEZBAS Q 6 TRESBAS CONDIM gt 1 MS8 1 M gt 8 2 0 ou Q et M sont d finis par deux l ments dans E Q CARVAR R donc Q est le nombre de variables de R et M FACTEUR X La fonction FACTEUR a pour valeur le facteur constant qui multiplie ventuellement la variable dans son argument et la valeur 0 si le terme Xi n est pas le produit d une expression par une constante Si X est l expression 5 V la valeur de M est 5 par contre si X est l expression W T sa valeur est 1 La fonction PROG A B o A est une priorit et B un entier a pour effet d augmenter de B unit s la valeur de la priorit A si B est n gatif il la diminue de B unit s Par exemple PROG ASSEZBAS 2 a pour valeur ASSEZELEVE Si B est nul qui est ici la valeur par d faut de M la valeur de A est inchang e L utilisation de cette fonction a l int r t de favoriser les essais o le terme premier membre de l in galit contient un coefficient et ce d autant plus que ce coefficient est grand En effet 10 V lt 13 d
226. t e des informations et la d sactivation de certains n uds 3 2 Choix du n ud d velopper Commen ons par pr ciser quelques concepts utilis s par la suite Choix principal choix pour lequel le syst me doit prendre une d cision Ce choix correspond dans les arbres classiques des arcs issus du n ud correspondant la situation courante Choix alternatif une choix C1 est un choix alternatif un choix C2 si C1 et C2 correspondent une m me d cision dans une m me situation Les arcs correspondant ces choix dans l arbre sont donc issus du m me n ud N ud Choix n ud issu d un arc choix N ud Evenement n ud issu d un arc v nement La mise au point de l alpha beta a rendu primordiale la question du m ta choix de l ordre des choix envisager pour un m me niveau Cet ordre est le conditionnement du nombre de coupes effectu es par l alpha beta Ce nombre est d autant plus grand et l algorithme plus efficace que les meilleurs coups sont consid r s en premier par le syst me En effet si le syst me obtient tr s t t la meilleur valeur pour le choix C1 il lui sera inutile de continuer d velopper les coups Cx alternatifs C1 partir du moment o il aura d j d velopp une des branches Cx 1 la valeur trouv e par chacune de ces explorations aboutissant forc ment de nouvelles coupes 44 Le choix du n ud d velopper doit donc toujours tre guid par l optique d obtenir le plus rapideme
227. t bien faire partager ses quatre complices Mais voil les cinq comm res sont dispers es ce jour l aux cinq coins de la ville Heureusement elles poss dent des t l phones portables Combien d appels t l phoniques au minimum seront n cessaires pour que chacune des cinq comm res poss de chacun des cinq potins Et combien d appels seront n cessaires avec un nombre quelconque de comm res N B Evidemment aucune n a un abonnement permettant la conversation trois ou plus ni m me le signal d appel Premiers essais deux m thodes pour trouver une solution en 7 appels g n ralisables pour n quelconques n 1 n 2 2n 3 Pour les premi res valeurs de n cela donne n 2 2 appels 85 n 3 3 appels 3 5 2 n 4 5 appels mais on peut faire mieux pour n 4 4 appels l par r currence sur n An An 2 1 n 4 appels pale Tiat debut gane SEA DAS CAT TS T ET OT DR il faudrait le compl ter la fin ue L aller retour simple desc donnant 2 n 3 appels ee Pe a nee 2 n 2 appels Remarque on passe de n n 1 en rajoutant 2 appels sauf pour 1 2et3 4 et0 1 Peut on faire mieux Id e regrouper 2 par 2 ou par paquets de 4 Travail sur les aller retours sur l appel qui rend la premi re comm re savante Importance du sous ensemble de 2 et importance du dernier morceau de 4 Nombreux essais CFO Der ZS ae 86 Le Le Inutile d essayer de faire
228. t des contraintes de Lyc e Jacquard Paris LIP6 P le IA SYSDEF Universit Pierre et Marie Curie Paris VI gt CRIP5 SBC Universit Ren Descartes ParisV 22 s lection Nous avons d fini les fondements math matiques d une m thode de r solution la m thode constructive adapt e aux conceptions usuelles des l ves et permettant d acc der la th orie math matique du domaine Tisseau et al 96 Le Calvez et al 97 Nous avons d fini une classification des probl mes du domaine et les sch mas de r solution associ s aux diff rentes classes Nous avons introduit pour chaque classe une machine a construire une solution Chaque machine se pr sente pour l l ve sous forme d une interface p dagogique qui conduit l l ve construire la solution d un exercice de la classe consid r e Dans une interface p dagogique la gestion des erreurs est tr s importante pour optimiser l efficacit p dagogique de l interface Contrairement une interface usuelle il faut pouvoir laisser l l ve la possibilit d exprimer sa solution et donc de commettre des erreurs G n ralement on essaie dans une interface de canaliser l activit de l intervenant pour qu il effectue le moins d erreurs possibles Choplin and al 98 Il est en effet techniquement possible de concevoir l interface pour que l utilisateur ne puisse pas commettre certaines erreurs En effet les erreurs sont provoqu es par des actions de l u
229. te une m connaissance suppl mentaire sur les situations pr visionnelles Les situations repr sent es par les n uds de l arborescence sont connues de mani re incertaine et impr cise le d roulement m me du jeu devient lui aussi vague Toutes ces difficult s d roulement du jeu variable incompl tude des informations hypoth ses sur des v nements abstraits rendent n cessaire l laboration d une expertise de choix du type d hypoth se poser Nous conseillons l utilisation de connaissances d claratives travers l emploi de m tar gles analysant la situation quelles sont les connaissances disponibles indisponibles dans la situation en question conseill res sur ce type d hypoth se A l ascenseur par exemple il est primordial pour l tude d un pli de conna tre l ouvreur de ce pli ou du moins savoir si le joueur simul par le syst me sera ou non l ouvreur les coups l gaux des joueurs tant d termin s pour une grande partie par le choix de cet ouvreur Lorsqu un n ud de l arbre de recherche d crit une situation dans laquelle l ouvreur d un pli n est pas connu alors qu elle comporte une description satisfaisante du pli pr c dent il sera bon que le syst me envisage de nouvelles situations g n r es par la pr c dente et fonction du joueur qui sera ouvreur Il appara t clairement que cette expertise d pend fortement des r gles du jeu auquel le syst me est confront Le jeu de l ascenseur Pour
230. tilisateur cliquer sur un bouton choisir un item de menu et il est parfois possible de pr voir avant m me que l action soit ex cut e si elle pourra provoquer une erreur ou non Dans ce cas on peut faire en sorte que les possibilit s d action offertes l utilisateur ne puissent pas provoquer d erreur et cela dynamiquement en fonction de la situation rendre indisponibles les boutons qui provoqueraient des erreurs ou ne faire figurer dans un menu que les items qui ne provoquent pas d erreur Les autres erreurs sont d tect es sur le champ signal es et ventuellement corrig es Dans une interface p dagogique il faut quelquefois laisser l l ve s exprimer m me si l on pr voit une erreur ou si l on en a d tect une soit pour qu il s en aper oive tout seul plus tard soit pour lui montrer qu il arrive une impasse et profiter de l occasion pour lui apprendre quelque chose Cependant toutes les erreurs ne sont pas de la m me difficult ni du m me int r t p dagogique Une tude sur les diff rents types d erreurs doit permettre de d cider quelles sont celles qui seront permises l l ve et celles qu il ne pourra commettre D autre part les erreurs peuvent tre de type diff rents par exemple provoqu es par l utilisation de l interface ou correspondant des concepts math matiques Dans certains cas on essaiera de proposer l l ve des possibilit s d interaction o il ne peut pas faire ces erreurs
231. tion de l nonc 7 1 Enqu te Le Monde 30 mai Affaire de Logique Probl me n 173 Trois malfaiteurs sont soup onn s de meurtre Un et un seul des trois est coupable Les enqu teurs ont recueilli trois d clarations de chacun d eux Andr Al Je suis innocent A2 D ailleurs l heure du crime j tais 10 kilom tres de l avec B atrice A3 Claude est coupable B atrice B1 Je suis innocente B2 Andr aussi B3 Mais il n tait pas avec moi l heure du crime Claude C1 Je suis innocent C2 B atrice aussi C3 Andr a menti trois fois Sachant que chacun des suspects a menti au moins une fois qui est coupable Jai d abord consid r que j tais 10 kilom tres de l avec B atrice n tait pas exactement la n gation de il n tait pas avec moi l heure du crime car Andr aurait pu tre avec B atrice l heure du crime mais pas 10 km de l Trouvant alors deux solutions B atrice ou Claude coupable jen ai conclu que mon interpr tation n tait pas la bonne non A2 entra ne B3 et B atrice est coupable C est la solution du Monde et cela tait galement clair pour d autres lecteurs de mon entourage 107 8 Autres probl mes Le premier de ces probl mes montre que quand on est tr s savant on r sout facilement les probl mes th oriquement mais qu avec un pe
232. tion no 2 Puisque droite a b droite d c et que les points o b et c sont align s alors l homoth tie de centre o envoyant a en d envoie b enc Les points a et b se transforment par l homoth tie hom en les points d et c or i est le milieu de ab etj est le milieu de d c donc j est l image de i par hom car une homoth tie conserve le milieu Dans une homoth tie un point et son image sont align s avec le centre donc comme ici i se transforme en j par l homoth tie de centre o et de rapport rap alors les points o i j sont align s les points o 1 et j sont align s donc j est un point de la droite oi 166
233. travail de Michel Buthion et en particulier par ses id es sur le transformations g om triques et l impl mentation de cette m thode La solution du Monde est la m me mais exprim e en termes beaucoup plus l mentaires et certainement moins facile trouver directement et moins facile m moriser 6 2 Des sous des sous Le Monde 28 mars Affaire de Logique Probl me n 164 Placez sur un papier une pi ce de 5 francs et un peu plus loin une pi ce de 10 centimes Menez du centre de la grande pi ce deux tangentes la petite et du centre de la petite deux tangentes la grande comme sur le dessin Il semblerait que les longueurs des segments verticaux AB et IJ soient gales est ce vrai Je vois imm diatement les deux triangles semblables OHA et OKO d o l on d duit RXR OO facilement que AB Idem pour IJ Ici il s est agi d un r flexe 102 6 3 La fausse pi ce Le Monde 25 janvier Affaire de Logique Probl me n 156 Vous disposez d une balance deux plateaux et de douze pi ces d aspect identique Onze sont d authentiques pi ces de collection la derni re n est qu une imitation si bien faite qu elle a le m me aspect que les autres Heureusement sa masse diff re l g rement de celle des vraies pi ces mais vous ignorez si elle est plus lourde ou plus l g re Comment en un minimum de pes es d masquer la faus
234. tre d couvertes et ventuellement modifi es par le syst me qui apprendra ainsi mieux s lectionner ses essais C est encore au monitoring de g rer la cr ation et la modification des conditions heuristiques Le syst me dispose actuellement d une soixantaine de r gles qui peuvent tre donn es 122 ind pendamment les unes des autres Chacune d entre elles a plusieurs utilisations possibles selon ce qui lui est donn au moment de l instanciation Par exemple la r gle R1 peut tre utilis e chaque fois que l on a une nouvelle contrainte d galit et aussi chaque fois que l on augmente la valeur de la borne inf rieure d une variable on prendra comme terme Y le membre d une galit qui la contient et enfin chaque fois que l on diminue la valeur de la borne sup rieure d une variable on prendra cette fois comme terme X le membre d une galit qui la contient Il est possible de l appliquer dans d autres situations mais cela ne donnera en principe rien d utile Si l on utilisait syst matiquement toutes les r gles dans toutes les situations o elles ont une chance m me tr s faible de donner un r sultat on aurait une m tacombinatoire norme En contrepartie on aurait dans certains cas des solutions tr s l gantes demandant une combinatoire tr s r duite Il est n cessaire d avoir des m taconnaissances capables de se servir des r gles bon escient et de faire un arbitrage judici
235. truit l arbre de preuve partir des faits d duits et l aide de celui ci produit une preuve r dig e en fran ais de l exercice propos Nous voquerons ensuite la possibilit pour le syst me de construire automatiquement des r gles partir du savoir math matique exprim de fa on d clarative Nous examinerons la possibilit qu a le syst me de lancer des appels de conjectures en cours de recherche si certaines conditions sont r unies dans la base de faits et aussi comment ARGOS apr s avoir r solu un exercice construit une base de donn es relative l exercice et apprend de nouvelles connaissances de savoir faire en mettant jour des strat gies qu il a lui m me mis au point de fa on automatique en r solvant des exercices Une utilisation du syst me est aussi possible dans le cadre d un EJAO nous montrerons de quelle mani re Nous conclurons en voquant la principale difficult des d monstrateurs qui consiste en la mise au point de r elles et efficaces heuristiques de cr ation d objets 2 Fonctionnement g n ral du syst me L id e de d part tait de construire un d monstrateur robuste et fiable et d utiliser ses potentialit s comme support permettant un apprentissage de la g om trie par un l ve de lyc e ou coll ge ARGOS est un syst me base de connaissances con u partir du syst me MUSCADET de Dominique Pastre et travaillant dans le domaine de la g om trie Il se situe dans la continu
236. u de t nacit on le r sout concr tement Les deux suivants sont des probl mes combinatoires pour lesquels des techniques type ALICE donnent de bons r sultats N anmoins dans le probl me de crypt arithm tique il est utile de ne pas se contenter d crire les quations entre les chiffres mais de consid rer aussi les entiers Enfin le dernier probl me conduit une r flexion sur la r partition des nombres qui m a tonn e 8 1 Pr fixes pour puissances Le Monde 22 f vrier Affaire de Logique Probl me n 160 En multipliant le chiffre 2 par lui m me un certain nombre de fois on obtient une puissance de 2 qui s crit avec un 2 suivi en exposant de ce nombre de fois Ainsi les premi res puissances de 2 sont 2 2 27 4 2 8 2 16 2 32 2 64 2 128 Une puissance de 2 peut elle commencer par le chiffre 7 Et par les quatre chiffres 2 0 0 0 Je pense d abord que non Je remplace 7 par 2 1 et j cris 2 1 x 10 a 2P De nombreuses manipulations regroupement des puissances de 2 factorisations log ne donnent rien Je regarde les premiers 1248 136 125 1248 136 125 Ca semble recommencer toujours Avec une calculette je trouve 2 7 0368 x 10 C est faisable la main Pour 2000 je divise successivement par 2 2000 1 9 1000 0 4 500 0 2 250 0 1 1250 FOSO z 625 0 4 B12 oF a 0 0 108
237. uation et tre observ en train de r soudre des probl mes De nombreux chercheurs ont effectu de telles observations Pastre 78 Chi 81 Schoenfeld 85 A d faut de pouvoir observer quelqu un d autre il est aussi possible de s auto observer Ces observations sont n cessairement un peu biais es car il est difficile d tre a la fois l observ et l observateur et d effectuer en plus de la t che de r solution de probl mes la t che d observation N anmoins ces observations peuvent tre tr s utiles pour l Intelligence Artificielle car m me si elles ne donnent pas exactement ce qui s est pass dans la t te de l observ elles montrent des cheminements plausibles dont il est T1 raisonnable de s inspirer pour r soudre automatiquement expliquer dialoguer Il est m me possible et utile de s observer en train de s observer Pitrat 99 Les probl mes dont la r solution est analys e dans cet article sont des probl mes de logique ou de math matiques ne n cessitant pas en g n ral de connaissances math matiques tr s approfondies mais n cessitant parfois une recherche assez longue Si certains ont t r solus en quelques heures ou m me en quelques minutes d autres ont n cessit plusieurs jours voire plusieurs semaines Dans ces cas l il y a bien s r en plus maturation entre deux p riodes de r flexion Dans ces conditions seule une auto observation tait envisageable II m
238. ui se passe dans d autres interfaces n attendons pas que la solution de l l ve soit compl te pour l analyser et pour signaler des erreurs Les erreurs sont d tect es lors des demandes de validation au cours de la construction de la solution et selon les concepts valider retenus Pour des raisons p dagogiques le moment de signalement des erreurs peut tre repouss apr s le moment de d tection Par exemple on pourrait attendre la validation finale pour signaler les erreurs externes c est dire celles qui correspondent une solution d un exercice de la classe de la machine mais qui ne correspondent pas une solution de l exercice r soudre Pour mettre en uvre ce retard dans le signalement de l erreur il faut m moriser les erreurs en tenant compte des annulations et modifications Cela n cessite un m canisme de mise jour du type historique ou pile Certaines erreurs peuvent tre signal es mais pas expliqu es sur le moment Leur explication peut tre report e la validation finale Lors de la d tection on voit juste un message Attention il y a une erreur Vous pouvez essayer de la corriger sinon vous pouvez continuer mais vous devrez attendre la validation finale pour avoir l explication d taill e Ce probl me de d tection et de signalement des erreurs est tr s diff rent des principes d ergonomie qui disent il faut tout contr ler le plus possible pour viter l apparition d err
239. uise une liste de connaissances qui vont s enrichir au fil des ans se modifier et s enrichir Il pourra crire des r gles math matiques m me fausses sans tre jug ou sanctionn qu il pourra voir l uvre sur des exercices concrets Il s apercevra alors des insuffisances ou contradictions et pourra avoir envie d y rem dier Ainsi 154 il pourra aussi am liorer sa fa on d expliquer en examinant les preuves renvoy es par Argos partir de ses mod les explicatifs Argos devient l apprenant et ceci fait jouer un r le actif l l ve qui est ainsi valoris 9 5 Insuffisances L l ve devrait pouvoir proposer lui m me une solution r dig e de l exercice tre aid dans la construction de la preuve et la faire analyser par Argos renvoi d un contre exemple pour une r gle mal utilis e indication des l ments cl s indiquer l impossibilit d une d duction etc Argos devrait pouvoir d gager l id e directrice de la d monstration les l ments cl pour pouvoir guider l l ve Il faudrait pouvoir en fonction des hypoth ses pr sentes demander Argos de donner toutes les instanciations correspondantes un certain type de configurations ceci revient en fait extraire de la figure des sous figures correspondantes des configurations classiques 10 Probl mes rencontr s en D monstration Automatique de Th or mes 10 1 Quels objets introduire au d part Il faut effectuer un savant dosage
240. un cart entre le temps pr vu et le temps effectu pour une action une s quence de m ta actions sera pr vue par exemple de rendre cette action moins souvent applicable ou de r duire sa priorit ou m me de ne plus du tout l ex cuter par la suite Le r le du m tamonitoring est de v rifier que ces m ta actions ne 130 prennent pas un temps inconsid r auquel cas il prendra sur ces s quences de m ta actions des d cisions analogues celles prises sur les actions Nous viterons toutefois d y inclure des m ta actions qui peuvent tre dangereuses parce que difficilement contr lables Un autre r le important du m tamonitoring sera de contr ler les exp riences que le syst me fait pour v rifier une hypoth se ou d terminer la meilleure valeur de certains coefficients Sans pr cautions cela peut amener des pertes de temps consid rables si l on fait des essais innombrables et sans grand int r t L expertise de m tamonitoring doit tre simple pour qu elle ne demande pas trop de temps et que l on puisse facilement s assurer de sa s curit Avec ce garde fou il devra tre possible de faire un syst me compl tement autonome pour lequel on n aura pas les risques de d rive auxquelles a d faire face un syst me comme EURISKO Lenat 83 Le niveau sup rieur doit tre la fois simple et inchangeable Dans un premier temps les op rations dangereuses seront seulement propos es ce sera l uti
241. un ensemble de n solutions partielles correspondantes n feuilles de l arbre des hypoth ses 1l existe encore de nombreuses fa ons d effectuer la combinaison et celles ci ne sont pas toutes viables ni quivalentes En effet des contraintes d unicit de ressource une pi ce ne peut avoir deux chemins diff rents deux pi ces ne peuvent aller au m me endroit au m me moment etc font que la simple addition des solutions partielles donne souvent une solution impossible Les modifications que l on peut alors apporter pour rendre la solution viable risquent de changer les cons quences et les int r ts des solutions partielles initiales Tout le probl me est donc de trouver la meilleure fa on de combiner l ensemble de solutions partielles tudi Pour simplifier les explications nous supposerons dans la suite que n 2 combinaison de deux solutions partielles Plus formellement le but de cette recherche est donc de g n rer deux solutions compatibles s et s 2 partir des solutions incompatibles s et s2 telles que s et s soient les moins d grad es possibles Il s agit alors d un nouveau probl me d optimisation pour le syst me Il existe plusieurs moyens pour supprimer une incompatibilit sans trop d grader les 63 solutions Dans le cas d un jeu de strat gie une incompatibilit provient par exemple de l utilisation de la m me pi ce dans les deux solutions avec des chemins diff rents On peut alors es
242. urtant cet essai a conduit la solution Ou bien il devait enlever au plus une valeur possible pour une variable et en r alit 1l en a supprim une dizaine Cette fois cela intervient plus souvent avec des m taconnaissances interpr t es o l on est beaucoup moins s r de ce que va donner un essai Il constate que tout se d roule normalement Cela permet de conforter l int r t d une m thode Il d cide de fonctionner en utilisant les m taconnaissances compil es ou au contraire d interpr ter les m taconnaissances d claratives Il se rend compte qu il ne sert rien d tre intelligent pour r soudre un certain sous probl me il engendre un programme combinatoire qui examine toutes les combinaisons de valeurs possibles pour les variables jusqu ce que ce sous probl me soit r solu Naturellement il doit cr er intelligemment ce programme combinatoire Lauri re 96 Il essaye de modifier l nonc du probl me de fa on le mettre sous une forme telle que ses heuristiques soient plus efficaces ou bien que la combinatoire soit bien plus faible 10 Il d cide de faire une exp rience pour v rifier une hypoth se en particulier l efficacit des m taconnaissances compil es qu il a engendr es 11 Il sauvegarde des informations sur ce qui s est pass dans une certaine situation afin d avoir des l ments pour apprendre ult rieurement partir de ce qui s est produit Il
243. uve ce m me coup en 1 2V n n uds si les coups sont bien ordonn s Knuth 75 L ordre des coups est important car du bon ordre d pend le nombre de coupes Algorithme AlphaBeta on appelle la fonction avec AlphaBeta Position 0 INFINI INFIND define PROFMAX 4 Ne marche que pour les niveaux pairs define INFINI MAXINT define odd a a 6 amp 1 int AlphaBeta char Position int profondeur int alpha int beta int valeur Best i N char PositionSuivante 100 if profondeur PROFMAX return Evaluation Position N TrouveCoupsPossibles Position PositionSuivante if odd profondeur Best INFINI else Best INFINI for i 0 i lt N i valeur AlphaBeta PositionSuivante i profondeur l alpha beta if odd profondeur on minimise if valeur lt Best Best valeur if Best lt beta beta Best if alpha gt beta return Best coupure alpha else if valeur gt Best on maximise Best valeur if Best gt alpha alpha Best if alpha gt beta return Best coupure beta return Best 2 3 Le NegaMax avec coupures Alpha B ta On peut utiliser des coupures Alpha et B ta dans le negamax On obtient alors l algorithme suivant define PROFMAX 4 Ne marche que pour les niveaux pairs define INFINI MAXINT int NegaAlphaBeta char Position int profond
244. ux choix abstraits sont envisag es par le syst me sous la forme d hypoth ses La possibilit de raisonner sur des hypoth ses est l une des facult s fondamentales de l intelligence humaine Le raisonnement hypoth tique consiste supposer vrai une connaissance dont on ne conna t pas en pratique la valeur de v rit puis la supposer fausse Dans les deux cas on effectue un raisonnement pour r soudre le probl me sous l hypoth se pos e phase de raisonnement puis on s lectionne la solution globale qui sera propos e phase de s lection A partir de ce fonctionnement g n rique des diff rences peuvent ensuite appara tre selon le type d hypoth se pos e Pour un syst me confront un environnement dans lequel il doit interagir les hypoth ses peuvent porter sur deux types diff rents de concept utilis dans le raisonnement les concepts contr lables et les concepts incontr lables Les premiers sont constitu s des actions personnelles du syst me dont la ma trise lui est totalement et exclusivement acquise Ils sont a la fois la cause et l objet du raisonnement Les concepts incontr lables comprennent quant eux la description de l tat actuel du monde et les v nements futurs g n r s par ce monde et subis par le syst me Les v nements futurs peuvent repr senter aussi bien des v nements al atoires intervention de la nature pour lesquels la th orie de la d cision fournit un cadre forme
245. ux plus tard sans utiliser de b T J ai alors la solution pour le cas 1 pes e en d s quilibre en effet on p se alors 2 pes e T si quilibre il reste qui est r solu en une 3 pes e 104 sinon on a ou qui est aussi r solu en une 3 pes e Je crois avoir termin mais je m aper ois que l autre cas apr s la 1 pes e 4 j avais la 2 mauvaise pi ce mais pas toujours le sens de l erreur en faisant 2 pes e T si d s quilibre on a qui est r solu en une 3 pes e mais sinon on a qui en une pes e ne donne que la pi ce pas toujours le sens de l erreur Je cherche les situations o l on peut en 2 pes es J essaie en pesant bbb Ca marche J essaie en pesant T bbbbb mais de toute fa on on n a pas 5b apr s la premicre pes e ci dessus Je remarque qu en cas d quilibre aux deux premi res pes es il faut qu il ne reste qu un sinon on ne peut pas conclure Je fais alors des essais infructueux en commen ant par la premi re pes e 5 T 5 2 car alors c est l autre cas de la 1 pes e qui ne marche plus Je d cide alors de nouveau de remonter depuis l arr t en cherchant syst matiquement le nombre de pes es n cessaires pour de petits ensembles de billes En faisant cela l id e suivante appara t il faut absolument que de on obtienne au pire
246. ves ou entre le correcteur et le candidat un examen Ceci d pend aussi du niveau d tude Une r daction de solution pour un exercice de g om trie donn ne sera pas la m me en troisi me en seconde ou en terminale Il y a des choses que l on passera sous silence pour viter des lourdeurs de r daction ou parce qu on pense qu un certain niveau le lecteur est capable de faire la d duction manquante par lui m me Il y a un bel exemple de ce genre de probl me dans l exercice d crit plus haut La r gle rajoutant que fbm abc car ce sont des angles oppos s par le sommet est oblig e de v rifier que f b et c sont align s dans cet ordre car sinon elle ferait d duire des arguments faux au d monstrateur dans d autres circonstances Avec une figure comme ci dessous en oubliant la condition pr c dente la r gle rajouterait que abe fbd 141 Pourtant quand on donne cet exercice un expert celui ci n voque jamais ce probl me Il le lit sur la figure et consid re cette propri t comme allant de soi Mais si on lui demande de le prouver a n est pas imm diat Pour le d monstrateur le contrat didactique est simple rien ne doit tre pass sous silence Par contre au moment de l argumentation ceci sera possible et m me souvent souhaitable d un point de vue p dagogique 4 3 3 Construction de la preuve r dig e Il s agit ici de r soudre un probl me celui d expliquer un utilisateu
247. x deux ga fbcar gab fest un parall logramme c t s oppos s d un parall logramme fg bacar fgab est un parall logramme c t s oppos s d un parall logramme ab f g est un losange car a b b f f g ga et donc les quatre c t s ont m me longueur 162 Annexe2 graphe complet du th or me ayant servi d exemple graphe du th or me th118 a 7 70E 01 lacmf rectangle ie es de d sur bc dans cet ordre 2 90E 01 mes 60 d veloppement classique N init 3 7 60E 01 5 90E 01 HHHHHHH bemil o mil c t Eu Tong2 ab Tong2 be A 6 10E 01 7 50E 01 ae 1 50E 01 a 10 5 70E 01 2 40E 01 long2 be long2 bf c app bc f app bc b app bc long ab long2 long long bc A 2 7 30E 01 7 40E 01 init 5 Lex init 3 1 90E 01 54 8 init 4 init 2 AI FprojOrthog de d 5 Es abc long4 bf long2 long4 ca Cael long mb b mil a m bc orthog fd long2 mf long mb mil b d saikera long ab A 7 10E 01 5 80E 01 7 30E 01 init 5 mbf f projOrthog l 2 mb M 4 bf quilat ral SS GERS de d sur bc A 6 90E 01 54 5 80E 01 2 90E 01 mes mbf long2 mf long2 mb mes 60 lt q _____ init 2 ae 5 70E 01 long mb long2 long eee 3 70E 01 1 40E 01 y fbc align s abd

1 Une maladie foudroyante pour l`un, un accident stupide pour l

Contents

Download Pdf Manuals

Related Search

Related Contents