• Un ESTADO INICIAL, que incluye la posición en el tablero y una indicación de a quien toca jugar
• Un CONJUNTO DE OPERADORES, que definen qué jugadas están permitidas a un jugador.
• Una PRUEBA TERMINAL, que define el término del juego
• Una FUNCION DE UTILIDAD, asigna un valor numérico al resultado obtenido en un juego.

El algoritmo MINIMAX, sirve para determinar la estrategia óptima para MAZ y decidir así cuál es la mejor jugada- Los algoritmos se componen de estos pasos:

1. Generación de todo el árbol de juego, completamente hasta alcanzar los estados terminales.
2. Aplicación de la función de utilidad a cada estado terminal y obtención de su valor respectivo.
3. Uso de la utilidad de los estados terminales para calcular la utilidad de los nodos del siguiente nivel superior en el árbol de búsqueda.

DECISIONES IMPERFECTAS

El algoritmo MINIMAX parte del superto de que el programa dispone de todo el tiempo necesario para efectuar una búsqueda hasta que logre llegar a los estados terminales, entonces se puede afirmar que el método en general NO ES PRACTICO. Por ende se sugieren modificarlo usando una Función de utilidad que se reemplaza mediante una función de evaluación EVAL y la prueba terminal se reemplaza por la llamada PRUEBA-SUSPENSION

FUNCIONES DE EVALUACION

Producen una estimación de la utilidad esperada de un juego correspondiente a una posición determinada. Esta debe coincidir con la función de utilidad de los estados temrinales. Se establece un compromiso entre precisión de la función de evaluación y su respectivo costo en tiempo. La función de evaluación deberá reflejar con presición las posibilidades reales de poder ganar.

De la ventaja material, se parte del supuesto de que el valor de una pieza puede calcularse independientemente de las otras piezas que estén en el tablero. A esto se le llama FUNCION LINEAL PONDERADA.

SUSPENSION DE UNA BUSQUEDA

Se debe definir un límite de profundidad fijo, de manera que la prueba de suspención concluya en todos los nodos que estén por encima o justo en la profundidad d. Esta se escoge de manera que la cantidad de tiempo invertida no exceda lo permitido por las reglas de juego.

PODA ALFA-BETA

Al proceso para evitar la exploración de una de las ramas del árbol de búsqueda se le conoce como poda, a la que se considera en particular se le llama poda alfa-beta

Si se considera un nodo (n) del árbol, tal que exista la posibilidad de que el jugador pueda ir a ese nodo. Si el jugador tuviera una mejor opción m, ya sea en el nodo padre de n, o en cualquier punto de elección posterior

F"..en un juego nunca se alcanzará n "

La eficiencia dependerá del orden como se exploren los sucesores