Inteligencia Artificial

Introdução

Análise Heurística

A Heurística vem do Grego e é um procedimento que, em face de questões difíceis envolve a substituição de respostas para um projeto, por outras de resolução mais fácil a fim de encontrar respostas viáveis, ainda que imperfeitas. Podendo tal procedimento ser tanto uma técnica deliberada de resolução de problemas, como uma operação de comportamento automática, intuitiva e inconsciente.

Sendo uma das técnicas mais importantes para começar a projetar experiências de usuário, é fazer a Análise Heurística que se trata de uma técnica de pesquisa e avaliação da usabilidade de um determinado projeto ou dos projetos concorrentes.

Baseia-se nos casos de uso e nas melhores práticas, buscando encontrar novas oportunidades e novos caminhos para entregar uma nova experiência com mais qualidades que possam surpreender o usuário.

Ao fazer uma heurística do projeto, devemos apontar os pontos fortes e fracos e propor recomendação para melhorias em um documento, descrevendo especificamente a situação.

Para desenvolver novas abordagens e conduzir uma reunião com a equipe, afim de encontrar a melhor solução do seu projeto.

No mercado existem inúmeras bases prontas de heurísticas, que podem ser muito específicas para determinados tipos de projetos, ou que podem ser mais abrangentes. A heurística mais conhecida e usada é de Jakob Nielsen. Nascido em 1957 em Copenhague na Dinamarca, é um cientista da computação com PHD em interação homem-máquina, sua heurística é basicamente a mais importante, porém aponta principalmente a usabilidade, deixando um pouco de lado a questão estética.

Já a mais completa, que aponta praticamente todos os fatores necessários foi criado por Abby Covert, uma arquiteta da informação americana que conseguiu fazer a versão mais aproximada entre design e usabilidade, se mantendo bem abrangente.

Uma análise heurística bem feita, pode oferecer uma compreensão sobre a qualidade do projeto e identificar quaisquer questões preocupantes ou que possam vir a prejudicar o seu desenvolvimento, também serve para identificar necessidades imediatas que podem levar a melhoras excelentes.

Busca Heurística estima qual o melhor nó da fronteira a ser expandido com base em funções heurísticas, tornando-se assim uma busca não exaustiva do espaço de estados, utilizando atalhos para sua exploração que descartam subespaços sem explorá-los. Em contrapartida, muitas vezes não se tem a garantia de sempre encontrar a melhor solução ou até uma solução em todas as instâncias do problema.

Alguns algoritmos de busca heurística global são: Busca gulosa, A*, RBFS, e SMA*. O algoritmo da busca gulosa pela melhor escolha tem como estratégia expandir o nó supostamente mais próximo a origem (heurística), através de uma estimativa. A distância do nó a expandir ao objetivo é estimada através de uma função heurística. Mas esta estratégia sofre dos mesmos problemas da Busca Exaustiva (cega) em Profundidade, fazendo com que ela não seja completa (pois pode ocorrer loops, por exemplo), não seja ótima (não encontra o menor caminho até o objetivo), e um pior caso de tempo e espaço da ordem de bm (b = fator de ramificação da árvore, e m = profundidade máxima do espaço de estados).

O algoritmo A* busca expandir o nó com menor valor Custo (Caminho) na fronteira do espaço de estados, utilizando a heurística Custo(Caminho) = Custo(Caminho Percorrido) + Custo(Caminho Restante) (f(n) = g(n) + h(n)), o que permite uma simplificação, eliminando caminhos redundantes. Como a exploração é em uma árvore de busca de largura primeira, este algoritmo tem vantagens e limitações parecidas à busca cega de custo uniforme. É uma estratégia completa, quando a heurística é admissível, isto é, quando ela sempre subestima o custo real (Custo (Caminho Percorrido)), para todo nó. Da mesma forma, é ótima para heurísticas admissíveis, garantindo mais eficiência do que qualquer outro algoritmo completo e ótimo usando a mesma heurística, e seu tempo e espaço são no pior caso O(bd), onde d = profundidade da solução de menor custo.

Este algoritmo A* tem algumas extensões, que tem o objetivo de limitar número de nós guardados na memória, já que o A* guarda todos os nós expandidos durante a busca. São eles: IDA*, que é semelhante à busca em aprofundamento iterativo, mas com a diferença de que o limite de expansão é dado por f(n) e não por d; Recursive Best-First-Search (RBFS), semelhante à busca recursiva em profundidade, com a diferença de que não desce indefinidamente na exploração, havendo um controle da recursão pelo valor de f(n), e se existir algum nó em um dos ancestrais que ofereça melhor estimativa que o nó atual, a recursão retrocede e a busca continua no caminho alternativo, sendo assim completa e ótima quando a heurística é admissível, com espaço O(bd) no pior caso e tempo difícil de se estimar; SMA* (Simple limited Memory A*), que utiliza toda a memória disponível, e quando a memória está cheia, ele elimina o pior nó folha (maior custo de f(n)) para continuar a busca, e é completa e ótima quando a memória alocada é suficiente.

O desempenho da busca deve está condicionado à qualidade da função heurística, que deve ser admissível e ter alta precisão (qualidade da distância do nó corrente ao nó objetivo).

Problema a ser solucionado

O Jogo do Quadrado

O Jogo do Quadrado utiliza o mesmo tabuleiro do Jogo da Velha. Os movimentos e as capturas de suas peças possuem algumas semelhanças com as peças peão e torre do jogo de xadrez. Descrevemos a seguir os materiais necessários, o objetivo e as regras do jogo.

• MATERIAL: Tabuleiro 3x3 e duas peças distintas, uma para cada jogador.

• INÍCIO DO JOGO: O jogo é disputado por dois jogadores, cada qual tem apenas uma peça. O Jogador 1 coloca a sua peça na extremidade esquerda inferior do tabuleiro e o Jogador 2 coloca a sua peça na extremidade direita superior do tabuleiro. O jogo é iniciado pelo Jogador 1, que é escolhido através de sorteio.

• OBJETIVO: Eliminar a peça ou chegar ao ponto de partida de seu adversário.

• REGRAS:

A. não pode voltar ao ponto de partida;

B. é permitida a eliminação da peça do adversário somente na diagonal e as peças se movem apenas uma casa na vertical ou uma casa na horizontal;