O que á uma solução de Inteligência Artificial?

Técnicas de Inteligência Artificial provêem mecanismos para tornar a solução de problemas mais próxima à que um ser humano utilizaria, melhorando a forma de utilização do conhecimento, a capacidade de generalização e a capacidade de tomar decisões em situações imprevistas ou singulares. Nesse artigo, vamos comparar  soluções para dois problemas, partindo da  "menos inteligente" até a que mais se enquadra ao conceito de uma solução da Inteligência Artificial. Vamos analisar tais soluções frente a três características: complexidade de implementação, capacidade de generalização e utilização do conhecimento. Para cada uma delas, vamos propor uma estrutura de dados para representar o problema e um algoritmo.

Problema 1- Jogo da velha

Solução 1

Estrutura de dados

Vamos definir um vetor de 9 elementos, onde cada elemento possui um dos seguintes valores:

     0, se a casa estiver em branco

     1, se houver um X  na casa

     2, se houver uma O (bola) na casa

Assim sendo, esse vetor vai conter um número ternário (base 3).

Utilizaremos também uma tabela de movimentos que contém 19683 entradas (3 elevado a 9), que são as combinações possíveis dos 3 valores (combinações com repetição de 3 valores para 9 posições). Cada entrada dessa tabela contém a jogada a ser efetuada, desde que o estado do tabuleiro que representa seja viável segundo as regras do jogo.

Algoritmo

1-Visualizar o vetor representando o tabuleiro como sendo um número ternário. Converter esse número para a base 10.

2-Utilizar o número obtido como um índice na tabela de movimentos e acessar a entrada.

3-O estado sugerido pela entrada acessada no passo 2 será a próxima jogada.

Análise

No que diz respeito à complexidade, esse algoritmo é bem simples de ser implementado. O problema dele está no enorme trabalho braçal necessário à confecção da tabela de movimentos: as melhores jogadas para cada estado têm que ser precisamente previstas. A capacidade de generalização também é mínima: se quiséssemos estendê-lo para uma versão tridimensional, isso seria inviável em termos de memória necessária. Precisa de muito conhecimento acerca das melhores jogadas na confecção da tabela de movimentos. Sem esse conhecimento, não existe chance de jogar bem.

Solução 2

Estrutura de dados

O tabuleiro será representado por um vetor de 9 posições numeradas de 1 a 9, onde cada elemento será 2 se a casa estiver vazia, 5 se for O (bola) e 3 se for X.

A próxima jogada a ser feita será denotada por um inteiro de 1 a 9 correspondendo à posição no vetor.

Algoritmo

Subrotinas:

faça2:  tenta colocar 2 de suas peças em uma fileira (linha, coluna ou diagonal) de forma a ter chance de ganhar na próxima jogada

ganha (p): retorna zero se o jogador p não puder vencer no seu movimento seguinte. Caso contrário, retorna o número do quadrado que constituir um movimento vencedor.

jogue(n) : Fazer um movimento no quadrado n

O X faz os movimentos ímpares 

A bola  faz os movimentos pares

1-Jogue (1)

2-Se tabuleiro[5]= 2 então jogue(5) senão jogue(1)

3-Se tabuleiro[9]= 2 então jogue(9) senão jogue(3)

4-Se ganha(X) diferente de 0 então jogue(ganha(X)) senão faça2.

5-Se ganha(X) diferente de 0 então jogue(ganha(X)) senão se ganha(O) diferente de 0 então jogue(ganha(O)) senão se tabuleiro[7] = 2 então jogue(7) senão jogue(3)

6-Se ganha(O) diferente de 0 então jogue(ganha(O)) senão se ganha(X) diferente de 0 então jogue(ganha(X)) senão faça2

7, 8 ou 9 - Se ganha(EU) diferente de 0 então jogue(ganha(EU)) senão se ganha(OUTRO) diferente de 0, então jogue(ganha(OUTRO)) senão jogue(QUALQUER POSIÇÃO)

Análise

Essa solução é de implementação mais complexa, mas pode ser generalizada e depende menos do conhecimento de todas as jogadas possíveis, como na solução 1. Portanto, está mais próxima ao que se espera de uma solução de Inteligência Artificial.

Solução 3

Extrutura de dados

Uma árvore de possibilidades, onde cada elemento é um vetor de 9 posições. Cada elemento aponta para outros elementos que são os estados possíveis  no movimento seguinte. Cada estado possui um número, que corresponde à chance de levar à vitória. Esse número é obtido da seguinte forma:

                          Número de colunas, linhas e diagonais onde X ganha menos número de colunas, linhas e diagonais onde O (bola) ganha.

Assim sendo, quanto maior esse número, melhor a jogada para o X  e pior para o O (bola)

     

Algoritmo

1-Verifique se a posição analisada é a vencedora. Se for, escolha-a.

2-Caso contrário, analise os movimentos do opositor a partir de determinada possibilidade (dois níveis abaixo na árvore, que são as jogadas do opositor). Veja qual é a pior para nós e suponha que o opositor fará opção por ela (pois é também a melhor para ele).

3-Passe essa pior jogada   para o nível imediatamente anterior (que é o de nossas jogadas possíveis)

4-Escolha a menos pior (a que tem o melhor valor da função de avaliação para nós).

5-Opositor joga

6-Volte a 1

Análise

Essa solução é grande consumidora de memória e é bem mais lenta que as anteriores.Normalmente, soluções de Inteligência Artificial exibem essa característica. Entretanto é altamente generalizável (basta trocar o vetor de 9 elementos por um vetor de 27 elementos, por exemplo, para torná-lo 3D) e não exige  nenhum conhecimento das jogadas possíveis, como nas duas soluções anteriores. Essa seria a solução clássica fornecida pela Inteligência Artificial.

Problema 2 - Identificador de caracteres - reconhecimento de padrões

Esse problema consiste em se identificar  caracteres em um texto. Esses caracteres são capturados e armazenados em uma estrutura de dados. É exatamente o que os OCRs (identificadores ópticos de caracteres) fazem. O problema aqui restringe-se à etapa de identificar os caracteres já armazenados na estrutura de dados adequada.

Solução 1

Estrutura de dados

• Uma matriz quadrada que representa o formato do caracter. Cada pixel é representado por um  "1" na matriz e a ausência de pixel por um zero na matriz. Cada caracter a ser reconhecido tem sua representação nessa matriz e o conjunto de todos os caracteres constitui o padrão a ser identificado.
• Uma tabela de randomização (hash) onde cada letra do padrão possui um lançamento. A chave da tabela de hash é calculada assim:
• Tirar 3 linhas da matriz de zeros e uns
• Concatenar as 3 linhas
• Através de uma função de hash, transformar as linhas concatenadas em uma chave de acesso

Algoritmo

1-Transformar o caracter a ser identificado em uma matriz de zeros e uns

2-Tomar na matriz as mesmas 3 linhas que foram utilizadas para os padrões

3-Aplique a essas 3 linhas a mesma função de haxh utilizada para os padrões

Análise

• As letras a identificar devem se assemelhar com exatidão aos padrões (ou seja, é pouco generalizável e exige muito conhecimento acerca do formato dos caracteres)
• Se modificar a coleção de símbolos, modificamos também a tabela de hash, o que pode se tornar bastante complicado
• Um número grande de símbolos aumenta a chance de colisões na tabela de hash.

Solução 2

Estrutura de dados

• Matriz de zeros e uns idêntica à da solução 1
• Padrões conhecidos: um conjunto de vetores de tamanho N, sendo um vetor para cada caracter. Esses vetores são formados tomando-se a matriz de zeros e uns e dividindo-as em N regiões. O número de 1´s em cada região é contado e registrado na posição do vetor correspondente à região  N deve ser suficientemente grande para que cada padrão tenha um vetor diferente.

Algoritmo

1-Converter a matriz de zeros e uns em um vetor conforme descrito

2-Calcule a diferença entre os vetores do padrão e o vetor do caracter a ser identificado

3-O padrão que tiver a menor diferença é o escolhido.

Análise

Essa solução melhora bastante a anterior, uma vez que a base de padrões não precisa ser modificada se novos caracteres forem acrescentados. A capacidade de generalização aumenta também, uma vez que procuramos o caracter mais próximo, melhorando a identificação de caracteres de formatos diferentes  do padrão.

Solução 3

Estrutura de dados

• Matriz de zeros e uns idêntica à da solução 1
• As letras do padrão a ser identificado serão representadas por meio de descrições feitas via referências na matriz de zeros e uns. Essas descrições podem ser feitas por predicados, como por exemplo:
• ARCO (C1, C2) (um arco conectando as células 1 e 2 da matriz) AND
• RETA(C1, C3)   (uma reta conectando as células 1 e 3 da matriz)

Algoritmo

1-Encontre ARCOS e RETAS no caracter a ser identificado e crie a descrição 

2-Selecione o padrão que tenha a descrição mais próxima à criada em 1

Análise

Essa solução é a mais próxima do que se espera de uma solução de Inteligência Artiticial. Os problemas de diferenças de formato e tamanho dos caracteres encontrados nas outras duas soluções são aqui minimizados, sendo portanto, muito mais generalizável. Por outro lado, é mais lento e de implementação muito mais complexa.

Referências


RICH, Elaine. Inteligência artificial. São Paulo: McGraw-Hill, 1988. 

RUSSELL, Stuart J.; NORVIG, Peter. Inteligência artificial. Rio de Janeiro, Elsevier, 2004.