Algoritmo Min Max en IA: componentes, propiedades, ventajas y limitaciones

El algoritmo min max en IA, conocido popularmente como minimax, es un algoritmo de retroceso que se utiliza en la toma de decisiones, la teoría de juegos y la inteligencia artificial (IA). Se usa para encontrar el movimiento óptimo para un jugador, asumiendo que el oponente también está jugando de manera óptima. Los populares juegos de computadora o en línea para dos jugadores como Ajedrez, Tic-Tac-Toe, Damas, Go, etc. usan este algoritmo.

Se utiliza un algoritmo de retroceso para encontrar una solución a los problemas computacionales de tal manera que un candidato se construya gradualmente hacia una solución, un paso a la vez. Y el candidato que no logra completar una solución es inmediatamente abandonado.

¿Como funciona?

En el algoritmo min max en AI, hay dos jugadores, Maximiser y Minimiser. Ambos jugadores juegan el juego mientras uno intenta obtener la puntuación más alta posible o el máximo beneficio mientras que el oponente intenta obtener la puntuación más baja o el mínimo beneficio.

Cada tablero de juego tiene asignada una puntuación de evaluación, por lo que el Maximizador seleccionará el valor maximizado y el Minimizador seleccionará el valor minimizado con movimientos contrarios. Si Maximiser tiene la ventaja, entonces la puntuación del tablero será un valor positivo, y si Minimiser tiene la ventaja, entonces la puntuación del tablero será un valor negativo.

Esto se basa en el concepto de juego de suma cero en el que la puntuación de utilidad total se divide entre los dos jugadores. Por lo tanto, un aumento en la puntuación de un jugador conduce a una disminución en la puntuación del jugador oponente, haciendo que la puntuación total sea siempre cero. Entonces, para que un jugador gane, el otro tiene que perder.

Únase a los cursos en línea de Certificación de aprendizaje automático e IA de las mejores universidades del mundo. Obtenga maestrías, PGP ejecutivo o ACP para acelerar su carrera.

Desglosando el algoritmo min max en AI

El árbol de juego completo se explora con un algoritmo de búsqueda en profundidad en el algoritmo min max en AI. Continúa completamente hasta el nodo terminal del árbol y luego retrocede a través del árbol.

El objetivo es encontrar el mejor movimiento posible para un jugador. Esto se puede hacer eligiendo el nodo con la mejor puntuación de evaluación. La mejor elección se hará después de evaluar todos los movimientos potenciales del oponente. El algoritmo analiza todos los valores posibles hasta el final y toma una decisión por el jugador.

Fuente

El árbol del juego anterior es una estructura de datos anidados que se utiliza para evaluar los movimientos. Aquí el nodo raíz es el Nivel 0, que se ramifica en el Nivel 1 o nodos principales, que luego se ramifican en el Nivel 2 o nodos secundarios. La ramificación puede continuar a muchos niveles, teniendo el potencial de niveles infinitos. El nivel 0 es como el estado actual del tablero, mientras que el nivel 1 son todos los estados posibles de los tableros en función del próximo movimiento.

Por lo tanto, si el jugador 2 ha realizado un movimiento, podemos suponer que el nodo raíz es el estado actual del tablero, esperando el movimiento del jugador 1. Los nodos de nivel 1 contienen todos los movimientos posibles para el jugador 1, y los nodos de nivel 2 contienen todos los movimientos posibles para el jugador 2 en función de cada movimiento posible del jugador 1.

Considere un ejemplo donde hay cuatro estados finales y el camino para alcanzarlos es desde la raíz hasta las cuatro hojas de un árbol. Los valores de las cuatro hojas son 3, 6 a la izquierda y 4, 7 a la derecha. Es el turno del Maximizador/Jugador 1 para hacer un movimiento. Para ejecutar el algoritmo, se deben hacer suposiciones para cada movimiento.

Si el Jugador 1 elige ir a la izquierda, el Minimizador/Jugador 2 tiene que elegir el mínimo entre 3 y 6, por lo que elegiría 3. Mientras que si el Jugador 1 elige a la derecha, el Jugador 2 elegirá 4, que es el mínimo. de los dos valores, 4 y 7. Entonces, el Nivel 1 ahora tiene los valores 3 y 4.

Dado que es el turno del Jugador 1/Maximizador, debe elegir el máximo de nodos de Nivel 1. Por lo tanto, elegirán 3. Entonces, la opción óptima es ir a la izquierda.

Los pasos para el algoritmo min max en AI se pueden establecer de la siguiente manera:

1. Crea todo el árbol del juego.
2. Evalúe las puntuaciones de los nodos hoja en función de la función de evaluación.
3. Retroceda desde la hoja hasta los nodos raíz:

Para Maximizer, elija el nodo con la puntuación máxima.

Para Minimizador, elija el nodo con la puntuación mínima.

4. En el nodo raíz, elija el nodo con el valor máximo y seleccione el movimiento respectivo.

Lea también: Ideas de proyectos de aprendizaje automático

Propiedades del algoritmo min max en IA

• El algoritmo está completo, lo que significa que en un árbol de búsqueda finito, seguramente se encontrará una solución.
• Es óptimo si ambos jugadores están jugando de manera óptima.
• Debido a la búsqueda primero en profundidad (DFS) para el árbol del juego, la complejidad temporal del algoritmo es O(b m ), donde b es el factor de ramificación y m es la profundidad máxima del árbol.
• Al igual que DFS, la complejidad espacial de este algoritmo es O(bm).

ventajas

• Se realiza una evaluación exhaustiva del espacio de búsqueda.
• La toma de decisiones en IA es fácilmente posible.
• Con este algoritmo se desarrollan máquinas nuevas e inteligentes.

Limitaciones

• Debido al enorme factor de ramificación, el proceso de alcanzar la meta es más lento.
• La evaluación y búsqueda de todos los nodos y ramas posibles degrada el rendimiento y la eficiencia del motor.
• Ambos jugadores tienen demasiadas opciones para decidir.
• Si hay una restricción de tiempo y espacio, no es posible explorar todo el árbol.

Pero con Alpha-Beta Pruning, el algoritmo se puede mejorar.

Conclusión

Este artículo explica todos los aspectos del algoritmo min-max en AI. En primer lugar, se proporciona una introducción a la teoría con ejemplos de dónde se usa, después de lo cual hay una descripción de cómo funciona el algoritmo en un juego.

El algoritmo se desglosa para explicar cómo se toma la decisión de realizar un movimiento óptimo en función de los movimientos y contramovimientos de los jugadores. A continuación, se enumeran las propiedades del algoritmo. Por último, se proporcionan las ventajas y desventajas del algoritmo.

Si está interesado en obtener más información sobre el aprendizaje automático, consulte el Programa PG Ejecutivo en Aprendizaje Automático e IA de IIIT-B y upGrad, que está diseñado para profesionales que trabajan y ofrece más de 450 horas de capacitación rigurosa, más de 30 estudios de casos y asignaciones, IIIT -Estado de exalumno B, más de 5 proyectos prácticos finales prácticos y asistencia laboral con las mejores empresas.