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?
- Elagage Alpha-Beta (correct)
- Programmation par contraintes
- Algorithme génétique
- Fouille de données
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?
- Peut se terminer avant que tous les mouvements soient effectués
- Dépend uniquement des mouvements de Max
- Toujours un match nul
- Peut être soit une victoire pour Max ou Min (correct)
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?
- 10^100
- 10^123
- 10^360 (correct)
- 10^58
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?
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é?
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?
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?
Quelle caractéristique distingue AlphaZero des autres programmes de jeu?
Quelle caractéristique distingue AlphaZero des autres programmes de jeu?
Flashcards
Jeu à adversaire
Jeu à adversaire
Un jeu où deux joueurs s'affrontent pour atteindre un objectif spécifique, les mouvements étant déterminés par des règles strictes.
Algorithme MiniMax
Algorithme MiniMax
Un algorithme qui permet de trouver le meilleur mouvement possible pour un joueur dans un jeu à adversaire, en évaluant tous les mouvements possibles et en choisissant celui qui maximise ses chances de gagner.
Elagage Alpha-Beta
Elagage Alpha-Beta
Une technique d'optimisation de l'algorithme MiniMax qui permet d'éliminer certaines branches de l'arbre de recherche, réduisant ainsi le temps de calcul.
État initial (s0)
État initial (s0)
Signup and view all the flashcards
Actions(s)
Actions(s)
Signup and view all the flashcards
Result(s,a)
Result(s,a)
Signup and view all the flashcards
Terminal-test(s)
Terminal-test(s)
Signup and view all the flashcards
Utility(s,j)
Utility(s,j)
Signup and view all the flashcards
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.
