Algoritmos capazes de resolver um cubo mágico já apareceram antes, mas um novo sistema da Universidade da Califórnia em Irvine usa inteligência artificial para resolver o quebra-cabeça 3D do zero e sem a ajuda de humanos. Como se não bastasse, ele faz isso com velocidade e eficiência impressionantes.
Uma nova pesquisa publicada esta semana na Nature Machine Intelligence descreve o DeepCubeA, um sistema capaz de resolver qualquer cubo mágico com que ele se deparar. De forma mais impressionante, ele pode encontrar o caminho mais eficiente para o objetivo — ou seja, a solução que requer o menor número de movimentos — em cerca de 60% das vezes. Em média, o DeepCubeA precisou de apenas 28 movimentos para resolver o quebra-cabeça, exigindo 1,2 segundo para calcular a solução.
Parece rápido, mas outros sistemas resolveram o quebra-cabeça em menos tempo, incluindo um robô que pode solucionar o cubo em apenas 0,38 segundos. Mas esses sistemas foram projetados especificamente para a tarefa, usando algoritmos escritos por humanos para resolver o quebra-cabeça da maneira mais eficiente possível. O DeepCubeA, por outro lado, aprendeu a resolver o cubo mágico usando uma abordagem de inteligência artificial conhecida como aprendizado por reforço.
“A inteligência artificial pode derrotar os melhores jogadores de xadrez e de Go do mundo, mas alguns dos enigmas mais difíceis, como o Cubo de Rubik, não foram resolvidos por computadores, então pensamos que eles estavam abertos para abordagens de IA”, disse Pierre Baldi, principal autor do novo artigo, em um comunicado de imprensa. “A solução para o cubo mágico envolve mais pensamento simbólico, matemático e abstrato, então uma máquina de aprendizagem profunda com o potencial de resolver um quebra-cabeça desses está mais próxima de se tornar um sistema que pode pensar, raciocinar, planejar e tomar decisões.”
De fato, um sistema especialista projetado para uma única tarefa — como resolver um cubo mágico — sempre será limitado a esse domínio, mas um sistema como o DeepCubeA, com sua rede neural altamente adaptável, poderia ser aproveitado para outras tarefas, como resolver problemas científicos, matemáticos e de engenharia complexos.
Além disso, esse sistema “é um pequeno passo em direção à criação de agentes capazes de aprender a pensar e planejar sozinhos em novos ambientes”, disse Stephen McAleer, coautor do novo artigo, ao Gizmodo.
O aprendizado por reforço funciona como o próprio nome diz. Os sistemas são motivados a atingir uma meta designada, período durante o qual eles ganham pontos por implantar ações ou estratégias bem-sucedidas e perdem pontos por desviar do curso. Isso permite que os algoritmos melhorem com o tempo e sem intervenção humana.
O aprendizado por reforço faz sentido para o cubo mágico, se levarmos em consideração o número absurdo de combinações possíveis no quebra-cabeça 3x3x3, que chega a cerca de 43 quintilhões. Simplesmente escolher movimentos aleatórios com a esperança de resolver o cubo simplesmente não funcionará, nem para os humanos nem para os supercomputadores mais poderosos do mundo.
O DeepCubeA não é a primeira tentativa destes pesquisadores da Universidade da Califórnia em Irvine. Seu sistema anterior, chamado DeepCube, usava uma estratégia convencional de busca de árvores e um esquema de aprendizado de reforço semelhante ao empregado pelo AlphaZero da DeepMind.
Mas, embora essa abordagem funcione bem para jogos de tabuleiro um-contra-um, como xadrez e Go, ela se mostrou desajeitada para o cubo mágico. Nos testes, o sistema DeepCube exigia muito tempo para fazer seus cálculos e suas soluções ficavam longe do ideal.
A equipe da UCI usou uma abordagem diferente com o DeepCubeA. Começando com um cubo resolvido, o sistema fez movimentos aleatórios para embaralhar o quebra-cabeça. Basicamente, ele aprendeu a ser proficiente no cubo mágico jogando ao contrário.
No início, os movimentos eram poucos, mas o estado de confusão se tornou cada vez mais complicado à medida que o treinamento progredia. Ao todo, o DeepCubeA jogou 10 bilhões de combinações diferentes em dois dias, enquanto trabalhava para resolver o cubo em menos de 30 movimentos.
“O DeepCubeA tenta resolver o cubo usando o menor número possível de movimentos”, explicou McAleer. “Consequentemente, os movimentos tendem a parecer muito diferentes de como um humano resolveria o cubo”.
Após o treinamento, o sistema foi encarregado de resolver 1.000 cubos mágicos aleatoriamente embaralhados. Nos testes, o DeepCubeA encontrou uma solução para 100% de todos os cubos e encontrou um caminho mais curto para o objetivo em 60,3% das vezes. O sistema precisou, em média, de 28 movimentos para resolver o cubo, o que acontecia em cerca de 1,2 segundo. Em comparação, os humanos solucionadores de quebra-cabeças mais rápidos do mundo precisam de cerca de 50 movimentos.
“Como descobrimos que o DeepCubeA está resolvendo o cubo no menor número de movimentos em 60% das vezes, fica claro que a estratégia que ele está usando está próxima da ideal, conhecida como algoritmo de Deus“, afirma Forest Agostinelli, coautor do estudo. “Embora as estratégias humanas sejam facilmente explicáveis com instruções passo a passo, a definição de uma estratégia ótima geralmente requer conhecimento sofisticado de teoria dos grupos e análise combinatória. Embora definir matematicamente essa estratégia não esteja no escopo deste artigo, podemos ver que a estratégia que o DeepCubeA está empregando não é imediatamente óbvia para os seres humanos.”
Para mostrar a flexibilidade do sistema, o DeepCubeA também foi ensinado a resolver outros quebra-cabeças, incluindo jogos de deslizar peças como Lights Out e Sokoban, o que ele fez com proficiência similar.
“Aplicamos nosso algoritmo a um total de sete quebra-cabeças e descobrimos que ele conseguiu resolver todos. Portanto, isso é uma evidência de que o método pode ser aplicado de modo mais geral”, disse Agostinelli. “Acreditamos que, dado apenas um objetivo e um método para trabalhar de trás para frente a partir desse objetivo, os algoritmos de inteligência artificial não só podem aprender a encontrar um caminho para o objetivo, mas também aprender a fazê-lo da maneira mais eficiente possível.”
Daqui para a frente, os pesquisadores da UCI gostariam de modificar o algoritmo DeepCubeA para realizar outras tarefas, como a predição de uma estrutura proteica, que poderia ser útil para o desenvolvimento de novos medicamentos. Eles também gostariam de usar as habilidades do sistema que são usadas na busca de caminhos para ajudar os robôs a navegar de maneira mais eficiente em ambientes complexos.