JUEGOS MINI-MAX

La estrategia minimax es una estrategia de búsqueda exhaustiva mediante un árbol de búsqueda. Este algoritmo considera el caso de 2 participantes a los que se les denomina Max y Min.

El que inicia el juego es Max y existe una alternancia en la participación del juego. Por lo tanto lo que tiene que hacer Max, es determinar la secuencia de jugadas que conduzca a un estado Terminal ganador o favorecedor. La figura 1 muestra parte del árbol generado para la búsqueda por la técnica de Minimax para el juego del tres en raya.

Sin embargo, esta búsqueda muchas veces tiene que evaluar ramas innecesarias que no le traerán beneficio alguno para obtener el mejor resultado. Por lo tanto, es aquí donde se plantea la solución mediante la poda de esas ramas que no beneficiaran en nada a la mejor jugada: La técnica de Poda Alpha-Beta. El algoritmo 1 muestra la implementación de la técnica de Minimax en forma recursiva.

Algoritmo 1: Algoritmo recursivo de la técnica de Minimax

Entrada:
  - Nodo N.
Salida:
  - Valor de utilidad de N
-------------------------------------------------------------------------------------------------------------
Si N es nodo Hoja
     ValorUtilidad<-función de utilidad
De lo contrario
Para cada nodoHijo Hi de
      valorUtilidadi<-MiniMaxR(Hi)
Fin para
Si N es max
       valorUtilidad<- max(H1,H2,...Hn)
De lo contrario
       valorUtilidad<- min(H1,H2,...Hn)

Devolver (valorUtilidad)