|
Exercices I |
 |
peut être définie comme la tentative d'obtenir des machines comme celles qu'on voit dans les films." Russell Beale |
Après avoir fait un survol de l'histoire de l'intelligence artificielle,
dans la premiere session d'exercises, il s'agit de jouer le jeu de nim
contre un ordinateur et de comprendre "l'intelligence" de l'ordinateur, utiliser
un système expert et finir par une séance avec la thérapeute Eliza.
1. Le Jeu de Nim
Le jeu de Nim se joue à deux, avec quelques allumettes, en nombre
N.
Chacun des deux joueurs doit retirer du tas, à tour de
rôle, 1, 2 ou 3 allumettes.
Celui qui prend la dernière a perdu.
Essayez de jouer avec l'ordinateur: site
1
Ce 2ème site vous permet de joueur une autre version du jeu de Nim.
Comment ça marche ?
L'espace des états de ce jeu, c'est à dire le nombre
de possibilités de jouer, n'est pas très grand.
Alors, on peut programmer dans l'ordinateur l'arborescence qui conduit
à la victoire!
Si on jeu, par exemple avec 7 allumettes, l'ordinateur s'initialise
à l'état F7 et attend le choix de l'autre joueur.... si vous prennait une allumette, il passera à
l'état S6, si vous prennez deux
allumettes, il passera à l'état S5, et ainsi de suite
(voir Figure 1)
Figure
1.
Voici l'arbre complet pour un jeu de 7 allumettes:
Les noeux terminaux (les feuilles) prennent les valeurs W et L pour indiquer à l'ordinateur s'il gagne (W) ou pas (L).
Un truc pour gagner: l'examen attentif de l'arborescence du jeu montre qu'il existe une solution algorithmique simple: pour gagner, il faut laisser toujours a l'autre joueur un nombre N d'allumettes tels que N=4n+1, n=1,2,3...!
Dans le cas du jeu d'échecs, l'espace des états a été
estimé à 1043, donc, pas possible de exploiter
un tel arbre. Il faut utiliser des algorithmes de recherche et des heuristiques, mais surtout une machine très puissante!
2. Minimax et Minimax avec élagage alpha-beta
2.1 Exécuter manuellement l'algorithme Minimax dans l'arbre de la figure ci-dessus.
2.2 Exécuter l'élagage alpha-beta (de gauche à droite) sur l'arbre de l'exercice 2.1
2.3 Exécuter l'élagage alpha-beta (de droite à gauche) sur l'arbre de l'exercice 2.1. Expliquez les différences avec le résultat obtenue dans l'exercice 2.2
3. Minimax pour le Jeu de Dames (Checkers)
Dans ce fichier zip vous allez trouver les sources (JAVA) du Jeu de Dames. Vous y trouverez également l'implémentation de l'algorithme Minimax.
Le principe du jeu est expliqué dans l'encyclopédie libre Wikipédia.
Essayez d'abord le jeu et ensuite répondez aux questions suivantes:
3.1 Quelle est la profondeur utilisée par l'ordinateur pour faire la recherche du meilleur coup ?
3.2 Est-ce qu'on utilise un méchanisme quelconque pour améliorer Minimax ? Lequel ?
3.3 Quels sont les heuristiques utilisés pour évaluer un état du jeu ?
Aide: un 'checker' est un 'pion' en anglais, un 'King' est une 'Dame'.
4. Systèmes experts
Il s'agit d'utiliser un des systèmes experts disponibles ici .
Choisir par example, l'expert Whale Watcher qui vous aidera déterminer l'espèce de baleine que vous avez observé lors de votre dernier voyage au Canada, ou bien l'expert Spa Advisor, qui vous informera sur les possibles causes des problèmes que vous avez avec votre Jacuzzi.
5. Eliza
Il s'agit simplement de faire une séance avec la thérapeute Eliza , originalement développée dans les années 60 (en anglais). Aujourd'hui, on parle de "chat bots", des programmes sachant (théoriquement) soutenir une conversation courante. On vise leur utilisation comme présentateurs des sites web d'entreprises, pour donner des informations, dans les "help desks".
Clicker ici pour demander des informations (conseil) à une hôtesse virtuelle chez IKEA-France.
Clicker ici pour discuter avec Jack the ripper (Jack l'Eventreur). Sans doute le plus célebre de tous les tueurs en série.