Tica

Conceptos Necesarios
Debemos tener en cuenta los siguientes conceptos para poder desarrollar la aplicación:
• Estado Inicial: Incluye la posición del tablero, e identifica al jugador que mueve.
• Función Sucesor: Devuelve una lista de pares (movimiento, estado), indicando un movimiento legal y el estado que resulta.
• Test Terminal: Determina cuando se termina el juego, detectando si unestado es terminal o no.
• Función de Utilidad: Le da un valor numérico a los estados terminales. En este caso tendremos +1 para el ganador, -1 para el perdedor y 0 si es empate.

Algoritmo Minimax
Ahora para entender el algoritmo minimax veamos la siguiente imagen: Tenemos 2 jugadores MAX y MIN, los valores altos son buenos para MAX (y malos para MIN) y los bajos buenos para MIN (y malos paraMAX), los nodos de la última fila son estados terminales. Ahora dado el estado inicial, y asumiendo que MAX inicia el juego, ¿Qué decisión tomar? Minimax asume que tanto MAX como MIN juegan de forma óptima o sea, si MAX juega por B, MIN opta por b1 (3, menor valor), si juega por C, MIN opta por c1 (2), si juega por D, MIN opta por d3 (2), estos valores se convierten en los valores minimax de B,C y D. Entonces MAX toma una decisión también óptima y elige B (mayor valor).

Si el árbol tiene más niveles, la técnica explicada se extiende dando lugar a un algoritmo recursivo. Minimax va desde las hojas hasta la raíz para poder obtener el valor de utilidad de los estados superiores.
Poda Alfa-Beta
Como podemos deducir de la explicación anterior es necesaria realizar una búsqueda sobretodo el árbol del espacio de estados. Se puede realizar una mejora al algoritmo minimax utilizando un criterio mostrado en la siguiente figura:

En la figura c) se está calculando el valor minimax para el nodo B, o sea el mínimo de sus hijos, luego de obtener 3, 12 y 8 se escoge 3 como el valor minimax de B. El nodo A puede tomar ventaja de este valor ya calculado: Dado que él quiere valoresmayores sólo le interesan valores mayores a 3 de ahora en adelante (en C o en D). Cuando de calcula el valor minimax de C (figura d), obtenemos en el primer hijo el valor de 2, y como éste es un nodo MIN se buscará valores menores a 2 en los demás hijos, es decir hasta el momento C a lo mucho será 2, pero A es como mínimo 3 (por el nodo B), por lo que no es necesario realizar el resto de búsquedaen los hijos de C y podamos esa rama.

Implementación en Prolog
Dados los conceptos necesarios, procederemos a implementar el juego Tres en Raya en Prolog. Utilizaremos una lista de listas (matriz) para representar el tablero, y un valor J=1 para el jugador MAX y J=-1 para el jugador MIN, el tablero estará inicialmente lleno de ceros, cuando juegue MAX, marcará 1 en el tablero y cuando juegueMIN marcará -1 en el tablero. Explicaré los principales predicados del programa:

Predicados para generar la lista de estados siguientes
Tenemos que a partir de una matriz bidimensional generar los demás estados posibles, mi razonamiento fue obtener las coordenadas de la matriz con valor cero, e ir marcando la matriz original con el valor 1 o -1 para generar cada uno de los estadossiguientes e ir almacenando los estados siguientes en una lista.

Aquí explico que hace cada predicado:
- marcarLista: Recibe una lista, una posición, un valor a marcar y devuelve una nueva lista con el valor marcado en la posición dada, por ejm.:
marcarLista([1,0,0,0],3,2,L). Devuelve:
L = [1, 0, 2, 0].

- marcarTablero: Recibe una matriz (lista de listas), un numero de fila, un numero decolumna, el valor,y devuelve la matriz con el valor marcado, por ejm.:
marcarTablero([[1,0,0,0],[0,0,0,0],[0,0,0,0]],2,3,1,M). Devuelve:
M = [[1, 0, 0, 0], [0, 0, 1, 0], [0, 0, 0, 0]].

- getPuntosLista: Recibe una lista, un numero de fila, un numero de columna inicial (1), y devuelve las coordenadas de de los valores ceros en la lista, este predicado lo utiliza getPuntos tablero, por ejemplo:...