- Universidade: [Instituto Politécnico de Setúbal]
- Projeto: [Projeto 1 - Jogo do Cavalo: Jogador Único]
- Aluno(s): [Julio Sousa (201902012)] [Marco Ventura (202000792)]
- Data: 18/12/2023
Nesta secção, descrevemos a arquitetura geral do sistema, incluindo:
- Identificação dos módulos
- Módulo de procura (Ficheiro procura.LISP)
- Módulo de interação com o utiizador (Ficheiro projeto.LISP)
- Módulo de mecânicas do Jogo (Ficheiro puzzle.LISP)
- Objetivos individuais de cada módulo
- Módulo de procura: Contém a implementação dos algoritmos de pesquisa sejam BFS, DFS e A*
- Módulo de interação com o utiizador: Carrega os outros ficheiros de código, escreve e lê ficheiros, e trata da interação com o utilizador.
- Módulo de mecânicas do Jogo: Relacionado com a implementação do jogo, contém funções relativamente a regras e jogabilidade.
- Conexões entre os módulos
A conexão entre os módulos faz-se através da função load no ficheiro projeto.LISP, no qual carregam-se os dos módulos Procura e Mecânicas.
- Fluxo de informações dentro de cada módulo e entre módulos
O primeiro módulo a ser executado é o Módulo de interação com o utilizador, sendo que através deste modulo são obtidos os parâmetros iniciais para chamar a função preparação do módulo de procura e a mesma vai executar o algoritmo de procura pretendido, interagindo com o módulo de Mecânicas.
Aqui, abordamos as entidades do sistema, tanto do ponto de vista do domínio da aplicação como do ponto de vista da implementação.
(
(2 NIL 4 NIL 6 NIL 8 NIL 10 NIL)
(NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL)
(NIL 3 NIL 5 NIL 7 NIL 9 NIL 11)
(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 NIL NIL NIL NIL)
(NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL)
)
Observamos um tabuleiro de dimensões 10x10 onde as casas podem adquirir os valores:
- T: Posição atual do cavalo.
- NIL: Casa marcada como visitada e inacessível pelo cavalo.
- "Valor Numérico": Casa acessível pelo cavalo com o valor disponível para acumular.
Para gerar o tabuleiro temos a função tabuleiro-aleatorio
;; tabuleiro-aleatorio
(defun tabuleiro-aleatorio (lista &optional (n 10))
"Recebe a lista e opcionalmente o n, Retorna o tabuleiro baralhado"
(cond
((null lista) nil)
(t (cons (subseq lista 0 n) (tabuleiro-aleatorio (subseq lista n) n)))
)
)Na interação com o tabuleiro temos seguintes:
- posicao-casa: Recebe o tabuleiro e o valor da casa, as coordenadas da casa, NIL caso não exista
;; posicao-casa
(defun posicao-casa (tabuleiro casa)
"Recebe o tabuleiro e o valor da casa, as coordenadas da casa, NIL caso não exista"
(let* (
(lista (mapcar #'(lambda (linha) (position casa linha :test #'eql)) tabuleiro))
(j (find-if #'(lambda (x) (not (null x))) lista))
)
(cond
((null j) NIL)
(t (list (position-if #'(lambda (x) (not (null x))) lista) j))
)
)
)- substituir: Substitui o VALOR nas coordenadas (INDICE1, INDICE2) do TABULEIRO.
(defun substituir (indice1 indice2 tabuleiro &optional (valor nil))
"Substitui o VALOR nas coordenadas (INDICE1, INDICE2) do TABULEIRO."
(let* ((linha-substituida (substituir-posicao indice2 (linha indice1 tabuleiro) valor)))
(substituir-posicao indice1 tabuleiro linha-substituida))
)-celula: Função que recebe dois índices e o tabuleiro e retorna o valor presente nessa célula do tabuleiro.
(defun celula (linha coluna tabuleiro)
"Função que recebe dois índices e o tabuleiro e retorna o valor presente nessa célula do tabuleiro."
(if (and (integerp linha) (integerp coluna) (< linha (length tabuleiro)) (< coluna (length (first tabuleiro))))
(nth coluna (nth linha tabuleiro))
nil
)
) (
(2 NIL 4 NIL T NIL 8 NIL 10 NIL)
(NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL)
(NIL 3 NIL 5 NIL 7 NIL 9 NIL 11)
(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 NIL NIL NIL NIL)
(NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL)
)
O cavalo possui um conjunto de operadores que representam os movimentos possíveis num determinado estado. O máximo de movimentos possíveis serão 8, desde que essas casas não tenham sido ainda visitadas ou removidas pela regra dos simétricos ou duplos. (Os custos de aplicação dos operadores são considerados constantes e unitários)
Exemplo de uma função operador:
;; operador-1
(defun operador-1 (estado)
"Recebe o estado, e define o operador, movimento a seguir"
(definir-operador '+ 2 '- 1 (car estado) (second estado))
)É importante observar que para os movimentos do cavalo tambem são adicionadas um conjunto de regras. Que são a seguintes:
- 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 outro nú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.
Com o objetivo de resolver estas dos problematicas foram implementadas a seguintes funções:
;; simetrico-solucao
(defun simetrico-solucao (coordenada-objetivo tabuleiro)
"Recebe o tabuleiro, valor da coordenada objetivvo e o valor acumulado, retorna o novo estado"
(let* (
(valor-celula (celula (car coordenada-objetivo) (second coordenada-objetivo) tabuleiro))
(valor-simetrico (valor-simetrico valor-celula))
(posicao-peca (posicao-casa tabuleiro valor-simetrico))
)
(cond
((not (null posicao-peca)) (substituir (car posicao-peca) (second posicao-peca) tabuleiro))
(t tabuleiro)
)
)
);; duplo-solucao
(defun duplo-solucao (tabuleiro)
"Recebe o tabuleiro e o valor acumulado, retorna o novo estado"
(let* (
(duplos-atuais (valores-duplos-atuais tabuleiro))
)
(cond
((not (null duplos-atuais))
(let* (
(escolha (random (length duplos-atuais)))
(posicao-peca (posicao-casa tabuleiro (nth escolha duplos-atuais)))
)
(substituir (car posicao-peca) (second posicao-peca) tabuleiro)
)
)
(t tabuleiro)
)
)
)Nesta secção, dividimos o sistema em algoritmos e explicamos cada um deles.
Para todos os algoritmos de procura é realizada uma preparação prévia com o objetivo de que o utlizador selecione a primeira casa é a partir de ali começa a pesquisa da solução ao problema. Dita preparação tem o seguinte comportamento:
;; preparacao
(defun preparacao (algoritmo tabuleiro valor-objetivo)
(imprimir-tabuleiro tabuleiro)
(let* (
(coordenada-objetivo (escolher-coordenadas (obter-coordenadas-iniciais tabuleiro)))
(valor-da-coordenada-objetivo (celula (car coordenada-objetivo) (second coordenada-objetivo) tabuleiro))
(novo-tabuleiro (substituir (car coordenada-objetivo) (second coordenada-objetivo) tabuleiro T))
(resultado
(let* (
(inicio (get-internal-real-time))
(resultado-algoritmo (cond
((equal algoritmo 'bfs)
(funcall algoritmo (criar-no (list novo-tabuleiro valor-da-coordenada-objetivo) 1 0 0 (criar-no (list tabuleiro 0))) 'no-solucaop 'sucessores (operadores) valor-objetivo)
)
((equal algoritmo 'dfs)
(let* ((profundidade (escolher-profundidade)))
(funcall algoritmo (criar-no (list novo-tabuleiro valor-da-coordenada-objetivo) 1 0 0 (criar-no (list tabuleiro 0))) 'no-solucaop 'sucessores (operadores) valor-objetivo :d profundidade)
)
)
((equal algoritmo 'aestrela)
(let* ((heuristica-escolhida (mostrar-menu (opcoes-heuristicas))))
(let* (
(h (cond
((= heuristica-escolhida 0) (calculo-heuristica valor-da-coordenada-objetivo 1 novo-tabuleiro))
(t (heuristica-cavalo (criar-no (list novo-tabuleiro valor-da-coordenada-objetivo) 1 0 0 (criar-no (list tabuleiro 0)))))
)
)
)
(funcall algoritmo (criar-no (list novo-tabuleiro valor-da-coordenada-objetivo) 1 h (f 1 h) (criar-no (list tabuleiro 0))) 'no-solucaop 'sucessores (operadores) valor-objetivo :heuristica heuristica-escolhida)
)
)
)
)
)
)
(let* ((fin (get-internal-real-time)))
(list resultado-algoritmo (- fin inicio))
)
)
)
)
(cond
((null (car resultado)) (format t "O problema nao tem solucao."))
(t (imprimir-resultado algoritmo resultado))
)
)
)Estrutura do no e construtor
Foram implementadas diversas funções para a criação, alteração e retorna das deversas carateristicas de um no, como são seguintes:
;; criar-no
(defun criar-no (estado &optional (g 0) (h 0) (f 0) (pai nil))
"Recebe o tabuleiro e opcionalmente o acumulador de pontos, heuristica e o no pai, retorna um novo no"
(list estado g h f pai)
)
;;; Metodos seletores
;; no-estado
(defun no-estado (no)
"Recebe o no, retorna o estado"
(car no)
)
;; no-pontos-acumulados
(defun no-pontos-acumulados (no)
"Recebe o no, retorna os pontos acumulados"
(second (car no))
)
;; no-tabuleiro
(defun no-tabuleiro (no)
"Recebe o no e retorna o tabuleiro"
(car (car no))
)
;; no-profundidade
(defun no-profundidade (no)
"Recebe o no, retorna a profundidade"
(second no)
)
;; no-heuristica
(defun no-heuristica (no)
"Recebe o no, retorna a heuristica"
(third no)
)
;; no-heuristica
(defun no-interesse (no)
"Recebe o no, retorna o interesse"
(fourth no)
)
;; no-pai
(defun no-pai (no)
"Recebe o no, retorna no pai"
(fifth no)
)Validação da solução do algoritmo
Para validar se um no é o nó solução foi implementada a seguinte função:
;; no-solucaop
(defun no-solucaop (no valor-objetivo)
"Recebe o no e o valor objetivo, retorna T se os pontos acumulados >= aos pontos objetivo, NIL caso contrario"
(>= (no-pontos-acumulados no) valor-objetivo)
)Operadores
Os operadores foram abordados anteriormente neste documento e eles são encarregados de ditar as ações do cavalo neste jogo.
No total temos 8 operadores para os 8 posiveis movimentos do cavalo, as funções para representar cada operador são as seguintes:
;; operadores
(defun operadores ()
"Retorna predicados referente aos operadores"
(list 'operador-1 'operador-2 'operador-3 'operador-4 'operador-5 'operador-6 'operador-7 'operador-8)
)
;; operador-1
(defun operador-1 (estado)
"Recebe o estado, e define o operado, movimento a seguir"
(definir-operador '+ 2 '- 1 (car estado) (second estado))
)
;; operador-2
(defun operador-2 (estado)
"Recebe o estado, e define o operado, movimento a seguir"
(definir-operador '+ 2 '+ 1 (car estado) (second estado))
)
;; operador-3
(defun operador-3 (estado)
"Recebe o estado, e define o operado, movimento a seguir"
(definir-operador '+ 1 '+ 2 (car estado) (second estado))
)
;; operador-4
(defun operador-4 (estado)
"Recebe o estado, e define o operado, movimento a seguir"
(definir-operador '- 1 '+ 2 (car estado) (second estado))
)
;; operador-5
(defun operador-5 (estado)
"Recebe o estado, e define o operado, movimento a seguir"
(definir-operador '- 2 '+ 1 (car estado) (second estado))
)
;; operador-6
(defun operador-6 (estado)
"Recebe o estado, e define o operado, movimento a seguir"
(definir-operador '- 2 '- 1 (car estado) (second estado))
)
;; operador-7
(defun operador-7 (estado)
"Recebe o estado, e define o operado, movimento a seguir"
(definir-operador '- 1 '- 2 (car estado) (second estado))
)
;; operador-8
(defun operador-8 (estado)
"Recebe o estado, e define o operado, movimento a seguir"
(definir-operador '+ 1 '- 2 (car estado) (second estado))
)
;; definir-operador
(defun definir-operador (pre-op-i valor-i pre-op-j valor-j tabuleiro valor-acumulado)
"Define qual é o operador a seguir"
(let* (
(posicao (posicao-cavalo tabuleiro))
)
(cond
((null posicao) NIL)
(t (let* (
(coordenada-objetivo (list (funcall pre-op-i (first posicao) valor-i) (funcall pre-op-j (second posicao) valor-j)))
)
(cond
((e-validop (car coordenada-objetivo) (second coordenada-objetivo) tabuleiro)
(let* ((valor-objetivo (celula (car coordenada-objetivo) (second coordenada-objetivo) tabuleiro)))
(list (mover posicao coordenada-objetivo (escolher-solucao coordenada-objetivo tabuleiro)) (+ valor-acumulado valor-objetivo))
; (list (mover posicao coordenada-objetivo tabuleiro) (+ valor-acumulado valor-objetivo))
)
)
(t NIL)
)
)
)
)
)
)Sucessores
Os sucessores definem os nós resultantes de cada nó expandido no algoritmo. E a criação do sucessores tem a seguinte estrutura:
;; novo-sucessore
(defun novo-sucessor (no nome-operador valor-objetivo heuristica)
"Recebe o no e o predicado do operador, retorna o no sucessor, NIL caso no existir o no sucessor"
(let* ((resultado (funcall nome-operador (no-estado no))))
(cond
((null resultado) NIL)
(t
(let* (
(h (cond
((= heuristica 0) (calculo-heuristica valor-objetivo (second resultado) (car resultado)))
(t (heuristica-cavalo no))
)
)
)
(list (criar-no resultado (1+ (no-profundidade no)) h (f (1+ (no-profundidade no)) h) no))
)
)
)
)
)
;; sucessores
(defun sucessores (no operadores &optional (valor-objetivo 0) (heuristica 0))
"Recebe o no e os operadores, retorna os nos sucessores ao no, NIL caso não existir sucessores"
(apply #'append (mapcar #'(lambda (nome-operador)
(novo-sucessor no nome-operador valor-objetivo heuristica)
) operadores))
)Heurística
Neste projeto foram abordadas 2 heurísticas:
- A heurística baseada em privilegiar visitar as casas com o maior número de pontos.
- A heuristica baseada na adaptação a distança manhattan mas com a diferença que a casa objetivo é a casa de maior valor no tabuleiro
Para implementação e calculo destas heurísticas foram implementadas um conjuntos de funções:
(defun f (g h)
"Recebe a profundidade e a heuristica, retorna a soma de g e h"
(+ g h)
)
;; calculo-heuristica
(defun calculo-heuristica (valor-objetivo valor-acumulado tabuleiro)
"Calcula a heuristica h(x) = o(x)/m(x) onde o(x) é o número de pontos que faltam para atingir o valor definido como objetivo e m(x) a média por casa dos pontos que constam no tabuleiro"
(/ (- valor-objetivo valor-acumulado) (m tabuleiro))
)
;; m
(defun m (tabuleiro)
"Recebe o tabuleiro, Retorna a média por casa dos pontos que constam no tabuleiro"
(let* ((lista-sem-nil (apply #'append (mapcar #'(lambda (lista) (remove-if #'(lambda (n) (or (null n) (equal (write-to-string n) "T"))) lista)) tabuleiro))))
(cond
((null lista-sem-nil) 1)
(t (/ (apply #'+ lista-sem-nil) (length lista-sem-nil)))
)
)
)
;; heuristica-cavalo
(defun heuristica-cavalo (no)
"Recebe o no, coordenada objetivo e o valor objetivo, Retorna a heuristica pretendida"
(let* ((valor-objetivo (let* ((lista-sem-nil (apply #'append (mapcar #'(lambda (lista) (remove-if #'(lambda (n) (or (null n) (equal (write-to-string n) "T"))) lista)) (no-tabuleiro no)))))
(cond
((null lista-sem-nil) 0)
(t (apply #'max lista-sem-nil))
)
))
(coordenada-objetivo (posicao-casa (no-tabuleiro no) valor-objetivo))
(coordenada-cavalo (let* ((p (posicao-cavalo (no-tabuleiro no))))
(cond ((null p) '(0 0)) (t p) )
)
)
(dm (distanca-manhattan coordenada-cavalo coordenada-objetivo))
(pontos-acumulados (no-pontos-acumulados no)))
(+ (* 0.5 dm) pontos-acumulados)))
;; distanca-manhattan
(defun distanca-manhattan (p1 p2)
"Calcula a distanca Manhattan entre dois posicoes no tabuleiro"
(let ((x1 (first p1))
(y1 (second p1))
(x2 (first p2))
(y2 (second p2)))
(+ (abs (- x1 x2)) (abs (- y1 y2)))))
Algoritmos de pesquisa
Foram implementados 3 algoritmos de pesquisa:
- BFS (Breadth First Search)
- DFS (Depth First Search)
- A*
- BFS (Breadth First Search)
BFS é um algoritmo de pesquisa em grafos que explora todos os vértices de um nível antes de passar para o próximo nível. Começa pelo nó inicial e visita todos os seus vizinhos antes de se mover para os vizinhos dos vizinhos.
Para o efeito foi criada a seguinte função recursiva:
;; bfs
(defun bfs (no-inicial f-objetivo f-sucessores operadores valor-objetivo &key (abertos nil) (fechados nil) (d nil) (heuristica 0))
"Através do algoritmo bfs, retorna o no solução, NIL caso contrario"
(labels (
(recursiva (abertos-atual fechados-atual nos-gerados)
(cond
((null abertos-atual) NIL)
(t (let* (
(no-atual (car abertos-atual))
(sucessores (funcall f-sucessores no-atual operadores valor-objetivo))
(novos-abertos (inserir-bfs (cdr abertos-atual) sucessores))
(novos-fechados (cons no-atual fechados-atual))
)
(cond
((funcall f-objetivo no-atual valor-objetivo) (list no-atual novos-abertos novos-fechados (+ nos-gerados (length sucessores))))
(t (recursiva novos-abertos novos-fechados (+ nos-gerados (length sucessores))))
)
)
)
)
)
)
(recursiva (cons no-inicial abertos) fechados 0)
)
)- DFS (Depth First Search)
DFS é um algoritmo de pesquisa em grafos que explora o máximo possível ao longo de um ramo antes de retroceder. Começa pelo nó inicial e mergulha profundamente até atingir o fim de um caminho antes de retroceder.
Para o efeito foi criada a seguinte função recursiva:
;; dfs
(defun dfs (no-inicial f-objetivo f-sucessores operadores valor-objetivo &key (abertos nil) (fechados nil) (d nil) (heuristica 0) (heuristica 0))
"Através do algoritmo dfs, retorna o nó solução, NIL caso contrário."
(labels (
(recursiva (abertos-atual fechados-atual nos-gerados)
(cond
((null abertos-atual) NIL)
(t (let* (
(no-atual (car abertos-atual))
(sucessores (funcall f-sucessores no-atual operadores valor-objetivo))
(novos-abertos (cond
((and (not (null d)) (> (no-profundidade no-atual) d)) (recursiva (cdr abertos-atual)))
(t (inserir-dfs (cdr abertos-atual) sucessores))
)
)
(novos-fechados (cons no-atual fechados-atual))
)
(cond
((funcall f-objetivo no-atual valor-objetivo) (list no-atual novos-abertos novos-fechados (+ nos-gerados (length sucessores))))
(t (recursiva novos-abertos novos-fechados (+ nos-gerados (length sucessores))))
)
)
)
)
)
)
(recursiva (cons no-inicial abertos) fechados 0)
)
)- A*
A* é um algoritmo de pesquisa heurística que combina a eficiência do Dijkstra com uma heurística para estimar o custo restante até o objetivo. Avalia os nós com base no custo do caminho percorrido e na estimativa do custo restante até o objetivo.
Para o efeito foi criada a seguinte função recursiva:
;; aestrela
(defun aestrela (no-inicial f-objetivo f-sucessores operadores valor-objetivo &key (abertos nil) (fechados nil) (d nil) (heuristica 0))
"Através do algoritmo A*, retorna o nó solução, NIL caso contrário."
(labels (
(recursiva (abertos-atual fechados-atual nos-gerados)
(cond
((null abertos-atual) NIL)
(t (let* (
(no-atual (no-menor-custo abertos-atual))
(sucessores (funcall f-sucessores no-atual operadores valor-objetivo))
(novos-abertos (inserir-aestrela (remover-no no-atual abertos-atual) fechados-atual sucessores))
(novos-fechados (cons no-atual fechados-atual))
)
(cond
((funcall f-objetivo no-atual valor-objetivo) (list no-atual novos-abertos novos-fechados (+ nos-gerados (length sucessores))))
(t (recursiva novos-abertos novos-fechados (+ nos-gerados (length sucessores))))
)
)
)
)
)
)
(recursiva (cons no-inicial abertos) fechados 0)
)
)BFS
| Problema | Valor acumulado | Opção | Nós gerados | Nós expandidos | Penetrância | Profundidade | FRM | Tempo | Observações |
|---|---|---|---|---|---|---|---|---|---|
| A | A0 | Não tem solução | |||||||
| A | 72 | B0 | 2 | 3 | 3/2 | 3 | 1 micro-segundos | ||
| A | C0 | Não tem solução | |||||||
| B | 65 | A0 | 9 | 10 | 10/9 | 10 | 2 micro-segundos | ||
| B | 60 | C0 | 9 | 10 | 8/9 | 8 | 3 micro-segundos | ||
| B | E0 | Não tem solução | |||||||
| B | G0 | Não tem solução | |||||||
| B | I0 | Não tem solução | |||||||
| C | 272 | A0 | 16 | 13 | 3/8 | 6 | 4 micro-segundos | ||
| C | B0 | Não tem solução | |||||||
| C | C0 | Não tem solução | |||||||
| C | D0 | Não tem solução | |||||||
| C | F0 | Não tem solução | |||||||
| D | 665 | A0 | 40 | 40 | 13/40 | 13 | 14 micro-segundos | ||
| D | 665 | B0 | 32 | 31 | 3/8 | 12 | 10 micro-segundos | ||
| D | 665 | C0 | 29 | 30 | 12/29 | 12 | 10 micro-segundos | ||
| D | D0 | Não tem solução | |||||||
| D | E0 | Não tem solução | |||||||
| D | 661 | F0 | 36 | 36 | 1/3 | 12 | 12 micro-segundos | ||
| D | 638 | G0 | 29 | 28 | 12/29 | 12 | 11 micro-segundos | ||
| D | H0 | Não tem solução | |||||||
| D | I0 | Não tem solução | |||||||
| D | 657 | J0 | 35 | 34 | 12/35 | 12 | 11 micro-segundos | ||
| E | B0 | Stack overflow | |||||||
| E | F0 | Stack overflow (deep) | |||||||
| E | J0 | Stack overflow (deep) | |||||||
| F | Todas as opções | Stack overflow (deep) |
DFS
| Problema | Valor acumulado | Opção | Nós gerados | Nós expandidos | Penetrância | Profundidade | FRM | Tempo | Observações |
|---|---|---|---|---|---|---|---|---|---|
| A | A0 | Não tem solução | |||||||
| A | 72 | B0 | 2 | 3 | 3/2 | 3 | 1046 micro-segundos | ||
| A | C0 | Não tem solução | |||||||
| B | 65 | A0 | 9 | 10 | 10/9 | 10 | 1428 micro-segundos | ||
| B | 60 | C0 | 9 | 10 | 8/9 | 8 | 1592 micro-segundos | ||
| B | E0 | Não tem solução | |||||||
| B | G0 | Não tem solução | |||||||
| B | I0 | Não tem solução | |||||||
| C | 272 | A0 | 11 | 8 | 6/11 | 6 | 1606 micro-segundos | ||
| C | B0 | Não tem solução | |||||||
| C | C0 | Não tem solução | |||||||
| C | D0 | Não tem solução | |||||||
| C | F0 | Não tem solução | |||||||
| D | A0 | Não tem solução | |||||||
| D | 665 | B0 | 16 | 13 | 3/4 | 12 | 1218 micro-segundos | ||
| D | 665 | C0 | 27 | 26 | 4/9 | 12 | 1406 micro-segundos | ||
| D | D0 | Não tem solução | |||||||
| D | E0 | Não tem solução | |||||||
| D | 665 | F0 | 18 | 14 | 2/3 | 12 | 976 micro-segundos | ||
| D | 665 | G0 | 20 | 17 | 13/20 | 13 | 1001 micro-segundos | ||
| D | H0 | Não tem solução | |||||||
| D | 643 | I0 | 31 | 30 | 10/31 | 10 | 1606 micro-segundos | ||
| D | 657 | J0 | 19 | 17 | 12/19 | 12 | 1689 micro-segundos | ||
| E | B0 | Stack Overflow (Deep) | |||||||
| E | F0 | Stack Overflow (Deep) | |||||||
| E | J0 | Stack Overflow (Deep) | |||||||
| F | Todas as opções | Stack Overflow (Deep) |
A
| Problema | Valor acumulado | Opção | Nós gerados | Nós expandidos | Penetrância | Profundidade | FRM | Tempo | Observações |
|---|---|---|---|---|---|---|---|---|---|
| A | Não tem solução | ||||||||
| A | 72 | B0 | 2 | 3 | 3/2 | 3 | 4143 micro-segundos | ||
| A | Não tem solução | ||||||||
| B | 65 | A0 | 9 | 10 | 10/9 | 10 | 1686 micro-segundos | ||
| B | 60 | C0 | 8 | 8 | 1 | 8 | 1339 micro-segundos | ||
| B | E0 | Não tem solução | |||||||
| B | G0 | Não tem solução | |||||||
| B | I0 | Não tem solução | |||||||
| C | 282 | A0 | 14 | 11 | 3/7 | 6 | 1559 micro-segundos | ||
| C | B0 | Não tem solução | |||||||
| C | C0 | Não tem solução | |||||||
| C | D0 | Não tem solução | |||||||
| C | F0 | Não tem solução | |||||||
| D | 665 | A0 | 39 | 37 | 1/3 | 13 | 1484 micro-segundos | ||
| D | 665 | B0 | 32 | 29 | 3/8 | 12 | 1307 micro-segundos | ||
| D | 665 | C0 | 21 | 21 | 4/7 | 12 | 1212 micro-segundos | ||
| D | D0 | Não tem solução | |||||||
| D | E0 | Não tem solução | |||||||
| D | 661 | F0 | 35 | 30 | 12/35 | 12 | 1240 micro-segundos | ||
| D | 661 | G0 | 23 | 21 | 12/23 | 12 | 1243 micro-segundos | ||
| D | H0 | Não tem solução | |||||||
| D | I0 | Não tem solução | |||||||
| D | 657 | J0 | 32 | 27 | 3/8 | 12 | 2878 micro-segundos | ||
| E | Todas as opções | Stack Overflow (Deep) | |||||||
| F | Todas as opções | Stack Overflow (Deep) |
Aqui descrevemos as opções de implementação que foram escolhidas em vez de outras alternativas. Certas opções podem não ser óbvias, e é importante documentá-las.
-
Por obrigação desta cadeira os algoritmos de pesquisa foram feitos de forma recursiva, sendo que de forma iterativa proporcionam melhores resultados, foram deixadas as soluções iterativas comentadas para caso de teste.
-
Devido à pouca memória disponibilizada pelo Lisp, evitou-se o uso excessivo de funções recursivas, em substituição optou-se por usar funções de ordem superior.
Nesta seção, discutimos:
- Devido à pouca memória disponibilizada pelo Lisp alguns problemas apresentam "Stack Overflow" sobre tudo quando é abordada uma solução recursiva.
- Para evitar este problema poderíamos melhorar as funções usando soluções iterativas ou funções de ordem superior.
- A implementação das soluções Bónus não foi implementada, funções Simplified Memory‒Bounded A* (SMA*), Iterative Deepening A* (IDA*) e Recursive Best First Search (RBFS)
O projeto do jogo do cavalo, explorando os algoritmos de pesquisa em largura (BFS), pesquisa em profundidade (DFS) e A*, revelou-se uma jornada envolvente no campo da inteligência artificial e resolução de problemas complexos. Ao longo do manual técnico, foram abordadas as implementações detalhadas desses algoritmos e suas aplicações no contexto específico do tabuleiro de xadrez com movimentos de cavalo.
O algoritmo BFS, com sua abordagem de pesquisa nivelada, mostrou-se eficaz para encontrar soluções ótimas quando a prioridade é alcançar o objetivo com o menor número de movimentos possíveis. A sua característica de expandir os nós em camadas proporciona uma visão clara das soluções mais curtas.
A pesquisa em profundidade (DFS), por outro lado, revelou-se útil para explorar a fundo os caminhos do tabuleiro, proporcionando uma compreensão abrangente das possíveis soluções. No entanto, é crucial lidar com seus desafios, como ciclos e caminhos mais longos.
O algoritmo A* apresentou um equilíbrio eficiente entre otimização e exploração, incorporando uma heurística inteligente para guiar a pesquisa. Isso mostrou-se particularmente valioso em cenários complexos, permitindo encontrar soluções rápidas e eficientes.
Ao implementar estes algoritmos, ganhámos insights valiosos sobre a importância da escolha do algoritmo adequado para diferentes contextos. Cada abordagem tem seus pontos fortes e limitações, e a escolha dependerá das características específicas do problema em questão.
Em resumo, este manual técnico proporciona uma visão aprofundada do desenvolvimento e implementação de algoritmos de pesquisa para o jogo do cavalo.
- Universidade: [Instituto Politécnico de Setúbal]
- Projeto: [Projeto 2 - Jogo do Cavalo]
- Aluno(s): [Julio Sousa (201902012)]
- Data: 26/01/2024
O sistema do Jogo do Cavalo consiste em diversos módulos interligados para permitir a interação entre jogadores humanos e computadores, bem como a implementação dos algoritmos de inteligência artificial necessários para a jogabilidade. A arquitetura geral do sistema compreende:
- Módulo de Interface com o Utilizador (Ficheiro interact.LISP)
- Módulo de Lógica do Jogo (Ficheiro jogo.LISP)
- Módulo de Algoritmos de Inteligência Artificial (Ficheiro algoritmo.LISP)
O sistema inclui as seguintes entidades principais:
(
(NIL 25 63 -1 42 1 4 84 70 10 )
(13 0 8 49 94 NIL 85 40 99 NIL)
(24 NIL NIL 61 53 50 98 89 33 64 )
(18 54 31 65 83 48 47 28 7 21 )
(NIL 72 NIL 81 80 88 87 45 51 22 )
(27 52 56 19 35 -2 30 34 29 5 )
(14 36 39 NIL 82 68 12 73 16 57 )
(17 41 11 69 NIL 59 43 26 92 58 )
(NIL 86 NIL 37 93 38 75 78 71 3 )
(NIL 76 95 46 91 74 96 NIL NIL 67 )
)
Observamos um tabuleiro de dimensões 10x10 onde as casas podem adquirir os valores:
- -1: Posição atual do jogador 1.
- -2: Posição atual do jogador 2.
- NIL: Casa marcada como visitada e inacessível pelos jogadores.
- "Valor Numérico": Casa acessível pelos jogadores com o valor disponível para acumular.
Para gerar o tabuleiro temos a função tabuleiro-aleatorio
;; tabuleiro-aleatorio
(defun tabuleiro-aleatorio (lista &optional (n 10))
"Recebe a lista e opcionalmente o n, Retorna o tabuleiro baralhado"
(cond
((null lista) nil)
(t (cons (subseq lista 0 n) (tabuleiro-aleatorio (subseq lista n) n)))
)
)Na interação com o tabuleiro temos seguintes:
- posicao-casa: Recebe o tabuleiro e o valor da casa, as coordenadas da casa, NIL caso não exista
;; posicao-casa
(defun posicao-casa (tabuleiro casa)
"Recebe o tabuleiro e o valor da casa, as coordenadas da casa, NIL caso não exista"
(let* (
(lista (mapcar #'(lambda (linha) (position casa linha :test #'eql)) tabuleiro))
(j (find-if #'(lambda (x) (not (null x))) lista))
)
(cond
((null j) NIL)
(t (list (position-if #'(lambda (x) (not (null x))) lista) j))
)
)
)- substituir: Substitui o VALOR nas coordenadas (INDICE1, INDICE2) do TABULEIRO.
(defun substituir (indice1 indice2 tabuleiro &optional (valor nil))
"Substitui o VALOR nas coordenadas (INDICE1, INDICE2) do TABULEIRO."
(let* ((linha-substituida (substituir-posicao indice2 (linha indice1 tabuleiro) valor)))
(substituir-posicao indice1 tabuleiro linha-substituida))
)- celula: Função que recebe dois índices e o tabuleiro e retorna o valor presente nessa célula do tabuleiro.
(defun celula (linha coluna tabuleiro)
"Função que recebe dois índices e o tabuleiro e retorna o valor presente nessa célula do tabuleiro."
(if (and (integerp linha) (integerp coluna) (< linha (length tabuleiro)) (< coluna (length (first tabuleiro))))
(nth coluna (nth linha tabuleiro))
nil
)
)Jogador: Representa os jogadores, tanto humanos quanto computadores, e mantém o estado do jogo para cada jogador.
O cavalo possui um conjunto de operadores que representam os movimentos possíveis num determinado estado. O máximo de movimentos possíveis serão 8, desde que essas casas não tenham sido ainda visitadas ou removidas pela regra dos simétricos, duplos ou o outro jogador.
Exemplo de uma função operador:
;; operador-1
(defun operador-1 (posicao)
"Recebe a posicao retorna a coordenada"
(list (+ (car posicao) 2) (- (second posicao) 1))
)É importante observar que para os movimentos do cavalo tambem são adicionadas um conjunto de regras. Que são a seguintes:
- 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 outro nú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.
Com o objetivo de resolver estas dos problematicas foram implementadas a seguintes funções:
;; simetrico-solucao
(defun simetrico-solucao (coordenada-objetivo tabuleiro)
"Recebe o tabuleiro, valor da coordenada objetivvo e o valor acumulado, retorna o novo estado"
(let* (
(valor-celula (celula (car coordenada-objetivo) (second coordenada-objetivo) tabuleiro))
(valor-simetrico (valor-simetrico valor-celula))
(posicao-peca (posicao-casa tabuleiro valor-simetrico))
)
(cond
((not (null posicao-peca)) (substituir (car posicao-peca) (second posicao-peca) tabuleiro))
(t tabuleiro)
)
)
);; duplo-solucao
(defun duplo-solucao (coordenada-objetivo tipo-jogo jogador tabuleiro)
"Recebe o tabuleiro e o valor acumulado, retorna o novo estado"
(let* (
(duplos-atuais (valores-duplos-atuais (celula (car coordenada-objetivo) (second coordenada-objetivo) tabuleiro) tabuleiro))
)
(cond
((null duplos-atuais) tabuleiro)
(t
(let* (
(escolha (cond
((and (eql tipo-jogo 0) (eql jogador -1))
(progn
(format t "Escolher valor duplo a apagar:~%")
(let* (
(coor (escolher-coordenadas (mapcar #'(lambda (casa) (posicao-casa tabuleiro casa)) duplos-atuais)))
)
(celula (car coor) (second coor) tabuleiro)
)
)
)
(t
(random (length duplos-atuais))
)
)
)
(posicao-peca (posicao-casa tabuleiro (nth escolha duplos-atuais)))
)
(substituir (car posicao-peca) (second posicao-peca) tabuleiro)
)
)
)
)
)O sistema utiliza o algoritmo Alfa-Beta para a tomada de decisões dos jogadores computadorizados. O Algoritmo Alfa-Beta é uma variação do algoritmo Minimax, usado em jogos de decisão de múltiplas rodadas, como o Jogo do Cavalo. Ele permite uma análise eficiente das possíveis jogadas, reduzindo a quantidade de nós avaliados na árvore de busca.
Este algoritmo é fundamental para o desempenho e a competitividade dos jogadores computadorizados, permitindo que eles explorem profundamente as possíveis jogadas em um tempo razoável.
;; alfabeta
(defun alfabeta (no p-max alfa beta e-max tempo-limite tempo-inicial &optional (tempo-atual 0) (num-nos-eval 0) (cortes-max 0) (cortes-min 0))
"Recebe o no, profundidade maxima, o alfa e o beta, retorno o no com a melhor avaliação"
(cond
((or (eql p-max 0) (>= (- tempo-atual tempo-inicial) (- tempo-limite 100000))) (list no num-nos-eval cortes-max cortes-min))
(t
(let* (
(max-eval -999999)
(min-eval 999999)
(nos-sucessores (sucessores no))
(no-eval (list (car nos-sucessores) num-nos-eval cortes-max cortes-min))
)
(cond
((null (car no-eval)) (list no (+ (length nos-sucessores) num-nos-eval) cortes-max cortes-min))
(e-max
(evaluar-sucessores-max nos-sucessores p-max max-eval no-eval alfa beta tempo-limite tempo-inicial(+ (length nos-sucessores) num-nos-eval) cortes-max cortes-min)
)
(t
(evaluar-sucessores-min nos-sucessores p-max min-eval no-eval alfa beta tempo-limite tempo-inicial (+ (length nos-sucessores) num-nos-eval) cortes-max cortes-min)
)
)
)
)
)
);; avaliar-sucessores-max
(defun avaliar-sucessores-max (nos p-max max-eval no-max-eval alfa beta tempo-limite tempo-inicial &optional (num-nos-eval 0) (cortes-max 0) (cortes-min 0))
"Recebe os nos, profundidade maxima, o minimo valor, o no do minimo valor, o alfa e o beta, retorna o no avalidado"
(cond
((null nos) (list (car no-max-eval) num-nos-eval cortes-max cortes-min))
(t
(let* (
(eval (alfabeta (car nos) (1- p-max) alfa beta NIL tempo-limite tempo-inicial (get-internal-real-time) num-nos-eval cortes-max cortes-min))
(novo-max-eval (max max-eval (no-valor (car eval))))
(novo-no (cond ((> (no-valor (car eval)) max-eval) eval) (t no-max-eval)))
(novo-alfa (max alfa (no-valor (car eval))))
)
(cond
((<= beta alfa) (list (car novo-no) num-nos-eval (1+ cortes-max) (1+ cortes-min)))
(t (avaliar-sucessores-max (cdr nos) p-max novo-max-eval novo-no novo-alfa beta tempo-limite tempo-inicial num-nos-eval cortes-max cortes-min))
)
)
)
)
);; evaluar-sucessores-min
(defun evaluar-sucessores-min (nos p-max min-eval no-min-eval alfa beta tempo-limite tempo-inicial &optional (num-nos-eval 0) (cortes-max 0) (cortes-min 0))
"Recebe os nos, profundidade minima, o minimo valor, o no do minimo valor, o alfa e o beta, retorna o no avalidado"
(cond
((null nos) (list (car no-min-eval) num-nos-eval cortes-max cortes-min))
(t
(let* (
(eval (alfabeta (car nos) (1- p-max) alfa beta T tempo-limite tempo-inicial (get-internal-real-time) num-nos-eval cortes-max cortes-min))
(novo-min-eval (max min-eval (no-valor (car eval))))
(novo-no (cond ((< (no-valor (car eval)) min-eval) eval) (t no-min-eval)))
(novo-beta (max beta (no-valor (car eval))))
)
(cond
((<= beta alfa) (list (car novo-no) num-nos-eval (1+ cortes-max) (1+ cortes-min)))
(t (evaluar-sucessores-min (cdr nos) p-max novo-min-eval novo-no alfa tempo-limite tempo-inicial novo-beta num-nos-eval cortes-max cortes-min))
)
)
)
)
)Foram implementadas diversas funções para a criação, alteração e retorna das deversas carateristicas de um no, como são seguintes:
;; criar-no
(defun criar-no (pontos-j1 pontos-j2 tabuleiro &optional (g 0) (pai NIL) &aux (v (+ (* 3 g) (* 5 (- pontos-j1 pontos-j2)) (* 2 (obter-numero-casa-tabuleiro tabuleiro)))))
"Recebe o tabuleiro e opcionalmente o acumulador de pontos, heuristica e o no pai, retorna um novo no"
(list (list pontos-j1 pontos-j2 tabuleiro) g v pai)
)
;;; Metodos seletores
;; no-estado
(defun no-estado (no)
"Recebe o no, retorna o estado"
(car no)
)
;; no-pontos-acumulados-j1
(defun no-pontos-acumulados-j1 (no)
"Recebe o no, retorna os pontos acumulados do jogador 1"
(first (car no))
)
;; no-pontos-acumulados-j2
(defun no-pontos-acumulados-j2 (no)
"Recebe o no, retorna os pontos acumulados do jogador 1"
(second (car no))
)
;; no-tabuleiro
(defun no-tabuleiro (no)
"Recebe o no e retorna o tabuleiro"
(third (car no))
)
;; no-profundidade
(defun no-profundidade (no)
"Recebe o no, retorna a profundidade"
(second no)
)
;; no-valor
(defun no-valor (no)
"Recebe o no, retorna o valor"
(third no)
)
;; no-pai
(defun no-pai (no)
"Recebe o no, retorna no pai"
(fourth no)
)
Operadores
Os operadores foram abordados anteriormente neste documento e eles são encarregados de ditar as ações do cavalo neste jogo.
No total temos 8 operadores para os 8 posiveis movimentos do cavalo, as funções para representar cada operador são as seguintes:
;; operadores
(defun operadores ()
"Retorna predicados referente aos operadores"
(list 'operador-1 'operador-2 'operador-3 'operador-4 'operador-5 'operador-6 'operador-7 'operador-8)
)
;; operador-1
(defun operador-1 (posicao)
"Recebe a posicao retorna a coordenada"
(list (+ (car posicao) 2) (- (second posicao) 1))
)
;; operador-2
(defun operador-2 (posicao)
"Recebe a posicao retorna a coordenada"
(list (+ (car posicao) 2) (+ (second posicao) 1))
)
;; operador-3
(defun operador-3 (posicao)
"Recebe a posicao retorna a coordenada"
(list (+ (car posicao) 1) (+ (second posicao) 2))
)
;; operador-4
(defun operador-4 (posicao)
"Recebe a posicao retorna a coordenada"
(list (- (car posicao) 1) (+ (second posicao) 2))
)
;; operador-5
(defun operador-5 (posicao)
"Recebe a posicao retorna a coordenada"
(list (- (car posicao) 2) (+ (second posicao) 1))
)
;; operador-6
(defun operador-6 (posicao)
"Recebe a posicao retorna a coordenada"
(list (- (car posicao) 2) (- (second posicao) 1))
)
;; operador-7
(defun operador-7 (posicao)
"Recebe a posicao retorna a coordenada"
(list (- (car posicao) 1) (- (second posicao) 2))
)
;; operador-8
(defun operador-8 (posicao)
"Recebe a posicao retorna a coordenada"
(list (+ (car posicao) 1) (- (second posicao) 2))
)Sucessores
Os sucessores definem os nós resultantes de cada nó explorado no algoritmo. E a criação do sucessores tem a seguinte estrutura:
;; sucessores
(defun sucessores (no)
"Recebe o no e retorna os nos sucessores ao no, NIL caso não existir sucessores"
(let* (
(tabuleiro (no-tabuleiro no))
(pontos-j1 (no-pontos-acumulados-j1 no))
(pontos-j2 (no-pontos-acumulados-j1 no))
(coordenada-j1 (posicao-casa tabuleiro -1))
(coordenada-j2 (posicao-casa tabuleiro -2))
(coordenadas-j1 (obter-coordenadas-de-jogo -1 tabuleiro))
)
(cond
((null coordenadas-j1)
(let* ((coordenadas-j2 (obter-coordenadas-de-jogo -2 tabuleiro)))
(cond
((null coordenadas-j2) (list NIL))
(t (mapcar #'(lambda (coor2)
(let* (
(estado (simular-jogada 1 -2 coordenada-j2 coor2 pontos-j2 tabuleiro))
)
(novo-sucessor no pontos-j1 (car estado) (third estado))
)
) (obter-coordenadas-de-jogo -2 tabuleiro))
)
)
)
)
(t
(let* ((estados-1 (mapcar #'(lambda (coor1) (simular-jogada 1 -1 coordenada-j1 coor1 pontos-j1 tabuleiro)) coordenadas-j1)))
(apply #'append (mapcar #'(lambda (estado-1-atual)
(let* ((coordenadas-j2 (obter-coordenadas-de-jogo -2 (third estado-1-atual))))
(cond
((null coordenadas-j2)
(list (novo-sucessor no (car estado-1-atual) pontos-j2 (third estado-1-atual)))
)
(t
(let* ((estados-2 (mapcar #'(lambda (coor2) (simular-jogada 1 -2 coordenada-j2 coor2 pontos-j2 (third estado-1-atual))) coordenadas-j2)))
(mapcar #'(lambda (estado-2-atual)
(novo-sucessor no (car estado-1-atual) (car estado-2-atual) (third estado-2-atual))
) estados-2)
)
)
)
)
) estados-1))
)
)
)
)
)
;; novo-sucessor
(defun novo-sucessor (no pontos-j1 pontos-j2 tabuleiro)
"Recebe o no, os pontos-j1, os pontos-j2 e o tabuleiro, retorna o no sucessor, NIL caso no existir o no sucessor"
(criar-no pontos-j1 pontos-j2 tabuleiro (1+ (no-profundidade no)) no)
)Heurística
A heurística se obtem através da soma Ponderada que atribui pesos a cada um dos fatores (profundidade, diferença de pontos, valor das casas restantes) e soma seus valores multiplicados pelos pesos correspondentes. Por exemplo:
Heurística = (Peso_Profundidade * Profundidade) + (Peso_Diferença_Pontos * Diferença de Pontos) + (Peso_Valor_Casas * Valor das Casas Restantes)
- implementação
(v (+ (* 3 g) (* 5 (- pontos-j1 pontos-j2)) (* 2 (obter-numero-casa-tabuleiro tabuleiro))))(
(51 3 5 59 80 71 69 42 21 78)
(29 56 6 9 75 92 8 33 30 16)
(36 24 88 74 99 90 37 62 40 67)
(34 28 85 73 19 43 79 54 45 31)
(52 83 60 20 25 32 39 10 14 53)
(27 64 89 86 7 72 57 66 23 2 )
(98 97 0 41 46 12 11 87 77 38)
(76 68 18 13 93 58 17 44 4 50)
(91 15 48 49 61 84 82 94 26 47)
(55 81 63 35 1 65 70 95 22 96)
)- 5000 milisegundo
| Nos gerados | Cortes max | Cortes min | Tempo |
|---|---|---|---|
| 30790 | 780 | 2724 | 4.2667s |
| 16293 | 651 | 1394 | 1.9442s |
| 26475 | 882 | 2425 | 4.9506s |
| 34765 | 1802 | 3696 | 4.0687s |
| 23340 | 734 | 2529 | 4.2627s |
| 13170 | 539 | 1493 | 1.6791s |
| 7845 | 383 | 1134 | 1.4732s |
| 6277 | 286 | 838 | 0.8317s |
| 2124 | 145 | 298 | 0.3681s |
| 2065 | 116 | 232 | 0.2988s |
| 1213 | 67 | 149 | 0.1809s |
| 146 | 11 | 18 | 0.0339s |
| 5 | 0 | 0 | 0.0012s |
(
(51 3 5 59 80 71 69 42 21 78)
(29 56 6 9 75 92 8 33 30 16)
(36 24 88 74 99 90 37 62 40 67)
(34 28 85 73 19 43 79 54 45 31)
(52 83 60 20 25 32 39 10 14 53)
(27 64 89 86 7 72 57 66 23 2 )
(98 97 0 41 46 12 11 87 77 38)
(76 68 18 13 93 58 17 44 4 50)
(91 15 48 49 61 84 82 94 26 47)
(55 81 63 35 1 65 70 95 22 96)
)- 5000 milisegundo
| Nos gerados | Cortes max | Cortes min | Tempo |
|---|---|---|---|
| 34049 | 1390 | 3517 | 4.9504s |
| 42121 | 1549 | 4009 | 4.9501s |
| 10549 | 409 | 1019 | 1.4340s |
| 18782 | 755 | 1853 | 3.3047s |
| 23264 | 956 | 2151 | 4.9502s |
| 17393 | 867 | 1466 | 2.7020s |
| 30759 | 1236 | 2851 | 3.7869s |
| 2929 | 89 | 375 | 0.4784s |
| 12 | 0 | 0 | 0.0007s |
| 14 | 0 | 0 | 0.0011s |
| 10 | 0 | 0 | 0.0006s |
| 10 | 0 | 0 | 0.0009s |
| 4 | 0 | 0 | 0.0003s |
| 10 | 0 | 0 | 0.0006s |
| 2 | 0 | 0 | 0.0002s |
| 4 | 0 | 0 | 0.0003s |
| 6 | 0 | 0 | 0.0004s |
| 8 | 0 | 0 | 0.0005s |
| 6 | 0 | 0 | 0.0004s |
| 4 | 0 | 0 | 0.0003s |
| 4 | 0 | 0 | 0.0005s |
Algumas limitações técnicas do sistema incluem:
- Restrições de tempo de processamento para determinadas configurações de jogo.
- Limitações na capacidade de avaliação de jogadas para jogadores computadorizados.
Para futuras versões do jogo, algumas ideias de desenvolvimento incluem:
- Implementação de algoritmos mais sofisticados de inteligência artificial.
- Adição de uma interface gráfica de usuário para melhorar a experiência do jogador.
Ao longo deste Manual Técnico, exploramos detalhadamente a implementação do sistema de Inteligência Artificial para o jogo do Cavalo. Utilizamos uma abordagem baseada no algoritmo Alfa-Beta, combinado com heurísticas que consideram a profundidade da busca, a diferença de pontos entre os jogadores e o valor das casas restantes no tabuleiro.
Além disso, apresentamos dois de modos de jogo, incluindo a opção de jogador contra computador e computador contra computador, oferecendo aos usuários diferentes experiências.
No entanto, durante o desenvolvimento do projeto, enfrentamos desafios significativos, como a implementação do algoritmo Alfa-Beta em cenários complexos, a seleção adequada de heurísticas para balancear a eficiência computacional e a precisão da busca.
Apesar dos desafios, o processo de desenvolvimento deste jogo proporcionou uma oportunidade valiosa para a aplicação dos conceitos teóricos aprendidos em sala de aula em um contexto prático e desafiador.