Comprendre AlphaZero

29

Très récemment, la nouvelle est venue que l'équipe de recherche DeepMind d'Alphabet a étendu son moteur d'apprentissage automatique pour jouer à la fois au shogi et aux échecs. Apparemment, après seulement quelques heures d'auto-apprentissage, c'est-à-dire qu'en jouant contre lui-même étant donné les règles du jeu, ses performances aux échecs ont déjà dépassé celles des meilleurs moteurs actuels tels que Stockfish 8. Personnellement, je ne sais pas encore exactement comment les matchs ont été organisés, comme dans quelles conditions Stockfish devait être exécuté, car si les temps de calcul sont limités, les moteurs peuvent très mal fonctionner. En tout cas, c'est une réalisation très impressionnante, car même s'il s'avérait que l'on aurait pu configurer Stockfish de manière plus optimale, avec quelques heures de formation supplémentaires, AlphaZero dépasserait à nouveau le niveau de jeu, ce qui signifie qu'AlphaZero est fondamentalement plus fort que n'importe quel autre actuel moteur d'échecs standard basé sur des fonctions d'évaluation heuristique.

Maintenant, à la lumière de ces nouvelles, il serait formidable que quelqu'un puisse expliquer les principales différences dans le fonctionnement d'un moteur d'échecs à apprentissage automatique par rapport aux moteurs standard que nous sommes tous habitués à utiliser. Plus concrètement:

  1. La fonction d'évaluation qu'AlphaZero utilise, formée par des méthodes d'apprentissage automatique, n'est-elle pas à la fin une autre fonction d'évaluation heuristique? Si oui, serait-il juste de dire que la différence fondamentale entre les fonctions d'évaluation des deux moteurs est le fait que Stockfish a une fonction d'évaluation optimisée réglée manuellement par les humains, ce qui signifie que la définition de la fonction à optimiser est fixe, alors que pour AlphaZero, la fonction d'évaluation de la cible est constamment redéfinie par une formation supplémentaire (par exemple par l'auto-jeu)? Faire de ce dernier une approche beaucoup plus dynamique.
  2. En fin de compte, vaguement, un moteur comme Stockfish, applique sa fonction d'évaluation à l'arbre des mouvements possibles, décidant quelles branches garder et lesquelles abandonner, puis à travers un béton plus profondl'analyse de chaque branche, toujours à travers sa fonction d'évaluation, elle détermine quelle branche a donné la valeur la plus élevée, et cela devient la principale variation (bien sûr, il existe de nombreuses techniques avancées autour de ce processus pour tailler efficacement ce grand arbre). Cela signifie que pour chaque poste, cette routine extrêmement concrète doit être répétée pour que Stockfish prenne une décision. En revanche, j'imagine qu'AlphaZero fait quelque chose de très différent, à savoir qu'il ne s'appuie pas sur une analyse concrète de l'arbre des mouvements possibles à une position donnée, au lieu de cela sa fonction d'évaluation attribue essentiellement une valeur à cette position (ce qui est intuitivement similaire à mettre le poste actuel par analogie avec tous les autres postes pour lesquels il a été formé), sans jamais avoir à réaliser du bétonanalyse comme le fait Stockfish, ou même un joueur humain. S'agit-il du tout d'une image solide du fonctionnement d'AlphaZero ou de moteurs d'apprentissage machine formés de manière similaire?

  3. Nous savons que l'espace des positions d'échecs est suffisamment grand pour que toute tentative d'échantillonnage de toutes les positions qu'il contient serait même en principe complètement vaine (complexité EXPTIME), ce qui suggérerait qu'aucune quantité d'entraînement par auto-jeu ne serait suffisante pour ont exploré toutes les positions, alors comment le résultat final peut-il être bon malgré avoir potentiellement exploré une petite fraction des positions de l'espace via le jeu automatique? Quelle est l'idée clé ici en jeu?

  4. Je suppose que AlphaZero a un moyen très optimal de comparer une position donnée, même nouvelle, à une position précédemment visitée dans son ensemble de formation, plus la comparaison est proche, plus l'évaluation peut être valide à partir de la comparaison. Par exemple, quand il a joué le coup Bg5 dans le jeu 5 , il doit avoir exploré une structure similaire lors de son entraînement, c'est-à-dire qu'il est capable de reconnaître que cette position est essentiellement équivalente (éventuellement complètement) différente à celle étudiée dans son entraînement, en analogie avec la façon dont la reconnaissance des visages est obtenue grâce à l'apprentissage automatique, et en conséquence, il conclut que Bg5 devrait être le meilleur choix, comme ce fut le cas dans (ou dans) d'autres positions similaires. Est-ce une supposition correcte? Je ne sais pas comment cette comparaison est fait, car il n'est sûrement pas possible de stocker toutes les positions entraînées et de les analyser à chaque fois.

Il s'agit simplement d'une tentative pour obtenir un tel aperçu du fonctionnement d'AlphaZero et de la façon dont il prend une décision en fonction d'un poste.

user929304
la source

Réponses:

18
  • Comment AlphaZero sélectionne-t-il un mouvement dans la recherche?

C'est très évident d'après le document.

Chaque simulation se déroule en sélectionnant dans chaque état un déplacement avec un nombre de visites faible, une probabilité de déplacement élevée et une sélection de valeur élevée ...

Qu'est-ce que ça veut dire? AlphaZero a formé des probabilités pour chaque mouvement (fin de la page 2 de l'article) à partir d'un réseau neuronal profond. Pendant la recherche, il choisit un mouvement proportionnel à cette probabilité, ainsi que des nœuds qui ont un faible nombre (pour garantir que l'espace d'échantillonnage est exploré). Ce n'est pas un nouveau concept, Monte Carlo Tree Search était dans la littérature avant que Google n'existe.

------ (Très) Exemple approximatif ------

Nous avons une position, et nous avons deux mouvements juridiques.

  • Le coup 1 est bon et raisonnable
  • Move 2 met votre propre roi en danger sans compensation

Selon l'article, un modèle profond entraîné pourrait estimer les probabilités à (0,90, 0,10). Supposons qu'AlphaZero utilise 4 itérations à Monte Carlo. Les itérations pourraient ressembler à:

Itération 1 : Choisissez le coup 1 car il a la probabilité la plus élevée. Faites une simulation à partir du coup 1. Itération 2 : Choisissez le coup 1 parce qu'il a la probabilité la plus élevée. Faites une simulation à partir du coup 1. Itération 3 : Choisissez le coup 1 parce qu'il a la probabilité la plus élevée. Faites une simulation à partir du coup 1.

Maintenant, nous sommes à l'itération 4. Bien que le coup 1 ait la probabilité estimée la plus élevée mais que le coup 2 n'ait pas été recherché ("faible nombre de visites" dans le document), AlphaZero choisirait maintenant le coup 2 et ferait une simulation.

Les deux mouvements seraient considérés, mais AlphaZero mettrait plus de ressources informatiques sur le mouvement 1 (bonne chose).

AlphaZero choisirait alors le mouvement avec le meilleur résultat attendu.

------------------ Vos questions: ------------------

La fonction d'évaluation qu'AlphaZero utilise, formée par des méthodes d'apprentissage automatique, n'est-elle pas à la fin une autre fonction d'évaluation heuristique?

La fonction d'évaluation entraînée est un réseau neuronal profond, ce n'est pas un ensemble de règles heuristiques, comme ce que vous voyez dans Stockfish. Personne ne comprend parfaitement (pas même l'équipe Google) le réseau formé, cela fonctionne. C'est ainsi que NN fonctionne en général.

alors que pour AlphaZero, la fonction d'évaluation cible est constamment redéfinie grâce à la fonction d'évaluation cible est constamment redéfinie grâce à une formation supplémentaire.

La fonction d'évaluation d'AlphaZero est un ensemble de neurones entraînés (biais + poids). L'équipe Google a utilisé des machines très puissantes pour entraîner les paramètres. En règle générale, plus vous investissez de ressources dans la formation d'un modèle d'apprentissage en profondeur, meilleurs sont les paramètres que vous obtenez.

(2).

Stockfish utilise l'alpha-bêta, tandis qu'AlphaZero utilise Monte-Carlo. Ce sont deux algorithmes très différents. L'algorithme alpha-bêta suppose une limite inférieure / supérieure, tandis que Monte-Carlo crée des simulations de la racine à la feuille.

d'avoir exploré toutes les positions, alors comment le résultat final peut-il être bon malgré avoir potentiellement exploré une petite fraction des positions de l'espace via le jeu automatique? Quelle est l'idée clé ici en jeu?

Google n'a pas prétendu avoir résolu les échecs, même leurs puissantes machines ne pouvaient pas énumérer toutes les positions d'échecs. Mais ils n'avaient pas à le faire ... c'est le point pour l'apprentissage automatique, le modèle "apprend" à partir de l'ensemble de formation. Dans ce cas, l'ensemble d'entraînement provient de l'auto-jeu. L'idée clé est de jouer contre lui-même autant de jeux de bonne qualité que possible et rapidement.

Par exemple, quand il a joué le coup Bg5 dans le jeu 5, il doit avoir exploré une structure similaire lors de son entraînement,

Je ne pense pas qu'AlphaZero ait rencontré exactement la même position dans les jeux d'entraînement. Je pense qu'une lecture rapide de Monte-Carlo est une bonne idée:

https://chessprogramming.wikispaces.com/Monte-Carlo+Tree+Search

AlphaZero a pu jouer le coup en atteignant une profondeur suffisante. L'algorithme estime la probabilité attendue de gagner pour chaque coup, apparemment, le coup Bg5 a donné la probabilité attendue la plus élevée.

Vous pouvez penser que AlphaGo a pu si bien chercher qu'il a vu la probabilité de gagner la plus élevée après Bg5, tandis que Stockfish n'a pas considéré le mouvement sérieusement (et donc perdu).

SmallChess
la source
2
"Monte Carlo Tree Search était dans la littérature avant que Google n'existe" Je ne peux retracer les SCTM que vers 2006.
CodesInChaos
2
@CodesInChaos MCTS n'est pas une nouvelle technique. Google n'a certainement pas inventé Monte Carlo.
SmallChess
4
Brügmann 1993 n'est clairement que MC. MC Go Dev. (2003) combine MC et arbres, mais de manière primitive. Chang (2005) est assez proche, mais dans un contexte différent et je pense qu'il manque encore le bon choix du nœud à développer et la propagation des estimations. Opérateurs de sélectivité et de sauvegarde efficaces dans les SCTM Remi Coulom (2006) est un SCTM approprié, pour autant que je sache, le premier.
CodesInChaos
1
@SmallChess Certaines parties de votre réponse semblent contradictoires: "maintenant AlphaZero choisirait le mouvement 2 et ferait de la simulation. Les deux mouvements seraient considérés, mais AlphaZero mettrait plus de ressources informatiques sur le mouvement 1 (bonne chose)." contredit l'énoncé Chaque simulation procède en sélectionnant dans chaque état un mouvement avec un faible nombre de visites ... car, dans votre exemple, ce serait 2 plutôt que 1. Pour être honnête, le document ne contient aucune information utile pour le compréhension, car ils ne montrent aucun moyen de reproduire l'expérience ou donnent un aperçu de la façon dont ils forment les réseaux.
gented
1
Ce qu'ils font est essentiellement de dire "nous avons utilisé l'algorithme X et cela fonctionne" - ce qui fournit peu ou pas de compréhension sur les méthodes elles-mêmes, donc je ne me concentrerais pas trop sur le papier lui-même pour essayer de comprendre ce qu'il fait vraiment.
gented
0

Je suppose que ma question serait de savoir comment le réseau neuronal "apprend" ce qu'il doit faire dans une position qu'il n'a pas rencontrée. Dire que l'AZ réel exécute un SCTM en utilisant les biais + poids du réseau neuronal formé repousse simplement une étape vers la façon dont le réseau neuronal calcule ces valeurs. Si c'est à travers un jeu de hasard aléatoire, sans aucune connaissance humaine, comment décide-t-il comment pondérer une position qu'il n'a jamais vue?

Roy Koczela
la source
1
Je pense que je pourrai peut-être vous répondre, mais pas ici. Veuillez commencer une nouvelle question.
SmallChess