Índice:
1. Introducción al contexto de la práctica.
2. Breve descripción de la estructura de la memoria.
3. Estudio del algoritmo Hill Climbing.
3.1. Objetivo.
3.2. Descripción del algoritmo expuesto.
3.3. Ventajas e inconvenientes detectados.
3.4. Pruebas y resultados.
4. Algoritmo de búsqueda local ILS.
4.1. Objetivo.
4.2. Solución al problema propuesto.
4.3. Ventajas e inconvenientes detectados.
4.4. Pseudocódigo.
4.5. Pruebas y resultados.
5. Algoritmo de búsqueda local VNS.
5.1. Objetivo.
5.2. Solución al problema propuesto.
5.3. Ventajas e inconvenientes detectados.
5.4. Funcionamiento del Algoritmo y Pseudocódigo.
5.5. Pruebas y resultados.
6. Algoritmo MiniMax.
6.1. Objetivo.
6.2. Solución al problema propuesto y heurística elegida.
6.3. Ventajas e inconvenientes detectados.
6.4. Funcionamiento de Algoritmo y Pseudocódigo.
6.5. Pruebas y resultados.
7. Conclusión.
1. Introducción al contexto de la práctica.
Como breve introducción, se resaltan unas breves pinceladas sobre el trabajo realizado.
En primer lugar, se ha analizado y estudiado el algoritmo Hill Climbing que viene implementado en la práctica, con lo que hemos obtenido una serie de conclusiones.
Tras este estudio, se ha desarrollado e implementado dos técnicas metaheurísticas, como son el algoritmo de búsqueda local VNS (búsqueda en entornos variables) e un algoritmo ILS (búsqueda local iterada).
También se han implementado una seriede evaluadores, para probar partidas con distintas configuraciones. Para ello hemos modificado el número y tipo de fantasmas, la cantidad de vidas que dispone el Pacman, y el número de niveles máximos que acotan la duración de la partida, de tal forma que se nos facilita considerablemente la realización de pruebas para probar las implementaciones realizadas.
Estos algoritmos serán aplicados y utilizados para optimizar la partida de un PacMan, de forma que se realizarán multitud de simulaciones de juegos para conseguirlo.
También se ha implementado un jugador basado en el algoritmo MiniMax (Búsqueda con adversario), que implementa la clase ParameterizedPacmanPlayer, de manera que se le podrán pasar unos parámetros iniciales, para ser utilizados a la hora de realizar la evaluación en las hojas del árbol de búsqueda.
Por último se habla de las diferencias entre ambos algoritmos de búsqueda local implementados y obtenemos nuestra conclusión de la práctica.
2. Breve descripción de la estructura de la memoria.
A continuación se detalla la estructura que seguirá la presente memoria, para facilitar en la medida de lo posible su comprensión, en cada apartado aparecerá de forma aproximada el siguiente guión:
· Objetivo: Se comenta brevemente los que se quiere conseguir, y cuál es el algoritmo a desarrollar.
· Solución al problema propuesto: Es decir, cómo ha sido resuelto el problema desde un punto de vista conceptual y sin entrar en detalles de implementación.
· Ventajas e inconvenientes detectados: Antes y después del proceso de implementación.
· Funcionamiento del algoritmo y Pseudocódigo: Detalles sobre la implementación del algoritmo.
· Pruebas y resultados: Testeo del funcionamiento del algoritmo con el mayor detalle posible.
Además, en la descripción de los algoritmos se pretenderá utilizar una notación y un nivel de detalle que faciliten la comprensión de los mismos.
Así mismo, se denota la posibilidad de prescindir de aquellos puntos que no aporten nada al desarrollo de la memoria.
3. Estudio del algoritmo Hill Climbing.
3.1 Objetivos.
Tras analizar el código del algoritmo y ejecutarlo varias veces, se puede observar que se trata de un algoritmo simple de búsqueda local, más en concreto se trata de una Búsqueda por escalada o ascensión de colinas. Para una mejor comprensión de este, en los siguientes apartados se tratará de realizar una descripción lo más detallada posible de este.
3.2 Descripción del algoritmo.
Para ir desglosando poco a poco el problema expuesto, se comenzará a detallar el espacio de configuraciones usado en el algoritmo a estudiar. En esta ocasión, se dispone de un espacio de configuraciones formado por un vector c, con un tamaño fijo de 22 elementos. Donde cada posición representa un peso asociado a un parámetro del comecocos, como por ejemplo:
C = (p1, p2, p3,……, p22)
Donde cada peso tendrá un valor de entre 0.0 y 5.0, y en cada posición se hace correspondencia a un aspecto importante en el desarrollo del juego. Como por ejemplo, a los puntos que quedan en la pantalla, a la distancia existente entre el Pacman y los fantasmas, etc.
Se ha de mencionar, que la función de evaluación usada determina la puntuación que se obtiene con la configuración de pesos que se está valorando. Para así, posteriormente determinar cuál es la mejor configuración posible.
A continuación, se detallarán las partes importantes, que desde nuestro criterio tiene el algoritmo.
De forma general, es sencillo ver que el este dispone de tres partes importantes. Primeramente se genera un vecino x, de forma aleatoria, ofreciendo así una posible solución al problema propuesto.
Tras esto, y basándonos en esta primera configuración, comenzará a obtener nuevas soluciones, con nuevos individuos de la vecindad. En este punto se destaca, que para ello, se realiza una operación sencilla, que consiste en recorrer uno a uno los elementos del vector C, para así añadirles 1 si es mayor que 0, o restarles 1 si es mayor que cinco. En el siguiente ejemplo se puede observar de forma más clara.
[1.0,2.0,0.0,3.0,1.0,1.0,4.0,5.0,0.0,1.0,4.0…]
[0.0,1.0,0.0,3.0,1.0,1.0,4.0,5.0,0.0,1.0,4.0…] [0.0,3.0,0.0,3.0,1.0,1.0,4.0,5.0,0.0,1.0,4.0…] [0.0,2.0,1.0,3.0,1.0,1.0,4.0,5.0,0.0,1.0,4.0…] [0.0,2.0,0.0,2.0,1.0,1.0,4.0,5.0,0.0,1.0,4.0…]
[0.0,2.0,0.0,4.0,1.0,1.0,4.0,5.0,0.0,1.0,4.0…]
[0.0,2.0,0.0,3.0,0.0,1.0,4.0,5.0,0.0,1.0,4.0…]
Por último, vemos que se determina la mejor solución como aquella que consigue mejor puntuación, y que si en alguna iteración no se encuentra una solución que mejora la última encontrada hasta el momento. Se termina la ejecución del algoritmo.
3.3 Ventajas e Inconvenientes detectados.
Los principales problemas que se encuentran en este algoritmo son, como en todo algoritmo de búsqueda local, que es muy propenso a acabar en un óptimo local, una cresta o una meseta.
Debido a que no se ha realizado ninguna mejora sobre este algoritmo (como ILS, o la que hemos implementado VNS), es especialmente dependiente de la solución que se escoja como inicial.
Si bien, es cierto que siempre encentra una solución posible al problema, aunque esta no sea del todo óptima.
3.4 Pruebas y Resultados.
Hill Climbing
| ||||
Evaluador
|
Puntuación
|
Tiempo (s)
|
Nº Evaluaciones
| |
Evaluator1
|
Ejecución 1
|
19719
|
211
|
113
|
Ejecución 2
|
19559
|
143
|
75
| |
Ejecución 3
|
19134
|
86
|
76
| |
Valor Medio
|
19470
|
146
|
88
| |
Evaluator2
|
Ejecución 1
|
751
|
27
|
67
|
Ejecución 2
|
860
|
28
|
69
| |
Ejecución 3
|
2453
|
30
|
70
| |
Valor Medio
|
1354
|
28
|
68
| |
Evaluator3
|
Ejecución 1
|
1303
|
65
|
149
|
Ejecución 2
|
1019
|
31
|
72
| |
Ejecución 3
|
981
|
34
|
77
| |
Valor Medio
|
1101
|
43
|
99
| |
4. Algoritmo de búsqueda local ILS.
4.1 Objetivos.
Como objetivo principal en este apartado, se propone realizar la implementación de una búsqueda local, basado en Búsqueda Local Iterativa o ILS.
Posteriormente, se realizarán una serie de pruebas para determinar como de bueno o malo es el algoritmo desarrollado, y que ayude a posteriores comparaciones con otros algoritmos similares.
4.2 Solución al problema propuesto.
Para llevar a cabo la resolución del problema propuesto, tomamos la decisión de que el espacio de configuraciones a usar será exactamente el mismo que fue detallado en el punto 3.2 de la presente memoria.
Una vez establecido esto, se detalla que el algoritmo funciona exactamente igual que el anterior pero con algunos matices o variaciones.
Para ello se establece que cuando el algoritmo de ascensión de colinas no encuentre una solución mejor, no acabará la ejecución, si no que basándonos en la mejor solución encontrada hasta el momento, se realizará una perturbación en esta, y continuaremos iterando hasta volver a tener una solución que no mejora la anterior y volvamos a perturbar, haciendo esto hasta 3 veces en la ejecución del algoritmo.
La perturbación llevada a cabo, consiste en generar una nueva vecindad recorriendo uno a uno los pesos de la solución x, y estableciendo un número calculado de forma aleatoria entre 0.0 y 5.0 para todos aquellos pesos con posiciones pares.
Además, se establecerá la misma operación para todos los pesos impares con un índice en el vector de pesos mayor que 10.
Con esto, vemos que como antes el algoritmo tiene 3 partes importantes, añadiendo en esta ocasión, la generación de una nueva vecindad con la forma antes descrita, y el reinicio a partir de esta tras caer en un óptimo local.
4.3 Ventajas e Inconvenientes detectados.
La ventaja principal que se observa en este tipo de algoritmos es que evitamos mediante perturbaciones caer en un óptimo local. Así mismo vemos que, por lo general, se obtienen mejores puntuaciones que con el algoritmo detallado en el punto anterior.
Por el contrario, el tiempo de ejecución y el coste computacional aumenta sustancialmente en este tipo de algoritmos.
4.4 Pseudocódigo.
En este apartado, se describe el pseudocódigo desarrollado para adoptar la solución propuesta anteriormente. Se ha de destacar, que solo se expondrá el código relacionado exclusivamente con la implementación del algoritmo ILS, y por tanto, solo mostraremos el código que ha sido desarrollado por nosotros, obviando así el código que venía desarrollado en el algoritmo Hill Climbing.
La resolución del problema se desarrolla principalmente en la función “run ()”, donde se seleccionará y devolverá la configuración de pesos más apropiada. A continuación se describe esta función:
funcion double[] run() {
double[] currentSolucion = Calculamos la configuración inicial;
double bestScore = Calculamos La puntuacion de(currentSolucion)
Mostramos ambas cosas: Solucion + score.
… Todo esto es igual que para el Algoritmo de Ascención de Colinas.
Mientras ( tenga una solución mejor ) hacer
…Hill Climing.
If ( No tenemos una solución mejor && no se ha perturbado 3 veces)
Perturbamos a partir de la mejor solución hasta ahora, con la función à generateNuevaVecindad(mejorSolucion).
Calculamos su score.
Mostramos todo: Solución + Score.
Establecemos esta solución, como la encontrada, y continuamos con la ejecución como si estuviéramos en Hill Climbing.
Fin_si
Fin_mientras
Mostramos la solución Final, y su score.
Retornamos la solución Final.
}
Función generateNuevaVecindad(mejorSolucion){
NuevaSolucion[] = mejorSolucion[];
Para( i =0; i < Numero de pesos; i++) hacer
If ( i es par ) entonces
NuevaSolucion[i] = ramdom entre 0.0 y 5.0;
Fin_si
If ( i es impar y es mayor que 10 )
NuevaSolucion[i] = ramdom entre 0.0 y 5.0;
Fin_si
Fin_para
Retornamos NuevaSolucion;
}
4.5 Pruebas y Resultados.
Se han realizado tres ejecuciones por cada evaluador, usado examplePacmanPlayer, de manera que los resultados que analizaremos serán los correspondientes a la media de estas.
Los resultados que hemos obtenido se resumen en la siguiente tabla:
ILS
| ||||
Evaluador
|
Puntuación
|
Tiempo (s)
|
Nº Evaluaciones
| |
4 fantasmas tipo Basic
|
Ejecución 1
|
20119
|
313
|
252
|
Ejecución 2
|
19079
|
351
|
293
| |
Ejecución 3
|
20163
|
314
|
192
| |
Valor Medio
|
19787
|
326
|
246
| |
4 fantasmas tipo Stalking
|
Ejecución 1
|
1068
|
91
|
227
|
Ejecución 2
|
2449
|
99
|
221
| |
Ejecución 3
|
2459
|
113
|
224
| |
Valor Medio
|
1992
|
101
|
226
| |
2 Stalking y 2 Dave
|
Ejecución 1
|
4399
|
126
|
296
|
Ejecución 2
|
1796
|
71
|
183
| |
Ejecución 3
|
2360
|
102
|
230
| |
Valor Medio
|
2852
|
100
|
236
| |
5. Algoritmo de búsqueda local VNS.
5.1 Objetivos.
En el siguiente apartado se especifica paso a paso como se ha llevado a cabo la implementación del algoritmo de búsqueda local VNS, para solucionar los problemas encontrados en el algoritmo del punto anterior, tal y como se expone en el enunciado de la práctica.
5.2 Solución al problema propuesto.
Para llevar a cabo la resolución de este problema, seguiremos tomando el mismo espacio de configuraciones que en los dos puntos anteriores.
Quedando fijado lo anterior, diremos que el algoritmo de búsqueda local VNS, tiene un funcionamiento idéntico a los anteriores, a excepción de que cuando este no encuentra una solución que mejore a la actual, que en este caso aumentaríamos la amplitud de la vecindad y continuaríamos buscando hasta encontrar una solución mejor. En caso de encontrarla, la siguiente iteración se realizara con la amplitud de vecindad que teníamos inicialmente, pero si no encontramos una solución mejor, volveríamos a ampliar la vecindad.
En este algoritmo, solo ampliaremos la vecindad dos veces consecutivas, en caso de que no se obtenga una mejora de la solución, se devolverá la mejor solución obtenida en la ejecución.
Cada ampliación de vecindad, nos generara un número de vecinos que casi duplicará a los de la iteración anterior.
La forma de realizar los cambios en los individuos para conseguir nuevos vecinos consistirá en cambiar los dígitos de forma lineal, sumando o restando una unidad a las componentes, de forma que en una vecindad de nivel uno, se cambiaran cada uno de los dígitos del individuo. Si la vecindad es de nivel dos, se cambiarán los dígitos 0 y 1, después 1 y 2, después 2 y 3, y así sucesivamente. Para la vecindad de nivel tres también se realizarían así (0, 1 y 2, después 1,2 y 3, etc).
Con este sistema, se intentara obtener mejores soluciones que con los algoritmos anteriormente descritos, debido a que evitaremos quedarnos con una solución que meramente sea un óptimo local.
5.3 Ventajas e Inconvenientes detectados.
La principal ventaja es la de que este algoritmo intenta no terminar en óptimos locales ampliando la búsqueda a partir de una solución (la que tengamos en ese momento) prometedora. A pesar de esta mejora, también es cierto que los costes, sobre todo en tiempo, aumentan considerablemente, ya que al aumentar la vecindad, el número se individuos prácticamente se duplica.
Otro detalle que también hemos de remarcar es que, aunque el algoritmo encuentre el óptimo global del espacio de búsqueda en su primera iteración, éste no se dará cuenta hasta que explore la vecindad de nivel tres.
5.4 Funcionamiento del Algoritmo y Pseudocódigo.
El funcionamiento de este algoritmo es básicamente el que hemos visto en clase.
El algoritmo comienza su ejecución en la función run () generando aleatoriamente gracias a la función generateInitialSolution() de un individuo, tras esto se evalúa dicho individuo.
Con la solución inicial, nos introducimos en el bucle principal del algoritmo con la generación de la vecindad. De esto se encarga el método generateNeighbourhood(), que, de forma recursiva generará las vecindades, cambiando uno o más dígitos del individuo, sumando o restando una unidad. Se cambiarán uno o más dígitos dependiendo de la población requerida, de forma que se cambiarán un digito para población de nivel uno, dos dígitos para la de nivel dos, y tres dígitos para la de nivel tres.
El algoritmo parará en el momento en el que llegue a tener una solución que no ha sido capaz de mejorar después de explorar su vecindad hasta nivel tres. En este momento, el algoritmo parará y devolverá la solución encontrada.
La resolución del problema se desarrolla principalmente en la función “run ()”, donde se seleccionará y devolverá la configuración de pesos más apropiada. A continuación se describe esta función:
funciondouble[] run() {
double[] currentSolucion = Calculamos la configuración inicial;
int vecindad = 1;
doublebestScore = Calculamos La puntuacion de(currentSolucion)
Mostramos ambas cosas: Solucion + score.
… Todo esto es igual que para el Algoritmo de Ascensión de Colinas.
Mientras ( vecindad sea menor o igual que tres) hacer
…Hill Climing.
Si( No tenemos una solución mejor)
Obtenemos la nueva vecindad a partir de la mejor solución que tengamos hasta ahora, con la función àgeneraVecinos(mejorSolucion,vecindad,0).
Calculamos su score.
Mostramos todo: Solución + Score.
Establecemos esta solución, como la encontrada, y continuamos con la ejecución como si estuviéramos en Hill Climbing.
Aumentamos la variable vecindad.
Fin_si
Fin_mientras
Mostramos la solución Final, y su score.
Retornamos la solución Final.
}
Función generaVecinos(mejorSolucion,vecindad,i){
ArrayList<double[]> vecindad= new ArrayList<double[]>();
Si (vecindad es distinto de 0)
Si (La posición i de mejorSolucion es mayor que 0)
double[] NewSolution1 = mejorSolucion
Restamos uno a la componente i del vector NewSolution1
Añadimos el vecino al vector vecindad y llamamos a la función generaVecinos(NewSolution1,vecindad-1,i+1)
Fin_si
Si (La posición i de mejorSolucion es menor que 5) {
double[] NewSolution2 = mejorSolucion
Sumamos uno a la componente i del vector NewSolution1
Añadimos el vecino al vector vecindad y llamamos a la función generaVecinos(NewSolution1,vecindad-1,i+1)
Fin_si
Sino
Añades al vector vecindad mejorSolucion
Fin_si
Retornamos vecindad.
}
5.5 Pruebas y Resultados.
Con este algoritmo hemos realizado una serie de pruebas con distintos evaluadores. Estos evaluadores simularán partidas con 4 fantasmas tipo Basic, otro con 4 tipos Stalking, y otro con 2 Stalking y 2 Dave. Además existirá una limitación de diez niveles y el número de vidas del PacMan en cada uno de ellos será tres.
Se han realizado tres ejecuciones por cada evaluador, usado examplePacmanPlayer, de manera que los resultados que analizaremos serán los correspondientes a la media de estas.
Los resultados que hemos obtenido se resumen en la siguiente tabla:
VNS
| ||||
Evaluador
|
Puntuación
|
Tiempo (s)
|
Nº Evaluaciones
| |
4 fantasmas tipo Basic
|
Ejecución 1
|
20519
|
4011
|
503
|
Ejecución 2
|
20489
|
2921
|
275
| |
Ejecución 3
|
20539
|
2726
|
386
| |
Valor Medio
|
20516
|
3219
|
388
| |
4 fantasmas tipo Stalking
|
Ejecución 1
|
2447
|
1339
|
329
|
Ejecución 2
|
2447
|
1117
|
264
| |
Ejecución 3
|
2435
|
1126
|
266
| |
Valor Medio
|
2443
|
1194
|
286
| |
2 Stalking y 2 Dave
|
Ejecución 1
|
2444
|
139
|
202
|
Ejecución 2
|
4351
|
219
|
280
| |
Ejecución 3
|
2377
|
108
|
172
| |
Valor Medio
|
3057
|
155
|
218
| |
Se puede observar que según la media, el número de puntos obtenido es bajo, ya que cuando introducimos fantasmas distintos a los Basic, el jugador ExamplePacManPlayer no juega correctamente y el PacMan es cogido por los fantasmas rápidamente.
6. Algoritmo MiniMax.
6.1 Objetivos.
El objetivo principal en este apartado es desarrollar un agente de búsqueda basado en un algoritmo Minimax, para llevar a cabo la resolución de los puntos 4.3 y 4.4 de la práctica objeto de esta memoria.
6.2 Solución al problema propuesto y Heurística elegida.
A continuación se detalla, de forma puramente teórica, como se ha realizado la resolución del problema. En primer lugar se ha de mencionar que al tratarse de una Búsqueda con adversarios, primero se ha de identificar a estos. Con lo que, decidimos que el Pacman sea el jugador identificado como Max, y el fantasma más cercano a este será el jugador Min.
De esta forma, nuestro problema se reduce a determinar de entre los movimientos legales de los que dispone Pacman, cuál será el más apropiado para él, para posteriormente movernos en esa dirección.
Como heurística, establecerá que Max realice el movimiento que le aporta la mayor cantidad de score posible, siendo este determinado por su aporte y establecido en una configuración de pesos. Esta será de la siguiente forma:
Pesos = {3, // Puntos en pantalla
0, // Manhattan punto más cercano
0, // Manhattan fantasma más cercano
5, // Media Manhattan puntos
2, // Media Manhattan fantasmas
1, // Penalización por cabeceo
De forma contraria, Min escogerá el movimiento que haga que Pacman tenga menos score, pues esto es lo mejor para él.
Además, se realizan pruebas con el mismo algoritmo, pero con la configuración de pesos dada inicialmente, es decir 22 pesos, y como se puede ver en las pruebas posteriores, por lo general funciona bastante peor que con la configuración que proponemos.
Con esto, básicamente se trata de realizar un recorrido en profundidad por todos los estados, y escoger la mejor opción basándonos en los scores expuesto en las hojas de este árbol.
6.3 Ventajas e Inconvenientes detectados.
Las ventajas de este algoritmo, frente a un MiniMax sin parámetros, no son demasiadas, ya que no varía la funcionalidad del algoritmo en ambos casos.
Pero de esta manera, podemos realizar ejecuciones con algoritmos de optimización combinatoria, y obtener el mejor valor de los parámetros, evaluando los puntos que va obteniendo el PacMan en sus reiteradas ejecuciones.
Por otra parte, el valor de estos parámetros está muy restringido, ya que solo se toman valores de 0 a 5, y por tanto, no podemos probar gran parte de combinaciones posibles, que pudiesen dar mejores resultados en la ejecución del MiniMax.
6.4 Funcionamiento del Algoritmo y Pseudocódigo.
El funcionamiento interno del propio algoritmo es el siguiente: la función chooseMove(game) elegirá el movimiento que mejor puntuación tenga. Esta puntuación resultará tras generar los posibles movimientos del agente PacMan en ese estado y llamando a la función Max(state,int).
Una vez en la función Max, según el valor de la profundidad: si es cero, calculará y devolverá el valor del estado, según la función evaluateState(state) que a continuación comentaremos; y si es mayor que cero, listará los posibles movimientos del PacMan en ese estado, y tras esto llamará a la función Min(state,int) con una profundidad reducida en uno. La función Max en este caso devolverá el valor máximo de los que haya obtenido.
Cuando el algoritmo entre en la función Min realizará lo mismo que en Max, pero calculando los movimientos de los fantasmas (en vez del movimiento del PacMan) y devolverá el valor mínimo de entre los que ha obtenido.
De esta forma, el funcionamiento general consistirá en escoger el máximo valor de los estados cuando “mueve” el PacMan, y el valor mínimo de los estados en los que “se mueven” los fantasmas. Así obtendremos el movimiento que más nos convenga en función de que los fantasmas estén más lejos.
El pseudocódigo de las funciones Min y Max, sería el siguiente:
Ambas funciones tendrán como entradas el estado siguiente y la profundidad, y devolverán la puntuación correspondiente.
Max(State n, int prof){
double puntuación, inicializado a menos infinito.
Si( La profundidad es mayor que 0)
Si hemos ganado devolvemos 10000
Sino si hemos perdido devolvemos -10000
Sino
Obtenemos movimientos legales del estado n pasado
Mientras (queden movimientos legales por simular)
Obtenemos el estado siguiente
Llamamos a la función Min(nextState,prof-1)
Si la puntuación actual es menor que la devuelta por min, se actualiza la puntuación actual con el valor máximo.
Fin_si
Fin_mientras
Fin_si
Fin_si
Si (profundidad es 0)
Llamamos a evaluateState con el estado actual, y lo que nos devuelva lo guardamos en puntuación.
Fin_si
Devolvemos puntuación.
}
Max(State n, int prof){
double puntuación, inicializado a más infinito.
Si( La profundidad es mayor que 0)
Si hemos ganado devolvemos 10000
Sino si hemos perdido devolvemos -10000
Sino
Obtenemos movimientos legales del estado n pasado
Mientras (queden movimientos legales por simular)
Obtenemos el estado siguiente
Llamamos a la función Max(nextState,prof-1)
Si la puntuación actual es mayor que la devuelta por Max, se actualiza la puntuación actual con el valor mínimo.
Fin_si
Fin_mientras
Fin_si
Fin_si
Si (profundidad es 0)
Llamamos a evaluateState con el estado actual, y lo que nos devuelva lo guardamos en puntuación.
Fin_si
Devolvemos puntuación.
}
Las funciones chooseMove y evaluateState, son similares a las del examplePacmanPlayer.
6.5 Pruebas y Resultados.
MiniMax con ILS
| ||||
Evaluador
|
Puntuación
|
Tiempo (s)
|
Nº Evaluaciones
| |
4 fantasmas tipo Basic
|
Profundidad 3
|
17859
|
84
|
87
|
Profundidad 5
|
19559
|
327
|
79
| |
Profundidad 7
|
17973
|
1351
|
60
| |
Valor Medio
|
18464
|
587
|
75
| |
4 fantasmas tipo Stalking
|
Profundidad 3
|
1611
|
33
|
65
|
Profundidad 5
|
881
|
62
|
75
| |
Profundidad 7
|
778
|
149
|
66
| |
Valor Medio
|
1090
|
81
|
67
| |
2 Stalking y 2 Dave
|
Profundidad 3
|
1428
|
40
|
99
|
Profundidad 5
|
1422
|
84
|
86
| |
Profundidad 7
|
779
|
78
|
74
| |
Valor Medio
|
1210
|
67
|
86
| |
MiniMax con ILS, profundidad 3 y 22 componentes
| |||
Evaluador
|
Puntuación
|
Tiempo (s)
|
Nº Evaluaciones
|
4 fantasmas tipo Basic
|
1175
|
1072
|
267
|
4 fantasmas tipo Stalking
|
2447
|
1339
|
329
|
2 Stalking y 2 Dave
|
1773
|
260
|
250
|
MiniMax con VNS
| ||||
Evaluador
|
Puntuación
|
Tiempo (s)
|
Nº Evaluaciones
| |
4 fantasmas tipo Basic
|
Profundidad 3
|
17189
|
286
|
137
|
Profundidad 5
|
16580
|
685
|
126
| |
Profundidad 7
|
18159
|
4853
|
126
| |
Valor Medio
|
17309
|
1941
|
112
| |
4 fantasmas tipo Stalking
|
Profundidad 3
|
746
|
34
|
58
|
Profundidad 5
|
436
|
31
|
38
| |
Profundidad 7
|
1337
|
475
|
80
| |
Valor Medio
|
840
|
180
|
59
| |
2 Stalking y 2 Dave
|
Profundidad 3
|
1417
|
56
|
98
|
Profundidad 5
|
1270
|
94
|
76
| |
Profundidad 7
|
834
|
112
|
29
| |
Valor Medio
|
1174
|
87
|
68
| |
MiniMax con VNS, profundidad 3 y 22 componentes
| |||
Evaluador
|
Puntuación
|
Tiempo (s)
|
Nº Evaluaciones
|
4 fantasmas tipo Basic
|
7124
|
2909
|
704
|
4 fantasmas tipo Stalking
|
20494
|
1189
|
671
|
2 Stalking y 2 Dave
|
4448
|
762
|
495
|
7. Conclusión.
Tras el desarrollo de esta práctica se puede concretar que por lo general, si un algoritmo basado en Búsqueda por escalada es más eficiente, requerirá un mayor coste computacional.
Como podemos ver en los resultados obtenidos en las diferentes pruebas realizadas a cada tipo de algoritmo de búsqueda local (Hill Climbing, ILS y VNS), se observa que por lo general, el algoritmo Hill Climbing es el que menos puntuaciones obtiene como media, mientras que VNS obtiene muy buenas puntuaciones.
A la postre, vemos que VNS requerirá más tiempo de ejecución, y realizará un mayor número de evaluaciones. Estos resultados se pueden observar gráficamente en las siguientes gráficas comparativas.
Tras esto, podemos deducir que el algoritmo que más se ajusta con respecto a prestaciones, tiempo de ejecución y número de iteraciones es ILS, ya que es un término medio entre los tres.
Con respecto a MiniMax, observamos que tiene un mejor rendimiento cuando se usan la opción de ser parametrizado. Además vemos que funciona mejor con 6 parámetros que con 22. Suponemos que es debido a un tiempo computacional mayor con el de 22.
1 comentarios:
Muy bien explicado pero creo que hay un error en pseudocodigo de minimax, Dentro de max deberia llamar a la duncion min, y no otra vez a la max. Vamos eso lo entiendo al menos.
Publicar un comentario