Ejemplo de aplicacin de algoritmo minimax con poda alfa-beta

Ejercicio: Considrese el juego bipersonal que utiliza el tablero que se muestra a continuacin.

Jugador 1

Jugador 2

1 2 3 4 5 6 7 8 9

Sobre este tablero los jugadores van poniendo por turno monedas de 1 euro en las casillas de su fila. Cuando un jugador ha puesto una moneda en una posicin (columna), esa posicin queda bloqueada para el otro jugador. Quien primero ocupe tres nmeros distintos que sumen 15 se lleva todo el dinero que haya en la mesa. Desarrollar las 2 primeras jugadas con una profundidad de juego igual a 3 utilizando la poda alfa-beta.

Evaluacin de un estado: para cada posible opcin ganadora sumo 1 por cada nmero de la terna

elegida por mi, y resto 1 por cada nmero elegido por el contrario

Evalo hijos Nodo raz:

Y decido que siempre voy a explorar por orden descendente de estos valores (5,1,4,6,8,2,3,7,9)

Exploro 5

Exploro 5 1

Exploro y Evalo hijos

5 1 2 3 4 6 7 8 9

1 5 9 0 0 0 0 0 0 0

1 6 8 -1 -1 -1 0 -1 0 -1

1 4 9 -1 -1 0 -1 -1 -1 0

2 5 8 2 1 1 1 1 2 1

2 6 7 1 1 1

3 4 8 1 1 1

3 5 7 1 2 1 1 2 1 1

4 5 6 1 1 2 2 1 1 1

Valor 3 3 4 4 3 4 2

V(5 1)=4 (Max hijos= max{3,3,4,4,3,4,2}=4)

V(5)

Exploro 5 4 (beta=4)

Exploro 5 4 1: V(5 4 1)=4

V(5 4) >=4: Podo 5 4

Exploro 5 6 (beta=4):

Exploro 5 6 1: V(5 6 1)=4

V(5 6) >=4: Podo 5 6

Exploro 5 8 (beta=4)

Exploro 5 8 1: V(5 8 1)=4

V(5 8) >=4: Podo 5 8

Exploro 5 2 (beta=4)

Exploro 5 2 1: V(5 2 1)=5

V(5 2) >=5: Podo 5 2

Exploro 5 3 (beta=4)

Exploro 5 3 1: V(5 3 1)=5

V(5 3) >=5: Podo 5 3

Exploro 5 7 (beta=4)

Exploro 5 7 1: V(5 7 1)=5

V(5 7) >=5: Podo 5 7

Exploro 5 9 (beta=4)

Exploro 5 9 1: V(5 9 1)=5

V(5 9) >=5: Podo 5 9

V(5)=4

VALOR>=4 alpha=4

Exploro 1 alpha=4

Exploro 1 5

Exploro y Evalo hijos

1 5 2 3 4 6 7 8 9

Valor 1 1 2 2 1 2 0

V(1 5)=2

V(1)

Exploro 4 alpha=4

Exploro 4 5

Exploro y Evalo hijos

-----------------------------------------------

Max hijos=2

V(4 5)=2

V(4)

Exploro 3 5

Exploro y Evalo hijos

-----------------------------------------------

Max hijos=1

V(3 5)=1

V(3)