¿De qué sirven los valores mínimos en los árboles minimax?

Considere un árbol minimax para un problema de búsqueda adversarial. Por ejemplo, en esta imagen (poda alfa-beta):

Al marcar el árbol con los valores abajo hacia arriba, primero atravesamos el nodo 3 y asignamos B. \ max = 3 . Luego atravesamos 12 y 8 en este orden, se asegurará de que B.max = 3 .$[\min,\max]$$3$$B.\max = 3$$12$$8$$B.max = 3$

Pero, ¿por qué $B.\min = 3$ ? ¿De qué sirve ese valor?

Esta figura (que de hecho es correcta) se utiliza en la explicación del algoritmo de poda alfa-beta en un árbol minimax. La poda alfa-beta es un método utilizado para podar partes del árbol minimax en un problema de búsqueda adversarial. En el contexto de un juego de tic-tac-toe, los árboles minimax están destinados a permitir que la computadora busque a través del espacio de todos los tableros de juego posibles (configuraciones de x's y o's) suponiendo que los movimientos del jugador sean óptimos. Esto permite que la computadora presente un movimiento que proporcione el mejor resultado (¡esta es la razón por la cual el juego de conectar cuatro en su computadora es tan increíblemente difícil de superar!). Para una descripción más completa, sugiero "AI a Modern Approach" de Stuart y Norvig (pág. 162-170 ish en la 2ª ed.).

Ahora que hemos aclarado alguna confusión sobre el algoritmo. La poda alfa-beta intenta evitar expandir los subárboles en función de cómo funciona el algoritmo minimax. Sabemos que el nodo máximo en el nivel superior tomará el mayor valor de todos sus hijos. Entonces, el nodo encuentra el valor , y hasta ahora, este es el valor máximo que está dispuesto a pasar a su padre, por lo que coloca este valor en la ranura MAX. Luego encuentra . Recuerde que es un nodo MIN, por lo que quiere minimizar el valor que pasa a su padre, por lo tanto, mantiene el valor en la ranura MAX. De nuevo por . Cuando ha buscado en todos sus elementos secundarios, conoce el límite inferior máximo ($B$$3$$12$$B$$3$$8$$B$$\alpha$) y la solución de límite superior mínimo ( ) de su subárbol y mantiene esos valores en MIN ( ) y MAX ( ) (como [3, 3]).$\beta$$\alpha$$\beta$

Nota: ¡min y max etiquetados en la figura NO son los valores mínimos y máximos del subárbol! Son (etiquetados de manera bastante confusa) los límites alfa-beta de las soluciones del subárbol (recuerde que este es un problema de búsqueda contradictorio).

A continuación se mueven al nodo . Aquí nos encontramos con un en la primera posición. El nodo , que desea seleccionar el valor más bajo de su subárbol, ahora SABE que su padre no elegirá su valor ya que el nodo encontró un valor mayor. Por lo tanto, podemos podar el resto del subárbol y continuar hasta .$C$$2$$C$$B$$D$

Finalmente, para responder la pregunta específica: ¿Por qué .min = 3? Un valor para (el límite inferior máximo de soluciones en este nodo) y (el límite superior mínimo de soluciones en este nodo) se mantiene en cada nodo para realizar la poda. Estos valores limitan los casos posibles en los que el valor de un nodo (o su subárbol) puede ser parte de la solución.$B$$\alpha$$\beta$

En este ejemplo, no parece jugar un papel, sin embargo, intente mirar ejemplos más complicados (es decir, árboles con una altura> 3) como este y ver si puede darle sentido.

No puedo hacer justicia a la poda minimax o alfa-beta aquí (principalmente porque no los he usado en años), así que si realmente desea entender esto, consulte un libro sobre IA como el de Stuart y Norvig (el la página de wikipedia sorprendentemente tampoco tiene visualización).