Relatorio Tecnico - Knight's Tour Bounded Look Ahead

[pic 1][pic 2][pic 3]

Relatório Técnico

Passeio do Cavalo utilizando Minimax com Antecipação Limitada

Discentes: Alonso Lucca Fritz, RA: 39927
Pedro Henrique de Moraes Xavier, RA: 136968

Docente: Adriana Postal

Inteligência Artificial

Ciências Exatas e Tecnológicas da Universidade Estadual do Oeste do Paraná

Bacharel em Ciência da Computação

Cascavel-PR, 20 de Maio de 2019

Índice

Resumo        3

Contexto do problema        3

Algoritmo de Busca        3

Testes        4

Problemas e Soluções        5

Considerações Finais        5

Referências Bibliográficas        6

Apêndices        6

1. Resumo

        A aplicação tem como objetivo resolver o problema conhecido como Passeio do Cavalo (NP-HARD), utilizando o método de Busca Minimax com Antecipação Limitada

1. Contexto do problema

O problema do Passeio de Cavalo consiste em uma sequência de movimento de um Cavalo em um Tabuleiro de Xadres, MxN, de tal forma que o a Peça visite todas as casas do tabuleiro apenas uma vez no seu trajeto. Existem dois casos diferentes que apresentam soluções, um em que o Cavalo termina em um quadrado que num próximo movimento pode-se alcançar a casa inicial conhecimento como Caminho Fechado, e outro em que ele completa a sequência de movimentos e termina em outro ponto do tabuleiro, neste caso ele é conhecido como Caminho Aberto.

Como objetivo principal deve-se encontrar uma solução final para o problema descrito, de forma que a solução não precise necessáriamente ser de Caminho Aberto ou Fechado, mas que apenas precise visitar todas as casas do Tabuleiro definido apenas uma vez.

A abordagem utilizada foi o método de Busca Minimax com Antecipação Limitada, tal método foi definido, ou seja, não foi escolhido por ser o melhor método a se utilizar para a solução deste problema.

Como a Abordagem utilizada não é a melhor para a solução do problema, foi necessário algumas adaptações com relação ao funcionamento do algoritmo, para que se pudesse obter uma solução final, a aplicação resolve o Passeio do Cavalo, para Tabuleiros que não sejam 3x3, 4x4 e nem para tabuleiros cujo número de Colunas e/ou Linhas seja menor que 3, já que considerando os possíveis movimentos da Peça Cavalo em um Tabuleiro de Xadrez, esses tamanhos de Tabuleiro não geram nenhuma solução possível.

1. Algoritmo de Busca

        Em uma solução utilizando uma Árvore Minimax, pode-se ver na árvore toda os valores referentes a “pontuação” em cada um dos níveis da árvore em qualquer ponto determinado durante o jogo. Visualizando essa árvore, um jogador pode ser capaz de prever quais movimentos são mais vantajosos. A Raiz da árvore representa a posição do jogador atual, dependendo do número de níveis a serem pesquisados, todos os níveis ímpares representam um jogador, enquanto os níveis pares representam outro.

        Em um jogo de dois jogadores, o primeiro se move com uma Pontuação MAX ou MIN, dependendo da forma da implementação, enquanto o segundo se move com a pontuação contrária do primeiro. A busca minimax é utilizada para determinar todas as possíveis continuações do jogo até o nível desejado. Uma pontuação/peso é originalmente atribuida a folha da árvore e, em seguida, avaliando cada conjunto possível de movimentos, uma pontuação/peso é atribuida ao nível superior pelo algoritmo minimax, ele realiza um percurso em pré-ordem e calcula as pontuações em tempo real, o mesmo resultado poderia ser obtido por um algoritmo recursivo simples. A complexidade do algoritmo é igual ao número de nós na árvore.

        Em grandes árvores torna-se impossível procurar todos os nós, a ideia do Algoritmo Minimax com antecipação é de certa forma “aparar” nossa árvore de possibilidades e fazer uma aproximação dessa forma “fingindo” ser uma boa solução. A diferença principal é que agora as pontuações não são mais exatas, mas sim aproximações instruídas. As pontuações/pesos obtidas são calculados com uma função de avaliação específica a qual é construída de forma diferente dependendo do problema que ela deve solucionar, porém ainda podemos empregar o algoritmo minimax para calcular as pontuações.

        A principal dificultade e diferença da implementação do método de Minimax com Antecipação Limitada é delimitar o Reach/Alcance que a árvore chegará até que seja feito a aproximação, desde que se forem utilizados Reachs/Alcances ruins perde-se totalmente a eficiência desta implementação.[pic 4]

1. Testes

        Para os testes optamos pela escolha de utilizar um tabuleiro com uma grande quantidade de Linhas e Colunas, dessa forma obtendo uma quantidade grande de posicoes possíveis para o Cavalo. Portanto para os testes foi utilizado um Tabuleiro 32x32, que gera um grafo com 1024 nos,  com o aumento da complexidade aumenta-se também o custo de processamento para cada recursão necessária, ou seja, quanto maior o alcance maior a complexidade e o custo de processamento.

        Para a validacao dos testes foram feitos 5 testes em cada um dos seguintes casos

        Tabuleiro 32x32, Alcance 1, Inicio 0
        Tabuleiro 32x32, Alcance 2, Inicio 0
        Tabuleiro 32x32, Alcance 4, Inicio 0
        Tabuleiro 32x32, Alcance 6, Inicio 0

        Segue no Apendice a Tabela referente aos testes e o Grafico demonstrando as suas diferenças.

1. Problemas e Soluções

1. Adaptação da Árvore

        Inicialmente considerando o Problema do Passeio do Cavalo, ele não apresenta uma solução que possa ser representada por meio de uma Árvore Binária, portanto optou-se pela utilização de um Grafo para representar as possibilidades escolhas para cada Casa do Tabuleiro, onde cada casa foi representada por um Nó o qual teria uma lista de ponteiro para cada um de seus possíveis movimentos.

...