Las primeras propuestas de función de evaluación estaban orientadas a tener una evaluación estática de la posición basada fundamentalmente en el concepto de material. Rápidamente se captó que esta evaluación no era suficiente, considerando que en el ajedrez existen factores estructurales los cuales afectarán a largo plazo el curso de la partida, por lo cual es muy probable que el programa no encuentre las consecuencias de esta situación en su búsqueda en profundidad. Estos aspectos, denominados "Posicionales" debieron incluirse en la función de evaluación.
Los primeros programas incluyeron algunos parámetros posicionales básicos, los cuales tenían un peso importante en la evaluación de la posición pero no igualable al peso que poseía el factor de material. El problema entonces de dar un adecuado "peso" a cada parámetro de la función de evaluación, y en qué momento de la partida darlo a uno u otro parámetro constituía un problema denominado carencia de "conocimiento ajedrecístico" cuya solución estaba en captar las impresiones de los jugadores humanos "expertos" y asimilarlas en el programa.
La inclusión de un mayor "conocimiento ajedrecístico" en los programas fue logrado mediante el trabajo conjunto entre programadores y maestros de ajedrez. Desafortunadamente, costó bastante el poder combinar de manera eficiente una idea de función de evaluación lo más completa posible con la mayor cantidad de parámetros de medición, pero a la vez muy rápida en su capacidad de cálculo.
Nuevamente acá los avances en hardware permitieron crear funciones de evaluación más poderosas y cuya utilización no significaba un alto costo de CPU. El problema entonces se redujo a cómo dar pesos adecuados a cada parámetro de la función con tal de que la combinación de éstos entregue una evaluación al menos similar a la que concluiría un maestro de ajedrez.
A este respecto resulta destacable el trabajo realizado por Hsu,Campbell y Anantharaman [31], quienes testearon su programa DeepBlue con cerca de 900 posiciones particulares de partidas de Grandes Maestros. Durante el análisis por parte de la máquina de estas posiciones, los programadores iban ajustando manualmente los pesos de cada parámetro de la función de evaluación con tal de que el programa encontrara el movimiento seleccionado. Este ajuste de "pesos" resultó ser un notorio avance en la performance de la función de evaluación del programa. Respecto de esto una cita de Anantharaman en el ICCA Journal describiendo esta metodología :
"La función de evaluación del software de Deep Thought es ajustada contra una base de datos de partidas de maestros de ajedrez. La diferencia de evaluación entre el movimiento elegido por el programa y el maestro es minimizada. La performance del programa de ajedrez con la función de evaluación ajustada fue medida en forma experimental. El programa jugó varios matchs de 500 partidas con diferentes ajustes contra un programa fijo. Los resultados mostraron que un 98% de la performance de la función de evaluación puede ser mejorada en aproximadamente una semana ajustándola a partir de la información de partidas de la base de datos".
Este método lineal de ajuste de los pesos de parámetros de la función de evaluación fue combinado con extensivas sesiones de partidas entre programas y Grandes Maestros, en donde los experimentados humanos entregaban sus observaciones acerca de las características de juego de la máquina.
Hsu relata en [8] acerca de la necesidad de realizar sesiones de entrenamiento entre DeepBlue y el GM Joel Benjamin, en donde el campeón norteamericano aportó con excelentes observaciones acerca del comportamiento de la evaluación de la máquina, qué cosas valoraba por sobre otras y qué ajustes podían realizarse con tal de mejorar su "concepto" ajedrecístico.
Un excelente ejemplo de esta técnica de refinamiento se vió en la partida 2 del match entre DeepBlue y Kasparov en 1997 (ver anexo de partidas). En posiciones en donde se producían "tensiones de peones" (peones que pueden ser cambiados despejando columnas) la máquina tendía a realizar el cambio de peones con tal de ocupar luego la columna abierta generada por ese cambio con las torres. Esta actitud del programa debía mejorarse puesto que en vez de cambiar peones y ocupar la columna es por lo general mucho mejor primero ocupar la columna "candidata a abrirse" con las Torres y luego proceder a los cambios de peones. El movimiento 24 de DeepBlue en la citada partida fue consecuencia de esta observación.
En la actualidad las mejoras introducidas en la función de evaluación de los programas apuntan a los trabajos desarrollados con redes neuronales y algoritmos genéticos los cuales apuntan a la utilización de métodos de aprendizaje por parte del programa [52]. La apuesta es bastante interesante pues toma en consideración una de las capacidades básicas de los humanos en la mejora de su nivel de juego, el hecho de adquirir conocimientos nuevos frente a experiencia. Las técnicas apuntan a mejorar el nivel de conocimiento ajedrecístico de los programas.
martes, 15 de junio de 2010
Técnicas de Búsqueda
Las técnicas de búsqueda en el ajedrez han sido probablemente la parte más desarrollada en términos de investigación para la mejora de algoritmos dentro del proceso del juego. Es acá en donde el programa realiza el mayor esfuerzo en recolectar información suficiente para decidir por un movimiento.
Los algoritmos desarrollados para este fin han sido variados. La primera propuesta, presentada por Shannon, fue la búsqueda por fuerza bruta a profundidad fija, examinando todas las continuaciones posibles hasta cierto límite de movimientos. Esta búsqueda se realizaría mediante el algoritmo Minimax.
Hasta principios de los 70 los programas de ajedrez seguían basándose en los modelos de Shannon para realizar su proceso de búsqueda. Hasta ese momento el diseño de programas de ajedrez se focalizaba principalmente en el orden de los movimientos con tal de lograr la mejor "poda" de variantes: jaques, capturas, "movidas asesinas", amenazas y avances de peones pasados. Categorizando los movimientos en distintos grupos mediante amenazas tácticas (de corto plazo) o estratégicas (de largo plazo) se podía asegurar el que las variantes "forzadas" serían analizadas primero. Esta técnica lograba generar cortes o reducciones en el árbol de búsqueda para aquellas variantes que se clasificaban como innecesarias de analizar.
También durante la década de 1970 la noción de búsqueda iterativa fue refinada y sometida a prueba. Con un enfoque de completitud y uniformidad las búsquedas eran generalmente hechas a una profundidad fija (en forma iterativa dependiendo del tiempo de reflexión restante). El uso del tiempo para controlar la búsqueda tomó también un carácter de suma importancia, dado que ofrecía la flexibilidad de confirmar si el movimiento encontrado en la anterior iteración era efectivamente el mejor. Esto hizo que de alguna manera la búsqueda selectiva (estrategia "B" de Shannon) cayera en desuso, debido a la dificultad de su implementación en las computadoras.
Resultó que la seguridad de buscar en todos los movimientos posibles otorgó mejores resultados que el descarte de variantes basado en su baja relevancia. La búsqueda selectiva vio prácticamente su muerte en esta década, si bien fue la estrategia líder de los 60 con el programa MackHack, el cual estaba implementado con un selector de movimientos plausibles [46]. A finales de la década los beneficios de la búsqueda de posiciones estables con profundidad variable fue clara, y esto llevó a la preponderancia de los programas de estrategia tipo A los cuales utilizaron búsquedas basadas en distintas etapas.
Con el aumento en la velocidad de los procesadores pudieron realizarse búsquedas más profundas causando a principio de los 80 un interés por realizarlas en etapas. La idea fue realizar una primera búsqueda a profundidad fija de varios movimientos seguida de una búsqueda selectiva y terminando con una búsqueda de posiciones estables a partir de movimientos como capturas o respuestas a jaques. Este modelo de búsqueda demostró ser a la vez bastante robusto. De todas maneras, este tipo de búsqueda en etapas no reflejaba adecuadamente la noción intuitiva de que las extensiones en la profundidad de búsqueda deben ser selectivas en vez de uniformes, aplicándose en variantes forzadas.
Era claro que la extensión de un movimiento debía realizarse cuando uno de los bandos se encontraba en jaque. Un idea similar era extender la búsqueda cuando un jugador tuviera sólo un movimiento legal posible, pero lo que realmente se deseaba buscar era una extensión en situaciones en que cualquiera de los dos jugadores tuviese sólo un movimiento "sensible" (por ejemplo, una captura). Esto implicaba algún tipo de pre-poda con tal de detener la expansión de identificación de malos movimientos. Dos ideas de pre-poda bastante trabajadas variantes fueron los cortes a raz y en vano ("razoring" and "futility" cutoffs). Por ejemplo, si justo antes del horizonte de búsqueda el score está sobre el límite beta del minimax para el bando que juega, cortar inmediatamente (corte al raz). Alternativamente, si el movimiento actual está bajo el límite alfa y los factores posicionales no tienen el potencial para aumentarlo, descontinuar la variante (corte en vano).
Métodos de búsqueda variable como estos fueron refinados para asegurar el control de las extensiones, sobretodo en las búsquedas sin límite (por ejemplo, jaques perpetuos) y en cambios drásticos de equilibro material (por ejemplo en promociones de peón). Como conclusión era clara la necesidad de algún tipo de búsqueda selectiva de profundidad variable.
En los 90 ya estaban bien entendidos los criterios para extender en forma automática la búsqueda, con lo cual el foco de atención se centralizó nuevamente en la búsqueda selectiva con pre-poda (forward pruning), una idea que había sido repetidamente intentada en décadas pasadas pero con resultados contradictorios. Una generalización de las podas de corte de navaja (razoring) y de valor nulo (futility) fue el uso del "`movimiento de paso" en la búsqueda de posiciones estables [32]. La esencia de la tercera etapa de búsqueda es considerar sólo movimientos de captura, algunos jaques y movimientos tácticos que alteran considerablemente el equilibrio material. El uso de un movimiento de paso (que en el fondo significa permitir al adversario mover dos veces) asegura que una amenaza del rival puede ser encontrada más rápidamente. Técnicas de movimiento de paso fueron la pre-poda utilizada en inicios de los 90. La implementación de esta pre-poda con mayor suceso fue desarrollada por Goetsch y Campbell [44].
En el tiempo en que los métodos de "movimiento de paso" (null-move) eran descritos se comenzó a trabajar en otras formas de variar la profundidad de búsqueda. Era claro ya que las respuestas a jaques no debían contar como un movimiento que adelanta un paso al horizonte de búsqueda. para esto, una extensión automática puede realizarse por cada movimiento forzado pero con respuesta única. A principios de los 90 la noción de "Extensiones Singulares" fue introducida e implementada [30]. Movimientos que son sustancialmente mejores que otros de su mismo nivel de búsqueda son analizados con un nivel más de profundidad con tal de reducir el riesgo del efecto horizonte.
En el pasado la búsqueda selectiva fue un método de alto riesgo pero con gran potencial de desarrollo. En la actualidad los métodos de búsqueda variable son un área de desarrollo activo. Recientemente algunos métodos de poda existentes fueron mejorados por Heinz [49], quien los generalizó con tal de realizar podas en niveles por sobre el horizonte mientras que Marsland [58] realizó estudios sobre las búsquedas en nodos factibles de ser podados. Ambos métodos lograron mejoras en el nivel de juego y están siendo empleados por varios de los más fuertes programas de la actualidad.
Con el incremento en espacio de memoria, renovado interés tuvo el desarrollo de algoritmos de búsqueda desechados con anterioridad como el SSS* de Stockman y el B* de Berliner [34] y métodos combinados como el DUAL* [57] los cuales eran computacionalmente eficientes pero lentos de ejecutar.
Los algoritmos desarrollados para este fin han sido variados. La primera propuesta, presentada por Shannon, fue la búsqueda por fuerza bruta a profundidad fija, examinando todas las continuaciones posibles hasta cierto límite de movimientos. Esta búsqueda se realizaría mediante el algoritmo Minimax.
Hasta principios de los 70 los programas de ajedrez seguían basándose en los modelos de Shannon para realizar su proceso de búsqueda. Hasta ese momento el diseño de programas de ajedrez se focalizaba principalmente en el orden de los movimientos con tal de lograr la mejor "poda" de variantes: jaques, capturas, "movidas asesinas", amenazas y avances de peones pasados. Categorizando los movimientos en distintos grupos mediante amenazas tácticas (de corto plazo) o estratégicas (de largo plazo) se podía asegurar el que las variantes "forzadas" serían analizadas primero. Esta técnica lograba generar cortes o reducciones en el árbol de búsqueda para aquellas variantes que se clasificaban como innecesarias de analizar.
También durante la década de 1970 la noción de búsqueda iterativa fue refinada y sometida a prueba. Con un enfoque de completitud y uniformidad las búsquedas eran generalmente hechas a una profundidad fija (en forma iterativa dependiendo del tiempo de reflexión restante). El uso del tiempo para controlar la búsqueda tomó también un carácter de suma importancia, dado que ofrecía la flexibilidad de confirmar si el movimiento encontrado en la anterior iteración era efectivamente el mejor. Esto hizo que de alguna manera la búsqueda selectiva (estrategia "B" de Shannon) cayera en desuso, debido a la dificultad de su implementación en las computadoras.
Resultó que la seguridad de buscar en todos los movimientos posibles otorgó mejores resultados que el descarte de variantes basado en su baja relevancia. La búsqueda selectiva vio prácticamente su muerte en esta década, si bien fue la estrategia líder de los 60 con el programa MackHack, el cual estaba implementado con un selector de movimientos plausibles [46]. A finales de la década los beneficios de la búsqueda de posiciones estables con profundidad variable fue clara, y esto llevó a la preponderancia de los programas de estrategia tipo A los cuales utilizaron búsquedas basadas en distintas etapas.
Con el aumento en la velocidad de los procesadores pudieron realizarse búsquedas más profundas causando a principio de los 80 un interés por realizarlas en etapas. La idea fue realizar una primera búsqueda a profundidad fija de varios movimientos seguida de una búsqueda selectiva y terminando con una búsqueda de posiciones estables a partir de movimientos como capturas o respuestas a jaques. Este modelo de búsqueda demostró ser a la vez bastante robusto. De todas maneras, este tipo de búsqueda en etapas no reflejaba adecuadamente la noción intuitiva de que las extensiones en la profundidad de búsqueda deben ser selectivas en vez de uniformes, aplicándose en variantes forzadas.
Era claro que la extensión de un movimiento debía realizarse cuando uno de los bandos se encontraba en jaque. Un idea similar era extender la búsqueda cuando un jugador tuviera sólo un movimiento legal posible, pero lo que realmente se deseaba buscar era una extensión en situaciones en que cualquiera de los dos jugadores tuviese sólo un movimiento "sensible" (por ejemplo, una captura). Esto implicaba algún tipo de pre-poda con tal de detener la expansión de identificación de malos movimientos. Dos ideas de pre-poda bastante trabajadas variantes fueron los cortes a raz y en vano ("razoring" and "futility" cutoffs). Por ejemplo, si justo antes del horizonte de búsqueda el score está sobre el límite beta del minimax para el bando que juega, cortar inmediatamente (corte al raz). Alternativamente, si el movimiento actual está bajo el límite alfa y los factores posicionales no tienen el potencial para aumentarlo, descontinuar la variante (corte en vano).
Métodos de búsqueda variable como estos fueron refinados para asegurar el control de las extensiones, sobretodo en las búsquedas sin límite (por ejemplo, jaques perpetuos) y en cambios drásticos de equilibro material (por ejemplo en promociones de peón). Como conclusión era clara la necesidad de algún tipo de búsqueda selectiva de profundidad variable.
En los 90 ya estaban bien entendidos los criterios para extender en forma automática la búsqueda, con lo cual el foco de atención se centralizó nuevamente en la búsqueda selectiva con pre-poda (forward pruning), una idea que había sido repetidamente intentada en décadas pasadas pero con resultados contradictorios. Una generalización de las podas de corte de navaja (razoring) y de valor nulo (futility) fue el uso del "`movimiento de paso" en la búsqueda de posiciones estables [32]. La esencia de la tercera etapa de búsqueda es considerar sólo movimientos de captura, algunos jaques y movimientos tácticos que alteran considerablemente el equilibrio material. El uso de un movimiento de paso (que en el fondo significa permitir al adversario mover dos veces) asegura que una amenaza del rival puede ser encontrada más rápidamente. Técnicas de movimiento de paso fueron la pre-poda utilizada en inicios de los 90. La implementación de esta pre-poda con mayor suceso fue desarrollada por Goetsch y Campbell [44].
En el tiempo en que los métodos de "movimiento de paso" (null-move) eran descritos se comenzó a trabajar en otras formas de variar la profundidad de búsqueda. Era claro ya que las respuestas a jaques no debían contar como un movimiento que adelanta un paso al horizonte de búsqueda. para esto, una extensión automática puede realizarse por cada movimiento forzado pero con respuesta única. A principios de los 90 la noción de "Extensiones Singulares" fue introducida e implementada [30]. Movimientos que son sustancialmente mejores que otros de su mismo nivel de búsqueda son analizados con un nivel más de profundidad con tal de reducir el riesgo del efecto horizonte.
En el pasado la búsqueda selectiva fue un método de alto riesgo pero con gran potencial de desarrollo. En la actualidad los métodos de búsqueda variable son un área de desarrollo activo. Recientemente algunos métodos de poda existentes fueron mejorados por Heinz [49], quien los generalizó con tal de realizar podas en niveles por sobre el horizonte mientras que Marsland [58] realizó estudios sobre las búsquedas en nodos factibles de ser podados. Ambos métodos lograron mejoras en el nivel de juego y están siendo empleados por varios de los más fuertes programas de la actualidad.
Con el incremento en espacio de memoria, renovado interés tuvo el desarrollo de algoritmos de búsqueda desechados con anterioridad como el SSS* de Stockman y el B* de Berliner [34] y métodos combinados como el DUAL* [57] los cuales eran computacionalmente eficientes pero lentos de ejecutar.
Generador de Movimientos
La forma inicial de programar un generador de movimientos fue el generar mediante fórmulas matemáticas los movimientos legales de cada pieza sobre el tablero, obteniendo todas las posibilidades con tal de entregárselas como una lista al software de búsqueda. Esta propuesta fue mencionada por vez primera en el paper de Shannon [68] y se aplicó a prácticamente todos los programas de la época.
La idea inicial fue el que el programa generara sólo los mejores movimientos con tal de reducir drásticamente el árbol de variantes (estrategia "B", según la nomenclatura dada por Shannon) pero los resultados distaron de ser positivos puesto que el problema principal relacionado con este proceso fue que en las búsquedas en profundidad esta forma de generar los movimientos tomaba un tiempo excesivo, lo cual hacía muy lento el proceso global, motivo por el cual se buscaron otras formas de programar la generación de movidas en base a operaciones que la computadora pudiese realizar más rápidamente.
Sólo hasta principios de 1970 (gracias a la presencia de hardware y ambientes de desarrollo de mayor capacidad) se utilizó la técnica de los mapas de bits (bit-boards)la cual significó un gran avance en este proceso del juego de la máquina dado que se redujo la complejidad de operaciones a aquellas que son básicas para la máquina. A pesar de este avance, era clara la necesidad de implementar fuera del software esta función del programa, dado que la necesidad de hacer búsquedas más rápidas y profundas se basaba en un generador de alta velocidad, cosa que era muy difícil lograr a nivel de hardware.
Las mejoras en esta función del programa vinieron principalmente del lado del desarrollo de hardware específico para la generación de movimientos. En 1977 el programa "Belle" fue el primero en utilizar circuitos digitales para la generación de movimientos logrando aumentar su velocidad de búsqueda de 200 a 160.000 posiciones por segundo. El generador utilizado en Belle sirvió como punto de partida para máquinas más poderosas. El computador que derrotó a Kasparov en 1997, DeepBlue, tenía 30 procesadores IBM RS-6000 SP acoplados a 480 chips. Esta máquina fue capaz de lograr velocidades computacionales de 200 millones de posiciones por segundo.
Las característica principal de estos generadores a nivel de Hardware es el poder caracterizar a las casillas de origen y destino mediante transmisores y receptores respectivamente, para luego generar mediante un árbol de prioridades los movimientos ordenados de acuerdo a criterios de capturas, jaques, etc. [38]. La principal ventaja entre el generador de movimientos de DeepBlue y BELLE es que el primero solucionó el problema de generar en primer orden los movimientos de jaque.
En la actualidad la utilización de mapas de bits es prácticamente universal en todos los programas de ajedrez. Las mejoras se ven principalmente en los tipos de mapas generados de acuerdo al tipo de movimientos buscados (reglas de mapas de bits). El principal desarrollo en este tema es a nivel de hardware en donde los avances se han visto en el orden de jugadas entregado en la generación de los movimientos. En el último año se han desarrollado también tarjetas de hardware específicas para implementación en computadoras personales (Field Programable Gate Arrays) las cuales han sido utilizadas en forma experimental.
La idea inicial fue el que el programa generara sólo los mejores movimientos con tal de reducir drásticamente el árbol de variantes (estrategia "B", según la nomenclatura dada por Shannon) pero los resultados distaron de ser positivos puesto que el problema principal relacionado con este proceso fue que en las búsquedas en profundidad esta forma de generar los movimientos tomaba un tiempo excesivo, lo cual hacía muy lento el proceso global, motivo por el cual se buscaron otras formas de programar la generación de movidas en base a operaciones que la computadora pudiese realizar más rápidamente.
Sólo hasta principios de 1970 (gracias a la presencia de hardware y ambientes de desarrollo de mayor capacidad) se utilizó la técnica de los mapas de bits (bit-boards)la cual significó un gran avance en este proceso del juego de la máquina dado que se redujo la complejidad de operaciones a aquellas que son básicas para la máquina. A pesar de este avance, era clara la necesidad de implementar fuera del software esta función del programa, dado que la necesidad de hacer búsquedas más rápidas y profundas se basaba en un generador de alta velocidad, cosa que era muy difícil lograr a nivel de hardware.
Las mejoras en esta función del programa vinieron principalmente del lado del desarrollo de hardware específico para la generación de movimientos. En 1977 el programa "Belle" fue el primero en utilizar circuitos digitales para la generación de movimientos logrando aumentar su velocidad de búsqueda de 200 a 160.000 posiciones por segundo. El generador utilizado en Belle sirvió como punto de partida para máquinas más poderosas. El computador que derrotó a Kasparov en 1997, DeepBlue, tenía 30 procesadores IBM RS-6000 SP acoplados a 480 chips. Esta máquina fue capaz de lograr velocidades computacionales de 200 millones de posiciones por segundo.
Las característica principal de estos generadores a nivel de Hardware es el poder caracterizar a las casillas de origen y destino mediante transmisores y receptores respectivamente, para luego generar mediante un árbol de prioridades los movimientos ordenados de acuerdo a criterios de capturas, jaques, etc. [38]. La principal ventaja entre el generador de movimientos de DeepBlue y BELLE es que el primero solucionó el problema de generar en primer orden los movimientos de jaque.
En la actualidad la utilización de mapas de bits es prácticamente universal en todos los programas de ajedrez. Las mejoras se ven principalmente en los tipos de mapas generados de acuerdo al tipo de movimientos buscados (reglas de mapas de bits). El principal desarrollo en este tema es a nivel de hardware en donde los avances se han visto en el orden de jugadas entregado en la generación de los movimientos. En el último año se han desarrollado también tarjetas de hardware específicas para implementación en computadoras personales (Field Programable Gate Arrays) las cuales han sido utilizadas en forma experimental.
Suscribirse a:
Comentarios (Atom)