AMYAN


Amyan
Cómo funcionan
Links


Páginas :

Presentación
Sailor Mercury
Amyan
Series Anime
Juegos
Layla
Tsuky
Política de Privacidad
Hosting (de un hermano)

Antonio Diéguez
e-mail:
zodiamoon en yahoo.com

   

Cómo funcionan... :)


Si quieres programar un juego de ajedrez, o si quieres desempeñarte mejor cuando juegas contra uno o si tienes curiosidad te sería interesante conocer cómo le hace más o menos aquel programita que bajaste o compraste el otro día para hacer como que sabe jugar ajedrez (!?)

Primero que nada quiero decir que esto es sólo para introducir a personas interesadas en este tema, cualquiera que ya haya hecho un juego de ajedrez o ya sepa de esto sabrá como se implementarán este tipo de juegos, pero este documento de todas fomas tiene valor de tipo curiosístico, sobre todo si te gusta el ajedrez y como que te llama mucho la atención esto del ajedrez jugado por computadoras, o si estás cansado de tanto inglés de otras páginas. Ahora bien, si no sabes programar, te cuento que es un proceso en el que se "le instruye" al compu qué hacer, y se suele hacer de una manera muy objetiva y clara, a menos que se utilicen algunas técnicas de inteligencia artificial que tienen resultados difíciles de preveer, como machine learning, (o deeplearning que está de moda y que utiliza bastante DeepMind, que juega al GO y que jugará con Lee Sedol en marzo 2016), pero que yo sepa no ha tenido mucha relevancia en el ajedrez, aunque yo ya no sigo este tema.


Okey empecemos, pero me gustaría que sea participativo, alguien?

pregunta: Un programa de ajedrez calcula las variantes?

respuesta: Sí, un programa de ajedrez claro que calcula variantes...


pregunta: Pero no son demasiadas variantes? por ejemplo al comienzo de la partida son 20 las jugadas posibles y en el medio juego son aún más, y por ejemplo calcular seis movimientos en el medio juego asumiendo 35 movimientos posibles cada vez serían 35x35x35x35x35x35 = 1.838.265.625 !!, o sea más de mil millones de combinaciones para sólo inspeccionar 3 jugadas !!!

respuesta: sencillamente así como tú no tienes necesidad de calcular tantas millones de jugadas, el programa tampoco...


pregunta: claro eso pensé pero y como le hace para ver algunas y otras no? y como le hace por ejemplo si todas sus jugadas no ganan material ni hacen mate, como elige "su mejor" jugada?

respuesta: sencillamente asi como al ver una posición en tu mentecilla, ella te parece linda o fea, qué tan linda o qué tan fea (si es que te decides), un programa de ajedrez tambien debe juzgar posiciones, y así descartar muchas continuaciones sin sentido también.


pregunta: guau! pero igual todo esto esta como en el aire, como puede ser eso posible?

respuesta: Mira te lo voy a explicar en más detalle...


Un programa de ajedrez suele tener dos partes importantísimas, su algoritmo de búsqueda y su algoritmo de evaluación de posiciones. A esta evaluación se le suele llamar estática, pues lo usual es que por sí sola nunca vea variantes, y sólo usándola dentro de una búsqueda es posible obtener una evaluación dinámica.

En la evaluación de una posición, se determinan la presencia o ausencia de determinados factores y en qué grado (je esa frase la leí en otro lado). Naturalmente el material ocupa un papel importante, y entre otros factores se encuentran la seguridad de los reyes, estructura de peones y movilidad. Sé que todavía esto está como en el aire, pero no tiene nada de mágico!, a decir verdad tiene mucho de brutágico, ya que aquí se le asigna un puntaje a cada cosa, y de la manera más espeluznante...

Te doy un ejemplo, una evaluación muy sencilla sería:

* 100 por cada peon,
* 315 por cada caballo,
* 330 por cada alfil,
* 500 por cada torre,
* 940 por cada dama,

* 1 punto por cada casilla a la que se puedan mover los alfiles y las torres,
* 12 puntos por tener un peón en el centro,
* De -20 hasta 15 gradualmente por la posicion de cada caballo (desde un rincon del tablero hasta el centro),
* De -4 a 4 gradualmente por la posicion de la dama(desde un rincon hasta el centro),
* -10 por peon doblado,
* -15 por peon aislado,
* De 20 a 80 por peón pasado, dependiendo de cuán cerca esté de la casilla de coronación,
* Bonus gradual para la posicion del rey, en la apertura mientras más cerca del centro es más malo y en los finales de partida (poco material) al revés.

Una evaluacion seria los puntajes de un bando menos los del otro.
Definamos la evaluación desde el punto de vista del compu, sería bonuses de sus piezas menos bonuses de las piezas del contrincante, + algún otro factor que no se pueda evaluar por separado. Cosa que mientras más positivo el resultado la posicion es supuestamente mejor para él, y asignando el cero a una posición supuestamente igualada.

Te fijas? naturalmente es una evaluación muy mala y ningún programa de ajedrez decente tiene una tan sencilla pero te impresionaría notar que sólo con eso y un buen algoritmo de búsqueda ya un juego de ajedrez te impresionaría porque pareciera que estuviera vivo... y de hecho como actualmente los programas ven continuaciones bien largas pues al final terminan jugando extremadamente bien!
Considerar de una manera aceptable cualquier cosa en la evaluación naturalmente requiere más tiempo de cómputo, provocando que el programa se pasee por menos posiciones por segundo(siendo "más lento"), así que no necesariamente más "inteligente" por cuanto a evaluación significa automáticamente más fuerte.
Respecto a esto hay programadores que prefieren hacer sus programas más inteligentes que rápidos, otros al revés y la mayoría ni lo uno ni lo otro...
Por supuesto que no necesariamente un programa "más lento" que otro significa que tiene una evaluación más "inteligente", ya que pueden ser de distinta calidad y también en una buena búsqueda hay inteligencia y puede consumir un tiempo apreciable. Además por lo menos respecto a los programas amateurs, un programa puede ser mucho más lento que otro simplemente porque el autor ha sido menos capaz o no se ha preocupado de optimizar el código.

Por supuesto que una evaluación programada con reglas de este estilo, aunque sean muchas, y relativamente bien hechas, difícilmente igualará el criterio de un buen jugador. De partida la evaluación la escribe el programador así que qué se puede esperar de esto? bueno la verdad algunos en esta parte han experimentado con técnicas de machine learning aunque no tanto para escoger los parámetros que considerar sino para escoger los valores de puntaje a utilizar dentro de una estructura ya definida por el programador (y ha servidor pero no tanto). Bueno, una cosa muy rescatable de la evaluación es la "confiabilidad" en que el programa al menos nunca se equivocará en evaluar exactamente cómo le dicen que lo haga, y en todo caso esta es una parte que se supone que con el tiempo se va mejorando o al menos disminuyendo sus inexactitudes, mientras el humano puede tener muchas dudas, ser inconsecuente, etc).
De todas formas, es lo que le da el estilo de juego al programa y lo que lo mueve.

Para que el valorar una posición tenga alguna utilidad, viene el otro gran aspecto, que es la búsqueda, cuya efectividad depende de los detalles del algoritmo en sí y el hardware sobre el cual está corriendo el programa... Para que tengas una referencia respecto de esto, mi juego, en mi excompu, un AMD K6 a 233 Mhz, alcanza mínimo 18.000 posiciones visitadas por segundo, y aún así se me hacía poco, y en mi actual compu, un CELERON a 1.3 Ghz, es más de 6 veces más, pero igual... Muchísimos softwares de ajedrez, ya sean comerciales o amateurs, son dos veces más "rápidos" que amyan o aún más, en cuanto a pos/sec. Deep Blue en su segundo match ante Kasparov, evaluaba alrededor de 200.000.000 de posiciones por segundo (!), no sé si Kasparov pase más allá de las 5 si es que se puede decir de esa manera, así que ahí notamos por donde va la fuerza del ser humano y por donde va la fuerza de las máquinas en este aspecto, no es que haya demasiada inteligencia artificial o algo así, simplemente prima la rapidez de la máquina, que no hace más que eso y no sabe ni amarrarse los cordones(de tener :) )

Pero y cómo funciona la búsqueda? bueno debemos usar nuestra función de evaluación de alguna forma... el ejemplo más trivial es, que a partir de la posición actual en el tablero, siendo el turno del compu, éste calcule todos sus movimientos que puede efectuar y los "pruebe" él solito y evalúe cada una de las posiciones resultantes con su función de evaluación, y naturalmente la mejor jugada sería la que le dio una mejor valoración resultante.
Ahora bien... eso es sólo para 1 media jugada de profundidad de cálculo, como te podrás dar cuenta, pero agregar más medias jugadas no es muy difícil... lo que se forma es un lindo arbolito. Si ya has programado recursiones te sería muy fácil porque esta es una muy simple, maximizar, minimizar, maximizar, minimizar,...

En el árbol de variantes, el programa va cogiendo, en el caso de la más pura fuerza bruta, las mejores jugadas para cada bando en cada nodo del arbolito, según evaluaciones efectuadas en las posiciones "de más al fondo".
Al cambiar de nodo en nodo (nodo=cada posicion dentro del arbolito), la posición en la memoria la vas cambiando (haciendo cada movida, y deshaciéndola luego de analizar la variante).
Nota : yo digo árbol pero no implica que haya que implementar la estructura de datos llamada árbol ok?
Naturalmente para implementar la búsqueda antes que nada hay que darse el trabajo de tener representada ya la posición con los datos sobre cómo está el tablero y las piezas y tener una función por ejemplo a la que le pases la posicion y te calcule las posibles movimientos legales, entre otras trivialidades. Trivialidades no porque sea implementable en un rato sino porque hay más brillo en la búsqueda y la evaluación claro está.
En los nodos de más al fondo (las posiciones más profundas), la posición es evaluada, obteniendo así un puntaje en aquellos nodos, que luego implicarán un puntaje en el nodo padre luego de tener un puntaje todos los nodos hijos. Dependiendo del turno en cada nodo padre se elige el máximo de los puntajes de los hijos para él (si le toca al bando del computador) o el mínimo (si le toca al bando del contrario), habiendo definido nuestra evaluación siempre como bonuses del bando del computador-bonuses del bando contrario. Si lo piensas bien, esto funciona, y el nodo raiz, al final queda con un puntaje estimativo de la posicion inicial..., y la jugada a jugar por el compu será el movimiento que llevó a ese puntaje...

Okey ahora mi buen observador, seguramente ya te preguntaste qué pasa si en el último movimiento calculado en la variante X un bando juega alfil por caballo, o algo así, en caso que el caballo haya estado defendido posiblemente el alfil también se muere y ya, pero eso estaría mas allá del cálculo del programa, así que la evaluación, que vería un caballo menos para un bando sería completamente errónea...
Bueno lo que se hace siempre, teniendo en cuenta esto, es a partir de una cierta profundidad, no terminar inmediatamente retornando la evaluación, sino además permitir ver jugadas pero achicando el espectro... lo más común y simple es probar sólo las capturas, que son las jugadas que pueden cambiar radicalmente una posición, no es así? de esta manera se retorna lo que más le convenga al bando que tenga el turno(el puntaje de evaluar o el de efectuar alguna captura), recuerda que este necesita ya sea el mínimo o el máximo dependiendo si es el bando del compu o no...
Además de capturas se pueden ver otro tipo de jugadas en esta parte final o Quiescence Search como le dicen en inglés... ("búsqueda de quietud") ya sea jugadas que hacen jaque al enemigo o atacan una pieza, o bien si nos están amenazando por ejemplo una torre con un caballín procurar verificar si se pierde la pieza.

Una pregunta me hacen aquí de que si se escoge una profundidad definida entonces si el programa está jugando con tiempo entonces como responde cuando debe? elegimos la profundidad que parezca adecuada de antemano? bueno la verdad es que no hay para qué, lo común es hacer una búsqueda de profundidad igual a 1, luego a 2, luego a 3 etc. (no se cuenta la qsearch aquí) Puedes imaginar que como cada búsqueda de éstas (o iteración) no demora tanto en relación a la siguiente, a fin de cuentas la mayor parte del tiempo se tomará en la última iteración asi que no sería mucha pérdida, además que así en todo momento se sabe cual es la mejor jugada no? y además, por lo que veremos luego, una iteración x ayuda a que la iteración x+1 sea más eficiente.

Bueno espero que haya quedado todo claro hasta ahora, pero todavía no se ve nada de descarte de jugadas malas cierto? empecemos...

Primero que nada, hay algo muy obvio que nos ayuda muchísimo en este aspecto y es que cada quien juega lo mejor que puede. Ahora bien, por lo menos yo a veces cuando juego con un rival débil (más débil que yo incluso asi que imagínate) me puedo pasar rollos con que se le va a ir algo y me arriesgo y no juego la que creo es mi jugada más correcta, pero esto no lo consideraremos ok? olvidemos también a Lasker por un momento en este tema.
Qué implica eso? bueno, si sabes jugar ajedrez ya lo sabes, móntate en un nodo en el cual le toque al compu jugar y supón que ya le viste que su primera jugada que le pruebas (cualquiera sirve en realidad) le da finalmente 46 puntos, bastante bien para nuestro programita, y ahora sigues analizando su segunda opción(jugada) y en aquel nodo hijo, en el cual juega el bando contrario, la primera jugada de este sujeto arroja un puntaje 23 como resultado. A ver qué cosa útil me puedes deducir con eso...?

Seguramente sabes a que me refiero, no? eso espero... lo que pasa es que en ese caso no necesitamos analizar ahora la segunda jugada del sujeto (del contrario) puesto que concluimos que este nodo hijo tiene un valor 23 o menos (recuerda, este hijo va a querer el mínimo...) y su nodo padre jamás lo elegirá puesto que el compu ya tiene una mejor alternativa con 46 puntos (recuerda, este va a querer el máximo...). En este caso, estos 46 puntos pasaron a ser un limite inferior para el puntaje del nodo, y en cuanto se vea que en alguna rama inferior que nazca de una jugada paralela arrojará 46 o menos, esa rama se termina porque no tendrá incidencia.
Si lo piensas bien, esta observación vale para cualquier punto del árbol y ya sea el turno del compu o no, sólo que como que se revierten algunas cosas.
Bueno, un poquito de terminología: cuando se implementa esta cosa en un lenguaje de programación le llaman "alpha-beta", vale para ajedrez, damas y juegos por el estilo, el alpha es el límite inferior y el beta es el superior, y son parámetros cambiantes de la función recursiva de la búsqueda. Especifícamente cuando pasa eso de que no hace falta seguir viendo las alternativas de un bando le llaman "cut-off", okey mucho inglés asi que sigamos.

Okey cual es la ganancia con la idea anterior? bueno, depende. Se puede optimizar tratando de calcular primero las mejores jugadas en cada nodo para ver si ocurre uno de estos cut-offs luego. Una buena idea es guardar en memoria jugadas que han logrado estos cut-off en algún nodo y probarlas primero en otros nodos, especialmente de la misma profundidad, aunque tambien se comete la bruteza de guardar en memoria las jugadas que mejor han servido para cada posicion vista, y a eso viene el uso de una tabla de hashing, a menudo denominada tabla de transposicion, donde se guardan la id de la posición(fácil de calcular, difícil de repetirse pero no necesariamente única, para ahorrar memoria y tiempo) y la jugada recomendada y otras cosas. Otra pequeña idea por ejemplo es cuando se revisen las jugadas de caballo que se vean primero las que mueven hacia el centro ya que un movimiento a un rincón de un caballo no es precisamente un buen candidato, y ver jugadas de piezas que avancen antes de las que retroceden y cosas como esas. Qué opinas?

Me preguntan de nuevo, cuánta es la ganancia? y yo respondo, muchísima. Hay que tener en cuenta que la tabla de hashing también sirve para disminuir el doble trabajo cuando ocurren transposiciones( por algo el nombre :) ). La cantidad de posiciones que se deben ver, por ejemplo, pueden pasar de un factor 35 a un factor 6 o algo así.
Y menos mal que se puede descartar tanto matemáticamente porque descartar de otra forma es un lío, te imaginas? Este es un punto de constante mejora en cada programa, y lo que provoca más diferencia de fuerza entre los programas de ajedrez, bastante más incluso que la función de evaluación.
El chiste generalmente está en que no necesariamente se debe de constatar que, en el ejemplo dado anteriormente, una rama paralela arrojará 46 o menos, sino que, sin necesariamente probarlo, se estime o anticipe eso en cierto punto. La verdad esto suena a veces tan técnico pero es lo mismo que haces al jugar ajedrez.

Bueno los descartes se dividen en dos tipos:

1.- futiles (creemos que el nodo será <=alpha), o
2.- auspiciosos (creemos que el nodo será >=beta).

1.- Por dar un ejemplo, bien profundo en la búsqueda(cerca de los nodos terminales), si la evaluación es menor que alpha(menos un margen) podrían no verse todas las jugadas, sino sólo las capturas, las que atacan otra pieza, avanzan un peón pasado, etc. y en el caso que el nodo no sea de tan al fondo, lo que se hace es una reducción para la mayoría de las jugadas (por ejemplo, todo lo que no sea una captura o una killer(jugada que ha sido buena anteriormente) o una amenaza, se ve con 1, 2 o más movimientos menos, ahora bien si su puntaje resulta mayor que alpha hay que volver a calcular con la profundidad pendiente original.
2.- Aquí es parecido pero respecto a beta. Ahora bien... un descarte muy conocido y muy usado con leves diferencias es la jugada nula("null-move" en inglés), y te la explico: en los nodos en los que la desees hacer, antes de calcular los posibles movimientos primero haces una null-move, o sea, no mueves y pasas altiro al nodo hijo, el valor que le dé el nodo hijo al padre es usado como un límite para el futuro valor del padre y si tienes suerte, este valor es lo suficientemente grande (en el caso de turno del compu) o lo suficientemente pequeño (en el caso de turno del otro) como para no analizar ninguna alternativa en absoluto debido a un corte auspicioso, y más encima cuando se usa null-move se suele achicar + la profundidad pendiente cuando le pasas el trabajo al nodo hijo (es decir no sólo un movimiento menos, tres funciona bien por ej.), teniendo muchísima confianza en el principio "alguna jugada debe de haber que sea preferible a pasarle el turno al contrario", qué opinas? Por supuesto que el principio es muuuuy muy cierto excepto en posiciones de zugzwang(que felizmente casi siempre son en posiciones con poquitas piezas), pero que se le achique la profundidad provoca hartos errores diseminados en el arbolito por aquí y por allá.

No hay casi ningún descarte perfecto, normalmente se acepta nomás que hayan errores en el árbol de búsqueda, pero la mayoría son errores entre comillas, pues en el fondo son como ir a la qsearch más luego, o sea no es lo mismo que un error de evaluación. Hay que ver lo que funciona mejor en la práctica.

El factor exponencial de la cantidad total de nodos gastados cumplida cada iteración, puede quedar en un poquito más de 2.

Además de la irregularidad del árbol producto del descarte, que implica reducir la profundidad en aquellas líneas, por lo menos en continuaciones que parecen forzadas, como recapturas, o al escapar de un jaque, y una que otras pocas situaciones conviene extender la búsqueda un poquito, aunque es el humano quien sí sabe extender en muuuchas situaciones cuando huele algo, y sí lo hace bien... pero suele pasar que el árbol de combinaciones explote demasiado en tamaño si se extienden algunas cosas sin extremo cuidado asi que tampoco es cosa de que se te ocurra algo para extender y ya, porque si "no había nada allí" el extender habrá sido casi sólo una pérdida desagradable de tiempo.

Te recomiendo hacer una full evaluación en todos o casi todos los nodos, es la info más útil que hay. Bueno al menos ese es mi estilo tú hace lo que quieras :P


Específicas


pseudocódigo para la búsqueda


El siguiente es código que muestra más o menos un esqueleto para un bien puro Minimax(sin alpha ni beta.)
La Qsearch se ejecuta en la función MinimaxQ, que es casi igual a esta función excepto que la variable mejor se inicializa con Evaluar(p) para aplicar el concepto conversado anteriormente...
No se detecta jaquemate ni se ordenan las jugadas ni nada de nada, pero la idea está.
Antes de pasar al siguiente paso tienes que entender esto muy bien!!

int Minimax (posicion p, int turno, int profundidad)
{
     int mejor, mejorjugada, puntaje;

     if (profundidad <= 0)   { return MinimaxQ (p, turno, profundidad); }

     if (turno==turnoDelPrograma) { mejor=-INFINITO; }
     else                         { mejor=+INFINITO; }

     int cuantos=generarMovimientos (p, turno);

     for (int i = 1; i <= cuantos; ++i)
     {
          p.efectuarMovimientoIésimo(...);
          puntaje=Minimax (p, 1-turno, profundidad-1);
          p.deshacerMovimientoIésimo(...);

          if (turno==turnoDelPrograma && puntaje > mejor)
          {
               mejor=puntaje;  mejorjugada=i;
          }
          else if (turno!=turnoDelPrograma && puntaje < mejor)
          {
               mejor=puntaje;  mejorjugada=i;
          }
     }

     return mejor;
}

Ahora podemos meter alpha-beta, fíjate bien!!
La variable mejor aquí es omitible ya que siempre es igual a alpha o beta. Sigue aquí sólo por razones didácticas...
Debes notar que en AlphabetaQ, el puntaje que es devuelto por Evaluar(p) recibe el mismo trato que un puntaje de cualquier movimiento, pudiendo incluso provocar un corte inmediato o achicar la ventana.
Tienes que entender que, en cada nodo, si se termina retornando el alpha original, eso significa que el valor exacto del nodo es a lo más alpha, y si se termina retornando el beta, eso significa que el valor del nodo es mínimo beta. Sólo si el resultado está entre alpha y beta el resultado es exacto.

int Alphabeta (posicion p, int turno, int profundidad, int alpha, int beta)
{
     int mejor, mejorjugada, puntaje;

     if (profundidad <= 0)   { return AlphabetaQ (p, turno, profundidad, alpha, beta); }

     if (turno==turnoDelPrograma) { mejor=alpha; }
     else                         { mejor=beta; }

     int cuantos=generarMovimientos(p,turno);

     for (int i = 1; i <= cuantos; ++i)
     {
          p.efectuarMovimientoIésimo(...);
          puntaje=Alphabeta(p, 1-turno, profundidad-1, alpha, beta);
          p.deshacerMovimientoIésimo(...);

          if (turno==turnoDelPrograma && puntaje > alpha)   // (alpha es = a mejor)
          {
               if (puntaje >= beta) { return beta; }        // corte inmediato!

               alpha = puntaje;                             // achica ventana por lo menos

               mejor = puntaje;   mejorjugada = i;
          }
          else if (turno!=turnoDelPrograma && puntaje < beta) // (beta es = a mejor)
          {
               if (puntaje <= alpha) { return alpha; }        // corte inmediato!

               beta = puntaje;                                // achica ventana por lo menos

               mejor = puntaje;   mejorjugada = i;
          }
     }

     return mejor;
}

Bueno ahora viene un truco para abreviar esto, no es fácil darse cuenta que funciona...
El siguiente código es equivalente al anterior!
Todo debe de estar desde el punto de vista de quien tiene el turno en cada nodo. Así que el puntaje de Evaluar(p) debe de ser bueno o malo dependiendo si la posicion es buena o mala para el bando que tiene el turno en el nodo donde se evalúa. Es decir, si nuestra evaluación la medíamos antes como (bonuses del bando del programa) - (bonuses del bando del contrario) ahora tiene que ser siempre (bonuses del bando que tiene el turno) - (bonuses del bando que no tiene el turno).

int Alphabeta (posicion p, int turno, int profundidad, int alpha, int beta)
{
     int mejor,mejorjugada,puntaje;

     if (profundidad <= 0)   { return AlphabetaQ (p, turno, profundidad, alpha, beta); }

     mejor=alpha;   // !!

     int cuantos=generarMovimientos(p,turno);

     for (int i = 1; i <= cuantos; ++i)
     {
          p.efectuarMovimientoIésimo(...);
          puntaje=-Alphabeta(p, 1-turno, profundidad-1, -beta, -alpha);  // !!
          p.deshacerMovimientoIésimo(...);

          if (puntaje > alpha)                           // (alpha es = a mejor)
          {
               if (puntaje >= beta) { return beta; }     // corte inmediato!

               alpha = puntaje;                          // achica ventana por lo menos

               mejor = puntaje;   mejorjugada = i;
          }
     }

     return mejor;
}

Al menos esa es la forma más conocida de escribirlo, pero dificulta mucho la vista estar dando vuelta el alpha y el beta y más encima cambiarles el signo cada vez que llames a la función. Así que si eres un ser humano igual que yo te aconsejo de sobremanera dejarlo así:

int Alphabeta (posicion p, int turno, int profundidad, int beta, int alpha)   // aquí nomás ponerlos dados vuelta
{

alpha = -alpha;  // cambio de signo
beta  = -beta;   // cambio de signo
...
...
          puntaje=-Alphabeta(p, 1-turno, profundidad-1, alpha, beta);     // ahora se pueden poner igual que antes!!
...
...
}




Jugando con las ventanitas



Ya sabrás que mientras más cercanos uno a otro sean alpha y beta (o sea, mientras más pequeña sea la ventana (alpha,beta)) más rápida (casi siempre) será esa búsqueda, porque hay cortes más luego y más variantes no se ven.
Por tanto, si se cree probable que el resultado de una búsqueda estará cerca de un valor X, entonces en lugar de usar quizás una ventana (-inf,+inf) puede convenir usar una alrededor de X con un intervalo mucho más pequeño... lo que encaja justo en el caso cuando se comienza revisando la mejor jugada de la iteración pasada, ya que el puntaje pasado es la mejor apuesta posible. Asimismo, si se espera que una jugada sea peor que la mejor encontrada hasta el momento (con ptje X) puede convenir usar una ventanita para ella de (X, X+1) en vez de (X, beta), con la esperanza de que retorne X y ya.
Naturalmente, cada vez que se comete un error se debe hacer una rebúsqueda, la que puede ser para adivinar de nuevo el resultado en un pequeño intervalo o terminar de una vez abarcando todo el resto.
La idea de PVS ("principal variation search"...) es más o menos analizar la primera jugada con la ventanita grandecita pero todo el resto con una ventanita (ptjeactual, ptjeactual+1). Si todo anduvo perfecto, todo ese resto retornó ptjeactual, y sino, por ahí se tuvo que rebuscar alguna(s) jugada(s) con (ptjeactual, beta), actualizando cada una de esas veces claro la mejor jugada y el puntaje actual.
La idea de MTD es usar muchas ventanitas de tamaño 0 (o sea (x, x+1), de tamaño 0 porque entre x y x+1 no hay nada...), e incluso darle pasadas a la iteración sin necesariamente haber descubierto la mejor movida todavía. Por supuesto cuando en la raíz se revisa la mejor jugada y le quieres cazar su puntaje lo debes hacer de la mejor manera.
Naturalmente, no tienes que casarte 100% con ninguna alternativa.
Una cosa, cuando se achica a un intervalo más pequeño la ventana en la raíz (en vez de de inmediato usar (-inf, +inf) para la mejor movida o (x,+inf) al encontrar una nueva), a ésta se le llama "aspiration window" o ventana de aspiración. En la mayoría de los programas reduce la cantidad de nodos un poco.

Nota 1: Me puedo equivocar un poco en las definiciones exactas, pero no importa demasiado.
Nota 2: Con -inf o +inf me refiero simplemente a valores que no pueden ser rebasados.


Ordenamiento



Bueno, esta parte es bien importante, y se refiere al orden con que son probados los movimientos en cada posición en el arbolito. Es otro lado por el cual se optimiza una búsqueda alpha-beta y más vale tener una implementación decente, pues lo que se persigue es minimizar el factor de anchura.
Ya mencioné algo acerca de esto anteriormente, pero aquí hay una descripción más detallada del orden que se sigue comúnmente más o menos:

1.- Jugada recomendada en la hash (si había)
2.- Capturas que no parecen perder material.
3.- Las Killers.
4.- Otras jugadas que no capturan.
5.- Capturas que parecen perder material.

1: Es natural pensar que ésta tenga buenas posibilidades.

2 y 5: Aquí ya empezamos a ver estos polémicos movimientos...
Para ver si una captura podría perder material o no, podemos tratar de vaticinar los cambios que ocurrirán en la casilla polémica, a esto le llaman SEE ("static echange evaluator"...), función que retorna algo respecto a la esperada ganancia o pérdida al efectuar la captura. No necesariamente esta tiene que ser "completa" o "exacta" (si bien no sé hasta qué punto en ese caso se sigue llamando SEE), pero pareciera en general preferible en caso de equivocación que el puntaje sea optimista y no pesimista, sobre todo en la qsearch, que es donde te gustaría descartar de plano las jugadas que parezca pierden material.
También puedes pretender ver algo de interdependencia, o sea quizás una pieza defensora está clavada o sobrecargada, etc. pero nunca alcanzarás una perfección, así que todo esto es relativo y tienes que ver lo que te funcione mejor en la práctica.
Muy bien entonces, puedes ordenar las capturas según algún puntaje que les de el SEE, pero de todas formas también hay un orden bien popular que funciona bastante bien y es MVV/LVA ("Most Valuable Victim / Less Valuable Attacker") y define un orden así: primero capturas a Dama, luego a Torre, luego a Pieza Menor y luego a Peón... y dentro de un mismo grupo seguir un orden inverso para la pieza capturante, es decir, PxD,CxD/AxD,TxD,DxD,PxT,CxT/AxT,TxT,DxT, etc.
Como MVV/LVA es fácil de implementar, puedes comenzar por él, si quieres primero para relegar algunas capturas del ítem 2 al 5 puedes ir haciendo unos simples chequeos para saber si la captura era a una pieza de menor calibre y defendida, o algo así.

3: Las Killers se refieren a esas jugadas que han provocado corte o han sido la mejor jugada en otros nodos. Se suele restringir a las nocapturas. La típica implementación es una pequeñita lista para cada nivel del árbol. Entre los detalles que se deciden está cuantos killers se guardan/usan por nivel (típicamente coinciden, y 2-3 es común), en qué lugar de la lista poner un nuevo killer y cómo recompensar un killer si funcionó bien de nuevo. Obviamente los killers se usan si están entre las jugadas posibles...
"History Heuristic" es otra cuestión parecida a esta, pero toma en cuenta todas las jugadas posibles habidas y por haber (se puede implementar con un arreglo de 2 o 3 dimensiones) No pertenece a ningún nivel específico pero sí importa el nivel cuando es afectada esta matriz por una jugada para hacerse sumar puntaje. La definición exacta no la sé pero relativamente hablando por killer se entiende algo que es más bien específico al nivel del árbol, y por esto otro algo que lo es mucho menos.

4: Bueno en este resto puedes hacer lo que te funcione mejor... todo lo que puedas hasta que ya no te valga la pena, que suele ser no mucho(ver Notas)

Una cosa, respecto al ordenamiento en la raiz, puedes hacer la iteración 1 todita con (-inf,+inf), y así tendrás únicamente puntajes exactos, y luego ordenas esos movimientos según esos puntajes y ahí tienes un orden decente para seguir con ése en la iteración sgte. Naturalmente, cada vez que se encuentra una nueva mejor movida ésta se pondría a la cabeza.

Nota 1: El ordenamiento consume tiempo. Además puedes deducir que existe una relatividad en cuanto a su efectividad respecto al tiempo que consumen otras áreas del programa, la cercanía a la raíz, la velocidad del hardware y el tiempo que le des al programa para calcular.


Tablas de hashing para un programa de ajedrez



Una tabla de hashing es un "arreglo asociativo", donde, así en forma abstracta, incluso una instancia de un objeto puede usarse para accesarlo(o sea no necesariamente un entero.)
Ahora bien, lo que se hace en realidad es convertir ese objeto en un número y ese numerito es el que se usa como índice para el arreglo común y corriente.
Está claro que esta forma de trabajar es mucho más eficiente que recorrer todo el arreglo en busca de el registro correspondiente, sobre todo si el arreglo es muy grande!
Hay que notar que cuando se encuentra el lugar correspondiente en ese arreglo, no está garantizado de forma gratuita que los datos que habían allí corresponden a nuestro objeto, así que lo que se hace es guardar entre ellos siempre también una clave(otro numerito), y esa clave es la que se supone identifica a nuestro objeto. Para una persona una clave excelente sería su rut, o su número de seguro social o lo que corresponda en su país.

Bueno lo que vamos a convertir aqui en índices y claves, son posiciones de ajedrez, porque vamos a relacionar posiciones de ajedrez con los datos que queramos dejarles guardados...

Cómo obtener un índice y una clave para una posición de ajedrez?, bueno una manera muy recomendada es con el algoritmo de Zobrist, utilizando instrucciones XOR(o exclusivo):

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

con numeritos un poquito más grandes, es bit a bit, por ejemplo:

001101 ^

100101 =

101000


Bueno cómo se usa:
Primeramente al iniciar el programa, para cada pieza en cada casilla posible y para ambos bandos se define un numerito único.
Por ejemplo para torre blanca en la casilla a1 definimos que será por ejemplo 12331 (11000000101011 en binario), y así con (6 tipos de piezas)X(64 casillas)X(2 bandos) terminando con 768 numeritos aquí, que los podemos guardar en un arreglo de tres dimensiones.
Pero además necesitamos otros 4 numeritos que dicen acerca de los derechos a enrocar (las blancas tienen derecho a enrocar corto? las blancas tienen derecho a enrocar largo? y lo mismo para las negras. )
También otros 16 más por si se puede comer al paso en alguna casilla(uno por c/u de esas casillas, claro.)
Y por último uno que dice a quien le toca jugar.

Entonces una clave o un índice de una posición, uno la va armando haciendo XORes con todos los numeritos que corresponden. Por ejemplo para la posicion inicial seria:

num.de torre blanca en a1^num.de caballo blanco en b1^ num.de alfil blanco en c1^...etc.

El resultado de todo eso daria la clave(o el índice.)
No te parece esto un poco caótico? está bien que sea caótico.

Nota que en la creación del índice y la clave lo más sano es utilizar dos sets de números totalmente distintos. Imagínate si usaran el mismo set de números. La clave sería inútil!!

Bueno, una gracia que tiene este método es que estos valores son actualizables. Fíjate que:

A^B^C^...^B = A^C^...


Se entiende?
O sea si metes dos veces a xorear el mismo numerito es como si no se hubiera introducido nunca. Me crees?

Por eso aplicar un XOR de un numerito es como hacer aparecer una pieza o hacer desaparecerla.
O sea supongamos que tenemos la clave de la posición inicial y queremos actualizarla porque se ha jugado e4. Tenemos que hacer:

clave anterior^
num.de peon blanco en e2^
num.de peon blanco en e4^
num. de cambio de turno.

y eso da la clave nueva.

O sea se hizo desaparecer el peon de e2(porque ya estaba allí en la clave por decirlo así, y al repetirlo se fue...) y luego se hizo aparecer otro peón blanco en e4. Posteriormente se cambió el turno y eso hay que hacerlo notar con el numerito del cambio de turno, al que puedes considerar como un "le toca a las negras" y lo haces aparecer, luego desaparecer, y aparecer, etc., asumiendo que por defecto le toca a las blancas :)

Naturalmente cuando el movimiento es una captura hay que xorear también el numerito correspondiente a la pieza capturada "para que se vaya"...

Además hay que tener cuidado con los derechos de enroque y las casillas al paso.

Y eso sería pues. De esta forma, siempre vamos a tener una variable "indice" y una variable "clave" para cada posición.
Si quieres definir un tamaño para la hash, tienes que hacer que el índice no se pase de los límites, para lo cual puedes utilizar en vez del índice tal cual, el valor de indice % CAPACIDAD_HASH.
Si te das cuenta, si X e Y son ambos menores que un 2 a la n, entonces X^Y también ya que no van a aparecer más unos a la izquierda. Por eso una opción es definir la capacidad de la tabla de hashing como un 2 a la n, con el fin de ahorrarse el operador %, pero con la desventaja de limitar los tamaños posibles de la tabla de hashing, y además se puede optimizar un poquito más formando el índice no separadamente sino sacando unos cuantos bits de la clave, aunque esto tiene otra pequeña desventaja que es la de ir achicando la clave efectiva cada vez que se quiere usar una hash más y más grande (a más grande tabla de hashing, más bits se sacan para el índice.)

Bueno... suponiendo que estamos en un nodo dentro de la búsqueda en un programa y vamos a ver si ya estaba la posición guardada en la hash, lo que hacemos es ver que hay en mihash[indice].

Si mihash[indice].clave ("la clave que hay allí guardada") es igual a la clave actual entonces algunos datos de esta posición los habíamos guardado antes aquí mismo, y podemos usarlos si sirven de algo porque corresponde.
Si mihash[indice].clave NO es igual a la clave actual es porque en ese lugar se habían guardado datos correspondientes a otra posición. En tal caso no se pueden usar así como así obviamente y tenemos que decidir si vamos a remplazarlos o no con los de esta posición etc.

Te preguntarás porque se usa ^ en vez de algo más "común y corriente" como sumas y restas (+ para aparecer y - para desaparecer) bueno además de la simplicidad de usar sólo una operación, que además es más rápida, supongo que se recomienda también porque minimiza más la cantidad de colisiones.
Una colisión es que dos objetos distintos(en este caso posiciones) pero con la misma clave, se te topen(o sea tengan el mismo índice más encima), lo que bien puede ocurrir pero se debe hacer que tenga una probabilidad lo suficientemente baja como para no preocuparse mucho.
Mientras más bits se usen para generar la clave es más baja la probabilidad de colisiones. Yo estoy usando 46 bits exclusivamente para la clave. La probabilidad de colisiones es baja, pero existe, y esas raras veces que ocurre puede que lastime algo, o puede que no...

Si se va a sacar el índice de la clave misma, parece necesario usar por lo menos un entero de 64 bits, ya que suponiendo por ejemplo 16 bytes por entrada y 256 MB para la hash, se necesitarían ya 24 bits para el índice( (256*1024*1024)/16 = 2 elevado a 24), y la clave efectiva sería de 64-24 = 40 bits y mientras más mb para la hash peor...


Bueno, lo mínimo que se guarda y recupera en una hash para la búsqueda suele ser:

o.-Jugada recomendada
o.-Profundidad
o.-Valor del nodo
o.-Tipo de valor

La jugada recomendada es la que fue la mejor la última ocasión para esta posición o al menos causó un corte anteriormente. Es la primera jugada en probar esta ocasión.
El valor del nodo se refiere al valor resultante del nodo la vez pasada.
El tipo de valor señala si ese valor es exacto, o sólo un límite inferior o superior.
La profundidad señala cuanto le faltaba al nodo en medias jugadas para la qsearch. Naturalmente sólo si ésta es mayor o igual que la profundidad actual entonces sólo en ese caso se usa el valor guardado, si es que de algo sirve (en el mejor de los casos se retorna de inmediato, o por lo menos se agranda alpha o achica beta.)

Algunos usan dos tablas de hashing para la búsqueda, pero con distinto criterio de reemplazamiento.
Algunos usan una tabla de hashing especial sólo para la qsearch.

Por supuesto, también puedes tener una hash para tu evaluación.
La evaluación es donde la mayoría de los programas gasta lejos la mayor parte de su tiempo así que usar ésta puede acelerar un poco el programa, dependiendo de cuan heavy sea la evaluación. También está la posibilidad de usar una hash para [parte de] la evaluación exclusiva de peones, ya que las estructuras de peones cambian mucho menos que el resto de las piezas durante la búsqueda, e incluso una diminuta hash para peones hace una diferencia (por supuesto ahí se crea un índice y clave usando sólo los peones.)

Está casi demás decir que las claves de las posiciones son las que se usan para detectar empates por repetición.


Oooooookey eso es todo aqui, si sabes programar, te atrae el tema, y tienes tiempo y AÚN NO has hecho un juego de ajedrez, podrías considerar perder el tiempo de esta manera...
En la página de links hay unas direcciones que puedes revisar sobre esto, pero en todo caso no necesitas acumular mucha sabiduría ni nada para comenzar. (Será este un consejo poco profesional?).

Buena suerte...