Alfa, Beta Poda en AI

La poda alfa-beta es una optimización de la técnica para el algoritmo minimax. A lo largo de este blog, discutiremos lo que significa la poda alfa beta, discutiremos el algoritmo minimax, las reglas para encontrar un buen orden y más.

1. Introducción
2. Algoritmo Minimax
3. Puntos clave en la Poda Alfa-beta
4. Funcionamiento de la Poda Alfa-beta
5. Mover el orden en la Poda
6. Reglas para encontrar un buen orden
7. Códigos en Python

Introducción

La palabra «podar» significa cortar ramas y hojas. En la ciencia de datos, la poda es un término muy utilizado que se refiere a la poda posterior y previa en árboles de decisión y bosques aleatorios. La poda alfa-beta no es más que la poda de ramas inútiles en árboles de decisión. Este algoritmo de poda alfa-beta fue descubierto de forma independiente por investigadores en la década de 1900.

La poda alfa-beta es una técnica de optimización para el algoritmo minimax que se discute en la siguiente sección. La necesidad de podar vino del hecho de que en algunos casos los árboles de decisión se vuelven muy complejos. En ese árbol, algunas ramas inútiles aumentan la complejidad del modelo. Por lo tanto, para evitar esto, la poda Alfa-Beta entra en juego para que el ordenador no tenga que mirar todo el árbol. Estos nodos inusuales hacen que el algoritmo sea lento. Por lo tanto, al eliminar estos nodos, el algoritmo se vuelve rápido.

Aprenda sobre el algoritmo A*.

Algoritmo Minimax

Minimax es una técnica clásica de búsqueda en profundidad para un juego secuencial de dos jugadores. Los dos jugadores se llaman MAX y MIN. El algoritmo minimax está diseñado para encontrar el movimiento óptimo para MAX, el reproductor en el nodo raíz. El árbol de búsqueda se crea expandiendo recursivamente todos los nodos desde la raíz de una manera de primera profundidad hasta que se alcanza el final del juego o la profundidad máxima de búsqueda. Exploremos este algoritmo en detalle.

Como ya se mencionó, hay dos jugadores en el juego, viz-Max y Min. Max da el primer paso. La tarea de Max es maximizar su recompensa, mientras que la de Min es minimizar la recompensa de Max, aumentando su propia recompensa al mismo tiempo. Digamos que Max puede tomar las acciones a, b o c. ¿Cuál de ellas le dará a Max la mejor recompensa cuando termine el juego? Para responder a esta pregunta, debemos explorar el juego árbol a una profundidad suficiente y asumir que Min juega de manera óptima para minimizar la recompensa de Max.

Aquí hay un ejemplo. Hay cuatro monedas seguidas y cada jugador puede recoger una o dos monedas en su turno. El jugador que recoge la última moneda gana. Suponiendo que Max juegue primero, ¿qué movimiento debe hacer Max para ganar?

Si Max elige dos monedas, solo quedan dos monedas y Min puede elegir dos monedas y ganar. Así, recoger 1 moneda maximizará la recompensa de Max.

Como habrás notado, los nodos del árbol en la figura de abajo tienen algunos valores inscritos en ellos, estos se llaman valor minimax. El valor minimax de un nodo es la utilidad del nodo si se trata de un nodo terminal.

Si el nodo es un nodo Máximo no terminal, el valor minimax del nodo es el máximo de los valores minimax de todos los sucesores del nodo. Por otro lado, si el nodo es un nodo Min no terminal, el valor minimax del nodo es el mínimo de los valores minimax de todos los sucesores del nodo.

Ahora vamos a discutir la idea detrás de la poda alfa beta. Si aplicamos la poda alfa-beta al algoritmo minimax estándar, da la misma decisión que el algoritmo estándar, pero poda o corta los nodos que son inusuales en el árbol de decisiones, es decir, que no afectan la decisión final tomada por el algoritmo. Esto ayudará a evitar la complejidad en la interpretación de árboles complejos.

Vea cómo funciona el algoritmo KNN.

Ahora hablemos de la intuición detrás de esta técnica. Intentemos encontrar la decisión minimax en el árbol de abajo :

En este caso,

Aquí en el resultado anterior debe tener una duda en su mente que, ¿cómo podemos encontrar el máximo de valor que falta. Por lo tanto, aquí está la solución de su duda también:

En el segundo nodo elegimos el valor mínimo como c que es menor o igual a 2, es decir, c <= 2. Ahora si c < = 3 y tenemos que elegir el máximo de 3, c, 2 el valor máximo será 3.

Hemos llegado a una decisión sin mirar esos nodos. Y aquí es donde la poda alfa-beta entra en juego.

Puntos clave en la poda Alfa-beta

• Alfa: Alfa es la mejor opción o el valor más alto que hemos encontrado en cualquier instancia a lo largo de la ruta de Maximizer. El valor inicial de alfa es -∞.

• Beta: Beta es la mejor opción o el valor más bajo que hemos encontrado en cualquier instancia a lo largo del camino de Minimizer. El valor inicial de alfa es + ∞.

• La condición para la poda Alfa-beta es que α > = β.

• Cada nodo debe realizar un seguimiento de sus valores alfa y beta. Alfa solo se puede actualizar cuando es el turno de MAX y, de manera similar, beta solo se puede actualizar cuando es la oportunidad de MIN.

• MAX solo actualizará los valores alfa y MIN player solo actualizará los valores beta.

• Los valores de nodo se pasarán a los nodos superiores en lugar de los valores de alfa y beta durante la entrada al reverso del árbol.

• Los valores Alfa y Beta solo se pasan a los nodos secundarios.

Trabajo de Poda Alfa-beta

1. Primero comenzaremos con el movimiento inicial. Inicialmente definiremos los valores alfa y beta como el peor de los casos, es decir, α = -∞ y β= +∞. Podaremos el nodo solo cuando alfa sea mayor o igual a beta.

2. Dado que el valor inicial de alfa es menor que beta, no lo podamos. Ahora es el turno de MAX. Por lo tanto, en el nodo D, se calculará el valor de alfa. El valor de alfa en el nodo D será max (2, 3). Por lo tanto, el valor de alfa en el nodo D será 3.

3. Ahora el siguiente movimiento será en el nodo B y su turno durante un minuto. Por lo tanto, en el nodo B, el valor de alfa beta será min (3,∞). Por lo tanto, en el nodo B los valores serán alfa= – ∞ y beta será 3.

En el siguiente paso, los algoritmos recorren el siguiente sucesor del nodo B, que es el nodo E, y también se pasarán los valores de α= – ∞ y β = 3.

4. Ahora es el turno de MAX. Por lo tanto, en el nodo E buscaremos MAX. El valor actual de alfa en E es – ∞ y se comparará con 5. Así, MAX ( – ∞ , 5) será 5. Por lo tanto, en el nodo E, alfa = 5, Beta = 5. Ahora, como podemos ver, alfa es mayor que beta, lo que satisface la condición de poda, por lo que podemos podar el sucesor correcto del nodo E y el algoritmo no se atravesará y el valor en el nodo E será 5.

6. En el siguiente paso, el algoritmo vuelve al nodo A desde el nodo B. En el nodo A alfa se cambiará al valor máximo como MAX ( – ∞ , 3). Así que ahora el valor de alfa y beta en el nodo A será (3,+∞) respectivamente y se transferirá al nodo C. Estos mismos valores se transferirán al nodo F.

7. En el nodo F, el valor de alfa se comparará con la rama izquierda, que es 0. Por lo tanto, MAX (0, 3) será 3 y luego se comparará con el hijo correcto que es 1, y MAX (3,1) = 3 todavía α permanece 3, pero el valor del nodo de F se convertirá en 1.

8. Ahora el nodo F devolverá el valor del nodo 1 a C y se comparará con el valor beta en C. Ahora su turno para MIN. Entonces, MIN ( + ∞ , 1) será 1. Ahora en el nodo C, α = 3, y β= 1 y alfa es mayor que beta, lo que de nuevo satisface la condición de poda. Por lo tanto, el siguiente sucesor del nodo C es decir. G serán podadas y el algoritmo no compute en todo el subárbol G.

Ahora, C devolverá el valor del nodo a y el mejor valor de a será MAX (1, 3) será de 3.

El árbol representado arriba es el árbol final que muestra los nodos que se calculan y los nodos que no se calculan. Así, para este ejemplo, el valor óptimo de la maximizer 3.

Mira las bibliotecas de código abierto de Python.

Orden de movimiento en la poda

La efectividad de la poda alfa – beta se basa en el orden en el que se examina el nodo. El orden de movimientos juega un papel importante en la poda alfa beta.

Hay dos tipos de orden de movimiento en la poda Alfa beta:

1. Peor orden: En algunos casos de poda alfa beta, ninguno de los nodos se poda con el algoritmo y funciona como el algoritmo minimax estándar. Esto consume mucho tiempo, ya que debido a factores alfa y beta, así como no proporciona ningún tipo de resultados eficaces. Esto se llama el peor orden en la poda. En este caso, el mejor movimiento ocurre en el lado derecho del árbol.
2. Orden ideal: En algunos casos de poda alfa beta de los nodos podados por el algoritmo. Esto se llama orden ideal en la poda. En este caso, el mejor movimiento ocurre en el lado izquierdo del árbol. Aplicamos DFS, por lo tanto, la primera búsqueda a la izquierda del árbol y profundizamos el doble del algoritmo minimax en la misma cantidad de tiempo.

Reglas para encontrar un buen orden

• El mejor movimiento ocurre desde el nodo más bajo
• Use el conocimiento del dominio mientras encuentra el mejor movimiento
• El orden de los nodos debe ser de tal manera que los mejores nodos se calculen primero

Códigos en Python

class MinimaxABAgent: """ Minimax agent """ def __init__(self, max_depth, player_color): """ Initiation Parameters ---------- max_depth : int The max depth of the tree player_color : int The player's index as MAX in minimax algorithm """ self.max_depth = max_depth self.player_color = player_color self.node_expanded = 0 def choose_action(self, state): """ Predict the move using minimax algorithm Parameters ---------- state : State Returns ------- float, str: The evaluation or utility and the action key name """ self.node_expanded = 0 start_time = time.time() print("MINIMAX AB : Wait AI is choosing") list_action = AIElements.get_possible_action(state) eval_score, selected_key_action = self._minimax(0,state,True,float('-inf'),float('inf')) print("MINIMAX : Done, eval = %d, expanded %d" % (eval_score, self.node_expanded)) print("--- %s seconds ---" % (time.time() - start_time)) return (selected_key_action,list_action) def _minimax(self, current_depth, state, is_max_turn, alpha, beta): if current_depth == self.max_depth or state.is_terminal(): return AIElements.evaluation_function(state, self.player_color), "" self.node_expanded += 1 possible_action = AIElements.get_possible_action(state) key_of_actions = list(possible_action.keys()) shuffle(key_of_actions) #randomness best_value = float('-inf') if is_max_turn else float('inf') action_target = "" for action_key in key_of_actions: new_state = AIElements.result_function(state,possible_action) eval_child, action_child = self._minimax(current_depth+1,new_state,not is_max_turn, alpha, beta) if is_max_turn and best_value < eval_child: best_value = eval_child action_target = action_key alpha = max(alpha, best_value) if beta <= alpha: break elif (not is_max_turn) and best_value > eval_child: best_value = eval_child action_target = action_key beta = min(beta, best_value) if beta <= alpha: break return best_value, action_target

En este documento hemos visto un componente importante de la teoría de juegos. Aunque el rendimiento del algoritmo minimax es bueno, el algoritmo es lento. Así que para hacerlo rápido, usamos un algoritmo de poda alfa-beta que cortará los nodos inusuales del árbol de decisiones para mejorar el rendimiento. Hoy en día, el algoritmo rápido y bien realizado se usa ampliamente.

Eche un vistazo a estos cursos de Inteligencia Artificial y Aprendizaje Automático, desde Gran Aprendizaje hasta perfeccionamiento en el dominio y podado Alfa Beta maestro y otros algoritmos similares.

Lectura adicional

1. Algoritmo de Búsqueda A* en Inteligencia Artificial (IA)
2. Algoritmo de Árbol de decisiones Explicado con ejemplos
3. El Mejor Primer Algoritmo de Búsqueda en IA | Concepto, Implementación, Ventajas, Desventajas
4. ¿Qué es la Inteligencia Artificial? ¿Cómo funciona la IA, los Tipos y el futuro de la TI?