Integrales definidas

Módulo 3: Conecta-4 (avanzado)

Introducción
Esta tercera entrega consiste en programar un jugador avanzado de Conecta-4 que optimice su estrategia de juego, utilizando el algoritmo Minimax.
El resultado será similar a este jugador de Conecta -Cuatro.
El jugador que implementes entrará en competición con los jugadores de tus compañeros. La tabla de clasificación (ver enlace en la sección de"entregas") se actualizará cada poco tiempo con las entregas más recientes. Los mejores jugadores serán recompensados en la nota final.
Algoritmo Minimax
El algoritmo Minimax es un método de decisión que se utiliza en juegos con adversario, que consiste en calcular la jugada que me produce una mayor ganancia, suponiendo que mi contrincante va a realizar la jugada que le produzca a él una mayorganancia (o sea, que me produzca a mí una mayor pérdida). Minimax se implementa como un algoritmo de búsqueda en profundidad en árboles.
Minimax es muy empleado en áreas como la teoría de juegos, la teoría de la decisión, la estadística y la filosofía para analizar la toma de decisiones en presencia de incertidumbre. En los juegos de suma cero, Minimax es una solución óptima porque alcanzael equilibrio de Nash (¿recuerdas la película "Una mente maravillosa" que ganó 4 Óscars en 2001?).
La idea consiste en comenzar en el estado actual del juego, y generar un árbol con todas las posibles jugadas mías y de mi oponente, hasta un nivel de profundidad determinado. La siguiente figura muestra un ejemplo de árbol minimax con el juego de las Tres-En-Raya. El primer nivel es mi primera jugada, elsegundo nivel es la respuesta de mi adversario, el tercer nivel es mi respuesta a su respuesta... y así sucesivamente, hasta llegar a un nodo terminal (fin de partida).

A continuación se aplica una función de evaluación a cada uno de los nodos del árbol y se elige aquel nodo que obtenga la mejor evaluación para el jugador. La función de evaluación debe devolver valores positivos cuando el estadodel juego es ventajoso para el jugador y valores negativos cuando es ventajoso para el oponente.
Por ejemplo, para las Tres-En-Raya, una posible función de evaluación podría ser:
f() = (nº de líneas abiertas para MAX)-(nº de líneas abiertas para MIN)

Luego se lleva el mejor valor obtenido un nivel arriba en el árbol, continuando la evaluación de formarecursiva hasta llegar al nivel superior que indicará la jugada óptima a realizar.
Por ejemplo, en la siguiente figura, el valor de la función de evaluación para la jugada en la esquina inferior derecha sería 5 líneas abiertas para MAX (las X) menos 6 líneas abiertas para MIN (los O), en total -1. En esta misma figura, la jugada óptima, por tanto, sería la que conduce al estado mejor evaluado (el demás arriba, con valor de 2), esto es, empezar en el centro, que intuitivamente es lo más razonable.

El nombre del algoritmo deriva de considerar que el jugador trata de maximizar el valor de la función de evaluación en sus jugadas, mientras que intenta minimizar el valor de la función de evaluación en las jugadas del contrario. Es decir, Minimax puede resumirse como elegir mejor movimiento paratí mismo (max) suponiendo que tu contrincante escogerá el peor para tí (min).
En el siguiente ejemplo [Fuente: Wikipedia] puede verse el funcionamiento de Minimax en un árbol generado para un juego imaginario. Los movimientos MAX se corresponden con uno de nuestros movimientos. Los movimientos MIN se corresponden con un movimiento de nuestro contrincante. Los nodos terminales se corresponden conun movimiento que lleva al final del juego y por tanto a una puntuación.
El primer paso será calcular los nodos terminales, en verde, aplicando la función de evaluación del estado. Posteriormente calcularemos el cuarto nivel, movimiento MIN, minimizando el valor de la función de evaluación (es decir, cogiendo los mínimos: 5, 2 y 1). Después podremos calcular el tercer nivel, movimiento MAX,...