Universidad Catlica de Temuco

Ingeniera Civil en Informtica

Ajedrez, una forma de desarrollar habilidades sociales y cognitivas

Ajedrez e Informtica
Inteligencia Algoritmica aplicada al ajedrez

Camilo Alexis Silva Silva

Temuco - 1 de julio de 2012

1. Introduccin
Las primeras nociones e ideas sobre computadoras capaces de jugar ajedrez, curiosamente datan desde tiempo antes de la invencin y existencia de estas mismas. Claude Shannon en 1950 public el primer artculo cientco que inclua ideas y 'predicciones' sobre algoritmos o programas que podran determinar jugadas, a las que nombr de 'tipo A' y de 'tipo B'. Con los programas de tipo A hacia referencia a una bsqueda basada en 'fuerza bruta', este termino en el rea informtica consiste en el anlisis de todos los resultados o combinaciones posibles, por lo tanto, el algoritmos de tipo A examinara todas las posibles posiciones de cada rama del rbol de movimientos, usando el 'Algoritmo de Mimimax' (explicado ms adelante). El problema es que es imposible agotar todo el rbol por el tiempo que llevara analizarlo. Por otro lado y para evitar perder tiempo en examinar movimientos malos, Shannon sugiri los programas de tipo B, los cuales utilizaran un tipo de 'inteligencia articial estratgica', con la cual solo se analizaran las mejores jugadas de cada posicin, tratando de asimilar el pensamiento humano en una partida. El problema de este motor de bsqueda es decidir qu movimientos son sucientemente buenos como para ser considerados. Los software que hoy en da estn en el mercado se basan en las teoras mencionadas, por lo que ellas fueron el punta pie inicial para la creacin de grandes y sosticados programas, con algoritmos renados que acompaados del buen hardware actual, ejecutan jugadas sumamente rpido y con capacidades tcticas impresionantes.

2. Implementacin de los software ajedrez

Los programadores y desarrolladores de sistemas de ajedrez se basan en una serie de tcnicas para implementar sus algoritmos, a continuacin mencionare las principales.

2.1. Representacin del tablero

Las estructuras de datos se utilizan para representar piezas y su respectiva posicin, esta es la clave del rendimiento en cuanto a movimientos y evaluaciones de posiciones.

2.1.1. Requerimientos
Un software bien estructurado debe cumplir con ciertos requerimientos que entreguen una completa descripcin de una posicin de ajedrez, estos elementos son los siguientes:

El lugar de cada pieza en el tablero El jugador que tiene el turno de mover El estado de la regla de los 50 movimientos El estado del enroque de ambos jugadores Si es posible que una pieza pueda capturar al paso y de cual pieza se trata

2.1.2. Los 5 tipos de representacin del tablero mas usados Lista de piezas Usada en los primeros programas de ajedrez de computadoras, dado que en ese tiempo
no se dispona de mucha memoria, buscaron mtodos de acuerdo a lo que se tena y almacenaron los lugares de cada pieza y de cada jugador, en vez de representar las 64 casillas del tablero en una memoria.

Basado en arreglos

Una de las ms utilizadas, bsicamente consiste en una matriz de 8x8 (Figura 1),

es decir 64 casillas donde a cada una de ellas se les asigna un valor numrico, de la siguiente forma (esto para las piezas blancas, para las negras se consideran los mismos nmeros pero negativos): Casilla vaca: 0, Pen: 1, Caballo: 2, All: 3, Torre: 4, Dama: 5, Rey 6

Figura 1: Grilla de disposicin de piezas

El problema de usar este mtodo es que cada movimiento se debe comprobar, para asegurarse que esta `contenido' en el tablero, lo cual ralentiza el proceso. La solucin a esto fue crear una matriz de 12x12 o 10x12 (ms optimo en cuanto a recursos) y asignar un valor diferente a los usados en la representacin, de tal modo que cuando una pieza tratara de tomar ese como un movimiento vlido el software pudiera determinar que esa casilla no se puede considerar como tal, esto porque estamos hablando de lgica algortmica, es decir la mquina debe saber cuando una pieza esta algn extremo del tablero y para que lado los movimientos son vlidos.

El mtodo 0x88

Este mtodo usa un arreglo de 16x8=128 bits, bsicamente son 2 tableros uno real a

la izquierda y el de la derecha representa movimientos ilegales, para saber si la casilla de destino esta en el tablero real se usa un operador booleano AND, que cuando entrega un nmero diferente de cero indica que la casilla no es parte del tablero real, este mtodo es ms veloz que el mencionado anteriormente.

Tabla de bits (bitboard)

Es una secuencia de 64 bits, en los cuales son contenidos las piezas o bien

estan ausentes, esta representacin es ventajosa por el hecho de permitir realizar operaciones a nivel de bits lo cual es ms interactivo con el hardware, sobre todo para las arquitecuras de 64 bits.

Codicacin de Human

La posiciones son representadas como patrones de bits (como una codi-

cacin binaria), la representacin es la siguiente:

Pieza
Casilla vaca Pen All Caballo Torre Dama Rey Donde

Representacin
0 10c 1100c 1101c 1110c 11110c 11111c

es el bit que representa el color de cada pieza

1 = blanco, 0 = negro.

Adems se necesitan bits adicionales para representar por ejemplo: La regla de los 50 movimientos (6 bits) La columna de posible captura al paso (4 bits) El turno del jugador (1 bit) Los derechos de enroque (4 bits) Esta representacin ocupa mas recursos que cualquier otra, es decir hace mayor uso de la CPU, no obstante es ideal para almacenar posiciones a largo plazo, por ejemplo, para llevar un libro de aperturas.

2.2. Tcnicas de bsqueda

Los movimientos en el juego, son considerados por la computadora como arboles de juegos (o en matemticas discretas considerado como grafo dirigido conexo), se supone que los algoritmos deberan llegar examinar todos los movimientos y contra-movimientos (del adversario) hasta llegar a una hoja nal que es evaluada, no obstante y como he mencionado es imposible agotar el rbol completo por lo que se han implementado tcnicas de simplicacin y mtodos para aumentar la velocidad de las bsquedas y lograr ignorar movimientos triviales o considerado malos, entre los principales puedo destacar:

2.2.1. Algoritmo Minimax

Por denicin, en teora de juegos Minimax es un mtodo de decisin para minimizar la prdida mxima esperada en juegos con adversario y con informacin perfecta, este algoritmo es recursivo, es decir evala nodo a nodo por cada nivel hasta llegar a las hojas y nalmente entrega un recuento basado en valores mnimos o mximos segn corresponda, en resumen es elegir el mejor movimiento para mi suponiendo que el contrincante escoger el peor o el mas daino tambin para mi. En la siguiente imagen (Figura 2) se muestra una representacin del rbol de juego Minimax.

Figura 2: rbol de juego Minimax

2.2.2. Poda alfa-beta

Este mtodo es una extensin del algoritmo de Minimax, aplicada a juegos de dos contrincantes, es uno de los algoritmos mas utilizados dada su excepcional capacidad de aumentar la velocidad de bsqueda sin sufrir perdidas de informacin.

Funcionamiento:

Cada vez que el algoritmo evala un nodo u hoja, el algoritmo determina si los nuevos

hijos generados pueden generar una mejor utilidad de la que ya posee el nodo estudiado y si afecta al nodo padre. Si esta situacin no se produce seguir analizando es rama desperdiciara recursos como tiempo y espacio, por lo que no se sigue analizando se

poda

(de all el nombre).

Veamos una aplicacin:

puntuacin para la posicin esa posicin a su origen

En la secuencia de variantes mostrada en la Figura 3, utilizando el algoritmo

alfa-beta slo 3 de los 4 nodos terminales necesitarn ser examinados. La bsqueda determina primero la

D.

Luego de asignar su valor (0 por defecto) ste es se pasa al nodo padre de

B.

Este score establece un 'techo' para la evaluacin siguiente, la posicin

un score de +2 signica que para el adversario en la posicin Axc3 ya que de ese nodo se deba obtener el mnimo y determina que una torre es mas valiosa que un all). Al analizar la posicin

E con B , es decir, el movimiento Txd5, es mejor que 0 < 2 (ms adelante se explica como el programa

un valor de -4 es asignado a ella, por lo cual no ser necesario analizar las

siguientes posiciones terminales, ya que por regla del algoritmo conviene seguir por la rama de la posicin

(ya que en ese nivel se debe escoger el mximo). Con esto se .ahorra.analizar otra rama luego de la

posicin

C. A
es mejor

De esta forma el software determina que para la jugada de las piezas blanca en la posicin comer la reina con el all que tomar la torre enemiga con la torre de la posicin d5.

Figura 3: Ejemplo de poda Alpha-Beta

2.3. Funcin de evaluacin

Cuando el juego comienza las piezas blancas escogen uno entre 20 movimientos posibles (16 opciones para los 8 peones mas 4 opciones para los 2 caballos), as mismo las negras tienen 20 opciones de respuesta sin importar la eleccin de las blancas, por lo que slo para la primera jugada por cada pieza se tienen 400 (20x20) posiciones o combinaciones diferentes. En la siguiente tabla se muestran las combinaciones aproximadas posibles solo para 4 jugadas por cada pieza:

Movimientos Combinaciones posibles por cada jugador

1 2 3 4 400 72.084 9.000.000 288.000.000.000.000

Cuando el algoritmo obtiene el recuento o puntaje calculando por medio de una funcin de evaluacin para la posicin nal de cada rama o posiciones terminales, mide cuan buena o mala es la posicin para el jugador de turno, un valor positivo si la computadora tiene ventaja o negativo si la tiene su oponente. La frmula aplicada es la siguiente (en las siguientes subsecciones se explica de donde como obtener y

f ed, f em

f et): F = f ed + f em + f et
Mientras mas sosticada sea la funcin de evaluacin para poder dar una respuesta 'inteligente', mayor

ser el costo de procesamiento, lo cual ha llevado a establecer ciertos criterios de evaluacin.

2.3.1. Evaluacin de balance de material

Es la funcin de evaluacin ms utilizada por su simpleza y aparente efectividad para dar valor a las jugadas, se basa en la importancia que tiene la ventaja numrica en algunos casos sobre el adversario o en el peor caso el balance de fuerzas. En la siguiente tabla se muestra el peso o valor de cada pieza (esto es relativo, ya que cada software puede determinar otros nmeros pero guardando siempre la proporcionalidad).

Pieza
Rey Dama Torre All Caballo Pen

Puntos Smbolo
100 9 5 4 3 2 Rm Dm Tm Am Cm Pm

Ahora con este puntaje se puede calcular la funcin de evaluacin de desequilibrio material, cuya formula es la siguiente:

F ed = (N r Rm + N d Dm + N t T m + N a Am + N c Cm + N p P m) (N re Rm + N de Dm + N te T m + N ae Am + N ce Cm + N pe P m)
Con migas.

N (letra)

igual al nmero restante de piezas propias y

N (letra)e

nmero restante de piezas ene-

2.3.2. Evaluacin Tctica

Respecto a la funcin anterior esta es mucho ms simple, los criterios que aplica se basan en penalizaciones para las jugadas que infrinjan o bonus en caso que logre un buen evento o jugada.

Evento o jugada
Pen obstruyendo a pieza amiga Pen obstruyendo a enemigo Pen retrasado con respecto a sus compaeros La frmula para calcular esta funcin es:

Bonus(+)/ Penalizacion(-)
-20 +20 -2

F et = nP AObs 20 + nP EObs 20 nP R 2
Donde:

nP AObs: Nmero de piezas amigas obstruidas. nP EObs: Nmero de piezas enemigas obstruidas. nP R: Nmero de peones retrasados con respecto a

sus compaeros.

2.3.3. Evaluacin de movimientos

De las 3 funciones mostradas esta es la ms importante, permite denir las consecuencias de realizar un movimiento u otro. Algunas veces al realizar jugar una pieza x, a simple vista una 'buena jugada',pero sin haber considerado los movimientos futuros del adversario, muchas veces dos o tres jugadas posteriores esa 'buena jugada' se convierte en la sentencia del juego y recin ah es cuando uno se percata que la decisin tomada fue mala, ya que me produjo perdida material o inclusive la derrota. A diferencia de las dems funciones esta evala las consecuencias para cada nodo, antes de realizar algn movimiento, calicando cada pieza segn cual esta sea, por ejemplo, se sabe que las piezas como la reina torres o rey en lo ideal no se deben mover al comienzo en las aperturas, sino en la mitad o al nal, ste es el mtodo que le brinda esa 'inteligencia' al software ya que sacar una reina o peor aun mover el rey hacia adelante al principio puede en unas cuantas jugadas del adversario traer consecuencias catastrcas. Junto a lo anterior esta funcin tambin puede medir la libertad de movimiento para cada pieza, esto es poder moverse sin ningn ataque de por medio, a continuacin adjunto la tabla de peso para cada pieza donde a mayor puntaje mayor preferencia de movimiento (notar que los peones lideran la preferencia):

Pieza
Rey Dama Torre All Caballo Pen La frmula es la siguiente:

Puntos Smbolo
1 2 3 4 5 10 Rmv Dmv Tmv Amv Cmv Pmv

F em =
Donde:

np i=0 ncl

np i=0

nc j =0 T pmvij

np : Nmero de piezas propias. nc : Nmero de casilleros alcanzables para atacar a piezas enemigas. ncl : Nmero de casilleros libres para la pieza i. T P mvij : Tipo de pieza de movimiento (puntaje), de la pieza i en el v : valor en funcin de ataque o defensa.

casillero j.

2.4. Conguracin del juego

Luego de haber explicado los algoritmos principales que tienen que guardan relacin con la forma de razonamiento del software, en la siguiente tabla muestro el nivel de dicultad del juego, con respecto a la profunidad del rbol (esto mbiguo y relativo ya que segn el software la profundidad puede variar levemente).

Profundidad Nivel
4 6 8 Bsico Intermedio Avanzado

3. Caso Rybka
Este software creado por Valsik Rajlich (Maestro internacional de ajedrez y experto en programacin de computadoras), es considerado el programa de ajedrez mas fuerte, obteniendo el Campeonato Mundial de Ajedrez por Computadoras cinco aos consecutivos, desde 2007 hasta el 2011. Este software entre el 2007 y el 2008 fue puesto a prueba con humanos, enfrentado a Grandes Maestros incluso uno de lite. Bajo ciertas venjas para los humanos Rybka gan la mayora de las partidas, empat una y perdi una contra Valdim Milov (con un Elo de 2705, numero 28 mundial en el 2011), eso s con condiciones muy ventajosas a favor de Milov. El revuelo que a causado en el mundo ajedrecstico por el llamado caso Rybka, donde el software fue descalicado por dopaje digital, ha dado mucho que hablar. La Asociacin Internacional de Juegos de Computadora (ICGA) ha resuelto por unanimidad descalicar a Rybka, el ordenador tetracampen por plagio a otros software (ya se mencionarn). Luego de una ardua investigacin, se logr demostrar que Vasik Rajlich inyecto cdigos de otros competidores digitales en su software para mejorar el rendimiento de su mquina, despus de que Rybka ganara algunos torneos los espectadores se percataron que el software haca jugadas similares a las de otros programas, por lo que decidieron abrir el caso y comenzar a estudiar al respecto. Para comprobar las teoras y acusaciones a Rybka la ICGA aplico ingeniera inversa al cdigo, la cual se dene como obtener informacin o un diseo a partir de un producto accesible al pblico, con el n de determinar de qu est hecho, qu lo hace funcionar y cmo fue fabricado. Con el estudio realizado lograron descubrir que Rybka inclua fragmentos fragmentos de programacin de otros dos software de cdigo libre Fruit y Crafty. De acuerdo a las reglas esta 'mala jugada' del creador de Rybka le ha salido costosa, dado que l como su equipo de produccin estn vetados de por vida de la competencias por computadora, adems se le pidi que devolviera el dinero ganado en los torneos as como los trofeos obtenidos. Por si fuera poco la asociacin borr sus nombres de la lista de ganadores, dando el reconocimiento a los subcampeones de dichos campeonatos. Hoy en da segn las estadsticas de motores de ajedrez realizadas por IPON (http://www.inwoba.de/), el software Houdini es el motor ms fuerte superando el Elo de Rybka.

10

4. Conclusin
Despus de todo el estudio realizado y como entendido en el rea informtica, me parece destacable la inteligencia articial junto con la complejidad algortmica utilizada en la implementacin de un software ajedrecstico, la unin de stas dan nacimiento a cdigos y mtodos autnomos, capaces de decidir y determinar entre un sin n de situaciones la mejor estrategia a seguir. La forma y el renamiento que han adquirido estos mtodos utilizados a los largo de los aos es admirable; pensar que todo comienza con una 'idea', un 'indicio' y ms aun, sin existir la tecnologa. Esas premisas aos ms tarde dan inicio a los juegos computacionales de ajedrez, logrando la implementacin por medio de arboles y recursividad, en este punto y a modo de comentario personal quiero comentar que, cuando curse estructura de datos, dentro de los contenidos estaba recursividad en algoritmos y en ese momento me pregunte, esto es complejo!, pero... ser til? en que o que tipo de software, en que situacin podra hacer uso de recursividad?. Y ahora, dos aos ms tarde con este estudio respondo completamente mi pregunta. La recursividad es un pilar fundamental en el desarrollo de este tipo de aplicaciones, el anlisis que los algoritmos como el mtodo Minimax junto con la poda Alpha-Beta realizan en cada jugada es sorprendente, dada la cantidad de nodos y ramas que se extiende en cada jugada, se dice que existen ms nodos en un rbol y posiciones posibles de ajedrez que todas las estrellas de la Va Lctea, interesante no?. Aun sabiendo que jams existir un algoritmo o software capas de analizar todas las jugadas, aun as, quin lider el ttulo mundial de ajedrez en su oportunidad fue una mquina pensante, el sorprendente

Rybka,

a pesar de lo que se diga de el, de lo que se habl y el cmo lo hayan construido, simplemente

logr liderar, asi como hoy en dia lo hace el motor de all de nuestras capacidades pensantes.

Houdini,

estos gigantes han logrado sobrepasar la

capacidad humana en este juego, destacando que la inteligencia articial en cierta forma a logrado ir ms

5. Bibliograa
http://es.wikipedia.org/wiki/Ajedrez_por_computadora http://es.wikipedia.org/wiki/Representaci%C3%B3n_del_tablero_%28Ajedrez%29 http://es.wikipedia.org/wiki/Minimax http://es.wikipedia.org/wiki/%C3%81rbol_de_juego http://es.wikipedia.org/wiki/Claude_Shannon http://www.inwoba.de/ http://es.wikipedia.org/wiki/Motor_de_ajedrez http://es.wikipedia.org/wiki/Houdini_%28ajedrez%29 http://es.wikipedia.org/wiki/Rybka http://la-morsa.blogspot.com/2011/06/rybka-es-un-tramposo.html http://www.fenach.cl/docs/memoria/node37.html http://www.fenach.cl/docs/memoria/node36.html http://www.rybkachess.com/index.php?auswahl=Rybka+4+book http://thales.cica.es/rd/Recursos/rd99/ed99-0035-01/temas/partidas.html www.top-5000.nl/ps/SomeAspectsOfChessProgramming.pdf http://www.frayn.net/beowulf/theory.html

11