TOPICO: Inteligencia Artificial: Proyecto 1º Unidad: "Juego Mancala"

MANCALA

A continuación veamos las características del juego en sí que implementamos, es decir algo de su historia, sus reglas del juego; luego continuaremos mencionando los algoritmos empleados.

Historia Mancala. Mancala es el nombre de una familia de juegos de tablero muy extendidos por toda África. Este juego se practicaba ya en el antiguo Egipto, pues se han encontrado tableros en la pirámide de Keops, y de allí debió extenderse a otros países de África y Asia.
Forma parte desde tiempos muy remotos de la tradición cultural de muchos pueblos y tribus, principalmente de África, y su práctica ha estado ligada a diferentes hechos, como a ritos funerarios, con motivo de mantener entretenido al espíritu del difunto; a ceremonias nupciales, para asegurar la fertilidad de la unión; y además, en casi todos los pueblos ha sido objeto de adivinación. Hoy, sin embargo, se juega sobre todo por placer y se ha convertido en el juego nacional de muchos países africanos, donde es conocido bajo diversas denominaciones, conociéndose casi doscientas variantes del juego, aunque todas ellas poseen características comunes.

Las versiones de Mancala más comunes en Europa, son el Awale (también llamado Wari), el Kakua, el Mweso o Hus (que se juega con 64 fichas en un tablero de 32 huecos), el Oware, que es una de las variantes más sencilla, y el Kalah, Kalaha o conocido simplemente como Mancala, que es la variante egipcia, la más extendida y conocida en Occidente, y es la implementada en este proyecto.

Reglas de Juego. Bueno como ya mencionamos, El Mancala se juega en un tablero que contiene dos filas de seis huecos o hoyos en cada una, y dos huecos especiales o Mancalas situados en ambos lados del tablero. Al comienzo del juego, todos los hoyos han de tener el mismo número de fichas, y los Mancalas de ambos jugadores han de estar vacíos.
Para comenzar a jugar, los jugadores se sitúan uno frente al otro, dominando el lado del tablero que se encuentra más próximo y el Mancala que se encuentra situado a su derecha, véase Figura 1.

El objetivo del juego es introducir el mayor número de fichas en el propio Mancala. Ganará el jugador que, al término del juego, tenga más de la mitad de las fichas en su Mancala (nuestro caso seria 25 el minimo mayor de la mitad ya que tenemos 48 fichas en total).

Las reglas para los movimientos a realizar son:

Un movimiento consiste en coger todas las fichas del hoyo en el lado del jugador, e ir en contra de las agujas del reloj poniendo una ficha en cada hoyo hasta q no haya nada. Se puede dar el caso q el jugador ponga una ficha en su mancala pero no se puede dar el caso q la ponga en la mancala de su oponente, en este caso saltara al siguiente hoyo, véase Figura 2. Así mismo si fuese a dar más de una vuelta al tablero, no deberá depositar una ficha en el hoyo donde inició.

Cuando en un movimiento, la última ficha se deposita en el Mancala del jugador al que pertenece el turno de juego, este jugador tendrá un turno extra. Pero si la última ficha de un movimiento cae en cualquier hoyo, tanto propio como del adversario, el siguiente turno será del jugador contrario, véase Figura 3.

Cuando en un movimiento, la última ficha se deposita en un hoyo vacío del jugador que mueve, se produce una captura. El jugador tomará las fichas que se encuentren en el hoyo de su adversario situado justo enfrente y las colocará, junto a la suya, en su Mancala, véase Figura 4. El turno tras la captura será del jugador contrario.

En el momento en que todos los hoyos de un jugador estén vacíos se llega a la situación de fin de juego. El jugador contrario, depositará en su Mancala todas las fichas almacenadas en sus hoyos, véase Figura 5. Ganará el juego el jugador que haya almacenado más fichas en su Mancala.

Algoritmos Utilizados

A continuación describimos el Algoritmo Minimax con Poda Alfa-Beta desarrollado y la función evaluación utilizada con la Heurística y Programación Genética.

Algoritmo Minimax con Poda Alfa-Beta. En el desarrollo de los juegos de dos jugadores, a uno se le denominará MAX y al otro MIN, cada uno con su turno correspondiente
Esta búsqueda realizada se puede definir en base a: un Estado Inicial, Movimientos Posible o Legales (Sucesores, luego de aplicar la Función Sucesor), un Estado Final, Valor o Función de Utilidad; los mismos que a su vez vienen a definir un árbol de juego y donde se desarrollará primero una búsqueda en profundidad, para nuestro caso profundidad limitada.

Usualmente se puede decir en una Búsqueda cualquiera, la estrategia óptima se logra alcanzar cuando tras un conjunto de movimientos posibles se llega a la meta u objetivo que viene a ser el estado ganador; sin embargo, la estrategia óptima que aquí hablamos no va por ese camino, sino mas bien consideramos que tras la realización de una jugada MAX, viene una jugada MIN y tras la misma viene otra MAX y puede ser vista en el árbol de juego (generado dado una cierta profundidad), evaluando la función del Valor Mínimax en cada nodo.

Existe un problema en el Algoritmo Minimax, el cual tiene que ver con la complejidad del mismo, ya que el número de estados a examinar o evaluar es exponencial en el número de movimientos. Sin embargo aunque este exponente no se pueda eliminar, existe una posibilidad de reducirlo a la mitad, y esto mediante la realización de una Poda al árbol Minimax, en nuestro caso: Poda Alfa-Beta, donde Alfa y Beta representan, respectivamente, las cotas inferior y superior de los valores que se van a ir buscando en la parte del subárbol que queda por explorar. Si Alfa llega a superar o igualar a Beta, entonces no será necesario seguir analizando las ramas del subárbol.

Entonces nuestro algoritmo del Minimax con poda Alfa Beta aplicado a nuestro juego Mancala (considerando el doble turno), queda:

Algoritmo MINIMAX-A-B
Entrada: nodoJuego (Mancala), Profundidad, turnoPC, Alfa (inicialmente -inf), Beta (inicialmente +inf)
Salida: el nodo (Mancala) a Jugar

1. Si el estado del nodoJuego es un final (Juego Terminado) o la profundidad de análisis restante es cero,
    1.1. Devolver nodoJuego cuyo valor sea el valor calculado mediante la función de Evaluación respectiva.
    1.2. En caso contrario, hacer
          1.2.1 Calcular los SUCESORES del nodoJuego
          1.2.2 Si la lista de SUCESORES es vacía
                1.2.2.1 Devolver nodoJuego cuyo valor sea el valor calculado mediante la función de Evaluación respectiva.
               1.2.2.2 En caso contrario, si el jugador del nodoJuego es MAX
                      1.2.2.2.1 Devolver el nodo de la lista de SUCESORES obtenido con la función MAXIMIZADOR-A-B
                      1.2.2.2.2 Sino Devolver el nodo de la lista de SUCESORES obtenido con la función MINIMIZADOR-A-B

Veamos sólo la función MAXIMIZADOR-A-B, ya que el otro es similar, solo que para los casos donde se consideran a Alfa, en el otro se consideran a Beta.

Algoritmo MAXIMIZADOR-A-B
Entrada: Sucesores a evaluar, Profundidad, Alfa, Beta
Salida: el nodo (Mancala) a Jugar Máximo

1. Crear las siguientes variables locales
     1.1. MEJOR-SUCESOR (para almacenar el mejor sucesor encontrado hasta el momento o el sucesor por defecto en caso de no encontrar ninguno que mejore la cota ALFA), cuyo valor es el primer elemento de la lista de SUCESORES
     1.2. VALOR (para almacenar el mejor valor encontrado hasta el momento), cuyo valor inicial es 0.
2. Para todo SUCESOR de la lista de SUCESORES hacer
     2.1. Calcular el VALOR minimax-a-b de SUCESOR, disminuyendo en 1 la profundidad de análisis y utilizando los valores de ALFA y BETA.
     2.2. Cuando el VALOR calculado sea mayor que ALFA, hacer
             2.2.1 Actualizar ALFA, que pasa a ser VALOR
             2.2.2 Actualizar el MEJOR-SUCESOR, que pasa a ser SUCESOR
     2.3. Cuando el valor de ALFA supere o iguale al de BETA, terminar el bucle: se ha producido un corte alfa.
3. Poner ALFA como valor del MEJOR-SUCESOR.
4. Devolver el MEJOR-SUCESOR.

Función de Evaluación. Tenemos para la función de evaluación dos formas de hallarla:

F1: Ser Ganador del Juego = 500 puntos.
F2: Puntos a Favor
Heurística=F1+10*F2
Heurística Total= Heurística a favor – Heurística del oponente

Programación Genética
La Programación Genética es parecida a los algoritmos genéticos con algunas variaciones como por ejemplo:

Los cromosomas ya no son cadenas de 1’s y 0’s en este caso son árboles que representan programas, ver figura 6.

El operador de mutación viene dado de la siguiente manera, seleccionar un subárbol, borrarlo y crear un subárbol aleatorio.
El operador de cruzamiento consiste dado 2 árboles, seleccionar 2 subárboles aleatoriamente e intercambiarlos.

En el caso de nuestro programa hemos usado las siguientes funciones:

Si _ <>
Resta
Adición
valorDe _: Calcula el valor de un depósito dada una posición.
Nuestro conjunto de terminales esta compuesto de números entre 0 y 13.

Implementación

Implementamos el juego Mancala, para un jugador (jugador 1 ó A y PC jugador 2 ó B) como para 2 Jugadores, y bajo la siguiente estructura de Juego:

Bueno el de 2 jugadores no tiene nada de interesante ya que ahí interactúan sólo dos personas, sin embargo, para el caso de 1 jugador, éste tendrá a la “máquina” como contrincante, siendo la persona el que inicie la jugada (jugador 1). Bueno aquí tenemos luego opciones de jugar por niveles, es decir nivel Principiante, Intermedio, Avanzado, y tenemos la opción de Programa Genético.

Para el caso de escoger cualquiera de los 3 niveles, se enfrentarán a la máquina, la misma que utilizará el algoritmo Minimax con Poda Alfa-Beta (donde el factor de ramificación máximo es 6), a profundidades: 2 (para Principiantes), 4 (para Intermedio), 6 (para Avanzado), y utilizará como función de evaluación la heurística ya definida por nosotros (que fue ya mencionada con anterioridad).

Para el caso de escoger Programa Genético, la máquina utilizará un programa genético creado luego de ejecutar Programación Genética vs Poda Alfa-Beta, donde tenemos a la probabilidad de mutación de 0.01, probabilidad de cruzamiento de 0.9, tamaño de población igual a 10, y para el caso de Poda Alfa-Beta profundidad 6.

A continuamos veamos como se ejecuta el juego: Para ellos empieza el jugador 1, es decir nosotros,

Entonces escogemos mover las fichas de la posición 2 (según nuestra estructura de juego ya mostrada),

Vemos que nos toca realizar otra jugada dada por la regla del turno extra, entonces escogemos mover las fichas de la posición 1, y vemos como inmediatamente la máquina también ejecuta su jugada y nos toca ya otra vez jugar a nosotros: