YouTube

Artigos Recentes

Qual é o atual ápice da Inteligência Artificial?

- Artigo atualizado no dia 16 de julho de 2019 -

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.

          Mas dois estudos recentemente publicados - um na Science e outros mais recente na Nature -, descreveram a criação de novos programas de IA - chamados AlphaZero e DeepCubeA -, os quais dominaram sozinhos diferentes jogos. O AlphaZero aprendeu sozinho a como jogar Go, xadrez e shogi (uma versão Japonesa de xadrez), se tornando imbatível nos três jogos. Já o DeepCubeA aprendeu a dominar também sozinho vários jogos (puzzles) de combinação, se tornando o segundo mais rápido resolvedor não-humano do famoso Cubo Mágico.

- 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 tornam 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. Seu desenvolvimento e sua performance foram descritos em um estudo publicado na Science (Ref.1).

- 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 -



   DEEPCUBEA

          O DeepCubeA, um algoritmo de aprendizado (via reforço de aprendizado) programado por cientistas da computação e matemáticos da Universidade da Califórnica, EUA, foi o mais recente avanço no campo da inteligência artificial, contribuindo para mais um importante passo nessa área. O algoritmo funciona usando valor aproximado de iteração para treinar uma rede neural profunda (DNN), e foi capaz de solucionar em uma fração de segundo, sem qualquer domínio específico de conhecimento ou orientação in-game de humanos, o tão desafiado Cubo Mágico. E isso não é uma tarefa simples, considerando que o cubo pode ser solucionado em bilhões de caminhos alternativos mas com apenas um estado possível de solução (cada uma das suas seis fases precisam estar apenas com lados de uma única cor), algo que aparentemente não pode ser encontrado apenas com movimentos aleatórios. Mais especificamente, são 4,3x1019 diferentes estados possíveis.



          No estudo descrevendo o DeepCubeA, publicado na Nature Machine Intelligence (Ref.2), os pesquisadores demostraram que essa IA resolveu 100% de todas as configurações de teste, encontrando o caminho mais curto de resolução de estado em 60,3% das vezes. Além disso, o algoritmo conseguiu trabalhar e resolver outros jogos combinatórios, como o Lights Out e o Sokoban, encontrando sempre o mais curto caminho de resolução na maioria dos casos verificáveis. É a primeira vez que um computador consegue resolver puzzles de alta dificuldade, os quais envolvem um pensamento mais simbólico, matemático e abstrato. Nesse sentido, a IA ficou perto de se tornar um sistema que pode pensar, racionalizar, planejar e tomar decisões.



           Os pesquisadores já tinham demonstrado em 2018 um algoritmo auto-didata que conseguia resolver o Cubo Mágico (Ref.3) - chamado de DeepCube -, e estavam interessados em entender como e porque a IA faz seus movimentos e quanto tempo levou para aperfeiçoar seu método de auto-aprendizagem. Para investigar isso, eles começaram com uma simulação computacional de um cubo completado e então o misturaram. Uma vez que um novo código otimizado estava pronto e operando (DeepCubeA), este treinou em isolamento por dois dias, resolvendo uma série de combinações com dificuldade cada vez crescente (total de 1000 combinações).

           O DeepCubeA - versão otimizada baseada no seu predecessor DeepCube (este o qual era inspirado no algoritmo do AlphaZero, MCTS) -, no final do seu auto-treino, precisou de apenas cerca de 20 movimentos para resolver o cubo e em 0,38 segundos, a maior parte das vezes requerendo o número mínimo de passos. Antes, a marca alcançada tinha sido 30 passos. Humanos que detêm o recorde de tempo mínimo para resolver o cubo precisam em torno de 50 movimentos. Os pesquisadores notaram que a estratégia da IA parece ser diferente daquela adotada por humanos.

          O DeepCubeA não é o primeiro algoritmo ou o mais rápido a solucionar o Cubo Mágico, porém é o primeiro que aprendeu a solucioná-lo sozinho com um sistema baseado em redes neurais de aprendizado. No MIT (Instituto de Tecnologia de Massachusetts), um robô já tinha sido criado - chamado min2phase algorithm - que resolvia o cubo três vezes mais rápido, porém essa era sua única finalidade e não aprendeu sozinho a dominar o puzzle (não era algo próximo de uma real IA), necessitando de domínio de conhecimento.

           A formidável performance do DeepCubeA sugere que ele pode ser usado para resolver problemas além de puzzles combinatórios, com potencial aplicação em áreas de planejamento, robótica e ciências naturais que lidam com amplos estados espaciais e poucos estados finais.

- 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. Apoiado no AlphaZero, o DeepCubeA não precisou de ajuda para se tornar um mestre no Cubo Mágico. 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. Já o DeepCubeA foi além das estratégias humanas para dominar os jogos combinatórios de puzzle. Estamos cada vez mais próximos de alcançarmos uma ambição há muito tempo almejada no campo das IAs: um sistema geral que possa dominar qualquer tipo de jogo e de problemas espaciais, um one to rule them all. E isso nos aproxima também de IAs só vistas hoje em obras de ficção-científica.


REFERÊNCIAS CIENTÍFICAS

  1. http://science.sciencemag.org/content/362/6419/1140 
  2. https://www.nature.com/articles/s42256-019-0070-z 
  3. https://arxiv.org/abs/1805.07470