Discussion :

[xokami35x]

Bonjour, dans le cadre d'un TPE, je dois faire des recherches sur l'utilisation de l'intelligence artificielle dans les jeux vidéos.
J'aurai aimé avoir quelques renseignements, après avoir lu pas mal de sujets sur le forum:

Premièrement, j'aurai aimé savoir quelle est la différence entre L'IA symbolique et L'IA située, car bien que j'ai vu ces deux notions sur wiki, je n'ai trouvé aucune informations précises la dessus.

Ensuite, est ce que quelqu'un a des sources d'un jeu(dames, morpion...) simple, qui utilise l'intelligence artificielle, c'est à dire basé sur une base de connaissances avec apprentissage, et qu'il voudrait bien partager?
Biensur, bien que qu'ayant quelques notions de programmation(en Java particulièrement, avec quelques bases en C/C++ et php), je ne m'attends pas à comprendre tout le code, peut être juste des petis bouts, si ils sont commentés.

Merci d'avance pour vos réponses

[seeme]

Bonjour,

L'IA symbolique manipule des symboles, elle ne sait pas à quoi il correspondent mais connais les règles pour passer d'un état à un autre, comparer les symboles.

Exemple, dans une machine à états finis d'un ennemi dans un jeu, pour le jeu, les états "Attaque", "Idle", "Demander de l'aide" n'ont pas plus de sens que "Purée", "Courge" et "Plante verte". Ce sont des symboles, et c'est l'Homme qui va leur attribuer un sens.

L'IA située utilise l'expérience, elle évolue en partant d'un état ou d'une base de connaissance pour converger vers une solution (l'expertise Humaine intervient très peu).

Plus que des sources, je pense que ce serait plus payant pour toi (et pour ta note de TPE) d'explorer un algorithme (pourquoi pas d'en dérouler les étapes lors de ton exposé).

Par exemple, les algorithme AlphaBeta et MinMax sont simples, très utilisés et permettent de résoudre des problèmes simples comme le morpion (tu ne vas pas passer 2 heures à expliquer l'énoncé du problème à ton jury)..

Pour les algorithme évolutionnaires, les plus simples (d'après moi) sont le génétique et peut-être le tabou. Si tu veux aller vers de penchants plus mathématiques intéresse toi aux réseaux de neurones (moins évident pour le néophyte je trouve).

Conseil: insiste bien sur la complexité des problèmes (en application numérique, amuses toi à calculer le nombre de solution d'un morpion de dimension N), définis et illustre des problèmes NP complets (ne te lances pas dans la démonstration qu'un problème est NP complet, je ne pense pas que ce soit de ton niveau...)

Si tu as besoin de plus de détails, n'hésite pas.

[Aleph69]

Bonjour,

si tu veux éventuellement enrichir ton TPE d'exemples d'application, tu peux regarder du côté des tournois homme contre machine.

Aux échecs, il y a plusieurs rencontres avec Kasparov qui a finalement fini par perdre. La machine est capable de prévoir un nombre impressionnant de coups à l'avance mais c'est purement calculatoire. L'apprentissage se situe plus au niveau de sa capacité à reproduire des enchaînement de mouvement historiques à partir de sa base de données.

Au texas holdem poker, des rencontres de heads-up ont également eu lieu. La machine adopte une approche probabiliste et apprend le "profil" de son adversaire au fur et à mesure des coups. Il y a aussi des étapes d'optimisation, notamment pour décider de jouer/relancer/coucher une main en fonction du pot, du tapis et des cartes.

Tu peux peut-être aussi regarder du côté des tournois de robots (matchs de foot, duels, etc).

[Aleph69]

Regarde également la page wilkipedia et la bibliographie associée :
http://fr.wikipedia.org/wiki/Intelli...eux_vid.C3.A9o

Au passage, il me semble indispensable que tu parles des travaux d'Alan Turing dans ton TPE (au moins en le citant dans une chronologie).

[Aleph69]

Concernant l'IA symbolique et l'IA située :

- l'IA symbolique correspond aux formes d'intelligence qu'on pouvait trouver dans les premiers jeux vidéos : elle formulée sous forme de règles et n'évolue pas en fonction de ta manière de jouer.

-l'IA située correspond aux formes d'intelligence qui peuvent s'adapter aux situations, c'est-à-dire qui évoluent en fonction de ton comportement dans le jeu.

En gros, la première est une intelligence statique et l'autre une intelligence dynamique.

[Clercq]

Il n'ai pas evident d'etre precis sur ces concept, et certain petit detail peuvent titiller.

En gros, la première est une intelligence statique et l'autre une intelligence dynamique.

Compartimenter IA symbolique dans la case "statique", et l'IA située dans la case dynamique est restrictif, et même faux. L'IA symbolique peut être vu comme la phase de restitution de l'information du processus de la mémoire.

L'IA symbolique manipule des symboles, elle ne sait pas à quoi il correspondent mais connais les règles pour passer d'un état à un autre, comparer les symboles.

Exemple, dans une machine à états finis d'un ennemi dans un jeu, pour le jeu, les états "Attaque", "Idle", "Demander de l'aide" n'ont pas plus de sens que "Purée", "Courge" et "Plante verte". Ce sont des symboles, et c'est l'Homme qui va leur attribuer un sens.

En effet, l'IA symbolique manipule des symbole, car ces symbole sont la manière dont est stocké l'information. A partir de règle et de la base de connaissance on en déduit un résultat.
Mais comme dans la vrai vie, un symbole n'a que la signification que l'on veut bien lui donner. Il ne faut pas voir ça comme une faiblesse de ce genre d'IA.

L'IA située utilise l'expérience, elle évolue en partant d'un état ou d'une base de connaissance pour converger vers une solution (l'expertise Humaine intervient très peu).

Oui et non, l'IA située contient les RdNs, qui nécessite des données étiquetés, qui proviennent bien d'une expertise humaine. Dans le domaine du jeux on peut le voir autrement, les données étiqueté provenant directement de la façon de jouer.

Les deux IA on des forces différentes. Dans le cas d'un jeux comme les échecs, il va être compliquer de stocker de l'information avec de l'IA situer, on va plutôt utiliser une IA symbolique. Par contre, s'il s'agit de retrouver un objet dans une scène une IA située sera plus appropriée.

Apres t'avoir bien embrouiller le cerveaux, je te dirais que les deux IA on des concept très différents, et que l'une ne peut remplacer l'autre (c'est une prise de position personnelle).
Elles proviennent de granularité différentes pour représenter le grossièrement le fonctionnement du cerveaux (stockage/utilisation de l'information).

[Aleph69]

Bonjour,

Oui et non, l'IA située contient les RdNs, qui nécessite des données étiquetés, qui proviennent bien d'une expertise humaine.

Les réseaux de neurones (RdNs) ne nécessitent pas nécessairement d'avoir des données étiquetées. Il existe des RdNs spécialisés dans l'apprentissage non supervisé (cartes de Kohonen). De plus, les données étiquetées ne proviennent pas nécessairement d'une expertise humaine mais peuvent être obtenues à partir d'un algorithme de clustering.

[Clercq]

Les réseaux de neurones (RdNs) ne nécessitent pas nécessairement d'avoir des données étiquetées. Il existe des RdNs spécialisés dans l'apprentissage non supervisé (cartes de Kohonen). De plus, les données étiquetées ne proviennent pas nécessairement d'une expertise humaine mais peuvent être obtenues à partir d'un algorithme de clustering.

Je m'incline.
Tout dépends du domaine et du RdN utilisé, on ne peut pas généraliser (dans un sens ou dans l'autre). J'avoue tout de suite penser feed-forward quand j'entends RdN, c'est une erreur de ma part.

[xokami35x]

Déjà merci à tous pour vos réponses, excusez moi pour le temps de réponse.
Je vais aller me renseigner sur tout ça, et relire tout ce que vous m'avez dit(oui c'est assez complexe comme sujet...)
J'aurai surement d'autres questions.
encore merci

Edit: Alors j'ai trouvé un super site expliquant l'algo de minmax et donnant un exemple de code, cependant, peut on classer cet algo dans l'IA située ou symbolique?

De plus, sur le site: http://www.grappa.univ-lille3.fr/~to...ielle/jeux.php
Il parle au tout début de profondeur de noeuds, à quoi cela correspond?
Puis à un moment, il dit "on fait remonter les évaluations depuis les feuilles jusqu'à la racine (en bleu les noeuds où l'on maximise, en vert les noeuds où l'on minimise)"
C'est à dire minimiser, maximiser? J'ai un peu de mal sur cette étape.

Merci d'avance

[Clercq]

De plus, sur le site: http://www.grappa.univ-lille3.fr/~to...ielle/jeux.php
Il parle au tout début de profondeur de noeuds, à quoi cela correspond?

Certain jeux (comme le morpion, les dames ...) peuvent être développé sous forme d'arbre représentant les coup possible, alternativement des joueurs A et B.
Les algorithmes en profondeur d'abord parcours l'arbre ...vers le fond. En gros, on prends un noeud et on développe de successeur en successeur. Arrivé au bout d'une branche on revient au père (noeud précèdent) et on recommence le parcours avec le second successeur s'il existe sinon on remonte au père précèdent ... Ce jusqu’à trouver une solution (si elle existe).

Puis à un moment, il dit "on fait remonter les évaluations depuis les feuilles jusqu'à la racine (en bleu les noeuds où l'on maximise, en vert les noeuds où l'on minimise)"
C'est à dire minimiser, maximiser? J'ai un peu de mal sur cette étape.

Dans un jeux comme le morpion, on peut voir que l’intérêt d'un joueur A est de maximiser ses gains (son score), et le but de l'adversaire B est de minimiser les gains de A.
Dans un algorithme tels que le minimax, on part de la fin du jeux (on a préalablement développé les coups possibles). Pour le joueur A, pour chaque coup ultime, on va choisir ceux qui maximise ses gains, ensuite pour le joueur B (adversaire de A), on va choisir les coup qui minimise les gains max de A ...

[xokami35x]

Ok merci beaucoup pour ta réponse, je pense avoir compris^^

Quand tu parles d'une solution, c'est en fait un coup gagnant?

[seeme]

Ca dépend à quel niveau tu te places.

Pour moi, une solution, c'est une suite de coup qui mênent à la victoire (où la défaite la moins pire)..

Tu peux voir à un autre niveau et dire qu'une solution c'est un coup.

Tout dépend de la formalisation du problème.

[Clercq]

Comme le dis seeme on peut le voir de plusieurs façon.

Pour moi, ça dépends plus du jeu. Dans un jeu tels que le morpion 'normal', il existe forcement un coup final gagnant (on deroule tout les coup possible).

Par contre on peut imaginer un morpion ou des pièces ont déjà été posées. Dans ce cas peut être qu'il n'existe plus de coup gagnant, donc pas de solution.

Enfin tu peux imaginer un jeu ou le but est de 'faire' des points, dans ce cas il n'y a plus vraiment 'Le' coup gagnant, mais plusieurs solutions gagnantes (ou pas -> perte de point (argent ? )).

D'ou l'utilisation générale de 'solution'.

[xokami35x]

Ok merci pour ces précisions

[xokami35x]

Alors voila, j'ai terminé la partie avec le minmax, en suivant vos conseils, en insistant sur la complexité des problèmes ect

Maintenant j'aimerai survoler les algorithme d'IA située

Pour les algorithme évolutionnaires, les plus simples (d'après moi) sont le génétique et peut-être le tabou. Si tu veux aller vers de penchants plus mathématiques intéresse toi aux réseaux de neurones (moins évident pour le néophyte je trouve).

Je n'ai trouvé aucun site parlant de tabou précisément. Connaitreriez vous des sites expliquant rapidement le fonctionnement d'un algorithme evolutionnaire?

Merci d'avance

[seeme]

En général, un algorithme évolutionnaire a pour but de faire évoluer une solution (ou une population de solutions) vers une meilleure solution (resp. population).

Je vais t'expliquer les principes généraux.

-> Algorithme génétique:
* On part d'une solution initiale (générée aléatoirement par exemple).
* On va avoir une phase de sélection. On ne sélectionne pas nécessairement que les meilleures solution, il faut garder en tête qu'il faut de tout pour faire un monde, et qu'une mauvaise solution pourrait être à la base d'une excelente solution plus tard. Cette phase s'appelle aussi phase de compétition ou de reproduction.
* On va croiser une partie des individus pour en obtenir de nouveaux.
* Ensuite, on va muter une partie de la population, en la modifiant (légèrement).
* Et on recommence pour un nombre d'itérations ou un temps donné.

L'exemple le plus simple serait des chaines binnaires, que tu peux voir comme une chaine ADN. Pour la sélection, on pourrait par exemple garder le premier tiers des individus et le mélanger avec le dernier quart (je dis complètement au hasard). Pour les croisements, on peut par exemple mélanger deux chaines:

0110101100 x 1001001000 = 0110001000 et 1001101100

(on peut faire une nouvelle phase de sélection et ne conserver qu'une partie des fils).

Finalement, pour la mutation, on peut par exemple inverser un bit, ou en swapper 2.

Et on recommence.

Il y a quelques points clef ici. Un point CRUCIAL pour ce genre d'algorithme est l'heuristique qui sera employée pour juger de la qualité d'une solution. Une mauvaise heuristique va tout plomber.

De plus, il s'agit du principe général de l'algorithme. On peut faire un peu ce qu'on veut pour la sélection, la mutation et les croisement, il faut essayer diverses solutions et combinaisons pour affiner. On peut aussi maintenir une population archive, faire de l'eugénisme etc...

Un de mes profs disait que ce genre d'algorithme, c'est 30 minutes à coder, 3 mois à configurer.

-> Recherche Tabou
si tu te représentes l'espace des solutions comme ça:




En A, tu as le minimum global, la meilleure solution de l'espace de recherche. Le risque, c'est que si on y prend pas garde, si on recherche autour d'une solution (c'est ce que fait la mutation, on dit que l'on fait une recherche locale), on risque de se retrouver coincé en B, un optimum local de l'espace de recherche. Du coup l'algorithme va avoir tendance à bloquer ici.

C'est là qu'intervient la recherche tabou. La recherche tabou consiste à partir d'une solution, et à en explorer le voisinage en tenant à jour une liste tabou qui correspond aux mouvements déjà effectués. Par exemple, on peut se souvenir que l'on a déjà inversé le bit i. Ce mouvement devient tabou pendant une durée donnée.

Ce système force l'exploration vers d'autres solutions et permet de se sortire d'un optimum.

Tu peux aussi regarder l'algorithme du kangourou ou du hill climbing qui peuvent être utilisé pour la recherche de voisinage.

-> Recuit simulé:
Cet algorithme s'inspire du monde des forges. L'idée c'est que quand on chauffe un métal, on augmente l'energie qu'il contient. Si on veut le métal le plus dur possible, il faut faire tomber cette énergie à zéro. Pour arriver à ça, les forgerons utilisent la méthode du recuit. On chauffe le metal jusqu'à une certaine température, puis on le refroidit un peu. On le réchauffe un peu et on recommence jusqu'à ce que la temperature soit la bonne.

Par exemple, on chauffe jusqu'à 200°, on refroidit jusqu'à 180°, on réchauffe jusqu'à 190° et ainsi de suite.

C'est la même chose pour l'algorithme: on prend une solution pas top, on l'ameliore un peu, on réintroduit de l'entropie (du bordel quoi), sans que la solution devienne pire qu'avant, et on recommence.

Exemple avec le sudoku.

On prend pour heuristique le nombre d'erreurs que contient la grille.

La solution initiale pourrait être une grille aléatoire.
On compte les erreurs (on peut aussi les pondérer) et on a une heuristique de 20 (au pif).
On va prendre un chiffre et le modifier pour essayer d'améliorer la solution. On arrive à une heuristique de 17 (on a "refroidis").
On va rajouter un peu d'entropie en prenant deux ou trois nombres et en les changeant pour d'autres valeures aléatoires. On arrive à une heuristique à 18.

Note qu'il y a des équations pour savoir plus précisement où l'on va


-> Enfin, il faut bien comprendre que l'on peu mélanger ces algorithmes entre eux. On peut ainsi fair eun algorithme génétique avec une étape de recherche locale avec un tabou par exemple.

C'est un domaine extrêment vaste et un peu vague...

[xokami35x]

Ouahhh merci de cette réponse ultra complète, et merci beaucoup du temps que tu m'accordes, c'est super sympa.

Va falloir que je relise ça plusieurs fois. J'ai un peu tiqué sur un mot: heuristique, j'ai été voir sur wikipedia

une heuristique est un algorithme qui fournit rapidement (en temps polynomial) une solution réalisable, pas nécessairement optimale

Je ne comprends pas ce que tu veux dire par

On prend pour heuristique le nombre d'erreurs que contient la grille

Si c'est une notion trop complexe, ne prend pas trop de temps pour me l'expliquer.

En tout cas vraiment merci

[seeme]

Ce n'est pas complexe du tout.

On va faire simple avec l'exemple d'A*.

Sans rentrer dans les détails, A* est un algo de recherche de plus court chemin dans un graph. Seulement, pour fonctionner, on a besoin à un moment de savoir si on se rapproche plus ou moins de l'endroit où on veut aller.

Pour ça, il faut trouver une heuristique, un moyen simple, rapide et le plus représentatif possible de la distance.

On peut par exemple prendre la distance à vol d'oiseau entre là où tu es et là où tu veux aller. C'est simple à calculer (distance de Manhattan), ça donne une assez bonne idée de la distance qu'il reste à faire (note q'il existe d'autres solutions qui pourront donner des meilleurs résultats ou des moins bon).

Trouver la bonne heuristique est un art!

Toute la subtilité est là. Il faut trouver un moyen d'évaluer une solution au problème, mais si tu passes plus de temps à faire ça qu'à faire progresser ta solution, c'est assez inutile.

Donc, pour résumer (en fait c'est pas si simple que ça à expliquer..), une heuristique, il faut voir ça comme un moyen simple et efficace d'évaluer la solution (en temps polynomial d'après wikipedia, il faut comprendre que si on met 3 heures à évaluer une solution calculée en 3 minutes, il y a peut-être un problème), et plus généralement, une heuristique c'est une solution simple et efficace pour avoir une estimation de quelque chose.

Pour l'exemple du sudoku, si on compte le nombre d'erreurs dans la grille (même nombre dans une ligne, une colonne ou une zone), on a un nombre calculé très simplement (en temps polynomial en plus) qui donne une bonne idée de la qualitée de la solution -> nombre élevé = beaucoup d'erreur => mauvaise solution, nombre bas -> peu d'erreur => plutôt bonne solution.

Note qu'une heuristique peut-être une fonction à minimiser (ici le nombre d'erreur) ou à maximiser (dans un problème de planning, augmenter l'argent économisé par exemple).

N'hésite pas à demander si tu as besoin de précisions.

[xokami35x]

Encore une réponse très complète, merci beaucoup.
Je me plonge là dedans, et je reposte si il y a un truc avec lequel j'ai du mal.

Encore merci

[xokami35x]

Alors, après relecture, j'ai bien compris le principe d'heuristique.
Cependant, il reste une question au niveau du principe de l'algorithme génétique

* On part d'une solution initiale (générée aléatoirement par exemple).

Je ne comprends pas trop ce que tu appelles solution

edit: Peut on classer les algorithme evolutionnaire dans une des deux familles de l'IA?(située ou symbolique)