Question:
Procédure de recherche d'AlphaZero
Kortchnoi
2019-01-06 05:34:08 UTC
view on stackexchange narkive permalink

Je connais des questions connexes et des réponses intéressantes sur le même sujet, comme Comprendre AlphaZero. Mes questions sont liées à la figure suivante sur la procédure de recherche d'AlphaZero

enter image description here

Cette figure provient de la Article scientifique sur AlphaZero (Fig. 4, page 4). La recherche est illustrée pour une position du très beau jeu 1 AlphaZero (blanc) et Stockfish (noir) après 29. ... Qf8. Le reste de la note de la figure est la suivante

L'état interne des MCTS d'AlphaZero est résumé après 10 ^ 2, ..., 10 ^ 6 simulations. Chaque résumé montre les 10 états les plus visités. La valeur estimée est affichée dans chaque état, du point de vue du blanc, mise à l'échelle de la plage [0, 100]. Le nombre de visites de chaque état, par rapport à l'état racinaire de cet arbre, est proportionnel à l'épaisseur du cercle de bordure. AlphaZero considère 30.c6 mais joue finalement 30.d5.

J'apprécierais quelques idées concernant les questions suivantes. (Il est important de noter que je suis un simple joueur d'échecs sans connaissances en informatique. Je trouve toujours cela fascinant)

  1. Que représentent les simulations 10 ^ 2, ..., 10 ^ 6 ? Je suis très confus parce que dans le matériel supplémentaire, ils notent que `` pendant la formation, chaque SCTM a utilisé 800 simulations ''.
  2. Qu'est-ce que cela signifie que chaque SCTM a utilisé 800 simulations?
  3. Je suppose que la valeur de 60 dans le cercle rouge dans les 10 ^ 2 simulations représente un score attendu de 60% pour le blanc, qui est la moyenne de toutes les évaluations de poste. Cependant, la moyenne simple des 9 coups indiqués est égale à 61,2. Je suppose que d'autres mouvements ont également été pris en compte et simulés. Suis-je juste ici?
  4. Je suppose que pour les simulations 10 ^ 3 à 10 ^ 6, elles ne présentent qu'un échantillon illustratif des branches. La simulation 10 ^ 5 n'est pas affichée après 34.Rce1 ou arrêtée après 34.Rce1? Je suppose que chaque simulation va jusqu'à un score attendu de 100%.
Un répondre:
Inertial Ignorance
2019-01-06 11:51:15 UTC
view on stackexchange narkive permalink

Le diagramme montre les 10 états / positions de jeu les plus visités calculés par AlphaZero. Il examine en fait des milliers de postes, mais il ne montre que les 10 postes auxquels il revient le plus. Pour vos questions:

1) L'algorithme de recherche d'AlphaZero s'appelle Monte Carlo Tree Search (MCTS). Les principes de base de son fonctionnement en pensant à un état de jeu:

  • Choisissez un coup. La façon dont ce mouvement est choisi est basé sur un algorithme favorisant:
    • La qualité d'un mouvement dans les simulations aléatoires précédentes de celui-ci.
    • La fréquence à laquelle il a été choisi (un mouvement joué less ==> plus souhaitable).
  • Suivez ce mouvement vers un nouvel état de jeu (c'est-à-dire la position qui survient lorsque vous jouez le coup).
  • Répétez l'étape 1, pour une limite de temps ou de profondeur.

Le coup qui a le meilleur score moyen dans tous ses playouts est celui choisi par AlphaZero. Il y a plus que cela, mais ce qui précède est l'idée générale des SCTM. Donc quelque chose comme 10 ^ 2 simulations pour le nœud racine signifie qu'AlphaZero a exécuté l'algorithme ci-dessus 10 ^ 2 fois pour cette position.

La partie où ils ont mentionné "800 simulations" se réfère au moment où AlphaZero apprenait ( avant ses jeux avec Stockfish). La façon dont AlphaZero apprend les heuristiques par lui-même (qui lui permettent d'évaluer avec précision les positions) est de se jouer encore et encore. Donc, je suppose qu'ils signifient que pendant cette phase de jeu en lui-même, chaque fois qu'il pensait à quoi jouer dans une position, il n'effectuait que 800 simulations à partir d'une position. Le but était probablement d'avoir le temps de faire plus de jeux d'entraînement. Contre Stockfish, jouer extrêmement rapidement n'est pas nécessaire, et AlphaZero peut tout aussi bien utiliser le temps qui lui a été accordé pour jouer beaucoup plus de simulations de ce genre.

2) Expliqué ci-dessus.

3) Oui, des milliers d'autres mouvements sont également pris en compte, ils ne sont tout simplement pas affichés dans le diagramme. De plus, même si les 10 états affichés étaient les seuls atteints, vous ne pouviez pas simplement faire la moyenne de leurs scores. La raison en est que certains états de jeu sont atteints plus souvent que d'autres, et ont donc un poids plus élevé dans le calcul moyen.

  • Pour illustrer cela, supposons que vous n'aviez que deux coups possibles dans lesquels vous pourriez jouer le début d'une partie: 1.e4 et 1.h4. En regardant en arrière l'algorithme MCTS que j'ai décrit, les playouts / simulations sur 1.e4 se produiraient plus souvent puisque 1.e4 fonctionnait mieux. Cependant, 1.h4 serait également choisi de temps en temps en raison de la fréquence à laquelle vous le regardez. Alors peut-être que vous faites 9 playouts sur 1.e4 et obtenez un score de 60%, alors que faites 1 playout sur 1.h4 et obtenez un score de 0%. Vos chances de gagner à partir de la position de départ ne sont pas (60% + 0%) / 2 = 30%, mais plutôt (60% * 9 + 0% * 1) / 10 = 54%.

4) Oui, seul un exemple illustratif est affiché car ils ne voulaient afficher que les 10 états de jeu les plus visités. Je suis sûr qu'AlphaZero a continué l'algorithme MCTS bien après 34.Rce1.

Merci! Très bonne réponse. Ok, je comprends que, pendant les matchs contre SF, AZ a effectué 10 ^ 6 simulations par position / état joué, par ex. après 29 ... Qf8 ... En ce qui concerne Q1, ce qui n'est pas clair pour moi est 1 / "Choisissez un coup" est un SCTM et "Répétez l'étape 1" sera un autre SCTM ou 2 / votre exemple est-il seulement un SCTM?
Pour être plus précis dans le 2ème cas: votre exemple est-il un SCTM avec 2 simulations?
@Kortchnoi Le MCTS est un algorithme récursif. Cela signifie que pour s'exécuter, il s'appelle X fois (où X est la profondeur à laquelle il exécute la simulation de lecture à partir de la position de départ). Les étapes que j'ai énumérées de «choisir un coup» jusqu'à «répéter l'étape 1» font toutes partie d'une simulation MCTS, quel que soit le nombre de fois où l'algorithme effectue une itération récursive dans l'arborescence du jeu. Une autre simulation ne démarre que lorsque l'algorithme a terminé la recherche, puis une nouvelle simulation de lecture recommence à partir de la position de départ.
Pensez-y comme ça. Vous voulez savoir quoi jouer dès le premier coup. Vous choisissez 1.e4 via l'algorithme, car dans le passé, il a bien fonctionné dans les simulations que vous avez effectuées mentalement, et en même temps vous n'avez pas fait trop de simulations dessus. Maintenant dans la nouvelle position après 1.e4, vous devez choisir un coup pour que les Noirs jouent. Vous faites le même algorithme, et disons que vous obtenez 1 ... c5. C'est maintenant au tour de White de jouer donc vous faites le même algorithme. Etc, jusqu'à ce que vous atteigniez une limite de profondeur ou que quelqu'un gagne la partie (ou tire). Tout cela est une simulation à partir de la position de départ.
Le résultat de la simulation affecte le score de 1.e4. Cependant, tous les coups joués dans la simulation (tels que 1 ... c5) ont également leurs scores affectés.
Merci beaucoup. Je suppose que je vois. Commençons un SCTM du premier coup. 1.e4 c5 2.Cf3 ... jusqu'à ce que j'atteigne une certaine limite de profondeur serait la simulation 1; 1.e4 c5 2.c3 ... jusqu'à ce que j'atteigne une certaine limite de profondeur serait la simulation 2; 1.e4 d5 2.exd5 ... jusqu'à ce que j'atteigne une certaine limite de profondeur serait la simulation 3; 1.d4 d5 2.Cf3 ... jusqu'à ce que j'atteigne une certaine limite de profondeur serait la simulation 4. etc ... Ai-je raison?
Ensuite, si je joue 1.e4 c5, je lance un MCTS sur le coup 2 avec de nombreuses simulations ...
Oui, exactement. Chaque SCTM n'est qu'un ensemble de ces simulations exécutées à partir de la position à laquelle vous pensez.


ⓘ
Ce Q&R a été automatiquement traduit de la langue anglaise.Le contenu original est disponible sur stackexchange, que nous remercions pour la licence cc by-sa 4.0 sous laquelle il est distribué.
Loading...