Chessy - Parte 2

Ésta es la continuación del mini-proyecto llamado Chessy, una aplicación para reproducir partidas de ajedrez. En el post anterior decidí usar usar una lista de posiciones del tableros como UI-Data, y aquí dejo algunas notas sobre cómo generaralas.

Los partidos de ajedrez que uso están escritos en una notación llamada PGN y contienen la lista de movimientos que sucedieron en el partido. Pero lo que necesito es generar una lista de posiciones del tablero, y guardarlo en un archivo JSON.

Gráficamente:

A continuación, algunas notas sobre el formato PGN, la notación en la que se escriben los movimientos, y de qué se trata el procesamiento intermedio (el cuadro anaranjado). Al final agrego links a la implementación.

Input

Archivos PGN

Un partido de ajedrez escrito en formato PGN se compone de dos grandes partes: información general (jugadores, lugar, fecha, torneo) y los movimientos del partido.

El siguiente es un partido de ejemplo:

[Event "WCh 2013"]
[Site "Chennai IND"]
[Date "2013.11.16"]
[Round "6"]
[White "Anand, Viswanathan"]
[Black "Carlsen, Magnus"]
[Result "0-1"]
[WhiteTitle "GM"]
[BlackTitle "GM"]
[WhiteElo "2775"]
[BlackElo "2870"]
[ECO "C65"]
[Opening "Ruy Lopez"]
[Variation "Berlin defence"]
[WhiteFideId "5000017"]
[BlackFideId "1503014"]
[EventDate "2013.11.09"]

1. e4 e5 2. Nf3 Nc6 3. Bb5 Nf6 4. d3 Bc5 5. c3 O-O 6. O-O Re8 7. Re1 a6 8. Ba4
b5 9. Bb3 d6 10. Bg5 Be6 11. Nbd2 h6 12. Bh4 Bxb3 13. axb3 Nb8 14. h3 Nbd7 15.
Nh2 Qe7 16. Ndf1 Bb6 17. Ne3 Qe6 18. b4 a5 19. bxa5 Bxa5 20. Nhg4 Bb6 21. Bxf6
Nxf6 22. Nxf6+ Qxf6 23. Qg4 Bxe3 24. fxe3 Qe7 25. Rf1 c5 26. Kh2 c4 27. d4 Rxa1
28. Rxa1 Qb7 29. Rd1 Qc6 30. Qf5 exd4 31. Rxd4 Re5 32. Qf3 Qc7 33. Kh1 Qe7 34.
Qg4 Kh7 35. Qf4 g6 36. Kh2 Kg7 37. Qf3 Re6 38. Qg3 Rxe4 39. Qxd6 Rxe3 40. Qxe7
Rxe7 41. Rd5 Rb7 42. Rd6 f6 43. h4 Kf7 44. h5 gxh5 45. Rd5 Kg6 46. Kg3 Rb6 47.
Rc5 f5 48. Kh4 Re6 49. Rxb5 Re4+ 50. Kh3 Kg5 51. Rb8 h4 52. Rg8+ Kh5 53. Rf8 Rf4
54. Rc8 Rg4 55. Rf8 Rg3+ 56. Kh2 Kg5 57. Rg8+ Kf4 58. Rc8 Ke3 59. Rxc4 f4 60.
Ra4 h3 61. gxh3 Rg6 62. c4 f3 63. Ra3+ Ke2 64. b4 f2 65. Ra2+ Kf3 66. Ra3+ Kf4
67. Ra8 Rg1 0-1

Como claramente se puede leer (o eso espero), ese partido fué entre Carlsen y Anand, se jugó en 2013, y las negras ganaron. Todo eso está en la primera parte, como información general. Después de leer varias partidas noté que no hay muchas reglas sobre cuántas líneas ni cuáles hay en esta sección. Por ejemplo, solo algunas incluyen el ELO de los jugadores (ranking), el Round (si el enfrentamientos tiene varias rondas), o el Opening (parte del análisis a-posteriori).

La segunda parte, los movimientos, está en todos los partidos y comienza con un 1. y termina con el resultado (0-1 en el ejemplo). Los movimientos estan escritos usando la Notación Algebraica.

Notación Algebraica

Cada movimiento en es un manojo de letras que tienen significado por sí mismo y también posicionalmente (como el número “0”, que significa una cosa por sí solo y otra cuando está a la derecha de otro número). Cada movimiento completo (de Blancas y de Negras, en ese órden) empieza con un número que incrementa de a uno seguido por un punto (en el ejemplo se pueden ver 1., 2., 3., etc). Luego se escribe el movimiento de las Blancas y, si el partido no se terminó, el de las negras después de un espacio. En el partido de ejemplo, e4 es el primer movimiento de Blancas y e5 es el primer movimiento de Negras.

Dentro de cada movimiento, las letras de la a a la h hacen referencias a las columna del tablero (si uno mira el tablero desde el lado de las Blancas, a está a la izquierda), y los números del 1 al 8 son las filas/líneas, siendo 1 el lado de las blancas. Las letras mayúsculas hacen referencia a la pieza: Q es Queen (dama), K es King (rey), N es kNight (caballo), B es Bishop (alfil), R es Rook (torre), ninguna letra es un peón. Además, = indica promoción, O-O y O-O-O son enroques, ! advierte un jaque, etc.

Lo importante de todo esto es que la Notación Algebrica indica explícitamente el casillero al que se dirige una pieza, pero no desde dónde lo hace. Para saber eso (desde dónde), uno debería mirar el tablero y deducir cuál es la única pieza que puede realizar tal movimiento. Si hubiese más de una piezas que puede realizarlo ese movimiento, se añaden letras adicionales (fila, línea, o ámbas) para quitar esa ambigüedad. En el partido de ejemplo, ésto sucede en el movimiento 20. Nhg4, que indica que el caballo que está en la columna h - y no el otro - es el que realiza el movimiento.

Procesamiento

El procesamiento consta de leer y entender el partido, e ir jugándolo en un tablero. Así, una vez terminado el partido, puedo obtener todas las posiciones intermedias (la salida deseada).

Entre las varias posibilidades para leer y entender el partido de entrada, elegí usar la técnica usada por los compiladores que consta de un Lexer y un Parser (hace rato quería hacer algo así). El rol del Lexer es detectar tokens a medida que lee el texto. El Parser, que va recibiendo dichos tokens, intenta agrouparlos en construcciones semánticas válidas. Los tokenes vendrían a ser clasificaciones de las partes de un texto; por ejemplo: 1. es un número de movimiento, Q, K, o R son piezas, y números del 1 al 8 son líneas. Ejemplos de algunas posibles construcciones semánticas son movimiento, resultado, partido.

Una vez que un movimiento es detectado por el Parser, lo juego en un Tablero. Para ello el Tablero necesita cierta lógica, dado que el movimiento escrito no provee toda la información necesaria para mover una pieza de lugar. Como mencioné anteriormente, un movimiento en Notación Algebraica especifica claramente hacia dónde se mueve cierta pieza pero no desde dónde. Por ello el Tablero inspecciona primero el tablero para ver cuál es la pieza, o piezas, afectada. El Tablero además guarda todas las posiciones a medida que juega. Cuando el Parser detecta que el juego se terminado, el Tablero provee todas las posiciones intermedias para ser escritas en el archivo JSON de salida.

NOTA: en la primera iteración del Procesamiento, dejé de lado la parte de la información general - nombre de los jugadores, fecha, lugar, etc - y me enfoqué exclusivamente en los movimientos.

Implementación

La implementación de todas esta parte está en Python. En un primer momento consideré usar los legendarios lex & bison en C, pero encontré en SLY para Python algo bastante parecido pero mucho más moderno, intrigante, y (creo) útil. La documentación es muy entendible y junto con ésta charla del creador son una buena introducción al mundo de los parsers.

El Lexer define los tokens con expresiones regulares y los usados en chessy están al principio de éste archivo

El Parser define las construcciones semánticas en formato de reglas de producción y las usadas en este proyecto están en la seguna parte del mismo archivo¹. El Parser también invoca un par de funciones cuando detecta algunas reglas - movimiento y partido terminado - que una especie de coordinador lo conecta a un Tablero.

El Tablero, que recibe y “juega” los movimientos, fijándose cuáles son las piezas que pueden hacerlo, está implementado en este archivo. Todas las posiciones intermedias son guardadas en una lista de manera que luego puedan ser extraídas, convertidas a FEN, y ser parte del archivo JSON que alimenta la UI.

Todo lo anterior se accede mediante una mini CLI; así que para procesar un archivo PGN y generar un JSON por cada partido, basta con ejecutar:

python src/main.py --pgnFile <pgn-file>

Y eso es todo por hoy, hasta pronto!◆