PGN son las siglas de Portable Game Notation, un sistema para anotar partidas de ajedrez, usando el esquema de la notación algebraica, que es el único sistema de escritura oficial de la Federación Internacional de Ajedrez (FIDE). Gracias a este mecanismo, cualquiera puede leer una partida de ajedrez sin prácticamente importar en qué parte del mundo se encuentre. La notación de una partida de ajedrez contempla los siguientes rubros: Evento (en qué torneo se jugó el torneo), lugar del evento, fecha completa, ronda, nombre del conductor de las blancas, nombre del conductor de las negras, resultado, ECO (código de la apertura de acuerdo a la Encyclopedia of Chess Openings - ECO), el rating de las blancas, el rating de las negras, entre otros apartados (estos son los más generalizados). Inmediatamente después de esto, viene la partida, codificada de la siguiente manera: número de jugada, jugada del blanco, jugada del negro, número de jugada, etc. hasta llegar va 1-0, 0-1 o 1/2 (ganan blancas, ganan negras, empate).
Por ejemplo, esta es la partida entre Leko e Ivanchuk, del torneo alemán de Dortmund, del 2008:
[Event "Sparkassen"]
[Site "Dortmund GER"]
[Date "2008.06.29"]
[Round "2"]
[White "Leko, P."]
[Black "Ivanchuk, V."]
[Result "1-0"]
[ECO "B46"]
[WhiteElo "2741"]
[BlackElo "2740"]
1. e4 c5 2. Nf3 e6 3. d4 cxd4 4. Nxd4 Nc6 5. Nc3 a6 6. Nxc6 bxc6 7. Bd3 d5 8. O-O Nf6 9. Qf3 Be7 10. Qg3 Nh5 11. Qf3 Nf6 12. e5 Nd7 13. Qg3 g6 14. Bh6 c5 15. Na4 c4 16. Be2 Bb7 17. b3 Bc6 18. Nb2 Rb8 19. Nd1 Nc5 20. Ne3 Ne4 21. Qh3 Ng5 22. Qg4 c3 23. a3 Bb5 24. Bxb5+ axb5 25. f3 Qb6 26. Rae1 d4 27. Nd1 d3+ 28. Kh1 dxc2 29. Nf2 Bc5 30. Nd3 Be3 31. Bxg5 Bd2 32. Re2 O-O 33. Nc1 b4 34. Bxd2 cxd2 35. Rxd2 bxa3 36. Rxc2 Rfc8 37. Qe4 Rxc2 38. Qxc2 Qd4 39. Na2 Qxe5 40. b4 Rd8 41. h3 h5 42. Rb1 Qe3 43. Rd1 Rd5 44. Qb1 Qe2 45. Re1 Qd2 46. Rc1 Rd8 47. b5 Rb8 48. Rc3 h4 49. b6 Qd6 50. Rb3 Rb7 51. Nc3 Qc6 52. Rxa3 Qxb6 53. Qxb6 Rxb6 54. Ra4 g5 55. f4 Rb3 56. Ne2 Re3 57. Ng1 1-0
Aquí las piezas se denominan por sus siglas en inglés: K-king (rey), Q-queen (dama), B-bishop (alfil), N-knight (caballo), R-rook (torre). No se pone la "P" de peón porque como hay dieciseís, se tomó la decisión que sería redundante. Si no hay pieza que se mueve, se asume que es un peón. Cabe hacer notar además, que aquí hemos puesto la partida en notación larga, es decir, indicando de qué casilla se mueve la pieza o peón y a qué casilla llega. En general se usa la notación corta, que es simplemente la pieza que se mueve y hacia qué casilla se mueve. Si dos piezas iguales pueden acceder a la casilla a la que se mueve la pieza, hay entonces que indicar cuál es la que se mueve, poniendo las coordenadas de donde nace la jugada. Por ejemplo, una partida en notación larga se ve así:
[Event ""]
[Site "Breslau"]
[Date "1912"]
[Round ""]
[White "Levitzky"]
[Black "Marshall"]
[Result "0-1"]
1.e2-e4 e7-e6 2.d2-d4 d7-d5 3.Nb1-c3 c7-c5 4.Ng1-f3 Nb8-c6 5.e4xd5 e6xd5 6.Bf1-e2 Ng8-f6 7.O-O Bf8-e7 8.Bc1-g5 O-O 9.d4xc5 Bc8-e6 10.Nf3-d4 Be7xc5 11.Nd4xe6 f7xe6 12.Be2-g4 Qd8-d6 13.Bg4-h3 Ra8-e8 14.Qd1-d2 Bc5-b4 15.Bg5xf6 Rf8xf6 16.Ra1-d1 Qd6-c5 17.Qd2-e2 Bb4xc3 18.b2xc3 Qc5xc3 19.Rd1xd5 Nc6-d4 20.Qe2-h5 Re8-f8 21.Rd5-e5 Rf6-h6 22.Qh5-g5 Rh6xh3 23.Re5-c5 Qc3-g3 0-1
Todo esto viene a cuento porque la cuestión es que se me había ocurrido hacer en prolog, sí, en prolog, un programa que leyera archivos de esta naturaleza y desplegara la partida en formato PGN en un tablerito electrónico. Para simplificar las cosas, decidí primero usar la notación larga, porque así resulta más fácil ya que la propia notación me dice qué movimiento hay que hacer, considerando la casilla inicial y la casilla de llegada de la pieza que hace la jugada.
Un problema inicial que observé es que en prolog no hay arreglos como en muchos lenguajes como Pascal o C. No incluyo Basic porque esto es de la "Tierra Primitiva". Pero en prolog lo equivalente son las listas. Así, puedo definir una lista con ocho casilleros: [tb,cb,ab,db,ab,cb,tb], lo cual representaría la primera fila del tablero. Quizás haya que ser más precisos y poner: fila(1,[tb,cb,ab,db,ab,cb,tb]).
Si quisiéramos usar esta representación para el tablero completo, podríamos poner:
fila(8,[tn,cn,an,dn,an,cn,tn]). fila(7,[pn,pn,pn,pn,pn,pn,pn,pn]). fila(6,[b,b,b,b,b,b,b,b]). fila(5,[b,b,b,b,b,b,b,b]). fila(4,[b,b,b,b,b,b,b,b]). fila(3,[b,b,b,b,b,b,b,b]). fila(2,[pb,pb,pb,pb,pb,pb,pb]). fila(1,[tb,cb,ab,db,ab,cb,tb]).
donde tb, cb, ab, db, pb y rb son torre blanca, caballo blanco, alfil blanco, dama blanca, peon blanco y rey blanco, respectivamente (y con sus equivalentes para torre negra, caballo negro,alfil negro, etc.) La "b" representa una casilla vacía.
Muy bien, aquí ya tenemos parte del asunto zanjado. ya podemos representar en claúsulas de prolog el tablero de ajedrez. Ahora sólo resta poder manipular las jugadas y hacer que éstas se representen en el tablero.
En prolog, podemos encontrar el enésimo elemento de una lista de manera muy fácil:
% Hallar el enésimo elemento de una lista. % El primer elemento de la lista es el 1. element_at(X,[X|_],1). element_at(X,[_|L],K) :- K > 1, K1 is K - 1, element_at(X,L,K1).
Esto significa que hallar, digamos, el quinto elemento de una lista es equivalente a hallar el cuarto elemento de una lista menos su primer elemento, o el tercer elemento de una lista sin considerar los dos primeros elementos, etc. Así se hace fácilmente en prolog.
Ahora basta ver la partida y describir cada jugada como una acción en prolog. Por ejemplo, si tengo la jugada "e2-e4", basta con poner lo que hay en la casilla 52 y pasarlo a la casilla 54. Para ello, ponemos una "b" (de blanco) en la casilla 52 (e2) y lo que había en esa casilla, lo escribimos en la casilla 54. (ver el tablero en la siguiente imagen - correspondence-chess.jpg).
Para hacer la traducción de las coordenadas de cada columna a, b, c, d, e, f, g, h, podemos hacer el siguiente predicado de equivalencias:
equivalencia(a,1). equivalencia(b,2). equivalencia(c,3). equivalencia(d,4). equivalencia(e,5). equivalencia(f,6). equivalencia(g,7). equivalencia(h,8).
Así, basta ir de jugada en jugada y hacer una rutina que lea las coordenadas, inicial y final, así como la pieza que debe ir ahí y listo, el tablero cambiará su posición. Si la jugada la tenemos como una lista, por ejemplo: [e,2,e,4], el pseudocódigo podría ser algo así:
haz_jugada([X1,Y1,X2,Y2], Pieza) :- /*saca las coordenadas de la posición inicial y final de la pieza que se mueve*/ /*revisa qué pieza hay en la lista (fila) correspondiente a la posición de la coordenada inicial*/ /*sustituye el valor que haya ahí por un blanco*/ /*ve a la posición final y pon la pieza en la coordenada de la fila correspondiente*/
Es claro que este algoritmo no valida si las jugadas son legales o no, pero la idea es que las partidas dadas en formato PGN son correctas y no contienen errores. En caso de contenerlos caemos en "garbage in -> garbage out" (si le das basura al programa regresará basura).
Con esto en mente, podemos hacer un programa que lea el archivo PGN y pase jugada por jugada una partida. Sin embargo, esto sólo puede hacerse de ida, es decir, en una dirección, porque cuando se captura una pieza, por ejemplo, la pieza capturada desaparece y no llevamos registro de esto. Así, si queremos ir, por decir algo, una jugada hacia atrás, pues no podemos hacerlo porque no tenemos información de qué pieza fue eliminada del tablero.
La solución a esto es en realidad crear tantos tableros de ajedrez completos en donde cada jugada esté en uno de ellos. Así, si quiero ir a la jugada 27, entonces pinto inmediatamente el tablero 27. No me tengo que acordar si ahí hubo captura o no de alguna pieza. Si hago así las cosas, entonces mi definición del tablero de ajedrez debo modificarlo para que contemple en qué jugada está el programa en ese momento desplegando el tablero:
/*ejemplo de la estructura del tablero para el primer movimiento*/ fila(8,[tn,cn,an,dn,an,cn,tn],1). fila(7,[pn,pn,pn,pn,pn,pn,pn,pn],1). fila(6,[b,b,b,b,b,b,b,b],1). fila(5,[b,b,b,b,b,b,b,b],1). fila(4,[b,b,b,b,b,b,b,b]1,). fila(3,[b,b,b,b,b,b,b,b],1). fila(2,[pb,pb,pb,pb,pb,pb,pb],1). fila(1,[tb,cb,ab,db,ab,cb,tb],1).
Una partida promedio, digamos de 40 jugadas tendría entences 80 tableros (8 claúsulas por tablero), que se generarían en tiempo de ejecución como claúsulas de prolog. esto significa 640 claúsulas para guardar en memoria, cosa que actualmente cualquier computadora puede hacer sin mayores dificultades.
De hecho, los programas comerciales como Chessbase hacen precisamente esto, aunque como no lo hacen en prolog, usan otras técnicas. No sé en qué lenguaje está escrito Chessbase, pero pienso que es C. Si este es el caso, y si se sigue lo que aquí hemos comentado, entonces un programa que lea una partida PGN creará en tiempo de ejecución un diagrama por cada movimiento. Como en C se pueden crear arreglos bidimensionales, probablemente el tablero esté definido de esta manera y entonces, cuando se hace una jugada, se crea un tablero nuevo, en una estructura dinámica, que solamente pide la memoria necesaria cuando el sistema lo necesita.
Cuando se termina de ver esa partida, se libera toda esa memoria (es mandar los apuntadores a nil, por ejemplo), y entonces tenemos un sistema por demás eficiente.
El sistema de lectura de partidas PGN en Prolog no es el más eficiente, pero es un problema que puede ser atacado por Prolog de manera razonable y además, sin necesidad de pensar en estructuras dinámicas como en otros lenguajes, cosa que en general se aprende hasta un segundo curso de programación.
No comments:
Post a Comment