A* e o N-Puzzle

Olá pessoal, aqui é o Lince. Bem vindos de volta.
Como vocês estão?

Algoritmos de busca poder ser utilizados para resolução de diversos tipos de problema, contando com que se possa transformar o problema em um grafo cujos nós são os estados que o problema pode assumir.

Este artigo será uma forma de mostrar a usabilidade do A* para outro tipo de busca, no qual não existe um mapa claro e no qual a navegação não é imediatamente intuitiva para as pessoas.

O problema apresentado é um jogo conhecido como N-Puzzle (sendo N podendo ser substituído pela quantidade de números no jogo) ou Tile Puzzle.

Figura 1: Configurações de um 8-Puzzle: Estado inicial embaralhado (esquerda); Estado resolvido (direita)

Neste jogo o jogador é apresentado com uma tabela de números embaralhados; seu objetivo é organizar os números em ordem crescente deslizando os quadrados para o espaço vazio e, um a um, colocando os números nas posições corretas.

Figura 2: Animação exemplo da execução de movimentos num 8-Puzzle

Planejando o AI

Para usar o A* para resolver um problema é necessário construir um grafo a ser navegado. O grafo precisa ter um ponto de partida e um objetivo. Para funcionar bem, o A* também precisa de uma boa heurística para guiar suas escolhas. Vamos atacar esses pontos um de cada vez.

Construindo o Grafo

Usaremos o código do A* já mostrado aqui antes, então a classe que representa o grafo deve implementar uma interface com uma função que retorna um vetor com os vizinhos de dado nó num grafo, outra função que retorna o custo entre dois nós vizinhos, e uma outra função que retorna o valor da heurística para dado nó. Essa classe será a TableGraph.

Uma classe para representar os nós do grafo, que representam possíveis estados da tabela. Essa classe é a TableNode.

Os vizinhos de um nó neste grafo são as tabelas a um movimento de diferença desse nó.

Figura 3: Estado inicial na esquerda e seus dois vizinhos na direita

O custo para se mover de um estado para qualquer um de seus vizinhos é sempre o mesmo, por conveniência usaremos o valor 1, que fará com que no final o custo seja igual ao número de movimentos necessários.

A Heurística

A heurística é a parte mais importante para o A* resolver o problema de forma eficiente. Um algoritmo de busca poderia, em tese, passar por todos os nós do grafo para decidir qual é o melhor caminho, em alguns casos isso é simplesmente impraticável, seja por restrições de tempo ou de memória. O objetivo da heurística é guiar a busca para que siga primeiro os caminhos que parecem mais promissores, em outras palavras, caminhos que parecem se aproximar do objetivo.

Por exemplo, no projeto do RPG Maker a heurística é a distância “geográfica” entre o nó atual e o objetivo, já que os nós possuem coordenadas associadas isso é intuitivamente fácil de calcular e compreender.

No nosso problema atual não temos coordenadas associadas, mas mesmo assim usaremos uma forma da heurística de distância, mais especificamente a Manhattan Distance, que calcula a distância apenas ortogonalmente. O nome se deve à distância de dois pontos nas ruas da cidade de Manhattan, que são todas a ângulos retos umas das outras.

A distância entre dois estados de um jogo será calculada como a soma das distâncias de cada número em um estado em relação ao mesmo número no outro estado. Consideremos os seguintes estados:

Figura 4: Estado embaralhado e estado final do jogo

Queremos calcular a distância do estado embaralhado (à esquerda) até o estado resolvido do jogo (à direita) usando a nossa heurística.

O número quatro está a um movimento de distância do número quatro do estado final, então somamos um à distância total, o número dois está no mesmo lugar então não somamos nada (somamos zero), o número cinco está a dois movimentos de distância, um no eixo horizontal e outro no vertical, então somamos dois à distância total. Fazendo isso para todos os números obteremos nosso valor da heurística, que neste exemplo é 8.

Figura 5: representação do cálculo da heurística

É importante lembrar que quanto menor o valor da heurística melhor é aquele caminho, ou seja, quanto menor a distância até o estado resolvido melhor.

Figura 6: Estado de um jogo (à esquerda) com os dois vizinhos e seus respectivos valores de heurística (à direita)

Na figura 6 vemos um exemplo do uso da heurística. Podemos mudar o estado atual do jogo (à esquerda) de duas maneiras diferentes (à direita), e para saber qual delas provavelmente é a melhor para resolver o problema consultamos a heurística, que nos diz que a segunda opção é melhor, pois está a uma menor distância do objetivo.

Nesse exemplo específico podemos verificar isso nós mesmos: na primeira opção estamos movimentando o número 2, que já está na posição desejada, enquanto que na segunda opção estamos movimentando o número 1 para a sua posição desejada, então essa opção provavelmente é melhor.

A Execução

Por último, vamos ver um pequeno exemplo do passo a passo da execução do algoritmo.

Figura 7: Grafo com apenas um nó, o ponto de partida da busca

Na Figura 7 vemos o estado inicial embaralhado a partir do qual iniciaremos a busca. O primeiro passo é adicionar ao grafo os nós vizinhos ao estado inicial.

Figura 8: Construindo o grafo

Na Figura 8 já temos diversas novidades em relação ao grafo anterior.

• Agora os nós estão numerados por ordem que foram adicionados no grafo, isso vai facilitar a identificação quando for necessário mencionar algum nó na explicação.
• Os nós 2, 3, e 4 estão circulados, isso significa que são novos e ainda não foram visitados pelo A*. Na literatura de Pathfinding isso é chamado de "Fronteira".
• Abaixo desses nós existe uma equação com dados sobre eles que será usada pelo A*: prioridade = custo + heurística. A prioridade é usada pelo A* para decidir qual é o próximo nó a ser visitado, os nós com menor prioridade são visitados primeiro; o custo é a quantidade de movimentos para chegar a esse estado partindo do estado inicial; e a heurística é o cálculo mencionado anteriormente.
• O nó cujo identificador estiver sublinhado (nesse caso, o inicial) é que está sendo analisado atualmente pelo A*.
• A seta que conecta os nós indica por onde ir para chegar no estado inicial.

Figura 9: Construindo o grafo

O próximo nó visitado foi o 3 que, apesar de ter a mesma prioridade que o nó 4, foi adicionado antes ao grafo, por isso é visitado primeiro. Acontece a mesma coisa logo em seguida, onde os nós 4 e 5 tem a mesma prioridade, mas o 4 é visitado antes.

Figura 10: Construindo o grafo

O modus operandi do A* é escolher qual dos nós ainda não visitados deve ser visitado a seguir de acordo com sua prioridade, então expandir o grafo a partir deste nó e repetir o processo até chegar no nó de destino.

Figura 11: Grafo concluído com caminho para resolução (Clique para expandir)

Após encontrar o nó de destino (circulado em vermelho na Figura 11), o A* retrocede pelas setas até o nó inicial memorizando os nós pelos quais passar. Estes nós memorizados representam o caminho a ser usado como a solução do problema.

Principal fonte de pesquisa: HeuristicsWiki N-Puzzle

Código fonte no Github

Então é isso, espero que tenham entendido e aprendido algo, qualquer coisa deixa um comentário aí. E como sempre vocês podem me encontrar no tuiter @LinceLazuli ou no email emailDoLince (arroba) gmail (ponto) com para qualquer dúvida, sugestão, crítica ou simplesmente se quiser trocar uma ideia.

Abraços do Lince.

Tweetar