Decisiones imperfectas en juegos de dos adversarios Decisión imperfecta ? Estrategia Mixta El algoritmo minimax asume una expansión hasta el final (en realidad es imposible). Se usa una función de evaluación (f), que sea una estimación de u. Función de evaluación: El papel de f es el de u en nodos terminales Ejemplos: Si hay 50% posibilidades de ganar, 25% de perder y 25% de empate, f=1*0.50+(-1)*0.25+0*0.25=0.25 En el ajedrez: peón=1, alfil=3, …. Suponiendo que MAX=fichas-blancas: f=(num-peones-negros)*1 + (num-alfiles-negros)*3 …. -(num-peones-blancos)*1 – (num-alfiles-blancos)*3 ….
Decisiones imperfectas en juegos de dos adversarios Dada una función de evaluación f, se puede aplicar una búsqueda minimax con límite de profundidad: Se elige un límite de profundidad Observación: el límite puede tener una posición desventajosa en un nivel más abajo. Se pueden elegir sucesivos límites de profundidad. El límite de profundidad se debería aplicar sólo a posiciones “inactivas”. En ajedrez, serían por ejemplo posiciones en las que es poco probable que existan capturas Problema del horizonte Surge cuando el programa se enfrenta a una acción del oponente, inevitable y que causa serios perjuicios. Ejemplo: en la figura anexa, peón blanco amenaza convertirse en dama. Torre negra amenaza con jaque. La ventaja actual es negra y la inmediata futura es blanca (evaluación calidad piezas).
Decisiones imperfectas en juegos de dos adversarios Exploración y evaluación: El procedimiento de exploración visto separa por completo el proceso de generación del árbol de exploración y la evaluación de posiciones. Se puede reducir el esfuerzo requerido si se hace evaluación de los nodos finales y se llevan hacia atrás esas evaluaciones con la generación el árbol Fcd-max: número de filas, columnas o diagonales libres para MAX Fcd-min: número de filas, columnas o diagonales libres para MIN Ejemplo: Tres en raya Definimos la función de utilidad:
Decisiones imperfectas en juegos de dos adversarios Ejemplo: Tres en raya ver Nilsson
Poda Consiste en tratar de localizar la decisión óptima minimax sin tener que explorar todos los nodos del árbol. Aplicable a árboles de cualquier profundidad Puede podar subárboles enteros Principio general El algoritmo efectúa una búsqueda en profundidad. Si durante la misma se produce que m es mejor que n para un jugador, entonces nunca se llegará a n en el juego
Fundamentos del algoritmo de poda: Si n es ascendiente de m, si se verifica alguna de estas condiciones: Si n nodo MAX, m nodo MIN: el valor alpha se alcanza en nodo hijo de n
n nodo MIN, m nodo MAX: el valor alpha se alcanza en nodo hijo de n
En ambos casos no hace falta seguir examinando por debajo de m (se producen podas). El nodo m no afecta al resultado final y es prescindible. Definimos Un valor es una cota inferior para el valor obtenido por propagación. Un valor es una cota superior para el valor obtenido por propagación. Poda
Algoritmo (Russell & Norvig) Poda Es similar al minimax salvo sendas líneas en las rutinas MIN-VALUE y MAX-VALUE que mantienen los valores de alpha y beta
Estimación en el ajedrez Un agente puede examinar unas 1000 posiciones/segundo. Si tenemos 150 segundos para pensar un movimiento, entonces, como b es aproximadamente 35, podemos descender 3 ó 4 niveles en el árbol. La poda va a permitir bajar hasta más niveles. Ejemplos, I 3 12 8 2 4 6 14 5 2 (Gp:) =3
(Gp:) < =2
(Gp:) =2
(Gp:) =3
Ejemplo sencillo de poda
Ejemplos, II “2” “5” “1” 2 “7” “3” 6 4 “0” 3 “5” “1” 9 6 2 8 [? ?] [-??] [-??] [-??] [-??] (Gp:) [-?”2”]
(Gp:) [“2” ?]
(Gp:) [2 ?]
(Gp:) [“2” 1]
(Gp:) [-?2]
(Gp:) [-?2]
(Gp:) [-?2]
(Gp:) [-?”2”] (Gp:) No mejoran ? = 2
(Gp:) [2 ”2”]
? > ? ! ? = ? ! ? = ? ! (Gp:) [-?”2”] (Gp:) No mejora valor de ? (lo devuelve hacia arriba)
(Gp:) [2 ?]
(Gp:) [2 ?]
(Gp:) [2 ?]
(Gp:) [2 ?]
(Gp:) [“2” 0]
? > ? ! (Gp:) [“2” ?]
(Gp:) [“2” 2]
(Gp:) [2 ?]
(Gp:) [2 5]
(Gp:) [“2” 1]
Efectividad de la poda La poda depende del orden en que se examinan los nodos En el ejemplo de la página siguiente, no se producen podas por debajo del nodo n porque la rama se expande la última. Si se pudiera elegir el nodo más conveniente (el nodo de f mínima en el caso de MIN): Knuth y Moore [1], demostraron que la complejidad temporal es:
Por tanto, el factor de ramificación efectivo sería en lugar de b. En el ajedrez tendríamos Podríamos bajar hasta el nivel 8. Es una situación ideal (supondría expandir los nodos para calcular el de menor f).
[1] Donald E. Knuth; Ronald W. Moore; An analysis of alpha-beta pruning. Artificial Intelligence 6(4); 293-326 (1975)
Efectividad de la poda Knuth y Moore demostraron también que si examinan los sucesores de forma aleatoria para valores moderados de b, la complejidad temporal es aproximadamente: O(b 3d/4)
3 12 8 2 4 6 14 5 2 n [-??] [-??] [-?, 3] [3, ?] [3, ?] [3, 2] [3, ?] [3, 14] [3, 5] [3, 2]
| Página siguiente |