Jeux et arbres - inf362.forge.imag.frinf362.forge.imag.fr/.../Presentation-Algorithmique-Jeux-2017-c-gz.pdf · Introduction aux stratégies [email protected] Avril 2017 Jeux

Jeux Arbres et/ou La gaufre Minimax Approximation Alpha/Beta Vrac

Jeux et arbresIntroduction aux stratégies

[email protected]

Avril 2017

1 / 27Jeux et arbres


JEUX ET ARBRES

1 Jeux

2 Arbres et/ou

3 La gaufre

4 Minimax

5 Approximation

6 Alpha/Beta

7 Vrac



PROBLÈME

Jeux de plateau (et dérivés)

◮ Jeux à 2 joueurs (joueur A et joueur B), le joueur A commence

◮ Jeu à information complète : tout est connu par les 2 joueurs◮ pas de connaissance statistique (excepté l’historique de la partie en cours)◮ pas d’information non partagée (ex : poker)◮ information = configuration du jeu à un instant donné

◮ Jeu à somme nulle◮ le gain du joueur A est égal à la perte du joueur B (et réciproquement)◮ cas de partie nulle possible (3 valeurs de gain pour le joueur A +1, 0 ou −1◮ pas de "banque" (ex : roulette)

Exemples

◮ Jeux de stratégie classiques

◮ Échecs, Dames, Marelles (moulin), Othello,...◮ Awele et variantes de jeux de semailles◮ Jeu de Go

◮ Jeux jouets◮ Tic, Tac, Toe, Marelle, jeu de Nim, Pipopipette, la gaufre,...



EXEMPLE : SAUTE-MOUTON

Description du jeu

2 3 4 51

Objectif pour le joueur rouge (resp. bleu) de placer ses 2 pions en case 4 et 5 (resp. 1 et 2).

Règles

◮ À chaque tour le joueur ne déplace qu’un seul pion.◮ Les pions rouges (resp. bleus) se déplacent vers la droite (resp. gauche).◮ Un pion se déplace en occupant la case libre si elle se trouve dans son sens de déplacement.◮ Si aucun déplacement n’est possible le joueur passe son tour.

Exemple En début de partie le joueur rouge le pion en position 1 en position 3 ou le pion enposition 2 en position 3. Si le joueur rouge place le pion 1 en position 3, le joueur bleu peutplacer son pion en position 4 en position 1 (ou son pion 5...)




Analyse du jeu

Configuration◮ la position des 4 pions◮ le trait (c’est à dire le joueur devant jouer)

Complexité◮ N taille de l’espace dans lequel évolue les configurations

N =

(5

2

)(3

2

)

× 2 = 60

◮ degré de branchement : ici 2 possibilités au plus par joueur◮ profondeur maximale (nombre maximum de 1

2 coups) : ici 6 12

Espace des configurations




Graphe du jeu

Configuration initiale

Configurations terminales

Relation : 12 coups admissibles

Propriétés du graphe◮ graphe sans circuits (fonction décroissante stricte)◮ graphe biparti (alternance des coups)◮ toutes les configurations ne sont pas accessibles : 27 configurations◮ nombre de nœuds terminaux : 4




Analyse de l’arbre des chemins




Valuation de l’arbre des chemins















JEUX ET ARBRES

1 Jeux

2 Arbres et/ou

3 La gaufre

4 Minimax

5 Approximation

6 Alpha/Beta

7 Vrac



ARBRE ET/OU

Noeud OU Noeud ET

◮ Expression booléenne

◮ Valuation des feuilles : vrai/faux

◮ Évaluation de l’arbre : parcours de l’arbre◮ profondeur/largeur d’abord◮ post-fixé : la valeur d’un nœud est calculée après l’évaluation de ses fils◮ amélioration par idempotence



ÉVALUATION DE L’ARBRE ET/OU

Évaluation_Joueur_A (configuration)Données: Configuration de jeu, c’est au joueur A de jouerRésultat: vrai si la configuration est gagnante, faux sinon (elle est perdante)if configuration = feuille

// la configuration ne permet pas de jouer, elle est gagnante ou perdante pour le joueur A

Return gagnante (configuration)

else// Le joueur A doit jouer

C=Coup (A,configuration)// C Ensemble des coups jouables par A

Valeur = fauxforall the c∈ C do

Valeur = Valeur Ou Evaluation_Joueur_B (Jeu (c,configuration))

Return Valeur









Valeur = fauxforall the c∈ C do

Valeur = Valeur Ou Evaluation_Joueur_B (Jeu (c,configuration))

Return Valeur

Évaluation_Joueur_B (configuration)Données: Configuration de jeu, c’est au joueur B de jouerRésultat: vrai si la configuration est gagnante pour A, faux sinon (elle est perdante)if configuration = feuille

// la configuration ne permet pas de jouer, elle est gagnante/perdante pour le joueur A


else// Le joueur B doit jouer

C=Coup ( B,configuration)// C Ensemble des coups jouables par B

Valeur = vraiforall the c∈ C do

Valeur = Valeur et Évaluation_Joueur_A (Jeu (c,configuration))

Return Valeur




Commentaires

◮ le joueur A et le joueur B ne sont pas symétriques

◮ jeu avec un gagnant (pas de partie nulle)

◮ parcours de tout l’arbre des parties : coût en O(bp) avec b facteur de branchement et pprofondeur de l’arbre

◮ graphe sans circuit : assure la terminaison de l’algorithme






Valeur = fauxcoup_gagnant[configuration]= ∅

forall the c∈ C doif Evaluation_Joueur_B (Jeu (c,configuration))

Valeur = vraiajouter (c, coup_gagnant[configuration])

// si coup_gagnant[configuration]) est vide faire un choix arbitraire (randomisé ou non)

Return Valeur



JEUX ET ARBRES

1 Jeux

2 Arbres et/ou

3 La gaufre

4 Minimax

5 Approximation

6 Alpha/Beta

7 Vrac



LA GAUFRE

Problème

cases

N cases

M

◮ Taille de la gaufre M × N

◮ Configuration : profil

◮ Bijection avec un vecteur de M + Nbits ayant M bits 1 et N bits 0

◮ Nombre de configurations(M+N

M

)



LA GAUFRE

Problème

M

N cases

cases





M

)



LA GAUFRE

Problème

N cases

casesM





M

)



LA GAUFRE

Problème

N cases

casesM





M

)

Gaufre 2 × 3 Nombre de configurations(5

2

)

= 10



LA GAUFRE

Problème

N cases

casesM





M

)

OR

AND

OR

OR

AND


2

)

= 10



LA GAUFRE

Problème

N cases

casesM





M

)

OR

AND

OR

OR

AND


2

)

= 10



LA GAUFRE

Problème

N cases

casesM





M

)

OR

OR

AND

AND

OR


2

)

= 10



LA GAUFRE

Problème

N cases

casesM





M

)

AND

OR

OR

OR

AND


2

)

= 10



LA GAUFRE

Problème

N cases

casesM





M

)

AND

OR

OR

OR

AND


2

)

= 10Mémoïsation et Negamax : 10 calculs !



LA GAUFRE : STRATÉGIE GAGNANTE

Étude du premier coup

Coup gagnant

Mcases

N cases

Coup perdant





Coup gagnant

Mcases

N cases

Coup perdant

Mcases

N cases





Coup gagnant

Mcases

N cases

Coup perdant

Mcases

N cases





Coup gagnant

Mcases

N cases

Coup perdant

Mcases

N cases

Le premier joueur gagne





Coup gagnant

Mcases

N cases

Coup perdant

Mcases

N cases

Le premier joueur gagne

Vol de stratégie !



JEUX ET ARBRES

1 Jeux

2 Arbres et/ou

3 La gaufre

4 Minimax

5 Approximation

6 Alpha/Beta

7 Vrac



ARBRE MINIMAX

Noeud MINNoeud MAX

◮ Valuation des feuilles dans un ensemble ordonné◮ Évaluation de l’arbre : parcours de l’arbre

◮ profondeur/largeur d’abord◮ post-fixé : la valeur d’un nœud est calculée après l’évaluation de ses fils◮ amélioration par idempotence



ARBRE MINIMAX

2 7 4

4 214

5

Noeud MAX Noeud MIN





ARBRE MINIMAX

5

4 7

7

7

1

4

52 7 4

4 21

Noeud MAX Noeud MIN





ÉVALUATION DE L’ARBRE MINIMAX

Évaluation_Joueur_A (configuration)Données: Configuration de jeu, c’est au joueur A de jouerRésultat: meilleure valeur (si B joue parfaitement)if configuration = feuille

// la configuration ne permet pas de jouer, on évalue sa valeur

Return Valeur (configuration)



Valeur = −∞

forall the c∈ C doValeur = max (Valeur,Evaluation_Joueur_B (Jeu (c,configuration)))

Return Valeur

Évaluation_Joueur_B (configuration)Données: Configuration de jeu, c’est au joueur B de jouerRésultat: valeur minimisant la perte de Bif configuration = feuille

// la configuration ne permet pas de jouer

Return Valeur (configuration)

else// Le joueur B doit jouer

C=Coup ( B,configuration)// C Ensemble des coups jouables par B

Valeur = vraiforall the c∈ C do

Valeur = min (Valeur, Évaluation_Joueur_A (Jeu (c,configuration))

Return Valeur



JEUX ET ARBRES

1 Jeux

2 Arbres et/ou

3 La gaufre

4 Minimax

5 Approximation

6 Alpha/Beta

7 Vrac



ÉVALUATION DE L’ARBRE MINIMAX

Commentaires

◮ le joueur A et le joueur B ne sont pas symétriques

◮ maximisation du gain pour A (minimisation de la perte)

◮ parcours de tout l’arbre des parties : coût en O(bp) avec b facteur de branchement et pprofondeur de l’arbre

◮ arrêt à une profondeur d’exploration fixée : évaluation heuristique

Évaluation d’une configuration

◮ choix de la fonction heuristique : LE PROBLÈME

◮ arrêt garanti

◮ pas de preuve d’optimalité



Algorithme en horizon fini

Évaluation_Joueur_A (configuration,horizon)Données: Configuration de jeu, c’est au joueur A de jouerRésultat: meilleure valeur (si B joue parfaitement)if configuration = feuille ou profondeur = 0

// la configuration ne permet pas de jouer, on évalue sa valeur

Return(Valeur (configuration)) // fonction d’évaluation si ce n’est pas une feuille



Valeur = −∞

forall the c∈ C doValeur = max (Valeur,Evaluation_Joueur_B (Jeu (c,configuration)),horizon -1)

Return Valeur

Coût de l’algorithme minimax pour évaluer une configuration

◮ dépend du facteur de branchement b ;

◮ de la profondeur choisie p ;

◮ du coût du calcul de la valeur d’une configuration C.

Coût = C(bp+1− 1)/(b − 1) ≃ Cbp



ÉVALUATION DE LA VALEUR D’UNE CONFIGURATION :APPROCHE EMPIRIQUE

Fonction du chemin emprunté pour arriver à la configuration courante.Les valeurs de configurations sont comparables.

◮ différence entre le gain cumulé de A et le gain cumulé de B

◮ estimation du meilleur gain de la configuration courante à l’objectif (cf A∗)

◮ valeur empirique d’une configuration (exemples)◮ nombre de pions / points / cases occupées-libres / tours ... comptage◮ séparation : somme de valeurs de sous-configuration + évaluation de la décomposition◮ configurations spécifiques (motifs gagnants ou forts)◮ ...

◮ Validation de la fonction valeur empirique◮ propriétés◮ test expérimentaux (faire jouer les stratégies l’une contre l’autre)◮ faire un plan d’expérience

=⇒ le moteur doit jouer des stratégies l’une contre l’autre : auto-apprentissage



ÉVALUATION DE LA VALEUR D’UNE CONFIGURATION :APPROCHE RANDOMISÉE

Valeurs de configurations entières =⇒ cas d’égalité :choix randomisé du coup à joueravantages

◮ stratégie imprévisible pour l’adversaire

◮ en moyenne "devrait" être bon (empirique ! ! ! à tester)

◮ simple à mettre en œuvre

inconvénients◮ reproductibilité (rejouer des parties pour analyser les choix)

◮ contrôle de l’aléatoire : l’uniformité est la garantie de non prévisibilté◮ générateur Random : qualité◮ générateur uniforme de coup (exemple)◮ méthode basée sur l’énumération◮ méthode basée sur le rejet◮ méthode basée sur le conditionnement◮ ...



ÉVALUATION DE LA VALEUR D’UNE CONFIGURATION :MÉTHODE DE MONTE-CARLO

Hypothèse : on dispose d’une stratégie S0 (complexité de calcul simple)

Évaluation_Joueur_A (configuration,taille_echantillon)Données: Configuration de jeu, c’est au joueur B de jouerRésultat: probabilité de gain de A sous la stratégie S0 pour A et BSomme = 0for i=0 to taille_echantillon

C=configurationJoueur = Bwhile Fin de jeu

C=Jouer(C,Joueur, S0)Joueur = adversaire(Joueur)

Somme = Somme + Valeur(C)

Return Somme / taille_echantillon

◮ la profondeur du jeu doit être faible (linéaire ou polynomiale)

◮ la précision dépend de la taille de l’échantillon (théorème central-limite)

ǫ =Φσ

√taille_echantillon

Φ associé au niveau de confiance, σ =√

p(1 − p) l’écart-type

◮ voir α − β, si l’estimation de la probabilité est proche de 0 ou 1 la taille de l’échantillon peutêtre réduite

◮ mélange minimax et méthode de Monte-Carlo



JEUX ET ARBRES

1 Jeux

2 Arbres et/ou

3 La gaufre

4 Minimax

5 Approximation

6 Alpha/Beta

7 Vrac


Min-Max

●  Jeu à 2 joueurs: MAX and MIN . ●  L’arbre de jeux représente tous les coups possibles jusqu’à une

certaine profondeur à partir de la position courante. ●  Chaque feuille est évaluée avec une fonction d’évaluation. ●  Un nœud MAX choisit un coup de score maximal parmi ses fils. ●  Un nœud MIN choisit un coup de score minimal parmi ses fils.

5

Coupure Alpha-Beta

2 9 7 4 8 3 6 4

Principe: si la valeur d’un fils f d’un nœud MAX est supérieure à la valeur courante d’un nœud MIN ancêtre, alors les frères de f n’ont pas besoin d’être explorés :

coupure beta (beta cutoff).

5

Coupure Alpha-Beta

2 9 7 4 8 3 6 4



5

Coupure Alpha-Beta

2 9 7 4 8 3 6 4



5 2 9 7 4 8 3 6 4



Coupure Alpha-Beta

5

Coupure Alpha-Beta

2 9 7 4 8 3 6 4



3

5 2 9 7 4 8 3 6 4



3 3

Coupure Alpha-Beta

5

Coupure Alpha-Beta

2 9 7 4 8 3 6 4



3 6

5

Coupure Alpha-Beta

2 9 7 4 8 3 6 4



3 6

5

Coupure Alpha-Beta

2 9 7 4 8 3 6 4



3 6

5

Coupure Alpha-Beta

6

2 9 7 4 8 3 6 4



3 6

5

Coupure Alpha-Beta

6

2 9 7 4 8 3 6 4



3 6

5

Coupure Alpha-Beta

6

2 9 7 4 8 3 6 4



3 6

5

Coupure Alpha-Beta

6

2 9 7 4 8 3 6 4



3 6 2

5

6

2 9

2

7 4 8 3 6 4



3 6

Coupure Alpha-Beta

5

Coupure Alpha-Beta

6

2 9

2

7 4 8 3 6 4



3 6 ¸6

5

5

Coupure Alpha-Beta

6

2 9

2

7 4 8 3 6 4



3 6 ¸6

5

5

Coupure Alpha-Beta

6

2 9

2

7 4 8 3 6 4



3 6 ¸6

5

5

Coupure Alpha-Beta

6

2 9

2

7 4 8 3 6 4



3 6 ¸6

5

5

Coupure Alpha-Beta

6

2 9

2

7 4 8

¸6

3 6 4



3 6 ¸6

5

4 8

5

Coupure Alpha-Beta

6

2 9

2

7 4 8 3 6 4



3 6 ¸6

5

¸6

4 8

Coupure Alpha Coupure Beta

Coupe α

Élagage fils d’un noeud MIN

U

7 V

4

4

U

3 V

Coupe β

Élagage fils d’un noeud MAX

NB Les coupes peuvent être pronfondes.

Fenêtre [α,β]

•  Seuls sont considérés les nœuds de valeur dans [α,β] : –  Elagage des nœuds

•  MAX si valcour > β

•  MIN si valcour < α.

–  Initialisation: α=-∞, β=+∞ ou alors iterative deepening

Max

Min

Max

7 Min

Valeur courante du MAX: α=2

Valeur courante du MIN: β=6 Max

3 Min

Max

9

α=3

2

7 > ß

2 < α

9 > ß


JEUX ET ARBRES

1 Jeux

2 Arbres et/ou

3 La gaufre

4 Minimax

5 Approximation

6 Alpha/Beta

7 Vrac



IDÉES EN VRAC

Début de partie

Il est un peu ridicule de lancer une exploration dès le début de la partie, d’autant plusqu’elle ne pourra se faire qu’à une profondeur très limitée à ce stade de la partie. C’estpourquoi il est classique de calculer les premiers coups à l’avance, avec une profondeurde recherche élevée (ouvertures apprises par cœur par les joueurs humains).

Fin de partie

De la même manière, on peut se constituer une bibliothèque de fins de partie : c’estbien sûr un moment critique où il faudrait jouer parfaitement, autrement ditdévelopper l’arbre de jeu jusqu’aux fins de partie et cela, le plus tôt possible. Encoreune fois, ces calculs peuvent être faits à l’avance et les résultats stockés.

Variantes

Une autre optimisation est de faire varier la profondeur de recherche selon le momentou l’état de la partie, autrement dit aller plus profond lorsque :

◮ lorsqu’il n’y a pas beaucoup de coups possibles et que l’on peut donc explorer plus profonddans le temps imparti ;

◮ lorsque les situations évaluées aux feuilles semblent instables et qu’il faut poursuivre un peupour déterminer qui a vraiment l’avantage ;

◮ uniquement pour le coup qui a été choisi et dans le but de confirmer ce choix (il s’agit là decombattre l’effet d’horizon, défaut connu des algorithmes de type Min-Max) ;


Documents

Jeux et arbres - inf362.forge.imag.frinf362.forge.imag.fr/.../Presentation-Algorithmique-Jeux-2017-c-gz.pdf · Introduction aux stratégies [email protected] Avril 2017 Jeux