Como funciona a "pesquisa Monte-Carlo"?

16

Eu ouvi sobre esse conceito em um post do Reddit sobre o Alpha Go. Tentei analisar o artigo e o artigo, mas não consegui entender o algoritmo.

Então, alguém pode dar uma explicação fácil de entender de como o algoritmo de busca Monte-Carlo funciona e como ele está sendo usado na criação de bots de IA para jogos?

Dawny33
fonte
Uma boa descrição do algoritmo MCTS pode ser encontrada em: https://towardsdatascience.com/monte-carlo-tree-search-in-reinforcement-learning-b97d3e743d0f .
Nvr 9/04/19

Respostas:

13

O método de Monte Carlo é uma abordagem na qual você gera um grande número de valores ou simulações aleatórias e forma algum tipo de confusão baseada nos padrões gerais, como médias e variações.

Como exemplo, você pode usá-lo para previsões meteorológicas . Prever o tempo a longo prazo é bastante difícil, porque é um sistema caótico em que pequenas mudanças podem levar a resultados muito diferentes. Usando os métodos de Monte Carlo, você pode executar um grande número de simulações, cada uma com mudanças atmosféricas ligeiramente diferentes. Depois, você pode analisar os resultados e, por exemplo, calcular a probabilidade de chuva em um determinado dia com base em quantas simulações terminaram com chuva.

Quanto ao uso de Monte Carlo no Alpha Go, eles parecem estar usando o chamado Monte Carlo Tree Search . Nesta abordagem, você faz uma árvore de possíveis movimentos, algumas voltas para o futuro e tenta encontrar a melhor sequência. No entanto, como o número de jogadas possíveis no jogo go é muito grande, você não poderá explorar muito à frente. Isso significa que alguns dos movimentos que parecem bons agora podem se tornar ruins depois.

Portanto, na Pesquisa em árvore de Monte Carlo, você escolhe uma sequência promissora de movimentos e executa uma ou mais simulações de como o jogo pode prosseguir a partir desse ponto. Em seguida, você pode usar os resultados dessa simulação para ter uma idéia melhor de quão boa é a sequência específica de movimentos e atualizar a árvore de acordo. Repita conforme necessário até encontrar uma boa jogada.

Se você quiser obter mais informações ou dar uma olhada em algumas ilustrações, encontrei um artigo interessante sobre o assunto: C. Browne et al., Uma pesquisa de métodos de pesquisa em árvores de Monte Carlo ( repositório aberto / link permanente (paywalled) )

Espreitador Desencantado
fonte
Então, basicamente, o que monte carlo faz no alphago é criar estratégias de longo prazo, considerando diferentes combinações de movimentos, e não o contrário (escolha uma estratégia e depois os movimentos para alcançá-la)?
Diego Antonio Rosario Palomino
Não há menção ao elemento-chave da abordagem de Monte Carlo, que é o elemento estocástico integrado à seleção de movimentos disponíveis para investigar. A troca de exatidão também não foi mencionada. Esses são os dois aspectos mais importantes e estão ausentes na resposta. Em vez disso, foi mencionado "grande número de valores ou simulações aleatórias", quando é um número menor de simulações de fatores pseudo-aleatórios (uma pesquisa menos exaustiva) que é característica da convergência de Monte Carlo.
FauChristian