documentacion.lyx

#LyX 1.6.4 created this file. For more info see http://www.lyx.org/
\lyxformat 345
\begin_document
\begin_header
\textclass article
\begin_preamble
\date{}
\end_preamble
\use_default_options true
\language spanish
\inputencoding auto
\font_roman default
\font_sans default
\font_typewriter default
\font_default_family default
\font_sc false
\font_osf false
\font_sf_scale 100
\font_tt_scale 100

\graphics default
\float_placement H
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry true
\use_amsmath 1
\use_esint 1
\cite_engine basic
\use_bibtopic false
\paperorientation portrait
\topmargin 3cm
\bottommargin 3cm
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\defskip medskip
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\author "" 
\author "" 
\end_header

\begin_body

\begin_layout Title
Análisis y diseño del algoritmos II 
\begin_inset Newline newline
\end_inset

Trabajo práctico especial
\end_layout

\begin_layout Author
Lucas Moauro y Maximiliano Matos
\end_layout

\begin_layout Standard
\begin_inset Newpage pagebreak
\end_inset


\end_layout

\begin_layout Standard
\begin_inset CommandInset toc
LatexCommand tableofcontents

\end_inset


\end_layout

\begin_layout Section
Introducción
\end_layout

\begin_layout Standard
En este informe se detalla sobre la implementación y análisis de funciones
 heurísticas para la generación de soluciones subóptimas para un clon del
 juego 
\emph on
Pacman
\emph default
.
\end_layout

\begin_layout Standard
Los algoritmos 
\emph on
heurísticos 
\emph default
surgen de la necesidad de resolver problemas de complejidad alta(en algunos
 casos indecidibles) para lograr acotar el tiempo de obtención de resultados.
 En general, los resultados generados no son óptimos; éstos dependen directament
e de la calidad de la heurística.
 Las funciones heurísticas se valen de estimaciones con respecto a su entrada
 para producir un resultado que se aproxime al valor óptimo.
 Se diferencian de los algoritmos 
\emph on
aproximados 
\emph default
por el hecho de no saber con que precisión se acerca la solución generada
 a la mejor.
\end_layout

\begin_layout Standard
En este trabajo, las funciones heurísticas son utilizadas para estimar el
 costo para que el 
\emph on
pacman 
\emph default
devore los puntos restantes del mapa, a partir de un estado arbitrario.
 Hay diversas variables que pueden considerarse: cantidad de puntos restantes,
 distancia a los fantasmas, distancia a puntos, etc.
 También tiene incidencia en el resultado la importancia que se le de a
 cada variable en una heurística.
\end_layout

\begin_layout Standard
Las funciones 
\emph on
heurísticas estáticas
\begin_inset Foot
status collapsed

\begin_layout Plain Layout

\emph on
Se llama estática a una función heurística que tiene como parámetro sólo
 la configuración de un estado.
 
\end_layout

\end_inset

 
\emph default
implementadas se usan en los algoritmos de búsqueda parcial
\emph on
 minimin 
\emph default
y 
\emph on
RTA* 
\emph default
para acotar el espacio de búsqueda generado, y en consecuencia, el tiempo
 de ejecución.
 Los algoritmos de búsqueda parcial introducen una variable más para analizar
 las heurísticas, la profundidad del árbol de exploración generado en la
 búsqueda.
\end_layout

\begin_layout Standard
La implementación y el análisis de las funciones involucraron los siguientes
 pasos:
\end_layout

\begin_layout Enumerate
A partir de una hipótesis se implementa una función heurística.
 Puede ser que surja a partir de una idea nueva o como una mejora a heurísticas
 anteriores.
\end_layout

\begin_layout Enumerate
Se hace un análisis empírico de la heurística.
\end_layout

\begin_layout Enumerate
Se sacan conclusiones y se justifica el comportamiento del pacman.
\end_layout

\begin_layout Standard
En el análisis empírico se tiene en cuenta:
\end_layout

\begin_layout Itemize
El nivel de profundidad de la búsqueda.
\end_layout

\begin_layout Itemize
El resultado de la ejecución(si ganó o perdió).
\end_layout

\begin_layout Itemize
Cantidad de pasos de la solución.
\end_layout

\begin_layout Itemize
Cantidad de puntos que quedaron sin comer.
\end_layout

\begin_layout Itemize
Espacio de búsqueda total.
\end_layout

\begin_layout Itemize
La precisión de la heurística en la predicción, es decir, la diferencia
 entre el valor real de la solución(determinado por el resultado final de
 la ejecución) y el costo devuelto por la heurística en cada uno de los
 pasos
\begin_inset Foot
status open

\begin_layout Plain Layout
La función de la solución real con respecto la cantidad de pasos siempre
 será lineal decreciente.
\end_layout

\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename Heuristica-ejemplo.gif
	scale 40

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Ejemplo de comparación entre la solución real y el valor devuelto por la
 función heurística
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
A continuación se detalla sobre la implementación y la calidad de cada heurístic
a.
\end_layout

\begin_layout Section
Heurísticas
\end_layout

\begin_layout Subsection
Heurística 1
\end_layout

\begin_layout Subsubsection*
Idea e hipótesis
\end_layout

\begin_layout Standard
Una forma de obtener una cota inferior de la cantidad de pasos faltantes
 para que el pacman gane el juego es considerar la cantidad de puntos sin
 comer en el estado de entrada
\begin_inset Foot
status collapsed

\begin_layout Plain Layout
Ésta es la heurística de ejemplo provista por la cátedra
\end_layout

\end_inset

.
 El problema que surge con ésta estimación simple es que no se considera
 en ningún grado la incidencia de los fantasmas, lo que produce que el pacman
 termine encerrado por ellos en la mayoría de los casos.
 
\end_layout

\begin_layout Standard
\begin_inset Float table
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="4">
<features>
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Nivel
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Resultado
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Pasos
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Puntos restantes
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
12
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Perdió
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
378
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
7
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
15
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Perdió
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
78
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
167
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
17
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Ganó
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
485
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
22
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Perdió
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
238
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
80
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Resultados para la heurística que sólo tiene en cuenta los puntos
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
Esta heurística considera la cantidad de fantasmas cercanos al pacman.
 Se introduce un parámetro denominado 
\emph on
frontera 
\emph default
que determina la cantidad límite de pasos en todas las direcciones a la
 que debe estar un fantasma para que se considere cercano al pacman.
 Mientras más fantasmas se encuentren en la zona fronteriza mayor será el
 costo agregado.
 El objetivo de este costo es evitar que el pacman caiga en situaciones
 en las cuales pueda llegar a ser acorralado.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename frontera.png
	scale 40

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Estado de juego con un fantasma en la frontera
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
Para obtener buenos resultados se debe elegir una frontera
\emph on
 
\emph default
adecuada, ya que si es demasiado grande no tendrá incidencia en el resultado
 y si es muy chica la evaluación heurística agregará un costo sólo cuando
 le queden pocas chances de sobrevivir.
\end_layout

\begin_layout Standard
Además del costo correspondiente a los fantasmas se agrega el costo de la
 cantidad de puntos restantes, que permite que el pacman se acerque a la
 solución.
\end_layout

\begin_layout Standard
Esta función considera el peso de los fantasmas y de los puntos restantes
 en forma independiente, teniendo la consecuencia que en algunos estados
 una variable tendrá más peso que la otra y viceversa.
 Por ejemplo, cuando restan pocos puntos por comer, el peso de los fantasmas
 incide en mayor grado que al comienzo del juego.
 Este comportamiento puede ser indeseado en algunas instancias del juego
 cuando se prueba con niveles de profundidad bajos.
\end_layout

\begin_layout Standard
En esta heurística no se tienen en cuenta el comportamiento de los fantasmas,
 por ejemplo, si los fantasmas estan en modo asustadizo, su dirección con
 respecto al pacman y la identidad de cada fantasma cercano.
 En consecuencia, puede que ciertos estados se evaluen como más hostiles
 para el pacman de lo que realmente son.
\end_layout

\begin_layout Subsubsection*
Implementación
\end_layout

\begin_layout LyX-Code

\size footnotesize
unsigned int h1(const Game * game) 
\end_layout

\begin_layout LyX-Code

\size footnotesize
{     
\end_layout

\begin_deeper
\begin_layout LyX-Code

\size footnotesize
int frontera = 4; //valor de frontera    
\end_layout

\begin_layout LyX-Code

\size footnotesize
const GameSpace & gs = game->getGameSpace();
\end_layout

\begin_layout LyX-Code

\size footnotesize
int w = gs.getWidth(); 
\end_layout

\begin_layout LyX-Code

\size footnotesize
int h = gs.getHeight(); 
\end_layout

\begin_layout LyX-Code

\size footnotesize
const LogicObject * pacman = game->getObject(PACMAN); 
\end_layout

\begin_layout LyX-Code

\size footnotesize
const Shape * shape = pacman->getShape();    
\end_layout

\begin_layout LyX-Code

\size footnotesize
int x = shape->getX();    
\end_layout

\begin_layout LyX-Code

\size footnotesize
int y = shape->getY();    
\end_layout

\begin_layout LyX-Code

\size footnotesize
int hi, hf, wi, wf; //Extremos del rectangulo.
   
\end_layout

\begin_layout LyX-Code

\size footnotesize
hi = max(0, y - frontera);   
\end_layout

\begin_layout LyX-Code

\size footnotesize
hf = min(h - 1, y + frontera);   
\end_layout

\begin_layout LyX-Code

\size footnotesize
wi = max(0, x - frontera);   
\end_layout

\begin_layout LyX-Code

\size footnotesize
wf = min(w - 1, x + frontera);
\end_layout

\begin_layout LyX-Code

\size footnotesize
set<string> ghostSubtype;
\end_layout

\begin_layout LyX-Code

\size footnotesize
ghostSubtype.insert(GHOST);  
\end_layout

\begin_layout LyX-Code

\size footnotesize
list<const LogicObject *> ghosts;   
\end_layout

\begin_layout LyX-Code

\size footnotesize
gs.getObjects(Rectangle(wi,hi,wf-wi,hf-hi), 
\end_layout

\begin_layout LyX-Code

\size footnotesize
              LogicObject::Type(ghostSubtype), ghosts);  
\end_layout

\begin_layout LyX-Code

\size footnotesize
int cant_ghosts = ghosts.size();  
\end_layout

\begin_layout LyX-Code

\size footnotesize
int cant_puntos = game->getVariables().getInteger(DOT_COUNT);
\end_layout

\begin_layout LyX-Code

\size footnotesize
return cant_puntos + frontera*cant_ghosts;
\end_layout

\end_deeper
\begin_layout LyX-Code

\size footnotesize
}
\end_layout

\begin_layout Standard
Se eligió el tamaño de la frontera de considerando que tan cerca tendría
 que estar un fantasma para ser hostil.
 
\end_layout

\begin_layout Standard
Como puede observarse en el código, cuando desde la posición del pacman
 hacia una dirección la extensión de la frontera queda fuera del espacio
 de juego, simplemente se toma el extremo del mapa como extremo del rectángulo
 a extraer.
\end_layout

\begin_layout Standard
El costo asociado al estado es una combinación lineal entre la cantidad
 de puntos del mapa y la cantidad de fantasmas del rectángulo extraído.
 Para dar un mayor peso a los fantasmas se lo multiplica por la frontera,
 esto puede interpretarse como la cantidad de pasos que requiere el pacman
 para escapar de una situación comprometida(a mayor cantidad de fantasmas,
 mayor es el costo).
\end_layout

\begin_layout Subsubsection*
Resultados empíricos e interpretación
\end_layout

\begin_layout Standard
La función se probó en cuatro niveles de profundidad.
 En la elección de los niveles influyeron las dos variables de la heurística.
 En niveles de profundidad bajos el pacman tiene una menor amplitud en cuanto
 al alcance de sus acciones.
 Si en un estado quedan pocos puntos y el pacman está alejado de estos,
 los estados que se deriven con la aplicación del minimin probablemente
 no obtendrán mejoras en el costo con respecto a la variable que considera
 los puntos restantes, porque el pacman no llegará a comer ningún punto.
 También es interesante observar el comportamiento de la componente del
 costo de los fantasmas en niveles bajos, porque se tiene menor capacidad
 para prever situaciones de riesgo.
\end_layout

\begin_layout Standard
Por otra parte, en niveles de profundidad altos, el pacman puede prever
 estados en los que se encuentra en cualquier parte del mapa, lo que permitiría
 que sea posible obtener costos de heurísticas menores con respecto a la
 variable de los puntos.
 En forma similar ocurre con el costo asociado a los fantasmas.
\end_layout

\begin_layout Standard
Se eligieron dos niveles bajos(6 y 10) y dos moderadamente altos(20 y 30).
\end_layout

\begin_layout Standard
\begin_inset Float table
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="5">
<features>
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Nivel
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Resultado
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Pasos
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Puntos restantes
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Estados evaluados
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
6
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Perdió
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
76
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
173
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1345
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
10
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Ganó
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
564
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
22245
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
20
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Ganó
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
481
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
73868
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
30
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Ganó
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
458
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
267781
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Resultados de la heurística 1
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename Heuristica1-30.gif
	scale 40

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Gráfico que muestra la precisión de estimación de la heurística en nivel
 30
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
La tabla 2 muestra que salvo en el nivel 6, los resultados de las soluciones
 fueron consistentes.
 En general, las hipótesis se cumplieron, pero hubo algunos patrones en
 el comportamiento para destacar:
\end_layout

\begin_layout Itemize
Cuando quedan pocos puntos el pacman tiende a hacer movimientos redundantes
 que no mejoran el estado de la solución en forma significativa, esto se
 debe a que el peso de los fantasmas es superior que el de los puntos en
 los estados finales del juego.
 Puede observarse en el gráfico de la figura 3 que al final se sobre estima
 el costo de la solución y a medida que se comen más puntos la función del
 costo va entrando en una meseta.
\end_layout

\begin_layout Itemize
Hay situaciones en las que el pacman deja puntos aislados y se dirige a
 una zona donde hay más puntos.
 Este comportamiento es más marcado cuando se prueba con niveles elevados.
 Interpretamos que ocurre porque la heurística evalúa que es mejor ir directamen
te a comer en la zona donde hay más puntos que volver unos pocos pasos atrás,
 comer los puntos aislados y luego ir a la zona densa, esto pasa porque
 en la heurística no hay ningún costo asociado al de volver a comer los
 puntos aislados.
 En la mayoría de los casos, el dejar puntos aislados hace que la cantidad
 de pasos de la solución sea mayor.
\end_layout

\begin_layout Itemize
En niveles altos el pacman tiende a pasar cerca de los fantasmas con mayor
 frecuencia.
 Como se tiene mayor visión, en una evaluación heurística ganadora(de costo
 mínimo) puede que el pacman pase cerca de los fantasmas en estados intermedios
 porque se sabe que al final no terminará en una posición hostil.
\end_layout

\begin_layout Itemize
La heurística no tiene en cuenta las paredes, lo que lleva que el pacman
 tome desiciones desacertadas.
\end_layout

\begin_layout Itemize
Como se predijo, el pacman no aprovecha posibles ventajas que pueda sacar
 en el modo asustadizo.
\end_layout

\begin_layout Subsection
Heurística 2
\end_layout

\begin_layout Subsubsection*
Idea e hipótesis
\end_layout

\begin_layout Standard
En esta heurística se intenta aproximar el costo de la solución considerando
 la distancia al punto más cercano del pacman en el estado de juego.
 Este costo asociado puede pensarse como la cantidad de pasos que debería
 hacer el pacman para encontrarse con un punto.
 A su vez, la cantidad de puntos restantes se toma como una variable importante
 para que el pacman se acerque a la solución y de esta forma evitar ciertas
 acciones indeseadas que se pueden generar cuando sólo se tiene en cuenta
 la distancia a los puntos.
\end_layout

\begin_layout Standard
Además de la obtención de un costo que tenga una mayor correspondencia al
 costo real en comparación a sólo considerar la cantidad de puntos, esta
 función tiene el propósito derivado de hacer que el pacman logre comer
 los puntos en una forma más eficiente, es decir, que recorra la menor cantidad
 de espacios en blanco(sin puntos) posible.
 La situación ideal(aunque poco factible) sería que el pacman coma los puntos
 en forma continua siempre estando a sólo un movimiento del próximo punto
 a comer.
\end_layout

\begin_layout Standard
A diferencia de la heurística 1, se plantea una relación de dependencia
 entre las variables consideradas por la heurística, es decir, el resultado
 de la función estará compuesto en forma distinta, de acuerdo si se cumple
 o no cierta relación entre la cantidad de puntos y la distancia al punto
 más cercano.
 Esta dependencia surge de la hipótesis de que si el costo fuera un valor
 en donde las variables son independientes, en los estados donde quedan
 pocos puntos la distancia al punto más cercano conformaría la mayor parte
 de este, haciendo que el pacman no coma puntos en situaciones en las que
 comer puntos dejaría al punto más cercano en una posición alejada.
 En la situación anterior el pacman dependería de que los fantasmas lo 
\begin_inset Quotes eld
\end_inset

obliguen
\begin_inset Quotes erd
\end_inset

 a comer los puntos persiguiéndolo.
 Está relación se detallará en la sección de implementación.
\end_layout

\begin_layout Standard
Al no considerar a los fantasmas en el costo, puede que se necesiten niveles
 altos para que logre llegar a una solución.
 Esta omisión debería tener como consecuencia que los resultados no tengan
 la misma consistencia que en la heurística 1, ya que no se tienen elementos(a
 excepción de la exploración del algoritmo de búsqueda) que permitan detectar
 estados hostiles.
 Por esta razón pensamos que el nivel de profundidad tendrá una mayor incidencia
 para la supervivencia del pacman.
 Tampoco se saca ventaja del modo asustadizo.
 
\end_layout

\begin_layout Standard
Una posible ventaja cuando se lo pruebe con niveles de exploración bajos
 y se encuentre alejado de una zona de puntos, es que el costo asociado
 a la distancia lo acercaría a la hacia la zona con puntos.
 En cambio, si sólo se considerara la cantidad de puntos total, el pacman
 no tendría forma acercarse(salvo que sea llevado por los fantasmas hacia
 la zona).
\end_layout

\begin_layout Subsubsection*
Implementación
\end_layout

\begin_layout Standard
Para implementar la heurística se tuvo que ver como medir las distancias
 a los puntos.
 Se consideraron dos formas de medir distancias: la distancia euclídea y
 la de Manhattan.
 Sean 
\begin_inset Formula $\left(x_{1},y_{1}\right)$
\end_inset

 y 
\begin_inset Formula $\left(x_{2},y_{2}\right)$
\end_inset

 las coordenadas de dos objetos, la distancia de Manhattan entre esos dos
 puntos se define como 
\begin_inset Formula $|x_{1}-x_{2}|+|y_{1}-y_{2}|$
\end_inset

, tomamos esta última para la heurística porque en el mapa no hay caminos
 en diagonal, lo que la hace más precisa.
\end_layout

\begin_layout LyX-Code

\size footnotesize
int distancia_manhattan(int x1, int x2, int y1, int y2)
\end_layout

\begin_layout LyX-Code

\size footnotesize
{     
\end_layout

\begin_deeper
\begin_layout LyX-Code

\size footnotesize
return abs(x1-x2) + abs(y1-y2);
\end_layout

\end_deeper
\begin_layout LyX-Code

\size footnotesize
}
\end_layout

\begin_layout Standard
Para obtener la distancia al punto más cercano se implementó una función,
 distancia_punto_mas_cercano, que extrae rectángulos que contienen al pacman
 como centro hasta encontrar un punto en ese área.
 El área del rectángulo a considerar se va duplicando en cada iteración.
 Está función invoca a la función distancia_manhattan para encontrar la
 menor distancia.
\end_layout

\begin_layout LyX-Code

\size footnotesize
int distancia_punto_mas_cercano(const LogicObject * pacman, const GameSpace
 & gs)
\end_layout

\begin_layout LyX-Code

\size footnotesize
{     
\end_layout

\begin_deeper
\begin_layout LyX-Code

\size footnotesize
int x = pacman->getShape()->getX();     
\end_layout

\begin_layout LyX-Code

\size footnotesize
int y = pacman->getShape()->getY();     
\end_layout

\begin_layout LyX-Code

\size footnotesize
int w = gs.getWidth();     
\end_layout

\begin_layout LyX-Code

\size footnotesize
int h = gs.getHeight();
\end_layout

\begin_layout LyX-Code

\size footnotesize
list<const LogicObject *> puntos; 
\end_layout

\begin_layout LyX-Code

\size footnotesize
int min_dist = 1000;     
\end_layout

\begin_layout LyX-Code

\size footnotesize
int frontera = 2;     
\end_layout

\begin_layout LyX-Code

\size footnotesize
bool cubrio_espacio_total = false;     
\end_layout

\begin_layout LyX-Code

\size footnotesize
bool hay_puntos = false;     
\end_layout

\begin_layout LyX-Code

\size footnotesize
do {         
\end_layout

\begin_deeper
\begin_layout LyX-Code

\size footnotesize
int wi = max(0, x - frontera);         
\end_layout

\begin_layout LyX-Code

\size footnotesize
int hi = max(0, y - frontera);         
\end_layout

\begin_layout LyX-Code

\size footnotesize
int wf = min(w, x + frontera);         
\end_layout

\begin_layout LyX-Code

\size footnotesize
int hf = min(h, y + frontera);
\end_layout

\begin_layout LyX-Code

\size footnotesize
gs.getObjects(Rectangle(wi, hi, wf - wi, hf - hi), DOT, puntos);        
 
\end_layout

\begin_layout LyX-Code

\size footnotesize
for (list<const LogicObject *>::const_iterator it = puntos.begin();
\end_layout

\begin_layout LyX-Code

\size footnotesize
     it != puntos.end(); it++) {             
\end_layout

\begin_deeper
\begin_layout LyX-Code

\size footnotesize
const Shape * s = (*it)->getShape();             
\end_layout

\begin_layout LyX-Code

\size footnotesize
min_dist = min(min_dist, distancia_manhattan(x, s->getX(), y, s->getY()));
\end_layout

\end_deeper
\begin_layout LyX-Code

\size footnotesize
}
\end_layout

\begin_layout LyX-Code

\size footnotesize
hay_puntos = puntos.size() > 0;         
\end_layout

\begin_layout LyX-Code

\size footnotesize
cubrio_espacio_total = (x - frontera) <= 0 && (y - frontera) <= 0 &&   
                                        
\end_layout

\begin_layout LyX-Code

\size footnotesize
                       (x + frontera) >= w && (y + frontera) >= h;     
    
\end_layout

\begin_layout LyX-Code

\size footnotesize
frontera *= 2;    
\end_layout

\end_deeper
\begin_layout LyX-Code

\size footnotesize
} while (!hay_puntos && !cubrio_espacio_total);
\end_layout

\begin_layout LyX-Code

\size footnotesize
return min_dist;
\end_layout

\end_deeper
\begin_layout LyX-Code

\size footnotesize
}
\end_layout

\begin_layout Standard
El código de la heurística 2 es:
\end_layout

\begin_layout LyX-Code

\size footnotesize
unsigned int h2(const Game * game) 
\end_layout

\begin_layout LyX-Code

\size footnotesize
{     
\end_layout

\begin_deeper
\begin_layout LyX-Code

\size footnotesize
const LogicObject * pacman = game->getObject(PACMAN);     
\end_layout

\begin_layout LyX-Code

\size footnotesize
const GameSpace & gs = game->getGameSpace();
\end_layout

\begin_layout LyX-Code

\size footnotesize
int cant_puntos = game->getVariables().getInteger(DOT_COUNT); 	
\end_layout

\begin_layout LyX-Code

\size footnotesize
int dist_cercano = distancia_punto_mas_cercano(pacman, gs);
\end_layout

\begin_layout LyX-Code

\size footnotesize
if (cant_puntos <= dist_cercano)         
\end_layout

\begin_deeper
\begin_layout LyX-Code

\size footnotesize
return cant_puntos;     
\end_layout

\end_deeper
\begin_layout LyX-Code

\size footnotesize
return cant_puntos + dist_cercano;
\end_layout

\end_deeper
\begin_layout LyX-Code

\size footnotesize
}
\end_layout

\begin_layout Standard
Aquí puede observarse la relación entre las dos variables que se remarcó
 en la sección anterior.
 El propósito es que cuando quedan pocos puntos(menos que la distancia al
 más cercano) sólo se considera esta cantidad, evitando que el pacman no
 coma los pocos puntos restantes.
\end_layout

\begin_layout Standard
La complejidad de la función heurística se determina considerando la complejidad
 de la función distancia_punto_mas_cercano, que depende del ancho y el largo
 del mapa.
 Calculamos la complejidad para un mapa genérico.
 El peor de los casos ocurre cuando el punto más cercano se encuentra a
 distancia máxima del pacman.
 En este caso se deberá revisar sobre todos los rectángulos incrementalmente,
 hasta que se extrae el mayor rectángulo que abarca todo el mapa.
 Como se debe iterar sobre todo el rectángulo para encontrar el punto más
 cercano y esta es la operación más costosa, la complejidad del algoritmo
 es de 
\begin_inset Formula $O\left(w*h\right)$
\end_inset

, siendo 
\begin_inset Formula $w$
\end_inset

 y 
\begin_inset Formula $h$
\end_inset

 el ancho y el largo del mapa respectivamente.
\end_layout

\begin_layout Subsubsection*
Resultados empíricos e interpretación
\end_layout

\begin_layout Standard
Se probó esta heurística considerando que en niveles bajos el hecho de conocer
 cuando el pacman esta cerca de un punto puede hacer que la deficiencia
 de la poca expansión en el algoritmo de búsqueda no sea tan evidente.
 Aunque en los niveles bajos, se presenta la desventaja de tener poca informació
n sobre la posición de los fantasmas con respecto al pacman.
\end_layout

\begin_layout Standard
En niveles de profundidad elevados, puede que el ajuste mediante la dependencia
 lineal cuando quedan pocos puntos favorezca al pacman, ya que al tener
 una extensión de búsqueda mayor y sólo considerar la cantidad de puntos,
 se puede encontrar una solución eficiente en el último tramo.
\end_layout

\begin_layout Standard
La heurística se probo con cuatro niveles de profundidad.
 Los niveles 10, 20, y 30 se tomaron para comparar los resultados con otras
 heurísticas.
 Se probó en nivel 35 para observar si se obtienen mejoras a partir de las
 observaciones anteriormente mencionadas.
\end_layout

\begin_layout Standard
\begin_inset Float table
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="5">
<features>
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Nivel
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Resultado
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Pasos
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Puntos restantes
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Estados evaluados
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
10
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Perdió
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
323
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
68
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
11188
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
20
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Ganó
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
498
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
74814
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
30
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Ganó
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
567
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
302372
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
35
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Ganó
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
471
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
412414
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Resultados de la heurística 3
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename Heuristica2-35.gif
	scale 40

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Gráfico de precisión de la heurística 2 en nivel 35
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
Viendo los resultados y el comportamiento obtuvimos las siguientes conclusiones:
\end_layout

\begin_layout Itemize
En el nivel de profundidad 10 el pacman es acorralado, esto concuerda con
 la hipótesis para niveles bajos.
 El factor de la distancia hizo que se acercara a puntos a los que no hubiese
 llegado sin considerar este factor, aunque esto no fue muy evidente por
 la muerte prematura.
\end_layout

\begin_layout Itemize
Una situación imprevista en todos los niveles fue que en algunos lugares
 el pacman se queda parado(NoAction) o tiene un comportamiento cíclico(hace
 un movimiento en una dirección y después otro en la dirección opuesta).
 Este comportamiento se debe a que el costo asociado a la distancia del
 punto más cercano luego de comer los puntos de una zona es mayor que el
 beneficio de comer los puntos.
 Debido a esto, cuando el pacman se encuentra en esas posiciones de equilibrio,
 sólo se mueve hacia los puntos cuando comienza a ser perseguido por los
 fantasmas.
 Esto demuestra algunas falencias en la relación establecida entre las variables
, se podría haber utilizado un factor de ajuste para corregir este comportamient
o(posiblemente se modifique en otra heurística).
\end_layout

\begin_layout Itemize
En general, la relación de dependencia entre las variables establecida en
 la implementación funciona bien en los niveles altos, cuando se da que
 las distancias a los puntos más cercanos son mayores a la cantidad de puntos
 total, se comienza a considerar exclusivamente la cantidad de puntos lo
 que lleva a una solución rápida.
\end_layout

\begin_layout Itemize
Como se observa en el gráfico de la figura 4 se mejoró la precisión de la
 estimación de la heurística con respecto a la primera heurística, los picos
 que se ven en el tramo final del gráfico son generados principalmente por
 el costo agregado de la distancia al punto más cercano cuando se terminan
 de comer todos los puntos de una sección.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename varado.png
	scale 40

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
El pacman en prefiriendo conservar distancias
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Heurística 3
\end_layout

\begin_layout Subsubsection*
Idea e hipótesis
\end_layout

\begin_layout Standard
Esta heurística surge a partir de la combinación de las primeras dos heurísticas
 y de la interpretación de los resultados de las heurísticas anteriores
 para mejorar la calidad de la solución.
\end_layout

\begin_layout Standard
Una de las expectativas para la segunda heurística fue que considerando
 la distancia al punto más cercano daría al pacman una mayor visión sobre
 el espacio de juego cuando se lo probara en niveles bajos, el problema
 que surgió fue que al no asociar un costo a los fantasmas el pacman terminó
 acorralado.
 A partir de esto, decidimos incluir en esta heurística un costo que penalice
 los estados en los cuales hay fantasmas en una posición cercana al pacman,
 al igual que en la primera heurística.
 De la misma manera, está función puede considerarse una optimización de
 la primera heurística, ya que al considerar la distancia a los puntos provocarí
a que el pacman llegue a una solución en menos pasos.
\end_layout

\begin_layout Standard
Otro aspecto en el que hicimos hincapié fue la interpretación de los resultados
 anteriores para ajustar los factores asociados a cada variable.
\end_layout

\begin_layout Standard
En la primera heurística, cuando quedaban pocos puntos, el costo asociado
 a estos era menor al de los fantasmas, lo que hacía que el pacman tuviera
 un comportamiento algo redundante.
 En esta heurística se aumenta el factor de la variable de los puntos para
 que en los estados finales este costo siga siendo el más preponderante.
 Esta modificación se hizo a riesgo de que se llegue a una solución en menos
 casos.
\end_layout

\begin_layout Standard
En la segunda heurística, se planteó una relación de dependencia entre la
 cantidad de puntos y la distancia al punto más cercano.
 El principal inconveniente fue que en algunos estados el pacman comienza
 a tener un comportamiento cíclico, porque se le da demasiada importancia
 a la distancia al punto más cercano.
 Como el principal objetivo del costo agregado a la distancia es dar una
 mayor visión en niveles de profundidad bajos y una mayor eficiencia en
 el recorrido, se aplica un factor para que esta variable tenga peso en
 el resultado cuando la distancia es grande, de esta forma este costo 
\begin_inset Quotes eld
\end_inset

guía
\begin_inset Quotes erd
\end_inset

 al pacman hacia los puntos cuando se encuentra a una distancia considerable
 y no interviene cuando está cerca.
 También, el costo correspondiente a los fantasmas debería reducir el comportami
ento cíclico mencionado.
\end_layout

\begin_layout Subsubsection*
Implementación
\end_layout

\begin_layout LyX-Code

\size footnotesize
unsigned int h3(const Game * game)
\end_layout

\begin_layout LyX-Code

\size footnotesize
{     
\end_layout

\begin_deeper
\begin_layout LyX-Code

\size footnotesize
int frontera = 4;     
\end_layout

\begin_layout LyX-Code

\size footnotesize
const GameSpace & gs = game->getGameSpace();     
\end_layout

\begin_layout LyX-Code

\size footnotesize
int w = gs.getWidth();     
\end_layout

\begin_layout LyX-Code

\size footnotesize
int h = gs.getHeight();     
\end_layout

\begin_layout LyX-Code

\size footnotesize
const LogicObject * pacman = game->getObject(PACMAN);     
\end_layout

\begin_layout LyX-Code

\size footnotesize
const Shape * shape = pacman->getShape();     
\end_layout

\begin_layout LyX-Code

\size footnotesize
int x = shape->getX();     
\end_layout

\begin_layout LyX-Code

\size footnotesize
int y = shape->getY();     
\end_layout

\begin_layout LyX-Code

\size footnotesize
int hi, hf, wi, wf; //Extremos del rectangulo.
     
\end_layout

\begin_layout LyX-Code

\size footnotesize
hi = max(0, y - frontera);     
\end_layout

\begin_layout LyX-Code

\size footnotesize
hf = min(h - 1, y + frontera);     
\end_layout

\begin_layout LyX-Code

\size footnotesize
wi = max(0, x - frontera);     
\end_layout

\begin_layout LyX-Code

\size footnotesize
wf = min(w - 1, x + frontera);     
\end_layout

\begin_layout LyX-Code

\size footnotesize
set<string> ghostSubtype;     
\end_layout

\begin_layout LyX-Code

\size footnotesize
ghostSubtype.insert(GHOST);     
\end_layout

\begin_layout LyX-Code

\size footnotesize
list<const LogicObject *> ghosts;     
\end_layout

\begin_layout LyX-Code

\size footnotesize
gs.getObjects(Rectangle(wi,hi,wf-wi,hf-hi), 
\end_layout

\begin_layout LyX-Code

\size footnotesize
              LogicObject::Type(ghostSubtype), ghosts);     
\end_layout

\begin_layout LyX-Code

\size footnotesize
int cant_ghosts = ghosts.size();     
\end_layout

\begin_layout LyX-Code

\size footnotesize
int cant_puntos = game->getVariables().getInteger(DOT_COUNT);    
\end_layout

\begin_layout LyX-Code

\size footnotesize
int dist_cercano = distancia_punto_mas_cercano(pacman, gs);
\end_layout

\begin_layout LyX-Code

\size footnotesize
return 5*cant_puntos + cant_ghosts * frontera + dist_cercano/10; 
\end_layout

\end_deeper
\begin_layout LyX-Code

\size footnotesize
}
\end_layout

\begin_layout Standard
Se observa que el código de esta heurística es una combinación de las primeras
 dos.
 Como se menciono anteriormente, se eligió el factor de la cantidad de puntos
 para que tenga mayor importancia que en casi todos los estados del juego(más
 que nada para cuando queden pocos puntos).
 Para que la distancia al más cercano sólo tenga incidencia a distancias
 significativas se divide el resultado por 10(si la distancia es menor que
 10 ese término es cero).
 
\end_layout

\begin_layout Standard
Al igual que en la primera heurística el término que contiene a la cantidad
 de fantasmas puede interpretarse como la cantidad de pasos para alejarse
 de esa zona, y además, cuantos más fantasmas hay en la zona mayor es el
 peligro.
\end_layout

\begin_layout Standard
Como en la segunda heurística, la complejidad está determinada por la complejida
d de la función distancia_punto_mas_cercano, que es de 
\begin_inset Formula $O\left(w*h\right)$
\end_inset

, siendo 
\begin_inset Formula $w$
\end_inset

 y 
\begin_inset Formula $h$
\end_inset

 el ancho y el largo del mapa respectivamente.
\end_layout

\begin_layout Subsubsection*
Resultados empíricos e interpretación
\end_layout

\begin_layout Standard
Se hizo una serie de pruebas a esta heurística para ver si se pudo mejorar
 las heurísticas anteriores.
 También es interesante observar el comportamiento, especialmente ver si
 se corrigieron las falencias que habíamos encontrado.
 Además, como se previó que esta heurística podría obtener buenos resultados
 en niveles bajos, probamos la función en dos niveles bajos(10 y 12) para
 corroborar o refutar nuestra hipótesis.
\end_layout

\begin_layout Standard
En niveles de profundidad elevados, es interesante ver como se comporta
 el pacman con respecto a las variables cantidad de puntos y distancia al
 punto más cercano, porque puede que al tener mayor alcance en el mapa la
 distancia al punto más cercano no tenga tanta incidencia como en los niveles
 bajos.
\end_layout

\begin_layout Standard
Otro aspecto a tener en cuenta es la incidencia de los factores y si estos
 cambian el comportamiento con respecto a las heurísticas 1 y 2.
\end_layout

\begin_layout Standard
\begin_inset Float table
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="5">
<features>
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Nivel
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Resultado
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Pasos
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Puntos restantes
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Estados evaluados
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
10
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Perdió
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
371
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
26
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
13170
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
12
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Ganó
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
452
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
22044
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
20
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Ganó
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
423
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
62558
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
30
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Ganó
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
509
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
252462
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Resultados de la heurística 3
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
Algunas observaciones sobre los resultados de la heurística:
\end_layout

\begin_layout Itemize
En general, se obtuvieron soluciones en menos pasos que en la heurística
 1 y en los niveles bajos sobrevivió por mayor tiempo en comparación con
 la segunda heurística.
 Esto concuerda con el objetivo principal de esta heurística.
 En particular, el resultado del nivel 10 muestra esta situación, si bien
 no se pudo ganar como en la heurística 1, el pacman logro una solución
 parcial en una cantidad de pasos bastante menor y además logro sobrevivir
 por más tiempo que en la heurística 2.
\end_layout

\begin_layout Itemize
Recordemos que en la segunda heurística en algunos estados el pacman tenía
 un comportamiento cíclico, es decir, se movía en una dirección y luego
 en la opuesta.
 Con el costo agregado de los fantasmas, este comportamiento se reduce considera
blemente, esto ocurre porque los fantasmas tienen mayor incidencia en el
 costo cuando se encuentran cerca del pacman, lo que lo lleva a moverse
 hacia una dirección y no volver atrás.
 El factor asociado a la distancia al punto más cercano también tuvo incidencia
 en este resultado, porque ahora sólo se consideran en el costo distancias
 mayores a 10 pasos, de esta forma se le da más importancia a la cantidad
 de puntos que a la distancia.
\end_layout

\begin_layout Itemize
El factor aplicado a la cantidad de puntos hizo que en el tramo final del
 juego el costo asociado a los fantasmas no sea tan preponderante, y así
 llegar a una solución en menos pasos.
 Aunque en niveles bajos el pacman sigue siendo bastante cauteloso en el
 tramo final(por ejemplo, en el nivel 12 cuando le quedan dos puntos, se
 asegura de estar bastante alejado antes de comerlos).
 En niveles altos esto no ocurre en forma marcada porque la profundidad
 de exploración permite prever el estado en el que gana con anterioridad.
\end_layout

\begin_layout Itemize
Un problema que incide en la cantidad de pasos de la solución es que se
 dejan puntos aislados en algunas secciones, esto también ocurrió en las
 heurísticas anteriores y es más evidente cuando se prueba con niveles altos.
 Esta comportamiento ocurre porque no se considera en el valor de la heurística
 el costo asociado a volver a comer los puntos olvidados, y en niveles altos
 es más marcado porque el pacman puede ver una zona con muchos puntos lo
 que lo lleva directamente hacia allí.
\end_layout

\begin_layout Itemize
En el gráfico de la figura 6 se observa que al principio se sobre estima
 el costo asociado, esto ocurre por el factor de los puntos, cuando quedan
 menos puntos, el valor se acerca al real.
 
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename Heuristica3-30.gif
	scale 40

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Precisión de la heurística 3
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Heurística 4
\end_layout

\begin_layout Subsubsection*
Idea e hipótesis
\end_layout

\begin_layout Standard
La cuarta heurística usa técnicas usadas en las heurísticas anteriores,
 con cambios significativos en los factores de las variables y en la forma
 de medir distancias.
 Además, se cambia la forma en que el pacman recorre el espacio de juego.
\end_layout

\begin_layout Standard
En esta heurística se divide el espacio en dos zonas del mismo tamaño, la
 zona superior y la zona inferior.
 La idea es que si se comen primeros los puntos de una zona y luego se pasa
 a la otra se evitará en mayor medida recorrer muchas veces caminos largos
 sin puntos.
 Para hacer que el pacman coma los puntos de una zona antes que en la otra,
 los puntos restantes se consideran en dos variables, una para la zona inferior
 y otra para la superior.
 Los puntos de la zona con más prioridad(en este caso se tomó la inferior
 porque es en donde comienza el juego) tendrán un factor mayor.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename zonas-heur-4.png
	scale 40

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
División del mapa en zonas
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
El otro costo asociado en la heurística es la distancia a todos los fantasmas.
 A diferencia de la primera heurística, en la cual se consideraba la cantidad
 de fantasmas dentro de una frontera, se tiene en cuenta la distancia en
 forma más precisa.
 También se aplica un factor a la distancia de cada fantasma para que sea
 inversamente proporcional al costo asociado.
 En cuanto a los cambios de medición de distancias se cambió la distancia
 de Manhattan por la euclideana.
 A diferencia de la distancia de Manhattan, la distancia euclideana da una
 cota inferior de la cantidad de pasos comprendidos entre dos puntos.
 La prueba experimental con estas distancias llevó a elegir a la distancia
 euclideana para esta heurística(en contraposición a lo planteado para las
 heurísticas 2 y 3).
 Como esta distancia es una cota inferior de la distancia real, su elección
 tiene la consecuencia de que el costo asociado a los fantasmas sea mayor
 que si se toma la de Manhattan.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename man y euc.png
	scale 40

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Distancias de Manhattan(rojo) y euclideana(verde) desde el pacman a un fantasma.
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Subsubsection*
Implementación
\end_layout

\begin_layout Standard
Se define la distancia euclideana:
\end_layout

\begin_layout LyX-Code

\size footnotesize
int distancia_euclidiana(int x1, int x2, int y1, int y2) 
\end_layout

\begin_layout LyX-Code

\size footnotesize
{     
\end_layout

\begin_deeper
\begin_layout LyX-Code

\size footnotesize
return (int)sqrt(pow((x2-x1), 2) + pow((y2-y1), 2)); 
\end_layout

\end_deeper
\begin_layout LyX-Code

\size footnotesize
}
\end_layout

\begin_layout Standard
Y la función heurística 4:
\end_layout

\begin_layout LyX-Code

\size footnotesize
unsigned int h4(const Game * game) 
\end_layout

\begin_layout LyX-Code

\size footnotesize
{     
\end_layout

\begin_deeper
\begin_layout LyX-Code

\size footnotesize
const GameSpace & gs = game->getGameSpace();     
\end_layout

\begin_layout LyX-Code

\size footnotesize
const LogicObject * pacman = game->getObject(PACMAN);     
\end_layout

\begin_layout LyX-Code

\size footnotesize
int pac_x = pacman->getShape()->getX();     
\end_layout

\begin_layout LyX-Code

\size footnotesize
int pac_y = pacman->getShape()->getY();     
\end_layout

\begin_layout LyX-Code

\size footnotesize
int cant_puntos = game->getVariables().getInteger(DOT_COUNT);
\end_layout

\begin_layout LyX-Code

\size footnotesize
int costo_fantasmas = 0;     
\end_layout

\begin_layout LyX-Code

\size footnotesize
list<const LogicObject *> ghosts;     
\end_layout

\end_deeper
\begin_layout LyX-Code

\end_layout

\begin_deeper
\begin_layout LyX-Code

\size footnotesize
ghosts.push_back(game->getObject(CLYDE));     
\end_layout

\begin_layout LyX-Code

\size footnotesize
ghosts.push_back(game->getObject(INKY));     
\end_layout

\begin_layout LyX-Code

\size footnotesize
ghosts.push_back(game->getObject(PINKY));     
\end_layout

\begin_layout LyX-Code

\size footnotesize
ghosts.push_back(game->getObject(BLINKY));
\end_layout

\begin_layout LyX-Code

\size footnotesize
list<const LogicObject *>::iterator it;
\end_layout

\begin_layout LyX-Code

\size footnotesize
for (it = ghosts.begin(); it != ghosts.end(); it++)     
\end_layout

\begin_layout LyX-Code

\size footnotesize
{         
\end_layout

\begin_deeper
\begin_layout LyX-Code

\size footnotesize
const Shape * s = (*it)->getShape();         
\end_layout

\begin_layout LyX-Code

\size footnotesize
costo_fantasmas += 10/distancia_euclidiana(s->getX(), pac_x, s->getY(),
 pac_y);
\end_layout

\end_deeper
\begin_layout LyX-Code

\size footnotesize
}
\end_layout

\begin_layout LyX-Code

\size footnotesize
list<const LogicObject *> puntos;     
\end_layout

\begin_layout LyX-Code

\size footnotesize
gs.getObjects(Rectangle(0, 15, 28, 31), DOT, puntos);     
\end_layout

\begin_layout LyX-Code

\size footnotesize
int puntos_abajo = puntos.size();     
\end_layout

\begin_layout LyX-Code

\size footnotesize
int puntos_arriba = cant_puntos - puntos_abajo;
\end_layout

\begin_layout LyX-Code

\size footnotesize
return 10*puntos_abajo + puntos_arriba + costo_fantasmas; 
\end_layout

\end_deeper
\begin_layout LyX-Code

\size footnotesize
}
\end_layout

\begin_layout Standard
El costo de la cantidad de puntos se calcula en forma separada teniendo
 en cuenta los puntos de cada zona, el factor de los puntos de la zona inferior
 es mayor que el de los de la zona superior por lo mencionado en la hipótesis.
\end_layout

\begin_layout Standard
En las iteraciones del ciclo for se calcula el costo que asociado a la posición
 de los fantasmas.
 Como la distancia es inversamente proporcional al costo, se encuentra dividiend
o en el cálculo.
 El factor(10) al que se divide puede pensarse como la máxima distancia
 en la que tendrá incidencia un fantasma.
 
\end_layout

\begin_layout Standard
Como la cantidad de puntos de cada zona se obtiene pidiendo el rectángulo
 que la comprende, la complejidad de la función es de 
\begin_inset Formula $O\left(w*h\right)$
\end_inset

, donde 
\begin_inset Formula $w$
\end_inset

 y 
\begin_inset Formula $h$
\end_inset

 son el ancho y el largo del mapa respectivamente.
\end_layout

\begin_layout Subsubsection*
Resultados empíricos e interpretación
\end_layout

\begin_layout Standard
La función se probó en dos niveles de profundidad bajos (8 y 10) y dos altos(20
 y 30).
 Además de la comparación de los resultados con las heurísticas anteriores,
 en los niveles bajos se observa el comportamiento considerando que tan
 efectivo es el costo asociado a los fantasmas(en niveles altos este costo
 no es tan importante para la supervivencia) y que incidencia tiene la división
 del costo de los puntos en zonas tanto en los niveles bajos como en los
 altos.
\end_layout

\begin_layout Standard
\begin_inset Float table
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Tabular
<lyxtabular version="3" rows="5" columns="5">
<features>
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Nivel
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Resultado
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Pasos
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Puntos restantes
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Estados evaluados
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
8
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Perdió
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
652
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
20
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
16204
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
10
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Ganó
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
358
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
14434
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
20
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Ganó
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
405
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
70050
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
30
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Ganó
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
449
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
254101
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Resultados de la heurística 4.
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
Observaciones sobre los resultados y comportamiento:
\end_layout

\begin_layout Itemize
En los niveles bajos el pacman llega a comer una buena cantidad de puntos(en
 10 ganó), en el nivel 8 el pacman termina acorralado en una esquina.
 Las esquinas del mapa son puntos peligrosos porque si dos fantasmas se
 dirigen a cada salida, en niveles de profundidad bajos y cuando hay puntos
 en la esquina no se prevé esta situación y termina perdiendo.
 Quizás, otra heurística podría aumentar el costo cuando se pasa por las
 esquinas.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename casi-acorr.png
	scale 40

\end_inset


\begin_inset Graphics
	filename acorr.png
	scale 40

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Pacman acorralado en una esquina.
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Itemize
En el nivel de profundidad 10 se obtuvo la mejor solución(hasta el momento)
 de todas las heurísticas.
 La principal razón de este resultado es que el pacman comió los puntos
 de la zona inferior, y luego las de la zona superior, sin volver abajo.
 En este caso se dejaron menos puntos aislados que en las heurísticas anteriores
, haciendo que al final se tengan que recorrer longitudes más cortas para
 comer la totalidad de los puntos.
 Que en el nivel 10 se haya conseguido una buena solución, no significa
 que la heurística pueda conseguir soluciones iguales o mejores en niveles
 cercanos al 10(como se vio en el caso del nivel 8).
 Esto en parte ocurre porque no se tienen en cuenta la distancia a los puntos
 a (diferencia de las heurísticas 2 y 3), combinado con la posibilidad de
 que el costo de los fantasmas lleve al pacman a una zona donde no hay puntos.
\end_layout

\begin_layout Itemize
En los niveles de profundidad más altos vuelve a surgir el problema de los
 puntos aislados, aunque en este caso se produce localmente en cada zona.
 Este comportamiento era de esperarse, porque al tener mayor visión el pacman
 puede verse comiendo en una zona con una densidad de puntos mayor a la
 de la zona en la que se encuentra antes de la exploración que realiza el
 método 
\emph on
minimin
\emph default
.
 Si bien surgió este problema, no es tan marcado como en las otras heurísticas,
 por esto se observa una mejora en la cantidad final de pasos para los niveles
 20 y 30.
 Una forma de reducir aún más los puntos aislados sería dividir el mapa
 en más zonas.
\end_layout

\begin_layout Subsection
Heurística 5
\end_layout

\begin_layout Subsubsection*
Idea e hipótesis
\end_layout

\begin_layout Standard
Esta heurística considera al espacio de juego dividido en 4 esquinas.
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename esquinas.png
	scale 40

\end_inset


\begin_inset Caption

\begin_layout Plain Layout
División en esquinas
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
La idea detrás de esta división es minimizar la cantidad de puntos que se
 dejan en una zona antes de pasar a la siguiente.
\end_layout

\begin_layout Standard
Las variables que se tienen en cuenta son la cantidad de puntos restantes
 en la totalidad del juego y en la zona correspondiente a la ubicación del
 pacman.
\end_layout

\begin_layout Standard
El resultado esperado al considerar la cantidad de puntos por zona es minimizar
 la cantidad de puntos aislados hacia el final del juego y en consecuencia
 el número de pasos requeridos para hallar la solución.
\end_layout

\begin_layout Standard
La cantidad de puntos restantes en la totalidad del juego tendrán más importanci
a debido a que no siempre será posible consumir todos los puntos de una
 zona antes de pasar a la siguiente.
\end_layout

\begin_layout Subsubsection*
Implementación
\end_layout

\begin_layout LyX-Code

\size footnotesize
unsigned int h5(const Game * game)
\end_layout

\begin_layout LyX-Code

\size footnotesize
{
\end_layout

\begin_deeper
\begin_layout LyX-Code

\size footnotesize
const LogicObject * pacman = game->getObject(PACMAN);
\end_layout

\begin_layout LyX-Code

\size footnotesize
const GameSpace & gs = game->getGameSpace();
\end_layout

\begin_layout LyX-Code

\size footnotesize
int cant_puntos = game->getVariables().getInteger(DOT_COUNT);
\end_layout

\begin_layout LyX-Code

\size footnotesize
int pac_x, pac_y;
\end_layout

\begin_layout LyX-Code

\size footnotesize
pac_x = pacman->getShape()->getX();
\end_layout

\begin_layout LyX-Code

\size footnotesize
pac_y = pacman->getShape()->getY();
\end_layout

\begin_layout LyX-Code

\size footnotesize
int hi, hf, wi, wf;
\end_layout

\begin_layout LyX-Code

\size footnotesize
if (pac_x <= 14)
\end_layout

\begin_layout LyX-Code

\size footnotesize
{
\end_layout

\begin_deeper
\begin_layout LyX-Code

\size footnotesize
wi = 1;
\end_layout

\begin_layout LyX-Code

\size footnotesize
wf = 14;
\end_layout

\begin_layout LyX-Code

\size footnotesize
if(pac_y <= 15)
\end_layout

\begin_layout LyX-Code

\size footnotesize
{
\end_layout

\begin_deeper
\begin_layout LyX-Code

\size footnotesize
hi = 1;
\end_layout

\begin_layout LyX-Code

\size footnotesize
hf = 15; 
\end_layout

\end_deeper
\begin_layout LyX-Code

\size footnotesize
}   
\end_layout

\begin_layout LyX-Code

\size footnotesize
else 
\end_layout

\begin_layout LyX-Code

\size footnotesize
{ 
\end_layout

\begin_deeper
\begin_layout LyX-Code

\size footnotesize
hi = 15;
\end_layout

\begin_layout LyX-Code

\size footnotesize
hf = 31;
\end_layout

\end_deeper
\begin_layout LyX-Code

\size footnotesize
}     
\end_layout

\end_deeper
\begin_layout LyX-Code

\size footnotesize
}
\end_layout

\begin_layout LyX-Code

\size footnotesize
else
\end_layout

\begin_layout LyX-Code

\size footnotesize
{
\end_layout

\begin_deeper
\begin_layout LyX-Code

\size footnotesize
wi = 14;
\end_layout

\begin_layout LyX-Code

\size footnotesize
wf = 28;
\end_layout

\begin_layout LyX-Code

\size footnotesize
if(pac_y <= 15)
\end_layout

\begin_layout LyX-Code

\size footnotesize
{
\end_layout

\begin_deeper
\begin_layout LyX-Code

\size footnotesize
hi = 1;
\end_layout

\begin_layout LyX-Code

\size footnotesize
hf = 15;
\end_layout

\end_deeper
\begin_layout LyX-Code

\size footnotesize
}
\end_layout

\begin_layout LyX-Code

\size footnotesize
else
\end_layout

\begin_layout LyX-Code

\size footnotesize
{ 
\end_layout

\begin_deeper
\begin_layout LyX-Code

\size footnotesize
hi = 15;
\end_layout

\begin_layout LyX-Code

\size footnotesize
hf = 31;
\end_layout

\end_deeper
\begin_layout LyX-Code

\size footnotesize
}
\end_layout

\end_deeper
\begin_layout LyX-Code

\size footnotesize
}
\end_layout

\begin_layout LyX-Code

\size footnotesize
list<const LogicObject *> puntos;
\end_layout

\begin_layout LyX-Code

\size footnotesize
gs.getObjects(Rectangle(wi,hi,wf,hf), DOT, puntos);
\end_layout

\begin_layout LyX-Code

\size footnotesize
int cant_puntos_zona = puntos.size();
\end_layout

\begin_layout LyX-Code

\size footnotesize
return 2*cant_puntos + cant_puntos_zona/5;
\end_layout

\end_deeper
\begin_layout LyX-Code

\size footnotesize
} 
\end_layout

\begin_layout Standard
Como es posible observar, la implementación es muy sencilla y la operación
 más costosa es la de obtener los puntos de la zona requerida.
\end_layout

\begin_layout Standard
Uno de los factores empleados para ajustar la ecuación es el factor(2) que
 multiplica a la cantidad de puntos que quedan por consumir para ganar el
 juego.
 La necesidad de este factor de ajuste surge a partir de, como fue mencionado
 anteriormente, priorizar el consumo de puntos ya que en algunas ocasiones
 no es posible consumir todos los puntos de una zona antes de pasar a otra
 y también de evitar que el pacman se quede dando vueltas en una misma esquina
 evitando pasar a la siguiente.
\end_layout

\begin_layout Standard
El otro factor empleado es el factor(1/5) que multiplica a la cantidad de
 puntos restantes en la zona, este factor puede interpretarse como que es
 aceptable que queden 5 puntos en una zona antes de moverse a la siguiente.
\end_layout

\begin_layout Subsubsection*
Resultados empíricos e interpretación
\end_layout

\begin_layout Standard
La función de evaluación heurística se probó en diferentes niveles de profundida
d (10, 18, 20, 30 y 35) y se comparó con las anteriores.
\end_layout

\begin_layout Standard
El primer punto interesante de comparación surge a partir de la comparación
 de la cantidad de niveles necesarios para llegar a ganar el juego.
 Al no considerar en ninguna medida a los fantasmas es previsible que se
 requiera una mayor cantidad de niveles.
\end_layout

\begin_layout Standard
\begin_inset Float table
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Tabular
<lyxtabular version="3" rows="6" columns="5">
<features>
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Nivel
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Resultado
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Pasos
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Puntos restantes
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Estados Evaluados
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
10
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Perdió
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
90
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
176
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
2764
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
18
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Ganó
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
811
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
81541
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
20
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Ganó
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
440
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
69312
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
30
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Ganó
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
462
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
240121
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
35
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Ganó
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
420
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
373377
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Resultados de la heurística 5
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
A partir del análisis de los resultados obtenidos se pueden remarcar los
 siguientes puntos:
\end_layout

\begin_layout Itemize
En niveles bajos, al no considerar a los fantasmas, el pacman queda atrapado
 y pierde el juego.
\end_layout

\begin_layout Itemize
Los cambios de zonas se producen cuando el pacman es perseguido por los
 fantasmas y obligado a desplazarse fuera de la esquina en la que se encontraba.
 Estos cambios se dan incluso aunque el pacman no haya terminado de consumir
 los puntos de la zona.
\end_layout

\begin_layout Itemize
Al cambiar de zona, debido a las características de la heurística, cambia
 el objetivo del pacman y no vuelve por los puntos que dejó atrás hasta
 regresar a la esquina anterior.
\end_layout

\begin_layout Itemize
En el nivel 18 surge algo interesante, cuando el pacman consume los puntos
 de las dos esquinas inferiores, debido a la baja profundidad, no puede
 ver que quedan puntos por consumir en las dos zonas superiores y sólo los
 alcanza cuando es perseguido por los fantasmas y se ve obligado a ir hacia
 arriba.
 Así se explica el alto número de acciones requeridas para completar el
 juego.
\end_layout

\begin_layout Itemize
En la figura 11 se puede ver que en general los valores devueltos se encuentran
 por debajo del costo real.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename Heuristica5-30.gif
	scale 40

\end_inset


\begin_inset Caption

\begin_layout Plain Layout
Precisión de la heurística 5
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename cambio de zona.png
	scale 40

\end_inset


\begin_inset Caption

\begin_layout Plain Layout
El pacman es obligado a cambiar de zona por los fantasmas
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Heurística 6
\end_layout

\begin_layout Subsubsection*
Idea e hipótesis
\end_layout

\begin_layout Standard
En la esta última heurística se toma como base la heurística 4, con cambios
 en los factores utilizados.
 Además se introducen variables nuevas y otras que han sido utilizadas en
 heurísticas anteriores.
 La idea de esta heurística es dar punto final al trabajo considerando una
 mayor cantidad de variables.
\end_layout

\begin_layout Standard
Recordemos que en la heurística 4 el mapa se dividía en dos secciones(inferior
 y superior), además la cercanía de los fantasmas al pacman incidía en buena
 parte del costo.
\end_layout

\begin_layout Standard
Para esta función se hicieron las observaciones y modificaciones:
\end_layout

\begin_layout Itemize
El objetivo principal de esta heurística no es el rendimiento en niveles
 altos, sino la mejora de la heurística 4 para que se logre una solución
 en niveles bajos(menos de 8) de profundidad, considerando también la cantidad
 de pasos de la solución.
\end_layout

\begin_layout Itemize
Nos pareció interesante que el modo asustadizo de los fantasmas tenga incidencia
 en el costo.
 El sentido común indica que en los estados de modo asustadizo los fantasmas
 son menos peligrosos para el pacman.
\end_layout

\begin_layout Itemize
A partir de las muertes en las esquinas del mapa en las heurísticas anteriores
 se plantea un costo adicional respecto de la posición del pacman en un
 estado determinado(hay una penalización por estar en las esquinas).
 Para este costo se tiene en cuenta la distancia de la posición del pacman
 al centro del mapa(las esquinas son los puntos más alejados del centro).
 El modo asustadizo también tendrá incidencia en que tan peligroso se considere
 estar en una esquina.
\end_layout

\begin_layout Itemize
Vuelve a usarse la distancia al punto más cercano principalmente como guía
 del pacman en niveles bajos.
\end_layout

\begin_layout Standard
Nuestra expectativa para esta heurística es que con todas las optimizaciones
 en cuanto a la supervivencia se logre obtener soluciones en niveles de
 profundidad bastante bajos.
 Para los niveles altos creemos que se van a conseguir soluciones pero no
 necesariamente buenas porque no se puso tanta atención en éstos, y como
 se ha visto a lo largo del trabajo, generalmente cuando se optimiza para
 una determinada situación, en otras partes baja la calidad de la heurística.
\end_layout

\begin_layout Standard
Otro problema que puede surgir al considerar tantas variables y en consecuencia
 que sea la heurística más compleja, es que se observe un comportamiento
 inesperado con respecto a las hipótesis anteriores y que sea más difícil
 encontrar los factores de cada componente, porque la modificación del factor
 de una variable incide en el costo relativo con todas las otras variables.
\end_layout

\begin_layout Subsubsection*
Implementación
\end_layout

\begin_layout LyX-Code

\size scriptsize
unsigned int h6(const Game * game) 
\end_layout

\begin_layout LyX-Code

\size scriptsize
{     
\end_layout

\begin_deeper
\begin_layout LyX-Code

\size scriptsize
const GameSpace & gs = game->getGameSpace();     
\end_layout

\begin_layout LyX-Code

\size scriptsize
int h = gs.getHeight();     
\end_layout

\begin_layout LyX-Code

\size scriptsize
int w = gs.getWidth();     
\end_layout

\begin_layout LyX-Code

\size scriptsize
const LogicObject * pacman = game->getObject(PACMAN);     
\end_layout

\begin_layout LyX-Code

\size scriptsize
int pac_x = pacman->getShape()->getX();     
\end_layout

\begin_layout LyX-Code

\size scriptsize
int pac_y = pacman->getShape()->getY();     
\end_layout

\begin_layout LyX-Code

\size scriptsize
int cant_puntos = game->getVariables().getInteger(DOT_COUNT);
\end_layout

\begin_layout LyX-Code

\end_layout

\begin_layout LyX-Code

\size scriptsize
int costo_fantasmas = 0;     
\end_layout

\begin_layout LyX-Code

\size scriptsize
list<const LogicObject *> ghosts;     
\end_layout

\begin_layout LyX-Code

\size scriptsize
ghosts.push_back(game->getObject(CLYDE));     
\end_layout

\begin_layout LyX-Code

\size scriptsize
ghosts.push_back(game->getObject(INKY));     
\end_layout

\begin_layout LyX-Code

\size scriptsize
ghosts.push_back(game->getObject(PINKY));     
\end_layout

\begin_layout LyX-Code

\size scriptsize
ghosts.push_back(game->getObject(BLINKY));     
\end_layout

\begin_layout LyX-Code

\size scriptsize
bool modo_asust = game->getVariables().getBoolean(SCATTERED_MODE);     
\end_layout

\begin_layout LyX-Code

\size scriptsize
if (!modo_asust)
\end_layout

\begin_layout LyX-Code

\size scriptsize
{
\end_layout

\begin_deeper
\begin_layout LyX-Code

\size scriptsize
list<const LogicObject *>::iterator it;   
\end_layout

\begin_layout LyX-Code

\size scriptsize
for (it = ghost.begin(); it != ghosts.end(); it++)
\end_layout

\begin_layout LyX-Code

\size scriptsize
{             
\end_layout

\begin_deeper
\begin_layout LyX-Code

\size scriptsize
const Shape * s = (*it)->getShape();             
\end_layout

\begin_layout LyX-Code

\size scriptsize
costo_fantasmas += 15/distancia_euclidiana(s->getX(), pac_x, s->getY(),
 pac_y);       
\end_layout

\end_deeper
\begin_layout LyX-Code

\size scriptsize
}
\end_layout

\end_deeper
\begin_layout LyX-Code

\size scriptsize
}
\end_layout

\begin_layout LyX-Code

\size scriptsize
list<const LogicObject *> puntos;     
\end_layout

\begin_layout LyX-Code

\size scriptsize
gs.getObjects(Rectangle(0, 15, 28, 31), DOT, puntos);     
\end_layout

\begin_layout LyX-Code

\size scriptsize
int puntos_abajo = puntos.size();     
\end_layout

\begin_layout LyX-Code

\size scriptsize
int puntos_arriba = cant_puntos - puntos_abajo;     
\end_layout

\begin_layout LyX-Code

\size scriptsize
int dist_cercano = distancia_punto_mas_cercano(pacman, gs);     
\end_layout

\begin_layout LyX-Code

\size scriptsize
int dist_centro = abs(pac_x-w/2) + abs(pac_y-h/2);
\end_layout

\begin_layout LyX-Code

\size scriptsize
if (modo_asust)         
\end_layout

\begin_deeper
\begin_layout LyX-Code

\size scriptsize
return  10*puntos_abajo + puntos_arriba + costo_fantasmas + dist_cercano/10
 + dist_centro/7;
\end_layout

\end_deeper
\begin_layout LyX-Code

\size scriptsize
return 3*puntos_abajo + puntos_arriba + costo_fantasmas +  dist_cercano/10
 + dist_centro/2;
\end_layout

\end_deeper
\begin_layout LyX-Code

\size scriptsize
}
\end_layout

\begin_layout Standard
Se destaca sobre la implementación:
\end_layout

\begin_layout Itemize
Se aumentó el factor del costo de los fantasmas con respecto a la heurística
 4(antes se tomaba 10/distancia) con el objetivo de que el pacman sea más
 cuidadoso.
\end_layout

\begin_layout Itemize
Si se está en modo asustadizo el costo de la distancia a los fantasmas es
 0.
 Se tomó está decisión considerando que si en un estado en el cual los fantasmas
 están cerca y se está en modo asustadizo, los fantasmas comenzarán a alejarse
 cada uno a su esquina.
 Si cada fantasma esta en su esquina, estar cerca de uno de estos no se
 considera peligroso porque los demás fantasmas están lejos(se toma un costo
 más contundente de lo que tomaría la distancia).
\end_layout

\begin_layout Itemize
El resultado final también depende si se está en modo asustadizo(como se
 ve en el if final).
 Cuando se está en modo asustadizo se toman menos precauciones haciendo
 que el costo final dependa en una mayor proporción a la cantidad de puntos.
 Igualmente se tiene en cuenta la distancia al centro para penalizar el
 pasaje por los bordes exteriores(principalmente las esquinas).
 El factor aplicado(1/7) puede pensarse como la cercanía con que tiene que
 estar el pacman del centro para estar seguro(en este caso si esta a menos
 de 7 pasos el costo de la distancia al centro se hace 0).
 Cuando no está en modo asustadizo el costo de la cercanía al centro decrementa
 y la cantidad de puntos en el estado no es tan significativa como antes(se
 modificó el factor de los puntos de la zona inferior, porque es en esa
 zona en la que el pacman tiene mayores problemas).
\end_layout

\begin_layout Subsubsection*
Resultados empíricos e implementación
\end_layout

\begin_layout Standard
La heurística se probó en los 3 niveles habituales(10, 20 y 30) y se agregaron
 los niveles 6 y 8 para ver como se comporta respecto a las hipótesis y
 si se encuentra algún comportamiento inesperado.
\end_layout

\begin_layout Standard
\begin_inset Float table
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Tabular
<lyxtabular version="3" rows="6" columns="5">
<features>
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<column alignment="center" valignment="top" width="0">
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Nivel
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Resultado
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Pasos
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Puntos restantes
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Estados evaluados
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
6
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Ganó
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1403
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
21704
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
8
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Ganó
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
575
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
16251
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
10
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Perdió
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
1001
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
5
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
40439
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
20
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Perdió
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
215
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
82
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
35890
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
30
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
Ganó
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
489
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
0
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
278885
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Resultados de la heurística 6
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
Observaciones sobre el comportamiento y los resultados:
\end_layout

\begin_layout Itemize
En los niveles bajos (6 y 8) las expectativas se cumplieron(aunque en 6
 fue bastante mayor la cantidad de pasos).
 Esta es la única heurística en la que se ganó en niveles tan bajos y se
 debe a la optimización que se pensó para éstos.
 Del comportamiento en el nivel 6 puede decirse que hubiera sido posible
 ganar mucho antes con una heurística mejor, cuando quedaban pocos puntos(figura
 13) el costo de la cercanía al centro, el costo asociado a los fantasmas
 y el hecho de que no hubiera mas estados en modo asustadizo hizo que el
 pacman se demorase más de la mitad de los pasos para comer los puntos restantes.
 El costo de la distancia también influyo mas que nada por ser un nivel
 bajo, primero influyo en forma positiva porque permitió al pacman acercarse
 a puntos lejanos, pero también fue negativo cuando hizo que no se comieran
 puntos porque la distancia al punto más cercano sería más significativa.
 En el nivel 8 estos problemas que aumentan tanto los pasos de la solución
 no ocurrieron.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename ultimos-puntos.png
	scale 40

\end_inset


\begin_inset Caption

\begin_layout Plain Layout
Le quedan pocos puntos por comer
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Itemize
El costo asociado a la cercanía al centro hizo que el pacman fuera más cuidadoso
 a la hora de pasar por las esquinas, en general sólo pasó por las esquinas
 cuando se estaba en modo asustadizo o los fantasmas no estaban cerca.
\end_layout

\begin_layout Itemize
Los resultados en los niveles 10 y 20 fueron inesperados(sobre todo en nivel
 20 que hasta ahora siempre se había ganado).
 Paradójicamente, en nivel 20 el pacman es acorralado en una esquina cuando
 va en búsqueda de puntos.
 Aquí se ve la incidencia de los factores de las variables con respecto
 al nivel de profundidad, porque la combinación del factor elevado de los
 puntos de la zona inferior y la capacidad de exploración en ese nivel(haciendo
 que el pacman 
\begin_inset Quotes eld
\end_inset

se vea
\begin_inset Quotes erd
\end_inset

 comiendo mayor cantidad de puntos) hace que se tome la decisión equivocada
 e ir en busca de esos puntos aún cuando el costo asociado a los fantasmas
 y la distancia al centro es mayor que en otros estados.
 El nivel 30 ya supera está situación por lo que no se presenta el mismo
 resultado.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename perdio-20.png
	scale 40

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout
Pacman acorralado en nivel 20
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename Heuristica6-6.gif
	scale 40

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption

\begin_layout Plain Layout

\size footnotesize
Grafico de predicción de la heurística 6 en nivel 6.
 Es bastante mala por la cantidad de variables considerada y la incidencia
 de los factores.
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Conclusión
\end_layout

\begin_layout Standard
En este trabajo presentamos la implementación y el análisis empírico para
 heurísticas del juego pacman.
 Probamos alternativas que representan diferentes estrategias de juego siempre
 considerando lo que significa cada componente del costo en la heurística.
 En todas las heurísticas vimos a la cantidad de puntos de un estado como
 una representación importante de su calidad, porque al fin y al cabo el
 objetivo principal del juego es que el pacman coma la totalidad de los
 puntos.
\end_layout

\begin_layout Standard
En lo personal, este trabajo nos resultó bastante distinto a lo que veníamos
 haciendo en otros trabajos porque se le dio más importancia a la prueba
 y el análisis de los resultados que a la implementación.
 Además el hecho de que el análisis haya sido en mayor parte empírico incidió
 en la forma en que sacamos las conclusiones y en muchas oportunidades hizo
 tuviéramos que corregir hipótesis planteadas antes de las pruebas.
 
\end_layout

\end_body
\end_document