Universidad Catolica

“Nuestra Senora de la Asuncion”

Sede Regional Asuncion

Facultad de Ciencias y Tecnologıa

Departamento de Ingenierıa

Electronica e Informatica

Carrera de Ingenierıa Informatica

Lenguajes de Programacion IIIng. Sergio Caceres

Ramırez, Pedro <pedroramirez22@gmail.com>

TRABAJO FINALCONECTA 4

26 de junio de 2015

INDICE 2

Indice

1. Objetivo del Juego 2

2. Reglas 2

3. Algoritmo Minimax 3

4. Tecnicas para mejorar Minimax 54.1. Poda Alfa-Beta . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

5. Funcion de Utilidad-Heurıstica 9

1. Objetivo del Juego

Dado un tablero de 6 filas por 7 columnas, el objetivo es formar una lıneahorizontal, vertical o diagonal de 4 fichas iguales. Aquel jugador que primero loconsiga gana el juego.

Para la descarga del juego implementado en lenguaje C, pulse aquı.

2. Reglas

El conecta 4 es un juego que involucra a un tablero, fichas y dos jugadores,que se rigen por las siguientes reglas

Casa jugador tiene 21 fichas, que se diferencian entre ellos por el color.

Una vez elegido quien inicia la partida, cada jugador realiza una jugadapor turno, sin posibilidad de saltar o pasar el turno.

Al inicio el tablero se encuentra en forma vertical y totalmente vacıo. Lasfichas se depositan siguiendo el sentido que marca la gravedad (de abajohacia arriba, conforme se vayan llenando casillas).

En su turno, el jugador deposita su ficha en algun lugar disponible deltablero en forma vertical, buscando distribuir las fichas de manera talque pueda formar una lınea de 4 fichas iguales, ya sea en forma vertical,horizontal o diagonal dentro del tablero.

El juego eventualmente puede terminar en un empate, que se da cuandoya no queden mas fichas ni espacios en el tablero, y ninguno de ellos haconseguido formar una lınea.

3 Algoritmo Minimax 3

3. Algoritmo Minimax

El algoritmo MiniMax es el algoritmo mas conocido (y utilizado) para prob-lemas con exactamente 2 adversarios, movimientos alternos (ahora tu ahorayo), e informacion perfecta.

Identificaremos a cada jugador como el jugador MAX y el jugador MIN.MAX sera el jugador que inicia el juego, el cual supondremos que somos nosotros,y nos marcaremos como objetivo encontrar el conjunto de movimientos queproporcionen la victoria a MAX (nosotros) independientemente de lo que hagael jugador MIN.

Etiquetar los jugadores como maximos y mınimos plasma perfectamente ladualidad de los objetivos de cada uno, ademas de que ası se puede contabilizarperfectamente como una situacion que mejora para un jugador hace que empe-ore para el otro. Matizar que no importa que jugador deseemos ser, pues bajonuestro punto de vista siempre calcularemos jugadas positivas a nuestro favory negativas para el oponente.

Y todo esto nos lleva a que por convenio una jugada vencedora del jugadorMAX (lo que vendrıa a ser un jaque mate) tendra valor infinito, y una jugadadel jugador MIN tendra valor menos infinito.

Debera existir para el juego a resolver una funcion de evaluacion heurısti-ca que devuelva valores elevados para indicar buenas situaciones, y valores neg-ativos para indicar situaciones favorables al oponente. Ahora ya podemos vercomo para cada movimiento conoceremos su valor numerico en funcion de sugrado de bondad, y podremos ser capaces de identificar nuestro mejor movimien-to.

Ademas de utilizar la anterior funcion heurıstica, usaremos una estrategiaDFS de profundidad limitada para explorar el conjunto de jugadas. Como esimposible hacer una exploracion exhaustiva de todas las jugadas, se hace unabusqueda limitada en profunidad. Significa que en lugar de estudiar todas lasposibles situaciones hasta el fin de la partida, se buscaran por ejemplo todaslas situaciones hasta de aquı 3 turnos. Aunque esto limitara lo que veamos delespacio de busqueda, y quizas nos incitara a realizar unas jugadas que a lalarga sean nefastas. La calidad de nuestras jugadas vendra determinada por laprofundidad a la que lleguemos en cada exploracion. Cuanto mas profunda sea,mejor jugaremos, pero mayor coste tendra el algoritmo.

3 Algoritmo Minimax 4

Por lo tanto, situados todos los elementos del algoritmo, veamos como esMiniMax:

Funcion MiniMax(estado) retorna movimiento

mejor_mov: movimiento;

max, max_actual: entero;

max = -infinito;

para cada mov en movimientos_posibles(estado) hacer

max_actual = valorMin(aplicar(mov, estado);

si max_actual > max entonces

max = max_actual;

mejor_mov = mov;

fsi

fpara

retorna mejor_mov;

fFuncion

Funcion valorMax(estado) retorna entero

valor_max:entero;

si estado_terminal(estado) entonces

retorna evaluacion(estado);

sino

valor_max := -infinito;

para cada mov en movimientos_posibles(estado) hacer

valor_max := max(valor_max, valorMin(aplicar(mov, estado));

fpara

retorna valor_max;

fsi

fFuncion

Funcion valorMin(estado) retorna entero

valor_min:entero;

si estado_terminal(estado) entonces

retorna evaluacion(estado);

sino

valor_min := +infinito;

para cada mov en movimientos_posibles(estado) hacer

valor_min := min(valor_min, valorMax(aplicar(mov, estado));

fpara

retorna valor_min;

fsi

fFuncion

El algoritmo tiene una funcion principal (MiniMax) que sera la que se usara,y la que nos devolvera la mejor realizable, y dos funciones recursivas mutuas

4 Tecnicas para mejorar Minimax 5

(valorMax y valorMin) que determinan el valor de las jugadas dependiendo desi es el turno de MAX o de MIN. De este modo cada nivel elegira el valor quepropaga a su ascendiente dependiendo de que jugador es. En los niveles de MAXse elegira el valor mayor de todos los descendientes, y en los niveles de MIN seelegira el menor. Tras esto la maquina supone que todo jugador elige siempresu mejor jugada, cosa que no siempre sera.

La funcion estado terminal determina si el estado actual es una solucion opertenece al nivel maximo de exploracion. La funcion evaluacion calcula el valorheurıstico del estado.

Pero esta version, aunque sea sencilla, no es la mas inteligente a la hora detratar juegos bipersonales. Por eso al algoritmo MiniMax se le pueden efectuaruna serie de tecnicas para mejorarlo, buscando siempre una decision mas seguradel movimiento, y un tiempo de calculo menor.

4. Tecnicas para mejorar Minimax

Pero MiniMax puede ser mucho mas inteligente de lo anteriormente expuesto.Veamos que tipo de mejoras pueden aplicarsele.

4.1. Poda Alfa-Beta

Un punto clave que hemos de tener en cuenta es que cuanto mas profundasea la exploracion, mejor podremos tomar la decision sobre que jugada debemosescoger.

Para juegos con un factor de ramificacion elevado, esta profundidad no po-dra ser muy grande, ya que el calculo necesario para cada decision sera pro-hibitivo. Su tiempo de exploracion sera prohibitivo.

Para reducir este tiempo se han estudiado los arboles de busqueda, y se hallegado a la conclusion de que es muy factible usar heurısticos con poda. Enotras palabras, una tecnica de ramificacion y poda (branch and bound) conla cual una solucion parcial se abandonara cuando se compruebe que es peorque otra solucion ya conocida.

La estrategia denominada alfa-beta aprovecha que el algoritmo del MiniMaxhace una exploracion en profundidad para guardar informacion sobre cual es elvalor de las mejores jugadas encontradas para cada jugador.

Concretamente guarda dos valores, denominados umbrales alfa y beta (deahı el nombre del heurıstico).

El valor alfa representa la cota inferior del valor que puede asignarse enultimo termino a un nodo maximizante, y analogamente el valor beta represen-tara la cota superior del valor que puede asignarse como ultima opcion en unnodo minimizante.

4.1 Poda Alfa-Beta 6

De esta manera el algoritmo podra acotar el valor de una exploracion, puesgracias a los umbrales alfa y beta conocera si vale la pena explorar un caminoo no, como se ve en la Figura 1.

Figura 1: Ejemplo de Poda Alfa-Beta

En el arbol superior podemos ver que el valor que propagarıa MiniMax alnodo raız serıa 8. Pero si nos fijamos en el nodo marcado, en el segundo de-scendiente de la raız ya sabe que el mejor nodo del primer descendiente tienevalor 8. Puesto que el desdendiente es un nodo Min, y se ha encontrado pordebajo un valor de 6, el algoritmo interpretara que por ese camino como mejorresultado habra ese 6 (pues el nodo inferior elegira o el 6 o algo inferior). Comoya conocemos el posible 8, todos los nodos que cuelgan del Min que elegirıa el 6ya no hace falta explorarlos, pues seguro que ahı no se encuentra nuestra mejorjugada. En este momento se realizarıa la poda de esa rama e irıa a explorar eltercer posible camino.

Podemos observar tambien que esta circunstancia se repetira en el tercerdescendiente al explorar su ultimo nodo, pero al no quedar mas descendientes lapoda no nos ahorrarıa nada. Significa que la efectividad de esta heurıstica depen-dera del orden de los nodos, pues cuanto antes encuentres un valor penalizadopor el umbral, antes podras podar la rama.

Esta heurıstica modifica el algoritmo del minimax introduciendo dos paramet-ros en las llamadas de las funciones, alfa y beta, y representaran el lımite delvalor que pueden tomar las jugadas que exploramos. Una vez superado ese lımitesabremos que podemos parar la exploracion porque ya tenemos el valor de lamejor jugada accesible.

4.1 Poda Alfa-Beta 7

La funcion MiniMax se mantiene igual. Solo varıan las funciones que hacenla exploracion de cada nivel, el codigo de las cuales serıa el siguiente:

funcion valorMax( g , alfa , beta ) retorna entero

si estado_terminal( g ) entonces

retorna ( evaluacion( g ) )

sino

para cada mov en movs_posibles( g ) hacer

alfa:=max( alfa , valorMin( aplicar(mov, g ), alfa, beta ) )

si alfa >= beta entonces

retorna ( beta )

fsi

fpara

retorna ( alfa )

fsi

ffuncion

funcion valorMin( g , alfa , beta ) retorna entero

si estado_terminal( g ) entonces

retorna ( evaluacion( g ) )

sino

para cada mov en movs_posibles( g ) hacer

beta:=min( beta , valorMax( aplicar (mov, g ), alfa, beta ) );

si alfa >= beta entonces

retorna ( alfa )

fsi

fpara

retorna ( beta )

fsi

ffuncion

La llamada que hara la funcion MiniMax a la funcion valorMax le pasara ?in-finito como valor de alfa y +infinito como valor de beta (pues al no conocerseningun valor es imposible marcar un umbral predefinido).

4.1 Poda Alfa-Beta 8

En la Figura 2 se ve como explorarıa el algoritmo de MiniMax con poda alfabeta el ejemplo anterior:

Figura 2: Ejemplo de Poda Alfa-Beta

En conclusion, con poda alfa beta podremos ampliar el lımite de profundidadde nuestra exploracion, ya que con las podas nos ahorramos la exploracion devarias parte del arbol de busqueda, llegandonos a ahorrar ası multiples niveles.De ahı deriva que algunas de las siguientes ampliaciones se basen en mejorar elcomportamiento de la poda alfa-beta.

5 Funcion de Utilidad-Heurıstica 9

5. Funcion de Utilidad-Heurıstica

int heuristica(int tablero[FILAS][COLUMNAS], int jugador)

{

if(verifica_ganador(tablero, jugador))

{

if(jugador == CPU)

return MAX_VALUE;

else

return MIN_VALUE;

}

return costo(MAX)-costo(MIN);

}

Si la jugada actual logro hacer ganar a CPU (computadora) la funcion deutilidad regresa 10000 siendo el maximo valor posible en el juego, si quien ganaen la tirada es el rival (humano) retornara -10000 siendo el mınimo valor posibleen el juego.

En caso contrario que ninguno haya ganado. La funcion heurıstica retornarael valor calculado de acuerdo a la siguiente evaluacion

h(n) = costo(MAX) − costo(MIN)

Donde costo(MAX) es el numero total de lıneas posibles que tiene el jugadorMAX para ganar (CPU). costo(MIN) es el numero total de lıneas posibles quetiene el jugador MIN para ganar (humano). n es el estado actual en el tablero.

Si el jugador MAX (CPU) tiene ventaja sobre MIN, el valor retornado espositivo puesto que el numero de lıneas sera mayor a MIN.

Si el jugador MIN (humano) tiene ventaja sobre MAX, el valor retornadosera negativo puesto que el numero de lınea sera mayor a MAX.

Con dicha evaluacion si humano tiene ventaja en el tiro sobre cpu, la funcionvalorMin tomara esa jugada y MAX se encargara de evitarla.