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.