Inteligência Artificial em Javascript que vence humanos na Batalha Naval

Inteligência Artificial em JavascriptHá uns meses atrás participei num evento de inteligência artificial em que os participantes tinham de construir um agente em Javascript que deveria competir com outros agentes num jogo de Batalha Naval. Hoje venho aqui tornar o meu código open-source.

Experimenta o jogo aqui: http://cybtricks.com/dev/battleships-ai/

Sobre o jogo

A batalha naval é um jogo de tabuleiro em que o objectivo é afundar todos os navios do oponente. Se não conheces o jogo clica aqui para saberes mais.

O código do jogo encontra-se disponível neste repositório: https://github.com/daniel3303/battleships-javascript-artificial-intelligence

As quadrículas vermelhas indicam que acertaste num barco que ainda não foi afundado.

As quadrículas brancas indicam que acertaste num barco que ainda não foi afundado.

As quadrículas pretas indicam que acertaste num barco que ainda não foi afundado.

 

Abaixo deixo uma animação que mostra dois agentes inteligentes a jogar entre si.

Animação que mostra dois agentes inteligentes a jogar entre si.

 

Como funciona o agente inteligente?

Bem, eu não me vou prender com detalhes da implementação, vou antes focar-me no funcionamento do algoritmo desenvolvido.

Este agente cria uma tabela de utilidade (classe js\agents\UtilityGrid.js) sendo que dentro dessa tabela existem várias células  (classe js\agents\UtilityCell.js) que representam cada uma das quadrículas do tabuleiro de jogo. O agente em cada jogada limpa a tabela e preenche-a com os valores de utilidade estimados para cada quadrícula do tabuleiro utilizando várias heurísticas. Por fim será escolhida como alvo a quadrícula com o maior valor de utilidade. Caso existam duas ou mais quadrículas com o mesmo valor de utilidade será escolhida uma aleatoriamente.

 

Cálculo dos valores de utilidade

Em cada jogada a tabela de utilidade é iniciada com o valor 0 (zero) para cada umas das suas células. Um valor de utilidade 0 (zero) indica que o agente nunca irá escolher aquela posição e por isso todas as quadrículas do tabuleiro que já foram jogadas têm sempre utilidade 0 (zero). Um valor de utilidade maior que zero indica que o agente pode eventualmente escolher aquela quadrícula como alvo.

O valor de utilidade de cada uma das quadrículas do tabuleiro é calculado utilizando 3 heurísticas (dentro da pasta js\agents\heuristics) . Note-se que é possível adicionar novas heurísticas, basta extender a classe  js\agents\heuristics\AbstractHeuristic.js e registar o nova heurística na classe responsável por gerir a tabela de utilidades (classe js\agents\UtilityGrid.js).

 

Primeira heurística

A primeira heurística do jogo diz-nos que qualquer quadrícula que ainda não foi jogada é candidata à próxima jogada. O que esta heurística faz é adicionar 1 unidade de utilidade a cada uma das quadrículas de jogo que ainda não foi escolhida. Esta heurística tem um peso absoluto de 1.

Ao colocar dois agentes inteligentes a jogar um contra o outro utilizando apenas esta heurística teremos uma tabela de utilidade parecida com a da imagem abaixo.

Agente inteligente com apenas uma heurística
O valor dentro de cada uma das quadrícula do tabuleiro indica o valor de utilidade da mesma.

Uma vez que todas as quadrículas não jogadas têm o mesmo valor de utilidade e como é escolhida aleatoriamente uma quadrícula do conjunto de quadrículas onde o valor de utilidade é máximo, então o que este agente faz é basicamente jogar de forma aleatória.

Utilizando apenas esta heurística e ao colocarmos o dois agentes inteligentes a jogar um contra o outro obtive estes resultados:

Número de jogos: 100

Número médio de tiros por jogo: 91,96

Tendo em conta que o máximo de tiros que pode haver num jogo é 100, podemos concluir que este heurística sozinha é pouco útil.

 

Segunda heurística 

A segunda heurística do jogo diz-nos que é preferível jogar em quadrículas onde um navio cabe num maior número de posições diferentes. Esta heurística faz com que o agente prefira jogar em quadrículas onde ainda não foi disparado nenhum tiro nas suas redondezas. Esta heurística tem um peso absoluto de 10 (ou seja é 10x mais importante que a anterior).

 

Ao colocar dois agentes inteligentes a jogar um contra o outro utilizando apenas esta heurística teremos uma tabela de utilidade parecida com a da imagem abaixo.

Agente inteligente com apenas uma heurística

Podemos observar que as quadrículas perto das já jogadas (as brancas e as vermelhas) têm um valor de utilidade mais baixo, tipicamente 80. As mais afastadas têm valores mais altos.

Utilizando apenas esta heurística e ao colocarmos o dois agentes inteligentes a jogar um contra o outro obtive estes resultados:

Número de jogos: 100

Número médio de tiros por jogo: 89,00

 

Terceira heurística 

A terceira heurística do jogo diz-nos que uma vez atingido um navio preferimos acabar de afundar este navio antes de procurarmos outro. Esta heurística atribui um valor de utilidade maior às quadrículas que estão coladas a uma quadrícula onde sabemos que existe um navio, tendo em consideração a possível orientação do navio, ou seja, se atingimos duas vezes um navio jogando em duas quadrículas que estão na mesma linha então é mais provável haver um navio na horizontal do que na vertical.  Esta heurística tem um peso absoluto de 500 (é 50x mais importante que a segunda heurística e 500x mais importante que a primeira).

Ao colocar dois agentes inteligentes a jogar um contra o outro utilizando apenas esta heurística teremos uma tabela de utilidade parecida com a da imagem abaixo.

Agente inteligente com apenas uma heurística

Podemos observar que as quadrículas encostadas às vermelhas têm um valor de utilidade muito alto sendo que todas as outras têm o valor de utilidade 0.

Utilizando apenas esta heurística e ao colocarmos o dois agentes inteligentes a jogar um contra o outro obtive estes resultados:

Número de jogos: 100

Número médio de tiros por jogo: 53,60

 

Combinação das 3 heurísticas

Ao combinarmos as 3 heurísticas teremos uma tabela de utilidade semelhante à seguinte num determinado estado do jogo.  

Agente inteligente com três heurísticas

E ao colocarmos o dois agentes inteligentes a jogar um contra o outro obtive estes resultados:

Número de jogos: 100

Número médio de tiros por jogo: 36,20

Se ainda não experimentaste o jogo, experimenta: http://cybtricks.com/dev/battleships-ai/

E é tudo. Espero que tenham gostado do artigo.

Daniel Oliveira

Daniel Oliveira, 21 anos, vive em Lisboa e é estudante de engenharia informática no Instituto Superior Técnico. Adora desporto principalmente paintball, football, golf, kitesurfing, surfing, downhill mountain biking, rafting, zorbing e rock climbing. Apesar dos conteúdos do blog não joga nem gosta de jogar jogos de computador.

Deixar uma resposta

Este site utiliza o Akismet para reduzir spam. Fica a saber como são processados os dados dos comentários.