La dificultad del ajedrez cronometrado

Una de las grandes diferencias en el juego de ajedrez entre los humanos y las máquinas es que las máquinas no sienten pánico ni se estresan.

Por razones que ya hemos explicado antes mientras más tiempo tenga una computadora para “pensar” mejor va jugar, y esto es independiente de si es un segundo, 10 o 100. Sin embargo con los humanos esto es muy distinto, podemos tener tres minutos para hacer una jugada y debido a que no somos una máquina sino estamos entrenados para eso pensaremos distinto debido al límite que si este no existiera…

Veamos un ejemplo:

Supongamos que de repente tenemos que jugar y tenemos 15 segundos para decidir, independientemente de si somos novatos o grandes maestros si tenemos poco tiempo estamos propensos a cometer errores. Sin embargo si tuviéramos todo el tiempo que quisiéramos para pensar la jugada, probablemente no haríamos lo mismo. Esto es similar al problema del horizonte que tienen los algoritmos del ajedrez.

A diferencia de las computadoras, si tuviéramos más tiempo no necesariamente jugaremos mejor, esto debido a la presión del tiempo. Cuando una computadora tiene 15 segundos más para decidir no se pone a contemplar si es buena idea la jugada que hizo por tercera vez o: “demonios, se acabando el tiempo que hago” simplemente es más tiempo para el algoritmo.

Entonces para los humanos el problema no está en la parte lógica del ajedrez, sino en el preámbulo, el contexto, el lado psicológico el juego, para algunas personas añadir la variable del tiempo es demasiado y los convierte de buenos jugadores a pésimos.

Me ha tocado ver partidas de ajedrez cronometrado donde un jugador vence al otro por paliza, en contraste esos mismos jugadores tienen partidas más cortas donde el jugador derrotado suele ganar la mayoría incluso en tiempo menor que el reglamentado en una partida de ajedrez cronometrado.

 

 

Zugzwangs y motores de ajedrez

Los humanos aun vencen a las computadoras en ajedrez en unas pocas situaciones, en detectar algunos zugzwang es el principal ejemplo(para quien no lo sepa un zugzwang es una posición donde sin importar que movimiento hagas tu situación empeora). Esto tiene que ver en como evalúan los motores de ajedrez, primero veamos un ejemplo:

En un movimiento las blancas pueden forzar un Zugzwang a las negras, el movimiento no es totalmente trivial sin embargo tampoco es muy complicado para un jugador experto o incluso alguien medianamente experimentado (1.Rh6!! y las negras están obligadas a empeorar su posición). La razón de esto tiene mucho que ver con las heuristicas y el horizonte que le asignemos a cada una.

El Zugzwang anterior causa problemas en Stockfish 6, uno de los motores de ajedrez mas fuertes(si no el mas fuerte) debido a una de sus estrategias llamada “Null move pruning” en pocas palabras lo que hace esto es corta muchas posibilidades del árbol de búsqueda para revisar jugadas mas interesantes, el problema principal con esto es que posiciones como estas fallan en ser detectadas. La explicación de esto es un poco mas complicada, para entenderla primero veamos que es un “Null move” o movida nula.

Una movida nula en los motores de ajedrez es dejar el tablero igual y ver si esto genera un cambio para revisar si esto altera una parte de la función de evaluación o seguir con ella deja las cosas igual. Algo tan sencillo tiene repercusiones importantes en las jugadas analizadas ya que podemos tener muchas movidas nulas, “Null move pruning” se dedica a cortar movidas nulas y al no ser analizadas esto mejora la eficiencia en un 99.99% de los casos conocidos.

Como ya habrán adivinado en el 0.01% restante se encuentran los Zugzwang, aquí esta otra posición donde Stockfish 6 falla en ver el mate:

1.Kg7 Bh2 2.Kg6 Bg1 3.Kf5 Bh2 4.Ke5 Bg1 5.Kd4 Bh2 6.Ke3 Bg1 7.Ke2 Bh2 8.Kf1 Bg1 9.Kxg1 Nh3+ 10.Kf1 Nf2 11.Ke2 Nd3 12.Bxe4# aunque siendo justos yo tampoco lo encontre y tuve que revisar la respuesta

Hay que mencionar que no solo Stockfish tiene este tipo de fallas por ejemplo, si le ponemos esta posición a Komodo 4:

No puede encontrar el mate(cabe notar que esto ya fue arreglado en una versión posterior) errores de este estilo los podemos encontrar en todos los motores de ajedrez excepto en los “Mate Finder”(Programas para encontrar jaque mates) que están hechos precisamente para evitar que se les escape estas jugadas. Pero a gran costo de elo en el resto de las posiciones. Para dar un ultimo ejemplo veamos la siguiente jugada:

Dejando de lado la probabilidad de que nos toque un juego así(0%) la posición es interesante debido a que muchos motores fallan en detectar el zugzwang y la manera de ganar la partida(1. h3 gana, 1. h4 empata) para quien quiera ver el desenlace ponga esta posición en Houdini 15a que ve el mate correctamente, esta posición también es muy interesante debido a que otros motores como Toga II consideran que h4 da la victoria cuando en realidad es un empate. Cada motor tiene sus pequeñas fallas y como es de esperarse en cuanto se descubren se tienden a arreglar. Lo interesante de los zugzwang es que siguen siendo un gran problema para los motores de ajedrez aun después de mucho tiempo que se detecto el problema.

El problema del horizonte en el ajedrez

El problema del horizonte es un problema muy conocido en inteligencia artificial, si bien cuando nos lo mencionan pensamos en el en el sentido cosmológico en el sentido computacional y ajedrecista nos referimos a que tanto podemos revisar.

Ya sabemos que es imposible revisar todas las posibles combinaciones a profundidad máxima y que un motor de ajedrez funciona en base a heuristicas ahora la pregunta es ¿Qué tanto revisan estas heuristicas?

Por dar un ejemplo mas facil de entender hay algunos mates en donde se ofrece un sacrificio de reina, y si el oponente lo toma es jaque mate unas cuantas jugadas después.

Supongamos que las blancas ofrecen un sacrificio de reina y que si el negro lo toma es mate en 4 jugadas. ¿Que pasa si pensamos los siguientes 3 movimientos solamente? ¿Y que tal si revisáramos los siguientes 4?

Como humanos si es que vimos que nos ofrecen la reina probablemente si estamos jugando contra un jugador experimentado pensaremos que nos esta colocando una trampa o que cometió un error muy grave. Y probablemente revisaríamos mas a detalle queramos o no.

Para una computadora que solo revisa 3 movimientos adelante según su función de evaluación tendría que en las próximas 3 jugadas tendría una ventaja de una reina y la tomaría. Sin tener idea que una jugada mas y es jaque mate.

Un ejemplo relacionado(sin el sacrificio) seria el mate del pastor, ya que después de 3 jugadas todo parece normal y en la 4 es jaque mate.

Pero si la computadora revisara 4 jugadas adelante descubriría que ganar la dama es solo temporal y que 4 jugadas después estaría destinada a perder el juego.

Este es un ejemplo muy sencillo del problema del horizonte pero esto ocurre todo el tiempo, En si se reduce a ¿Qué tantas jugadas de profundidad revisar? Claramente las que conducen a jaque mate de nuestro rey se descartan inmediatamente, pero ¿Y si perder una reina nos da la victoria 10 jugadas después? ¿Y si dar un peón de ventaja temporalmente nos lleva a recuperar 2 peones 15 jugadas después? Claro que valdría la pena revisarlo.

Viéndolo desde el otro lado, ¿Cuando vale la pena dejar de revisar?

Supongamos que tenemos la siguiente posicion y que nos toca mover: 

¿Cuantas jugadas de peones valdría la pena analizar? Cualquiera que haya jugado mas de 10 o 15 juegos sabría que la respuesta es 0 ya que cualquier jugada que no sea mover la reina nos lleva a perderla sin ganar nada a cambio.

Las heuristicas en el ajedrez funcionan asignando distintos horizontes de búsqueda dependiendo al conjunto de reglas del motor de ajedrez, entonces el problema del horizonte se vuelve un poco mas complejo, ya que no tenemos un horizonte si no muchos.

Por supuesto que esto es preferible, ya que si no solo seria una fuerza bruta recortada a profundidad X donde X seria el numero máximo de jugadas a buscar.

Un poco de historia del ajedrez

Historia del Ajedrez

En un serie de post siguientes pondré una historia detallada del ajedrez por computadora, pero antes de eso toca dar un poco de historia sobre el juego mismo.

Primero que nada hay que aclarar que sus orígenes no son del todo claros, probablemente su predecesor mas antiguo fue en la india. Pero no podemos saber con certeza, probablemente se perdió todo lo relacionado a sus orígenes. El primer lugar donde se tiene registro es en el Imperio Gupta. Su predecesor se llamaba Chaturanga, este se origino en el siglo VI. También según la Wikipedia en ingles(en español no aparece) en el Imperio Kushán alrededor de 200 – 50 AEC(a. C.) han podido rastrear los inicios tempranos del ajedrez.

Para no repetir la historia de Wikipedia solo mencionare que “Shāh Māt!” es persa para el rey esta indefenso. Y Shāh es rey, han existido distintos tipos de piezas a lo largo de la historia del ajedrez, pero esa parte de la historia del ajedrez la detallare en otro post. De ahí se expandió a Persia, al mundo Arabe, a Asia y Europa.

Finalmente en el siglo XV se tiene al ajedrez como es ahora, es a partir de este punto donde tenemos el ajedrez como es actualmente. Como mencione en un post anterior las piezas no siempre se han movido igual. En el siglo VIII seria imposible el mate del loco fue en este momento donde se cambiaron las reglas para que la dama y el alfil se movieran como actualmente. Y a partir de ese momento es donde “Comienza” el ajedrez moderno, hago esta distinción porque un pequeño cambio en retrospectiva parece no ser muy importante pero ¿Qué tal si mañana los peones se pudieran mover 2 lugares en lugar de uno? ¿Que tal que ahora los peones capturaran las piezas que tienen adelante también?

Dejando de lado que nos dificultaría el juego a los que lo hemos jugado por un buen tiempo, pues seria un juego con el mismo nombre, se podría llamar una variante, pero es claro que no es el mismo juego si nos cambian una regla así de importante es como si de repente nos pusieran a jugar con amazonas(Combina los poderes de la dama y el caballo. También llamada superdama) en lugar de reinas o cualquiera de las variedades de el ajedrez de piezas magicas. Ciertamente hace el juego mas divertido cambiar esas reglas un poco de vez en cuando, pero ya no es el mismo juego.

En 1749, el primer libro de gran importancia llamado “L’analizar des échecs” fue escrito. Su importancia es debido a que la manera en la que describe las cosas se mantiene hasta la actualidad; fue escrito por Philidor quien fue el mejor jugador en ese siglo. Un siglo después en 1851 se celebro el primer campeonato de ajedrez. Y en 1914 se creo la FIDE.

Hasta que en 1950 Claude E. Shannon publica su articulo: “Programming a Computer for Playing Chess” que hasta el día de hoy sigue siendo un referente de suma importancia para cualquiera interesado en el ajedrez por computadora, hasta este punto las computadoras habían sido de importancia marginal. Luego en 1953 Turing publica su articulo sobre ajedrez titulado “Chess”. En estos 2 artículos y algunos otros relacionados me centrare mas en futuros post. Pues son claves para entender como es que las computadoras ya juegan ajedrez mucho mejor que los humanos.

Por supuesto quien quiera leer mas detallado todo la Wikipedia le sera de utilidad.
http://es.wikipedia.org/wiki/Historia_del_ajedrez
Historia del ajedrez libro de Murray

Aprende Ajedrez con el Gran Maestro Bobby Fischer

Uno de los mejores libros para principiantes que he visto se llama “Bobby Fischer Enseña Ajedrez”. Antes que nada el link de descarga: https://e-nautia.com/chessnet/disk?p=5587108

Este libro es interesante por muchas razones, la primer es que uno de los coautores es Bobby Fischer que es de los mejores ajedrecistas que han existido. Otra razon a considerar es que son una serie de problemas con respuestas, para que lo pensemos un rato y si se nos ocurre la respuesta la demos. Si no se nos ocurre en lugar de  simplemente olvidarlo podemos revisar la respuesta.

Otra cuestión importante es que lo podemos checar 10 minutos al día y aun así aprender algo, también hay que notar que son problemas sencillos pero instructivos, por ejemplo:

bobby fischerAquí podemos ver claramente que el problema se reduce solo a si podemos dar mate o no, no nos importa mucho las cosas complicadas como la mejora de posición, las piezas de cada bando, que va a ocurrir en 20 jugadas ni cosas del estilo, solo se nos da una posición donde tenemos que contestar si podemos dar mate o no.

Las preguntas del libro son de este estilo, nos enseñan a ver patrones obvios y no tan obvios. Claro que para alguien del nivel de Bobby Fischer o algún gran ajedrecista como Capablanca o Carlsen el contenido del libro sera obvio, para un total principiante las ultimas paginas del libro sin haber leído las primeras le parecerá magia negra, sin embargo hay algo muy curioso de este libro y muchos otros del estilo. En términos de ajedrez por computadora, la maquina simplemente no juega así.

Claro que por casualidad puede que uno de los mates del libro coincida con una de las reglas que evalúa el motor de ajedrez como explique en el post anterior pero en general ese libro es un ejemplo perfecto de como las computadoras NO juegan.

¿Por qué? Bueno es muy sencillo en realidad, lo que aprendemos a lo largo de ese libro es a reconocer nuevos patrones y en base a ello generar otros nuevos, cosa que ningún motor de ajedrez fuerte actualmente hace, en cambio la computadora solo revisa si coincide con alguna regla o patrón y en base a eso ejecuta una búsqueda. El tema de este libro esto esta estrechamente relacionado con temas de, “Aprendizaje computacional” “Big Data” y “Mineo de datos” en el sentido de que si que es posible enseñarle a una computadora de esta manera revisando de entre muchos patrones distintos tal que tenemos que reconocer el correcto, ahora no me meteré en el tema porque es bastante complicado y merece su propio post o serie de post.

En pocas palabras es un libro que vale la pena, ya seas principiante o GM tanto por el sentido histórico como por su contenido ya que esta escrito por el gran Bobby Fischer, aunque sea para echarle una hojeada.

Explicación de como funciona un motor de ajedrez

Para cualquier persona que haya jugado ajedrez por computadora le sera bastante claro que la pc(en cualquiera de sus variedades) juega muy distinto a como juega un humano. El porque de esto lo abordare en otra entrada, en esta explicare como es que la computadora juega.

Hay muchos programas de ajedrez como son stockfish, komodo, gnuchess, houdini, sjeng por mencionar algunos. Bastante distintos entre si en sus detalles, pero el principio general con el que funcionan es el mismo. Para entender como funciona un programa de ajedrez necesitamos entender el concepto de árbol(en el sentido computacional, no el que se planta).

En pocas palabras esto tiene bastante que ver con el factor de ramificación  en si es una estructura llamada árbol que nos permite revisar las posibles jugadas, por ejemplo:

Al inicio del juego tenemos 20 posibles jugadas para las blancas(16 de peones y 4 de caballo) y lo mismo para las negras

Lo que hay que notar en este juego aparentemente sin gracia es que tras la primera jugada es solo 1 de los posibles 400 que pudo ocurrir, tras solo 4 jugadas este numero se dispara a mas de 288 mil millones entonces resolverlo revisando todas las jugadas es imposible(para el que este interesado en como se haría esto la manera se llama BFS) entonces necesitamos recurrir a una heurística(en pocas palabras una manera de revisar el árbol sin checar todas las posibilidades) uno se preguntaría ¿Como? Esa es la parte importante.

Para decidir que partes buscar y cuales no a cada pieza se le asigna un valor numérico donde por ejemplo el rey vale infinito(o un numero arbitrariamente grande) la dama vale 9, un peón vale 1(tabla completa aquí) y como la pieza con menor valor es el peón y la posición también es importante  se tiene una medida fraccionaria que vale centésimas(o milésimas de peón) en base a esto se toman las decisiones.

La razón de los valores numéricos es que las computadoras solo manejan 0 y 1, así que para poder calcular cualquier cosa(quien va ganando, la siguiente jugada etc…)  se necesita una medida que las computadoras puedan entender.

El valor de las piezas en cada motor de ajedrez suele ser el mismo(aunque nada nos impide crear un motor con valores distintos) debido a que son valores que funcionan. Donde suele variar es a los valores que se le da a una posición, a las combinaciones de piezas etc.

Existen bastantes algoritmos que se ocupan en el ajedrez para determinar que jugadas vale la pena explorar (el código de stockfish es abierto para el que quiera ver los detalles algorítmicos de como funciona un motor de ajedrez) y cuales no, en base a un conjunto de reglas se define una función de evaluación y en base a esa función de evaluación se decide cuales ramas del árbol(o sea posibles jugadas) analizar y la jugada que se mueve al final es la que nos haya regresado mejor puntuación en la función de evaluación.

En general los distintos niveles de un motor de ajedrez es decidir que reglas se ocupan para la función de evaluación, donde el nivel 0(o mono en algunas) es no ocupar ninguna regla y tirar al azar, y el nivel máximo es ocupar todas las reglas. En base a esas reglas una computadora actual puede analizar millones de jugadas en pocos segundos.

En pocas palabras se podría decir que es similar a la fuerza bruta en el sentido de que se revisan millones de posibles jugadas, pero distinto en el hecho de que se tiene una idea de donde buscar.

Una analogía bastante tonta(y no 100% correcta) pero que deja claro el punto seria que la fuerza bruta es como tratar de escribir el quijote usando letras al azar, y usar una función de evaluación seria como ocupar palabras completas, una función de evaluación burda es como ocupar palabras de muchos idiomas(por ejemplo árabe, chino, ingles, español) una función de evaluación buena seria solo ocupar palabras de el español y una función de evaluación muy buena seria solo ocupar palabras del español que se ocupan en el quijote. Claramente es posible escribir el quijote completo con cualquiera de estas 3 estrategias, sin embargo bajo estas restricciones es obvio porque una buena función de evaluación tardaría mucho menos que teclear letras al azar.

Escribir buenas reglas para la función de evaluación es una tarea bastante difícil y ahí es donde difieren los distintos motores de ajedrez, cada motor de ajedrez tiene un conjunto de reglas distintas(puede que algunas coincidan pero no todas), por supuesto que también hay otros factores mas relacionados con la eficiencia en la programación y las distintas maneras en la que se puede calcular la función, como se guarden las posibles jugadas entre muchos otros.

Pero lo importante(y aunque sea una simplificación algo inexacta) es que cada pieza tiene un valor, y en base a esos valores se crea una función que ocupa unas reglas, se toma el mejor valor de la función y esa es la jugada que se mueve.

Esta es solo la idea principal de como funciona un motor de ajedrez sin tablas syzygy ni nalimov ni explicar el problema del horizonte ni las técnicas especificas para calcular cuales reglas sirven y cuales no. Ya abra mas entradas sobre eso.

También hay que notar que esto solo explica como funciona un buen motor de ajedrez bajo las nociones estándar,  también es posible crear motores de ajedrez sin funciones de evaluación y solo ocupando reglas o  motores de ajedrez que su objetivo sea perder todas las piezas(para jugar losing chess por ejemplo) pero su funcionamiento es muy parecido. O algún motor de ajedrez que funcione radicalmente distinto, sin embargo esos actualmente son la excepción y no la regla.

Humano vs Stockfish nivel mas alto

En algún otro momento explicare porque es tan distinto la manera en la que juega una computadora comparado con como juega un humano, pero ya sera en otro momento, por ahora me puse a competir contra stockfish en el máximo nivel, el resultado como seria de esperarse me hizo pedazos aun cuando me pase del tiempo establecido por el reloj.

No hace falta decir que no es muy divertido jugar seguido contra un oponente que te hace pedazos cada vez que juegas. Pero probar de vez en cuando no esta tan mal.

El ajedrez y resolverlo con la fuerza bruta

tablero ajedrez con fuerza bruta
Dispararle a las piezas una por una es fuerza bruta, pero no resuelve  como ganar el juego

Uno de los temas que se nota cuando uno ha estudiado Ciencias de la Computación es cuando te preguntan, oye y ¿Por qué el ajedrez no esta resuelto aun?

Bueno, la respuesta es que a menos de que existan avances en la ciencia y tecnología que ni me puedo imaginar y supongo que no son posibles el ajedrez nunca sera resuelto por completo

En ese caso la pregunta correcta seria ¿Por qué no se puede resolver?

La respuesta corta es que hay muchos juegos posibles de ajedrez. Y nunca acabaríamos, hay aproximadamente 10120  posibles juegos de ajedrez para quien no este muy familiarizado con las matemáticas, se estima que la cantidad de átomos en el universo es aproximadamente 1082  o sea que existen 1038 veces mas partidas posibles de ajedrez que átomos.

Para quien le interese una respuesta mas elaborada teóricamente el ajedrez si se puede resolver, al ser una numero finito de partidas se puede computar, y al ser computable existe una maquina de Turing que lo resuelva, el problema no es que no sepamos como resolverlo, si no que ya en la practica es imposible.

Para los que no estén familiarizados con el tema revisar  todas las posibilidades tiene el nombre de fuerza bruta, el nombre se da porque en algunos casos existen estrategias para resolver cosas de manera mucho mas eficiente y la fuerza bruta también te entrega el resultado, solo tarda mucho mas, eso no quiere decir que sea mala, pues algunos problemas solo se pueden resolver de esta manera.

Suponiendo que tuviéramos almacenamiento y tiempo infinito, solo seria cuestión de revisar todos los juegos uno por uno y guardar los mejores, en 1950 Claude Shannon dijo que no era feasible por el tiempo que tardaría, aproximadamente unos 1090  años pero ya no estamos en 1950, ahora en 2015 ¿Cuanto tiempo tardaría?

El numero exacto no lo se pero una aproximación me da que son mas segundos que la cantidad de átomos del universo aun ocupando todas las computadoras del mundo en paralelo.

Porque tantas posibilidades, bueno en parte tiene que ver con el factor de ramificación ahora se podrán preguntar, ¿El ajedrez con menos piezas podría resolverse?

La respuesta es sí, y son las famosas Nalimov/Sysygy, todas las jugadas con hasta 6 piezas(incluyendo los 2 reyes) ya están resueltas y gran parte de las de 7 piezas(omitieron las rey vs rey + piezas).

Para el que haya entendido el articulo y tenga un poco de conocimiento en matemáticas el porque si es posible resolver hasta 6 o 7 piezas le parecerá obvio, simplemente existen muchos menos posibles juegos de ajedrez. ¿Cuantos menos? no daré la cifra exacta, pero claramente muchos pero muchos menos.

Y sobre lo que nos depara el futuro:

A realistic goal is to try and extend the perfect tables of play to eight, nine, ten and more pieces.

https://rjlipton.wordpress.com/2010/05/12/can-we-solve-chess-one-day/

El ajedrez y el factor de ramificacion

Cuando uno estudia o es aficionado al ajedrez por computadora se debe de conocer el concepto de factor de ramificación (branching factor) en palabras simples si tenemos la posición inicial y cada movimiento siguiente tiene X posibilidades, entonces el factor de ramificación es X, por ejemplo un juego ya resuelto por las computadoras es el famoso gato(tic tac toe en ingles) tiene factor de ramificación de 4.

El ajedrez tiene factor de ramificación 35 es un factor mucho mayor pero no se compara al factor de ramificación del go que es 250, por supuesto que también influye el tamaño del tablero y la cantidad de jugadas máximas posibles. 

Como se podrán imaginar a mayor tamaño de tablero y mayor cantidad de jugadas posibles mas “dificil” de resolver se vuelve el juego.

Solo para evitar confusiones, tener un factor de ramificación alto solamente no implica que un juego sea mas difícil, digamos que tenemos un juego donde su factor de ramificación es 1000 pero la cantidad total de jugadas es 2, al tener solo 2 jugadas existen muchas menos opciones que por ejemplo un juego de factor de ramificación 30 pero que se puedan jugar hasta 200 jugadas.

Pero manteniendo todos los demás valores constantes el factor de ramificación si es muy importante, un juego muy similar al ajedrez en tamaño de tablero y que ya esta resuelto son las damas(checkers en ingles) su factor de ramificacion es 8, mientras un juego muy similar llamado arimaa tiene factor de ramificacion de 17000 y de las cuales las computadoras aun no tienen mucha idea.

También hay que darse cuenta que el factor de ramificación no es constante, si no mas bien un promedio puede verse claramente que en esta jugada:

Se tienen muchas mas posibles movidas que en esta otra

Pero lo que nos importa es la cantidad promedio de ramificación promedio entre los juegos empezando desde el inicio.

Aclaro que todos los números mencionados son aproximados si quieren saberlo con exactitud les dejo unas referencias.

Referencias:

http://www.cs.cmu.edu/~adamchik/15-121/lectures/Game%20Trees/Game%20Trees.html

http://es.wikipedia.org/wiki/Factor_de_ramificación

http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/chess-programming-part-iv-basic-search-r1171

http://arimaa.janzert.com/bf_study/

Stockfish 5 vs Stockfish 6

Como mencione en el post anterior http://ajedrez.ga/2015/el-cambio-y-el-ajedrez-por-computadora en el ajedrez por computadora podemos asegurarnos de que lo que hagamos mejore una versión anterior por medio del testeo automatizado y es aquí donde el poder de el código libre brilla. Ya que se pueden hacer mejoras incrementales, prácticamente imperceptibles que a lo largo de un tiempo hacen una mejora brutal.

En el caso de Stockfish tienen una manera de asegurar la calidad en http://tests.stockfishchess.org/tests se puede revisar el historial de las pruebas hechas y se pueden sugerir otras nuevas, cada prueba son aproximadamente 25,000 juegos por lo que llegar a 1,000,000,000 de juegos tan solo en las pruebas no suena como algo muy distante.

Y eso combinado al hecho de que las pruebas están hechas específicamente con el fin de optimizar una pequeña cosa en especifico, que existen métricas claras de lo que se quiere lograr y el hecho de que cualquiera que este interesado puede contribuir de manera que ayude al proyecto (Quien sepa programar contribuyendo código, quien sepa bien ajedrez contribuyendo ideas y cualquier persona interesada donando tiempo de su maquina para las pruebas automatizadas) de manera que su contribución siempre beneficie al proyecto.

De tal manera que si comparamos a Stockfish 5 con Stockfish 6 notaremos que la ultima versión es casi 100 puntos de elo mas fuerte que la anterior y dado que esto se da en un entorno perfectamente claro y controlado sabemos que no tiene que ver con la velocidad de las maquinas con que se prueba. Esto lo hace el programa de ajedrez mas fuerte que ha existido.

¿Pero en realidad es tanta la diferencia?

Quizá para nosotros no lo sea ya que hasta un equipo formado por todos los GM del mundo competiendo contra Stockfish seria vencido. Pero este solo es un pequeño paso. Si hace 50 años pusiéramos a competir a el mejor programa de ajedrez contra un humano relativamente bueno, pero sin tener ningún titulo especial si le diéramos este diagrama y le tocara jugar con las negras probablemente se las arreglaría para ganarle a la computadora.

Ahora mismo si le damos las blancas a el mejor jugador humano de ajedrez, 3 veces mas de tiempo y corriéramos Stockfish 6 en una computadora de hace 5 años creo que lo mejor que podría conseguir el jugador humano es un empate.