Recherche adversariale et jeux
La recherche adversariale est l'étude de la prise de décision dans des contextes compétitifs, où un agent doit choisir des coups dans un arbre de jeu face à un adversaire qui tente d'atteindre le résultat opposé.
Definition
La recherche adversariale calcule un coup pour un joueur en explorant un arbre de jeu dans lequel les joueurs alternent leurs tours, en utilisant le principe minimax (chaque joueur optimise en supposant que l'adversaire joue de manière optimale) conjointement avec l'élagage et l'évaluation heuristique pour gérer les grands arbres.
Scope
Ce sujet couvre la recherche dans les jeux à deux joueurs, à somme nulle et à information parfaite : la règle de décision minimax, l'élagage alpha-bêta qui permet à minimax de sauter des branches manifestement non pertinentes, les fonctions d'évaluation et la recherche à profondeur limitée pour les jeux trop vastes pour être résolus exactement, ainsi que la recherche arborescente Monte Carlo pour les jeux avec des facteurs de branchement très importants. Il aborde la modélisation des arbres de jeu et la manière dont les limites computationnelles imposent des coupures heuristiques. Il ne couvre pas l'analyse générale de l'équilibre en théorie des jeux des incitations multi-agents, qui est traitée dans les systèmes multi-agents.
Core questions
- Comment la règle minimax détermine-t-elle un coup optimal contre un adversaire optimal ?
- Comment l'élagage alpha-bêta élimine-t-il des branches sans affecter la valeur minimax ?
- Comment les fonctions d'évaluation sont-elles utilisées pour limiter la recherche à une profondeur fixe dans les grands jeux ?
- Quand la recherche arborescente Monte Carlo est-elle préférable au minimax à profondeur limitée ?
Key concepts
- arbre de jeu
- valeur minimax
- élagage alpha-bêta
- fonction d'évaluation (heuristique)
- recherche à profondeur limitée et effet d'horizon
- jeux à somme nulle et à information parfaite
- recherche arborescente Monte Carlo
- ordonnancement des coups
Key theories
- Règle de décision Minimax
- Dans un jeu à somme nulle à deux joueurs, chaque joueur choisit le coup qui maximise son propre résultat minimum garanti ; la propagation de ces valeurs max/min vers le haut de l'arbre de jeu donne le coup optimal à la racine.
- Élagage alpha-bêta
- En suivant les meilleures valeurs déjà garanties aux joueurs maximisant et minimisant, la recherche alpha-bêta prouve que certains sous-arbres ne peuvent pas affecter la décision finale et les ignore, renvoyant la valeur minimax exacte tout en multipliant par deux, dans le meilleur des cas, la profondeur atteignable dans un temps donné.
- Recherche arborescente Monte Carlo
- Lorsque les facteurs de branchement sont trop importants pour une exploration exhaustive, la recherche arborescente Monte Carlo construit un arbre asymétrique guidé par des déroulements aléatoires et une règle de sélection équilibrant exploration et exploitation, une méthode qui a transformé le jeu informatique dans des jeux tels que le Go.
Clinical relevance
La recherche adversariale a produit des systèmes d'IA marquants, des moteurs d'échecs utilisant la recherche alpha-bêta aux programmes de Go basés sur la recherche arborescente Monte Carlo, et les mêmes techniques éclairent la négociation automatisée, les jeux de sécurité et tout contexte modélisé comme une compétition entre parties optimisantes.
History
L'article de Shannon de 1950 a formulé les échecs informatiques comme une recherche minimax avec une fonction d'évaluation, et le théorème minimax de von Neumann a fourni les fondements théoriques des jeux. L'élagage alpha-bêta a été développé dans les années 1950-1960 et analysé rigoureusement par Knuth et Moore (1975). La recherche arborescente Monte Carlo, formalisée dans les années 2000, a entraîné le prochain bond en avant dans la force de jeu, en particulier au Go.
Key figures
- Claude E. Shannon
- John von Neumann
- Arthur Samuel
- Donald E. Knuth
- Ronald W. Moore
Related topics
Seminal works
- shannon1950
- knuth1975
- browne2012
Frequently asked questions
- L'élagage alpha-bêta modifie-t-il le coup que minimax choisirait ?
- Non. L'élagage alpha-bêta renvoie exactement la même valeur et le même coup que le minimax complet ; il évite seulement d'explorer les branches qui ne peuvent manifestement pas influencer le résultat. Son avantage est la vitesse, et avec un bon ordonnancement des coups, il peut explorer environ deux fois plus profondément dans le même laps de temps.
- Pourquoi utiliser la recherche arborescente Monte Carlo plutôt que le minimax dans des jeux comme le Go ?
- Le Go a un facteur de branchement énorme et manque d'une fonction d'évaluation simple et précise, de sorte que le minimax à profondeur fixe est inefficace. La recherche arborescente Monte Carlo estime plutôt la qualité des coups à travers de nombreuses simulations aléatoires et développe l'arbre de manière sélective vers des lignes prometteuses, ce qui s'adapte bien mieux dans de tels jeux.