# **Manual Técnico**

<div align="center">

## Projeto Fase 1 - Jogo do Cavalo
### Unidade Curricular de Inteligência Artificial

Prof. Filipe Mariano e Prof. Joaquim Filipe
>Realizado por Pedro Moura (202100110) e Rui Jesus (202100279)


</div>

---

## **2. Arquitetura do Sistema**

A arquitetura da presente solução encontra-se dividida em 3 ficheiros principais:

- Projeto.lisp
- Responsável por carregar os restantes ficheiros de código
- Operações de *input e output*
- Interações com o utilizador
- Puzzle.lisp
- Código relacionado com o problema específico
- Procura.lisp
- Contém todos os algoritmos implementados no projeto

A divisão em causa representa os 3 principais elementos lógicos do projeto, e visa acima de tudo, representar diversas camadas de abstração.

Sendo este um problema de procura em espaço de estados, com algoritmos concebidos para uma implementação genérica, procurámos desde início promover a máxima abstração entre as funções relativas a estas operações e à estrutura relativa ao Jogo do Cavalo, promovendo a capacidade de aplicar o sistema relacionado com o puzzle a qualquer outro problema.

## **3. Entidades e a sua Implementação**

Para a realização do presente projeto, foi necessária a implementação de diferentes entidades e Tipos Abstratos de Dados, que permitissem a relação entre o código LISP e o domínio da aplicação.
As mesmas serão enumeradas no presente capítulo, através da sua identificação e descrição

### **3.1. Estado**
Elemento fundamental de qualquer algoritmo de procura, um estado visa caracterizar o problema num determinado momento da execução.
Direcionado ao domínio da aplicação, neste projeto o estado representará o tabuleiro e os pontos a atingir, associados ao problema. Através dos operadores do problema, estes estados sofrerão alterações, até que se alcance um estado solução, neste caso representado pelo número de pontos <=0.

<p style="text-align: center;"><img src="https://i.brainking.com/rules/kfight/01.gif" alt="drawing" width="250" align="center"/></p>

Recorrendo à notação BNF, o estado será representado através da expressão:

<Estado> ::= ( {<Pontos>} {<Tabuleiro>} )
<Tabuleiro> ::= ({Linha}*10)

E em lisp, tomará a forma seguinte:

   (<PONTOS> (
    (<              Linha 1              >) 
    (<              Linha 2              >) 
    (<              Linha 3              >) 
    (<              Linha 4              >) 
    (<              Linha 5              >) 
    (<              Linha 6              >) 
    (<              Linha 7              >) 
    (<              Linha 8              >) 
    (<              Linha 9              >) 
    (<              Linha 10              >)
    ))

Tomemos como exemplo a estrutura de um tabuleiro gerado aleatoriamente:

(2000 (
    (94 25 54 89 21 8 36 14 41 96) 
    (78 47 56 23 5 49 13 12 26 60) 
    (0 27 17 83 34 93 74 52 45 80) 
    (69 9 77 95 55 39 91 73 57 30) 
    (24 15 22 86 1 11 68 79 76 72) 
    (81 48 32 2 64 16 50 37 29 71) 
    (99 51 6 18 53 28 7 63 10 88) 
    (59 42 46 85 90 75 87 43 20 31) 
    (3 61 58 44 65 82 19 4 35 62) 
    (33 70 84 40 66 38 92 67 98 97)
    ))

Este TAD visa assim representar o **Tabuleiro** no âmbito do domínio da aplicação, através dos seguintes operadores:
- `estado-tabuleiro` - Devolve o tabuleiro do estado
- `estado-pontos` - Devolve o número de pontos restantes do estado

### **3.2. Nó**

Para execução do algoritmo de procura, é fundamental a existência de um tipo de Dados que permita a caracterização dos elementos necessários em cada nó do grafo. Para tal, definimos o TAD Nó, que visa caracterizar não só o estado, bem como o custo do mesmo e os seus antecessores, permitindo assim a construção desta árvore.

<p style="text-align: center;"><img src="https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/1200px-Binary_search_tree.svg.png" alt="drawing" width="300" align="center"/></p>

Recorrendo à notação BNF, o nó poderá ser caracterizado da seguinte forma:

Nó :== ({<Estado>} {<Profundidade>} {<Valor Heurística>} | nil {<nó pai>})
<Estado> ::= ( {<Pontos>} {<Tabuleiro>} )
    <Tabuleiro> ::= ({Linha}*10)
<Profundidade> :== <number>
<Valor Heurística> :== <number>
<Nó Pai> :== (<Nó> | nil)

Tomando como exemplo determinado nó ao longo de uma iteração:

(
;Estado
((20 ((NIL NIL 44 NIL NIL NIL NIL NIL NIL NIL) 
(NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL) 
(NIL NIL T NIL NIL NIL NIL NIL NIL NIL) 
(NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL) 
(NIL NIL NIL 22 NIL NIL NIL NIL NIL NIL) 
(NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL) 
(NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL) 
(NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL) 
(NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL) 
(NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL))) 
2 ;Profundidade
0 ;Heuristica

;Nó pai
((50 ((NIL T 44 NIL NIL NIL NIL NIL NIL NIL) 
(NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL) 
(NIL 3 30 NIL NIL NIL NIL NIL NIL NIL) 
(NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL) 
(NIL NIL NIL 22 NIL NIL NIL NIL NIL NIL) 
(NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL) 
(NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL) 
(NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL) 
(NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL) 
(NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL))) 
1 
0
(...........................)

Podemos interagir com este TAD através das seguintes operações

- `no-estado` - Devolve o estado do nó
- `no-profundidade` - Devolve a profundidade do nó
- `no-heuristica` - Devolve o valor da heurística do nó
- `no-pai` - Devolve o nó pai do nó
- `no-custo` - Devolve o custo do nó *(g+h)*

### **3.3. Solução**
Após a execução do algoritmo, sentimos a necessidade de construir um TAD que permitisse armazenar e processar a informação extra, obtida durante a sua execução, mas que não é pertencente ao nó, relativa, por exemplo, ao número de nós gerados aquando da execução da solução.

Este tipo de informações, serão assim essenciais à estrutura de estatísticas, responsáveis por apresentar a solução.

Com recurso à notação BNF podemos representar esta solução da seguinte forma:

Solução ::= ({<no-inicial>} {<no-solucao>} {<nr-abertos>} {<nr-fechados>} {<tempo-execução>} )

Poderemos interagir com este TAD através das operações seguintes:
- `dados-solucao_no-inicial` - Nó inicial do algoritmo
- `dados-solucao_no-solucao` - Nó solução pós execução
- `dados-solucao_nr-gerados` - Número de nós gerados no algoritmo
- `dados-solucao_nr-expandidos` - Número de nós expandidos
- `dados-solucao_tempo-execucao` - Tempo de execução do algoritmo

### **3.4. Escolha**
Após a interação com o utilizador que define as diferentes escolhas utilizadas ao longo da execução do algoritmo, existiu a necessidade de guardar este tipo de informação numa estrutura facilmente acessível ao longo do projeto.

Desta forma surgiu o TAD Escolha, responsável por armazenar estaas diferentes informações ao longo do algoritmo

Com recurso à notação BNF podemos representar esta solução da seguinte forma:

Solução ::= ({<Algoritmo>} {<Profundidade>} {<Heuristica>})

Poderemos interagir com este TAD através das operações seguintes:
- `escolha-algoritmo` - Algoritmo escolhido pelo utilizador
- `escolha-profundidade` - Profundidade escolhida pelo utilizador
- `escolha-heuristica` - Heurística escolhida pelo utilizador

## **4. Algoritmos e a sua Implementação**
O presente capítulo visa apresentar a descrição dos Algoritmos implementados na solução bem como a forma como os mesmos são executados.

### **4.1 Descrição Teórica**
Antes de contextualizar a execução dos algoritmos, é necessária a introdução teórica ao conceito por detrás dos mesmos.

Como é sabido, o processo de representação do espaço de estados prende-se assim com o conceito de nó, onde cada nó do grafo representa um estado do problema, com alguma informação adicional.

A solução é obtida aplicando operadores às descrições dos estados até que surja a descrição do estado final.

### **4.1.1 BFS - Breadth First Search**

O algoritmo BFS, denominado muitas vezes por busca em largura, é um método de procura não-informada, expandido e examinando sistematicamente todos os vértices de determinada árvore.

Este realiza assim uma busca exaustiva, onde começa pelo nó raiz, explorando todos os seus nós sucessores, e assim por diante.

Para garantir que nenhum nó será visitado mais que uma vez, utiliza duas listas, abertos e fechados, garantindo a ordem de chegada dos vértices e controlando a ordem correta de execução do algoritmo.

Este apresenta o seguinte pseudocódigo:

BuscaEmLargura
   escolha uma raiz s de G
   marque s
   insira s em F
   enquanto F não está vazia faça
      seja v o primeiro vértice de F
      para cada w ∈ listaDeAdjacência de v faça
         se w não está marcado então
            visite aresta entre v e w
            marque w
            insira w em F
         senao se w ∈ F entao
            visite aresta entre v e w
         fim se
      fim para
      retira v de F
   fim enquanto

### **4.1.2 DFS - Depth First Search**

O algoritmo DFS, denominado muitas vezes por busca em produfindade, é um método de procura não-informada, expandido e examinando sistematicamente todos os vértices de determinada árvore.

Este realiza assim uma busca exaustiva, onde começa pelo nó raiz, explorando tanto quanto possível cada um dos seus ramos, antes de retroceder.

À semelhança do BFS, este utiliza o conceito de listas para perceber a ordem correta de expansão dos sucessores, bem como para conservar o historial dos nós já explorados na árvore.

No âmbito da procura em espaço de estados, muitas vezes a procura em profundidade não termina, podendo inclusive existir um comprimneto de caminho infinito. Desta forma, é essencial existir igualmente um limite de aumento na profundidade da árvore.

Este algoritmo apresenta o seguinte pseudocódigo:

BuscaEmProfundidade
   escolha uma raiz s de G
   marque s
   empilhe s em P
   enquanto P não está vazia faça
      seja v o topo da pilha P
      para cada w ∈ listaDeAdjacência de v faça
         se w não está marcado então
            marque w
            empilhe w em P
            visite aresta entre v e w
         senao
            se w ∈ P então
               visite aresta entre v e w
            fim se
         fim se
      fim para
      desempilhe v de P
   fim enquanto

### **4.1.3 A***
O Algoritmo A*, é um algoritmo de procura informada, onde, através dos valores de duas funções, G e H, visa estimar o melhor caminho em relação ao custo, onde:

- G - Valor do custo acumulado do caminho percorrido
- H - Valor estimado restante do custo necessário até o destino

A soma dos dois valores acima estimam o caminho mais eficiente de um ponto inicial até o ponto final. O resultado dos valores acima é representado com a letra F e quanto menor for esse valor, menos custoso será o trajeto calculado.

Este algoritmo assenta assim no conceito de heurística, que visa, através de conhecimento empírico do problema, estimar a "qualidade" de determinado estado e qual a distância prevista entre este e a solução.

É possível representar o A* através do seguinte pseudocódigo:

A*
   inicializar a lista aberta (openList) com o nó inicial
   inicializar a lista fechada (closedList) como vazia

   enquanto openList não estiver vazia faça
      selecionar o nó com o menor custo total na openList (já ordenada -> primeiro nó) (custo total = custo do caminho até o nó + heurística do nó)
      mover o nó selecionado da openList para a closedList

      se o nó selecionado for o objetivo então
         retornar o caminho encontrado até o nó objetivo

      para cada vizinho w do nó selecionado faça
         se w estiver na closedList então
            continuar para o próximo vizinho

         custo_do_caminho = custo_do_caminho_do_nó_selecionado + custo_do_caminho_entre_nó_selecionado_e_w
         
         se w não estiver na openList ou custo_do_caminho < custo_do_caminho_armazenado_em_w então
            atualizar o custo_do_caminho_em_w para custo_do_caminho
            atualizar a heurística_de_w para a estimativa de custo do caminho de w até ao objetivo
            atualizar o nó pai de w para o nó selecionado
            se w não estiver na openList então
               adicionar w à openList
               ordenar openList

   fim enquanto

### **4.1.4 IDA***
O Algoritmo IDA* - Iterative Deepening A*, é um algoritmo de procura informada, onde à semelhança do A*, através dos valores de duas funções, G e H, visa estimar o melhor caminho em relação ao custo, onde:

- G - Valor do custo acumulado do caminho percorrido
- H - Valor estimado restante do custo necessário até o destino

Este algoritmo encaixa-se no ramo dos algoritmos *memory-bounded*, de memória limitada, que surgem com a premissa de olhar para os recursos computacionais como um bem não infinito.
Desta forma, surgiu a necessidade de fazer a pesquisa parametrizando o limite de memória disponível, tendando manter a sua eficácia e otimização.

O IDA* procura assim atribuir um limiar para a profundidade, dado pelo valor de f, onde este é incrementado para o menor valor da iteração anterior.

Após cada iteração, o corte da árvore é feito pelo menor valor da iteração que excede o limite.

É possível representar o IDA* através do seguinte pseudocódigo:

IDA*
   limite_global = h(nó_inicial)  
   enquanto verdadeiro faça
      limite_local = limite_global  
      resultado = busca_em_profundidade_limitada(nó_inicial, 0, limite_local)  
      se resultado = ENCONTROU_SOLUCAO então
         retornar SOLUCAO_ENCONTRADA
      senão se resultado = LIMITE_ATINGIDO então
         limite_global = próximo_limite()  
      senão
         retornar NAO_HA_SOLUCAO
   fim enquanto

busca_em_profundidade_limitada(nó, custo_acumulado, limite)
   f = custo_acumulado + h(nó)  
   se f > limite então
      retornar LIMITE_ATINGIDO
   se nó é o objetivo então
      retornar ENCONTROU_SOLUCAO
   mínimo_limite_excedido = INFINITO
   para cada vizinho w do nó faça
      resultado = busca_em_profundidade_limitada(w, custo_acumulado + custo(nó, w), limite)
      se resultado = LIMITE_ATINGIDO então
         mínimo_limite_excedido = mínimo(mínimo_limite_excedido, custo_acumulado + custo(nó, w) + h(w))
      senão se resultado = ENCONTROU_SOLUCAO então
         retornar ENCONTROU_SOLUCAO
   fim para
   se mínimo_limite_excedido = INFINITO então
      retornar LIMITE_ATINGIDO
   senão
      retornar próximo_limite()  

### **4.2 Implementação**

O presente capítulo visa detalhar a implementação da estrutura do projeto, bem como de cada um dos algoritmos implementados, efetuando uma ponte entre os seus fundamentos teóricos e a sua execução prática

#### 4.2.1 Geral

Como descrito no ponto de arquitetura, o presente projeto possui 3 componentes principais, correspondentes aos seguintes ficheiros:

- **Projeto.lisp**
- Responsável por carregar os restantes ficheiros de código
- Operações de *input e output*
- Interações com o utilizador
- **Puzzle.lisp**
- Código relacionado com o problema específico
- **Procura.lisp**
- Contém todos os algoritmos implementados no projeto

De um ponto de vista lógico, o programa inicia na função `iniciar`, que lança primeiramente uma Interface de utilizador que pede a seleção do problema, existindo a possibilidade de selecionar um tabuleiro do ficheiro fornecido pelo enunciado, bem como de gerar aleatoriamente um tabuleiro para 2000 pontos.

Após a leitura do tabuleiro, é selecionado, também pelo utilizador, o algoritmo a executar, dentro dos algoritmos disponibilizados pela solução. No caso dos algoritmos de busca informada, é ainda possível escolher a heurística em causa, e no caso do DFS a profundidade máxima desejada.

De um ponto de vista técnico, a função `iniciar` é assim responsável pela chamada do algoritmo, executado através da função `medir-tempo-execucao`, função essa que será responsável por perceber o tempo decorrido durante a execução da procura.

Ao algoritmo, serão assim fornecidos o nó inicial, a função de predicado de solução, a função de gerar sucessores, os operadores e os campos específicos do seu domínio (profundidade/heurística.)

Após conclusão do algoritmo, serão executadas as funções de `escrever-no`, responsáveis pelo output no ficheiro e ecrã da solução, assentando na mesma o caminho escolhido, o nó inicial, e os dados estatísticos relevantes.

#### 4.2.1.1 Operadores

No presente projeto, foram implementados 8 operadores, que visam representar os movimentos possíveis do cavalo em cada um dos estados. Estes foram implementados com base no seguinte código de exemplo, representativo do operador 1:

(defun operador-1 (estado)
  (let* (
         (tabuleiro (estado-tabuleiro estado))
         (posicao (posicao-cavalo tabuleiro))
         (linha-cavalo (first posicao))
         (coluna-cavalo (second posicao))
         (movimento-tabuleiro (substituir linha-cavalo coluna-cavalo estado))
         (nova-linha (+ 2 linha-cavalo)  )
         (nova-coluna (1- coluna-cavalo))
         (novo-estado  (substituir nova-linha nova-coluna movimento-tabuleiro 'T  ))
         )
    (cond (novo-estado
           ( -ou-simetrico (celula nova-linha nova-coluna tabuleiro ) novo-estado  ))
          (T nil)
          )
    
    ) 
  )

Como é possível verificar, este operador manipula assim o tabuleiro, visando devolver um novo estado com a nova posição do cavalo. É este operador o responsável pelo processo de movimento do cavalo, bem como de execução do operador `duplo-ou-simetrico`, que como frisado no enunciado do projeto:

> *"Se a casa escolhida tiver um número com dois dígitos diferentes, por exemplo 57, então, em consequência, o número simétrico 75 é apagado do tabuleiro, tornando esta casa inacessível durante o resto do jogo. Ou seja, nenhum cavalo pode terminar outra jogada nessa casa."*
>
> *"Se um cavalo for colocado numa casa com um número "duplo", por exemplo 66, então qualquer outronúmero duplo pode ser removido e o jogador deve escolher qual em função da sua estratégia (por default remover a de maior valor). Depois de um jogador deixar a casa para se movimentar para outra, a casa onde estava fica também inacessível para o jogo, ficando o numero da casa apagado.
> "* in Projeto Nº 1: Época Normal - Inteligência Artificial

#### 4.2.2 BFS

Apresentada a estrutura geral do funcionamento da solução, analisemos a implementação do algoritmo BFS no projeto. Esta, assentou assim no princípio teórico do mesmo, seguindo os passos seguintes:

- Nó inicial => ABERTOS
- Se ABERTOS vazia falha.
- Remove o primeiro nó de ABERTOS (n) e coloca-o em FECHADOS
- Expande o nó n. Colocar os sucessores no fim de ABERTOS, colocando os ponteiros para n.
- Se algum dos sucessores é um nó objectivo sai, e dá a solução. Caso contrário vai para 2.
> in Documentação da Unidade Curricular

A aplicação destes princípios resultou na função:

(defun bfs (noinicial objetivofunc funcsucessores operadores &optional (abertos (nos-iniciais noinicial)) (fechados nil))
   "Função de cálculo do algoritmo bfs"
  (if (null abertos) nil 
    (let* ((nodo (car abertos))
           (novos-fechados (cons nodo fechados))
           (sucessores_nao_filtrados (funcall funcsucessores nodo operadores 'bfs) )
           (final_sucessores (remove-if #'(lambda (nfechado) (no-existep nfechado fechados 'bfs))  sucessores_nao_filtrados ))
           (novos-abertos (abertos-bfs  (cdr abertos) final_sucessores))
           (existe-solucaop (remove-if-not #'(lambda (n) (funcall objetivofunc n)) final_sucessores)))
      (if (null existe-solucaop) (bfs noinicial objetivofunc funcsucessores operadores novos-abertos novos-fechados )
        (list noinicial (car existe-solucaop) (length novos-abertos) (length novos-fechados))
        )
      )
    )
  )

Como explicado na descrição do TAD Solução, este algoritmo, devolverá uma lista da forma:

Solução ::= ({<no-inicial>} {<no-solucao>} {<nr-abertos>} {<nr-fechados>} {<tempo-execução>})

#### 4.2.3 DFS
Semelhante ao BFS, a procura em profundidade troca essencialmente a ordem com que se coloca os sucessores em ABERTOS, sendo que, no presente algoritmo, estes são colocados no início, para que todo o ramo seja explorado. É importante notar ainda a verificação da profundidade ao longo da execução.

Desta forma, a implementação do DFS no projeto resulta dos seguintes princípios teóricos:

- Nó inicial => ABERTOS
- Se ABERTOS vazia falha.
- Remove o primeiro nó de ABERTOS (n) e coloca-o em FECHADOS
- Se a profundidade de n é maior que d vai para 2.
- Expande o nó n. Colocar os sucessores no início de ABERTOS, colocando os ponteiros para n.
- Se algum dos sucessores é um nó objectivo sai, e dá a solução. Caso contrário vai para 2.

A aplicação destes princípios resultou na função:

(defun dfs (noinicial objetivofunc funcsucessores operadores prof-max &optional (abertos (nos-iniciais noinicial)) (fechados nil))  "Função de cálculo do algoritmo dfs"
  (if (null abertos) nil 
    (let* ((nodo (car abertos))
           (novos-fechados (cons nodo fechados))
           (sucessores_nao_filtrados (funcall funcsucessores nodo operadores 'dfs prof-max) )
           (final_sucessores (remove-if #'(lambda (suce) 
                                           (or (no-existep suce fechados 'dfs) (no-existep suce abertos 'dfs) ) )
                                       sucessores_nao_filtrados ))
           (novos-abertos (abertos-dfs  (cdr abertos) final_sucessores))
           (existe-solucaop (remove-if-not #'(lambda (n) (funcall objetivofunc n)) final_sucessores)))
      ; verifcar se esta em sucessores
      (if (not (null existe-solucaop))    
          (list noinicial (car existe-solucaop) (length novos-abertos) (length novos-fechados)) 
        (dfs noinicial objetivofunc funcsucessores operadores prof-max novos-abertos novos-fechados ))    
      )
    )
  )

#### 4.2.4 A*

O algoritmo A* difere substancialmente dos descritos nos anteriores pontos pela sua natureza informada, onde o cálculo do custo de cada nó com base na heurística é uma necessidade ao longo das iterações.

Desta forma, podemos descrever teóricamente o algoritmo implementado da seguinte forma:

- Nó inicial => ABERTOS
- Se ABERTOS vazia, falha.
- Remove o primeiro nó de ABERTOS (n) e coloca-o em FECHADOS.
- Se n é um nó objetivo, a solução é encontrada.
- Caso contrário, vai para o próximo passo.
- Expande o nó n. Coloca os sucessores em ABERTOS.
- Para cada sucessor:
- Calcula o custo total $f(s) = g(s) + h(s)$
- Se o nó s já está em ABERTOS com um custo menor, ignora-o.
- Se o nó s já está em FECHADOS com um custo menor, ignora-o.
- Adiciona s a ABERTOS com o custo calculado e ponteiro para n.
- Escolhe o próximo nó a ser expandido com base no menor valor de f(s) em ABERTOS.
- Retorna ao passo 2.

A aplicação destes princípios resultou na função:

(defun a* (noinicial objetivofunc funcsucessores operadores heuristica &optional (abertos (ordenar-nos (nos-iniciais noinicial heuristica))) (fechados nil))
  "Função de cálculo do algoritmo a*"
  (if (null abertos ) nil
    (let* ( (nodo (car abertos))
            (novos-fechados (cons nodo fechados))
            (sucessores_nao_filtrados (funcall funcsucessores nodo operadores 'a* nil heuristica) )
            (final_sucessores (remove-if #'(lambda (suce) 
                                             (or (no-existep suce fechados 'a*) (no-existep suce abertos 'a*) ) )
                                         sucessores_nao_filtrados ))
            (abertosordenados (colocar-sucessores-em-abertos (cdr abertos) final_sucessores))
            (solucao (funcall objetivofunc nodo))
            ) 
      (if solucao (list noinicial nodo (length abertosordenados) (length novos-fechados))  
        (a* noinicial objetivofunc funcsucessores operadores heuristica abertosordenados novos-fechados ))
      )))

#### 4.2.5 IDA*

Como descrito na secção teórica, o IDA* apresenta-se como:

- Define um limite inicial de custo $f_{\text{limite}}$ para o custo do nó inicial.
- Repete os passos seguintes até encontrar uma solução.
- Nó inicial => ABERTOS.
- Se ABERTOS vazia, falha.
- Remove o primeiro nó de ABERTOS (n) e coloca-o em FECHADOS.
- Se n é um nó objetivo, a solução é encontrada.
- Se o custo total $f(n) = g(n) + h(n)$ excede $f_{\text{limite}}$, atualiza $f_{\text{limite}}$ com o mínimo dos custos que excedem $f_{\text{limite}}$.
- Expande o nó n. Coloca os sucessores em ABERTOS com custos calculados e ponteiros para n.
- Vai para 2.
- Atualiza $f_{\text{limite}}$ com o mínimo dos custos que excederam $f_{\text{limite}}$.
- Reinicia o processo do passo 2.

A aplicação destes princípios resultou em duas funções, uma de nível superior, responsável por controlar as sub-iterações do algoritmo:

(defun ida*-procura (noinicial objetivofunc funcsucessores operadores heuristica limite-corrente limite-futuro &optional (abertos (ordenar-nos (nos-iniciais noinicial heuristica))) (fechados nil) )
  "Função de cálculo do algoritmo ida*"
  (cond  ((null abertos ) (list limite-futuro))         
         (T  (let* ( (nodo (car abertos))
                     (novos-fechados (cons nodo fechados))
                     (sucessores_nao_filtrados (funcall funcsucessores nodo operadores 'a* nil heuristica) )
                     (sucessores_sem_repetidos (remove-if #'(lambda (suce) 
                                                              (or (no-existep suce fechados 'a*) (no-existep suce abertos 'a*) 
                                                                  ) )
                                                          sucessores_nao_filtrados ))
                     (sucessores_removidos (remove-if #'(lambda (suce) (<= (no-custo suce) limite-corrente )) sucessores_sem_repetidos ))
                     (novo-limite-futuro (limite-minimo-lista limite-futuro sucessores_removidos))
                     (final_sucessores (remove-if #'(lambda (suce) (> (no-custo suce) limite-corrente)) sucessores_sem_repetidos ))
                     (abertosordenados (colocar-sucessores-em-abertos (cdr abertos) final_sucessores))
                     (solucao (funcall objetivofunc nodo))
                     )
               (if solucao (list noinicial nodo (length abertosordenados) (length novos-fechados))  
                 (ida*-procura noinicial objetivofunc funcsucessores operadores heuristica limite-corrente novo-limite-futuro abertosordenados novos-fechados ))
               ))
         )
  )



(defun ida* (noinicial objetivofunc funcsucessores operadores heuristica &optional (limite-corrente (limite-inicial noinicial heuristica)) (limite-futuro  nil ))
  "Função que chama recursivamente o ida*-procura"
  (let* (
        (resultado (ida*-procura noinicial objetivofunc funcsucessores operadores heuristica limite-corrente limite-futuro))
        (limite-futuro-recebido (first resultado))
        )
    (cond 
     ((= (length resultado ) 1)  
      (if (null limite-futuro-recebido) nil
        (ida* noinicial objetivofunc funcsucessores operadores heuristica limite-futuro-recebido nil ))
      )
     (T resultado)
     
     )
    )
  )

## **5. Descrição das opções tomadas**

Serve o presente capítulo para descrição e justificação de determinadas opções tomadas ao longo do projeto, no que toca à sua arquitetura, execução, entre outros.

### **5.1 Escolha da Heurística**

Um dos essenciais pontos do projeto, assentava na criação de uma heurística, para utilização nos algoritmos de procura informada, que estimasse um custo desde o estado do nó a um estado que satisfaça o objectivo pretendido.

Para escolha da heurística original, utilizámos a seguinte fórmula:

$$
\begin{align}
h &= \frac{\text{Soma de pontos via operadores}}{\text{9 - número de operadores possíveis}}
\end{align}
$$

Esta heurística, visa assim fazer um quociente entre a soma de pontos possível de alcançar através dos operadores de dada posição, pelo rácio do número de operadores possível.

A equação $9-n$ visa "penalizar" as posições que tenham poucos operadores disponíveis, motivando o cavalo a manter-se em zonas centrais do tabuleiro, com mais pontos em redor.

Esta heurística parte assim do seguinte conhecimento empírico do problema:
- Quantas mais posições disponíveis, maiores serão as chances de encontrar casas de maior valor
- Quanto maior o valor em redor da posição, mais valiosa deve ser considerada a heurística.

Como comprovado adiante no relatório, esta heurística mostrou-se com ótimo desempenho na resolução de diversos problemas, superior à própria heurística do enunciado.

#### **5.1.1 Heurística do Enunciado**

A heurística de base do projeto, prende-se com uma função que privilegia visitar as casas com o maior número de pontos. Para um determinado tabuleiro x: $h(x) = o(x)/m(x)$ em que:

$m(x)$ é a média por casa dos pontos que constam no tabuleiro x,
$o(x)$ é o número de pontos que faltam para atingir o valor definido como objetivo.

### **5.2 Implementação da Lógica de Pontos**

Outra das nuances do projeto, prendia-se com os pontos associados a cada tabuleiro, e a necessidade de existir uma contagem dos mesmos, para perceber quando é que existia a solução.

De forma a reduzir o número de variáveis necessárias à execução do programa, ao invés da constante soma de números, que o predicado de solução iria comparar ao objetivo, decidimos, a cada iteração fazer a operação $pontos = pontos - {\text{[pontos casa atual]}}$, permitindo assim à solução, trabalhar sempre apenas com um valor, guardado junto do estado.

Este valor, é desta forma inicializado, no primeiro nó, com o número de pontos objetivo, e vai sendo reduzido ao longo da execução do algoritmo, e permutações do cavalo. Desta forma, a função de predicado prende-se com a execução de:

(defun no-solucaop (no)
  (<= (tabuleiro-pontos no) 0 )
  )

A subtração destes pontos é feita na função `duplo-ou-simetrico`, que é a responsável por devolver o novo estado.

Justificamos assim esta decisão com a simplicidade que a subtração dos pontos acrescenta à lógica do programa. Desta forma, não sentimos necessidade de manter ao longo do algoritmo os pontos objetivo, mas sim apenas de confirmar se os pontos associados ao estado são <=0.

### **5.3 Função Substituir verifica validade do movimento**
No âmbito do problema, é necessário verificar após cada movimento, qual a validade do mesmo no âmbito do estado. Por exemplo, determinada posição pode possibilitar o movimento do cavalo para uma casa inválida no tabuleiro, que exceda as suas dimensões.

Para tal, decidimos verificar a validade do movimento no âmbito da função substituir. A escolha deste local para a validação desta operação, prende-se com a tentativa de máxima abstração de todas as operações, sendo que, sabemos que será a operação de substiuir a responsável por esta deslocação, sendo assim o local mais apto a testar a legitimidade da mesma antes de devolver um valor.

### **5.4 Execução da Medição do Tempo**
Um dos requisitos do projeto representava a medição do tempo de execução do algoritmo. Para tal, procedemos ao uso das funções `internal-time-units-per-second` e `get-internal-real-time`.

No que toca à escolha de implementação das mesmas, decidimos englobar assim toda a execução do algoritmo, numa função denominada `medir-tempo execucao`, apresentada de seguida:

(defun medir-tempo-execucao (funcao &rest argumentos)
  (let* ((inicio (get-internal-real-time))
         (resultado (apply funcao argumentos) )
         (fim (get-internal-real-time))
         (tempo-execucao (/ (- fim inicio) internal-time-units-per-second)))
    (cond ((null resultado) nil)
          (T (append resultado (list(float tempo-execucao)) ))
          )
    )
  )

Esta, recebe como argumento o algoritmo a ser executado bem como os seus respetivos argumentos, e é não só responsável por medir o tempo antes e após a sua execução, bem como de realizar esta operação e devolver o resultado junto ao TAD Solução.

Justificamos esta escolha com o facto de através desta função, conseguirmos ter uma solução genérica para todos os algoritmos, completamente abstraída do tipo de procura a ser realizada.

### **5.5 Duplo ou Simétrico é responsável por devolver o estado**

Através da análise do código de cada operador, percebemos que o retorno do novo estado final do tabuleiro não é realizado pelo mesmo, sendo que a sua última instrução se refere a uma chamada à função `duplo-ou-simétrico`.

No que toca à arquitetura destas funções, percebemos que faria todo o sentido ser esta a responsável pelo processamento do novo estado, visto que seria após a execução da mesma e das possíveis condições de duplo ou simétrico, que o tabuleiro final poderia ser devolvido e utilizado posteriormente no nó.

Desta forma, a função `duplo-ou-simétrico` possui a seguinte estrutura:

(defun duplo-ou-simetrico (numero estado)
  "verifique se é duplo ou simetrico"
  (cond ((null numero) nil)
        (T (let*(
         
                 (novoestado (list (- (estado-pontos estado) numero) (estado-tabuleiro estado))))
     
             (cond ( (digitos-iguais-p numero) (duplo novoestado)   ) ; se duplo
                   (T (simetrico numero novoestado)) ;simetrico 
                   )
  
             ))
        )
  )

## **6. Resultados Alcançados**

### **6.1 BFS**

Como seria de esperar, a utilização do algoritmo BFS resolve sem problemas, os tabuleiros de complexidade baixa, porém, nunca parece demonstrar uma penetrância elevada, devido ao constante elevado número de nós gerados.

Este é o comportamento esperado por parte de um algoritmo não informado, que em problemas de maiores profundidades, apresenta uma baixa eficiência (por exemplo, problema D), ou até mesmo a não resolução em tempo e memória útil, como no problema de teste.

| Problema | Solução? | Profundidade | Nós Gerados | Nós Expandidos| Penetrância| Taxa Ramificação| Tempo (s)|
| -------- | -------- | -------- | -------- | ------- | ----- | ----- | ----- |
| A | Sim | 3 | 8 | 5 | 0.375 | 1.578 | 0.0 |
| B | Sim | 8 | 46 | 43 | 0.174 | 1.389 |0.004
| C | Sim | 6 | 40 | 35 |0.150 | 1.583 |0.002
| D | Sim | 12 | 263 | 247| 0.046 | 1.443 |0.025
| E | Overflow | N/A | N/A | N/A| N/A | N/A | N/A
| Teste | Overflow | N/A | N/A | N/A| N/A | N/A | N/A

### **6.2 DFS**

O algoritmo DFS apresenta um comportamento semelhante ao algoritmo anteriormente descrito, por partilhar a sua natureza de não informado. Mais uma vez, este resolve sem problemas, os tabuleiros de complexidade baixa, porém, nunca parece demonstrar uma penetrância elevada, devido ao constante elevado número de nós gerados.

Em alguns casos, como o problema D, é visível que a solução estaria possivelmente num ramo inicial, onde a eficiência da procura em profundidade saiu beneficiada.

| Problema | Solução? | Profundidade | Nós Gerados | Nós Expandidos| Penetrância| Taxa Ramificação| Tempo (s)|
| -------- | -------- | -------- | -------- | ------- | ----- | ----- | ----- |
| A | Sim | 3 | 7 | 5 | 0.429 | 1.488 | 0.0 |
| B | Sim | 8 | 41 | 39 | 0.195 | 1.363 |0.003
| C | Sim | 6 | 38 | 33 |0.157 | 1.566 |0.003
| D | Sim | 12 | 89 | 78| 0.146 | 1.254 |0.008
| E | Overflow | N/A | N/A | N/A| N/A | N/A | N/A
| Teste | Overflow | N/A | N/A | N/A| N/A | N/A | N/A

### 6.3 **A***

Através da execução do algoritmo A*, foi acrescentada uma componente de informação à procura em espaço de estados. Desta forma, é visível o aumento da penetrância, bem como do sucesso em resolver problemas de maior complexidade.

A análise específica dos resultados deste algoritmo encontra-se dividida pela heurística utilizada.

#### 6.3.1 **Heurística Enunciado**

Os resultados aquando da utilização da Heurística fornecida pelo enunciado em combinação com o algoritmo A*, apresentam uma clara melhoria em relação aos algoritmos não informados, sendo óbvio o aumento da penetrância em todos os problemas.

| Problema | Solução? | Profundidade | Nós Gerados | Nós Expandidos| Penetrância| Taxa Ramificação| Tempo (s)|
| -------- | -------- | -------- | -------- | ------- | ----- | ----- | ----- |
| A | Sim | 3 | 6 | 4 | 0.5 | 1.389 | 0.000 |
| B | Sim | 8 | 39 | 34 | 0.205 | 1.350 |0.003
| C | Sim | 6 | 39 | 32 |0.154 | 1.574 |0.002
| D | Sim | 12 | 98 | 74| 0.122 | 1.302 |0.009
| E | Overflow | N/A | N/A | N/A| N/A | N/A | N/A
| Teste | Sim | 31 | 137 | 33| 0.226 | 1.081 | 0.039

#### 6.3.2 **Heurística Original**

A heurística original desenvolvida, apresenta resultados surpreendentes na sua utilização juntamente ao A*, onde em grande parte dos problemas, supera a *performance* da estatística fornecida no enunciado.

É de destacar, por exemplo, o problema B, onde esta descobriu um caminho de profundidade 10, com uma penetrância de 0.714 e 14 nós gerados, onde a heurística do enunciado apenas alcançou uma penetrância de 0.205 e 39 nós gerados.

| Problema | Solução? | Profundidade | Nós Gerados | Nós Expandidos| Penetrância| Taxa Ramificação| Tempo (s)|
| -------- | -------- | -------- | -------- | ------- | ----- | ----- | ----- |
| A | Sim | 3 | 5 | 3 | 0.6 | 1.278 | 0.001 |
| B | Sim | 10 | 14 | 10 | 0.714 | 1.06 |0.001
| C | Sim | 6 | 30 | 27 |0.2 | 1.487 |0.004
| D | Sim | 12 | 28 | 14| 0.429 | 1.125 |0.004
| E | Overflow | N/A | N/A | N/A| N/A | N/A | N/A
| Teste | Sim | 37 | 196 | 68| 0.188 | 1.075 | 0.068

### 6.4 **IDA***

Através da utilização do algoritmo IDA*, analisamos agora um contexto *memory-bounded*, onde mais do que eficiência temporal, se procura a poupança de memória na acumulação de nós gerados.

A utilização deste algoritmo apresentou um aumento da penetrância em vários problemas, quando comparados à sua versão A*, não sendo porém, esta suficiente para resolução do problema E.

É porém de notar que pela reconstrução da árvore, e pelo uso e cálculo das heurísticas em questão, existe um ligeiro aumento do tempo neste tipo de algoritmo

#### 6.4.1 **Heurística Enunciado**

Os resultados aquando da utilização da heurística fornecida pelo enunciado em combinação com o algoritmo IDA*, apresentam uma ligeira melhoria em relação aos seus testes correspondentes realizados com o algoritmo A*, apresentando um aumento da penetrância, mesmo que ligeiro em todos os casos.

Apesar disto, não foi possível satisfazer as condições para resolução do problema E.

| Problema | Solução? | Profundidade | Nós Gerados | Nós Expandidos| Penetrância| Taxa Ramificação| Tempo (s)|
| -------- | -------- | -------- | -------- | ------- | ----- | ----- | ----- |
| A | Sim | 3 | 5 | 4 | 0.6 | 1.278 | 0.002 |
| B | Sim | 8 | 34 | 34 | 0.235 | 1.320 |0.014
| C | Sim | 6 | 33 | 32 |0.182 | 1.519 |0.027
| D | Sim | 12 | 74 | 74| 0.162 | 1.262 |0.063
| E | Overflow | N/A | N/A | N/A| N/A | N/A | N/A
| Teste | Sim | 30 | 130 | 34| 0.230 | 1.08 | 0.015

#### 6.4.2 **Heurística Original**

À semelhança do decorrido aquando da execução do algoritmo A*, a heurística original apresenta um desempenho consideravelmente superior à heurística do enunciado, apresentando um aumento da eficiência mesmo em problemas complexos.

Apesar disto, não foi possível satisfazer as condições para resolução do problema E.

| Problema | Solução? | Profundidade | Nós Gerados | Nós Expandidos| Penetrância| Taxa Ramificação| Tempo (s)|
| -------- | -------- | -------- | -------- | ------- | ----- | ----- | ----- |
| A | Sim | 3 | 5 | 3 | 0.6 | 1.278 | 0.001 |
| B | Sim | 8 | 31 | 31 | 0.258 | 1.299 |0.008
| C | Sim | 6 | 21 | 18 |0.286 | 1.373 |0.016
| D | Sim | 13 | 28 | 19| 0.464 | 1.104 |0.013
| E | Overflow | N/A | N/A | N/A| N/A | N/A | N/A
| Teste | Sim | 37 | 119 | 68| 0.311 | 1.055 | 0.236

## **7. Limitações técnicas e ideias para desenvolvimento futuro**

Efetuando um balanço final do projeto realizado, concluímos ter conseguido dar por executados todos os requisitos propostos, não só a nível funcional, mas inclusive na qualidade e estruturação de código, assumindo aquelas que são as boas práticas do Common LISP, recorrendo aos conceitos e estrutura do paradigma da programação funcional.

Apesar disto, conseguimos detetar algumas possíveis melhorias a executar numa solução futura, prendendo-se as mesmas com os pontos seguintes:

#### Construção de outros algoritmos

Mesmo com a conclusão de todos os algoritmos obrigatórios e a implementação com sucesso do algoritmo IDA*, consideramos que o presente projeto poderia ser melhorado com recurso à utilização dos algoritmos RBFS e SMA*, que teriam certamente um desempenho mais elevado na resolução de alguns problemas com dificuldades relativas ao uso de memória.

#### Interface com utilizador

Para utilização da aplicação pelo utilizador comum, consideramos que o uso da atual interface LISP não se apresenta como acessível. Desta forma, entendemos que numa fase posterior do projeto, poderia ser interessante a construção de uma interface do utilizador.

Para realizar tal funcionalidade, uma das possibilidades seria a utilização da solução [gtk+](https://www.gtk.org/), um projeto *open-source*, especializado na construção de elementos UI e compatível com a linguagem LISP.

#### Criação de novas heurísticas

Apesar dos bons resultados conseguidos com a heurística original implementada, que apresentou grandes melhorias em relação à fornecida juntamente ao enunciado, concluímos que poderíamos beneficiar da implementação de uma heurística com princípios matemáticos comprovados na matéria em causa, não partindo puramente de uma suposição, mas de um estudo teórico do problema relativo ao Jogo do Cavalo.

Em fases posteriores do projeto, seria assim interessante desenvolver novas heurísticas, que baseadas em princípios teóricos, apresentassem resultados ainda melhores que os apresentados até então

#### Verificar admissibilidade
Outra funcionalidade interessante para o presente projeto, seria o teste à condição de admissibilidade de determinada heurística após o fim da execução do problema.

Esta seria uma estatística de elevado relevo, que através do teste $h'(n) <= h(n)$ para todos os nós gerados, poderia verificar a admissibilidade da mesma, garantindo se a solução encontrada é ou não a melhor possível.

#### Utilização de uma superior quantidade de memória
Apesar da resolução de grande parte dos problemas propostos, consideramos que se ultrapassássemos a limitação do *Lispworks Personal Edition* em relação à memória utilizada para contextos de *stack*, poderia ser possível verificar a eficácia dos algoritmos em problemas de maior extensão.

Desta forma, em futuras versões do projeto, sentimos a necessidade de utilização de uma ferramenta que permita o uso de uma quantidade de memória superior.

## **8. Conclusão**

É com satisfação que apresentamos como concluída a atual fase do projeto, aguardando com expectativa a sua segunda componente de desenvolvimento, referente à introdução do conceito de Teoria de Jogos.

Consideramos que esta fez cumprir todos os requisitos propostos aquando do início do projeto, possibilitando a consolidação dos conteúdos teóricos relativos à procura em espaço de estados, mais precisamente dos algoritmos BFS, DFS e A*, bem como dos algoritmos bónus implementados ao longo da execução.

O presente projeto permitiu a aplicação real do conceito de procura em espaço de estados, direcionado ao Jogo do Cavalo, um problema clássico no ramo da Inteligência Artificial, que revelou a enorme importância e nuances dos diferentes tipos de algoritmos, divididos entre não-informados e informados.

Foi ainda possível recorrer à aplicação de duas heurísticas para os algoritmos informados, permitindo a passagem de um conhecimento empírico à solução, que se mostrou com uma elevada eficiência recorrendo a este tipo de processo, destacando a importância deste tipo de sistemas, quando comparados às soluções clássicas de exploração de árvores.

Damos assim por concluída a primeira fase deste projeto, apresentando como concluídos os 3 algoritmos base, e o algoritmo IDA* enquanto bónus, permitindo a utilização da solução de uma forma completamente funcional para a resolução de diferentes tipos de problemas no âmbito do Jogo do Cavalo.