Cours de DataScience & IA PDF

DataScience & IA Christophe Rodrigues Plan du cours Recherche en présence d’un adversaire - Liens avec les cours précédents - Exemple de jeu avec adversaire - Algorithme MiniMax - Elagage Alpha-Beta - Exemples historiques 2 Rappel Algorithme génétique Fouille de données A...

DataScience & IA Christophe Rodrigues Plan du cours Recherche en présence d’un adversaire - Liens avec les cours précédents - Exemple de jeu avec adversaire - Algorithme MiniMax - Elagage Alpha-Beta - Exemples historiques 2 Rappel Algorithme génétique Fouille de données A* Programmation par contraintes 3 Exemple : Jeu du morpion 4 Définitions Joueurs : Max et Min s0 : état initial Actions(s) : retourne l’ensemble des mouvements possibles dans un état Result(s,a) : retourne l’état résultat de l’action a dans l’état s Terminal-test(s) : vrai si le jeu est terminé, faux autrement Utility(s,j) : retourne la valeur finale du jeu pour le joueur j dans l’état s. 5 Exemples de Complexités d’arbres de jeux (#noeuds) Jeu de morpion : 10^5 Othello : 10^58 Jeu d’échecs : 10^123 Jeu de Go : 10^360 6 MiniMax 7 Elagage Alpha-Beta 8 Elagage Alpha-Beta 9 Deep Blue (jeu d’échecs) Premier ordinateur à battre le champion du monde au jeu d’échecs Garry Kasparov en 1997 Composé de 30 nœuds de 120 MHz avec 480 circuits dédiées aux éches En 1997 Deep Blue faisait partie des super-calcultateurs du top500 mondial Utilisait un élagage alpha-beta ainsi qu’un dictionnaire d’ouverture et de fermeture 10 TD-Gammon (Jeu de Backgammon) Premier programme à atteindre un niveau proche des meilleurs joueurs humains en 1992 Combinaison d’apprentissage par renforcement et d’apprentissage de réseaux de neurones Apprentissage complètement automatique contre lui-même. Converge après 1 500 000 de parties A permis de découvrir de nouvelles stratégies inconnues des joueurs 11 AlphaGo (jeu de Go) Bat le meilleur joueur humain en 2017 Apprentissage en deux étapes : d’abord entraîné en apprenant à partir de parties humaines Ensuite contre lui-même AlphaGo Zero : une nouvelle version apprenant uniquement à partir des règles AlphaZero : Une nouvelle version capable de jouer aux échecs, au Go et au Shogi battant tous les meilleurs programmes dans les 3 types de jeu. 12