Un método de búsqueda adversarial basado en una estrategia óptima iterativa
Autores: Liu, Chanjuan; Yan, Junming; Ma, Yuanye; Zhao, Tianhao; Zhang, Qiang; Wei, Xiaopeng
Idioma: Inglés
Editor: MDPI
Año: 2020
Acceso abierto
Artículo científico
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Búsqueda de árbol de juegos
Algoritmo heurístico minimax
Nodos patológicos
Minimax óptimo iterativo
Regla de respaldo
Rendimiento en juegos
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 19
Citaciones: Sin citaciones
Una búsqueda más profunda en el árbol de juego puede proporcionar una mayor calidad de decisión en un algoritmo heurístico minimax. Sin embargo, pueden ocurrir excepciones como resultado de nodos patológicos, que se consideran existentes en todos los árboles de juego y pueden causar una búsqueda más profunda en el árbol de juego, lo que resulta en un peor juego. Para reducir el impacto de los nodos patológicos en la calidad de la búsqueda, proponemos un algoritmo minimax óptimo iterativo (IOM) optimizando la regla de respaldo del clásico algoritmo minimax. La idea principal es que el cálculo de los valores de estado de los nodos intermedios implica no solo la función de evaluación estática involucrada, sino también una búsqueda en el futuro, donde esta última recibe un peso mayor. Demostramos experimentalmente que el algoritmo IOM propuesto mejoró el rendimiento en el juego en comparación con los algoritmos existentes.
Descripción
Una búsqueda más profunda en el árbol de juego puede proporcionar una mayor calidad de decisión en un algoritmo heurístico minimax. Sin embargo, pueden ocurrir excepciones como resultado de nodos patológicos, que se consideran existentes en todos los árboles de juego y pueden causar una búsqueda más profunda en el árbol de juego, lo que resulta en un peor juego. Para reducir el impacto de los nodos patológicos en la calidad de la búsqueda, proponemos un algoritmo minimax óptimo iterativo (IOM) optimizando la regla de respaldo del clásico algoritmo minimax. La idea principal es que el cálculo de los valores de estado de los nodos intermedios implica no solo la función de evaluación estática involucrada, sino también una búsqueda en el futuro, donde esta última recibe un peso mayor. Demostramos experimentalmente que el algoritmo IOM propuesto mejoró el rendimiento en el juego en comparación con los algoritmos existentes.