relatorio/final.tex

   1 % colocar referencias http://www.inf.ufrgs.br/~zirbes/EngSoftwareN.htm
   2 %       http://pt.wikipedia.org/wiki/PVC
   3 % colocar sumario
   4
   5 \documentclass[a4paper,10pt]{abnt} %
   6 \usepackage[utf8x]{inputenc}
   7 \usepackage[brazil]{babel}
   8 \usepackage{graphicx}
   9 \usepackage{listings}
  10 \usepackage[usenames,dvipsnames]{color}
  11 \usepackage{verbatim, amssymb, latexsym, amsmath, mathrsfs}
  12 \usepackage{url}
  13 \usepackage{subfigure}
  14 \usepackage{multicol}
  15 \usepackage{framed}
  16 \usepackage{array}
  17 \usepackage{float}
  18 \usepackage[section] {placeins}
  19 \usepackage[table]{xcolor}
  20
  21 %opening
  22 %\title{}
  23 %\author{Kauê Silveira \\171671 \and Silveira Kauê \\ 671171}
  24
  25 \autor{Bruno Coswig Fiss \\ Kauê Soares da Silveira} %\and
  26 \instituicao{Universidade Federal do Rio Grande do Sul}
  27 \orientador[Professor:]{Paulo Martins Engel}
  28 \titulo{Trabalho Prático}
  29 \comentario{Disciplina INF01048 - Inteligência Artificial}
  30 \data{1 de julho de 2010}
  31
  32 \begin{document}
  33
  34 %\maketitle
  35 \folhaderosto
  36 \sumario
  37 \listadetabelas
  38 \listadefiguras
  39
  40 %\begin{abstract}
  41 %\begin{resumo}
  42 %\end{abstract}
  43 %\end{resumo}
  44
  45 \chapter{Introdução}
  46
  47 O trabalho trata-se de desenvolver uma Inteligência Artificial para o jogo Lines of Action.
  48
  49
  50 \chapter{Características Gerais do Programa}
  51
  52 \section{Tecnologias}
  53 \begin{itemize}
  54         \item C++
  55         \item OpenGL, GLU, GLUT, GLUI
  56         \item Linux
  57         \item Vim, Make
  58 \end{itemize}
  59
  60 O programa foi escrito na linguagem C++, que alia eficiência e acesso aos recursos de baixo nível da máquina com orientação a objetos e suporte à abstração.
  61
  62 A interface gráfica utiliza-se da biblioteca GLUI (\cite{glui}), a qual está no topo de uma cadeia de bibliotecas (OpenGL, GLU, GLUT, GLUI) em cuja base se encontra OpenGL, sendo que todas são livres e portáveis.
  63
  64 O desenvolvimento ocorreu no sistema operacional Linux, utilizando ferramentas como Vim e Make. Como a portabilidade foi um dos enfoques, ao final também foi gerada, sem grandes dificuldades, uma versão para Windows.
  65
  66 \section{Estruturas de Dados}
  67 \begin{itemize}
  68         \item Bitvector
  69 \end{itemize}
  70
  71 Foi utilizada a classe bitvector da biblioteca padrão da linguagem (\cite{stl}). As peças são representadas em um vetor de 64 posições contendo o valor 1 nas casas ocupadas e 0 nas casas vazias. O tabuleiro é composto por dois destes vetores, um para cada jogador.
  72
  73 Para determinar casas ocupadas, independente da cor, utilizamos um terceirovetor que é o resultado do ou lógico, efetuado bit a bit, dos outros dois.
  74
  75 Para determinar os movimentos válidos, utilizamos vetores pré-computados com a quantidade de peças em cada linha, em cada coluna, em cada diagonal principal e em cada diagonal secundária.
  76
  77 Para detectar que todas as peças de um jogador estão adjacentes é utilizado um algoritmo recursivo, semelhante ao floodfill, que também utiliza um bitvetor, desta vez para marcar quais casas já foram visitadas.
  78
  79 O tabuleiro também armazena uma cache dos valores da heurística (ver seção \ref{heuristica}).
  80
  81 \section{Algoritmo}
  82 \begin{itemize}
  83  \item Negamax
  84  \item Poda alphabeta
  85  \item Best choice first
  86  \item Cache dos valores das heurísticas
  87 \end{itemize}
  88
  89 Utilizamos o algoritmo negamax \cite{negamax}, em que cada jogador objetiva maximizar o simétrico da resposta ótima do adversário. Acrescentamos a poda alpha beta \cite{alphabeta}, na qual variações que comprovadamente não levarão a um valor melhor de heurística não são avaliadas.
  90
  91 A cada iteração, o valor da heurística é calculado em todos os sucessores do nó atual e estes são ordenados por este valor, de forma que expandimos primeiro os nós que têm mais chance de se mostrarem melhores e causarem uma poda na árvore.
  92
  93 Também foi implementada uma cache dos de heurística (detalhados na seção \ref{heuristica}), de tal forma que apenas os valores do jogador que acabou de jogar são recalculados, sendo os valores referentes ao outro jogador aproveitados da iteração anterior.
  94
  95 \subsection{Heurística}
  96 \label{heuristica}
  97 \begin{itemize}
  98         \item Fator Aleatório
  99         \item Distância para o centro
 100         \item Concentração
 101         \item Centralização
 102         \item Centro de Massa
 103         \item Quadrados
 104         \item Conectividade
 105         \item Uniformidade
 106 \end{itemize}
 107
 108 Foram implementadas 7 funções heurísticas, inspiradas em \cite{tese}. Cada uma delas calcula o valor correspondente a cada um dos jogadores e retorna a diferença entre estes valores. Algumas utilizam o valor do centro de massa, calculado como:
 109
 110 $$ \frac{|P(p)|}{\sum_{(i, j) \in P(p)}(i, j)} $$
 111
 112 \subsubsection{Distância para o centro}
 113         É o inverso da média das distâncias euclidianas das peças para o centro. Objetiva recompensar configurações em que temos várias peças no centro, pois é necessário passar pelo centro para reunir as peças, e se for possível reuní-las no centro é melhor ainda.
 114
 115
 116 \subsubsection{Concentração}
 117         É o inverso da média das distâncias de manhatan das peças para o centro de massa. O centro de massa representa um bom ponto para tentar concentrar as peças, sendo uma alternativa ao centro absoluto (que é o caso da heurística anterior). Para não privilegiar configurações com menos peças, subtraímos uma constante pré-computada que representa o valor mínimo possível de ser assumido pela heurística dada a quantidade de peças atual (por exemplo, com 3 peças este valor é um, atingido quando uma das peças está sobre o centro de massa e as outras duas estão adjacentes a esta).
 118
 119 \subsubsection{Centralização}
 120         É a média da qualidade das posições das peças, segundo a seguinte tabela de pesos:
 121
 122 \begin{table}[htbp]
 123         \begin{tabular}{cccccccc}
 124                 -80 & -25 & -20 & -20 & -20 & -20 & -25 & -80 \\
 125                 -25 &  10 &  10 &  10 &  10 &  10 &  10 & -25 \\
 126                 -20 &  10 &  25 &  25 &  25 &  25 &  10 & -20 \\
 127                 -20 &  10 &  25 &  50 &  50 &  25 &  10 & -20 \\
 128                 -20 &  10 &  25 &  50 &  50 &  25 &  10 & -20 \\
 129                 -20 &  10 &  25 &  25 &  25 &  25 &  10 & -20 \\
 130                 -25 &  10 &  10 &  10 &  10 &  10 &  10 & -25 \\
 131                 -80 & -25 & -20 & -20 & -20 & -20 & -25 & -80 \\
 132         \end{tabular}
 133         \caption{Tabela de Pesos da Heurística de Centralização}
 134         \label{tab:centralisation}
 135 \end{table}
 136
 137         O objetivo é penalizar peças na borda do tabuleiro (que são facilmente bloqueáveis pelo inimigo e que têm mais chance de estar longe do grupo principal) e recompensar as peças que estão mais perto do centro.
 138
 139 \subsection{Pesos}
 140 \begin{itemize}
 141         \item Algoritmo Genético
 142         \item ...
 143 \end{itemize}
 144
 145 \subsection{Resultados}
 146 \begin{itemize}
 147         \item Profundidade
 148 \end{itemize}
 149
 150 \subsection{Interface}
 151 Figura aqui.
 152
 153 +++++++++++++++++++++++++++
 154 10 5 10 100
 155 +++++++++++++++++++++++++++
 156 13 0.00763 0.38113 0.14900 0.89597 0.14756 0.41463 0.49148 0.01265
 157 +++++++++++++++++++++++++++
 158 +++++++++++++++++++++++++++
 159 15 0.00763 0.38113 0.84633 0.89597 0.14756 0.41463 0.89042 0.00683
 160 +++++++++++++++++++++++++++
 161 +++++++++++++++++++++++++++
 162 11 0.00763 0.38113 0.84633 0.89597 0.14756 0.41463 0.72130 0.08975
 163 +++++++++++++++++++++++++++
 164
 165
 166 +++++++++++++++++++++++++++
 167 10 5 10 100
 168 +++++++++++++++++++++++++++
 169 12 0.00763 0.93755 0.84633 0.89597 0.03325 0.41463 0.88961 0.01265
 170 12 0.00763 0.38113 0.63358 0.89597 0.03325 0.41463 0.78261 0.01670
 171 +++++++++++++++++++++++++++
 172 tirar 0, 4, e 7;
 173
 174 +++++++++++++++++++++++++++
 175 10 5 10 100
 176 +++++++++++++++++++++++++++
 177 12 0.06116 0.67524 0.39141 0.66735 0.41225 0.17395 0.65427 0.72622
 178 +++++++++++++++++++++++++++
 179
 180 +++++++++++++++++++++++++++
 181 10 5 10 100
 182 +++++++++++++++++++++++++++
 183 10 0.25056 0.87480 0.07819 0.66735 0.50723 0.41734 0.32783 0.16855
 184 +++++++++++++++++++++++++++
 185
 186 tirar 2
 187 +++++++++++++++++++++++++++
 188 10 5 10 100
 189 +++++++++++++++++++++++++++
 190 15 0.27201 0.82723 0.25686 0.97915 0.04472 0.96032 0.96950 0.72310
 191 +++++++++++++++++++++++++++
 192
 193 \end{document}