Uso de módulos de ajedrez para estimar las habilidades humanas

08/12/2011 – En juegos y deportes, los sistemas de clasificación por puntuación están ampliamente aceptados como método para estimar la fuerza relativa de los contendientes. Se basan únicamente en el resultado de las competiciones directas. Matej Guid e Ivan Bratko, de la Universidad de Liubliana, proponen un enfoque distinto: establecer el nivel de pericia ajedrecístico con la aplicación de módulos de ajedrez que examinen las posiciones y movimientos realizados. Les ofrecemos un resumen de sus interesantes estudios académicos en un artículo traducido al castellano...

ChessBase 14 Download ChessBase 14  Download

Programa de gestión de bases de datos de ajedrez que es referencia mundial. Todos usan ChessBase, desde el campeón del mundo al aficionado. Inicie su historia de éxito personal con ChessBase.

Más información...

Jueves, 8 de diciembre de 2011

Uso de módulos de búsqueda heurística para estimar las habilidades humanas en el ajedrez

Por Matej Guid e Ivan Bratko

Universidad de Liubliana
Facultad de Informática y Ciencias de la Información
Laboratorio de Inteligencia Artificial
Liubliana (Eslovenia)

Este artículo se basa en un trabajo de los mismos autores publicado en el ICGA Journal cuya referencia completa se cita más abajo.

En 2006 llevamos a cabo una comparación con ordenadores de los campeones mundiales de ajedrez

Analizamos las jugadas efectuadas en duelos por el título mundial con el programa de ajedrez CRAFTY, para intentar evaluar objetivamente un aspecto de la fuerza de juego de ajedrecistas de distintas épocas. El criterio básico de comparación entre los jugadores era la desviación de sus jugadas con respecto a las jugadas del ordenador. Más precisamente, consideramos la desviación media entre las valoraciones de los ordenadores de los movimientos jugados por los humanos y los preferidos por la máquina. También diseñamos un método para medir la complejidad de una posición para tener en cuenta los distintos estilos de juego de los ajedrecistas y la dificultad de las posiciones que afrontaron.

Mucha gente encontró sorprendentes los resultados. Por ejemplo, Capablanca salió como el mayor anotador según el criterio principal del análisis. Una reserva sobre esos resultados fue: ¿era Crafty, cuya puntuación no es más que 2620, lo suficientemente fuerte para unas comparaciones tan exigentes? ¿Que pasaba si se usaba un programa más exigente? Ofrecemos aquí algunos resultados de dos estudios más (Guid et al. 2008; Guid y Bratko 2011) que son relevantes sobre estos temas. Esos resultados, que incluyen análisis con los programas SHREDER, RYBKA 2 y RYBKA 3, pueden resumirse en lo que sigue:

  • Al repetir nuestros análisis anteriores de los campeones de ajedrez, los resultados obtenidos con uno de los programas más fuertes, RYBKA 3 fueron cualitativamente muy similares a los logrados con CRAFTY.

  • El escalafón aproximado de los jugadores según los distintos programas es bastante estable. Más concretamente, dados dos ajedrecistas, o bien todos los programas  unánimemente sitúan a uno por encima del otro o todos los programas valoran que sus fuerzas son similares.

  • Para obtener un escalafón acertado de los jugadores según el criterio considerado, no es necesario usar un ordenador que sea más fuerte que los propios jugadores. Resulta interesante ver como programas considerablemente más débiles tienden de forma consistente a producir escalafones similares.

Introducción

El objetivo de nuestro análisis informático de las jugadas de los duelos por el campeonato mundial era determinar tan objetivamente como fuese posible un aspecto de la fuerza de juego de los ajedrecistas de distintas épocas. Se usó el programa de ajedrez de código abierto CRAFTY. Entre los diversos criterios considerados, el criterio básico para comparar entre jugadores fue la desviación media entre las valoraciones del ordenador de los movimientos jugados por humanos y aquellos preferidos por la máquina.

Los análisis estadísticos subsiguientes (2008) demostraron que, al menos para pares de jugadores cuyas puntuaciones diferían significativamente, no es muy probable que los puestos relativos en el escalafón de campeones según el criterio considerado fuesen a cambiar  si (1) se usase un programa de ajedrez más fuerte  o (2) si el programa calculase con más profundidad o (3) si se dispusiese de un número mayor de posiciones para analizar. En el presente artículo verificamos aún más las proposiciones (1) y (2) empíricamente al aplicar tres programas de ajedrez más fuertes que CRAFTY al mismo tipo de análisis informático de las habilidades de los jugadores.

También repetimos nuestros análisis con el programa CRAFTY de los campeones mundiales con uno de los programas más fuertes de la actualidad, RYBKA 3 y obtuvimos resultados cualitativamente muy similares a los de CRAFTY (haga clic si tiene mucha curiosidad y quiere ver los resultados del análisis informático con RYBKA 3 inmediatamente)

¿Misión imposible?

Usar programas de ordenador para estimar las habilidades de los ajedrecistas puede parecer imposible, ya que es de sobra conocido que tanto las valoraciones de los programas como las decisiones de los programas tienden a cambiar a medida que aumenta la profundidad de búsqueda. Además, los distintos programas suelen valorar de diferente manera un posición dada, incluso cuando usan la misma profundidad de búsqueda. Por lo tanto, ¿cuál es el programa más fiable como estimador: el más fuerte en la competición con otros programas o quizás el que sea el más igualmente injusto con todos los jugadores sujetos a evaluación?

 

Programa Valoración
Chessmaster 10
0.15
Crafts 19.19
0.20
Crafty 20.14
0.08
Deep Shredder 10
-0.35
Deep Shredder 11
0.00
Fritz 6
-0.19
Fritz 11
0.07
Rybka 2.2n2
-0.01
Rybka 3
-0.26
Zappa 1.1
0.13

Lasker-Capablanca (San Petersburgo, 1914), posición tras la jugada 12 de las blancas. La tabla de la derecha muestra las valoraciones heurísticas obtenidas con diversos programas de ajedrez, con una profundidad de 12 ply.

Todos los aspectos comentados parecen obstáculos en el camino para establecer métodos basados en la búsqueda heurística como estimadores válidos de las capacidades humanas, especialmente en juegos complejos como el ajedrez.

En la presente investigación, facilitamos un análisis de las diferencias entre los programas basados en búsquedas heurísticas para estimar la habilidad ajedrecística usando un enfoque similar al empleado en nuestros anteriores estudios (2006-2008). Estamos particularmente interesados en analizar el comportamiento de distintos programas de ajedrez y hasta que punto las puntuaciones y los escalafones de los jugadores se mantienen con distintas profundidades de búsqueda. Dado que la fuerza de los programas de ajedrez aumenta con la profundidad de búsqueda, el mantenimiento de los escalafones a diferentes profundidades de búsqueda por lo tanto sugeriría no solo que se han obtenido los mismos resultados al buscar con mayor profundidad, sino que el uso de programas más fuertes probablemente no afectaría significativamente a los resultados.

En la segunda parte presentamos algunos de los resultados de las siguientes  publicaciones científicas:

  • M. Guid y I. Bratko. Using Heuristic-Search Based Engines for Estimating Human Skill at Chess. ICGA Journal, Vol. 34, No. 2, pp. 71-81, 2011.
  • M. Guid, A. Pérez y I. Bratko. How Trustworthy is CRAFTY's Analysis of World Chess Champions? ICGA Journal, Vol. 31, No. 3, pp. 131-144, 2008.

Los lectores interesados encontrarán  más abajo más abajo los enlaces con ambas publicaciones.

Para evitar posibles malinterpretaciones del trabajo presentado, debe advertirse que estos artículos no se refieren a la cuestión de lo adecuada que es la medida concreta de la fuerza de juego (desviación de las jugadas de los ajedrecistas con respecto a los movimientos preferidos por el ordenador, empleando una muestra lo bastante grande de posiciones para el análisis informático) como criterio para comparar la habilidad de los ajedrecistas en general. Es uno solo de los muchos criterios razonables de este tipo. No obstante creemos que el relativamente buen mantenimiento de los escalafones con distintas profundidades de búsqueda empleando varios programas de distinta fuerza competitiva puede representar un sólido cimiento en el camino para descubrir métodos cada ves mejores de establecer los programas de ordenador basados en la búsqueda heurística como estimadores fiables de los niveles de pericia en el juego.

¿Qué pasaría se se usase un programa MÁS DÉBIL que Crafty (a 12-ply) para el análisis informático de los campeones?

Hubo diversos debates sobre nuestro artículo de 2006 en distintos blogs y foros populares en Internet y ChessBase pronto publicó algunas respuestas interesantes de varios lectores de todo el mundo, incluyendo algunos científicos. Un comentario frecuente de los lectores podría resumirse así: "Un estudio muy interesante, pero tiene un punto débil ya que el programa CRAFTY, cuya puntuación solo es de unos 2620, se empleó para analizar el rendimiento de jugadores más fuertes que él. Por ese motivo, los resultados no pueden ser útiles". Algunos lectores continuaban especulando más, añadiendo que el programa clasificaría mejor a los jugadores que tuviesen una fuerza similar al propio programa.

Las dos objeciones principales a la metodología empleada eran: (1) que el programa usado para el análisis era demasiado débil y (2) que la profundidad de búsqueda de 12 plies hasta la que investigaba el programa, era demasiado superficial.

Encaramos esas objeciones para establecer la fiabilidad de CRAFTY (o, por extrapolación, cualquier otro falible programa de ajedrez) como herramienta de comparación de ajedrecistas empleando la metodología sugerida. En particular, estábamos interesados en observar hasta donde se mantenían las puntuaciones y los escalafones de los jugadores con distintas profundidades de búsqueda. Primero observamos los escalafones de los campeones elaborados con CRAFTY con las menores profundidades de búsqueda.

En cada posición, realizamos búsquedas cuya profundidad iba desde 2 a 12 plies con quiescencia para asegurar unas valoraciones estáticas estables. Las valoraciones almacenadas de cada una de esas búsquedas se emplearon para los análisis. PV significa variante principal.

Llevamos a cabo investigaciones a distintas profundidades (incluyendo la búsqueda quiescente para obtener valoraciones estables). Luego las puntuaciones obtenidas por el programa son las diferencias medias entre las valoraciones del ordenador de las jugadas escogidas por los ajedrecistas y las preferidas por el ordenador a una profundidad de búsqueda determinada. En función de las puntuaciones de los jugadores, se ordenaron los ajedrecistas, de forma que una menor puntuación implicaba un puesto mejor. Las limitaciones adicionales y otros detalles sobre la metodología empleada se describen en nuestra publicación en el ICGA Journal (2008).

Los análisis del ordenador se basaron en la valoración de las partidas jugadas por los campeones de ajedrez en los duelos clásicos por el campeonato mundial entre 1886 (Steinitz-Zukertort) y 2006 (Kramnik-Topalov). Por lo tanto se incluyeron en el análisis los siguientes catorce campeones: Steinitz, Lasker, Capablanca, Alekhine, Euwe, Botvinnik, Smyslov, Tal, Petrosian, Spassky, Fischer, Karpov, Kasparov y Kramnik.

Nuestros resultados muestran, posiblemente de manera sorprendente, que al menos para los jugadores cuyas puntuaciones difieren suficientemente de las de los demás el escalafón se mantiene incluso con profundidades de búsqueda muy someras.

Las puntuaciones de CRAFTY (desviaciones medias entre las valoraciones de las jugadas realizadas y las consideradas mejores según CRAFTY) de cada campeón mundial "clásico" (1886-2006) a diferentes profundidades de búsqueda. Se resaltan las puntuaciones de Capablanca (curva inferior), Kramnik, Euwe y Steinitz (curva superior).

Algunos campeones cuyos puestos se desvían significativamente de los demás fueron identificados: Capablanca, Euwe y Steinitz. Sus puestos relativos entre todos los campeones se mantuvieron en todos los niveles de búsqueda. La estabilidad de sus posiciones se corroboró aún más con el análisis estadístico de los resultados y por el hecho de que Capablanca tuviera la mejor puntuación en el 95 % de todo el subconjunto de combinaciones profundas en 100 muestras que consistían en 500 posiciones escogidas al azar. Como hicimos en nuestro estudio, este resultado debería interpretarse a la luz del estilo de juego de Capablanca que tiende a posiciones de baja complejidad.

Uso de programas más fuertes para el análisis

Para estudiar si diferentes programas basados en la búsqueda heurística pueden usarse como estimadores de niveles de habilidad, nos centraremos ahora en esos tres jugadores y comprobaremos si otros programas de ajedrez los clasifican en el mismo orden que CRAFTY. Observaremos variaciones con la profundidad de las diferencias medias entre las decisiones del ajedrecista y del programa en un gran conjunto de posiciones escogidas al azar de los duelos por el campeonato del mundo de ajedrez usando tres programas de ajedrez más fuertes que CRAFTY, a saber: SHREDDER, RYBKA 2 y RYBKA 3.

Todas las posiciones para los análisis fueron tomadas de encuentros por los campeonatos del mundo (1886-2006). Además de analizar las jugadas de los tres ajedrecistas, también escogimos al azar más de 20.000 posiciones del resto de jugadores como grupo de control.

Las puntuaciones de Capablanca (curva inferior), el grupo de control, Euwe y Steinitz (curva superior), obtenidas con un subconjunto de partidas grande de los encuentros por el título mundial usando SHREDDER.

Las puntuaciones de Capablanca (curva inferior), el grupo de control, Euwe y Steinitz (curva superior), obtenidas con un subconjunto de partidas grande de los encuentros por el título mundial usando RYBKA 2.

Las puntuaciones de Capablanca (curva inferior), el grupo de control, Euwe y Steinitz (curva superior), obtenidas con un subconjunto de partidas grande de los encuentros por el título mundial usando RYBKA 3.

El puesto relativo de Capablanca, Euwe, Steinitz y los jugadores del grupo de control se mantuvo con todas las profundidades usando cualquiera de los programas a cualquier nivel de búsqueda. Estos hallazgos experimentales rechazan posibles especulaciones según las cuales el uso de programas de ajedrez más fuertes que CRAFTY para los análisis podría llevar a resultados completamente distintos y que los resultados de Capablanca son una mera consecuencia de que su estilo es similar al de CRAFTY. También vimos estos resultados como otra confirmación de que para obtener una clasificación razonable de ajedrecistas no es necesario usar un ordenador que sea más fuerte que los propios jugadores .

 Análisis informático de los campeones mundiales revisado con RYBKA 3

Presentamos los resultados del análisis informático de los campeones del mundo de ajedrez obtenidos por RYBKA 3. Analizamos los mismos duelos que en 2008, para comparar los resultados obtenidos por los programas de ajedrez CRAFTY y RYBKA 3 de manera tan relevante como fuera posible. Es decir fueron seleccionadas para el análisis partidas por el título mundial en las que los catorce campeones del mundo clásicos (de Steinitz a Kramnik) luchaban por el título o lo defendían. Los detalles de la metodología se dan en la publicación 2011. Las búsquedas a 11 y 12 plies se omitieron para acortar el tiempo de procesamiento necesario para unos análisis tan extensos.

Las puntuaciones de RYBKA (desviaciones medias entre las valoraciones de las jugadas realizadas y las mejores según RYBKA 3) para todos los campeones mundiales "clásicos" (desde 1886 a 2006) con diferentes profundidades de búsqueda. Se destacan las puntuaciones de Capablanca (curva inferior), Kramnik, Euwe y Steinitz (curva superior). En función de las puntuaciones de los jugadores, se obtiene un escalafón de los jugadores, de forma que la curva más baja supone la mejor posición en el escalafón.

Veámoslo con más detalle:

Una vista más detallada: las puntuaciones de los campeones obtenidas por el programa de ajedrez RYBKA 3 con varias profundidades de búsqueda. Para casi todas las profundidades se mantiene el que puesto(Capablanca) < puesto(Kramnik) < puesto(Kasparov) < puesto(Karpov) < puesto(Petrosian) < puesto(Botvinnik) < puesto(Euwe) < puesto(Steinitz).

Los resultados se asemejan mucho a aquellos obtenidos por CRAFTY (2008). De nuevo los puestos se mantienen en casi todas las profundidades:  puesto(Capablanca) < puesto(Kramnik) < puesto(Kasparov) < puesto(Karpov) < puesto(Petrosian) < puesto(Botvinnik) < puesto(Euwe) < puesto(Steinitz) Sin embargo, hay no obstante algunas diferencias evidentes entre los resultados obtenidos por los dos programas.

Primeramente, CRAFTY situó a Karpov mejor que a Kasparov en todas las profundidades; justo al revés que RYBKA 3. No obstante las puntuaciones de ambos (y también las de otros muchos) jugadores son bastante similares.

El segundo lugar, el rendimiento de Fischer tal y como lo ve RYBKA 3 es significativamente mejor en comparación con los resultados obtenidos por CRAFTY. Este hallazgo está asociado con la siguiente (hasta ahora sin respuesta) cuestión: ¿hace el estilo de juego de un programa que éste tenga preferencia por algún jugador concreto? La comparación de los resultados de los análisis informáticos de los campeones obtenidos por CRAFTY y RYBKA 3 sugieren que el estilo de juego del programa puede afectar a los escalafones, pero sólo con un alcance limitado.

El significado de las puntuaciones

Una frecuente pregunta de los lectores estaba asociada con el significado de las puntuaciones de los jugadores obtenidas por el programa. Una típica interpretación errónea de su significado era del estilo de la siguiente: "Para cada 8 movimientos de media, CRAFTY espera lograr una ventaja de un peón sobre Kasparov". Nos gustaría destacar aquí que las puntuaciones logradas por el programa sólo miden las diferencias medias entre las elecciones de jugada de los ajedrecistas y las elecciones del ordenador. Sin embargo, ya que el análisis muestra que estas puntuaciones dependen del ordenador usado tienen buenas opciones de generar escalafones razonables de los jugadores.

Los resultados experimentales no sólo confirman que las puntuaciones no son invariables para el mismo programa a diferentes profundidades de búsqueda, las puntuaciones también difiere significativamente al usar distintos programas. Esto se puede ver claramente en el siguiente gráfico, donde se muestran las puntuaciones medias de todos los jugadores obtenidas en el mismo conjunto de partidas de duelos por el campeonato mundial  para los tres programas y se comparan con las puntuaciones medias de todos los jugadores según  CRAFTY. Mientras que las puntuaciones de SHREDDER son bastante similares a las puntuaciones de CRAFTY, las puntuaciones de los dos RYBKA difieren considerablemente de aquellas de los otros los programas.

Comparación de la media de puntuaciones de todos los jugadores (incluyendo los del grupo de control)
obtenidas por CRAFTY, SHREDDER, RYBKA 2, and RYBKA 3.

En la publicación 2011, facilitamos la siguiente explicación con respecto a la magnitud de las puntuaciones en relación con la profundidad de búsqueda. La tendencia decreciente de las puntuaciones a medida que aumenta la profundidad de búsqueda (típica en profundidades de búsqueda menores) es una consecuencia de las elecciones del programa cada vez mejores. A mayores profundidades de búsqueda, sin embargo, el mayor coste de no escoger la mejor jugada según el programa puede incluso conllevar un aumento de puntuación debido a la propiedad de monotonía de las funciones de evaluación heurística.  Es decir, en posiciones ganadas las valoraciones de los programas tienden a aumentar monótonamente con la profundidad de búsqueda.

¿A dónde ir a partir de aquí?

Nuestro enfoque para estimar los niveles de pericia apunta a establecer la calidad del juego independientemente del resultado de la partida e implica el uso de estimadores falibles (en contraposición a los estimadores infalibles, como las tablas de finales). Desde nuestro trabajo de 2006, han aparecido varios trabajos científicos interesantes relacionados. Haworth (2007) definió un mapeado de la aparente habilidad del jugador en un Espacio Agente de Referencia, usando un agente estocástico y un método de inferencia bayesiana. Los resultados de los análisis experimentales con ese enfoque (Di Fatta, Haworth y Regan, 2009; Haworth, Regan y Di Fatta, 2010; Regan y Haworth, 2011) mostraron que las distribuciones de probabilidad inferidas de las habilidades aparentes son capaces de discriminar los rendimientos de los jugadores en distintos rangos de Elo. Estos resultados hablan más en favor de una posibilidad de estimar las habilidades humanas basada en valoraciones heurísticas informáticas. Se dan referencias completas de estas publicaciones más abajo.

Estos dos enfoques para estimar los niveles de pericia en juegos complejos tienen algo en común, además de que se basan en análisis informáticos de las acciones de los jugadores: ambos asumen (implícita o explícitamente) que las diferencias medias en las valoraciones informáticas entre los movimientos de los jugadores y los movimientos del ordenador aportan una base sólida para una razonable clasificación de los jugadores cuando se dispone de una cantidad de datos suficientemente grande. Es decir, sin contar con como se refine luego esa medida para tener en cuenta el contexto completo de las decisiones del jugador, esas diferencias medias por si solas tienen buenas posibilidades como medidas bastante estables del rendimiento, incluso cuando se usan distintos programas como estimadores de las habilidades de los jugadores.

Una destacable cantidad de procesamiento informático para análisis por ordenador similares de los campeones de ajedrez fue efectuado por Charles Sullivan. Según el autor, durante 24 horas al día, durante 15 meses (desde febrero de 2007 hasta mayo de 2008), 12 flujos de computación (en 3 ordenadores con procesadores Intel de cuatro núcleos Q6600 a 3.0 GHz) analizaron las partidas de los campeones mundiales. Se analizaron todas sus carreras como jugadores; en total fueron proicesadas 617.446 posiciones de 18.785 partidas. Los resultados están publicados en Truechess.com. El autor considera que las estadísticas del "mejor periodo de 10 años" son útiles para seleccionar al "más ajedrecista más grande de todos los tiempos". Los escalafones que obtuvo fueron algo distintos de los nuestros. Sin embargo, estos resultados no pueden compararse directamente porque su análisis incluía TODAS las partidas jugadas, pero limitadas al periodo de los 10 mejores años. También debería tenerse en cuenta que en sus análisis la cantidad de procesamiento de cada posición estaba limitada por el tiempo y no por la profundidad. Así las diferencias medias entre las elecciones de los jugadores y las del ordenador en el análisis de Sullivan fueron obtenidas con distintos niveles de profundidad de búsqueda y no pueden ser comparables directamente, debido a la propiedad monótona de las funciones de evaluación heurísticas (para una explicación detallada véase la tesis doctoral de Matej Guid, capítulo 8.5.1). Recomendamos totalmente emplear profundidades de búsqueda fijas para este tipo de análisis informático de partidas de ajedrez.

Uno de los temas importantes (y todavía no resuelto completamente) es: ¿cómo tener en cuenta las diferencias entre jugadores en la dificultad media de las posiciones encontradas en sus partidas? En 2006, concebimos un método de búsqueda heurística para establecer la dificultad media de las posiciones empleadas para estimar el rendimiento de los campeones y presentamos los resultados de aplicar este método para comparar ajedrecistas de distintos estilos de juego. Aquellos resultados sugerían que la destacada puntuación de Capablanca en términos de poca diferencia entre los movimientos del jugador y los del ordenador debería interpretarse a la luz de su estilo de juego, que tendía hacia posiciones de baja complejidad. Sin embargo, creemos que se necesita más trabajo sobre esa cuestión.


Los autores

Matej Guid ha recibido su doctorado en informática por la Universidad de Liubliana (Eslovenia) Su interés investigador incluye los juegos informáticos, las explicaciones automatizadas y los sistemas guía, la búsqueda heurística y el aprendizaje de las máquinas basado en razonamientos. Algunos de sus trabajos científicos, entre los que está su tesis doctoral titulada Search and Knowledge for Human and Machine Problem Solving, están disponibles en la página de investigación de Matej. El ajedrez ha sido uno de los pasatiempos preferidos de Matej desde su niñez. También fue un par de veces campeón juvenil de Eslovenia y tiene el título de Maestro FIDE.

Ivan Bratko es profesor de informática en la Universidad de Liubliana (Eslovenia) Dirige el Laboratorio de Inteligencia Artificial de la Facultad de Ciencias Informáticas de la Universidad de Liubliana y ha dirigido investigaciones sobre aprendizaje de las máquinas, sistemas expertos, modelos cualitativos, robótica inteligente, programación heurística y ajedrez informático (¿Conocen el famoso test Bratko-Kopec?) El profesor Bratko ha publicado más de 200 trabajos científicos y diversos libros incluyendo el muy vendido Prolog Programming for Artificial Intelligence. El ajedrez es uno de sus pasatiempos favoritos.

Referencias

Copyright Guid/Bratko/ChessBase


Discussion and Feedback Join the public discussion or submit your feedback to the editors


Comentar

Normas sobre los comentarios

 
 

¿Aún no eres usuario? Registro