Tuesday, November 6, 2012

Como hacer un programa de Ajedrez

PROGRAMACIÓN
¿Por donde empezar si quieres realizar un programa de ajedrez? Ya he comentado anteriormente que si quieres ver un programa sencillo, te puedes fijar en el código del programa firstchess, es el programa más sencillo que he visto.
Pero si antes de ver código, quieres tener una idea general de lo que debe hacer un programa de ajedrez, puedes visualizar el siguiente organigrama, pertenece a un programa de ajedrez compatible con el protocolo xboard. Pulsa sobre la imagen para verla ampliada o mejor descargatela y haz un par de zoom para verla bien con un programa por ejemplo como ACDSEE.
Función principal
La función principal es básicamente un bucle que espera recibir un comando xboard del interface o GUI, una vez recibido pasa el control a la función xboard(). Lo primero que tenemos que hacer en la función principal es incluir mediante #include la cabecera de los archivos necesitados para algunas funciones que vamos a utilizar de C, también incluimos el resto de archivos en los que hemos dividido el programa, esto último no es algo standard, yo lo he hecho así pero es más normal dividir el programa en varias fuentes y utilizar variables externas si procede.
Puedes ver dicha función principal aquí.
Función xboard
Función xboard(), sustituye a la función principal si recibimos el parámetro xboard,
gracias a estos comandos, podemos hacer jugar a DanaSah con interfaces de usuario como Winboard, Arena, Fritz, Chessmaster, etc.
Para comprender dicho protocolo debes examinar la siguiente página:
http://www.tim-mann.org/xboard/engine-intf.html
Puedes ver dicha función aquí.
Funciones de libro de aperturas
Si queremos que el programa juegue los primeros movimientos de libro, necesitamos unas funciones para que nos devuelvan un movimiento del libro si la variante que estamos jugando aparece en dicho libro. Yo simplemente compruebo que la variante está en el libro, miro a ver cuales son los posibles movimientos para jugar y selecciono uno al azar. Sería mucho mejor que el programa eligiera el movimiento según unas estadísticas, por ejemplo el número de partidas que se ganan con ese movimiento, si es jugada por jugadores fuertes, etc, pero por simplicidad yo lo he hecho así.
Puedes ver dichas funciones aquí.
Algunas de las técnicas utilizadas en la mayor parte de los programas de ajedrez son las siguientes:
Algoritmo alphabeta-cutoff con ordenadación (el corazón del programa)
Como ya sabemos la función alphabeta es la que nos va a permitir buscar cual es el mejor movimiento entre la lista de movimientos candidatos. A la función alphabeta la llamaremos de la siguiente forma:
puntos = Alphabeta (alpha, beta, profundidad)
donde alpha es el valor mínimo que podrá tener la evaluación, pueder ser el que nos den mate (-mate), beta será el valor máximo que podemos obtener, que nosotros demos el mate (+mate) y profundidad será el ply hasta el que queramos jugar (a no ser que se termine el tiempo). A la hora de realizar los movimientos comprobaremos primero los movimientos mejores, empezamos por el mejor.
ahora veamos como son los pasos a seguir:
  • Si no queda profundidad para buscar evaluaremos la posición con la función de evaluar.
  • Generaramos la lista de movimientos.
  • Ordenamos los movimientos de mejor a peor (primero las capturas buenas y promociones, luego las malas, luego el resto de movimientos).
  • Mientras haya movimientos a realizar probamos a realizar uno.
  • Ahora nuestra puntuación será, puntos = -alphabeta (-beta, -alpha, profundidad-1), nuestra puntuación es la del contrario con signo negativo, estarmos utilizando una función recursiva, es decir se llama asi misma.
  • Deshacemos el movimiento.
  • Si el valor obtenido es mayor que beta, no hace falta que sigamos buscando, esto es un cuttoff (cortamos el árbol de variantes), no vamos a obtener ningun valor mejor.
  • Si el valor obtenido es mayor que alpha, ajustamos el valor de alpha a ese valor, el movimiento que provoca ese resultado es digno de tener encuenta para nuestra variante principal.
  • Comprobamos si se produce mate o tablas por ahogado, repeticiones, etc.
Ahora el pseudocódigo,
int AlphaBeta(int alpha, int beta, int profundidad )
{
    if (profundidad == 0)
    return Evaluar();
    GenerataMovimientosLegales();
    OrdenaMovimientos();
    while (QuedanMovimientos()) {
    HacerProximoMovimiento();
    puntos = -AlphaBeta(-beta, -alpha, profundidad-1 );
    DeshacerMovimiento();
    if (puntos>= beta) // cutoff
    return beta;
    if (puntos> alpha)
    alpha = puntos;
    GuardamosMovimiento();
    }
return alpha;
}
Hay que decir que normalmente cuando no nos queda profundidad no se evalua directamente la posición si nuestro último movimiento es una captura, sino que se suele llamar a otra función Búsqueda de conocimiento (quiscent search), donde se comprueba si hay una posible recaptura, no podemos cortar de golpe ya que si no se nos produciría el llamado efecto horizonte, el programa jugaría mal en profundidades bajas dejándose material, esta función tiene el mismo esquema que el alphabeta pero solamente que tenemos que llamar a un generador de capturas que solo realice capturas y promociones, cuando no queden recapturas entonces evaluaremos la posición.
PVS (Principal Variation Search)
Una pequeña modificiación sobre el algoritmo alphabeta, consiste primero en estudiar la variante que tenemos de movimientos anteriores, normalmente la variante encontrada anteriormente es la buena, si seguimos con esta variante tenemos muchas posibilidades que el movimiento adecuado sea ese. Para seguir la variante principal podemos hacerlo de 2 formas, a la hora de ordenar los movimientos, colocamos ese el primero en la lista o la segunda forma es modificando el alphabeta un poco:
  • Mientras haya movimientos a realizar probamos a realizar uno.
  • Si seguimos la pvs, puntos = -alphabeta (-alpha-1, -alpha, profundidad-1)
  • Si no estamos siguiendo la pvs o resulta que puntos es mayor que alpha y menor que beta entonces hacemos una búsqueda normal, puntos = -alphabeta (-beta, -alpha, profundidad-1)
  • Deshacemos el movimiento.

int AlphaBeta(int depth, int alpha, int beta)
{
BOOL seguirPV = FALSO;
if (depth == 0)
return Evaluar();
GeneraMovimientosLegales();
OrdenaMovimientos();
while (QuedaMovimientost() {
HacerProximoMovimiento();
if (seguirPV == VERDADERO) {
puntos = -AlphaBeta(-alpha-1, -alpha, profundidad-1);
if ((puntos>alpha) && (puntos< beta)) // ¿Fallo?
puntos=-AlphaBeta(-beta,-alpha,profundidad-1);
} else
puntos=-AlphaBeta( -beta, -alpha, profundidad-1);
DeshacerMovimiento();
if (puntos>= beta)
return beta;
if (puntos> alpha) {
alpha = puntos;
seguirPV = VERDADERO;
GuardamosMovimiento();
}
return alpha;
}
Seguir la variante principal encontrada anteriormente hace que el algoritmo alphabeta tenga un redimiento de más del 100%, no se exactamente cuanto (¿quizás un 250%?), pero es algo obligatorio de hacer vamos.
Movimiento nulo
Otra posibilidad es cuando nos toca mover, pensar más en el movimiento que nos va a hacer el contrario que en el nuestro, de esta forma podemos ver más fácil las amenzas, a esto se llama técnica del movimiento nulo y consigue de uno a 3 ply más de profundidad.
Desgraciadamente el movimiento nulo no podemos utilizarlo en todos los momentos, no debemos utilizarlo si estamos siguiendo la variante principal (esto no ayudaría), pero tampoco lo debesmos utilizar por ser peligroso cuando estamos en jaque, si anteriormente ya hemos utilizado otro movimiento nulo, ni tampoco si hay poco material, yo lo utilizo cuando al menos en el tablero queda alguna torre.
El código correspondiente al movimiento nulo lo introducciremos en la función AlphaBeta justo antes de comenzar la Generación de movimientos.
if ((material >= VALOR_TORRE) && ( !EnJaque) && (profundidad>0) && ( !seguirPV) && ( !hahabidoNuloantes)) {
CambiarTurno();
puntos = -Alphabeta(-beta, -alpha, profundidad-1- R);
RecuperarTurno();
if (puntos>beta)
return beta;
}
R suele tener un valor normalmente de 2 ó 3, a mi me funciona mejor 2.
Es increíble este código, con apenas 10 líneas de código añadido podemos aumentar la velocidad de búsqueda en 2 ó 3 plys en el mismo tiempo.
Profundidad iterativa
Hace que si se acaba el tiempo tengamos un movimiento al menos decente de nivel anterior, además muy importante es que ayuda a ordenar los movimientos y nos sirve para visualizar la línea principal en cada nivel. En lugar de buscar entre todos los movimientos en un nivel de profundidad, el programa trata inicialmente de seguir una línea cercana a la anterior, si hay un cambio brusco de evaluación entonces examina entre todos los posibles valores, esto se hace indicando al programa un margen que se llama ventana de apiración, aspiration windows.
Extensiones
Normalmente tendríamos que intentar reducir por todos los medios el árbol de variantes, pero hay situaciones en las cuales nos puede servir el pensar más profundamente, unos casos que son habituales es cuando nos encontramos en jaque, cuando un peón está a punto de coronar o corona, cuando solo hay una respuesta posible al movimiento del contrario.
El código para estas extensiones lo incluiríamos dentro del alphabeta, empezaríamos después del movimiento nulo:
if (EnJaque )
profundidad++;
GenerarMovimientosLegales;
if (número_movimientos ==1)
profundidad++;
OrdenarMovimientos();
HacerProximoMovimiento();
if ((tipo_movimiento == Promocion) || (fila_ = 7))
profundidad++;
Antes de nada tengo que deciros que teneís una buena página de programación, la de Bruce Moreland, http://www.seanet.com/~brucemo/topics/topics.htm en la que aprendí muchas de las cosas que escribo aquí.
 
 
credito a:
http://www.euskalnet.net/pecas/
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)