Showing posts with label tesis de doctorado. Show all posts
Showing posts with label tesis de doctorado. Show all posts
Wednesday, August 22, 2018
GigaChess: una base de datos de posiciones de ajedrez
Llevo tres años trabajando en el doctorado y parece ser que ya las cosas se están aclarando. Tengo un lenguaje de descripción de patrones y ahora el plan -entre otros- es hallar los patrones comunes en la base de partidas que hoy en día tiene más de 7 millones de estas.
Una idea que llevaba hace tiempo trabajando era la de buscar patrones en una base de datos de posiciones, lo cual debe ser mucho más rápido que el tener que buscar el patrón jugando cada partida. Además, si cambio de patrón, tendría que volver a "jugar" partida tras partida para ver si el patrón que busco existe.
Por otra parte, pienso que si guardo cada partida como "fotografías" de cada posición que se dio, puedo hacer las búsquedas más rápidamente. La primera pregunta es cuánto espacio necesito. Hagamos uns imple cálculo: 7 millones de partidas por 80 posiciones (asumiendo que en promedio una partida tiene 40 jugadas, 80 movimientos de blancas y negras). Esto da: 560,000,000 posiciones en total. Si necesito un registro de al menos 64 casillas para guardar una posición (en formato Forsyth), esto nos dará 35,840,000,000 bytes, es decir, unos 35 gigabytes de almacenamiento. Hay que guardar, desde luego, el encabezado de cada partida y hacer el sistema que buisque los patrones. Vamos, hay trabajo por hacer.
35 Gigabytes no parece mucho espacio hoy en día, en donde tenemos discos con 1 o 2 terabytes de almacenamiento.
Así pues, el primer problema es generar las posiciones y ya escribí hace tiempo un programa que hace esta tarea. Cada partida, en la máquina que tengo, se procesa en promedio, en 5 segundos (veces menos). Eso da, para 7 millones de partidas un total de 35,000,000 segundos, lo cual en días es equivalente a 405 días, como un año y tres meses...
Denasiado tiempo. Así que he reeducido a un millón de partidas, quizás menos. Por otra parte, AMD me donó una computadora mucho más rápida que la que uso normalmente y espero que esto baje el tiempo de procesamiento aún más. Con un millón de partidas, más o menos tardaré: 57 días, unos 2 meses...
Pronto seguiré dando avances sobre esta idea, la cual -después de mucho pensarlo- me parece más útil para la cuestión de programación de computadoras que para el ajedrecista que usa programas para apoyar su estudio.
Wednesday, March 29, 2017
Bosquejo de un lenguaje de patrones de ajedrez
Ya antes en este blog (busquen por "patrones de ajedrez") he hablado sobre un lenguaje para describir posiciones de ajedrez, el cual es lo suficientemente genérico para establecer patrones del juego. Después de varios meses de trabajar en esto, creo haber hallado un lenguaje de patrones que bien puede ser útil para expresar posiciones de ajedrez de forma que puedan usarse para cambiar incluso el paradigma de cómo los programas de ajedrez funcionan, quitando el cálculo bestial que hoy en día hacen por un enfoque más humano, basándose en que el ajedrez es un juego en donde intervienen patrones, sin lugar a dudas. De esta manera podrían construirse programas "más humanos".
Introducción al lenguaje de patrones
Definimos el ataque de una pieza a otra como:
Pi(P2)
donde P1 es la pieza del atacante y P2 es la pieza atacada. Si las piezas son del mismo color, hablamos de que P1 defiende a P2, pero si son de diferente color, P1 ataca a P2. Por ejemplo, A(ph7), lo cual significa que un alfil ataca a un peón negro en h7. Por convención las piezas blancas se ponen con su iniciales mayúsculas y las piezas negras con sus iniciales en minúscula.
También podemos decir: A(h7), lo que indica que el alfil blanco ataca la casilla h7. Cabe decir que no es necesario decir en qué casilla está el alfil del blanco. De hecho, en el ejemplo, el alfil podría estar en b1, c2, d3, e4, f5 o g6.
Podemos definir una pieza en una casilla en particular con la notación: Ad3, lo que indica que el alfil blanco está en la casilla d3. Nótese que en este caso no sabemos qué casillas ataca/defiende. Solamente sabemos su posición.
Se ha definido una instrucción: taboo(casilla), indicando que para el defensor, la "casilla" mencionada no está disponible. Por ejemplo, en la partida Carlsen - Karjakin, del Campeonato Mundial 2016 llevado a cabo en Nueva York a fines del año pasado, se llegó a esta posición:
Carlsen - Karjakin
Nueva York 2016
Juegan las blancas
El patrón de esta posición es D(h6), Tc8, T(f7), Ph5, rh7, pg7, taboo(g6). 1. Dh6+
El patrón no sólo describe la posición, sino que también se define al menos la primera jugada que debe hacerse (1. Dh6+). Esto podría ser una manera para hacer un programa en donde los patrones orientaran sobre cuáles son las mejores jugadas en lugar de hacer un cálculo de fuerza bruta.
Pero como ya indicamos antes en este mismo blog, tenemos que en la partida Popov - Novopashin, URSS 1979, se dio la siguiente posición:
Popov - Novopashin
URSS 1979
Juegan las blancas
Cuyo patrón es: D(h6), Tf8, Tb1, Ph4, rh7, pg7, taboo(g6). 1. Dh6+
Nótese que la instrucción taboo(g6) hace que la casilla g6 no esté disponible a las negras. Es intereante cómo los dos patrones se ven muy similares.
Otra idea interesante es la de los conectores lógicos. Un patrón en ajedrez consiste en definir las piezas en ciertas casillas o definiendo qué ataca o qué defiende. El patrón puede considerarse como un conjunto de instrucciones separadas por comas. Definimos a la "," como el AND lógico e introducimos el otro conector lógico, el OR, cuyo símbolo será ";" como en la mejor tradición del lenguaje Prolog. Sin embargo, en lugar de usar los símbolos, quien defina un patrón puede usar indistintamente "AND" o "," y "OR" o ";".
Por ejemplo, en la partida Pestalozzi - Duhm, Berna 1990, se llegó a la siguiente posición:
Pestalozzi - Duhm,
Berna 1990
Juegan la blancas
Aquí tenemos el sacrificio griego, el cual podría definirse como: A(h7), Cf3, Pe5, ph7, pg7, pf7, pe6, rg8 y añadiendo Dd1 OR Dg4. La primera jugada es 1. Axh7+.
Definiéndolo de esta manera, tenemos que el patrón buscado será:
A(h7), Cf3, Pe5, ph7, pg7, pf7, pe6, rg8, Dd1
o
A(h7), Cf3, Pe5, ph7, pg7, pf7, pe6, rg8, Dg4
Patrones posicionales
Un lenguaje de patrones debe poder no solamente lidiar con elementos tácticos. Debería tener la capacidad de definir patrones posicionales. Definimos estos a partir de su estructura de peones. Así, creamos dos instrucciones: structw(lista de peones) y structb(lista de peones). Por ejemplo, en Botvinnik - Donner, tenemos la siguiente posición:
Botvinnik - Donner
Amsterdam, 1963
Juegan las blancas
Su patrón puede expresarse como:
structw(a3, b4, e2, f2, g3, h2)
structb(a7, b6, e6, f7, g7, h7)
obtener el punto débil c6 (para las blancas)
Botvinnik logró la ventaja después de 14. Cd4, Axg2 15. Rxg2 Dc7 16. Db3 Tfc8 17. Tfc1 Db7+ 18. Df3 Cd5 19. e4 C5f6 20. b5! a6 21. Cc6, logrando quedarse con la casilla c6 y posteriormente llevándose el triunfo.
Los patrones posicionales son más difíciles de definir porque no hay un mecanismo directo para obtener la ventaja por métodos tácticos, pero a través de structw/b podemos definirlos. Esto es lo que en la literatura de ajesrez se denomina como "priyomes", que es una palabra rusa que se usa para representar algún tipo de maniobra o técnica típica. Por ejemplo, una técnica de un priyome defensivo es usar el rey, en los finales de torres, para atacar los peones enemigos. Sin embargo, los priyomes normalmente se usan para referirse a posiciones con cierta estructura de peones.
Un resumen de las instrucciones de este lenguaje de patrones
Las instrucciones del lenguaje son:
P1(P2) - La pieza 1 ataca/defiende a la pieza 2.
P(casilla) - La pieza ataca la casilla.
P casilla - La pieza está en esa casilla
taboo(casilla) - hace esa casilla como no disponible al bando defensor.
structw(lista de peones) - define la estructura de los peones blancos en el tablero.
structb(lista de peones) - define la estructura de los peones negros en el tablero.
Conectores lógicos - "," = AND y ";" = OR. Pueden usarse indistintamente (",",";") o (AND,OR).
Comentarios (por línea) - "//", por ejemplo //esto es un comentario.
Por el momento lo dejo aquí. Hay cosas que definir, por ejemplo, ¿cómo es que dos patrones son similares? ¿cómo definir la similitud en dos patrones para considerarlos que son el mismo? ¿se puede crear una métrica de la similitud? Hay que trabajar sobre esto.
Subscribe to:
Posts (Atom)





