Analysis by Rybka 3 1-cpu 32-bit:
1. +- (#8): 1.Db8
1. +- (#8): 1.Db8
2. +- (#9): 1.Db6
3. +- (#10): 1.Dd2
4. +- (#10): 1.Db4
5. +- (#11): 1.Df2
6. +- (#13): 1.Db5
7. +- (#15): 1.De2
8. +- (#15): 1.Dc2
9. +- (#17): 1.Da2
(, 05.02.2009)
(, 05.02.2009)
Pero el problema no es tan difícil, de hecho no es necesario el programa, después de
1.-Rh2 h3 [única] 2.-Rh1 h2 [Única] 3.-Af7 Rh7 [Única] 4.-Dh2#
Pero eso es por el efecto horizonte que tienen los algoritmos.
El efecto horizonte es un problema inherente al minimax y que es imposible eliminar por completo. Se presenta cuando se envía a evaluar una posición intermedia en una secuencia táctica.
Consideremos un par de ejemplos:En una secuencia de cambios tácticos el programa captura una torre. El motor evalúa esta posición con un valor de +5 porque tiene una torre más que su adversario. A la siguiente jugada el rival corona un peón que estaba en la séptima fila. Se ha producido el temido efecto horizonte. El programa evaluó una posición intermedia en una secuencia táctica y obtuvo una valoración errónea.
Otro ejemplo más: supongamos que es el turno de juego del programa con blancas. La función de búsqueda empieza a construir su árbol de variantes y en uno de los nodos terminales asigna un valor de +10 a la posición. La valoración tan alta se explica porque el programa acaba de comerse la dama de su rival. Si contamos el material que hay en el tablero vemos que las blancas tienen una dama de más y por tanto la función de evaluación valora esta posición con una ventaja de 10 puntos.Pero si seguimos mirando una jugada más allá vemos que las negras restablecen la igualdad material porque capturan la dama blanca en el siguiente movimiento. Es decir, lo que al programa le parece una captura de dama en realidad es un simple cambio. El desastre puede ser total si para llegar a ese cambio de damas el programa ha sacrificado material confiando en que al comerse la dama enemiga saldría ganando finalmente.
El efecto horizonte continúa apareciendo sea cual sea la profundidad de búsqueda. No importa si el programa puede ver hasta una profundidad de 4, 5 o 16 jugadas: si las posiciones de los nodos terminales son posiciones intermedias en una secuencia de cambios el efecto horizonte impedirá al programa jugar bien. Esta ceguera suicida es parte del algoritmo de búsqueda empleado por los programas de ajedrez y si bien no se puede eliminar completamente sí se puede mitigar en gran parte.
Consideremos un par de ejemplos:En una secuencia de cambios tácticos el programa captura una torre. El motor evalúa esta posición con un valor de +5 porque tiene una torre más que su adversario. A la siguiente jugada el rival corona un peón que estaba en la séptima fila. Se ha producido el temido efecto horizonte. El programa evaluó una posición intermedia en una secuencia táctica y obtuvo una valoración errónea.
Otro ejemplo más: supongamos que es el turno de juego del programa con blancas. La función de búsqueda empieza a construir su árbol de variantes y en uno de los nodos terminales asigna un valor de +10 a la posición. La valoración tan alta se explica porque el programa acaba de comerse la dama de su rival. Si contamos el material que hay en el tablero vemos que las blancas tienen una dama de más y por tanto la función de evaluación valora esta posición con una ventaja de 10 puntos.Pero si seguimos mirando una jugada más allá vemos que las negras restablecen la igualdad material porque capturan la dama blanca en el siguiente movimiento. Es decir, lo que al programa le parece una captura de dama en realidad es un simple cambio. El desastre puede ser total si para llegar a ese cambio de damas el programa ha sacrificado material confiando en que al comerse la dama enemiga saldría ganando finalmente.
El efecto horizonte continúa apareciendo sea cual sea la profundidad de búsqueda. No importa si el programa puede ver hasta una profundidad de 4, 5 o 16 jugadas: si las posiciones de los nodos terminales son posiciones intermedias en una secuencia de cambios el efecto horizonte impedirá al programa jugar bien. Esta ceguera suicida es parte del algoritmo de búsqueda empleado por los programas de ajedrez y si bien no se puede eliminar completamente sí se puede mitigar en gran parte.
Posiciones estables: La solución parcial que permite minimizar los efectos de este problema se basa en la búsqueda de posiciones estables. El algoritmo de búsqueda no se detiene hasta que encuentra una posición estable. A efectos prácticos vamos a suponer que una posición estable en ajedrez es aquella en la que no existen capturas legales ni golpes tácticos como coronaciones de peón, etc.
Si tratamos de poner esto en práctica de forma directa extendiendo la búsqueda hasta llegar a posiciones estables pronto se descubre que no vamos a llegar muy lejos: la búsqueda de las posiciones estables extiende demasiado el árbol, es peor el remedio que la enfermedad.
Si tratamos de poner esto en práctica de forma directa extendiendo la búsqueda hasta llegar a posiciones estables pronto se descubre que no vamos a llegar muy lejos: la búsqueda de las posiciones estables extiende demasiado el árbol, es peor el remedio que la enfermedad.
Búsqueda quiescente: Hay que utilizar otro tipo de búsqueda: la búsqueda quiescente. Esta técnica consiste en desarrollar normalmente el árbol de búsqueda hasta llegar a los nodos terminales. En ese momento, en lugar de pasar estas posiciones terminales a la función de evaluación las mandamos a una función de búsqueda quiescente.
Esta nueva función es igual que la normal, con poda alfa beta incluida. La diferencia es el generador de movimientos que utiliza. Se trata de un generador distinto del principal. Esta vez sólo calculamos jugadas "peligrosas", básicamente capturas, jaques y promociones de peón. Antes, cuando describíamos el problema del efecto horizonte vimos que se trata de vuelcos repentinos que ocurren en la valoración de la posición. Estos vuelcos suceden casi siempre cuando están involucradas jugadas del mismo tipo que calcula nuestro generador especial: capturas, jaques y coronaciones. Al terminar la búsqueda quiescente hemos conseguido obtener una valoración más realista porque hemos profundizado hasta una posición estable. Además hemos podido encontrar esta estabilidad en un tiempo razonable gracias a que hemos podido reducir drásticamente el factor de ramificación. Recordemos que antes definimos el factor de ramificación como el número medio de jugadas que un bando tiene a su disposición. Si descartamos todas las jugadas normales y nos quedamos sólo con las peligrosas en vez de 30-35 jugadas posibles de media tendremos muchas menos, a menudo sólo 1 ó 2. Esta búsqueda con un factor de ramificación tan bajo produce un árbol de variantes muy profundo y estrecho.
La búsqueda quiescente no es una técnica perfecta, pero permite minimizar el efecto horizonte y es fundamental para que un programa pueda jugar bien al ajedrez.
Esta nueva función es igual que la normal, con poda alfa beta incluida. La diferencia es el generador de movimientos que utiliza. Se trata de un generador distinto del principal. Esta vez sólo calculamos jugadas "peligrosas", básicamente capturas, jaques y promociones de peón. Antes, cuando describíamos el problema del efecto horizonte vimos que se trata de vuelcos repentinos que ocurren en la valoración de la posición. Estos vuelcos suceden casi siempre cuando están involucradas jugadas del mismo tipo que calcula nuestro generador especial: capturas, jaques y coronaciones. Al terminar la búsqueda quiescente hemos conseguido obtener una valoración más realista porque hemos profundizado hasta una posición estable. Además hemos podido encontrar esta estabilidad en un tiempo razonable gracias a que hemos podido reducir drásticamente el factor de ramificación. Recordemos que antes definimos el factor de ramificación como el número medio de jugadas que un bando tiene a su disposición. Si descartamos todas las jugadas normales y nos quedamos sólo con las peligrosas en vez de 30-35 jugadas posibles de media tendremos muchas menos, a menudo sólo 1 ó 2. Esta búsqueda con un factor de ramificación tan bajo produce un árbol de variantes muy profundo y estrecho.
La búsqueda quiescente no es una técnica perfecta, pero permite minimizar el efecto horizonte y es fundamental para que un programa pueda jugar bien al ajedrez.
Ahora te dejo este problema de tarea, que puedes decirme de este ejercicio. (A Guzman.)
Blancas juegan y ganan.
Ribka 3, da una ventaja de -+ 2.00 a las negras, que se supone debería ser definitivo.
No hay comentarios:
Publicar un comentario