CayleyPy aplica redes neurais ao cubo mágico, onde o número de Deus é desconhecido

O cubo mágico 3×3×3 tem cerca de 4,3×10^19 estados válidos e, desde 2010, sabe-se que qualquer um deles pode ser resolvido em no máximo 20 movimentos na métrica HTM. Tomas Rokicki e colegas chegaram a esse resultado com uma análise completa do espaço de estados. Para os cubos 4×4×4 e 5×5×5, os cubos grandes e o megaminx, o diâmetro exato do grafo de Cayley continua desconhecido. O projeto CayleyPy tenta abordar esses quebra-cabeças por outro caminho: busca com redes neurais, em vez de enumeração exaustiva. Um dos integrantes da equipe publicou no Habr uma análise do pipeline e dos resultados das competições.

O quebra-cabeça como grafo

A formalização é simples. Os vértices do grafo de Cayley são os estados válidos do quebra-cabeça, e as arestas são os movimentos permitidos. Resolver com o menor número de movimentos vira um problema de caminho mais curto entre o vértice atual e o estado resolvido. O diâmetro do grafo, isto é, o máximo das distâncias mínimas entre todos os pares de vértices, é justamente o "número de Deus".

Para o 3×3×3, esse cálculo foi possível, embora tenha exigido recursos computacionais consideráveis e o uso de simetrias para reduzir o espaço. À medida que o quebra-cabeça cresce, o quadro muda. O 4×4×4 tem da ordem de 7,4×10^45 estados, e o 5×5×5, cerca de 2,8×10^74. Percorrer o grafo inteiro aqui é impossível. Restam heurísticas, estimativas de limite superior e inferior e a busca por soluções subótimas, que vão reduzindo aos poucos a distância até o ótimo desconhecido.

O que faz o CayleyPy

O CayleyPy é uma biblioteca aberta em torno da qual foi montada uma série de competições no Kaggle. O objetivo é encontrar caminhos ótimos e subótimos em grafos de Cayley com um número enorme de vértices. Os participantes enviam soluções, e a plataforma as verifica e as classifica pelo comprimento dos caminhos encontrados. Para os pesquisadores, é uma forma gratuita de testar ideias em um benchmark comum; para os organizadores, é um jeito de reunir muitas abordagens diferentes para um mesmo problema matemático.

Segundo o anúncio, no artigo o autor analisa três pontos:

• a arquitetura do pipeline de redes neurais do CayleyPy;
• os resultados dos concursos já encerrados;
• as regras das competições atuais para cubos grandes, nas quais ele participa como membro da equipe.

O trecho disponível não traz números sobre o comprimento dos caminhos encontrados nem sobre a colocação das equipes. Por isso, só o texto completo permite avaliar o quanto a abordagem com redes neurais supera a busca clássica. O título do original afirma justamente isso: a rede neural supera os métodos clássicos. Quais métricas e quais algoritmos de referência foram usados na comparação não dá para saber a partir do anúncio.

Por que a abordagem importa além dos cubos

O esquema geral é bem conhecido: a rede neural aprende a estimar a distância até o objetivo, e o algoritmo de busca usa essa estimativa para não expandir ramos desnecessários. É assim que funcionam também trabalhos anteriores que resolvem o cubo mágico com aprendizado por reforço. O valor está no fato de o grafo de Cayley ser um laboratório matemático limpo. Ele tem respostas exatas para os casos pequenos, complexidade escalável e uma métrica de qualidade inequívoca. Se um método funciona no 3×3×3, é possível testá-lo no 4×4×4 e além, observando onde ele falha.

Os grafos de Cayley descrevem grupos de permutações, e por isso as estimativas de diâmetro e a busca por caminhos curtos interessam à combinatória e à teoria de grupos. Estruturas comparáveis aparecem em problemas de roteamento e em topologias de rede, embora ainda seja cedo para tirar conclusões aplicadas a partir de uma única publicação.

O que fazer com isso, se você é engenheiro

Se você trabalha com busca e heurísticas, o repositório aberto do CayleyPy no GitHub e as competições no Kaggle são uma plataforma pronta para testar suas próprias ideias em um problema cuja resposta pode ser medida em número de movimentos. Um bom começo é pelos quebra-cabeças pequenos, em que o diâmetro é conhecido, comparando a estimativa de distância da rede neural com o valor exato. Depois, vale passar aos cubos grandes, onde o que se disputa é o comprimento das soluções encontradas.

É importante ter em mente uma limitação: trata-se de uma análise feita por um participante do projeto, não de uma pesquisa independente. Qualquer afirmação de superioridade sobre a busca clássica precisa ser conferida nas tabelas de resultados concretas e nos solvers usados na comparação.