NazaWiki: GameAI: Inteligência Artificial Para Jogos (2007.1)

GameAI: Inteligência Artificial Para Jogos (2007.1)

Aluno: Daniel Amaral de Medeiros Rocha

Primeira lista de exercícios (PROLOG)

Exercício 1

escritor([machado,de,assis]).
escritor([shakeaspeare]).
escritor([michael,chrichton]).

tipo([dom,casmurro],romance).
tipo([quincas,borba],romance).

tipo([hamlet],teatro).
tipo([otelo],teatro).

escritoPor([dom,casmurro],[machado,de,assis]).
escritoPor([quincas,borba],[machado,de,assis]).

escritoPor([hamlet],[shakeaspeare]).
escritoPor([otelo],[shakeaspeare]).

escritoPor([jurassic,park],[michael,chrichton]).
escritoPor([sphere],[michael,chrichton]).

publicadoEm([dom,casmurro],1900).
publicadoEm([quincas,borba],1891).

publicadoEm([hamlet],1600).
publicadoEm([otelo],1610).

publicadoEm([jurassic,park],1993).
publicadoEm([sphere],1998).

ficcao(X) :- tipo(X,romance);tipo(X,teatro).
romancista(X) :- escritoPor(Y,X),tipo(Y,romance).
autorModerno(X) :- escritoPor(Y,X),publicadoEm(Y,Z),Z > 1900.

Exercício 2

edge(alcapao,buraco).
edge(buraco,alcapao).

edge(alcapao,caverna).
edge(caverna,alcapao).

edge(caverna,rio).
edge(rio,caverna).

edge(buraco,rio).
edge(rio,buraco).

edge(rio,estabulo).
edge(estabulo,rio).

edge(tunel,lareira).
edge(lareira,tunel).

connected(N1,N2) :- edge(N1,N2); connected(N1,NX),connected(NX,N2).

Exercício 3

prefixo([],_) :- true.
prefixo([P|X],[P|Y]) :- prefixo(X,Y).

sufixo(S,S) :- true.
sufixo(S,[_|P]) :- sufixo(S,P).

Segunda lista de exercícios (Lógica de 1a ordem)

Exercício 1

a: Artur
b: Bernardo
c: Carlos
h: Heitor

in(X) -> X é inocente
amigo(X,Y) -> X é amigo de Y
gosta(X,Y) -> X gosta de Y
cidade(X) -> X estava na cidade no dia do crime
conhece(X,Y) -> X conhece Y
estava(X,Y) -> X estava com Y na hora do crime

Depoimentos dos suspeitos:
$in(a) \rightarrow amigo(b,h) \wedge \sim gosta(c,h)$
$in(b) \rightarrow \sim cidade(b) \wedge \sim conhece(b,h)$
$in(c) \rightarrow estava(a,h) \wedge estava(b,h)$

Quem estiver com Heitor no dia do crime, estava na cidade:
$estava(X,h) \rightarrow cidade(X)$

Quem é amigo, conhece:
$amigo(X,Y) \rightarrow conhece(X,Y)$

Quem gosta, conhece:
$gosta(X,Y) \rightarrow conhece(X,Y)$

Somente um culpado:
$(in(a) \vee in(b)) \wedge (in(b) \vee in(c)) \wedge (in(a) \vee in(c))$

Queremos descobrir:
$\exists x \sim in(x)$

Para isso, usamos Skolen e adicionamos uma cláusula resp(x):
$in(X) \wedge resp(X)$

Vamos agora eliminar todos os implica, transformar todas as fórmulas para a forma normal conjuntiva e eliminar as conjunções. Ficamos com o seguinte conjunto:
01. $\sim in(a) \vee amigo(b,h)$
02. $\sim in(a) \vee \sim gosta(c,h)$
03. $\sim in(b) \vee \sim cidade(b)$
04. $\sim in(b) \vee \sim conhece(b,h)$
05. $\sim in(c) \vee estava(a,h)$
06. $\sim in(c) \vee estava(b,h)$
07. $\sim estava(X,h) \vee cidade(X)$
08. $\sim amigo(X,Y) \vee conhece(X,Y)$
09. $\sim gosta(X,Y) \vee conhece(X,Y)$
10. $in(a) \vee in(b)$
11. $in(b) \vee in(c)$
12. $in(a) \vee in(c)$
13. $in(X) \vee resp(X)$

O processo de resolução é, então:

(clausulas usadas): nova cláusula
(13,03): 14. $\sim cidade(b) \vee resp(b)$
(13,04): 15. $\sim conhece(b,h) \vee resp(b)$
(14,07): 16. $\sim estava(b,h) \vee resp(b)$
(15,08): 17. $\sim amigo(b,h) \vee resp(b)$
(16,06): 18. $\sim in(c) \vee resp(b)$
(17,01): 19. $\sim in(a) \vee resp(b)$
(19,11): 20. $in(c) \vee resp(b)$
(20,18): 21. $resp(b)$

Logo, concluímos que o assassino de Heitor é Bernardo.

Exercício 2

Vamos usar os seguintes predicados:
$barbeiro(X)$ - indica que $X$ é um barbeiro.
$barbeia(X,Y)$ - indica que $X$ barbeia $Y$ .

Do enunciado do problema, derivamos as seguintes expressões:
1. $\forall X,Y barbeiro(X) \rightarrow barbeia(X,Y) \vee barbeia(Y,Y)$
2. $\forall X,Y \sim(barbeiro(X) \wedge barbeia(X,Y) \wedge barbeia(Y,Y))$

Vamos obter as cláusulas a partir das expressões acima:
01. $\sim barbeiro(X) \vee barbeia(X,Y) \vee barbeia(Y,Y)$
02. $\sim barbeiro(X) \vee \sim barbeia(X,Y) \vee \sim barbeia(Y,Y)$

Vamos tentar então provar a negação:
$\sim(\sim \exists X barbeiro(X)) \equiv \exists X barbeiro(X)$

Eliminando o $\exists$ , usando Skolen:
03. $barbeiro(b)$

Resolvendo, então:

(01,03): 04. $barbeia(b,Y) \vee barbeia(Y,Y)$
(02,03): 05. $\sim barbeia(b,Y) \vee \sim barbeia(Y,Y)$
(02,04): 06. $\sim barbeia(X,b) \vee \sim barbeiro(X) \vee \sim barbeia(b,b)$
(06,01) - fatoração + merging: 07. $\sim barbeiro(X) \vee barbeia(b,b)$
(07,03): 08. $barbeia(b,b)$
(08,05): 09. $\sim barbeia(b,b)$
(08,09): 10. $\Box$