class: center, middle # Monte Carlo Tree Search .author[Luiz Carlos Rumbelsperger Viana] <!-- .address[Departamento de Informática -- Pontifícia Universidade Católica do Rio de Janeiro (PUC-RJ) -- Rio de Janeiro, RJ, Brazil] --> .email[luizcarlosrvn424@gmail.com] Rio de Janeiro, 26 de Novembro, 2020. ??? [Give pause so that people can read the title of the slide] Hoje eu vou apresentar o algoritmo de Monte Carlo Tree Search, que pode ser utilizado, entre outras coisas, para solucionar processos de decisão de Markov. Mas nós vamos focar em usar esse algoritmo para descobrir a forma ótima de se jogar um jogo de tabuleiro, por exemplo jogo da velha, Xadrez ou Go. Estes são jogos determinísticos de informação perfeita, e são os exemplos mais óbvios de como este algoritmo pode ser usado, mas ele também pode ser usado para resolver jogos não-determinísticos, de informação imperfeita ou mesmo para resolver problemas mais gerais envolvendo busca em árvores ou grafos. Depende um pouco de como você escolhe generalizar o algoritmo, né. Vamos falar também um pouquinho sobre a história desse algoritmo e falar de passagem do uso que a DeepMind tem feito dele para jogar Go, Xadrez e StarCraft. Então uma pergunta: focando nesse problema dos jogos, alguém já teria alguma idéia de um algoritmo de busca para encontrar a estratégia ótima para jogar um jogo? O jogo da velha, por exemplo? [pause] --- # Solução pouco eficiente: MiniMax  ??? Então, um algoritmo básico que consegue de fato encontrar uma solução que, em certo sentido é ótima, é o MiniMax. Nesse algoritmo os jogadores de um jogo qualquer tentam minimizar as recompensas máximas dos outros jogadores. Por exemplo, se nós tivermos um jogo por exemplo com dois jogadores onde cada jogador sempre tem de escolher entre duas ações possíveis a cada turno, vamos supor que nós sejamos o jogador círculo aqui. Daí esse algoritmo vai explorando toda a árvore indo até as folhas, ele verifica os valores de cada folha e propaga os valores de cada nó de acordo. [explicar a propagação] Ele encontra a solução ótima no sentido de que ele atinge o chamado Equilíbrio de Nash para jogos desse tipo, ou seja, a melhor resposta para um jogador que utiliza MiniMax é utilizar MiniMax. Isto implica em particular que qualquer outra estratégia jogada contra um jogador que usa MiniMax coloca o jogador que usa MiniMax em alguma vantagem sobre o jogador que não usa MiniMax. Essa vantagem não necessariamente precisa ser a maior vantagem possível dependendo do conhecimento que você tenha sobre o seu oponente, mas é a melhor vantagem possível sob a hipótese de que o seu oponente joga de modo ótimo ou mais racional possível, isto é, que ele também usa Minimax. Acontece que apesar de conseguir encontrar a solução ótima, esse algoritmo tem um problema muito sério de eficiência, porque notem que ele precisa percorrer toda essa árvore para conseguir determinar os valores de cada nó. Para um jogo trivial como jogo da velha, isso não é um problema sério, mas para um jogo razoavelmente complexo como o Xadrez a árvore pode ficar maior do que o número de átomos do universo, por exemplo. Uma otimização que é comumente feita é utilizar a heurística chamada alha-beta pruning, que permite ignorar certas partes da árvore que podemos garantir que não vão dar um resultado melhor do que as partes que já exploramos. Eu não vou entrar muito em detalhes de como funciona o algoritmo de alpha-beta pruning porque não é esse o foco da apresentação, mas mesmo com esse pruning a complexidade do minimax é exponencial na altura da árvore com uma base "grande", onde "grande" é aproximadamente o número médio de ações que o jogador pode tomar a partir de cada estado do jogo, o que para o Xadrez se estima que está entre 31 e 35 movimentos em média. Então por exemplo, imagine percorrer uma árvore com número de nós igual a 35^(número de átomos do universo), por exemplo. Quer dizer, se a gente não conseguir limitar a altura dessa árvore para um valor aceitável esse algoritmo vai ficar inviável de ser utilizado para jogos minimamente complexos. Basicamente a gente pode pensar o Monte Carlo Tree Search como uma forma mais eficiente de computar os valores MiniMax, que ao invés de percorrer todos os caminhos possíveis da árvore até o final do jogo, faz uma amostragem estocástica desses caminhos e tenta estimar os valores MiniMax como a média dos valores amostrados. Usando um argumento do tipo lei dos grandes números se pode demonstrar que quando o número de amostras vai para infinito os valores estimados convergem para os valores MiniMax. Uma outra vantagem que esse algoritmo tem sobre o MiniMax é que, além do pruning, por vezes o que o MiniMax faz para não ter que percorrer uma árvore muito grande, é rodar a busca até uma altura máxima. Por exemplo essa árvore aqui tem altura 4, mas se fosse o jogo de Xadrez, por exemplo, ele dificilmente terminaria em 4 turnos. Então vamos dizer que essa árvore é um lookahead de 4 movimentos nesse jogo de xadrez, ou seja, o algoritmo olha 4 movimentos no futuro a partir da posição inicial. Como o jogo não acaba em 4 turnos esses scores do último nível da árvore não podem ser o scores finais do jogo, que a gente ainda não tem como saber. Então o que a gente pode fazer para obter esse score é estimar o valor desses estados do tabuleiro no final usando uma função heurística. Se a gente não souber uma função heurística para estimar esse valor, não vai ser possível fazer essa redução de tamanho da árvore com lookahead, e aí é bem provável que a gente não consiga usar nenhuma variação de MiniMax para resolver o jogo indicado. Para o jogo de xadrez até não é difícil encontrar uma função heurística. Basta dar um certo valor a cada tipo de peça e depois somar os valores. Então, por exemplo, se um jogador tem rainhas, bispos, e cavalos e o outro jogador só tem peões o primeiro jogador estaria em uma posição melhor do que o segundo. Já por exemplo para o jogo de Go não é tão fácil descobrir uma heurística razoável para estimar qual jogador leva vantagem em uma certa posição do jogo. Às vezes nesse jogo nem experts conseguem dizer muito bem qual jogador está ganhando, então fica inviável reduzir o espaço de busca utilizando um lookahead dessa forma. Já o algoritmo de Monte Carlo Tree Search não precisa inventar uma função heurística para terminar a busca antes do final do jogo. Como ele faz uma amostragem aleatória dos movimentos até chegar ao final ele sempre tem acesso às recompensas de fim de jogo. --- # História e importância do MCTS * Década de 1940s, primeiros usos do método Monte Carlo para problemas em geral. * Bruce Abramson, PhD 1987, primeiro precursor de métodos monte carlo para busca em árvores. * Remi Coulom inventa MCTS em 2006. * Primeiro computador atinge rank de mestre (dan) em Go, 2008. * AlphaGo em 2014: testar quão bem uma rede neural consegue competir jogando Go. * AlphaGo ganha do campeão mundial Lee Sedol em 2016. * AlphaGo generalizado para *General Game Playing*: AlphaZero, MuZero, AlphaStar. 2017-hoje. [Site DeepMind](https://deepmind.com/blog/article/alphazero-shedding-new-light-grand-games-chess-shogi-and-go) ??? O algoritmo está sendo bem badalado atualmente pelo fato de que a DeepMind, que é uma empresa de inteligência artificial subsidiada da Google, o utilizou junto de uma rede neural para atingir um breakthrough na área de inteligência artificial, tendo em 2016 conseguido produzir o primeiro programa capaz de derrotar o campeão mundial no jogo de Go. Construir um algoritmo para jogar Go tão bem quanto um expert era um famoso problema em aberto nessa área. Mais importante do que isso, a DeepMind conseguiu generalizar esse algoritmo de deep reinforcement learning com Monte Carlo Tree Search para jogar uma imensa variedade de jogos, incluindo xadrez a nível de competir com as melhores inteligências artificiais já criadas nesse jogo, jogos de Atari e StarCraft II. Uma promessa no futuro é investigar folding de proteínas usando este algoritmo para descobrir novos remédios, por exemplo para curar o câncer. Outra coisa interessante é que o aprendizado nas versões mais novas do algoritmo é totalmente *tabula rasa*. Eles prometem conseguir treinar a rede neural apenas com exemplos que geram automaticamente a partir da busca com MCTS, sem nenhuma supervisão humana, e a versão mais nova do algoritmo, o MuZero, promete conseguir aprender inclusive as regras do jogo que está jogando sem precisar ser informado do contexto de antemão. Vale a pena acompanhar esse estado da arte. Se alguém se interessar eu posso passar por email depois uma bibliografia que eu tenho sobre o assunto, mas de qualquer forma vocês devem conseguir encontrar muitos dos papers deles no site da DeepMind. Por exemplo por esse link... --- class: center # MCTS Abstrato  ??? Finalmente chegamos à descrição do algoritmo em si. --- class: center # Um MCTS mais Concreto  ??? --- class:center, middle # UCT e UCB1 .large[A fórmula UCB1:]  **Exploration vs Exploitation** ??? Então, a heurística mais indicada para a versão mais simples do MCTS é a heurística UCT que é a chamada *Upper Confidence Bound for Trees*. Ela usa essa fórmula de Upper Confidence Bounds como heurística para determinar a seleção dos nós. Como o nome já diz, isso é uma adaptação do algoritmo de Upper Confidence Bounds que o professor mencionou na aula passada para o caso de busca iterativa em árvores. Uma coisa importante sobre essa fórmula é que ela admite esse parâmetro c aqui que é usado para balancear o nível de exploração e, digamos, conservadorismo da busca. Basta setar c = 2 e N = T para obter a fórmula original que foi apresentada. Notem por exemplo que se esse parâmetro c é pequeno a fórmula vai ficar muito próxima desse valor médio do nó, então o algoritmo vai tender a selecionar ações que foram bem no passado em detrimento a explorar novas possibilidades, ou seja ele vai ser muito mais conservador. Já se o parâmetro c for muito grande ele basicamente vai sempre escolher os nós menos explorados para tentar descobrir alguma nova jogada possível que seja melhor que as anteriores, ainda que ele tenha um nó de valor muito bom que já tenha sido escolhido várias vezes. Nesse caso, o valor dós nós só seria utilizado essencialmente para quebrar empates entre nós com o mesmo número de simulações. Assim esse parâmetro é usado para regular o tradeoff entre estar aberto a novas possibilidades e explorar as melhores opções já conhecidas. Nós também temos esse tradeoff em muitas decisões que nós temos que tomar, por exemplo, se eu sair para comer eu posso escolher um restaurante *tried-and-true* que eu já fui várias vezes e gosto, ou eu posso ir a um restaurante novo para descobrir se ele pode ser tão bom quanto os restaurantes que eu já conheço. Existe sempre um custo e uma recompensa possível associada a qualquer exploração, o custo consiste na possibilidade de que o restaurante seja ruim e eu perca a oportunidade de ir a um restaurante bom, mas a recompensa é de que se o restaurante for bom, possivelmente até melhor do que os que eu conheço, eu vou conseguir uma experiência melhor do que se eu ficasse com o que eu já conheço. Uma convenção que se toma também é que se um nó não foi simulado ainda o valor de UCB1 dele é infinito, então se um nó possuir algum filho ainda não simulado ele sempre vai ter de escolher um dentre eles para simular a seguir. Mas isso é usado só para o treinamento da árvore, depois que você tem uma estimativa boa dos valores basta decidir que ação jogar baseado no maior valor, o que é essencialmente usar MiniMax. --- class: center # Exemplo - UCT <p><a href="https://commons.wikimedia.org/wiki/File:MCTS-steps.svg#/media/File:MCTS-steps.svg"><img src="https://upload.wikimedia.org/wikipedia/commons/thumb/2/21/MCTS-steps.svg/1200px-MCTS-steps.svg.png" alt="MCTS-steps.svg"></a><br>By <a href="//commons.wikimedia.org/w/index.php?title=User:Rmoss92&amp;action=edit&amp;redlink=1" class="new" title="User:Rmoss92 (page does not exist)">Rmoss92</a> - <span class="int-own-work" lang="en">Own work</span>, <a href="https://creativecommons.org/licenses/by-sa/4.0" title="Creative Commons Attribution-Share Alike 4.0">CC BY-SA 4.0</a>, <a href="https://commons.wikimedia.org/w/index.php?curid=88889583">Link</a></p> --- # Como seres humanos aprendem a jogar * .large[Olhar alguns dos movimentos possíveis (Expansão)]. * .large[Selecionar os movimentos mais promissores (Seleção)]. * .large[Imaginar os resultados de um certo número de jogadas futuras (Simulação)]. * .large[Aprender com os resultados (Retropropagação/Backpropagation)]. <section> <div id="game--status"></div> <button class="game--restart">Restart Game</button> <div class="game--container"> <div data-cell-index="0" class="cell"></div> <div data-cell-index="1" class="cell"></div> <div data-cell-index="2" class="cell"></div> <div data-cell-index="3" class="cell"></div> <div data-cell-index="4" class="cell"></div> <div data-cell-index="5" class="cell"></div> <div data-cell-index="6" class="cell"></div> <div data-cell-index="7" class="cell"></div> <div data-cell-index="8" class="cell"></div> </div> </section> ??? Essencialmente, as pessoas normalmente aprendem jogando com outra pessoa, que vai expondo as regras conforme joga. Conforme o jogador vai aprendendo as regras ele vai pensando nos movimentos que ele pode fazer e quais as consequências desses movimentos. Ele passa a selecionar alguns movimentos que são mais promissores e imagina como o seu oponente vai reagir a eles ao longo de várias iterações possíveis do jogo, e no final dessa simulação mental ele descobre quais movimentos provavelmente darão os melhores resultados. Só então o jogador toma uma decisão concreta. Para dar um exemplo, nesse tabuleiro aqui eu primeiro observo que eu tenho 9 movimentos possíveis, o que equivale a expandir o meu horizonte de movimentos. Vamos dizer que eu não saiba jogar muito bem ainda, então eu posso escolher, por exemplo, começar colocando a peça na posição superior direita. Aí eu posso pensar que o meu oponente vai colocar embaixo por exemplo, nesse caso eu posso colocar a minha peça na posição 2, aqui, mas ai eu fico aberto ao ataque do oponente na posição 1. Porque eu não sei jogar, vamos dizer que eu coloque a próxima peça na última posição do tabuleiro, então o meu oponente pode jogar a posição 4, e dái eu perco em qualquer posição que eu jogue, então eu **aprendo** que essa sequência de movimentos não foi muito boa. Então eu paro de imaginar, ou **simular mentalmente** essa sequência de movimentos e tento denovo. Vamos dizer que eu **selecione** os mesmos movimentos até chegar na parte em que eu cometi o erro. Daí eu posso rever a minha jogada e decidir **selecionar** a posição central, que parece ser mais promissora, e a partir dela eu posso ganhar em dois movimentos. Parece razoável essa forma de proceder? Daí eu posso ir jogando várias vezes e ir aprendendo que --- class: center, middle # ***Dúvidas?*** ??? --- # ***Referências:*** <p><a href="https://commons.wikimedia.org/wiki/File:Minimax.svg#/media/File:Minimax.svg"></a><br>By Nuno Nogueira (Nmnogueira) - <a class="external free" href="https://en.wikipedia.org/wiki/Image:Minimax.svg">http://en.wikipedia.org/wiki/Image:Minimax.svg</a>, created in Inkscape by author, <a href="https://creativecommons.org/licenses/by-sa/2.5" title="Creative Commons Attribution-Share Alike 2.5">CC BY-SA 2.5</a>, <a href="https://commons.wikimedia.org/w/index.php?curid=2276653">Link</a></p> ??? --- class: center, middle # ***Fin*** ??? [End Video]