# **Manual Técnico - Fase 2**

<div align="center">

## Projeto Fase 2 - 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 4 ficheiros principais:

- **Interact.lisp**
- Carrega os restantes ficheiros
- Efetua a leitura e escrita de ficheiros
- Interação com o Utilizador
- **Jogo.lisp**
- Código relacionado com o problema específico
- **Algoritmo.lisp**
- Contém todos os algoritmos implementados no projeto
- **Log.dat**
- Contém os resultados do jogo executados

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

Sendo este um problema teoria de jogos, 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 dos jogadores, 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.

Neste contexto, o estado vai igualmente servir o papel de nó, visto não existir necessidade de armazenar outras informações, como a profundidade.

<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:

   (<PONTOSA> <PONTOSB> (
    (<              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:

( (0 0) (
              (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)
              ))

É importante frisar que, dada a necessidade de representar dois cavalos no tabuleiro, estes assumirão os dígitos:
- -1 -> Cavalo Jogador 1
- -2 -> Cavalo Jogador 2

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-jogador1` - Devolve o número de pontos do jogador1
- `estado-pontos-jogador2` - Devolve o número de pontos do jogador2
- `adicionar-pontos-jogador` - Adiciona pontos ao jogador passado por parâmetro

### **3.2 Movimento**

Ao longo do desenvolvimento do programa, foi necessário em determinado momento, detetar a possibilidade de movimento ameaçado. Visto que as funções de sucessores estavam integradas na chamada de duplo-ou-simetrico, estas tornavam-se infinitamente recursivas, tendo sido necessária a criação de um TAD que guardasse um estado, a nova linha e a nova coluna do movimento

Desta forma, o TAD em questão tem a seguinte estrutura:

Movimento :== ({<Estado>} {<Linha>} {<Coluna>} | 

E podemos interagir com o mesmo através dos seletores:

- `movimento-novo-estado` - Devolve o novo estado
- `movimento-nova-linha` - Devolve a linha
- `movimento-nova-coluna` - Devolve a coluna

### 3.3 Resultado Alfabeta
Graças à necessidade de a cada iteração do algoritmo, mostrar as suas estatísticas, foi necessária a criação de um Tipo Abstrato de Dados responsável pelo armazenamento das informações devolvidas pelo alfabeta.

Desta forma, este TAD tem a seguinte estrutura:

<Resultado-Alfabeta> ::= ( {<Valor>} {<Nos-Analisados>} {<Cortes-Alfa>} {<Cortes-Beta>} )

Podemos interagir com este TAD através das seguintes operações:
- `resultado-alfabeta-valor` - Devolve o valor do algoritmo
- `resultado-alfabeta-nos-analisados` - Devolve o número de nós analisados
- `resultado-alfabeta-cortes-alfa` - Devolve o número de cortes alfa
- `resultado-alfabeta-cortes-beta` - Devolve o número de cortes beta

### 3.4 Jogada Computador

Visto que o resultado do AlfaBeta é um Tipo Abstrato de Dados, limitado ás informações mostradas anteriormente, aquando das jogadas do computador, foi necessário também guardar a própria jogada executada, valor esse que não é retornado pelo alfabeta.

Desta forma, procedemos à criação do Tipo Abstrato de Dados Jogada-Computador, com a seguinte estrutura:

<Jogada-Computador> ::= ( {<Resultado-Alfabeta>} {<Tempo-Execucao>} {<Jogada>} )

## **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 teoria de jogos é composto por diversos algoritmos que visam desenvolver inteligência artifical para jogos competitivos de soma zero, onde um jogador vence, e outro perde.
O algoritmo minimax, utilizado no projeto, assenta num conceito de árvore de jogo, que recorrendo a nós efetua a análise das possibilidades a serem executadas.
Sob este algoritmo, existem ainda os cortes alfa-beta, que permitem uma otimização ao mesmo através do conceito de cortes sem perda de informação relevante.

### **4.1.1 Minimax**

O algoritmo Minimax caracteriza-se assim enquanto o mais importante algoritmo relativo à teoria de jogos, responsável pela iteração da árvore de jogo.
O princípio deste algoritmo, caracteriza-se por "descer" na árvore de jogo, até chegar ao seu termino, verificando se o jogador em causa, perdeu, empatou ou ganhou.

Após isto, o algoritmo sobe recursivamente os nós, atualizando os valores de min e max destas ramificações, repetindo isto até chegar ao nó raiz da árvore.

Desta forma, o algoritmo minimax visa assim anteceder as jogadas de todos os caminhos possíveis no jogo, aconselhando aqueles que devolvem melhores resultados ao jogador max

Este algoritmo, apresenta assim o seguinte pseudocódigo:

function MINIMAX-DECISION(state) returns an action
 return arg max a ∈ ACTIONS(s) MIN-VALUE(RESULT(state, a))

function MAX-VALUE(state) returns a utility value
 if TERMINAL-TEST(state) then return UTILITY(state)
 v ← −∞
 for each a in ACTIONS(state) do
   v ← MAX(v, MIN-VALUE(RESULT(state, a)))
 return v

function MIN-VALUE(state) returns a utility value
 if TERMINAL-TEST(state) then return UTILITY(state)
 v ← ∞
 for each a in ACTIONS(state) do
   v ← MIN(v, MAX-VALUE(RESULT(state, a)))
 return v
 

*Extraído do livro "Artificial Intelligence a Modern Approach, 3rd edition"*

### **4.1.2 AlphaBeta**

Aquando da utilização do minimax, é perceptível que em grande parte dos problemas, com uma elevada quantidade de possíveis estados, torna-se incomportável avaliar todos os nós possíveis da árvore de jogo.
Desta forma, torna-se necessário existir uma solução que permita o corte de nós cuja necessidade de avaliação seja nula, sem que isto afete o resultado final.

Surge assim o alfabeta, enquanto complemento ao algoritmo minimax, que pára de avaliar os nós quando sabe que o mesmo possui resultados desfavoráveis.

Este algoritmo apresenta o seguinte pseudocódigo:

function minimax(node, depth, isMaximizingPlayer, alpha, beta):

    if node is a leaf node :
        return value of the node
    
    if isMaximizingPlayer :
        bestVal = -INFINITY 
        for each child node :
            value = minimax(node, depth+1, false, alpha, beta)
            bestVal = max( bestVal, value) 
            alpha = max( alpha, bestVal)
            if beta <= alpha:
                break
        return bestVal

    else :
        bestVal = +INFINITY 
        for each child node :
            value = minimax(node, depth+1, true, alpha, beta)
            bestVal = min( bestVal, value) 
            beta = min( beta, bestVal)
            if beta <= alpha:
                break
        return bestVal

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

O presente capítulo visa detalhar a implementação da estrutura do projeto, efetuando uma ponte entre osfundamentos teóricos e a sua execução prática do AlfaBeta.

#### 4.2.1 Geral

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

- **Interact.lisp**
- Carrega os restantes ficheiros
- Efetua a leitura e escrita de ficheiros
- Interação com o Utilizador
- **Jogo.lisp**
- Código relacionado com o problema específico
- **Algoritmo.lisp**
- Contém todos os algoritmos implementados no projeto

De um ponto de vista lógico, o programa inicia na função `jogar`, no ficheiro **Interact.lisp**. Esta função é responsável pela chamada da interação inicial com o utilizadorm questionando o tipo de jogo a executar (computador-humano/computador-computador).

Após isto, é chamada a função respetiva de entre as várias possibilidades:
- `jogar-humano-computador`
- `jogar-computador-computador`

#### 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 peca)
  "Operador do problema, corresponde à jogada +2 linha e -1 coluna"
  (let* (
         (tabuleiro (estado-tabuleiro estado))
         (movimento (movimento-operador 'operador-1 estado peca))
         (nova-linha (movimento-nova-linha movimento))
         (nova-coluna (movimento-nova-coluna movimento))
         (novo-estado (movimento-novo-estado movimento))
         )
    (cond (novo-estado
           (duplo-ou-simetrico (celula nova-linha nova-coluna tabuleiro ) novo-estado peca))
          (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º 2: Época Normal - Inteligência Artificial

#### 4.2.2 Minimax+Alfabeta

Apresentada a estrutura geral do funcionamento da solução, analisemos a implementação do algoritmo no projeto. Esta, assentou assim no princípio teórico do mesmo, seguindo o pseudocódigo já apresentado

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

(defun alfabeta (no profundidade-max peca limite-tempo 
                    &optional (maximo T) (alfa most-negative-fixnum) (beta most-positive-fixnum)
                    (nos-analisados 0) (cortes-alfa 0) (cortes-beta 0) (tempo-inicial (get-internal-real-time))  
                    &aux (tempo-atual (get-internal-real-time))
                    (tempo-execucao ( - tempo-atual tempo-inicial )))
  (cond 
   ( (or (= profundidade-max 0) (no-terminalp no peca) 
         (> tempo-execucao limite-tempo)   )  
     (list (no-avaliacao no peca maximo) (1+ nos-analisados) cortes-alfa cortes-beta)
     )
   (T
    (let*
        (
         (jogadas (ordenar-nos-intermedios
                   (remove nil (mapcar #'(lambda (operador) (funcall operador no peca)  ) (operadores) ))
                   peca 
                   maximo
                   ))
         )
      (if maximo (minimax-max jogadas profundidade-max peca alfa beta nos-analisados cortes-alfa cortes-beta limite-tempo tempo-inicial)
        (minimax-min jogadas profundidade-max peca alfa beta nos-analisados cortes-alfa cortes-beta limite-tempo tempo-inicial) )
      )
    )
   )
  )
  

Esta função é assim responsável pela chamada das funções respetivas para o min e para o max:

(defun minimax-max (jogadas profundidade-max peca alfa beta nos-analisados cortes-alfa cortes-beta limite-tempo tempo-inicial
                            &optional (valor most-negative-fixnum) (melhor-jogada nil))
  (cond
   ((null jogadas) (progn (setq *jogada* melhor-jogada)
                     (list valor nos-analisados cortes-alfa cortes-beta))) ; atualiza *jogada* com a melhor jogada
   (T (let* (
             (jogada (car jogadas))
             (resultado (alfabeta-memo  jogada (1- profundidade-max) (trocar-peca peca) limite-tempo
                                   nil alfa beta nos-analisados cortes-alfa cortes-beta tempo-inicial ))
             (valor-resultado (resultado-alfabeta-valor resultado))
             (nos-analisados-resultado (resultado-alfabeta-nos-analisados resultado) )
             (novo-valor (max valor-resultado valor))
             (novo-alfa (max alfa novo-valor))
             (cortes-alfa-resultado (resultado-alfabeta-cortes-alfa resultado))            
             (cortes-beta-resultado (resultado-alfabeta-cortes-beta resultado))            
             (novo-cortes-alfa (if (>= novo-alfa beta) (1+ cortes-alfa-resultado) cortes-alfa-resultado))
             )
        (cond ((>= novo-alfa beta) (progn (setq *jogada* melhor-jogada) 
                                     (list beta nos-analisados-resultado
                                           novo-cortes-alfa cortes-beta-resultado ))  
               ) 
              (T     (if (> valor-resultado valor)           
                         (minimax-max (cdr jogadas) profundidade-max peca novo-alfa beta 
                                      nos-analisados-resultado
                                      novo-cortes-alfa cortes-beta-resultado
                                      limite-tempo tempo-inicial
                                      valor-resultado jogada) ; atualiza a melhor jogada
                       (minimax-max (cdr jogadas) profundidade-max peca novo-alfa beta
                                    nos-analisados-resultado
                                    novo-cortes-alfa cortes-beta-resultado
                                    limite-tempo tempo-inicial
                                    valor melhor-jogada))
                     )
              )
        )
      )
   )
  )


(defun minimax-min (jogadas profundidade-max peca alfa beta nos-analisados cortes-alfa cortes-beta limite-tempo  tempo-inicial
                            &optional (valor most-positive-fixnum) )
  (cond
   ((null jogadas) (list valor nos-analisados cortes-alfa cortes-beta))
   (T (let* (
             (jogada (car jogadas))
             (resultado (alfabeta-memo jogada (1- profundidade-max) (trocar-peca peca) limite-tempo
                                  T alfa beta nos-analisados 
                                  cortes-alfa cortes-beta tempo-inicial))
             (valor-resultado (resultado-alfabeta-valor resultado))
             (nos-analisados-resultado (resultado-alfabeta-nos-analisados resultado) )
             (novo-valor (min valor-resultado  valor))
             (novo-beta (min beta novo-valor))
             (cortes-alfa-resultado (resultado-alfabeta-cortes-alfa resultado))            
             (cortes-beta-resultado (resultado-alfabeta-cortes-beta resultado))            
             (novo-cortes-beta (if (>= alfa novo-beta ) (1+ cortes-beta-resultado) cortes-beta-resultado))
             )     
        (cond ((>= alfa novo-beta )
               (list alfa  nos-analisados-resultado cortes-alfa-resultado novo-cortes-beta) ) 
              (T (if (< valor-resultado valor ) 
                     (minimax-min (cdr jogadas)  profundidade-max peca alfa novo-beta                                 
                                  nos-analisados-resultado
                                  cortes-alfa-resultado novo-cortes-beta
                                  limite-tempo tempo-inicial
                                  valor-resultado)
                   (minimax-min (cdr jogadas)  profundidade-max peca alfa novo-beta 
                                nos-analisados-resultado
                                cortes-alfa-resultado novo-cortes-beta
                                limite-tempo tempo-inicial
                                valor))
                 )
              )
        )
      )
   )
  )

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

<Resultado-Alfabeta> ::= ( {<Valor>} {<Nos-Analisados>} {<Cortes-Alfa>} {<Cortes-Beta>} )

## **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 Função de Avaliação**

Uma das componentes de elevada importância na execução do AlfaBeta, é a escolha de uma função de avaliação que permita quantificar determinado estado. Para tal, procedemos à implementação de uma função `no-avaliacao`, responsável por devolver um valor quantitativo, no intervalo -inf e +inf, com o qual o *alfabeta* irá operar

Para tal, pensámos em avaliar o estado com base na seguinte operação:

(PontosJogador1 - PontosJogador2) + (PróximosPontosJ1 - PróximosPontosJ2) * Multiplicador

Tal, consiste no seguinte princípio teórico: É vista a diferença dos pontos entre jogadores, e somada aos pontos possíveis destes nas posições em seu redor. Nisto, é ainda multiplicado o valor 1 ou -1, consoante o jogador min ou max que estiver a jogar.

(defun no-avaliacao (no jogador maximo)
  ;pontos max - pontos min +  todos ao pe do max - todos ao pe do min
   "identifica qual o valor heuristico do nó terminal para o jogador"
  (let*
      (
       (pontos-jogador1 (estado-pontos-jogador no jogador))
       (pontos-jogador2 (estado-pontos-jogador no (trocar-peca jogador)))
       (maximo-multiplicador (if maximo 1 -1)) ; serve para caso seja o minimo a vencer, inverte o sinal
       (proximos-pontos-jogador1 (pontos-possiveis-jogador no jogador) )
       (proximos-pontos-jogador2 (pontos-possiveis-jogador no (trocar-peca jogador)) )
       )
    (* (+  (- pontos-jogador1 pontos-jogador2) 
(- proximos-pontos-jogador1 proximos-pontos-jogador2) )
 maximo-multiplicador )
  
    )
  )

### **5.2 Procura Quiescente**

Outra das necessidades de otimização do projeto, prende-se com a aplicação do conceito de procura quiescente. Esta, define-se pela aplicação da função de avaliação a posições com baixa probabilidade de terem variações bruscas no valor de f.

Tal foi aplicado modificando a função de avaliação, explorando um nó abaixo do proposto, de forma a atestar a veracidade do valor em causa.

Desta forma, modificámos a avaliação do nó terminal, de forma a permitir o cálculo da média entre o valor atual do nó, e o valor do melhor sucessor, obtendo uma precisão apurada do valor em causa.

(defun no-avalicao-terminal (no jogador maximo)
  (let
      (
       (avaliacao (no-avaliacao no jogador maximo))
       (jogadas (jogadas no jogador))
       )
    (cond 
     ((null jogadas) avaliacao)
     (T (let*
            (
             (valor-melhor-sucessor (melhor-jogada jogador maximo jogadas))
             )
          (/ (+ valor-melhor-sucessor  avaliacao) 2)
          )
        )
     )
    )
  )

### **5.3 Memoização**

Um dos importantes conceitos a ser utilizados neste tipo de algoritmos, é a existência de uma tabela hash, responsável pelo armazenamento de resultados de determinados estados, facilitanto assim o cálculo imediato destes sem que os seus sucessores tenham de ser gerados.

Para tal, foi efetuada a memoização, onde optámos por recorrer à criação de uma tabela hash, responsável pelo armazenamento destes dados através do conceito de *closure*.
Posto isto, aquando da execução do alfabeta, é chamada a função alfabeta-memo, que verifica se o valor para este estado já foi calculado previamente.

(let (
      (tabela (make-hash-table))
      )
  (defun alfabeta-memo (no &rest argumentos)
     (or (gethash no tabela)
           (let ((val (apply #'alfabeta (cons no argumentos))))
	   (setf (gethash no tabela) val)
              val))
     )
  )

### **5.4 Ordenação dos nós**
Em termos de eficiência, a ordenação dos nós mostrou-se como o principal fator de eficiência. Com esta implementação foi de notável observação, para um mesmo estado inicial, o aumento de número de cortes realizados em todas as jogadas.
Esta consistiu na ordenação dos nós intermédios segundo o seu valor heurístico. Ou seja, sempre que se gera novas jogadas, a partir de uma outra, estas jogadas são ordenadas de acordo com o tipo de nó em que estão (max ou min).
De seguida observa-se como foi implementado a ordenação dos nós intermédios da árvore de jogo.

;; Odenação dos nós 
; função que avalia o nó intermédio
(defun no-avaliacao-intermedio (no jogador maximo)
  "Funcao de avaliação de nos intermedios"
  (no-avaliacao no jogador maximo)
  )


; max -> de forma decrescente
; min -> crescente 
; funcao auxiliar que ordena nos de acordo com o seu valor associado
(defun ordenar-nos-com-valores (nos maximo)
  "ordena os nos de acordo com o seu valor associado, dependendo se é max ou min"
  (cond (maximo (sort nos #'(lambda (x y)
                              (> (first x) (first y)))))
        (T (sort nos #'(lambda (x y)
                         (< (first x) (first y)))))
        )
  )


;; Ordenar os nós intermediários
(defun ordenar-nos-intermedios (nos jogador maximo)
  "Ordena os nos intermedios recebidos"
  (cond ((null nos) nil)
        (T (let*
               (
                (valores-com-nos (mapcar #'(lambda (no) 
                                             (cons (no-avaliacao-intermedio no jogador maximo) no)
                                             ) nos ))
                (ordenados-com-valor (ordenar-nos-com-valores valores-com-nos maximo))
                (nos-ordenados (mapcar #'(lambda (no) (cdr no)) ordenados-com-valor ))
                )
             nos-ordenados
             ))
        )
  )

E aqui é como é utilizado esta ordenação:

  (jogadas (ordenar-nos-intermedios
                   (remove nil (mapcar #'(lambda (operador) (funcall operador no peca)  ) (operadores) ))
                   peca 
                   maximo
                   ))

### **5.5 Movimento**

Para cumprir a condição de verificação de peça ameaçada, foi necessário alterar a abordagem de movimento do programa. Para tal, os operadores foram sub-divididos, existindo uma função responsável pela chamada do movimento dos diferentes operadores:

(defun movimento-operador (operador estado peca)
  (cond 
   ( (equal operador 'operador-1 )  
     (let* 
         (
          (tabuleiro (estado-tabuleiro estado))
          (posicao (posicao-numero peca 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 peca))
          )
       (list novo-estado nova-linha nova-coluna)
       )
     )
   ( (equal operador 'operador-2)
     (let* 
         (
          (tabuleiro (estado-tabuleiro estado))
          (posicao (posicao-numero peca 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 peca))
          )
       (list novo-estado nova-linha nova-coluna)
       )
     )
   ((equal operador 'operador-3)
    (let*
        (
         (tabuleiro (estado-tabuleiro estado))
         (posicao (posicao-numero peca tabuleiro))
         (linha-cavalo (first posicao))
         (coluna-cavalo (second posicao))
         (movimento-tabuleiro   (substituir linha-cavalo coluna-cavalo estado))
         (nova-linha (1+  linha-cavalo)  )
         (nova-coluna (+ 2 coluna-cavalo))
         (novo-estado  (substituir nova-linha nova-coluna movimento-tabuleiro peca  ))
         )
      (list novo-estado nova-linha nova-coluna)
      )
    )

   ((equal operador 'operador-4)
    (let*
        (
         (tabuleiro (estado-tabuleiro estado))
         (posicao (posicao-numero peca tabuleiro))
         (linha-cavalo (first posicao))
         (coluna-cavalo (second posicao))
         (movimento-tabuleiro   (substituir linha-cavalo coluna-cavalo estado))
         (nova-linha (1-  linha-cavalo)  )
         (nova-coluna (+ 2 coluna-cavalo))
         (novo-estado (substituir nova-linha nova-coluna movimento-tabuleiro peca ))
         )
      (list novo-estado nova-linha nova-coluna)
      )
    )

   ((equal operador 'operador-5)
    (let*
        (
         (tabuleiro (estado-tabuleiro estado))
         (posicao (posicao-numero peca tabuleiro))
         (linha-cavalo (first posicao))
         (coluna-cavalo (second posicao))
         (movimento-tabuleiro   (substituir linha-cavalo coluna-cavalo estado))
         (nova-linha (- linha-cavalo 2)  )
         (nova-coluna (1+ coluna-cavalo))
         (novo-estado  (substituir nova-linha nova-coluna movimento-tabuleiro peca  ))
         )
      (list novo-estado nova-linha nova-coluna)
      )
    )

   ((equal operador 'operador-6)
    (let*
        (
         (tabuleiro (estado-tabuleiro estado))
         (posicao (posicao-numero peca tabuleiro))
         (linha-cavalo (first posicao))
         (coluna-cavalo (second posicao))
         (movimento-tabuleiro   (substituir linha-cavalo coluna-cavalo estado))
         (nova-linha (- linha-cavalo 2)  )
         (nova-coluna (1- coluna-cavalo))
         (novo-estado  (substituir nova-linha nova-coluna movimento-tabuleiro peca  ))
         )
      (list novo-estado nova-linha nova-coluna)
      )
    )

   ((equal operador 'operador-7)
    (let*
        (
         (tabuleiro (estado-tabuleiro estado))
         (posicao (posicao-numero peca tabuleiro))
         (linha-cavalo (first posicao))
         (coluna-cavalo (second posicao))
         (movimento-tabuleiro   (substituir linha-cavalo coluna-cavalo estado))
         (nova-linha (1-  linha-cavalo)  )
         (nova-coluna (- coluna-cavalo 2))
         (novo-estado  (substituir nova-linha nova-coluna movimento-tabuleiro peca ))
         )
      (list novo-estado nova-linha nova-coluna)
      )
    )

   
   
   ( (equal operador 'operador-8 )  
     (let* 
         (
          (tabuleiro (estado-tabuleiro estado))
          (posicao (posicao-numero peca tabuleiro))
          (linha-cavalo (first posicao))
          (coluna-cavalo (second posicao))
          (movimento-tabuleiro   (substituir linha-cavalo coluna-cavalo estado))
          (nova-linha (+ 1  linha-cavalo)  )
          (nova-coluna (-  coluna-cavalo 2))
          (novo-estado  (substituir nova-linha nova-coluna movimento-tabuleiro peca  ))
          )
       (list novo-estado nova-linha nova-coluna)
       )
     )
   )
  )

### **5.5 Execução da Medição do Tempo dentro do alfabeta**

Foi inicialmente definido um limite temporal a ser estabelecido para a jogada do computador.

Para que existisse sempre a devolução de um valor proveniente da execução do algoritmo alfabeta, foi necessário proceder à contagem deste tempo no interior da função, ao contrário do que vinha a ser feito durante a fase 1 do projeto, estando tal implementado da seguinte forma:

(defun alfabeta (no profundidade-max peca **limite-tempo** 
                    &optional (maximo T) (alfa most-negative-fixnum) (beta most-positive-fixnum)
                    (nos-analisados 0) (cortes-alfa 0) (cortes-beta 0) (tempo-inicial (get-internal-real-time))  
                    &aux (tempo-atual (get-internal-real-time))
                    (tempo-execucao ( - tempo-atual tempo-inicial )))
  (cond 
   ( (or (= profundidade-max 0) (no-terminalp no peca) 
         (> **tempo-execucao limite-tempo**)   )  
     (list (no-avaliacao no peca maximo) (1+ nos-analisados) cortes-alfa cortes-beta)


(...)
  

### **5.6 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. 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:

#### 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.

#### Refactoring de Código
No atual projeto, reconhecemos a existência de determinado formulamento de código que pode não estar realizado da forma mais correta. Por exemplo, através utilização do conceito *negamax*, poderíamos reduzir a repetição de código no algoritmo minimax com cortes alfabeta, levando a um código consideravelmente mais legí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.

## **7. Exemplo de aplicação**

Como se pode observar abaixo, é realizado um jogo entre um utilizador humano e a máquina. O primeiro jogador é o humano, com um tempo máximo de jogada para a máquina de 5 segundos.
Em termos de dificuldade, a máquina possui um limite máximo de horizonte de profundidade 6.

           ___                              
           |_  |                             
             | | ___   __ _  ___             
             | |/ _ \ / _` |/ _ \            
         /\__/ / (_) | (_| | (_) |           
         \____/ \___/ \__, |\___/            
                       __/ |                   
                      |___/                    
     _                               _          
    | |                             | |         
  __| | ___     ___ __ ___   ____ __| | ___     
 / _` |/ _ \   / __/ _` |\ \ / / _` | |/ _ \    
| (_| | (_) | | (_| (_| | \ V / (_| | | (_) |   
 \__,_|\___/   \___\__,_|  \_/ \__,_|_|\___/    
                                             
                                             
Escolha um jogo: 
1 - Humano vs Computador
2 - Computador vs Computador
1
Escolha o primeiro a jogar:
1 - Humano
2 - Computador
1
Escolha o tempo limite para o computador jogar, entre 1000 a 5000 milissegundos:
5000

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

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

Turno do JOGADOR1

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

Turno do JOGADOR2

Pontos do jogador 1 : 154 pontos
Pontos do jogador 2 : 97 pontos

Nos analisados: 450 
Cortes alfa: 52 
Cortes beta: 96 
Tempo de execucao: 1.895 

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

Turno do JOGADOR1

Pontos do jogador 1 : 154 pontos
Pontos do jogador 2 : 185 pontos
Indique a linha a selecionar
De 1 a 10
3
Indique a coluna a selecionar
De 1 a 10
6
|59|43|77|0 |10|  |2 |33|89|  |
|21|47|92|38|69|14|95|  |37|76|
|22|29|1 |27|65|-1|58|8 |32|51|
|44|19|25|42|13|4 |15|52|5 |  |
|31|40|60|67|7 |73|90|68|82|18|
|63|6 |23|41|56|85|9 |35|94|66|
|26|53|12|30|46|78|87|34|17|48|
|71|75|11|64|24|57|  |  |81|98|
|96|74|49|72|  |86|50|-2|70|91|
|28|36|83|80|3 |55|62|20|84|  |

Turno do JOGADOR2

Pontos do jogador 1 : 208 pontos
Pontos do jogador 2 : 185 pontos

Nos analisados: 529 
Cortes alfa: 60 
Cortes beta: 139 
Tempo de execucao: 1.99 

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

Turno do JOGADOR1

Pontos do jogador 1 : 208 pontos
Pontos do jogador 2 : 272 pontos
Indique a linha a selecionar
De 1 a 10
5
Indique a coluna a selecionar
De 1 a 10
7
|59|43|77|0 |10|  |2 |33|89|  |
|21|47|92|38|69|14|95|  |37|76|
|22|29|1 |27|65|  |58|8 |32|51|
|44|19|25|42|13|4 |15|52|5 |  |
|31|40|60|67|7 |73|-1|68|82|18|
|63|6 |23|41|56|85|  |35|94|66|
|26|53|12|30|46|  |-2|34|17|48|
|71|75|11|64|24|57|  |  |81|98|
|96|74|49|72|  |86|50|  |70|91|
|28|36|83|80|3 |55|62|20|84|  |

Turno do JOGADOR2

Pontos do jogador 1 : 298 pontos
Pontos do jogador 2 : 272 pontos

Nos analisados: 1623 
Cortes alfa: 223 
Cortes beta: 349 
Tempo de execucao: 5.021 

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

Turno do JOGADOR1

Pontos do jogador 1 : 298 pontos
Pontos do jogador 2 : 358 pontos
Indique a linha a selecionar
De 1 a 10
6
Indique a coluna a selecionar
De 1 a 10
9
|59|43|77|0 |10|  |2 |33|89|  |
|21|47|92|38|69|14|95|  |37|76|
|22|29|1 |27|65|  |58|8 |32|51|
|44|19|25|42|13|4 |15|52|5 |  |
|31|40|60|67|7 |73|  |  |82|18|
|63|6 |23|41|56|85|  |35|-1|66|
|26|53|12|30|46|  |  |34|17|48|
|71|75|11|64|24|57|  |  |81|98|
|96|74|  |72|  |-2|50|  |70|91|
|28|36|83|80|3 |55|62|20|84|  |

Turno do JOGADOR2

Pontos do jogador 1 : 392 pontos
Pontos do jogador 2 : 358 pontos

Nos analisados: 112 
Cortes alfa: 12 
Cortes beta: 74 
Tempo de execucao: 0.509 

|59|43|77|0 |10|  |2 |33|89|  |
|21|47|92|38|69|14|95|  |37|76|
|22|29|1 |27|65|  |58|8 |32|51|
|44|19|25|42|13|4 |15|52|5 |  |
|31|40|60|67|7 |73|  |  |82|18|
|63|6 |23|41|56|85|  |35|-1|66|
|26|53|12|30|  |  |  |34|17|48|
|71|75|11|-2|24|57|  |  |81|98|
|96|74|  |72|  |  |50|  |70|91|
|28|36|83|80|3 |55|62|20|84|  |

Turno do JOGADOR1

Pontos do jogador 1 : 392 pontos
Pontos do jogador 2 : 422 pontos
Indique a linha a selecionar
De 1 a 10
8
Indique a coluna a selecionar
De 1 a 10
10
|59|43|77|0 |10|  |2 |33|  |  |
|21|47|92|38|69|14|95|  |37|76|
|22|29|1 |27|65|  |58|8 |32|51|
|44|19|25|42|13|4 |15|52|5 |  |
|31|40|60|67|7 |73|  |  |82|18|
|63|6 |23|41|56|85|  |35|  |66|
|26|53|12|30|  |  |  |34|17|48|
|71|75|11|-2|24|57|  |  |81|-1|
|96|74|  |72|  |  |50|  |70|91|
|28|36|83|80|3 |55|62|20|84|  |

Turno do JOGADOR2

Pontos do jogador 1 : 490 pontos
Pontos do jogador 2 : 422 pontos

Nos analisados: 472 
Cortes alfa: 26 
Cortes beta: 240 
Tempo de execucao: 1.451 

|59|43|77|0 |10|  |2 |33|  |  |
|21|47|92|  |69|14|95|  |37|76|
|22|29|1 |27|65|  |58|8 |32|51|
|44|19|25|42|13|4 |15|52|5 |  |
|31|40|60|67|7 |73|  |  |82|18|
|63|6 |23|41|56|85|  |35|  |66|
|26|53|12|30|  |  |  |34|17|48|
|71|75|11|  |24|57|  |  |81|-1|
|96|74|  |72|  |  |50|  |70|91|
|28|36|-2|80|3 |55|62|20|84|  |

Turno do JOGADOR1

Pontos do jogador 1 : 490 pontos
Pontos do jogador 2 : 505 pontos
Indique a linha a selecionar
De 1 a 10
10
Indique a coluna a selecionar
De 1 a 10
9
|59|43|77|0 |10|  |2 |33|  |  |
|21|47|92|  |69|14|95|  |37|76|
|22|29|1 |27|65|  |58|8 |32|51|
|44|19|25|42|13|4 |15|52|5 |  |
|31|40|60|67|7 |73|  |  |82|18|
|63|6 |23|41|56|85|  |35|  |66|
|26|53|12|30|  |  |  |34|17|  |
|71|75|11|  |24|57|  |  |81|  |
|96|74|  |72|  |  |50|  |70|91|
|28|36|-2|80|3 |55|62|20|-1|  |

Turno do JOGADOR2

Pontos do jogador 1 : 574 pontos
Pontos do jogador 2 : 505 pontos

Nos analisados: 76 
Cortes alfa: 5 
Cortes beta: 28 
Tempo de execucao: 0.246 

|59|43|77|0 |10|  |2 |33|  |  |
|21|47|92|  |69|14|95|  |37|76|
|22|29|1 |27|65|  |58|8 |32|51|
|44|19|25|42|13|4 |15|52|5 |  |
|31|40|60|67|7 |73|  |  |82|18|
|63|6 |23|41|56|85|  |35|  |66|
|26|53|12|30|  |  |  |34|17|  |
|71|-2|11|  |24|  |  |  |81|  |
|96|74|  |72|  |  |50|  |70|91|
|28|36|  |80|3 |55|62|20|-1|  |

Turno do JOGADOR1

Pontos do jogador 1 : 574 pontos
Pontos do jogador 2 : 580 pontos
Indique a linha a selecionar
De 1 a 10
9
Indique a coluna a selecionar
De 1 a 10
7
|59|43|77|0 |10|  |2 |33|  |  |
|21|47|92|  |69|14|95|  |37|76|
|22|29|1 |27|65|  |58|8 |32|51|
|44|19|25|42|13|4 |15|52|  |  |
|31|40|60|67|7 |73|  |  |82|18|
|63|6 |23|41|56|85|  |35|  |66|
|26|53|12|30|  |  |  |34|17|  |
|71|-2|11|  |24|  |  |  |81|  |
|96|74|  |72|  |  |-1|  |70|91|
|28|36|  |80|3 |55|62|20|  |  |

Turno do JOGADOR2

Pontos do jogador 1 : 624 pontos
Pontos do jogador 2 : 580 pontos

Nos analisados: 296 
Cortes alfa: 34 
Cortes beta: 107 
Tempo de execucao: 0.907 

|59|43|77|0 |10|  |2 |33|  |  |
|21|47|92|  |69|14|95|  |37|76|
|22|29|1 |27|65|  |58|8 |32|51|
|44|19|25|42|13|4 |15|52|  |  |
|31|40|60|67|7 |73|  |  |82|18|
|-2|6 |23|41|56|85|  |35|  |66|
|26|53|12|30|  |  |  |34|17|  |
|71|  |11|  |24|  |  |  |81|  |
|96|74|  |72|  |  |-1|  |70|91|
|28|  |  |80|3 |55|62|20|  |  |

Turno do JOGADOR1

Pontos do jogador 1 : 624 pontos
Pontos do jogador 2 : 643 pontos
Indique a linha a selecionar
De 1 a 10
8
Indique a coluna a selecionar
De 1 a 10
9
|59|43|77|0 |10|  |2 |33|  |  |
|21|47|92|  |69|14|95|  |37|76|
|22|29|1 |27|65|  |58|8 |32|51|
|44|19|25|42|13|4 |15|52|  |  |
|31|40|60|67|7 |73|  |  |82|  |
|-2|6 |23|41|56|85|  |35|  |66|
|26|53|12|30|  |  |  |34|17|  |
|71|  |11|  |24|  |  |  |-1|  |
|96|74|  |72|  |  |  |  |70|91|
|28|  |  |80|3 |55|62|20|  |  |

Turno do JOGADOR2

Pontos do jogador 1 : 705 pontos
Pontos do jogador 2 : 643 pontos

Nos analisados: 103 
Cortes alfa: 12 
Cortes beta: 65 
Tempo de execucao: 0.342 

|59|43|77|0 |10|  |2 |33|  |  |
|21|47|92|  |69|14|95|  |37|76|
|22|29|1 |27|65|  |58|8 |32|51|
|44|19|25|42|13|4 |15|52|  |  |
|31|40|-2|67|7 |73|  |  |82|  |
|  |  |23|41|56|85|  |35|  |66|
|26|53|12|30|  |  |  |34|17|  |
|71|  |11|  |24|  |  |  |-1|  |
|96|74|  |72|  |  |  |  |70|91|
|28|  |  |80|3 |55|62|20|  |  |

Turno do JOGADOR1

Pontos do jogador 1 : 705 pontos
Pontos do jogador 2 : 703 pontos
Indique a linha a selecionar
De 1 a 10
6
Indique a coluna a selecionar
De 1 a 10
10
|59|43|  |0 |10|  |2 |33|  |  |
|21|47|92|  |69|14|95|  |37|76|
|22|29|1 |27|65|  |58|8 |32|51|
|44|19|25|42|13|4 |15|52|  |  |
|31|40|-2|67|7 |73|  |  |82|  |
|  |  |23|41|56|85|  |35|  |-1|
|26|53|12|30|  |  |  |34|17|  |
|71|  |11|  |24|  |  |  |  |  |
|96|74|  |72|  |  |  |  |70|91|
|28|  |  |80|3 |55|62|20|  |  |

Turno do JOGADOR2

Pontos do jogador 1 : 771 pontos
Pontos do jogador 2 : 703 pontos

Nos analisados: 87 
Cortes alfa: 3 
Cortes beta: 98 
Tempo de execucao: 0.296 

|59|43|  |0 |10|  |2 |33|  |  |
|21|47|92|  |69|14|95|  |37|76|
|22|29|1 |27|65|  |58|8 |32|51|
|44|19|25|42|-2|4 |15|52|  |  |
|  |40|  |67|7 |73|  |  |82|  |
|  |  |23|41|56|85|  |35|  |-1|
|26|53|12|30|  |  |  |34|17|  |
|71|  |11|  |24|  |  |  |  |  |
|96|74|  |72|  |  |  |  |70|91|
|28|  |  |80|3 |55|62|20|  |  |

Turno do JOGADOR1

Pontos do jogador 1 : 771 pontos
Pontos do jogador 2 : 716 pontos
Indique a linha a selecionar
De 1 a 10
7
Indique a coluna a selecionar
De 1 a 10
8
|59|  |  |0 |10|  |2 |33|  |  |
|21|47|92|  |69|14|95|  |37|76|
|22|29|1 |27|65|  |58|8 |32|51|
|44|19|25|42|-2|4 |15|52|  |  |
|  |40|  |67|7 |73|  |  |82|  |
|  |  |23|41|56|85|  |35|  |  |
|26|53|12|30|  |  |  |-1|17|  |
|71|  |11|  |24|  |  |  |  |  |
|96|74|  |72|  |  |  |  |70|91|
|28|  |  |80|3 |55|62|20|  |  |

Turno do JOGADOR2

Pontos do jogador 1 : 805 pontos
Pontos do jogador 2 : 716 pontos

Nos analisados: 49 
Cortes alfa: 4 
Cortes beta: 58 
Tempo de execucao: 0.209 

|59|  |  |0 |10|  |2 |33|  |  |
|21|47|92|  |69|14|95|  |37|76|
|22|29|1 |27|65|  |-2|8 |32|51|
|44|19|25|42|  |4 |15|52|  |  |
|  |40|  |67|7 |73|  |  |82|  |
|  |  |23|41|56|  |  |35|  |  |
|26|53|12|30|  |  |  |-1|17|  |
|71|  |11|  |24|  |  |  |  |  |
|96|74|  |72|  |  |  |  |70|91|
|28|  |  |80|3 |55|62|20|  |  |

Turno do JOGADOR1

Pontos do jogador 1 : 805 pontos
Pontos do jogador 2 : 774 pontos
Indique a linha a selecionar
De 1 a 10
5
Indique a coluna a selecionar
De 1 a 10
9
|59|  |  |0 |10|  |2 |33|  |  |
|21|47|92|  |69|14|95|  |37|76|
|22|29|1 |27|65|  |-2|8 |32|51|
|44|19|25|42|  |4 |15|52|  |  |
|  |40|  |67|7 |73|  |  |-1|  |
|  |  |23|41|56|  |  |35|  |  |
|26|53|12|30|  |  |  |  |17|  |
|71|  |11|  |24|  |  |  |  |  |
|96|74|  |72|  |  |  |  |70|91|
|  |  |  |80|3 |55|62|20|  |  |

Turno do JOGADOR2

Pontos do jogador 1 : 887 pontos
Pontos do jogador 2 : 774 pontos

Nos analisados: 71 
Cortes alfa: 14 
Cortes beta: 33 
Tempo de execucao: 0.219 

|59|  |  |0 |10|  |2 |33|  |  |
|21|47|92|  |69|14|95|  |  |76|
|22|29|1 |27|65|  |  |8 |32|51|
|44|19|25|42|  |4 |15|52|  |  |
|  |40|  |67|7 |-2|  |  |-1|  |
|  |  |23|41|56|  |  |35|  |  |
|26|53|12|30|  |  |  |  |17|  |
|71|  |11|  |24|  |  |  |  |  |
|96|74|  |72|  |  |  |  |70|91|
|  |  |  |80|3 |55|62|20|  |  |

Turno do JOGADOR1

Pontos do jogador 1 : 887 pontos
Pontos do jogador 2 : 847 pontos
Indique a linha a selecionar
De 1 a 10
3
Indique a coluna a selecionar
De 1 a 10
10
|59|  |  |0 |10|  |2 |33|  |  |
|21|47|92|  |69|14|95|  |  |76|
|22|29|1 |27|65|  |  |8 |32|-1|
|44|19|25|42|  |4 |  |52|  |  |
|  |40|  |67|7 |-2|  |  |  |  |
|  |  |23|41|56|  |  |35|  |  |
|26|53|12|30|  |  |  |  |17|  |
|71|  |11|  |24|  |  |  |  |  |
|96|74|  |72|  |  |  |  |70|91|
|  |  |  |80|3 |55|62|20|  |  |

Turno do JOGADOR2

Pontos do jogador 1 : 938 pontos
Pontos do jogador 2 : 847 pontos

Nos analisados: 45 
Cortes alfa: 0 
Cortes beta: 41 
Tempo de execucao: 0.101 

|59|  |  |0 |10|  |2 |33|  |  |
|21|47|92|  |69|14|95|  |  |76|
|22|29|1 |27|-2|  |  |8 |32|-1|
|44|19|25|42|  |4 |  |52|  |  |
|  |40|  |67|7 |  |  |  |  |  |
|  |  |23|41|  |  |  |35|  |  |
|26|53|12|30|  |  |  |  |17|  |
|71|  |11|  |24|  |  |  |  |  |
|96|74|  |72|  |  |  |  |70|91|
|  |  |  |80|3 |55|62|20|  |  |

Turno do JOGADOR1

Pontos do jogador 1 : 938 pontos
Pontos do jogador 2 : 912 pontos
Indique a linha a selecionar
De 1 a 10
4
Indique a coluna a selecionar
De 1 a 10
8
|59|  |  |0 |10|  |2 |33|  |  |
|21|47|92|  |69|14|95|  |  |76|
|22|29|1 |27|-2|  |  |8 |32|  |
|44|19|  |42|  |4 |  |-1|  |  |
|  |40|  |67|7 |  |  |  |  |  |
|  |  |23|41|  |  |  |35|  |  |
|26|53|12|30|  |  |  |  |17|  |
|71|  |11|  |24|  |  |  |  |  |
|96|74|  |72|  |  |  |  |70|91|
|  |  |  |80|3 |55|62|20|  |  |

Turno do JOGADOR2

Pontos do jogador 1 : 990 pontos
Pontos do jogador 2 : 912 pontos

Nos analisados: 31 
Cortes alfa: 3 
Cortes beta: 26 
Tempo de execucao: 0.071 

|59|  |  |0 |10|  |2 |33|  |  |
|21|47|92|  |69|14|95|  |  |  |
|22|29|1 |27|  |  |  |8 |32|  |
|44|19|  |42|  |4 |  |-1|  |  |
|  |40|  |-2|7 |  |  |  |  |  |
|  |  |23|41|  |  |  |35|  |  |
|26|53|12|30|  |  |  |  |17|  |
|71|  |11|  |24|  |  |  |  |  |
|96|74|  |72|  |  |  |  |70|91|
|  |  |  |80|3 |55|62|20|  |  |

Turno do JOGADOR1

Pontos do jogador 1 : 990 pontos
Pontos do jogador 2 : 979 pontos
Indique a linha a selecionar
De 1 a 10
2
Indique a coluna a selecionar
De 1 a 10
7
|  |  |  |0 |10|  |2 |33|  |  |
|21|47|92|  |69|14|-1|  |  |  |
|22|29|1 |27|  |  |  |8 |32|  |
|44|19|  |42|  |4 |  |  |  |  |
|  |40|  |-2|7 |  |  |  |  |  |
|  |  |23|41|  |  |  |35|  |  |
|26|53|12|30|  |  |  |  |17|  |
|71|  |11|  |24|  |  |  |  |  |
|96|74|  |72|  |  |  |  |70|91|
|  |  |  |80|3 |55|62|20|  |  |

Turno do JOGADOR2

Pontos do jogador 1 : 1085 pontos
Pontos do jogador 2 : 979 pontos

Nos analisados: 38 
Cortes alfa: 5 
Cortes beta: 28 
Tempo de execucao: 0.074 

|  |  |  |0 |10|  |2 |33|  |  |
|  |47|92|  |69|14|-1|  |  |  |
|22|29|1 |27|  |  |  |8 |32|  |
|44|19|  |42|  |4 |  |  |  |  |
|  |40|  |  |7 |  |  |  |  |  |
|  |  |23|41|  |  |  |35|  |  |
|26|53|-2|30|  |  |  |  |17|  |
|71|  |11|  |24|  |  |  |  |  |
|96|74|  |72|  |  |  |  |70|91|
|  |  |  |80|3 |55|62|20|  |  |

Turno do JOGADOR1

Pontos do jogador 1 : 1085 pontos
Pontos do jogador 2 : 991 pontos
Indique a linha a selecionar
De 1 a 10
3
Indique a coluna a selecionar
De 1 a 10
9
|  |  |  |0 |10|  |2 |33|  |  |
|  |47|92|  |69|14|  |  |  |  |
|22|29|1 |27|  |  |  |8 |-1|  |
|44|19|  |42|  |4 |  |  |  |  |
|  |40|  |  |7 |  |  |  |  |  |
|  |  |  |41|  |  |  |35|  |  |
|26|53|-2|30|  |  |  |  |17|  |
|71|  |11|  |24|  |  |  |  |  |
|96|74|  |72|  |  |  |  |70|91|
|  |  |  |80|3 |55|62|20|  |  |

Turno do JOGADOR2

Pontos do jogador 1 : 1117 pontos
Pontos do jogador 2 : 991 pontos

Nos analisados: 21 
Cortes alfa: 0 
Cortes beta: 19 
Tempo de execucao: 0.045 

|  |  |  |0 |10|  |2 |33|  |  |
|  |  |92|  |69|14|  |  |  |  |
|22|29|1 |27|  |  |  |8 |-1|  |
|44|19|  |42|  |4 |  |  |  |  |
|  |40|  |  |7 |  |  |  |  |  |
|  |  |  |41|  |  |  |35|  |  |
|26|53|  |30|  |  |  |  |17|  |
|71|  |11|  |24|  |  |  |  |  |
|96|-2|  |72|  |  |  |  |70|91|
|  |  |  |80|3 |55|62|20|  |  |

Turno do JOGADOR1

Pontos do jogador 1 : 1117 pontos
Pontos do jogador 2 : 1065 pontos
Indique a linha a selecionar
De 1 a 10
1
Indique a coluna a selecionar
De 1 a 10
8
|  |  |  |0 |10|  |2 |-1|  |  |
|  |  |92|  |69|14|  |  |  |  |
|22|29|1 |27|  |  |  |8 |  |  |
|44|19|  |42|  |4 |  |  |  |  |
|  |40|  |  |7 |  |  |  |  |  |
|  |  |  |41|  |  |  |35|  |  |
|26|53|  |30|  |  |  |  |17|  |
|71|  |11|  |24|  |  |  |  |  |
|96|-2|  |72|  |  |  |  |70|91|
|  |  |  |80|3 |  |62|20|  |  |

Turno do JOGADOR2

Pontos do jogador 1 : 1150 pontos
Pontos do jogador 2 : 1065 pontos

Nos analisados: 18 
Cortes alfa: 3 
Cortes beta: 7 
Tempo de execucao: 0.029 

|  |  |  |0 |10|  |2 |-1|  |  |
|  |  |92|  |69|14|  |  |  |  |
|22|29|1 |27|  |  |  |8 |  |  |
|44|19|  |42|  |4 |  |  |  |  |
|  |40|  |  |7 |  |  |  |  |  |
|  |  |  |41|  |  |  |35|  |  |
|-2|53|  |30|  |  |  |  |17|  |
|71|  |11|  |24|  |  |  |  |  |
|96|  |  |72|  |  |  |  |70|91|
|  |  |  |80|3 |  |  |20|  |  |

Turno do JOGADOR1

Pontos do jogador 1 : 1150 pontos
Pontos do jogador 2 : 1091 pontos
Indique a linha a selecionar
De 1 a 10
2
Indique a coluna a selecionar
De 1 a 10
6
|  |  |  |0 |10|  |2 |  |  |  |
|  |  |92|  |69|-1|  |  |  |  |
|22|29|1 |27|  |  |  |8 |  |  |
|44|19|  |42|  |4 |  |  |  |  |
|  |40|  |  |7 |  |  |  |  |  |
|  |  |  |  |  |  |  |35|  |  |
|-2|53|  |30|  |  |  |  |17|  |
|71|  |11|  |24|  |  |  |  |  |
|96|  |  |72|  |  |  |  |70|91|
|  |  |  |80|3 |  |  |20|  |  |

Turno do JOGADOR2

Pontos do jogador 1 : 1164 pontos
Pontos do jogador 2 : 1091 pontos

Nos analisados: 19 
Cortes alfa: 12 
Cortes beta: 8 
Tempo de execucao: 0.035 

|  |  |  |0 |10|  |2 |  |  |  |
|  |  |92|  |69|-1|  |  |  |  |
|22|29|1 |27|  |  |  |8 |  |  |
|44|19|  |42|  |  |  |  |  |  |
|  |-2|  |  |7 |  |  |  |  |  |
|  |  |  |  |  |  |  |35|  |  |
|  |53|  |30|  |  |  |  |17|  |
|71|  |11|  |24|  |  |  |  |  |
|96|  |  |72|  |  |  |  |70|91|
|  |  |  |80|3 |  |  |20|  |  |

Turno do JOGADOR1

Pontos do jogador 1 : 1164 pontos
Pontos do jogador 2 : 1131 pontos
Indique a linha a selecionar
De 1 a 10
3
Indique a coluna a selecionar
De 1 a 10
8
|  |  |  |0 |10|  |2 |  |  |  |
|  |  |92|  |69|  |  |  |  |  |
|22|29|1 |27|  |  |  |-1|  |  |
|44|19|  |42|  |  |  |  |  |  |
|  |-2|  |  |7 |  |  |  |  |  |
|  |  |  |  |  |  |  |35|  |  |
|  |53|  |30|  |  |  |  |17|  |
|71|  |11|  |24|  |  |  |  |  |
|96|  |  |72|  |  |  |  |70|91|
|  |  |  |  |3 |  |  |20|  |  |

Turno do JOGADOR2

Pontos do jogador 1 : 1172 pontos
Pontos do jogador 2 : 1131 pontos

Nos analisados: 8 
Cortes alfa: 0 
Cortes beta: 9 
Tempo de execucao: 0.016 

|  |  |  |0 |10|  |2 |  |  |  |
|  |  |92|  |69|  |  |  |  |  |
|22|29|1 |27|  |  |  |-1|  |  |
|44|19|  |-2|  |  |  |  |  |  |
|  |  |  |  |7 |  |  |  |  |  |
|  |  |  |  |  |  |  |35|  |  |
|  |53|  |30|  |  |  |  |17|  |
|71|  |11|  |  |  |  |  |  |  |
|96|  |  |72|  |  |  |  |70|91|
|  |  |  |  |3 |  |  |20|  |  |

Turno do JOGADOR1

Pontos do jogador 1 : 1172 pontos
Pontos do jogador 2 : 1173 pontos
Indique a linha a selecionar
De 1 a 10
1
Indique a coluna a selecionar
De 1 a 10
7
|  |  |  |0 |10|  |-1|  |  |  |
|  |  |92|  |69|  |  |  |  |  |
|22|29|1 |27|  |  |  |  |  |  |
|44|19|  |-2|  |  |  |  |  |  |
|  |  |  |  |7 |  |  |  |  |  |
|  |  |  |  |  |  |  |35|  |  |
|  |53|  |30|  |  |  |  |17|  |
|71|  |11|  |  |  |  |  |  |  |
|96|  |  |72|  |  |  |  |70|91|
|  |  |  |  |3 |  |  |  |  |  |

Turno do JOGADOR2

Pontos do jogador 1 : 1174 pontos
Pontos do jogador 2 : 1173 pontos

Nos analisados: 5 
Cortes alfa: 0 
Cortes beta: 2 
Tempo de execucao: 0.008 

|  |  |  |0 |10|  |-1|  |  |  |
|  |  |-2|  |69|  |  |  |  |  |
|22|  |1 |27|  |  |  |  |  |  |
|44|19|  |  |  |  |  |  |  |  |
|  |  |  |  |7 |  |  |  |  |  |
|  |  |  |  |  |  |  |35|  |  |
|  |53|  |30|  |  |  |  |17|  |
|71|  |11|  |  |  |  |  |  |  |
|96|  |  |72|  |  |  |  |70|91|
|  |  |  |  |3 |  |  |  |  |  |

Turno do JOGADOR1

Pontos do jogador 1 : 1174 pontos
Pontos do jogador 2 : 1265 pontos
Indique a linha a selecionar
De 1 a 10
2
Indique a coluna a selecionar
De 1 a 10
5
|  |  |  |0 |10|  |  |  |  |  |
|  |  |-2|  |-1|  |  |  |  |  |
|22|  |1 |27|  |  |  |  |  |  |
|44|19|  |  |  |  |  |  |  |  |
|  |  |  |  |7 |  |  |  |  |  |
|  |  |  |  |  |  |  |35|  |  |
|  |53|  |30|  |  |  |  |17|  |
|71|  |11|  |  |  |  |  |  |  |
|  |  |  |72|  |  |  |  |70|91|
|  |  |  |  |3 |  |  |  |  |  |

Turno do JOGADOR2

Pontos do jogador 1 : 1243 pontos
Pontos do jogador 2 : 1265 pontos

Nos analisados: 4 
Cortes alfa: 1 
Cortes beta: 1 
Tempo de execucao: 0.007 

|  |  |  |0 |10|  |  |  |  |  |
|  |  |  |  |-1|  |  |  |  |  |
|22|  |1 |27|  |  |  |  |  |  |
|44|-2|  |  |  |  |  |  |  |  |
|  |  |  |  |7 |  |  |  |  |  |
|  |  |  |  |  |  |  |35|  |  |
|  |53|  |30|  |  |  |  |17|  |
|71|  |11|  |  |  |  |  |  |  |
|  |  |  |72|  |  |  |  |70|  |
|  |  |  |  |3 |  |  |  |  |  |

Turno do JOGADOR1

Pontos do jogador 1 : 1243 pontos
Pontos do jogador 2 : 1284 pontos
Indique a linha a selecionar
De 1 a 10
3
Indique a coluna a selecionar
De 1 a 10
3
|  |  |  |0 |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |
|22|  |-1|27|  |  |  |  |  |  |
|44|-2|  |  |  |  |  |  |  |  |
|  |  |  |  |7 |  |  |  |  |  |
|  |  |  |  |  |  |  |35|  |  |
|  |53|  |30|  |  |  |  |17|  |
|71|  |11|  |  |  |  |  |  |  |
|  |  |  |72|  |  |  |  |70|  |
|  |  |  |  |3 |  |  |  |  |  |

Turno do JOGADOR2

Pontos do jogador 1 : 1244 pontos
Pontos do jogador 2 : 1284 pontos

Nos analisados: 2 
Cortes alfa: 1 
Cortes beta: 0 
Tempo de execucao: 0.002 

|  |  |  |0 |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |
|22|  |-1|-2|  |  |  |  |  |  |
|44|  |  |  |  |  |  |  |  |  |
|  |  |  |  |7 |  |  |  |  |  |
|  |  |  |  |  |  |  |35|  |  |
|  |53|  |30|  |  |  |  |17|  |
|71|  |11|  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |70|  |
|  |  |  |  |3 |  |  |  |  |  |

Turno do JOGADOR1

Pontos do jogador 1 : 1244 pontos
Pontos do jogador 2 : 1311 pontos
Indique a linha a selecionar
De 1 a 10
4
Indique a coluna a selecionar
De 1 a 10
1
|  |  |  |0 |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |
|  |  |  |-2|  |  |  |  |  |  |
|-1|  |  |  |  |  |  |  |  |  |
|  |  |  |  |7 |  |  |  |  |  |
|  |  |  |  |  |  |  |35|  |  |
|  |53|  |30|  |  |  |  |17|  |
|71|  |11|  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |70|  |
|  |  |  |  |3 |  |  |  |  |  |

Turno do JOGADOR2

Pontos do jogador 1 : 1288 pontos
Pontos do jogador 2 : 1311 pontos

Nos analisados: 1 
Cortes alfa: 0 
Cortes beta: 0 
Tempo de execucao: 0.0 

|  |  |  |0 |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |
|-1|  |  |  |  |  |  |  |  |  |
|  |  |  |  |-2|  |  |  |  |  |
|  |  |  |  |  |  |  |35|  |  |
|  |53|  |30|  |  |  |  |17|  |
|71|  |11|  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |3 |  |  |  |  |  |

Turno do JOGADOR1

Pontos do jogador 1 : 1288 pontos
Pontos do jogador 2 : 1318 pontos

Sem jogadas, ceder jogada!
|  |  |  |0 |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |
|-1|  |  |  |  |  |  |  |  |  |
|  |  |  |  |-2|  |  |  |  |  |
|  |  |  |  |  |  |  |35|  |  |
|  |53|  |30|  |  |  |  |17|  |
|71|  |11|  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |3 |  |  |  |  |  |

Turno do JOGADOR2

Pontos do jogador 1 : 1288 pontos
Pontos do jogador 2 : 1318 pontos

Nos analisados: 1 
Cortes alfa: 0 
Cortes beta: 0 
Tempo de execucao: 0.001 

|  |  |  |0 |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |
|-1|  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |35|  |  |
|  |53|  |-2|  |  |  |  |17|  |
|71|  |11|  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  |  |  |
O jogo terminou!
Vencedor é o JOGADOR2

Pontos do jogador 1 : 1288 pontos
Pontos do jogador 2 : 1348 pontos
----------------------------------------------

## **8. Conclusão**

É com satisfação que apresentamos como concluída a segunda fase deste projeto, integrando no Jogo do Cavalo os conceitos referentes à Teoria de Jogos, com os algoritmos Minimax com cortes AlfaBeta.

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 à Teoria de Jogos, implementando não só o algoritmo alfabeta, como as suas otimizações mais recorrentes, como a memoização, a procura quiescente e a ordenação de nós.

O presente projeto permitiu a aplicação real do conceito de teoria de jogos, direcionado ao Jogo do Cavalo, um problema clássico no ramo da Inteligência Artificial, que revelou o enorme potencial da implementação deste algoritmo e do uso dos cortes alfa-beta na árvore de jogo.

Damos assim por concluída a segunda e última fase deste projeto, apresentando como concluídos os objetivos do projeto, possibilitando o jogo Humano-Computador e Computador-Computador no âmbito do Jogo do Cavalo.