Solvable Sokoban Without a Solver via Diffusion

No mundo da ciência da computação, existe uma classe de problemas tão complexos que verificar uma solução pode ser fácil, mas encontrá-la exige navegar por um labirinto de possibilidades tão vasto que levaria mais tempo do que a idade do universo para ser resolvido por força bruta. Estes não são meramente quebra-cabeças difíceis; são problemas onde o caminho para a resposta não é apenas longo, mas exponencialmente longo, o que significa que cada passo que você dá pode abrir um universo de novas possibilidades enquanto simultaneamente fecha outras. Um dos exemplos mais famosos disso é um jogo chamado Sokoban, jogado em uma grade onde um único personagem deve empurrar caixas para quadrados de destino específicos. O detalhe é que o personagem só pode empurrar, nunca puxar, e uma vez que uma caixa fica presa em um canto, ela frequentemente fica travada para sempre. Porque a posição de uma única caixa pode alterar completamente a alcançabilidade de todo o tabuleiro, o jogo não pode ser decomposto em tarefas pequenas e independentes. Resolvê-lo requer um plano holístico que considere cada interação antes que um único movimento seja feito. Durante décadas, a capacidade de gerar novos quebra-cabeças válidos deste tipo foi um desafio, porque criar um labirinto solucionável é tão difícil quanto resolver um, e verificar se um labirinto funciona geralmente requer um computador poderoso para simular cada movimento possível.

Um estudo recente descobriu uma maneira surpreendente de gerar esses quebra-cabezas complexos sem sequer ensinar o computador como resolvê-los. Pesquisadores treinaram um tipo de modelo de inteligência artificial para preencher partes faltantes de uma grade de Sokoban, de forma muito semelhante a um humano completando um palavras cruzadas ao adivinhar as palavras que faltam com base nas letras ao redor. O modelo foi exposto a milhares de quebra-cabeças reais e solicitado a aprender os padrões de paredes, pisos e caixas, mas nunca lhe foi dito quais quebra-cabeças eram solucionáveis, nem lhe foram dadas recompensas por criar um jogo funcional. Ele simplesmente aprendeu a prever qual peça deveria ir em um espaço oculto com base nas peças já visíveis. O resultado foi impressionante: quando o modelo gerou novos quebra-cabeças do zero, 77,4 por cento deles eram solucionáveis. Este é um resultado notável porque o modelo nunca foi explicitamente treinado para garantir a solucionabilidade; ele foi apenas treinado para preencher as lacunas. Os pesquisadores descobriram que a capacidade de criar um quebra-cabeça solucionável não era uma habilidade separada que o modelo aprendeu, mas um subproduto natural do aprendizado dos padrões locais do jogo.

O sucesso desta abordagem depende de como o modelo pensa sobre a grade. Programas de computador tradicionais que geram sequências, como aqueles que escrevem textos, trabalham em uma ordem fixa, decidindo a primeira palavra, depois a segunda, depois a terceira. Esta abordagem linear tem dificuldade com o Sokoban porque uma decisão tomada no início da grade pode restringir o que é possível no final da grade, criando um conflito que o programa não consegue corrigir posteriormente. O modelo usado neste estudo, no entanto, não segue uma ordem fixa. Ele começa com uma grade completamente vazia onde cada célula está oculta e as revela uma a uma em uma sequência aleatória. Em cada etapa, ele observa todo o tabuleiro como ele se encontra no momento — paredes aqui, caixas ali e espaços vazios em outros lugares — e decide o que pertence ao próximo espaço oculto. Isso permite que o modelo coloque uma parede em um canto e um objetivo no canto oposto, e então entenda o corredor que os conecta, ajustando sua compreensão de todo o tabuleiro com cada nova peça que revela. Esta flexibilidade espelha a maneira como um jogador humano deve pensar sobre o jogo, onde a dificuldade vem das interações não locais entre partes distantes do tabuleiro.

Para testar o quão bem este método funcionou, os pesquisadores geraram 50.000 novos quebra-cabeças e verificaram cada um com um resolvedor padrão. Eles descobriram que quase três quartos dos quebra-cabeças eram solucionáveis imediatamente. Ainda mais revelador foi o que aconteceu com os quebra-cabeças que falharam. Em 94,5 por cento dos casos não solucionáveis, o quebra-cabeça poderia ser corrigido simplesmente removendo uma única parede interior. Isso sugere que o modelo não estava apenas adivinhando aleatoriamente; ele estava criando estruturas que eram quase inteiramente corretas, com apenas erros menores e superficiais impedindo uma solução. Os pesquisadores também verificaram para garantir que o modelo não estava simplesmente memorizando os quebra-cabeças que viu durante o treinamento. Eles compararam os novos quebra-cabeças com o conjunto de dados original e descobriram que os quebra-cabeças gerados eram tão diferentes dos dados de treinamento quanto quebra-cabeças reais e inéditos. O modelo havia aprendido a estrutura subjacente do jogo, não apenas uma lista de exemplos específicos.

O estudo também explorou como o comportamento do modelo mudava quando os pesquisadores ajustavam sua confiança. Ao tornar o modelo mais decisivo em suas escolhas, eles puderam aumentar a taxa de solucionabilidade para quase 99 por cento, embora isso tenha ocorrido à custa da criação de quebra-cabeças com um pouco mais de paredes do que o habitual. A configuração padrão, no entanto, produziu quebra-cabeças que correspondiam perfeitamente à densidade de paredes encontrada no conjunto de treinamento original. Este equilíbrio entre estrutura e aleatoriedade é fundamental. O modelo aprendeu que, para um quebra-cabeça ser válido, as paredes e as caixas devem se encaixar de uma maneira muito específica e, ao aprender a preencher as lacunas corretamente, ele inadvertidamente aprendeu as regras de solucionabilidade. Os pesquisadores observaram que o desempenho do modelo na propriedade global de solucionabilidade continuou melhorando muito depois que sua capacidade de prever peças individuais havia parado de melhorar. Isso indica que os dois objetivos são distintos: um modelo pode ser bom em preencher uma única peça sem ser bom em criar um quebra-cabeça inteiro, mas, neste caso, dominar os detalhes locais foi suficiente para desbloquear a solução global.

As implicações desta descoberta estendem-se para além de apenas criar melhores quebra-cabeças. Demonstra que propriedades globais complexas podem emergir de objetivos de treinamento locais simples. O modelo nunca foi instruído de que um quebra-cabeça deve ser solucionável, mas aprendeu a criá-los de qualquer maneira. Isso sugere que a estrutura dos próprios dados contém a lógica da solução, e que um modelo capaz de compreender as relações entre todas as partes de um sistema pode herdar a capacidade de resolvê-lo. Os pesquisadores confirmaram que o modelo não estava usando um resolvedor oculto para guiar sua geração. Cada etapa do processo foi impulsionada pelas próprias previsões do modelo baseadas nas partes visíveis da grade. O fato de o modelo poder gerar um labirinto solucionável sem nunca ter visto o caminho da solução é um testemunho do poder de aprender os padrões de um sistema profundamente o suficiente para reproduzir suas propriedades mais difíceis.

No fim, o trabalho mostra que a barreira entre gerar um problema e resolvê-lo não é tão alta quanto se pensava anteriormente. Ao treinar um modelo para simplesmente completar um padrão, os pesquisadores desbloquearam a capacidade de criar desafios válidos e complexos. O modelo não precisava ser um grande mestre do jogo para criar um jogo que valesse a pena jogar; ele só precisava entender as regras das peças. Esta abordagem oferece uma nova maneira de pensar sobre a inteligência artificial, sugerindo que, se ensinarmos um sistema a compreender as relações locais dentro de um mundo complexo, ele poderá naturalmente aprender a navegar nos desafios globais desse mundo sem nunca ser explicitamente ensinado a fazê-lo. Os quebra-cabeças gerados não eram perfeitos, mas eram próximos o suficiente para que um pequeno ajuste pudesse fazê-los funcionar, provando que o modelo havia compreendido a essência do jogo.