Showing posts with label descripción de posiciones. Show all posts
Showing posts with label descripción de posiciones. Show all posts

Wednesday, September 02, 2015

Un lenguaje para patrones en ajedrez II


En el artículo pasado hablamos de un lenguaje de patrones para las posiciones de ajedrez. Definamos más formalmente esto: Un patrón es una generalización de un objeto que contiene sus características esenciales. En ajedrez podemos definir las características de una posición en términos de ataque y defensa. Así pues, solamente hay dos tipos de relación.

Un ataque se da cuando una pieza de un bando ataca a otra (del bando contrario). Una defensa se da cuando una pieza de un bando defiende a otra (del mismo bando). Es decir la definición de ataque se da entre piezas rivales y el de defensa por piezas del mismo bando.

Las relaciones más importantes pueden definirse así:

  • P1 P2 donde P1 (pieza 1) ataca/defiende directamente a P2 (pieza 2). Por ejemplo: T p (Torre blanca ataca peón negro)
  • P1 P2 P3 donde P1 ataca directamente/defiende a P3 vía P2. Por ejemplo: T D p (Torre blanca ataca al peón negro indirectamente a través de la Dama blanca). A eso le denominamos ataque de rayos X.

También podemos definir la relación de un ataque/defensa/dominación a una casilla, P1 C1, donde P1 es una pieza y C1 es una casilla determinada.

Las relaciones que parecen más importantes son:

  • P1 C1 Pieza ataca/defiende/domina a Casilla
  • P1 P2 Pieza 1 ataca/defiende Pieza 2
  • P1 C P2 Pieza 1 controla/domina la Casilla C desde donde ataca/defiende a la pieza 2
  • P1 P2 P3 Pieza 1 ataca/defiende a P3 indirectamente vía la pieza 2
  • P1 P2 P3 P4 Pieza 1 ataca/defiende a la Pieza 4 indirectamente a través de P2 y P3.

Los siguientes ejemplos pueden mostrar cómo pueden representarse los patrones y además, cómo ellos representan (en posiciones que aparentemente son distintas), el mismo patrón. Empecemos por definir la relación ataque/defensa:


Alfil ataca el peón negro de h7 y a su vez es defendido por el peón de c2.

Cabe señalar que esta es una descripción estática porque no se define movimiento alguno a través del patrón definido. Requerimos un componente dinámico, que nos indique qué jugada o jugadas hay que hacer para que el patrón se considere ganador.

----

La necesidad de definir una parte dinámica basada en las jugadas por hacer por parte del bando ganador en el patrón muestra porqué el patrón es importante ya que define una posición ganadora o de la que se saca ventaja. No me queda aún muy claro qué profundidad (cuantos plies) deben describirse. En una primera aproximación bien podríamos definir solamente un ply (media jugada, es decir, un solo movimiento de alguno de los bandos), y esperar que un motor de ajedrez hiciese el árbol de variantes para encontrar la secuencia ganadora.

Podemos entonces asociar movimientos a los patrones definidos. Una P1 que capture una P2 y le dé la ganancia de la pieza 2 podría escribirse como:

P1 P2 [+P2]

Con ese criterio podríamos establecer la siguiente notación, por ejemplo, para cuando la dama captura una pieza rival: D p [+p], D t [+t], D c [+c], D a [+a], D d [+d]. Obviamente no puede existir D r [+r] porque el monarca rival nunca se captura. Recibe mate y se acaba la partida.

Si tenemos a una dama que captura a una torre enemiga (véase siguiente diagrama) pero a su vez esa dama es capturada por un peón que defiende a la torre mencionada, escribiríamos:



La dama blanca captura la torre negra (que está defendida)

D t [+t – D]

Es decir, estaríamos hablando de un sacrificio de dama propia por una torre rival.

En las siguientes dos posiciones podríamos definir el factor dinámico de la siguiente forma:


Nimzowitsch - Tarrasch
San Peterburgo, 1914
Juegan las negras
Elemento dinámico: 1. … Axh2+



Lasker - Bauer
Amsterdam 1889
Juegan las blancas
Elemento dinámico 1. Axh7+


Y suponer que un motor de ajedrez puede hallar el resto de la combinación que no excede 10 plies, (cinco jugadas).

Otra opción, que ahora estoy investigando es la de generar la posición final a partir del patrón. Por ejemplo, en las posiciones anteriores (Lasker-Bauer y Nimzowitsch-Tarrasch):

Lasker-Bauer:


                                 Posición Inicial                                  Posición final


Nimzowitsch-Tarrasch:


                                Posición Inicial                                  Posición final


Podríamos decir que hay una transformación entre la posición inicial (la cual por el momento no sé cómo puede definirse), cuando existe el patrón y el resultado final de la secuencia de jugadas que llevan a obtener la ventaja (o el triunfo). Esta operación bien podría denominarse el colapso (o reducción) de la posición rival (que nace de la secuencia obligada que lleva al bando ganador a obtener la ventaja).

Esto desde luego puede representarse como un árbol de posibles variantes, tarea no muy difícil de hacer con una computadora. Así pues, a partir de la secuencia ganadora, se pueden ver todas las sub-secuencias que llevan a la posición final ganadora (o a la que saca una ventaja definida).

Cabe señalar que en los ejemplos no importa realmente el color de las piezas en el patrón. Si las negras son las que lo ejecutan, lo único que hay que renombrar son las coordenadas (restando 9 a cada una de ellas, es decir, un alfil blanco que ataca el peón de h7 se convierte en un alfil negro que ataca h2).

Un hecho importante sobre este lenguaje de patrones es que permite describir posiciones que precisamente tiene sus características generales. Sin embargo, las posiciones mostradas no son estrictamente las mismas y ahora me parece claro que habría que considerar un índice o una métrica que definiera qué tan similares son los patrones de posiciones específicas. Es decir, parece evidente que no todos los elementos se repiten pero que hay algunos que son fundamentales para definir al patrón.

Monday, August 24, 2015

Un lenguaje para patrones en ajedrez


Hace unos meses escribí un artículo para un congreso que se llevaría a cabo en Holanda. Organizado por la ICCA (que es la Asociación Internacional de Juegos por Computadora), mi colaboración era un análisis de uno de los artículos más relevantes en lo que se refiere a la representación de las posiciones en ajedrez. El artículo, que salió originalmente en el Scientific American a principios de los años setenta del siglo pasado, hablaba de un programa (el US chess program), que jugaba a través del análisis de ciertas instancias, que formaban algo así como patrones.

En el artículo que escribí ponía cuatro posiciones, las cuales se veían diferentes pero las cuatro eran finalmente el mismo patrón. El artículo no fue aceptado pero incluso así, los revisores me mandaron los "peros" que hallaron al mismo. Uno de los argumentos era, ¿cómo puedes caracterizar las cuatro posiciones que identifican el mismo patrón? Buena pregunta. En el seminario del IIMAS, en donde hago el doctorado, presenté mis reflexiones sobre el artículo que escribí y los doctores Jorge Luis Ortega Arjona y Héctor Benítez volvieron a hacer la misma pregunta. Más aún, el Dr. Ortega iba un poco más allá cuando en alguna de nuestras sesiones semanales de avance de la tesis me preguntaba: ¿Cómo puedes generalizar estos patrones (y no sólo para el ajedrez, sino para los juegos de suma cero? De nuevo buena pregunta a la cual no tenía contestación.

Pues bien, me puse a tratar de entender cómo podía representar las posiciones en ajedrez y descubrí que quizás un lenguaje que inicia en los grafos podría ser la solución. La idea no es absolutamente mía y hay un par de referencias al respecto (ver bibliografía). Sin embargo, de pronto hallé que podía representar las posiciones que había puesto en mi artículo de forma tal que eran las cuatro identificables con el mismo patrón. Asombroso. Pero más aún el notar que la idea en realidad no es nada complicada. Funciona así.

Todo comienza con los elementos del ajedrez más básicos: el ataque y la defensa. Los ajedrecistas vemos cuando nos atacan una pieza o cuando nosotros defendemos alguna o incluso, cuando somos nosotros los que atacamos. En general, lo que decimos es que una pieza ataca a un peón, sin necesariamente decir en qué casilla está. Esto, curiosamente, es como los jugadores recuerdan posiciones. Ya De Groot halló que el ajedrecista no ve posiciones como si fuesen fotografías, sino que el cerebro las codifica como un conjunto de relaciones entre las piezas. Esta es la razón por la cual cuando De Groot puso posiciones -sin lógica ajedrecística- para que los jugadores de su experimento las recordaran, estos tuvieron las mismas dificultades que tenían los aficionados. Por una parte entonces, se elimina el mito de que el ajedrecista tiene una memoria fotográfica del tablero y por otro, se confirma que de alguna manera el jugador recuerda las relaciones que hay entre las piezas en una posición dada.

Por ejemplo, consideremos un alfil blanco en c2 que ataca un peón negro en h7 (véase diagrama). Un ajedrecista recordará esta posición no por la posición de las piezas en particular, sino por la relación que hay entre el alfil blanco y el ataque al peón negro en h7. De hecho, si le pedimos al ajedrecista que nos reproduzca la posición del diagrama (meses después de hacer el experimento), quizás el jugador simplemente se acuerde del ataque pero no pueda decidir si el alfil está en b1, c2 o d3, por ejemplo.


Un alfil blanco que ataca a un peón en h7

Así entonces, hablamos de relaciones entre las piezas y el único modelo al respecto, como ya dijimos, es ataque/defensa. Considerando esto, pensemos en definir que una pieza A ataca a una pieza B, Podemos representar eso como:

P1 P2

en donde P1 es la pieza 1 y P2 es la pieza 2. Si es un ataque es claro que P1 es de un color y P2 es del color contrario. Si son del mismo color hablamos de una defensa entre ambas piezas. Ahora consideremos la siguiente posición (ver siguiente diagrama):


La dama blanca ataca el peón negro de f7. 
La torre blanca en f1 ataca (con rayos X) el peón de f7

En este caso, tenemos que la Dama blanca (P1), ataca el peón de f7 (P2), pero también tenemos que la Torre en f1 (P3) ataca también el peón negro en f7. Podemos pensar que el ataque de la torre blanca es como en rayos X, pues pasa por sobre la dama, que se encuentra en f3. Si ponemos la dama blanca en h5, podemos ver con flechas los ataques de ambas piezas sin necesidad de pensar en este ataque como de rayos X.

En términos del lenguaje de patrones, podríamos poner una posición que bien podría ser equivalente:



Pero pensemos también que las piezas no atacan/defienden necesariamente a otras piezas. Podríamos pensar que las piezas atacan o defienden casillas. Por ejemplo, un peón blanco en h3 defiende la casilla g4. De esta manera podemos escribir:


P1C1

Donde P1 es la pieza 1 y C1 es una casilla en particular. En el caso del diagrama podría ponerse como P(h3)g4 o Ph3-g4, por ejemplo.

Así pues, en primera instancia estos son los bloques de un lenguaje de patrones para describir posiciones de ajedrez.

Con esto en mente, ¿Cómo podrían describirse las siguientes posiciones, en donde todas se comparte el mismo patrón? Veamos los siguientes ejemplos y saquemos al final conclusiones:

Posición 1:


Díaz Lombardo, I - López, M
Juegan las negras

La posición puede describirse (letras mayúsculas son piezas blancas, letras minúsculas son piezas negras): 

d(Pf2)
t(Pf2)
t(c1)

Posición 2:


McNab - Mullen
Juegan las blancas

D(pf7)
T(pf7)
T(a8)

Posición 3:


Atasik - Ruck
Juegan las blancas

D(pf7)
T(pf7)
T(h8)


Con estos tres primeros ejemplos basta. Todos se expresan de la misma manera. La Dama y la Torre (blancas o negras, sea el caso), atacan el peón de f7 (o f2) y la torre restante puede entrar en la octava fila del rival. En terminos generales debe estar claro que se trata de un patrón al menos similar, muy similar, a pesar de que no necesariamente las piezas están en los mismos lugares.

Pero observemos estos otros ejemplos:

Posición 4: 


Lasker-Bauer
Juegan las blancas

D(h5) //no importa si hay o no una pieza en esa casilla
A(ph7)
A(pg7)
T(f3)

Posición 5:


Polgar, Judit - Karpov, A
Juegan las blancas

D(h5)
A(ph7)
A(pg7)
T(h3)

Posición 6: 


Miles - Browne
Juegan las blancas

D(h5)
A(ph7)
A(pg7)
T(c3)

Posición 7:


Nimzowitsch - Tarrasch
Juegan las negras

d(h4)
a(Ph2)
a(Pg2)
t(d5)

Si se observa con cuidado, veremos que estamos hablando del mismo patrón. En esencia es prácticamente el mismo. 

Cabe decir que esta es una primera aproximación. Es claro que la descripción no es estrictamente la misma para las posiciones, pero las semejanzas y similitudes son evidentes para cualquier ajedrecista. Por ello, hay que señalar que estamos hablando de un lenguaje que debe lidiar (o al menos intentar hacerlo), con posiciones que no necesariamente son iguales, sino que son similares. En otras palabras, tienen un margen difuso.

Dentro de poco hablaré de cómo extender el lenguaje para que sea más dinámico. Por el momento, es claro que solamente estamos describiendo las posiciones estáticamente, pero evidentemente, debe haber un componente dinámico, es decir, las jugadas por hacer.

Bibliografía:

Learning to play chess selectively by acquiring move patterns
Lev Finkelstein and Shaul Markovitch
ICCA 1998

Adaptive Pattern Oriented Chess
Robert Levinson y Richard Snyder
AAAI-91 Proceedings 1991