IIA MCTS 20212

Prévia do material em texto

CIC 116653 Introdução à Inteligência Artificial Turma A, 02/2021
PPGInf - CIC/UnB
Prof. Li Weigang
weigang@unb.br 
Introdução à Inteligência Artificial  – IIA, 2020
Material:
David Silver, et.al., Mastering the game of Go with Deep Neural Networks and Tree Search, Nature, 529:484-490,2016
•Cameron Browne, et.al., Survey of Monte Carlo Tree Search Methods, IEEE Transactions on Computational Intelligence and AI in Games, 4(1):1-49,2012
•Sylvain Gelly, Levente Kocsis, Marc Schoenauer, et al., The Grand Challenge of Computer Go: Monte Carlo Tree Search and Extensions, Communications of the ACM, 55(3):106-113,2012
•Levente KocsisCsaba Szepesvari, Bandit Based Monte-Carlo Planning, ECML 2006
•Auer, P., Cesa-Bianchi, N., & Fischer, P. , Finite-time analysis of the multi-armed bandit problem, Machine learning, 47(2), 235-256, 2002
Contato:
weigang@unb.br
weigangbr@gmail.com
Página web:
https://cic.unb.br/~weigang/
Pesquisa árvore Monte Carlo
Introdução à Inteligência Artificial  – IIA, 2020
Pesquisa árvore Monte Carlo (MCTS)
Pesquisa árvore Monte Carlo ( MCTS )
Em ciência da computação , pesquisa árvore Monte Carlo ( MCTS ) é uma heurística algoritmo de busca para alguns tipos de processos de decisão , principalmente aqueles empregados em jogo. 
Os exemplos principais da pesquisa árvore Monte Carlo são recentes computador Go programas, seguido de xadrez e shogi , bem como jogos de vídeo em tempo real (como Total War: Rome II 's implementação da campanha de alto nível AI) e jogos com incompleta informação, tais como ponte e póquer .
https://pt.qwe.wiki/wiki/Monte_Carlo_tree_search
Multi-Armed Bandits: Objetivo de arrependimento cumulativo (Cumulative Regret Objective)
s
a1
a2
ak
…
Problema: encontre a estratégia de puxar o braço de modo que a recompensa total esperada no tempo n seja próxima da melhor possível (uma puxada por intervalo de tempo)
Otimo (na expectativa) é puxar o braço otimo n vezes
UniformBandit é uma escolha ruim --- perder tempo com armas ruins
Deve-se equilibrar a exploração de máquinas para encontrar bons resultados e explorar o conhecimento atual
O foco da pesquisa árvore de Monte Carlo é na análise dos movimentos mais promissoras, expandindo a árvore de busca com base em amostragem aleatória do espaço de busca. A aplicação de pesquisa de árvore Monte Carlo em jogos é baseado em muitos playouts . Em cada playout, o jogo é jogado fora até o fim, selecionando se move de forma aleatória. O resultado jogo final de cada playout é então utilizado para ponderar os nós da árvore de jogo para que melhores nós são mais propensos a ser escolhido em playouts futuras.
A maneira mais básica de usar playouts é aplicar o mesmo número de playouts após cada jogada legal do jogador atual, em seguida, escolher o movimento que levou a mais vitórias. A eficiência deste chamado método- Pure Monte Carlo Jogo da pesquisa -muitas vezes aumenta com o tempo à medida que mais playouts são atribuídas aos movimentos que freqüentemente resultou na vitória do jogador atual de acordo com playouts anteriores. Cada rodada de pesquisa árvore Monte Carlo consiste em quatro etapas.
Princípio da Operação - MCTS
Começar a partir de raiz de R e seleccionar sucessivas nós filhos, até que um nó de folha G é atingido. A raiz é o estado do jogo atual e uma folha é qualquer nó do qual ainda não foi iniciada nenhuma simulação (playout). A seção abaixo diz mais sobre uma maneira de influenciar a escolha de nós filho que permite que a árvore de jogo expandir para os movimentos mais promissoras, que é a essência da pesquisa árvore Monte Carlo.
Selecção - MCTS
A menos que L termina o jogo decisivamente (por exemplo, vencer / perda / desenhar) para qualquer um dos jogadores, criar um (ou mais) nós filhos e escolher nó C a partir de um deles. Nós filhos são todos os movimentos válidos a partir da posição de jogo definido por L .
Expansão  - MCTS
L. Kocsis and C. Szepesvari, Bandit based Monte-Carlo Planning, ECML, 2006:282–293 
Simulação : completar uma reprodução aleatória a partir do nó C . Este passo é, por vezes, também chamado de playout ou rollout. A reprodução pode ser tão simples como escolher aleatórios uniformes movimentos até que o jogo é decidido (por exemplo, em xadrez, o jogo é ganho, perdido, ou desenhado).
Backpropagation : usar o resultado do playout para atualizar as informações nos nós no caminho de C para R .
Simulação   - MCTS
Backpropagation : usar o resultado do playout para atualizar as informações nos nós no caminho de C para R .
Backpropagation - MCTS
Este gráfico mostra as etapas envolvidas na única decisão, com cada nó mostrando a proporção de vitórias para playouts totais a partir desse ponto na árvore de jogo para o jogador que o nó representa. No diagrama de Selecção, preto está prestes a mover. O nó raiz mostra que existem 11 vitórias em 21 playouts para branco a partir desta posição até agora. Complementa o total de 10/21 vitórias pretas mostrados ao longo das três nós pretos sob isso, cada um dos quais representa um possível movimento preto.
Se o branco perde a simulação, todos os nós ao longo da selecção incrementado sua contagem de simulação (o denominador), mas entre eles apenas os nós negros foram creditados com vitórias (o numerador). Se vitórias vez brancos, todos os nós ao longo da seleção ainda iria aumentar sua contagem de simulação, mas entre eles apenas os nós brancos seria creditado com vitórias. 
Nos jogos em que empates são possíveis, um empate faz com que o numerador tanto para preto e branco para ser incrementado por 0,5 e o denominador por 1. Isso garante que durante a seleção, as escolhas de cada jogador se expandir para os movimentos mais promissores para esse jogador, que espelha o objetivo de cada jogador para maximizar o valor de seus movimentos.
MCTS
MCTS - exemplo
V: o valor do no Si; N: vezes da visita ao pai; ni: vezes da visita do no.
1. O estado inicial da árvore:
T representa o valor total e 
N representa o número de visitas (contagem de visitas). 
A um meio de ação.
MCTS - exemplo
Estado S_0
 No início, para escolher entre as duas ações a seguir (assumindo que haja apenas duas ações disponíveis), o critério de seleção é U C B 1 (S i) valor. Obviamente, pode ser contado como:
UCB1 (S 1) = UCB1 (S 2) = ∞ 
Neste caso, tomaremos o primeiro em ordem, ou seja, A_1 
Assim, o estado S1 é alcançado 1
De acordo com o fluxograma das etapas 1 e 2, agora precisamos determinar o nó atual S_1
 (nó atual) é um nó folha, onde um nó folha significa que não foi expandido. Obviamente, este nó não foi expandido, então é um nó folha. Em seguida, de acordo com o fluxograma, é necessário determinar o nó S_1
Se o coeficiente acessado é 0. É 0, portanto, a implementação é necessária.
Rollout é, na verdade, realizar ações aleatórias em cada etapa das próximas etapas, até o ponto de parada (o final do jogo em Go), para obter um valor final.
Suponha que o valor final de Rollout seja 20.
MCTS – exemplo – 1 A primeira iteração
Seguida, vá para a etapa 4 Backpropagation, ou seja, use o valor finalmente obtido por Rollout para atualizar os valores T e N de cada nó no caminho.
MCTS - exemplo
Em seguida, exclua o resultado do Rollout. 
A ideia do MCTS é iterar continuamente a partir de S_0 e atualizar o valor do nó até que um determinado número de iterações ou tempo seja atingido.
MCTS - Segunda iteração:
Começamos de S_0 para a segunda iteração (iteração):
Primeiro, calcule os valores de UCB1 dos seguintes dois nós S_1 e S_2:
UCB1 (S1) = 20 UCB1 (S2) = ∞
Portanto, selecione a ação A_2 para atingir o estado S_2.
Da mesma forma que acima, agora é necessário julgar se o nó S_2 é um nó folha. Sim, continue a determinar o número de visitas. É 0, então insira Rollout, supondo que o valor final de Rollout seja 10..
MCTS - Segunda iteração:
Depois disso, retropropagação:
MCTS - Terceira iteração:
Primeiro, calcule o valor UCB1:
U C B 1 (S 1) ≈ 21,67 
U C B 1 (S 2) ≈ 11,67
Executar ação A_1 , Insira o estado S_1, é um nó folha?sim.
O número de visitas é 0? não.
De acordo com o fluxograma, agora entre na etapa de expansão do nó. Também presume-se que haja apenas duas ações disponíveis.
MCTS - Terceira iteração:
Selecione S_3 para Rollout, supondo que o valor final de Rollout seja 0.
MCTS - Terceira iteração:
Atualize o valor de cada nó no caminho e, em seguida, exclua o valor de Rollout:
MCTS - Quarta iteração:
Primeiro, calcule o valor UCB1:
Selecione A_2, entre no estado S_2 e siga as mesmas etapas da terceira iteração:
MCTS - Quarta iteração:
Nós no caminho de atualização:
Suponha que definimos o número máximo de iterações como 4, então nossa iteração está completa. Neste momento, use a árvore obtida para determinar o S_0
Qual ação deve ser selecionada. De acordo com o valor UCB1, obviamente temos que escolher a ação A_2
acima é o processo de MCTS, que é traduzido do youtube: 
https://www.youtube.com/watch?v=H__-7zzNiPk&list=RDCMUCBVCi5JbYmfG3q5MEuoWdOw&start_radio=1&rv=H__-7zzNiPk&t=73&ab_channel=Udacity
MCTS - Algoritmo:
MCTS - AlfaGo
MCTS - AlfaGo
Use supervised learning to train police network
–Idea: perform supervised learning (SL) to predict human moves 
–Given state 𝑠, predict probability distribution over moves 𝑎, 𝑝𝜎,𝑝(𝑎|𝑠) 
–Trained on 30M positions, 57% accuracy on predicting human moves 
–Also train a smaller, faster rollout policy network (24% accurate) 
Use reinforcement learning to train police network
–Idea: fine-tune policy network using reinforcement learning (RL) 
–Initialize RL network to SL network 
–Play two snapshots of the network against each other, update parameters to maximize expected final outcome 
–RL network wins against SL network 80% of the time, wins against open-source Pachi Go program 85% of the time 
MCTS - AlfaGo
Value network 
–Idea: train network for position evaluation 
–Given state 𝑠′, estimate 𝑣𝜃(𝑠′), expected outcome of play starting with position s and following the learned policy for both players 
–Train network by minimizing mean squared error between actual and predicted outcome 
–Trained on 30M positions sampled from different self-play games 
Go Overview
Only two basic rules
Capture rule: stones that have no liberties ->captured and removed from board
ko rule: a player is not allowed to make a move that returns the game to the previous position
X
. A "liberty" is an open "point" (intersection) next to a stone
28
Go In a Reinforcement Set-Up
Environment states
Actions
Transition between states
Reinforcement function
S = 
A = 
r(s)= 
0 if s is not a terminal state
1 o.w
Goal : find policy that maximize the expected total payoff
Action – any free space on the board
29
Why it is hard for computers to play GO?
Possible configuration of board extremely high ~10^700 
Impossible to use brute force exhaustive search 
Chess (b≈35, d≈80) 	Go (b≈250, d≈150)
main challenges
Branching factor 
Value function
https://googleblog.blogspot.co.il/2016/01/alphago-machine-learning-game-go.html
Branching factor is huge –possible moves – compare to chess 
thought to be impossible - intuition not calculation
 
30
Training the Deep Neural Networks
Human experts (state,action)
 - SL policy network
 - Rollout policy network
 - RL policy network
(state, win/loss)
 - Value network
Monte Carlo Tree Search 
High level description of the training pipeline 
KGS - Go Server you can play go
Two nn - to predict actions given a state. Policy network SL – copy expert players, and a rollout (faster version)
Using Reinfocment learning – refine Policy Rl
Generate new training data –using self play 
Train value network – predict who is winning and by how much given state
Combined to MCTS: search algorithm used in match time
Keep in mind that one of the amazing thing in Go is that its does not use handcrafted algorithms like Deep blue for example – very generic 
Try to remember the names we will talk about them for a while
31
Training the Deep Neural Networks
Policy
Policy
Value
The motivation of using policy and value networks
Policy – reduce the breadth of tree
Value – reducing the depth of tree
when thinking what it should do next can use the policy network to consider only greater then a Threshold actions
Estimating who is winning the game and by how much. Instead of searching until the end of the tree. 
Policy RL can beat policy SL 80% of the time
Breakthrough : value . Not writing by hand like deepblue.
32
SL Policy Network : 
~30 million (state, action)
Goal:maximize the log likelihood of an action
Input : 48 feature planes
Output: action probability map
19X19X48
12 convolutional + rectifier layers
Softmax
Probability map
The training data
Pass moves was excluded 
Kgs
include all 8 reflections and rotations of each position
The goal was to max the lo liklihood
Input : Features: current game state, number of liberties,…
Output 
Net architecture 
The gradient step
(test – 1 million , train ~29 million ) – pairs (s,a)
Step size – every 80 million training steps – alpha better and slower
		Accuracy
	AlphaGo (all input features)	57.0% 
	AlphaGo (only raw board position)	55.7%
	state of the art	44.4%
The left side is the architecture properties
The right side : the evaluation 
Notice that the policy with the most filters and features is the most accurate but the slowest
In the blue raw : percentage of wines against the green policy (which used for the AlphaGo) selecting moves directly 
Number of feature planes
Results: test and train accuracy on the KGS, percentage of wines against the highlighted (AlphaGo policy net): raw – select moves directly. Not raw – using AlphaGo search, finaly computation time for single evaluation 
34
Training the Rollout Policy Network 
Similar to SL policy 
Output – probability map over actions
Goal: maximize the log likelihood 
Input 
Not full grid 
*handcrafted local features*
12 convolutional + rectifier layers
Softmax
Probability map
		Forwarding 	Accuracy
	SL policy net 	3 milliseconds 	55.4%
	Rollout Policy Network 
	2 microseconds	24.2%
I will explain now about the rollout policy training
This should predict action given a state
But the forwarding should be much very fast because it is used to simulate games during match
Same architecture as SL-policy except input is much smaller - doesn’t look at the entire 19×19 board, 
smaller window around the opponent’s previous move and the new move it’s considering
The hadcraftes local features are mainly to encode common sense Go rolls 
Imp
The simplified version doesn’t look at the entire 19×19 board, but instead only looks at a smaller window around the opponent’s previous move and the new move it’s considering.
smaller window around the opponent’s previous move and the new move it’s considering – encode common sense Go rolls 
35
Training the RL Policy Network 
Refined version of SL policy ()
Initialize weights to 
{| is an old version of }
 vs. 
SGA
19X19X48
12 convolutional + rectifier layers
Softmax
Probability map
Preventing overfitting
RL policy Won more then 80% of the games against SL policy
Tune the SL policy to win the game
Improve the weights iteratively
All the old version of rho are kept and each iteration they picked a rho minus
Rho and rho minus are competing until a terminal state
Now we can evaluate if the policy was good or bad
Replayed in order to do SGA – where z controls the direction
Every 500 iteration added the current parameter rho to the opponent pool
36
 - RL policy network
 - Rollout policy network
Training the Deep Neural Networks
 - Value network
Monte Carlo Tree Search 
 - SL policy network
Human experts (state,action)
(state, win/loss)
remember at what stage of the training are we.
Finished the training of the first 2 polices that aim to mimic experts actions one is more accuratebut the other is more fast.
A function of state that outputs an action
We refined the net to our original purpose - winning a game, using reinforcement learning
Using the RL-policy network they generated new data. They self played using the policy and used pairs of state and loss or win 
37
Training the Value Network 
Position evaluation
Approximating optimal value function
Input : state , output: probability to win
Goal: minimize MSE
Overfitting - position within games are strongly correlated
19X19X48
convolutional + rectifier layers
fc
scalar
The value network goal is to give a position evaluation 
We would like to approximate the optimal value function by approximating the value function of policy p_rho 
Trained for 50 million mini-batches of 32 positions for one week.
The architecture is similar to the policy net works - except the output is scalar 
Used SGD – to minimaize the squared error
The naive approach of predicting game outcomes from data consisting of complete games leads to overfitting. The problem is that successive positions are strongly correlated, differing by just one stone, but the regression target is shared for the entire game. When trained on the KGS data set in this way, the value network memorized the game outcomes rather than generalizing to new positions, achieving a minimum MSE of 0.37 on the test set, compared to 0.19 on the training set. To mitigate this problem, we generated a new self-play data set consisting of 30 million distinct positions, each sampled from a separate game. Each game was played between the RL policy network and itself until the game terminated. Training on this data set led to MSEs of 0.226 and 0.234 on the training and test set respectively, indicating minimal overfitting.
38
Capacitação Inovadora para o Futuro das Pessoas e Organizações
image5.jpeg
image6.png
image7.emf
image8.emf
image9.png
image10.png
image11.png
image12.png
image13.png
image14.png
image15.png
image16.png
image17.png
image18.png
image19.png
image20.png
image21.png
image22.png
image23.png
image24.png
image25.png
image26.png
image27.emf
image28.png
image29.png
image30.png
image31.png
image32.jpeg
image33.png
image34.jpeg
image180.png
image190.png
image35.png
image210.png
image36.png
image160.png
image37.jpeg
image38.jpeg
image39.jpeg
image260.png
image40.png
image41.png
image42.png
image300.png
image350.png
image330.png
image37.png
image39.png
image43.png
image44.png
image47.jpeg
image430.png
image440.png
image45.png
image46.jpeg
image53.png
image48.png
image49.png
image4.png
image3.png
image1.png