Entendendo o AlphaZero

Muito recentemente, surgiu a notícia de que a equipe de pesquisa DeepMind da Alphabet estendeu seu mecanismo de aprendizado de máquina para jogar Shogi e xadrez. Aparentemente, depois de apenas algumas horas de auto-aprendizado, ou seja, apenas jogando contra si mesmo, dadas as regras dos jogos, seu desempenho no xadrez já superou o dos principais motores atuais, como o Stockfish 8. Pessoalmente, ainda não sei exatamente como as partidas foram organizadas, como em que condição o Stockfish estava definido para executar, pois se o tempo de cálculo for limitado, os motores poderão ter um desempenho muito ruim. De qualquer forma, esta é uma conquista muito impressionante, porque, mesmo que alguém possa ter configurado o Stockfish de maneira ideal, com poucas horas adicionais de treinamento, o AlphaZero superaria novamente o nível de jogo, o que significa que o AlphaZero é fundamentalmente mais forte do que qualquer outro produto atual. mecanismo de xadrez padrão baseado em funções de avaliação heurística.

Agora, à luz dessas notícias, seria ótimo se alguém pudesse elaborar as principais diferenças no funcionamento de um mecanismo de xadrez aprendido por máquina em comparação com os motores padrão que estamos acostumados a usar. Mais concretamente:

1. A função de avaliação que o AlphaZero usa, treinada pelos métodos de aprendizado de máquina, não é apenas mais uma função de avaliação heurística? Em caso afirmativo, seria justo dizer que a diferença fundamental entre as funções de avaliação dos dois motores é o fato de o Stockfish ter uma função de avaliação otimizada ajustada manualmente por seres humanos, o que significa que a definição da função a ser otimizada é fixa, enquanto que, para AlphaZero, a função de avaliação de objetivos está sendo redefinida constantemente por meio de treinamento adicional (por exemplo, por meio da reprodução automática)? Tornando o último uma abordagem muito mais dinâmica.

2. Por fim, vagamente falando, um mecanismo como o Stockfish aplica sua função de avaliação à árvore de possíveis movimentos, decidindo quais galhos manter e quais cair, e então através de um concreto mais profundoNa análise de cada ramo, novamente por meio de sua função de avaliação, ele descobre qual ramo produziu o valor mais alto e que se torna a principal variação (é claro que existem muitas técnicas avançadas em torno desse processo para podar com eficiência essa árvore grande). Ou seja, para cada posição, essa rotina extremamente concreta precisa ser repetida para que o Stockfish tome uma decisão. Por outro lado, imagino que o AlphaZero faça algo muito diferente, ou seja, não se baseie em uma análise concreta da árvore de possíveis movimentos em uma determinada posição, mas sua função de avaliação atribui essencialmente um valor a essa posição (que intuitivamente é semelhante a colocar a posição atual em analogia a todas as outras posições para as quais foi treinada), sem ter que executar tarefas concretasanálise da maneira que Stockfish, ou mesmo um jogador humano faz. Essa é uma imagem sólida do funcionamento do AlphaZero ou de mecanismos de aprendizado de máquina com treinamento semelhante?

3. Sabemos que o espaço das posições no xadrez é grande o suficiente para que qualquer tentativa de amostrar todas as posições nele seja, em princípio, completamente em vão (complexidade EXPTIME), o que sugere que nenhuma quantidade de treinamento através do jogo automático seria suficiente para exploraram todas as posições, então como o resultado final pode ser bom, apesar de ter potencialmente explorado uma pequena fração de posições do espaço por meio da reprodução automática? Qual é a ideia principal aqui em jogo?

4. Meu palpite é que, o AlphaZero tem uma maneira muito ideal de comparar qualquer posição, mesmo que nova, com uma posição anteriormente visitada em seu conjunto de treinamento, quanto mais próxima a comparação, mais válida será a avaliação da avaliação. Por exemplo, quando jogou o movimento Bg5 no jogo 5 , ele deve ter explorado uma estrutura semelhante durante o treinamento, ou seja, é capaz de reconhecer que essa posição é essencialmente equivalente a (possivelmente uma completamente) diferente estudada em seu treinamento, em analogia com a forma como o reconhecimento de face é alcançado através do aprendizado de máquina e, como resultado, conclui que o Bg5 deve ser a melhor jogada, como foi nessa (ou nessas) outras posições semelhantes. Isso é um palpite correto? Não tenho ideia de como essa comparação feito, pois certamente não é possível armazenar todas as posições treinadas e analisá-las todas as vezes.

Esta é apenas uma tentativa de obter informações tão detalhadas sobre o funcionamento do AlphaZero e como ele chega a uma decisão dada uma posição.

• Como o AlphaZero seleciona uma jogada na pesquisa?

Isso é muito óbvio no jornal.

Cada simulação prossegue selecionando em cada estado um movimento a com baixa contagem de visitas, alta probabilidade de movimento e alto vale selecionando ...

O que isso significa? O AlphaZero treinou probabilidades para cada movimento (final da página 2 do artigo) de uma rede neural profunda. Durante a pesquisa, ele seleciona um movimento proporcional a essa probabilidade e também nós com baixa contagem (para garantir que o espaço de amostragem seja explorado). Este não é um conceito novo, o Monte Carlo Tree Search já estava na literatura antes da existência do Google.

------ (Muito) Exemplo aproximado ------

Temos uma posição e temos dois movimentos legais.

• O movimento 1 é bom e razoável
• O movimento 2 coloca seu próprio rei em perigo sem compensação

Segundo o artigo, um modelo profundo treinado pode estimar as probabilidades como (0,90, 0,10). Digamos que o AlphaZero use 4 iterações em Monte Carlo. As iterações podem ter a seguinte aparência:

Iteração 1 : Escolha o movimento 1 porque tem a maior probabilidade. Faça uma simulação a partir do movimento 1. Iteração 2 : escolha o movimento 1 porque ele tem a maior probabilidade. Faça uma simulação a partir do movimento 1. Iteração 3 : escolha o movimento 1 porque ele tem a maior probabilidade. Faça uma simulação do movimento 1.

Agora, estamos na iteração 4. Embora o movimento 1 tenha a maior probabilidade estimada, mas o movimento 2 não foi pesquisado ("baixa contagem de visitas" no artigo), agora o AlphaZero selecionaria o movimento 2 e faria a simulação.

Os dois movimentos seriam considerados, mas o AlphaZero colocaria mais recursos de computação no movimento 1 (coisa boa).

O AlphaZero escolheria a jogada com o melhor resultado esperado.

------------------ Suas perguntas: ------------------

A função de avaliação que o AlphaZero usa, treinada pelos métodos de aprendizado de máquina, não é apenas mais uma função de avaliação heurística?

A função de avaliação treinado é uma rede neural profunda, é não um conjunto de regras heurísticas, como o que você vê na Stockfish. Ninguém entende completamente (nem mesmo a equipe do Google) da rede treinada, apenas funciona. É assim que o NN geralmente funciona.

enquanto que para o AlphaZero, a função de avaliação de objetivos é constantemente redefinida através da função de avaliação de objetivos é constantemente redefinida por meio de treinamento adicional.

A função de avaliação no AlphaZero é um conjunto de neurônios treinados (viés + pesos). A equipe do Google usou máquinas muito poderosas para treinar os parâmetros. Geralmente, quanto mais recursos você pode investir no treinamento de um modelo de aprendizado profundo, melhores parâmetros você obtém.

(2)

O Stockfish usa alfa-beta, enquanto o AlphaZero usa Monte-Carlo. Eles são dois algoritmos muito diferentes. O algoritmo alfa-beta assume um limite inferior / superior, enquanto Monte-Carlo cria simulações da raiz à folha.

por ter explorado todas as posições, então como o resultado final pode ser bom, apesar de ter potencialmente explorado uma pequena fração de posições do espaço por meio do auto-jogo? Qual é a ideia principal aqui em jogo?

O Google não afirmou que havia resolvido o xadrez, nem mesmo suas máquinas poderosas poderiam enumerar todas as posições do xadrez. Mas eles não precisavam ... esse é o ponto do aprendizado de máquina, o modelo "aprende" com o conjunto de treinamento. Nesse caso, o conjunto de treinamento vem do jogo automático. A idéia principal é jogar o máximo possível de jogos de boa qualidade contra si mesma, o mais rápido possível.

Por exemplo, quando jogou o Bg5 no jogo 5, ele deve ter explorado uma estrutura semelhante durante o treinamento,

Não acho que o AlphaZero tenha encontrado exatamente a mesma posição nos jogos de treinamento. Eu acho que uma leitura rápida de Monte-Carlo é uma boa idéia:

https://chessprogramming.wikispaces.com/Monte-Carlo+Tree+Search

AlphaZero foi capaz de executar a jogada, alcançando profundidade suficiente. O algoritmo estima a probabilidade esperada de ganhar para cada jogada, aparentemente, a jogada Bg5 deu a maior probabilidade esperada.

Você pode pensar que o AlphaGo conseguiu pesquisar tão bem que viu a probabilidade de ganhar maior após o Bg5, enquanto o Stockfish não considerou a jogada com seriedade (e, portanto, perdeu).

Acho que minha pergunta seria como a rede neural "aprende" o que fazer em uma posição que não encontrou. Dizer que o AZ real executa um MCTS usando os pesos de viés + da rede neural treinada apenas retrocede um passo na maneira como a rede neural calcula esses valores. Se foi por meio de brincadeiras aleatórias, sem conhecimento humano, como ele decide como pesar uma posição que nunca viu?