La búsqueda de mejor nodo ( BNS ) es un algoritmo de búsqueda minimax , desarrollado en 2011. Los experimentos con árboles aleatorios muestran que es el algoritmo minimax más eficiente . Este algoritmo indica qué movimiento conduce a minmax, pero no indica la evaluación de minimax . [1]
Actuación
MTD-f adivina el minimax llamando a podas alfa-beta de ventana cero . BNS llama a la búsqueda que indica si el minimax en el subárbol es más pequeño o más grande que el supuesto. Cambia el valor adivinado hasta que alfa y beta están lo suficientemente cerca o solo un subárbol permite un valor minimax mayor que el valor adivinado.
Pseudocódigo
la función nextGuess (α, β, subtreeCount) es devolver α + (β - α) × (subtreeCount - 1) / subtreeCountla función bns (nodo, α, β) es subtreeCount: = número de hijos del nodo hacer prueba: = nextGuess (α, β, subtreeCount) betterCount: = 0 para cada hijo del nodo hacer bestVal: = −alphabeta (hijo, −prueba, - (prueba - 1)) si bestVal ≥ prueba entonces betterCount: = betterCount + 1 bestNode: = niño (actualizar el número de subárboles que exceden el valor de la prueba de separación) (actualizar el rango alfa-beta) mientras que no (β - α <2 o mejor Cuenta = 1) devolver bestNode
La función nextGuess predeterminada anterior puede ser reemplazada por una que use información estadística para mejorar el rendimiento.
Generalización
La búsqueda de árboles con Murphy Sampling [2] es una extensión de Best Node Search a un entorno no determinista.
enlaces externos
Referencias
- ^ http://www.bjmc.lu.lv/fileadmin/user_upload/lu_portal/projekti/bjmc/Contents/770_7.pdf
- ^ Kaufmann, Emilie; Koolen, Wouter; Garivier, Aurelien (2018). "Prueba secuencial para la media más baja: de muestreo de Thompson a Murphy". arXiv : 1806.00973 [ stat.ML ].