Mejoras en la función de búsqueda para poda alfa-beta
Páginas: 3 (681 palabras)
Publicado: 26 de octubre de 2010
Profundización iterativa
La primera de estas mejoras resulta sorprendente. Consiste en realizar varias búsquedas en cada turno de juego, en lugar de una sola.
Primero realizamos una búsquedahasta el nivel 1. Un vez terminada ésta hacemos una segunda que llegue hasta el nivel 2, y así sucesivamente, profundizando un nivel más en cada ciclo hasta que se agota el tiempo disponible para esajugada.
Resulta paradójico: hacemos todo lo posible por reducir la búsqueda (poda alfa beta, etc) y ahora decidimos que es mejor hacer no una sino varias búsquedas por cada turno de juego. Hay variasrazones que explican que hacer esto es una buena idea:
1. Por la propia naturaleza del minimax sucede que cada nivel adicional que profundizamos cuesta tanto o más tiempo de cálculo que la suma detodos los niveles anteriores.
2. Con esta técnica nos aseguramos de que siempre habrá una jugada disponible cualquiera que sea el tiempo que tenemos para realizar la jugada, ya que la búsqueda hastalos primeros niveles es casi instantánea.
3. Lo más importante es que en cada búsqueda que hacemos obtenemos información muy valiosa que utilizaremos en la siguiente búsqueda. Esta realimentaciónes la base de varias mejoras en el algoritmo de búsqueda. Es decir, para mejorar y hacer más rápida la función de búsqueda primero tenemos que introducir la búsqueda iterativa como paso previo. Es labase para todas las mejoras posteriores.
Línea principal
La principal mejora que aprovecha la técnica de la profundización iterativa es el uso de la línea principal. Para esto debemos tener laprecaución de guardar y mantener la mejor variante cuando estamos calculando dentro de la función de búsqueda.
De esta forma cuando la búsqueda acaba tenemos no sólo la mejor jugada, también toda lalínea prevista por el programa como posibles respuestas de uno y otro bando hasta la profundidad hasta donde haya llegado. Llamamos a esta variante “línea principal”.
La línea principal se utiliza...
La primera de estas mejoras resulta sorprendente. Consiste en realizar varias búsquedas en cada turno de juego, en lugar de una sola.
Primero realizamos una búsquedahasta el nivel 1. Un vez terminada ésta hacemos una segunda que llegue hasta el nivel 2, y así sucesivamente, profundizando un nivel más en cada ciclo hasta que se agota el tiempo disponible para esajugada.
Resulta paradójico: hacemos todo lo posible por reducir la búsqueda (poda alfa beta, etc) y ahora decidimos que es mejor hacer no una sino varias búsquedas por cada turno de juego. Hay variasrazones que explican que hacer esto es una buena idea:
1. Por la propia naturaleza del minimax sucede que cada nivel adicional que profundizamos cuesta tanto o más tiempo de cálculo que la suma detodos los niveles anteriores.
2. Con esta técnica nos aseguramos de que siempre habrá una jugada disponible cualquiera que sea el tiempo que tenemos para realizar la jugada, ya que la búsqueda hastalos primeros niveles es casi instantánea.
3. Lo más importante es que en cada búsqueda que hacemos obtenemos información muy valiosa que utilizaremos en la siguiente búsqueda. Esta realimentaciónes la base de varias mejoras en el algoritmo de búsqueda. Es decir, para mejorar y hacer más rápida la función de búsqueda primero tenemos que introducir la búsqueda iterativa como paso previo. Es labase para todas las mejoras posteriores.
Línea principal
La principal mejora que aprovecha la técnica de la profundización iterativa es el uso de la línea principal. Para esto debemos tener laprecaución de guardar y mantener la mejor variante cuando estamos calculando dentro de la función de búsqueda.
De esta forma cuando la búsqueda acaba tenemos no sólo la mejor jugada, también toda lalínea prevista por el programa como posibles respuestas de uno y otro bando hasta la profundidad hasta donde haya llegado. Llamamos a esta variante “línea principal”.
La línea principal se utiliza...
Leer documento completo
Regístrate para leer el documento completo.