Matemática e teoria

Algoritmo do jogo do 15 — do BFS às bases de padrões

Quais algoritmos resolvem o jogo do 15, em ordem cronológica de invenção: BFS (anos 1960), A* (1968), IDA* (1985), bases de padrões aditivas (2002). Cada um é um avanço estrito sobre o anterior.

O jogo do 15 é um benchmark para algoritmos de busca em IA desde os anos 1960. Cada geração de algoritmo surgiu para derrubar o muro em que a anterior tinha batido. Este artigo percorre todas elas em ordem de invenção, mostrando em que cada uma se destacava e o que tornou a seguinte necessária.

Anos 1960 — busca em largura

É o primeiro algoritmo que todo mundo tenta. Ele explora os estados nível por nível: a profundidade 1 tem 4 estados, a 2 tem 16, a 3 tem 64, e assim por diante. Você continua explorando até encontrar o objetivo.

No jogo do 8, o BFS termina rápido: a profundidade do pior caso é 31, então são no máximo 4³¹ estados (bem menos na prática, por causa das revisitas). No jogo do 15, a profundidade mais difícil é 80, ou seja, 4⁸⁰ estados. Isso é mais estados do que átomos no universo observável. O BFS não termina.

O muro: explosão exponencial. Resolver por busca não informada é inviável além do 3×3.

1968 — busca A*

Hart, Nilsson e Raphael publicam A Formal Basis for the Heuristic Determination of Minimum Cost Paths. A ideia: em vez de explorar os estados em ordem de distância até o início, explorar em ordem de f = g + h, onde h é uma estimativa inferior da distância restante.

No jogo do 15, h é a distância de Manhattan: a soma das distâncias em linha e coluna de cada peça até sua posição-alvo. Manhattan é admissível (nunca superestima) e consistente (satisfaz uma desigualdade triangular). Com essas propriedades, o A* encontra a solução ótima.

Desempenho no jogo do 15: resolve qualquer tabuleiro, mas nas instâncias mais difíceis explora milhões de estados e consome centenas de megabytes de memória. O muro: memória.

1985 — IDA*

Depth-first iterative-deepening: An optimal admissible tree search, de Richard Korf. A sacada: em vez da fila de prioridade do A* (que guarda todos os estados explorados), fazer DFS com aprofundamento iterativo em que o limite é o custo f, e não a profundidade.

O IDA* explora os mesmos estados que o A* exploraria, mais ou menos na mesma ordem, mas sem se lembrar deles entre as iterações. Cada "varredura em profundidade" usa O(profundidade) de memória, e não O(estados explorados).

Desempenho no jogo do 15: resolve qualquer tabuleiro em segundos no hardware de 1985 e cabe em quilobytes de memória. O muro: a heurística continua sendo Manhattan. Acelerar a busca exige uma heurística mais justa.

Anos 1990 — conflito linear

Criticizing solutions to relaxed models yields powerful admissible heuristics, de Hansson, Mayer e Yung. A heurística de Manhattan assume que as peças podem passar umas pelas outras. Não podem.

O conflito linear soma 2 movimentos à heurística para cada par de peças que estão na mesma linha, pertencem as duas a essa linha, mas aparecem na ordem errada: uma delas vai ter que sair da linha para deixar a outra passar. O mesmo vale para as colunas.

Efeito: em geral, uma redução de 5–15% nos nós expandidos em tabuleiros difíceis do jogo do 15. É uma melhoria estrita sobre o Manhattan puro, sem desvantagem real.

1996 — walking distance

Uma heurística que captura mais a fundo a estrutura do quebra-cabeça. Para cada disposição de peças projetada apenas nas linhas (ignorando a posição dentro da linha), o algoritmo pré-calcula o número mínimo de trocas de linha necessário para colocar cada peça na linha certa. O mesmo para as colunas.

A walking distance é admissível e bem mais justa do que Manhattan + conflito linear: em geral 1,5–2× o valor de Manhattan, o que significa que o IDA* expande muito menos nós.

Custo de implementação: uma pequena tabela pré-calculada (~500 KB para um 4×4). É o ponto ideal para o jogo do 15.

2002 — bases de padrões aditivas disjuntas

Disjoint pattern database heuristics, de Korf e Felner. A heurística mais forte que se conhece para quebra-cabeças deslizantes.

A ideia: dividir as peças em grupos disjuntos (no jogo do 15, a divisão 7+8 é a padrão). Para cada grupo, pré-calcular o custo ótimo de levar só as peças desse grupo até suas posições-alvo, ignorando todas as outras. Depois, tabular todas as disposições possíveis do grupo.

Na hora da busca, você consulta a contribuição de cada grupo e soma. Como os grupos são disjuntos e os movimentos necessários para cada grupo não entram em conflito (sujeito a um argumento cuidadoso), a soma é admissível.

Custo de memória: cerca de 1 GB para o jogo do 15. Desempenho: resolve o jogo do 15 mais difícil em alguns milhares de expansões de nó, ou seja, milissegundos.

2005+ — bases de padrões maiores para quebra-cabeças maiores

A mesma técnica escala para o jogo do 24 (5×5) e além. Uma divisão 5+5+5+9 para o jogo do 24 ocupa cerca de 4 GB. Com ela, qualquer jogo do 24 aleatório se resolve em segundos.

O jogo do 35 (6×6) está no limite do tratável. As instâncias 6×6 mais difíceis continuam sendo objeto de pesquisa em 2026.

Anos 2010+ — heurísticas com redes neurais

Redes neurais foram treinadas para prever uma quantidade parecida com a distância de Manhattan em quebra-cabeças deslizantes, às vezes produzindo heurísticas mais justas do que as feitas à mão. O problema: em geral, as heurísticas neurais não são comprovadamente admissíveis, então os resolvedores construídos sobre elas devolvem respostas provavelmente ótimas, e não garantidamente ótimas.

Para artigos de pesquisa, isso é interessante. Para software em produção, onde a otimalidade importa (calibração de dificuldade em jogos), as bases de padrões clássicas continuam sendo a ferramenta certa.

Por que essa história importa

Cada onda de pesquisa em algoritmos de quebra-cabeças deslizantes veio da mesma pressão: o quebra-cabeça é pequeno o bastante para comparar algoritmos e grande o bastante para que os ruins estourem o tempo. O jogo do 15 foi o campo de testes de avanços gerais em busca heurística (A*, IDA*, bases de padrões) que hoje movem planejamento de rotas, demonstração de teoremas e muitas outras áreas.

Quando você resolve um jogo do 15 num aplicativo usando um botão de dica, está usando algoritmos desenvolvidos exatamente para esse jogo e depois generalizados para todo o resto.

Uma tabela-resumo

Ano Algoritmo Tempo para resolver jogo do 15 difícil Memória O que tornou possível
Anos 1960 BFS Não termina Enorme —
1968 A* + Manhattan Minutos Centenas de MB Busca heurística
1985 IDA* + Manhattan Segundos KB Aprofundamento iterativo
1996 IDA* + walking distance < 1 seg + 500 KB pré-calculados Heurística melhor
2002 IDA* + base de padrões 7+8 Milissegundos + 1 GB pré-calculado Enumeração de subconjuntos

Cada linha é um verdadeiro salto qualitativo, não uma melhoria marginal. A história da resolução do jogo do 15 é também a história da busca heurística moderna.

Por · Atualizado