CayleyPy supera algoritmos clássicos na resolução de cubos de Rubik grandes

O projeto CayleyPy promove uma série de competições na plataforma Kaggle dedicadas a encontrar soluções ótimas para quebra-cabeças mecânicos cujo número de Deus é desconhecido. Em vez de algoritmos clássicos como o IDA* e a busca bidirecional em largura (BFS), que dependem de tabelas pré-calculadas (Pattern Databases), a CayleyPy aplica uma heurística neural treinável. No cubo de Rubik clássico 3×3×3, com diâmetro de grafo de 20 movimentos (métrica HTM, Tomas Rokicki, 2010), o sistema atingiu 98,4% de soluções ótimas — superando o DeepCubeA (60,3%) e o EfficientCube (69,6%).

Arquitetura: três passos das caminhadas aleatórias até a busca

O método é composto por três etapas. A primeira é a geração de amostras: parte-se de um cubo resolvido, embaralha-se aleatoriamente e salva-se, para cada estado, um par «configuração–distância até o início». A segunda é o treinamento: a rede neural aprende a prever a distância a partir do estado, tornando-se assim uma heurística de busca. A terceira é o Beam Search: o algoritmo mantém W das posições mais promissoras (normalmente W=5 ou W=40), avalia seus vizinhos e seleciona as W melhores. O processo se repete até a montagem do cubo ou até atingir o limite de busca.

Uma conclusão importante dos experimentos: aumentar o tamanho da amostra de treinamento rapidamente deixa de melhorar a qualidade da heurística, enquanto ampliar a largura do feixe reduz de forma consistente o tamanho da solução.

Do cubo 4×4 ao megaminx: avanços em diâmetros desconhecidos

No cubo 4×4×4, o espaço contém 7,4×10⁴⁵ estados (26 ordens de magnitude maior que o 3×3). O número de Deus é desconhecido; os limites conhecidos são de 32 a 53 movimentos na métrica BTM, com uma hipótese de 48 movimentos. A CayleyPy atingiu uma média de 46,51 movimentos no ranking final, superando Tomas Rokicki.

No megaminx (dodecaedro), o espaço de estados é de aproximadamente 1,01×10⁶⁸. A configuração Superflip (todas as arestas invertidas, com cantos e centros no lugar) era considerada uma candidata potencial à configuração mais distante do estado resolvido. Tomas Rokicki resolveu o Superflip em 55 movimentos na métrica FTM em maio de 2023. Herbert Kociemba estabeleceu em 2016 o limite inferior do diâmetro do megaminx: 48 movimentos em FTM.

Vladislav Kuznetsov, usando a CayleyPy, resolveu o Superflip em 47 movimentos em FTM em maio de 2026. Da desigualdade 47<48 decorre diretamente que o Superflip não é o antípoda do grafo de Cayley do megaminx, o que significa que ele não pode ser uma configuração que atinja o diâmetro. Tomas Rokicki chamou o resultado de «o primeiro grande e significativo avanço na aplicação de inteligência artificial à teoria dos quebra-cabeças mecânicos» (SpeedSolving.com).

Competições atuais: escala das tarefas e recursos disponíveis

O Kaggle está sediando competições para três cubos com número de Deus desconhecido:

• Cubo 5×5×5 (2,83×10⁷⁴ estados), com prêmio de 10.000 rublos para soluções com menos de 90 movimentos; • Cubo 6×6×6 (1,57×10¹¹⁶ estados); • Cubo 7×7×7 (1,95×10¹⁶⁰ estados).

O principal problema do aprendizado por reforço clássico nesse contexto é o sinal esparso: o agente só recebe informação útil ao atingir o estado-alvo, deixando centenas de passos intermediários sem qualquer retorno. A CayleyPy resolve isso com um sinal contínuo: a rede neural avalia cada estado intermediário com um número, permitindo que o algoritmo siga um gradiente em vez de vagar às ciegas.

Os participantes têm acesso a GPUs NVIDIA Tesla T4/P100 e TPUs v3-8/v5e-8 na plataforma Kaggle, ao código-fonte aberto do projeto (480 estrelas no GitHub) e a problemas sem solução há quatro décadas. É possível se juntar ao projeto por meio de Alexander Chervov no Telegram.