Séance de cours

Connect quatre: α-β Taille vs Monte-Carlo Tree Search

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Description

Cette séance de cours présente l'application de la théorie du jeu pour résoudre Connect Four en utilisant l'algorithme minimax, optimisé avec la taille α-β, et comparé avec l'algorithme de recherche de l'arbre Monte-Carlo. La séance de cours porte sur la motivation, les principes et l'analyse de la performance de ces stratégies, et se termine par des remerciements.

Cette vidéo est disponible exclusivement sur Mediaspace pour un public restreint. Veuillez vous connecter à Mediaspace pour y accéder si vous disposez des autorisations nécessaires.

Regarder sur Mediaspace

Source officielle

Concepts associés (8)

Élagage alpha-bêta

En informatique, plus précisément en intelligence artificielle et en théorie des jeux, l’élagage alpha-bêta (abrégé élagage αβ) est une technique permettant de réduire le nombre de nœuds évalués par l'algorithme minimax. Il est utilisé dans des programmes informatiques qui jouent à des jeux à 2 joueurs, comme les échecs ou les dames. L'algorithme minimax effectue une exploration complète de l'arbre de recherche jusqu'à un niveau donné. L'élagage alpha-beta permet d'optimiser grandement l'algorithme minimax sans en modifier le résultat.

Algorithme minimax

L'algorithme minimax (aussi appelé algorithme MinMax) est un algorithme qui s'applique à la théorie des jeux pour les jeux à deux joueurs à somme nulle (et à information complète) consistant à minimiser la perte maximum (c'est-à-dire dans le pire des cas). Pour une vaste famille de jeux, le théorème du minimax de von Neumann assure l'existence d'un tel algorithme, même si dans la pratique il n'est souvent guère aisé de le trouver.

Théorie des jeux

La théorie des jeux est un domaine des mathématiques qui propose une description formelle d'interactions stratégiques entre agents (appelés « joueurs »). Les fondements mathématiques de la théorie moderne des jeux sont décrits autour des années 1920 par Ernst Zermelo dans l'article , et par Émile Borel dans l'article . Ces idées sont ensuite développées par Oskar Morgenstern et John von Neumann en 1944 dans leur ouvrage qui est considéré comme le fondement de la théorie des jeux moderne.

Théorie des jeux combinatoires

La théorie des jeux combinatoires est une théorie mathématique qui étudie les jeux à deux joueurs comportant un concept de position, et où les joueurs jouent à tour de rôle un coup d'une façon définie par les règles, dans le but d'atteindre une certaine condition de victoire. La théorie des jeux combinatoires a pour objet les jeux à information complète où le hasard n'intervient pas, comme les échecs, les dames ou le jeu de go.

Jeu coopératif (théorie des jeux)

En théorie des jeux, un jeu coopératif est un jeu tel que les joueurs ont la possibilité de se concerter et de s'engager à coopérer avant de définir la stratégie à adopter. À deux joueurs et deux stratégies avec une matrice des gains de la forme : où , , et . Des joueurs rationnels vont coopérer sur l'une ou l'autre des stratégies et recevoir les gains élevés. Pour ce faire, ils doivent pouvoir se coordonner sur l'une ou l'autre des stratégies, sous peine de se retrouver dans une situation défavorable.

Afficher plus

Séances de cours associées (27)

Introduction à la théorie des jeux

Couvre les fondamentaux de la théorie des jeux, l'équilibre de Nash et les interactions stratégiques dans les systèmes multi-agents.

Jeux de Markov: Concepts et applications dans l'apprentissage par renforcement

Couvre les jeux de Markov, leur dynamique, leurs équilibres et leurs applications dans l'apprentissage par renforcement.

Théorie des jeux: Stackelberg et Induction en arrière

Discute des jeux Stackelberg et de l'induction en arrière, illustrant les concepts de la théorie des jeux à travers des exemples et des applications dans des scénarios réels.

Séparer les hyperplans : théorie et applications

Explore la séparation des hyperplans pour deux ensembles X et Y, en discutant des conditions de séparation et des implications de la convexité.

Jeux potentiels: Dynamiques et équilibres de la meilleure réponse

Couvre les jeux potentiels, leurs propriétés et la convergence des dynamiques de meilleure réponse aux équilibres de Nash.

Afficher plus

Concepts associés (8)

Élagage alpha-bêta

Algorithme minimax

Théorie des jeux

Théorie des jeux combinatoires

Jeu coopératif (théorie des jeux)

Afficher plus