Inteligência Artificial
AI para simular raciocínio


Você está em: MarMSX >> Cursos >> AI   Vimos no capítulo anterior como dar um pouco de inteligência aos movimentos de um objeto na tela. Agora, nosso objetivo é fazer com que o MSX "pense" e seja capaz de jogar jogos de inteligência, como o jogo da velha.
  As técnicas apresentadas aqui poderão ser também cominadas com as técnicas comportamentais, fazendo com que um personagem seja ainda mais inteligente.
1. Jogada aleatória   Em um jogo o computador realiza uma jogada, escolhendo uma das opções possíveis aleatoriamente.
  Por exemplo, no jogo da velha é escolhida uma posição livre aleatoriamente.
Situação atual:
 X │   │
───┼───┼───
   │   │
───┼───┼───
   │   │

Locais possíveis para o "O":
 X │ O │ O
───┼───┼───
 O │ O │ O
───┼───┼───
 O │ O │ O

Uma dessas posições é escolhida aleatoriamente, sem qualquer tipo de análise!

  No jogo do 8-puzzle, devemos levantar todos os movimentos possíveis para a situação atual, e escolher um deles aleatoriamente. Por exemplo: 
Situação atual:
 1 │ 2 │ 3
───┼───┼───
 4 │ 8 │ 6
───┼───┼───
   │ 7 │ 5

Movimentos possíveis: peça 4 ou 7.

Nesse caso, uma das peças é escolhida e movida ao acaso!

  Esse tipo de jogada é literalmente um "tiro no escuro", pois o computador não avalia nada do que é feito e tampouco memoriza os erros e acertos. No caso do jogo da velha, as chances do computador perder são grandes e no 8-Puzzle é muito provável que o código rode infinitamente sem achar a solução do jogo.
  Entretanto, utilizar este tipo de jogada não é sempre condenável, pois há casos em que até os humanos devem dar um "tiro no escuro" para iniciar ou prosseguir em um jogo, como por exemplo a Batalha Naval. Nesse jogo, nada sabemos a respeito da posição dos navios até encontrar a parte de um deles. Assim, tanto o humano como o computador deverão "chutar" uma coordenada até encontrar uma parte, e então mudar a estratégia para completar o navio.

  O código em C para que o MSX solucione o jogo 8-puzzle aleatoriamente pode ser baixado aqui - arquivo "8pale.c".
2. Análise - heurísticas   Vimos na seção anterior que "dar um tiro no escuro" não ajuda muito a solucionar um problema, pois nada se sabe do que está sendo feito. Podemos melhorar essa situação, avaliando qual a melhor jogada a ser feita.
  Caso um determinado problema seja simples, basta utilizar alguma fórmula ou procedimento para resolver a questão. Entretanto, a solução para jogos normalmente é desafiadora e complexa. Nesse caso, devemos utilizar heurísticas para tentar solucioná-los.
  As heurísticas são soluções dadas para problemas em que não conhecemos a solução ou a melhor solução para ele. Para se ter uma idéia do que seja heurística, lembremos da brincadeira de cabra-cega. Alguém esconde um "tesouro" e uma outra pessoa vai em busca dele. A pessoa que está buscando o tesouro não sabe da localização dele, mas é informado pela pessoa que o escondeu se está "quente" ou "frio".
  No caso da brincadeira, a heurística é dar um passo, receber a classificação da posição e avaliar o movimento dado. Caso esteja "esquentando", significa que a direção de seu passo foi boa no sentido de encontrar o tesouro, e, conseqüentemente, que deva continuar naquela direção. Entretanto, caso esteja "esfriando", o movimento dado foi ruim e outra direção deverá ser tomada.


  -= O jogo do 8-puzzle =-

  No jogo do 8-puzzle, a solução do jogo é bem complexa, pois envolve diversas combinações de movimentos até chegar a configuração final (solução).
  Para solucionar o jogo, o computador deverá movimentar uma peça por vez, onde deverá testar todos os movimentos possíveis para a situação atual e avaliar qual o melhor movimento a ser dado [1]. É evidente que para avaliar a jogada, necessitamos realizar algum tipo de medida de eficiência. Uma medida possível é verificar o quão longe/perto o movimento de uma determinada peça o deixará de sua posição alvo (posição final da peça).

  Heurísticas:
  Jogada de exemplo:

 

  A distância pode ser medida como o número de movimentos de uma peça para atingir o alvo. Por exemplo, para o número 5 da imagem anterior, temos:

 

  Calcular a distância ao alvo DA: distância entre a posição atual de uma peça P(x,y) e a posição destino dela PA(xa,ya): 
DA = |x-xa| + |y-ya|

  Depois, calcular a distância do buraco DB: distância entre o buraco PB(xb,yb) e a posição destino da peça anterior PA(xa,ya): 
DB = |xb-xa| + |yb-ya|
  Obs: o buraco é o movimento futuro de uma peça.

  Por fim, devemos calcular a variação de distância que o movimento da peça irá causar: 
Δd = DB - DA

 

  Se for negativo, diminui a distância (bom). Se for positivo, a distância aumentou (ruim).

  No caso do 5, temos: 
DA = |3-2| + |3-2| = 1 + 1 = 2
DB = |2-2| + |3-2| = 0 + 1 = 1
Δd = 1-2 = -1

  Observe na figura abaixo que "mover a peça 5 para o buraco" representa uma vantagem, pois ela fica mais perto do alvo.

 


  Para a situação de jogo apresentada na primeira figura, temos os seguintes movimentos possíveis: 8, 7 e 5. Calculando os demais, temos: 
Para o 8:
DA = |2-2| + |2-3| = 0 + 1 = 1
DB = |2-2| + |3-3| = 0 + 0 = 0
Δd = 0-1 = -1

Para o 7:
DA = |1-1| + |3-3| = 0 + 0 = 0
DB = |2-1| + |3-3| = 1 + 0 = 1
Δd = 1-0 = +1

  Analisando os resultados, mover o 5 e o 8 são as melhores opções. Entretento, temos que escolher uma delas. Para desempatar, podemos:
  O código em C para que o MSX solucione o jogo 8-puzzle com análise pode ser baixado aqui - arquivo "8pheur.c".


  -= Batalha Naval =-

  No jogo Batalha Naval [2], quando encontramos uma parte da embarcação, o adversário é obrigado a revelar o tipo de embarcação atingida. Pela descrição, sabe-se o tamanho dela e sua posição na tela (horizontal ou vertical).
  Assim as heurísticas utilizadas no jogo para encontrar e afundar um navio são:

  As estratégias adotadas podem ser vistas em animações aqui.
3. Análise futura (árvore)   Podemos incrementar a análise de uma jogada, realizando uma previsão de N jogadas futuras. Dessa forma, além de avaliar cada jogada possível da situação atual, analisamos também as jogadas possíveis resultantes de cada uma delas.
  No exemplo do jogo 8-Puzzle da seção anterior, para a situação atual temos a possibilidade de mover as seguintes pedras para o buraco: 5, 7 e 8. Assim, para uma análise em 2 níveis, teríamos que avaliar também todos os novos movimentos possíveis resultantes da movimentação da pedra 5, da pedra 7 e da pedra 8 e depois combinar os resultados. Veja o diagrama a seguir.

 

  Observe que essa análise gera uma árvore, onde a raiz é a situação atual, o nível 1 os movimentos possíveis (5, 7 e 8) e o nível 2 (folhas) são os movimentos possíveis resultantes do nível anterior.
  A análise da jogada deve partir do nó até atingir cada folha, combinado os resultados.

  Por exemplo, mover o 5 e depois o 6 daria uma soma de -1+1 = 0.

 

  O código em C para que o MSX solucione o jogo 8-puzzle com níveis pode ser baixado aqui - arquivo "8ptree.c".
4. Competição   Nos jogos apresentados até aqui, as jogadas realizadas pelo computador NÃO sofriam qualquer interferência de outro jogador (eventos independentes). Até mesmo na Batalha Naval, é como se fossem dois jogos "solitários" em paralelo.
  Entretanto, em jogos como o jogo da velha, cada jogada de um participante irá influenciar a próxima jogada do adversário. Esse tipo de jogo é uma competição.


  -= Jogo da velha =-

  No jogo da velha, devemos avaliar a melhor jogada para nós e também tomar cuidado para não preparar uma boa jogada para o adversário. É um jogo de ataque e defesa.
  A heurística utilizada para ajudar o computador a realizar uma boa jogada é identificar se ela irá fazer com que seja gerada uma linha contendo mais "O"s do que as outras jogadas [1], caso o computador escolha o "O". No caso de gerar uma linha qualquer com três "O"s, essa deverá ser a jogada preferida, pois é a jogada vencedora. Além disso, por se tratar de uma competição, devemos também incluir as peças do adversário para a avaliação do movimento [1].
  Para avaliar uma jogada, criamos histogramas de "X"s e "O"s por linha, sabendo-se que são consideradas como linha todas as linhas, colunas e diagonais do tabuleiro.

 

  O histograma é um vetor de 0 a 3, onde: 
histO[0] = número de linhas com nenhum "O"
histO[1] = número de linhas com um "O"
histO[2] = número de linhas com dois "O"s
histO[3] = número de linhas com três "O"s

histX[0] = número de linhas com nenhum "X"
histX[1] = número de linhas com um "X"
histX[2] = número de linhas com dois "X"s
histX[3] = número de linhas com três "X"s
  Obs: somente as linhas sem nehuma peça do adversário são computadas nesse histograma [1].

  A influência de "O" é positiva e de "X" é negativa. Após criar os histogramas, uma equação [1] mede a eficiência da jogada: 
E = 128*histO[3] - 63*histX[2] + 31*histO[2] - 15*histX[1] + 7*histO[1]

  Pegue aqui a versão do jogo aleatória (velha1.c) e com a heurística (velha2.c) e compare os resultados.

  Podemos também realizar uma análise em dois níveis (árvore) para o jogo da velha. Porém, devemos observar que o primeiro nível é a jogada do computador e o segundo nível é a jogada do humano. Exemplo:

 

  Nesse caso, devemos considerar também nos cálculos a probabilidade de vitória do humano [1]: 
E = 256*histO[3] - 128*histX[3] - 63*histX[2] + 31*histO[2] - 15*histX[1] + 7*histO[1]

  Pegue aqui a versão do jogo em árvore (velha3.c).


  Referências:

  [1]- Inteligência Artificial em Basic, M. James, Editora Campus, 1985.
  [2]- Jogo Batalha Naval - MarMSX Development. Em: http://marmsx.msxall.com.
  [3]- Solving 8-Puzzle using A* algorithm. Em: http://blog.goodaudience.com.


<< Anterior   AI   Próxima >>