Please enable JavaScript.
Coggle requires JavaScript to display documents.
Capítulo 6. Búsqueda entre adversarios (Poda alfa-beta (Parámetros poda…
Capítulo 6. Búsqueda entre
adversarios
Juegos
Teoría matemática del juego
Ve a cualquier entorno multiagente como un juego a condición de que el impacto de cada agente sobre los demás sea significativo, sin tener en cuenta si los agentes son cooperativos o competitivos.
Juegos en IA
Significan entornos deterministas,totalmente observables en los cuales hay dos agentes cuyas acciones deben alternar y en los que los valores utilidad, al final de juego, son siempre iguales y opuestos.
Decisiones óptimas en juegos
Un juego se puede definir como una clase de problemas de búsqueda.
Componentes
Estado inicial
Incluye la posición del tablero e identifica al jugador que
mueve.
Función sucesor
Devuelve una lista de pares (movimiento, estado), indicando
un movimiento legal y el estado que resulta.
Test terminal
Determina cuándo se termina el juego
Una función de utilidad
Da un valor numérico a los estados terminales.
Algoritmo Minimax
Usa un cálculo simple recurrente de los valores minimax de cada estado sucesor, directamente implementando las ecuaciones de la definición
La recursión progresa hacia las hojas del árbol, y luego los valores minimax regresan a través del árbol cuando la recursión se deshace.
Poda alfa-beta
Es posible calcular la decisión minimax correcta sin mirar todos los nodos en el árbol del juego
Cuando lo aplicamos a un árbol minimax estándar, devuelve el mismo movimiento
que devolvería minimax, ya que podar las ramas no puede influir,
en la decisión final.
Parámetros poda alfa-beta
Alfa
El valor de la mejor opción (es decir, valor más alto) que hemos encontrado hasta
ahora en cualquier punto elegido a lo largo del camino para MAX.
Beta
El valor de la mejor opción (es decir, valor más bajo) que hemos encontrado hasta
ahora en cualquier punto elegido a lo largo del camino para MIN.
Búsqueda Alfa-Beta
La búsqueda alfa-beta actualiza el valor de
alfa
y
beta
mientras atraviesa el árbol.
Poda las ramas restantes en un nodo tan pronto como
el valor del nodo actual es peor que el actual valor
alfa
o
beta
para MAX o MIN, respectivamente
Corte de la búsqueda
Modificación de la BUSQUEDA-ALFA-BETA de modo que llame a la función heurística EVAL cuando se corte la búsqueda.
Decisiones en tiempo real imperfectas
Funciones de evaluación
Una función de evaluación devuelve una estimación de la utilidad esperada del juego desde una posición determinada
¿Cómo diseñamos funciones de evaluación
buenas?
Primero, la función de evaluación debería ordenar los estados terminales del mismo
modo que la función de utilidad verdadera
Segundo, el calculo no debe utilizar demasiado tiempo
Tercero, para estados no terminales, la función de evaluación debería estar fuertemente correlacionada con las posibilidades actuales de ganar
Juegos que incluyen un elemento de posibilidad
Nodos de posibilidad
Los nodos de posibilidad se evalúan tomando el promedio ponderado de los valores que se obtienen de todos los resultados posibles.
La presencia de nodos de posibilidades significa que hay que tener más cuidado
sobre la evaluación de valores medios.
Nodos MAX y MIN