Una partida de ajedrez con un tablero inca

En esta partida reviviremos la lucha entre los incas y los españoles con piezas de ajedrez temáticas.

Veamos la batalla desde el lado español antes de que comience

Hagamos lo mismo con el lado inca

Como todos ya sabemos los españoles abren la batalla

Los incas se preparan, saben defenderse de la ofensiva española

Hacen retroceder al alfil

La lucha es feroz, después de una larga batalla tanto los incas como los españoles quedan acuartelados en una esquina

Tanto los españoles como los incas creen que pueden lograr la victoria

En este momento es difícil decir quién saldrá victorioso, las bajas son muchas pero pronto la batalla llegar a su fin

Los incas toman ventaja, la situación para los españoles se ve perdida

Los incas aún no celebran, un error les puede costar la batalla.

Los españoles lloran amargamente, la reina inca ha dado jaque y atacado la torre al mismo tiempo

Los incas celebran, ya sabían que los españoles no podían ganar pero aún no cantaban victoria. El empate todavía era posibilidad más después de este movimiento ya no lo es.

El rey se ha quedado solo, con lo que le queda de fuerza intenta evadir el ataque inca pero es en vano

Se ha quedado acorralado, ya no hay nada más que hacer, solo pronunciar las palabras finales…

Jaque mate.

Hay una gran variedad de tableros de ajedrez con distintos temas, los hay clásicos, con pequeñas modificaciones, los hay temáticos como en este caso donde las blancas son representadas por los conquistadores españoles y las negras son representadas por los incas.

Tras jugar una partida con este tablero me he dado cuenta de lo importante que es tener piezas de ajedrez bien definidas. El tablero que poseo es hermoso pero es algo más ornamental que funcional. A media partida ya con el cansancio mental a veces es difícil distinguir entre las distintas piezas.

Como pasa con todo si llegara a jugar suficientes juegos con este tablero muy probablemente debería dejar de costarme trabajo pero las pocas partidas que he jugado con este han sido más complicadas, más difíciles por el simple hecho de que se confunden las piezas

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.

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/

El cambio y el ajedrez por computadora

Este no va a ser mi típico post de ajedrez, si no mas bien una reflexión del ajedrez por computadora.

Claramente cualquiera de nosotros espera que la versión siguiente de un programa mejore su rendimiento. En algunos casos eso suele ser un fracaso absoluto, Windows XP comparado con Windows Vista o Windows 7 comparado con Windows 8 son ejemplos clásicos. Otro muy sonado es la salida del nuevo y mejorado BlackBerry que fue totalmente aplastado por Android y iOS.

Una pregunta que nos es ¿Por que pasan esos errores? Las respuestas son muchas, errores humanos, falta de metas claras, consumo excesivo de recursos, o simplemente un mal diseño de entrada. Otro hecho que sin ser un error en si, es el cambio de requerimientos, lo que era tecnología de punta hace 10 años hoy probablemente empiece a estar obsoleto.

Ahora, si comparamos cualquier tipo de programa entre sus versiones pasadas y actuales muy probablemente escojamos quedarnos con las actuales, excepto en unos cuantos programas ya sea porque quitaron una función que nos agrada como lo ha hecho Adobe con su linea Creative Suite o agregan cosas que ni nos interesan ni queremos(Windows Vista es el ejemplo perfecto) o simplemente cambian su interfaz.

Se preguntaran ¿Y esto que tiene que ver con el ajedrez? A simple vista no mucho, pero si lo piensan bien notaran algo en común, nada de esto aplica al ajedrez, sus requerimientos no cambian con el tiempo, la meta es totalmente clara (Ganar el juego capturando al rey contrario), si un programa de ajedrez consume demasiados recursos en general es vencido por uno similar que haga lo mismo y consuma menos recursos. Entre otras cosas que deberían ser obvias como que si diseñamos un programa mal de entrada vamos a ser vencidos cada vez.

Por dar un ejemplo:

O sea mientras los requerimientos para ganar y las reglas del juego no cambien el conocimiento que tenemos sobre como mejorar es incremental y las reglas del ajedrez no han cambiado en mucho tiempo pero si le mostráramos este juego a alguien nacido hace 1000 años(y que jugara ajedrez claro esta) se quedaría perplejo y probablemente enfurecido ya que para el el las jugadas validas serian:

Claro que actualmente eso no pasa, las reglas se han mantenido muy estables por un largo tiempo de tal manera que si queremos mejorar estudiar los juegos de los grandes como Bobby Fisher o Capablanca nos es de gran ayuda. Sin embargo indirectamente esto también aplica a los programas de ajedrez ya que para ver si son mejores que la versión anterior basta con hacer pruebas entre ellos y dada la gran capacidad de computo actual comparada con cualquier época anterior se pueden gastar recursos en testeo automatizado y así asegurarnos mejoras, a diferencia de cuando se lanza un producto.