AlphaZero: apprentissage par renforcement et … R eseaux de Neurones L’algorithme AlphaZero R esultats exp erimentaux Conclusion Apprentisage par renforcement MCTS AlphaZero Calculs

AlphaZero:apprentissage par renforcement et reseaux de

neurones a convolutions pour les jeux de plateau

Remi Coulom

Juin 2018

IntroductionReseaux de Neurones

L’algorithme AlphaZeroResultats experimentaux

Conclusion

AlphaZeroPlan de l’expose

Janvier 2016: Le choc AlphaGo

Des resultats spectaculaires

Domine les meilleursconcurrents (99.8% devictoires)

Premiere victoire contre unjoueur humain professionnel(Fan Hui, championd’Europe)

Remi Coulom AlphaZero 2 / 50



Conclusion


Mars 2016: Defaite d’un champion legendaire

Match contre Lee Sedol

Victoire 4-1 pour la machine

Choc immense dans lemonde du go

Un film documentaire,AlphaGo (disponible surNetflix)




Conclusion


Octobre 2017: AlphaGo Zero, Decembre 2017: AlphaZero

Apprendre a partir de zero

AlphaGo apprenait a imiterdes parties d’experts

AlphaGo Zero apprend desparties qu’il joue contrelui-meme

AlphaZero generalisel’approche aux echecs et aushogi

Regles → AlphaZero → IA forte

go

echecs

shogi

gomoku




Conclusion


Plan de l’expose

Reseaux de Neurones

L’algorithme AlphaZero

Application au morpion




Conclusion

Regression lineaireReseaux de neurones scalaireDescente de gradientReseaux de neurones a convolutions

Regression lineaire

yi = w0 + w1 × xi

Erreur E =∑

i (yi − y∗i )2

Trouver w0 et w1 quiminimisent E




Conclusion


Un neurone




Conclusion


Rectified Linear Unit




Conclusion


Reseau de neurones scalaire




Conclusion


Descente de gradient stochastique

On initialize les poids aleatoirement

On mesure l’erreur E sur une entree xi aleatoire

w ← w − η ∂E∂w

η coefficient d’apprentissage (learning rate)




Conclusion


Donnees sous forme de matrice: images, jeu




Conclusion


Convolution




Conclusion


Architecture du reseau: une couche




Conclusion

Apprentisage par renforcementMCTSAlphaZero

Apprentissage par renforcement

Maximiser la somme des recompenses au cours du temps

Probleme de controle optimal

Par opposition a apprentissage supervise (probleme deregression)




Conclusion


L’approche acteur-critque

Le systeme estime, pour chaque action a, et chaque etat s:

acteur: π(s, a), probabilite de choisir a dans s

critique: V (s), esperance de recompense cumulee depuisl’etat s




Conclusion


Architecture du reseau




Conclusion


MCTS (Monte Carlo Tree Search)




Conclusion


MCTS avec un reseau de neurones

Selection de l’action a

maxa

Q(s, a) + cπ(s, a)

√∑b N(s, b)

1 + N(s, a)

Q(s, a): moyenne des evaluations

c: coefficient d’exploration

π(s, a): probabilite de a

N(s, a): nombre de visites de a




Conclusion


AlphaZero: 1. Jouer contre soi-meme




Conclusion


AlphaZero: 2. Apprendre




Conclusion


Calculs de AlphaGo Zero

80 couches de 256 unites.

256× 256 convolutions 3x3 par couche

environ 50 millions de parametres

pres de 20 milliards de multiplications pour une evaluation

5000 TPUs pendant 30 jours

4,9 millions de parties jouees a 1,600 simulations par coup




Conclusion


Resultat

Le programmable est imbattable par les humains

Un style original, imite par les pros




Conclusion

MorpionResultats experimentaux

Application au morpion (gomoku narabe)

Tres populaire en Asie etEurope de l’Est.

Les meilleures programmesne battent les meilleurshumains que depuis tresrecemment.

Une competition annuelleentre programmes: laGomocup.




Conclusion


Apprentissage

12 couches

128 neurones

environ 1 millions de poids

(contrainte de taille de la gomocup)




Conclusion


Detection de l’alignement de 5




Conclusion


Iteration 2




Conclusion


Iteration 11




Conclusion


Iteration 31




Conclusion


Position de depart V = −0.3611




Conclusion


Iteration 9 V = −0.10




Conclusion


Iteration 20 V = −0.70




Conclusion


Iteration 25 V = +0.8741




Conclusion


Iteration 31 V = +0.9974




Conclusion


Partie




Conclusion


Partie




Conclusion


Partie




Conclusion


Partie




Conclusion


Partie




Conclusion


Partie




Conclusion


Partie




Conclusion


Partie




Conclusion


Partie




Conclusion


Partie




Conclusion


Partie




Conclusion


Partie




Conclusion


Partie




Conclusion


Partie




Conclusion


Partie




Conclusion


Victoire contre Yixin

Le match

Yixin: Vainqueur de la Gomocup, 7 fois consecutivement

5 secondes par coup, GPU: GTX 960M, CPU: i7-6700HQ a2.60 GHz

41 ouvertures de piskvork, 1 partie de chaque couleur

Resultat: victoire 48-34 (8 fois 2-0, 1 fois 0-2, 32 fois 1-1).

Environ 800 evaluations par seconde (Yixin: 1000 fois plus?)




Conclusion

Conclusion

Une methode generique pour les jeux de plateau

Pas necessaire de construire des heuristiques a la main

Fonctionne hyper bien


Documents

AlphaZero: apprentissage par renforcement et … R eseaux de Neurones L’algorithme AlphaZero R esultats exp erimentaux Conclusion Apprentisage par renforcement MCTS AlphaZero Calculs