Relatório Final Inteligência Artificial 3º ano do Mestrado Integrado
Contents
1. Listing 1 O primeiro ciclo for da fun o Facilmente se mostra que este c digo tem uma complexidade O n nx l1 n gt 1 1 1 1 nx 1 2n 2 n x 2n 3 2n 3n gt O n O resto da fun o D ver c digo da listagem p chama a fun o Q para cada elemento do topo do tabuleiro para tentar descobrir caminhos que come em nesse ele mento e consiguem atingir o fundo do tabuleiro for int x 0 x boardToCheck 0 length x if boardToCheck 0 x color if checkLineThroughBoard boardToCheck 0 x color return true Listing 2 O segundo ciclo for da fun o O Observa se que a complexidade deste c digo O n O A fun o Q simplesmente cria uma lista vazia do tipo LinkedList que servir para armazenar as posi es do tabuleiro que a fun o Q ir processar para impedir que a fun o entre em ciclo infinito A fun o Q uma fun o recursiva Como tal teremos de come ar a an lise da sua complexidade pelo seu caso base que pode ser visto na listagem 3 Final do passo recursivo Chegar ao fundo do tabuleiro if y boardToCheck length 1 return true Listing 3 Caso base da fun o Facilmente se v que esta parte do c digo tem uma complexidade O 1 A parte recursiva da fun o envolve a procura de pe as que estejam adjacentes casa que est a ser analisada que tenham a mesma cor e que n o estejam prese2. Faculdade de Engenharia FEUP Hex Relat rio Final Intelig ncia Artificial 3 ano do Mestrado Integrado em Engenharia Inform tica e Computa o Elementos do Grupo Bruno Nova 080509109 ei08109 fe up pt Rolando Pereira 080509150 ei08150 fe up pt 22 de Maio de 2011 Objectivo Este trabalho t m como objectivo criar uma implementa o em Java do jogo Hex Esta implementa o servir como um suporte pr tico para melhorar a aprendiza gem de conceitos apresentados nas aulas te ricas da disciplina nomeadamente as es trat gias de pesquisa considerando advers rios Em especial este trabalho serviu para um estudo do algoritmo Minimax com cortes Alfa Beta Para facilidade de utiliza o do programa foi tamb m desenvolvida duas interfaces para o jogo uma interface em modo de texto e uma interface gr fica utilizando a API Swing do Java Para finalizar foram tamb m adicionadas v rias caracter sticas para melhorar a qualidade do jogo tais como diferentes modos de jogo diferentes modos de dificuldade e diferentes tamanhos de tabuleiro Descri o Funcionalidades O programa desenvolvido neste trabalho cont m v rias funcionalidades tais como a escolha do tamanho do tabuleiro no qual ir ser efectuado o jogo Existem tamb m tr s tipos de jogo dispon veis e Humano contra Humano e Humano contra Computador e Computador contra Computador tamb m poss vel modificar a dificuldade da intelig
3. btsov EMMA a free Java code coverage tool 2005 emma sourceforge net gt 4 The Apache Software Foundation Apache Ant Welcome 2010 ant apache org gt 5 Object Mentor Welcome to JUnit org JUnit org 2011 junit org gt 6 Free Software Foundation Emacs 23 2 1 lt http www gnu org software emacs gt 7 Oracle Corporation Netbeans 7 0 lt nttp netbeans org gt Internet 8 Vadim V Anshelevich A hierarchical approach to computer Hex in Elsevier Science B V 2002 visto a 15 05 2011 lt nttp home earthlink net vanshel VAnshelevich ARTINT pdf gt 9 Basic strategy guide HexWiki 2011 visto a 07 04 2011 lt http www nhexwiki org index php title Basic 28strategy guide 29 The two bridge gt Anexos Manual do utilizador Coloque aqui um manual sucinto de utiliza o do seu programa Exemplo de uma execu o Apresente aqui um exemplo de execu o do programa ilustrado por uma sequ ncia de printscreen s relativos a uma sess o de utiliza o do programa
4. mpilador javac e os ambientes de programa o Emacs 6 e Netbeans 7 Foram usados tamb m alguns pacotes extra de software que permitiram melhorar a qualidade do c digo Estes foram e Sistema de cobertura de c digo Emmal3 e Sistema de compila o de c digo Ant 4 e Sistema de testes unit rios Junit 5 Avalia o do programa Descreva a forma de avalia o do trabalho desenvolvido e os testes realizados Caso tenha feito simula es coloque nesta sec o uma descri o das condi es em que foram feitas as simula es e indique os correspondentes resultados obtidos Conclus es Escreva aqui as conclus es que achar devidas Diga como o programa poderia ser melhorado Que funcionalidades adicionais deveria ter ou que sofistica es gostaria de ver implementadas caso tivesse tempo para tal Como poderia aumentar a efici ncia do programa torn lo mais r pido ou restringir os gastos de mem ria forma de melhorar o programa melhorar a funcao heur stica do algoritmo mini max implementar esta 8 vers o do algoritmo Recursos Indique os recursos usados na realiza o do trabalho bibliografia e software e windows O c digo final tem de ser entregue com Makefile nesse caso tem que se colocar tam b m aqui o Make Refer ncias Software 1 Oracle Oracle Technology Network for Java Developers 2011 lt http www oracle com technetwork java index html gt 2 linux 3 Vlad Rou
5. ncia artificial tendo que conta que o nico par metro diferente entre as v rias dificuldades o n vel de profundidade do algoritmo Minimax que usado Dito isto as tr s dificuldades existentes s o e F cil correspondendo ao algoritmo Minimax com profundidade 2 e M dio correspondendo ao algoritmo Minimax com profundidade 3 e Dif cil correspondendo ao algoritmo Minimax com profundidade 4 Em termos de c digo a vari veis que determinam a profundidade do algoritmo Minimax para cada dificuldade encontram se no ficheiro Computer Al java sendo elas static private final int EASY DEPTH 2 static private final int MEDIUM DEPTH 3 static private final int HARD DEPTH 4 Estrutura do programa O programa desenvolvido encontra se dividido em v rios m dulos estando estes sep arados por ficheiros de c digo Java O m dulos desenvolvidos foram os seguintes e Hex Ponto de entrada do programa Cont m a fun o main do programa HexConsole M dulo da interface de consola e HexGraphical M dulo da interface em m do gr fico Board M dulo do tabuleiro de jogo Cont m o algoritmo para detectar camin hos no mesmo ComputerAI M dulo da intelig ncia artificial melhorar esta As rela es entre estes m dulos podem ser vistos na figura l seccao HexGraphical Computer I Figura 1 Diagrama dos m dulos do programa e as suas rela es Esquemas de Representa o de Conhecimen
6. ntes na lista passedPositions Essa parte recursiva requer o uso de uma fun o auxiliar listContainsBoardPlace uma lista de posi es do tabuleiro list e uma posi o do tabuleiro boardPlace e verifica se boardPlace est contido em list Esta fun o tem uma complexidade O n pois tem de percorrer a lista list apenas uma vez O algoritmo recursivo da fun o Q c digo na listagem 4 simplesmente chama se a si mesma para as casas que se encontram esquerda direita baixo e diagonal baixo esquerda desde que essas casas tenham a mesma cor que a da casa actual Este comportamento pode ser visto na figura 4 lt X 2 A 3 1 Figura 2 As casas que s o visitadas recursivamente pela fun o 9 Os n meros indicam a ordem de visita if boardToCheck y 1 x color int boardPlace y 1 x if listContainsBoardPlace passedPositions boardPlace passedPositions add boardPlace if checkLineThroughBoard boardToCheck boardPlace 0 boardPlace 1 color passedPositions return true if x boardToCheck 0 length 1 amp amp boardToCheck y x 1 color int boardPlace y x 1 if listContainsBoardPlace passedPositions boardPlace passedPositions add boardPlace if checkLineThroughBoard boardToCheck boardPlace 0 boardPlace 1 color passedPositions return true if x 0 amp amp boardToCheck y 1 x 1 col
7. or int boardPlace y 1 x 1 if listContainsBoardPlace passedPositions boardPlace passedPositions add boardPlace if checkLineThroughBoard boardToCheck boardPlace 0 boardPlace 1 color passedPositions return true if x 0 amp amp boardToCheck y x 1 color int boardPlace y x 1 if listContainsBoardPlace passedPositions boardPlace passedPositions add boardPlace if checkLineThroughBoard boardToCheck boardPlace 0 boardPlace 1 color passedPositions return true Listing 4 Parte recursiva do algoritmo Na an lise do algoritmo recursivo considera se que S corresponde ao tamanho do tabuleiro que est a ser analisado e que F corresponde fun o que recebe um tuplo n m em que n corresponde a uma posi o y do tabuleiro e m corresponde a uma posi o x do tabuleiro F recebe tamb m um conjunto que cont m os tuplos n m que j foram visitados F S Lm 1 F n m l F n 1 m l F n m 1 F n Il m 1 l n 1 m 1 l F n m 1 1 n m 1 l F n 0 l F n 1 m l F n m 1 1 F n S 1 F n 1 5 1 1 F n 1 S 2 1 F n S 2 1 sse n 1 m l sse n m 1 l sse sse Ambiente de desenvolvimento Este trabalho foi realizado na linguagem de programa o Javal tendo o c digo sido desenvolvido e testado em m quinas correndo o sistema operativo Linux 2 usando o co
8. to Descreva os esquemas de Representa o de Conhecimento que utilizou no trabalho Tente sempre que poss vel indicar as vantagens da representa o que escolheu em rela o a representa es alternativas que poderiam ter sido usadas Refira nesta sub sec o detalhes relevantes da implementa o An lise da complexidade dos algoritmos usados Fa a aqui uma an lise da complexidade dos algoritmos que usou no trabalho Board checkLineThroughBoard Devido ao polimorfismo da linguagem Java existem tr s fun es com o nome check LineThroughBoard na class Board Para ser poss vel diferenciar entre elas cada fun o ser numerada 1 checkLineThroughBoard int boardToCheck int color 2 checkLineThroughBoard int boardToCheck int y int x int color 3 checkLineThroughBoard int boardToCheck int y int x int color List lt int gt passedPositions A fun o encontra se dividida em duas partes O primeiro ciclo for mostrado na listagem 1 serve para verificar em existe pelo menos uma pe a da cor pedida em cada linha do tabuleiro Caso isso n o ocorra n o pode haver um caminho que v do topo do tabuleiro at ao fundo do mesmo mudar Listing List for int boardLine boardToCheck ERR boolean existsColoredPiece false for int boardPlace boardLine if boardPlace color existsColoredPiece true if existsColoredPiece return false
Download Pdf Manuals
Related Search