A.I. Para Jogar o Ligue-Ligue

Olá pessoal, aqui é o Lince. Bem vindos de volta. Como vocês estão?
Vocês devem conhecer o App chamado My Talking Tom, aquele que você tem um gato virtual de estimação e que tem uns joguinhos que você pode brincar com ele. Então, um desses jogos é o Ligue-Ligue (Connect no original); em que você é apresentado com uma tabela de bolinhas coloridas e que tem como objetivo desenhar caminhos entre as bolinhas de mesma cor, sem cruzar com os caminhos das outras bolinhas e antes do tempo acabar.
Certa feita, enquanto jogava esse jogo tive a curiosidade de descobrir o quão sistemática poderia ser a resolução de suas fase. A partir desse pensamento resolvi esquematizar e implementar uma inteligência que, sendo alimentada com fotos da tela do jogo, me desse a resolução para a fase em questão.

Até então o resultado é o seguinte:

O vídeo mostra um script que abre uma pasta com imagens de telas de diferentes fases do jogo e, uma a uma, alimenta o AI, mostrando logo em seguida uma simulação de como seria a resolução de cada fase.

Perceba que duas destas fases não são totalmente resolvidas pelo AI (aos 1:30 do vídeo), tocaremos nesse ponto mais tarde.

O método utilizado foi dividir o software em duas partes: uma para reconhecimento e extração do puzzle a partir de uma imagem (a Visão) e outra para resolver o puzzle usando técnicas de I.A. (o Cérebro).

A Visão:

Os passos para extrair o puzzle são os seguintes:

• Descobrir quantos quadrados compõem o puzzle
  
  • As tabelas que compõem o puzzle têm tamanho variável; essa função tem como objetivo calcular quais são as dimensões da tabela
• Descobrir qual o conteúdo de cada quadrado do puzzle
  • Cada quadrado pode estar preenchido por quatro objetos diferentes: Um espaço vazio, um círculo colorido, um bloqueio, ou uma ponte.
  • O objetivo dessa função é identificar o conteúdo dos quadrados e compor um objeto com essas informações
  • Essa tarefa é feita através da comparação de cada quadrado com quatro modelos de como são os objetos. De acordo com o nível de semelhança entre o quadrado e os modelos é decidido qual é seu conteúdo.
  • Quando o conteúdo é identificado como círculo, precisa-se também identificar se é de uma ou duas cores, e qual são essas cores.

O Cérebro:

Resolver o puzzle usando técnicas de PathFinding para ligar os pares de círculos.

• O objeto construído pela Visão possui um grafo que representa a tabela do puzzle. Cada bloqueio e ponte representa uma modificação no grafo.
  • O bloqueio retira o nó correspondente do grafo.
  • A ponte duplica o nó corresponde e refaz as ligações com os vizinhos
• Por fim é feita uma lista com os círculos encontrados e a busca é feita de par em par, sendo que:
  • Quando se encontra o caminho entre o par, as ligações correspondentes ao caminho são temporariamente bloqueadas no grafo para a próxima busca;
  • Quando não encontrar o caminho entre o par, as modificações temporárias são desfeitas e a lista de pares tem a ordem embaralhada (lexicograficamente) para recomeçar a busca a partir do primeiro da lista.

Para exemplificar o processo de transformação de imagem para grafo, vejamos o seguinte exemplo:

Nele temos um bloqueio no canto superior-direito e uma ponte no centro. Começamos com um grafo em formato de grade que será modificado de acordo com os objetos que encontrarmos.

Fazendo uma leitura da imagem, linha após linha, encontraremos um bloqueio e deletaremos o nó da posição correspondente, deixando-nos com o seguinte grafo:

No quadrado localizado no centro da imagem identificamos uma ponte. Deve-se então duplicar o nó central e rearranjar as conexões. Finalizando com o seguinte grafo, que representa fielmente os possíveis caminhos para a imagem analisada.

Sobre as fases não resolvidas mencionadas anteriormente:

Existe mais um objetivo intrínseco no jogo que não falei antes justamente por que ainda não desenvolvi uma estratégia para corresponde-lo; a questão é que ao terminar os caminhos entre todos os círculos, não podem haver espaços vazios.

Então o que o AI resolve dessa forma:	Deveria ser resolvido dessa forma:

Depois de resolver essa questão o próximo passo óbvio seria construir uma mão robótica controlada por esse software para pegar o celular e jogar o jogo por si, consequentemente batendo todos o recorde do dono do celular. Alô alguém que trabalhe com robótica lendo aqui!

Observação: Assim que puder, colocarei todo o código fonte no github e linkarei aqui. Se alguém tiver interesse me avise que o deixo sabendo assim que eu o fizer.
Código fonte no Github

Então é isso, espera que tenham gostado das sugestões e consigam curtir os jogos tanto quanto eu os curto, qualquer coisa deixa um comentário aí. E como sempre vocês podem me encontrar no tuiter @LinceAssassino 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