Podcast
Questions and Answers
Quel algorithme est principalement utilisé dans le jeu d'échecs pour réduire le nombre de mouvements à évaluer?
Quel algorithme est principalement utilisé dans le jeu d'échecs pour réduire le nombre de mouvements à évaluer?
Quel est l'état final d'un jeu dans le cas du jeu du morpion?
Quel est l'état final d'un jeu dans le cas du jeu du morpion?
Quelle est la complexité du jeu de Go en termes de noeuds d'arbres de jeux?
Quelle est la complexité du jeu de Go en termes de noeuds d'arbres de jeux?
Quel programme a été le premier à atteindre un niveau proche des meilleurs joueurs humains au Backgammon?
Quel programme a été le premier à atteindre un niveau proche des meilleurs joueurs humains au Backgammon?
Signup and view all the answers
Quel est le rôle de l'utilité dans un état de jeu pour un joueur donné?
Quel est le rôle de l'utilité dans un état de jeu pour un joueur donné?
Signup and view all the answers
Quelle est la principale méthode d'apprentissage utilisée par AlphaGo Zero?
Quelle est la principale méthode d'apprentissage utilisée par AlphaGo Zero?
Signup and view all the answers
Quelle technologie a été utilisée par Deep Blue pour battre Garry Kasparov?
Quelle technologie a été utilisée par Deep Blue pour battre Garry Kasparov?
Signup and view all the answers
Quelle caractéristique distingue AlphaZero des autres programmes de jeu?
Quelle caractéristique distingue AlphaZero des autres programmes de jeu?
Signup and view all the answers
Study Notes
Plan du Cours - Recherche en présence d'un adversaire
- Liens établis avec les cours précédents
- Exemple de jeu avec adversaire illustré (ex: morpion)
- Algorithme MiniMax détaillé
- Elagage Alpha-Beta détaillé
- Exemples historiques de jeux (morpion, Othello, échec, Go)
Rappel
- Algorithme génétique
- Fouille de données
- Algorithme A*
- Programmation par contraintes
Exemple : Jeu du morpion
- Démonstration d'un arbre de jeu avec les mouvements de MAX et MIN.
- Affichage des états terminaux et des utilités associées (valeurs de gain).
Définitions
- Joueurs : MAX et MIN
- s0 : état initial
- Actions(s) : ensemble des mouvements possibles à partir de l'état s
- Result(s,a) : état résultant de l'action a dans l'état s
- Terminal-test(s) : vrai si le jeu est terminé, faux sinon
- Utility(s,j) : valeur finale du jeu pour le joueur j dans l'état s.
Exemples de Complexités d'arbres de jeux (#noeuds)
- Jeu de morpion : environ 10^5 noeuds.
- Othello : environ 10^58 noeuds.
- Jeu d'échecs : environ 10^123 noeuds.
- Jeu de Go : environ 10^360 noeuds.
MiniMax
- Formule de MiniMax
- Illustration graphiquement sur l'arbre de jeu
- Calcul de la meilleure stratégie pour un joueur (MAX ou MIN).
Elagage Alpha-Beta
- Illustration graphique de l'élagage (coupe alpha et bêta) sur l'arbre de jeu, illustrant les cas où la valeur est inférieure à un seuil, ou supérieur à un autre.
- Explication de l'algorithme d'élagage Alpha-Beta pour réduire la recherche dans l'arbre.
Deep Blue (jeu d'échecs)
- Premier ordinateur à battre le champion du monde Garry Kasparov en 1997.
- Composé de 30 nœuds de 120 MHz avec 480 circuits dédiés aux échecs.
- Faisait partie des supercalculateurs dans le top 500 mondial.
- Utilisait l'élagage alpha-bêta et un dictionnaire d'ouvertures/fermetures.
TD-Gammon (Jeu de Backgammon)
- Premier programme à atteindre le niveau des meilleurs joueurs humains en 1992.
- Apprentissage complètement automatique (jeu contre lui-même).
- Apprentissage par renforcement et par réseaux de neurones
- Convergence après 1 500 000 parties.
- Découverte de nouvelles stratégies par l'apprentissage.
AlphaGo (jeu de Go)
- Bat le meilleur joueur humain en 2017.
- Apprentissage en deux étapes (d'abord entraînement sur les parties humaines, puis apprentissage contre lui-même).
- AlphaGo Zero : apprentissage uniquement à partir des règles.
- AlphaZero : une version jouant aux échecs, Go et Shogi, battant les meilleurs programmes dans ces trois jeux.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Related Documents
Description
Ce quiz explore les concepts de recherche dans des environnements avec adversaires, en se concentrant sur des algorithmes comme MiniMax et Alpha-Beta. Il inclut des exemples de jeux classiques tels que le morpion et Othello, tout en rappelant des algorithmes connexes. Testez vos connaissances sur la stratégie des jeux et la théorie des interviews adverses.
