YouTube

Artigos Recentes

Inteligência artificial aprende sozinha a jogar xadrez, Go e shogi, e se torna o melhor jogador do mundo nesses três jogos


Compartilhe o artigo:



          Desde que o programa Deep Blue derrotou o campeão mundial de xadrez em 1997, o campo de pesquisa em Inteligência Artificial (IA) tem marcado consideráveis avanços. E a medida desse progresso, em muitos casos, tem utilizado como base o desempenho da IA em populares e desafiadores jogos. Resultados animadores foram primeiro alcançados em jogos mais simples, onde a força bruta numérica era a única necessária, como o próprio xadrez, para depois os programas de IA avançarem para o complicado domínio do Go (1) e do Pôquer (2). Aliás, no ano passado, a IA desenvolvida pelo Google para o jogo Go - chamada de AlphaGo Zero - era auto-didata e derrotou os melhores jogadores do mundo (1). Todos esses avanços também possibilitaram que a IA se ramificasse para outras áreas, como dois recentes programas que aprenderam sozinhos a traduzir diferentes idiomas a partir de textos aleatórios (3).


          No entanto, esses programas são tipicamente construídos para um jogo em particular, explorando suas propriedades específicas, como as simetrias do tabuleiro onde são jogados. Ou seja, ainda não conseguem ser flexíveis o bastante para aprenderem novas habilidades e estratégias necessárias para outros jogos.

          Agora, em um estudo publicado na Science, pesquisadores descreveram a criação de um novo programa de IA chamado AlphaZero, o qual aprendeu sozinho a como jogar Go, xadrez e shogi (uma versão Japonesa de xadrez). E ele se tornou imbatível nos três jogos.

- Continua após o anúncio -



   ALPHAZERO

          Basicamente, o AlphaZero é uma versão evoluída do AlphaGo Zero, este o qual alcançou uma performance super-humana no Go ao reforçar seu auto-aprendizado ao jogar consigo mesmo repetidas vezes várias partidas. Nesse sentido, os pesquisadores generalizaram esse método em um único algoritmo - derivado dos mesmos algoritmos e arquitetura de rede do AlphaGo Zero - que consegue alcançar uma performance super-humana em vários jogos desafiadores. Dado apenas as regras de três jogos (xadrex, Go e shogi) aleatórios, o AlphaZero conseguiu derrotar de forma convincente um programa de IA campeão mundial para cada um desses jogos.




          O AlphaZero substitui as estruturas comuns de programação usadas em programas de game-playing com redes neurais profundas, um algoritmo de aprendizado reforçado para propósitos gerais, e um algoritmo de busca ramificado (tree) para propósitos gerais.

- Redes neurais: Ao invés de uma função avaliativa feita de forma manual e ordens de movimento heurísticas, o AlphaZero usa uma rede neural profunda (p, v) = fθ(s) com parâmetros θ. Essa rede neural fθ(s) toma a posição de tabuleiro s como uma entrada e libera um vetor de probabilidades de movimento p com componentes  pa = Pr(a|s) para cada ação a e um valor escalar v estimando o resultado esperado z do jogo a partir da posição sO AlphaZero aprende essas probabilidades de movimento e estimativas de valores inteiramente a partir de auto-play (jogando consigo mesmo várias vezes); esses parâmetros são usados então para guiar sua busca em jogos futuros.

- Algoritmo de busca: Ao invés de uma busca alfa-beta com melhoras domínio-específicas, o AlphaZero usa um algoritmo MCTS (Monte Carlo Tree Serch) de propósitos gerais. Cada busca consiste de uma série de jogos simulados a partir de auto-play que cruza uma 'árvore' (tree) a partir de uma estado de raiz sroot até um estado de 'folha' (leaf) ser alcançado. Cada simulação procede ao selecionar em cada estado s um movimento a com baixa contagem de visitas (não previamente explorado de forma frequente), alta probabilidade de movimento, e alto valor (média sobre os estados de folha de simulações que selecionam a a partir de s) de acordo com a atual rede neural fθ. A busca retorna um vetor π representando uma probabilidade de distribuição em termos de movimentos, πa = Pr(a|sroot).

- Reforço de aprendizado: Os parâmetros θ da rede neural profunda no AlphaZero são treinados via reforço do aprendizado com base no auto-play, começando a partir de parâmetros aleatórios inicializados θ. Cada partida é jogada ao se rodar um MCTS a partir da posição atual sroot = st na vez t e então selecionando um movimento, at ~ πt, seja proporcionalmente (para exploração justa) ou gananciosamente (para exploração injusta) em relação à contagem de visitas ao estado raiz. No final da partida, a posição terminal sT é pontuada de acordo com as regras do jogo para computar o resultado z: -1 para derrota, 0 para empate e +1 para uma vitória. Os parâmetros θ da rede neural são atualizados para minimizar o erro entre o resultado esperado vt;e o resultado da partida z e para maximizar a similaridade do vetor de política pt para a busca de probabilidades πt. Especificamente, os parâmetros θ são ajustados via descida gradual sobre uma perda de função l que resume sobre erros quadráticos e perdas de entropia-cruzada,


onde c é um parâmetro controlando o nível da regularização de peso L2. Os parâmetros atualizados são usados em partidas subsequentes de auto-play.

          Essas novas otimizações torna o AlphaZero bem diferente do AlphaGo Zero em vários aspectos. O AlphaGO Zero, por exemplo, estima e otimiza a probabilidade de vitória ao explorar o fato que as partidas de Go possuem um resultado binário de vitória ou derrota. No entanto, tanto o xadrez quanto shogi podem ter partidas terminadas empatadas. Aliás, acredita-se que a solução ideal para o xadrez é um empate (em termos de programação). Nesse sentido, o AlphaZero estima e otimiza o resultado esperado.

          Além disso, para acomodar uma ampla classe de jogos, o AlphaZero não assume simetria. O Go é simétrico, mas as regras do xadrez e do shogi são assimétricas. No xadrez, por exemplo, enquanto o peão pode se movimentar apenas para frente, as outras peças não; a rainha e o rei assumem movimentações em todas as direções, enquanto as outras peças são limitadas em uma ou duas direções. Outra diferença importante levada em conta pelo AlphaZero é que no shogi e no xadrez o jogo é posição-dependente, ou seja, dependendo da posição da peça, 'efeitos especiais' ocorrem, como no peão, onde esta peça pode avançar duas casas a partir da sua posição original no início da partida e pode ser promovido para outra peça quando alcança o final oposto do tabuleiro.

          O AlphaZero possui também uma rede neural que é continuamente atualizado e não espera uma interação ser completada para tal. No AlphaGo Zero, cada atualização espera o término de um treino, e baseia-se na comparação entre melhores jogadores.

- Continua após o anúncio -



PERFORMANCE

          O AlphaZero treinou de forma separada para cada um dos três jogos, em um total de 700 mil passos (em mini-pacotes de 4096 posições de treino) e englobando aproximadamente 9 horas no xadrez, 12 horas no shogi, e 13 dias no Go. Durante seu auto-aprendizado, o AlphaZero primeiro ultrapassou a performance do Stockfish no xadrez após apenas 4 horas (300 mil passos); no shogi, ultrapassou o Elmo em apenas 2 horas (110 mil passos); e, no Go, ultrapassou o AlphaGo após 30 horas (74 mil passos).


          Usando controles de tempo de 3 horas por partida, mais um adicional de 15 segundos para cada movimentação de peça, no Go, o AlphaZero derrotou o AlphaGo Zero, ganhando 61% das partidas. No xadrez, o AlphaZero derrotou o Stockfish, vencendo 155 partidas e perdendo 6 partidas em um total de 1000. No shogi, o Alpha Zero derrotou o Elmo, ganhando 98,2% das partidas quando jogando com as peças pretas, e 91,2% no geral.

          Em outras modalidades de partidas e controles de tempo - incluindo contra outras IA oponentes -, o AlphaZero continuou ganhando em todos os três jogos e por uma robusta vantagem, especialmente no shogi.

          E mesmo quando o AlphaZero era dado um tempo de busca 1/10 daquele do Stockfish para as jogadas (desvantagem), ele continuou derrotando esse programa no xadrez. E quando dado apenas 1/100 do tempo, ainda assim venceu 46% das partidas.

          E o mais impressionante é que o AlfaZero empregou uma taxa de busca de somente 60 mil posições por segundo no xadrez e no shogi, enquanto o Stockfish usava 60 milhões e o Elmo 25 milhões (confiavam mais na força bruta). Nesse sentido, o AlphaZero provavelmente estava compensando pelo número bem mais baixo de avaliações ao usar sua rede neural profunda para focar mais seletivamente nas variações com maior potencial de sucesso, uma estratégia mais humana de jogo.

- Continua após o anúncio -



   CONCLUSÃO

          Com um sistema altamente otimizado, o AlphaZero ultrapassou a performance de todas as atuais IA campeãs mundias em xadrez, shogi e Go. Via auto-aprendizado e com uma estratégia mais humana de jogar, o AlphaZero foi capaz de vencer a força bruta dos programas estado-da-arte para xadrez e shogi. Estamos um passo mais próximo de alcançarmos uma ambição há muito tempo almejada no campo das IAs: um sistema geral que possa dominar qualquer tipo de jogo, um one to rule them all. E isso nos aproxima também de IAs só vistas hoje em obras de ficção-científica.


Publicação do estudo: Science