Procedimento de busca do AlphaZero

Estou ciente de perguntas relacionadas e ótimas respostas sobre o mesmo tópico, como Noções básicas sobre o AlphaZero . Minhas perguntas estão relacionadas à figura a seguir no procedimento de pesquisa do AlphaZero

Esta figura vem do artigo da Science no AlphaZero (Fig. 4, página 4). A busca é ilustrada para uma posição do jogo muito agradável 1 AlphaZero (branco) e Stockfish (preto) após 29. ... Qf8. O restante da nota da figura é o seguinte

O estado interno do MCTS do AlphaZero é resumido após simulações de 10 ^ 2, ..., 10 ^ 6. Cada resumo mostra os 10 estados mais visitados. O valor estimado é mostrado em cada estado, da perspectiva do branco, escalado para o intervalo [0, 100]. A contagem de visitas de cada estado, em relação ao estado raiz dessa árvore, é proporcional à espessura do círculo da borda. AlphaZero considera 30.c6, mas eventualmente joga 30.d5.

Eu apreciaria algumas idéias sobre as seguintes perguntas. (Importante notar que sou um mero jogador de xadrez sem conhecimento em ciência da computação. Ainda acho isso fascinante)

1. O que representa as simulações 10 ^ 2, ..., 10 ^ 6? Estou muito confuso porque no Material Complementar eles observam que `` Durante o treinamento, cada MCTS usou 800 simulações ''.
2. O que significa que cada MCTS usou 800 simulações?
3. Suponho que o valor de 60 no círculo vermelho nas simulações 10 ^ 2 represente uma pontuação esperada de 60% para o branco, que é a média de todas as avaliações de posição. No entanto, a média simples dos 9 movimentos mostrados é igual a 61,2. Acho que outros movimentos também foram considerados e simulados. Estou bem aqui?
4. Suponho que para as simulações 10 ^ 3 a 10 ^ 6, elas apresentem apenas uma amostra ilustrativa dos ramos. A simulação 10 ^ 5 não é mostrada após 34.Rce1 ou parada após 34.Rce1? Eu acho que cada simulação vai até uma pontuação esperada de 100%.

O diagrama mostra os 10 estados / posições de jogos mais visitados que o AlphaZero calculou. Na verdade, ele está olhando para milhares de posições, mas elas estão apenas mostrando as 10 posições que mais voltam. Para suas perguntas:

1) O algoritmo de busca do AlphaZero é chamado Monte Carlo Tree Search (MCTS). Os fundamentos de como funciona quando se pensa em algum jogo:

• Escolha uma jogada. A maneira como essa movimentação é escolhida é baseada em um algoritmo que favorece:
  • Quão boa jogada foi executada em simulações aleatórias anteriores.
  • Com que frequência foi escolhida (uma jogada realizada menos ==> mais desejável).
• Siga este movimento para um novo estado de jogo (ou seja, a posição que surge quando você joga o movimento).
• Repita a etapa 1, por algum limite de tempo ou profundidade.

A jogada que tem a melhor pontuação média em todos os seus playouts é aquela que o AlphaZero escolhe. Há mais envolvimento do que isso, mas o acima é a ideia geral do MCTS. Então, algo como simulações de 10 ^ 2 para o nó raiz significa que o AlphaZero executou o algoritmo acima 10 ^ 2 vezes para essa posição.

A parte em que eles mencionaram "800 simulações" refere-se a quando o AlphaZero estava aprendendo ( antes de seus jogos com o Stockfish). A maneira como o AlphaZero aprende heurística por conta própria (que permite avaliar com precisão as posições) é jogando repetidamente. Então, eu suponho que eles querem dizer que, durante essa fase de reprodução, cada vez que pensava no que jogar em uma posição, ele só realizou 800 simulações a partir de uma posição. Provavelmente, o objetivo disso era ter tempo para começar mais jogos de prática. Contra o Stockfish, jogar com extrema rapidez é desnecessário, e o AlphaZero também pode usar o tempo que foi dado para reproduzir muito mais simulações.

2) Explicado acima.

3) Sim, milhares de outras jogadas também são consideradas, elas simplesmente não são mostradas no diagrama. Além disso, mesmo que os 10 estados mostrados fossem os únicos alcançados, você não poderia apenas calcular a média das pontuações deles. O motivo é que alguns estados do jogo são atingidos com mais frequência do que outros e, portanto, têm um peso maior no cálculo médio.

• Para ilustrar isso, suponha que você tenha apenas dois movimentos possíveis que você poderia jogar no início de um jogo: 1.e4 e 1.h4. Olhando para o algoritmo MCTS que descrevi, os playouts / simulações no 1.e4 aconteceriam com mais frequência, já que o 1.e4 tem um desempenho melhor. No entanto, o 1.h4 também seria escolhido de vez em quando devido à sua pouca frequência. Então, talvez você faça 9 playouts no 1.e4 e obtenha uma pontuação de 60%, enquanto faz 1 playout no 1.h4 e obtenha uma pontuação de 0%. Suas chances de ganhar na posição inicial não são (60% + 0%) / 2 = 30%, mas sim (60% * 9 + 0% * 1) / 10 = 54%.

4) Sim, apenas uma amostra ilustrativa é mostrada, pois eles só queriam mostrar os 10 estados de jogos mais visitados. Tenho certeza de que o AlphaZero continuou o algoritmo MCTS além de 34.Rce1.