Inteligencia Artificial

Para construir um programa que possa jogar xadrez, de especificar antes:

posição inicial;

regras que definem movimentos legais;

posições ou condições de vitória;

deixar implícito que a meta é ganhar e não apenas jogar.

A posição da partida pode ser descrita como uma matriz 8X8, em que cada posição contém um símbolo representando a peça correspondente em cada posição. peça correspondente em cada posição.

A posição inicial é representada pela matriz com as peças na posição oficial de abertura. posição oficial de abertura.

A meta é atingir qualquer posição de tabuleiro em que o oponente não tem um movimento legal e o rei está sob ataque.

Os movimentos legais fornecem o meio de ir do estado inicial para um estado meta. para um estado meta.

Estes movimentos podem ser facilmente descritos como um conjunto de regras conjunto de regras constituidas de duas partes:

se posição atual do tabuleiro, então posição seguinte do tabuleiro.

Teríamos de escrever uma regra distinta para cada uma das aproximadamente 10 aproximadamente 10120 posições possíveis do tabuleiro.

nenhuma pessoa consegue fornecer um conjunto completo de tais posições;

nenhum programa pode manipular todas estas regras.

É útil recorrer a estratégias apropriadas para reduzir o tamanho do espaço de busca sempre que isto for conveniente e possível.

Para obter este efeito, costuma-se recorrer aos métodos heurísticos, os quais, para acelerar a busca da solução, valem-se de informações disponíveis que permitem explorar o espaço de busca com economia e eficiência.

Resolver problemas difíceis exige com freqüência o comprometimento da sistematicidade, passando ao largo da exigência de encontrar a melhor solução, embora, em geral, boas soluções sejam detectadas.

A introdução de idéias heurísticas melhora a eficiência de um processo de busca ao sacrificar idéias de perfeição.

Com estes elementos é possível construir uma ÁRVORE DE BUSCA, cujo nodo raiz está associado a um estado inicial e onde os sucessores de qualquer nodo são associados aos estados obtidos através da aplicação das regras (associadas ou não às heurísticas) sobre a descrição do estado associado ao nodo.

Árvores são mais simples para busca que grafos. Primeiramente porque quando um novo nodo é gerado, podemos estar seguros que ele nunca foi visitado antes nem nunca será gerado depois.

Estratégias de Buscas

Busca às cegas - (Blind Search ou Uniformed Search Uniformed Search)

Uma estratégia de busca é dita "CEGA" se ela não leva em conta informações específicas sobre o problema a ser resolvido.

Existem basicamente duas estratégias cegas