AlphaGo Zero: fait $Q(s_t, a)$ dominer $U(s_t, a)$ dans des états de jeu difficiles?

Dec 03 2020

AlphaGo zéro

AlphaGo Zero utilise une recherche arborescente Monte-Carlo où la phase de sélection est régie par $\operatorname*{argmax}\limits_a\left( Q(s_t, a) + U(s_t, a) \right)$, où:

le paramètre d'exploitation est $Q(s_t, a) = \displaystyle \frac{\displaystyle \sum_{v_i \in (s_t, a)} v_i}{N(s_t, a)}$ (c'est-à-dire la moyenne des valeurs $v_i$ de toutes les simulations qui passent par le bord $(s_t, a)$)
le paramètre d'exploration est $U(s_t, a) = c_{puct} P(s_t,a) \frac{\sqrt{\sum_b N(s_t, b)}}{1 + N(s_t, a)}$ (c'est-à-dire la probabilité a priori $P(s_t, a)$, pondéré par la constante $c_{puct}$, le nombre de simulations qui passe par $(s_t, a)$, ainsi que le nombre de simulations qui passent par $s_t$).

La probabilité a priori $P(s_t, a)$ et valeur de simulation $v_i$ sont tous deux émis par le réseau neuronal profond $f_{\theta}(s_t)$:

Ce réseau de neurones prend comme entrée la représentation brute sur la carte s de la position et de son historique, et produit à la fois des probabilités de déplacement et une valeur, (p, v) = fθ (s). Le vecteur des probabilités de déplacement p représente la probabilité de sélectionner chaque coup a (passe comprise), pa = Pr (a | s). La valeur v est une évaluation scalaire, estimant la probabilité que le joueur actuel gagne à partir de la position s.

Ma confusion

Ma confusion est que $P(s_t, a)$ et $v_i$ sont des probabilités normalisées à différentes distributions, résultant en $v_i$ étant environ 80 fois plus grand que $P(s_t,a)$ en moyenne.

Les sorties du réseau neuronal $(p, v)$, où $p$ est un vecteur de probabilité donné $s_t$, normalisé sur toutes les actions possibles de ce tour. $p_a = P(s_t, a)$ est la probabilité de choisir une action $a$ état donné $s_t$. Une partie de Go a environ 250 coups par tour, donc en moyenne chaque coup a une probabilité$\frac{1}{250}$, c'est à dire $\mathbb{E}\left[ P(s_t, a) \right] = \frac{1}{250}$

D'autre part, $v$ est la probabilité de gagner un état donné $s_t$, normalisé sur toutes les conditions de fin de partie possibles (victoire / égalité / défaite). Par souci de simplicité, supposons$\mathbb{E} \left[ v_i \right] \ge \frac{1}{3}$, où le jeu est joué au hasard et chaque résultat est également probable.

Cela signifie que la valeur attendue de $v_i$ est au moins 80 fois plus grande que la valeur attendue de $P(s_t, a)$. La conséquence de ceci est que$Q(s_t, a)$ est au moins 80 fois plus grand que $U(s_t, a)$ en moyenne.

Si ce qui précède est vrai, alors la phase de sélection sera dominée par le $Q(s_t, a)$ terme, donc AlphaGo Zero devrait avoir tendance à éviter les arêtes sans simulation (arêtes où $Q(s_t, a) = 0$) à moins que tous les $Q(s_t, a)$ les termes sont extrêmement petits ($< \frac{1}{250}$), ou les SCTM contiennent tellement de simulations que le $\frac{\sqrt{\sum_b N(s_t, b)}}{1 + N(s_t, a)}$ terme en $U(s_t, a)$égalise les magnitudes des deux termes. Ce dernier n'est pas susceptible de se produire car je pense qu'AlphaGo Zero utilise uniquement$1,600$ simluations par coup, donc $\sqrt{\sum_b N(s_t, b)}$ plafonne à $40$.

Sélectionner uniquement les mouvements viables

Idéalement, les SCTM ne devraient pas sélectionner tous les mouvements possibles à explorer. Il ne devrait sélectionner que des mouvements viables dans un état donné$s_t$, et ignorez tous les mauvais coups. Laisser$m_t$ est le nombre de mouvements viables pour l'état $s_t$, et laissez $P(s_t, a)$ = 0 pour tous les coups $a$qui ne sont pas viables. Supposons également que les SCTM ne choisissent jamais un mouvement qui n'est pas viable.

Ensuite, la section précédente est en partie allégée, car maintenant $\mathbb{E} \left[ P(s_t, a) \right] = \frac{1}{m_t}$. Par conséquent,$Q(s_T, a)$ devrait seulement être $\frac{m_t}{3}$ fois plus grand que $U(s_t, a)$en moyenne . En supposant$m_t \le 6$, alors il ne devrait pas y avoir trop de problème

Cependant, cela signifie qu'AlphaGo Zero ne fonctionne idéalement que lorsque le nombre de mouvements viables est faible. Dans un état de jeu$s_t$ où il y a de nombreux mouvements viables ($>30$) (par exemple, un virage difficile avec de nombreux choix possibles), la phase de sélection des SCTM se détériorera comme décrit dans la section précédente.

Des questions

Je suppose que mes questions sont:

Ma compréhension est-elle correcte ou ai-je commis des erreurs quelque part?
Fait $Q(s_t, a)$ dominent généralement $U(s_t, a)$par autant en pratique lorsque l'état du jeu a de nombreux mouvements viables? La phase de sélection est-elle généralement dominée par$Q(s_t, a)$ pendant ces états de jeu?
Est-ce que le fait que $Q(s_t, a)$ et $U(s_t, a)$ être dans des ordres de grandeur si différents (lorsque l'état du jeu comporte de nombreux mouvements viables) affecte la qualité de l'algorithme des SCTM, ou les SCTM sont-ils robustes à cet effet et produisent toujours des politiques de haute qualité?
Dans quelle mesure un état de jeu a-t-il de nombreux mouvements viables (> 30) dans Go?

Réponses

2 DennisSoemers Dec 05 2020 at 03:08

Je ne pense pas que vous ayez nécessairement fait de vraies erreurs dans vos calculs ou quoi que ce soit de ce genre, tout semble exact. Je ne peux pas vraiment répondre avec confiance à vos questions sur "X se produit-il habituellement?" ou "Quelle est la fréquence de X?", aurait à expérimenter pour s'en assurer. Je pense que nous pouvons également répondre immédiatement en toute confiance à la question de savoir si les SCTM sont robustes et peuvent toujours produire des politiques de haute qualité avec «oui», car nous avons vu des résultats surhumains à la pointe de la technologie dans un tas de jeux utilisant ces techniques. .