JUEGO DEL MICHI (TRES EN RAYA)

Cada jugador coloca alternativamente una ficha en una matriz de 3x3.

Un jugador usa cruces (X) para indicar sus movimientos, el otro utiliza círculos (O).

Gana el jugador que completa primero una fila, columna o diagonal con sus fichas

Supóngase que: MAX → X MIN→ O

Primer movimiento: MAX

Profundidad límite: 2 niveles

Búsqueda en amplitud hasta generar todos los nodos del segundo nivel

Aplicar función de evaluación (estática) a las posiciones generadas por dichos nodos

Función de evaluación propuesta:

f(p) = (Nº filas, columnas y diagonales completas que todavía están libres para MAX) – (Nº filas, columnas y diagonales completas que todavía están libres para MIN)

Si p es una posición ganadora para MAX entonces: f(p) = ∞

Si p es una posición ganadora para MIN entonces: f(p) = - ∞

Si p representa la posición f(p) = 6 – 4 = 2

Para esta posición: f(p) = 6 – 6 = 0

Se puede utilizar las simetrías del juego para generar las posiciones sucesoras.

Jugada de MAX

- Propagar hacia el nodo raíz el valor máximo

- Escoger la jugada asociada al máximo valor de f(p) en los nodos del nivel 1

- Propagar los valores mínimos hacia atrás (al nivel 1)

- Obtener los mínimos en nivel 2 para cada posible jugada de MIN

- Calcular valores de f(p) para nodos del nivel 2

- Generar sucesores hasta nivel 2.

Según el árbol obtenido, el movimiento que tiene que hacer MAX es:

Presenta el mayor valor de propagación.

Asumamos que MIN responde con la siguiente jugada

MAX vuelve a aplicar búsqueda en amplitud a dicha posición, con profundidad límite de 2.

De las dos posibles jugadas de MAX se escoge:

MIN responde con el único movimiento que evita su derrota:

MAX vuelve a aplicar el proceso de búsqueda obteniendo:

Algunos nodos hoja del árbol representan victorias para MIN, por ello se evalúan a - ∞

Al propagar hacia atrás los valores, se obtiene que la mejor jugada para MAX es justamente la que evita su derrota

Supongamos que nodos hoja se evalúan al mismo tiempo que se generan.

Una vez evaluado el nodo A no se requiere generar (ni evaluar) los nodos B, C, D porque MIN tiene valor de - ∞

CODIGO EN LISP

Variables globales:

(defvar *estado-inicial*)

(defvar *movimientos*)

Generador de juegos:

(defun inicializa-3-en-raya (ficha)

(crea-estado-inicial ficha)

(list '3-en-raya. 'Empieza ficha))

Representación de estados:

(defstruct (estado (:constructor crea-estado)

(:conc-name nil)

(:print-function escribe-estado))

tablero

ficha)

Escritura de estados:

(defun escribe-estado (estado &optional (canal t) profundidad)

(let ((tablero (tablero estado)))

(format t "%d d d 0 1 2%d d d 3 4 5%d d d 6 7 8%"� � � � � � � � � � � � �

(or (nth 0 tablero) ".")

(or (nth 1 tablero) ".")

(or (nth 2 tablero) ".")

(or (nth 3 tablero) ".")

(or (nth 4 tablero) ".")

(or (nth 5 tablero) ".")

(or (nth 6 tablero) ".")

(or (nth 7 tablero) ".")

(or (nth 8 tablero) "."))))

Estado inicial:

(defun crea-estado-inicial (ficha)

(setf *estado-inicial*

(crea-estado :tablero '(nil nil nil nil nil nil nil nil nil)

:ficha ficha)))

Estados finales:

(defun es-estado-final (estado)

(or (es-estado-completo estado)

(tiene-linea-ganadora estado)))

(defun es-estado-completo (estado)

(not (position nil (tablero estado))))

Estados ganadores:

(defvar *lineas-ganadoras* '((0 1 2) (3 4 5) (6 7 8) (0 3 6)

(1 4 7) (2 5 8) (0 4 8) (2 4 6)))

(defun tiene-linea-ganadora (estado)

(loop for linea in *lineas-ganadoras* thereis

(es-linea-ganadora linea (tablero estado))))

(defun es-linea-ganadora (linea tablero)

(let ((valor (nth (first linea) tablero)))

(when (and (not (null valor))

(equalp valor (nth (second linea) tablero))

(equalp valor (nth (third linea) tablero)))

valor)))

(defun es-estado-ganador (estado turno jugador)

(when (tiene-linea-ganadora estado)

(not (equalp jugador turno))))

Movimientos:

(defparameter *movimientos*

(loop for i from 0 to 8 collect i))

Aplicar movimientos:

(defun ficha-opuesta (ficha)

(if (eq ficha 'x)

'o

'x))

(defun aplica (posicion estado)

(when (null (nth posicion (tablero estado)))

(let ((nuevo-tablero (loop for i in (tablero estado) collect i)))

(setf (nth posicion nuevo-tablero) (ficha estado))

(crea-estado :tablero nuevo-tablero

:ficha (ficha-opuesta (ficha estado))))))

Límites de la función de evaluación estática:

(defparameter *minimo-valor* -99999)

(defparameter *maximo-valor* 99999)

Función de evaluación estática:

(defun f-e-estatica (estado jugador)

(cond ((es-estado-ganador estado jugador 'max) *maximo-valor*)

((es-estado-ganador estado jugador 'min) *minimo-valor*)

((es-estado-completo estado) 0)

(t (- (posibles-lineas-ganadoras estado jugador 'max)

(posibles-lineas-ganadoras estado jugador 'min)))))

(defun posibles-lineas-ganadoras (estado turno jugador

(loop for linea in *lineas-ganadoras* counting

(not (esta (tablero estado)

(if (eq turno jugador)

(ficha-opuesta (ficha estado))

(ficha estado))

linea))))

(defun esta (tablero ficha linea)

(loop for i in linea

thereis (eq (nth i tablero) ficha)))