Duda con la busqueda.. en español!! please!!

[pimidrez]

Hola a todos,

mi duda es con respecto a la generacion de mov. y cuando evaluar:
a) mi motor de ajedrez actualmente busca si o si a 4 plys y evalua el nodo final, es decir por ejemplo:
e2e4 e7e5 d2d3 d7d6 ----> evalua el tablero cuando la posición esta echa d7d6 ...¿eso esta bien? ¿esta bien aplicado el algoritmo?

b) otro problema que tengo es que si hago que busque a modo de bucle más "plys" se me quedaria "colgado" en la primera jugada bucando más y más profundidad, y no se q criterio tomar para detenerlo a cierta profundidad y que asi continue con los otros movimiento...¿como es?

se me ocurre lo siguiente: a lo mejor debo evaluar primero todos los movimiento hasta el "ply" 2, luego si hay tiempo seguir con el "ply" 4 y asi sucesivamente...pero eso demandaria mucho tiempo y trabajo ya que estaria evaluando cada movimiento y no solo los nodos finales...


Cabe destacar que mi motor de ajedrez tiene su propia interfaz y no funciona con protocolos UCI ni Winboard...

Gracias, espero su repsuesta!!
saludos!

PIMIDREZ

[Pedro Castro]

Me imagino que tu programa para generar el árbol de movimientos de una posición utilizará el algoritmo alfa-beta o alguna de sus variantes. Me imagino que para evitar el efecto horizonte tu programa también extenderá las capturas y promociones con una función quiesce, normalmente en dicha función se suele llamar a la evaluación.

Practicamente el 95% de los programas pueden jugar con un sistema de tiempos y no juegan una determinada profundidad fija. El hacer esto es bastante sencillo, en lugar de llamar al alfa-beta directamente con el nivel de profundidad fija se llama al alfa-beta con una profundidad 1, cuando se termina se pasa a la 2 y asi sucesivamente, esto se llama busqueda iterativa y lo bueno del sistema es que no es más lento buscar cada uno de los niveles que buscar directamente y es debido a que cuando buscas primero el nivel 1 te va a ayudar a ordenar los movimimientos para el nivel 2 y asi sucesivamente. Además si utilizas tiempo y este se acaba al menos ya tienes una evaluación de la posición en un nivel ya completo ya examinada. Es muy importante que tu programa tenga una función para ordenadar los movimientos de mejor a peor para probar el alfa-beta ya que de lo contrario el alfa-beta no será efectivo. Primero se suelen probar movimientos con el que viene de las tablas hash, el movimiento de la variante principal en el anterior ply, capturas, movimientos killer y los otros movimientos ordenados por historia o por tablas.

Una página interesante que puedes leer es la de Bruce Moreland:

http://web.archive.org/web/200404032117 ... /index.htm

[Fermin Serrano]

Aunque Pedro ya te ha hecho una buena introdución, te comento algo que parece que todavia no sabes, y es uno de los puntos claves en un motor de ajedrez, y es el efecto horizonte. En tu ejemplo, parece que siempre terminas la busqueda cuando se han completado 4 plys (ply = media jugada). Esto es un problema importante. Imaginate en la jugada 4 haces una captura de damas (DxD), y como al motor no le das otro ply para ver la recaptura (p.e, PXd), entonces el motor piensa que en ese momento la posición es claramente ventajosa en material cuando en realidad no lo es.
Para evitar este problema, como te ha dicho Pedro se extienden solo las capturas en los nodos finales. En el link que te ha dado Pedro seguro que encuentras muchas respuestas.
Saludos
Fermin