El motor como ya hemos dicho es la parte "pensante" de un programa de ajedrez. Como ya hemos mencionado hay más de 300 motores disponibles, la mayoría de ellos son compatibles con el protocolo xboard y disponibles de forma gratuita en internet.
Puedes visitar la página de Leo Dijksman para tener información de los diferentes motores xboard http://wbec-ridderkerk.nl/index.html (inglés). En dicha página encontrarás no solamente información de muchos motores (incluido DanaSah) sino también el lugar donde descargarlos. En la página de Arena, http://www.playwitharena.com/ también puedes encontrar un apartado con los links donde descargar una gran cantidad de motores.
Y puedes visitar la página de Alex Schmidt si quieres tener información de los diferentes motores UCI http://www.uciengines.de/index.html (inglés). Verás que aunque dicha página es especialista en motores UCI, no se olvidadan de los motores xboard.
Vamos a ver ahora lo que hace un motor de ajedrez, un motor de ajedrez está construido principalmente de 3 partes:
- El generador de movimientos.
- La función de evaluación.
- La función de búsqueda.
El generador de movimientos.
Si queremos que el programa juegue, el programa deberá ser capaz de generar una lista con todos los posibles movimientos candidatos a ser jugados, más adelante ya veremos como luego sabe cual es el mejor movimiento que tiene que jugar, pero de momento tenemos que tener claro que inicialmente el programa generará dicha lista.
El programa debe por supuesto ser capaz de realizar movimientos de enroque, al paso y promociones. Y por supuesto no debe hacer movimientos ilegales, por ejemplo quedarse en jaque tras realizar el movimiento, aunque por motivos de rapidez se puede a la hora de generar los movimientos incluir los ilegales y más tarde eliminarlos.
Para generar la lista, tenemos que pensar en el tablero y por ejemplo a acada casilla asociamos un valor entre 0 y 63, empezando desde A1 hasta H8. Para hacer mover un peón sumaremos 8 a la casilla inicial si el peon avanza una casilla o 16 si avanza dos casillas, si come en diagonal habrá que suma 7 ó 9, esto desde el punto de vista del color blanco, para el negro tendríamos que restar. Para el resto de piezas haríamos lo mismo. Tenemos que tener en cuenta las dimensiones del tablero y que las piezas al hacer movimientos no se pueden salir del tablero, para ello debemos imponer unas condiciones, para hacer más fácil este trabajo algunos han inventado a la hora de generar los movimientos unos tablero de tamaño 12x10, 12x12, 16x8, aunque luego los vuelven a convertir al normal de 8x8, si al hacer el movimiento la pieza sale fuera del tablero 8x8 normal es que el movimiento es ilegal.
La función de evaluación
Es la que nos permite valorar cada posición, a la hora de evaluar una posición como mínimo tenemos que controlar el material o piezas de cada bando, al igual que lo hace un humano, a cada pieza le podemos dar un valor, por ejemplo 1 para el peón, 3 para caballo y alfíl, 5 para la torre y 9 para la dama. La evaluación será la suma de las piezas de un jugador menos las del otro. Solamente con esto y si el programa juega a una profundidad elevada, el programa parecerá que está vivo y jugará, ganando a muchos humanos y algún que otro programa.
Pero a parte del material es importante que el programa, al igual que un buen jugador de ajedrez, examinen otra serie de cosas, algo que sabe un buen aficionado es que es interesante ocupar el centro con los peones y piezas como caballos y alfiles, desarrollar sus piezas lo antes posible, enrocar, tener la máxima movilidad posible y espacio, que el rey esté seguro tras su enroque, tratar de tener la pareja de alfiles, llevar las torres a las columnas abiertas o semiabiertas, cuidar las estructura de peones y tratar de conseguir peones pasados para promocionar, etc. Cuántas más cosas le enseñemos al programa, mejor jugará, pero tan importante como que el programa tenga una buena evaluación, es que la búsqueda a traves del árbol sea lo más efectiva posible y que el programa no se pierda en las infinitas combinaciones posibles. Hay quien hace que el programa evalue mucho haciendo su programa lento en las búsquedas y por tanto no muy efectivo ya que es posible que no llegué a un nivel adecuado de profundidad y se pierda una combinación, hay quien busca muy rápido evaluando la posición muy poco, con lo cual el programa será un monstruo táctico pero fallará en su juego posicional y sobre todo en los finales, hay que tratar pues de buscar un equilibrio.
La función de búsqueda
La función de búsqueda es por tanto la encargada de buscar el mejor movimiento a realizar, echará mano de las funciones de generación de movimientos, para generar todos los posibles movimientos legales para una determinada posición y también echará mano de la función de evaluación para evaluar cada una de esas posiciones.
La función de búsqueda actuará como un humano, pensará en un determinado movimiento a realizar y comprobará la respuesta del contricante, para esta respuesta el programa pensará ahora en la siguiente jugada y después en la contrarespuesta, etc. Esta forma de pensar tanto para el programa o como el jugador, en el mundo del ajedrez se le conoce como árbol de variantes.
Al comienzo de una partida de ajedrez, el jugador blanco tiene 20 posibilidades (es decir puede mover cada uno de sus 8 peones una casilla o dos, eso hace 16 posibilidades y puede mover sus dos caballos a otras dos casillas, eso hacen otras 4 y en total 20), a cada una de esas posibilidades el negro puede responder con otras 20 posibilidades y entonces el blanco a esa respuesta podrá responder con otra serie de posibilidades. El número de posibilidades en este caso depende de los movimientos que se vayan realizando, pero se estima que en el medio juego el número de movimientos posibles para una posición es de 35.
Si conseguimos hacer un programa que vaya examinando todas las posiciones del árbol, podríamos recorrer el árbol por el camino que condujera a la victoria, en programas como 3 ó 4 en raya, donde el número de posibilidades no es muy elevado, si el programa comienza, siempre ganará, en el ajedrez el número de combinaciones es muy elevado y es imposible saber en el movimiento inicial cual es el camino hacia la victoria, al menos de momento. Al igual que existen los finales perfectos de 5 piezas (incluso ya algunos de 6), se podrían generar los finales perfectos de 32 piezas, pero de momento es imposible no hay ordenador capaz de generar tal número de combinaciones posibles y almacenarlas en los discos duros actuales y el tiempo en realizarlas sería casi infinito, ¿algún día?
En programación a la función que nos permite buscar los movimientos por todo el árbol y examinarlos se llaman mínimax. Siempre considera el mejor movimiento, se trate de buscar para las blancas o negras.
Un programa o un humano que solo piensen en la respuesta inmediata del contrario serán muy débiles, para jugar bien hay que pensar no solo en la respuesta inmediata sino que hay que ser capaces de ver como quedaría la posición unos movimientos más adelante. Un jugador que quiera ser considerado al menos como un buen aficionado deberá pensar al menos 3 movimientos suyos futuros, considerando los del contrario serían 6, a esto en el ajedrez se llama profundidad 6 (ply = 6).
Con un ply de 6 un ajedrecista tendrá un ELO (fuerza) de aproximadamente 1400 puntos. Si queremos hacer un programa con un ELO de al menos 2000 puntos la máquina deberá pensar al menos en ply =10 (se estima unos 150 puntos lo que se consiguen por cada ply extra, esto yo creo que se cumple para profundidades bajas, pero en profundidades altas posiblemente no, además hay que tener en cuenta las extensiones). Kasparov perdió su famoso encuentro contra Deep Blue, pero en una de las partidas que ganó a la máquina la máquina se sabe que había estado pensando en ply = 14 (hoy en día muchos programas alcanzan esa profundidad en tiempo de torneo), si echamos cuentas eso significa que la máquina estaría en una fuerza ELO 2600, lo cual creo que es bastante real, Kasparov tiene un ELO de unos 2800 puntos. Ya puestos se podría decir que Kasparov podría pensar más que en ply 15, pero Kasparov es humano y comete errores, la máquina no, la máquina siempre juega tal como se le ha enseñado.
Si hemos dicho que en cada posición hay unas 35 posibilidades, si queremos pensar en ply = 6, resulta que 35x35x35x35x35x35 = 1.838.265.625 combinaciones !!!!!!!!!!!!
Por supuesto ningún humano es capaz de analizar tal número de combinaciones, los humanos desechan la mayoría de posibilidades en una posición por intuición, para que vamos a comer con una dama un peón si está protegido, en principio pierdo la dama así que no voy a seguir investigando por ahí, aunque siempre hay que tener en cuenta la posibilidad de que haya sacrificios, podemos sacrificar la dama por ejemplo si un par de movimientos más tarde damos mate.
Un programa de ajedrez, ¿también desecha posibilidades o tiene que tener en cuenta todas las posibilidades y combinaciones?
Si nuestro programa mira todas las posibilidades y es capaz de analizar 50.000 posiciones por segundo necesitaríamos 1.838.265.625 / 50000 = 36765 sg, es decir aproximadamente 10 horas para llegar a ply = 6.
Afortunadamente el hardware cada día es más rápido y cualquier programa seguramente analizará más variantes. DanaSah es capaz de examinar 700.000 posiciones por segundo (la máquina Deep Blue examinaba más de 200.000.000 de posiciones por segundo, claro está con un hardware especial), Danasah llegaría pues a ply 5 (35x35x35x35x35=52521875) en poco más de un minuto, pero para llegar a ply=6 seguiría necesitando 3 cuartos de hora, así que DanaSah no puede examinar todas las posibilidades si quiere llegar a una profunidad elevada, debe pensar un poco como un humano.
Pero si DanaSah no examina todas las posibilidades, ¿eso significa que puede cometer errores al no considerar todas las posibiliades?
NO
Felizmente alguién se dió cuenta que no hace falta que un programa analice todas las posibilidades, al igual que los humanos desechan posibilidades, el programa poda el árbol de variantes si ve que no va a obtener una evaluación superior y lo hace de una forma matemática parecida a como lo haría un humano sin cometer errores, aproximadamente para una posición en la que hay 35 posibilidades la máquina con una función llamada alphabeta cuttof consigue quedarse con raiz cuadrada de 35 posibilidades a examinar, es decir que la máquina fundamentalmente se centrará en 6 posibilidades, lo cual hace que la máquina pueda jugar el doble de profundidad en el mismo tiempo. Así que teorícamente según lo dicho anteriormente DanaSah en poco más de un minuto podrá llegar al menos a profundidad (ply) 10.
¿Y como hacen los programas buenos como Shredder, Fritz, etc, para llegar a profundidad superiores a 16 en menos de 3 minutos?
Buena pregunta, para ello hay muchas técnicas que permiten a los programas accelerar al máximo la búsqueda y además estos programas emplean técnicas muy elaboradas para podar el árbol de variantes al máximo. Con todas estás tecnicas los programas punteros consiguen rebajar el número de movimientos a examinar normalmente de 6 a 3, aunque en este caso ya se corren riesgos de perderse algo.
Si quieres más detalles sobre como se acceleran las búsquedas visita el apartado programación de esta página web.
credito a la web:
No comments:
Post a Comment