A ferramenta do cão alfa: Algorithm de Monte Carlo, depois de ler, você entende!

O Alfabeto Alfa: Algorithmos de Monte Carlo, depois de ler!

De 9 a 15 de março deste ano, um grande acontecimento aconteceu no mundo do Go, quando uma batalha entre humanos e máquinas de cinco rodadas foi realizada em Seul, na Coreia do Sul. O resultado da disputa foi a derrota humana, com o campeão do mundo de Go, Lee Hsiung, sendo derrotado por 1 a 4 pelo programa de inteligência artificial AlphaGo, da Google. Então, o que é o AlphaGo e onde está a chave para vencer?

• AlphaGo e o algoritmo de Monte Carlo

De acordo com a agência Xinhua, o programa AlphaGo é um jogo de Go desenvolvido pela equipe DeepMind, da Google, e é conhecido pelos fãs de xadrez chineses como o jogo Alpha Shit.

No artigo anterior, falamos sobre um algoritmo de rede neural que o Google está desenvolvendo para permitir que as máquinas aprendam de forma autônoma, e AlphaGo é um produto semelhante.

O vice-presidente e secretário-geral da Associação Chinesa de Automatização, Wang Feiyu, disse que os programadores não precisam ser proficientes em go, mas apenas saber as regras básicas do jogo. Atrás do AlphaGo há um grupo de cientistas de computadores proeminentes, ou melhor, especialistas em aprendizado de máquina. Os cientistas usam algoritmos de redes neurais para inserir os registros de jogos dos especialistas em jogo no computador e deixar o computador competir consigo mesmo, aprendendo constantemente no processo.

Então, onde está a chave para que o AlphaGo aprenda a ser um genio?

O que é um algoritmo de Monte Carlo?A forma mais comum de explicar o algoritmo de Monte Carlo é: Se houver 1000 maçãs na cesta, você pode escolher a maior cada vez que fechar os olhos. Então, você pode fechar os olhos e escolher aleatoriamente uma, e depois escolher aleatoriamente uma comparando com a primeira, deixando grande, e depois escolher aleatoriamente uma, comparando com a última vez, deixando grande. O ciclo é repetido, e quanto mais vezes você pegar, maior a probabilidade de escolher a maior maçã, mas a menos que você escolha uma de todas as 1.000 maçãs, você não pode ter certeza de que a escolha final será a maior.

Ou seja, o algoritmo de Monte Carlo é que, quanto mais amostras houver, mais soluções ótimas serão encontradas, mas não é garantido que sejam as melhores, porque se houver 10.000 maçãs, provavelmente haverá mais.

A comparação com ele é o algoritmo de Las Vegas: Diz-se que, se houver uma fechadura, há mil chaves para escolher, mas apenas uma é correta. Então, cada vez que você tentar abrir uma chave ao acaso, não abre, você muda uma outra. Quanto mais tentativas, maior a chance de abrir o melhor, mas até que você abra, as chaves erradas não são úteis.

Assim, o algoritmo de Las Vegas é a melhor solução possível, mas não é necessariamente encontrada. Suponha que, de 1000 chaves, não há nenhuma chave para abrir a fechadura, a chave real é o número 1001, mas na amostra não há o número 1001, o algoritmo de Las Vegas não pode encontrar a chave para abrir a fechadura.

Algoritmo de Monte Carlo do AlphaGoA dificuldade do Go é especialmente grande para a IA, porque há muitas formas de jogar o Go, e os computadores têm dificuldade em discernir. Em primeiro lugar, há muitas possibilidades de go-go. Em cada passo do go-go há muitas possibilidades, 19 × 19 = 361 opções de cascos. Em um jogo de 150 rodadas de go-go, podem surgir até 10.170 situações. Em segundo lugar, as regras são muito sutis e, em certa medida, a escolha de cascos depende da intuição formada pela acumulação de experiência.

O AlphaGo não é apenas um algoritmo de Monte Carlo, mas sim uma versão atualizada do mesmo.

O AlphaGo completou o jogo de xadrez através de um algoritmo de pesquisa de árvores de Monte Carlo e duas redes neurais profundas. Antes de enfrentar o Lichtenstein, o Google primeiro treinou o neuralétrico do AlphaGo com quase 30 milhões de passos de um humano contra um macaco, para que ele aprendesse a prever como um jogador profissional humano cairia.

A tarefa deles é cooperar e selecionar os passos mais promissores, abandonando os erros óbvios e, assim, controlar a computação dentro do alcance do computador. Isso é essencialmente o mesmo que os jogadores humanos fazem.

Segundo o pesquisador do Instituto de Automação da Academia Chinesa de Ciências, Yi Yanqiang, o software de xadrez tradicional, geralmente usando pesquisa violenta, incluindo computadores azuis, é o de criar árvores de pesquisa para todos os possíveis resultados (cada resultado é um fruto na árvore) e fazer pesquisas de rastreamento conforme necessário. Este método também tem alguma viabilidade em xadrez, xadrez, etc., mas não é possível para o Go, porque o Go percorre 19 linhas e a probabilidade de queda é tão grande que o computador não pode construir o fruto da árvore para realizar pesquisas de rastreamento. O AlphaGo adota um método muito inteligente que resolve o problema perfeitamente.

Dongachi explica ainda que uma das unidades mais básicas da rede neural profunda é semelhante aos neurônios do nosso cérebro humano, com muitas camadas conectadas como se fossem redes neurais do cérebro humano. As duas redes neurais do AlphaGo são redes estratégicas e redes de avaliação, respectivamente.

A rede de estratégias de xadrez é usada principalmente para gerar estratégias de caça. No processo de xadrez, não pensa no que deveria acontecer, mas no que aconteceria com os melhores jogadores humanos. Ou seja, ele prevê onde o próximo jogo acontecerá, com base em um estado atual do tabuleiro de entrada, e propõe algumas estratégias viáveis que estão mais de acordo com a mente humana.

No entanto, a rede estratégica não sabe se o que está fazendo é bom ou ruim, ela só sabe se o que está fazendo é o mesmo que o que faz o ser humano.

A rede de avaliações de tábuas avalia a situação de toda a placa para todas as hipóteses possíveis e dá uma tábua de chances de vitória. Estes valores são refletidos no algoritmo de pesquisa de árvores de Monte Carlo, que, repetindo o processo anterior, deduz o caminho com a maior chance de vitória. O algoritmo de pesquisa de árvores de Monte Carlo determina que a rede estratégica só continuará a deduzir onde a tábua de chances de vitória é mais alta, para que possa abandonar certos caminhos e não usar um caminho para o preto.

O AlphaGo usa as duas ferramentas para analisar a situação e julgar os pontos fortes e fracos de cada estratégia, assim como os jogadores humanos julgam a situação atual e deduzem a situação futura.

O algoritmo de Monte Carlo é, sem dúvida, um dos núcleos do AlphaGo.

Duas pequenas experiências Por fim, vejamos duas pequenas experiências com o algoritmo de Monte Carlo.

• 1.计算圆周率pi。

Princípio: primeiro, desenhe um quadrado, desenhe o seu círculo interior, e depois, desenhe um ponto de desenho aleatório dentro deste quadrado, definindo um ponto que cai dentro do círculo como P, então P = área do círculo / área do quadrado. P = ((Pi)RR) / ((2R * 2R) = Pi / 4, ou seja, Pi = 4P

Passos: 1. Coloque o centro do círculo no ponto inicial e faça um círculo com R como raio, então a área de um quarto do primeiro quadrado é PiRR/4 2. Faça o quadrado exterior de um círculo de 1/4, cujos coordenados são ((0,0) ((0,R) ((R,0) ((R,R), então o quadrado tem uma área de RR 3. Tire o ponto ((X, Y) de forma que 0 <= X <= R e 0 <= Y <= R, ou seja, o ponto dentro do quadrado 4. através da fórmula X.X+YRR determina se o ponto está dentro de um quarto da circunferência. 5. Se todos os pontos (ou seja, o número de experimentos) são N, e os pontos que estão dentro de um círculo de 1/4, (ou seja, os pontos que atendem ao passo 4) são M, então

Então, se eu fizer uma comparação, então eu vou fazer uma comparação.Imagem 1

M_C ((10000) é executado em 3.1424

• 2.蒙特卡洛模拟求函数极值，可避免陷入局部极值

# Em um intervalo [-2,2], gerar um número aleatoriamente, encontrar o y correspondente e encontrar o valor máximo considerado como o valor máximo da função em [-2,2]Imagem 2

Após 1000 simulações, o valor máximo foi encontrado como 185.12292832389875 (muito preciso).

Veja aqui, cara, você entende. O código pode ser escrito à mão. Traduzido de WeChat Public.