Usuario:Karshan/Trabajando en

De Wikipedia, la enciclopedia libre

En el siglo XVIII empezó a difundirse la idea de crear una computadora capaz de jugar al ajedrez. En el año 1769, un jugador de ajedrez autómata llamado El Turco^[1] se hizo famoso antes de que se descubriera que era un engaño. Después de aquel suceso, el tema del ajedrez mecánico no se volvió a mencionar y cayó en el olvido, hasta la aparición de la computadora en la década de los 50. Desde entonces, los fanáticos del ajedrez y de la ingeniería informática han construido máquinas y programas que juegan al ajedrez.

Actualmente, las computadoras de ajedrez están disponibles por un precio insignificante, y hay numerosos programas (muchos de software libre, como GNU Chess, Amy, o Crafty) que pueden jugar al ajedrez en cualquier ordenador personal y derrotar a jugadores profesionales bajo condiciones de torneo, mientras que los mejores programas comerciales de ajedrez, como Shredder o Fritz, han vencido a muchos jugadores de calibre y varios campeones del mundo en tiempos de control muy cortos y partidas relámpago.

Tabla de contenidos 1 Origen 2 Estrategia contra fuerza bruta 3 Computadoras contra humanos 4 Tablas de finales 5 Referencias 6 Notas

[editar] Origen

Existen varias causas que motivaron la existencia del ajedrez computarizado, como el entretenimiento propio (pudiendo permitir que los jugadores practiquen y se diviertan cuando no hay ningún oponente disponible), también como herramienta o soporte de análisis, para competiciones entre computadoras de ajedrez, y como investigación o abastecimiento del conocimiento humano. Los dos primeros objetivos han sido saciados satisfactoriamente, siendo todo un logro, sobre todo si se vuelve la vista atrás, cuando los primeros intentos de programar una computadora capaz de desafiar a los grandes jugadores de ajedrez datan de hace solamente menos de cincuenta años. Podríamos decir que el ajedrez no es un gran problema para la computación contemporánea.

Sin embargo, y a pesar de la sorpresa de muchos, el ajedrez nos ha enseñado muy poco en lo referente a la construcción de máquinas que proporcionen inteligencia humana, o hacer cualquier otra cosa que no sea jugar prodigiosamente al ajedrez. Por esta razón, el ajedrez computarizado, así como también otros muchos juegos, como el Scrabble, no tienen un gran interés académico para los expertos de la inteligencia artificial, siendo éste reemplazado por juegos más intuitivos, como el Go. El funcionamiento de los programas de ajedrez consiste, esencialmente, en explorar un número muy elevado de posibles futuros movimientos y aplicarles una función de evalución al resultado, mientras que las computadoras de Go desafían a los programadores a idear nuevos enfoques y estrategias de juego.

Las tácticas basadas en la fuerza bruta son prácticamente inútiles para la mayoría de problemas que han afrontado los investigadores de la IA. El estilo de juego de un programa de ajedrez se diferencia en gran medida del estilo de juego humano, ya que la elección del movimiento a jugar es totalmente distinta. En algunos juegos de estrategia, las computadoras suelen vencer fácilmente la gran mayoría de partidas, mientras que en otros, los principiantes vencen a las máquinas sin mayor esfuerzo. En el ajedrez, el resultado de la fusión de las habilidades de los expertos, con los programas de ajedrez, es mayor que el de cualquiera de los dos a solas.

[editar] Estrategia contra fuerza bruta

El primer artículo sobre el tema fue escrito por Claude Shannon^[2], y publicado en 1950, antes de de existencia de una computadora que jugara al ajedrez, y predijo acertadamente las dos posibles principales formas de búsqueda de cualquier programa, a las que nombró de 'Tipo A', y de 'Tipo B'.

Los programas 'Tipo A', más rudimentarios, usarían una búsqueda basada en la "fuerza bruta", los cuales examinarían todas posibles posiciones de cada rama del árbol de movimientos usando el algoritmo minimax. Shannon creyó que esto sería muy poco práctico por dos razones.

En primer lugar, con aproximadamente 30 movimientos posibles en una posición muy típica de medio juego en la vida real, Shannon previó que buscando las 30 × 30 × 30 × 30 × 30 × 30 posiciones contenidas en los primeros tres movimientos (de ambos bandos, lo que son 6 plies), tardaría aproximadamente 16 minutos, siempre suponiendo que el programa evaluara un millón de posiciones por segundo (después de esta conjetura, se tardó alrededor de 40 años para conseguir esa velocidad).

En segundo lugar, se ignoraba el problema de la latencia, ya que el programa trata de evaluar la posición resultante después de todo el intercambio de piezas ocurrido durante todos esos movimientos al final de cada rama del árbol. Los programas de 'Tipo A' funcionan así, pero el inconveniente es que se incrementa enormemente el número de posiciones necesarias para el análisis, y de este modo el programa se ralentizaba todavía más.

En vez de este procedimiento tan poco productivo, Shannon sugirió que a los programas se les añadiesen una especie de inteligencia artificial que solucione estos problemas, y así en lugar de analizar todas las jugadas posibles, ya sean buenas o malas, se analizarían solo las mejores jugadas de cada posición, algo parecido a lo que hacen los jugadores humanos, surgiendo así lo que él denominaba programas de 'Tipo B'. Esto permitiría ver al programa más lejos y profundizar más en las líneas principales en un tiempo bastante razonable.

Adriaan de Groot entrevistó a varios jugadores de ajedrez de varios niveles, y su conclusión fue que tanto los grandes maestros como los principiantes calculan aproximadamente cuarenta o cincuenta posiciones antes de decidir que jugada mover. Lo que realmente diferencia a jugadores expertos de jugadores mediocres es la habilidad del reconocimiento de patrones, que se va adquiriendo con la experiencia. Esto permite analizar más profundamente las mejores líneas y no perder el tiempo con otras peores.

Una prueba de ello es que los jugadores de ajedrez recuerdan muchas de las posiciones jugadas en anteriores partidas y aprenden de la experiencia, sin embargo, las computadoras no lo tienen tan fácil.

El problema con las computadoras de 'Tipo B' es que se confían demasiado decidiendo qué movimientos son suficientemente buenos como para ser dignos de consideración en cualquier posición, siendo un problema mucho más grave que en computadoras de 'Tipo A' con un hardware de gran velocidad.

En 1973, la Universidad de Northwestern, encargada de la creación de programas de Tipo B, dejó de programarlos, pasando al bando de los programas de Tipo A. Fue la creadora de una varios de programas de ajedrez que ganaron los primeros tres torneos ACM Computer Chess Championships (1970-1972). El programa de Tipo A resultante fue "Chess 4.0", ganador del torneo ACM durante 5 años seguidos, además de inaugurar uno de los campeonatos más importantes, el World Computer Chess Championship (WCCC).

Una de las razones por las que realizaron el cambio fue porque encontraban a los programas de Tipo B poco estimulantes durante los torneos, ya que es muy difícil predecir lo que van a mover, y mucho menos el por qué. Otra razón fue que en los programas de Tipo A era mucho más fácil detectar los fallos del programa y depurarlos, y lograron hacer de él un programa lo suficientemente rápido.

En ese momento, los programas basados en la fuerza bruta triunfaron por estas razones y por el simple hecho de que parecía que jugaban mejor al ajedrez. El ajedrez no es un juego adecuado precisamente para decidir qué tipo de jugadas son malas, ineficaces, o buenas.

Además, el desarrollo y los avances tecnológicos hicieron que el sistema de fuerza bruta continuara en alza y se intensificara mucho más en los años 90. El resultado ha sido la creación de programas mucho más sólidos, con una IA táctica realmente asombrosa, programas mucho más exactos sin apenas errores, y conducidos hacia el límite de su profundidad de búsqueda. Esto ha producido resultados extraordinarios, por lo menos en lo referente al ajedrez, dejando que las computadoras hagan lo que mejor saben hacer, calcular, en vez de intentar emular la inteligencia y conocimiento humanos. En 1997, Deep Blue, una computadora de Tipo A, derrotó al Campeón del Mundo Garry Kasparov, siendo la primera vez que una computadora derrotara al campeón del mundo en tiempos de control de torneo.

Sin embargo, a finales de los años 1990, los programadores empezaron a preferir los programas de Tipo B, y empezaron a sustituir a los de Tipo A. En 1998 se puclica Rebel 10, un programa comercial de Tipo B, quien derrotó a Viswanathan Anand por 5-3, y se proclamó el segundo motor de ajedrez más fuerte del mundo aquel año. Cabe decir que de las cuatro partidas de ajedrez rápido (tiempo de control: 5 min + 5 s por jugada) que se jugaron, Rebel ganó 3 de ellas, en las dos partidas semirrápidas, quedaron 1.5-0.5 a favor de Rebel, y en la partida con tiempo de control más largo (40/2:00, 1 hora), fue Anand quien venció. De esto se puede deducir que las computadoras juegan mejor que los humanos en tiempos de control más rápidos, pero que la fuerza de los jugadores se mide con tiempos de control más largos, donde Anand demostró que los humanos siguien siendo mejores^[3] . A principios del Siglo XXI surgieron nuevos programas de ajedrez comerciales, como Deep Junior, o Fritz, quienes lograron empatar a los campeones del mundo Garry Kasparov y Vladimir Kramnik. En el 2005, Hydra, una computadora de ajedrez del Tipo B, derrotó al mejor jugador británico y séptimo mejor clasificado del mundo, Michael Adams, en un encuentro de seis partidas con un contundente resultado: 5.5 - 0.5 a favor de Hydra^[4].

[editar] Computadoras contra humanos

En 1968, el MI David Levy realizó una famosa apuesta, en la cual afirmaba que ninguna computadora de ajedrez sería capaz de derrotarle en diez años, bajo condiciones de torneo. Ganó la apuesta en 1978, venciendo por 3'5-1'5 en un match de cinco partidas a la computadora más fuerte por aquel entonces, Chess 4.7, y llevándose 1250 libras, aunque reconociendo que dentro de poco tiempo le superarían. En 1989, Levy no pudo superar a Deep Thought, derrotándole en una partida de exhibición.

Sin embargo, Deep Thought no estaba todavía a la altura de los mejores ajedrecistas del mundo, y en 1989 así lo demostró Garry Kasparov en dos ocasiones, hasta que por fin, en 1996, la computadora Deep Blue de IBM logró que Kasparov perdiera su primera partida contra una computadora en tiempos de control de torneo, es más, era la primera vez que una computadora derrotaba a un campeón del mundo con ritmo de juego lento. Sin embargo, después Kasparov consiguió vencer tres y empatar dos de las cinco últimas partidas, logrando la victoria sobre la computadora por 4-2 ^[5].

En mayo de 1997, una versión mejorada de Deep Blue derrotó a Kasparov en un encuentro de 6 partidas por 3'5-2'5 ^[6], originando un gran debate sobre si el jugador más fuerte por aquel entonces era una máquina.

Deep Blue no volvió a jugar desde entonces. Sin embargo, se han seguido jugando partidas entre humanos y computadoras. En octubre de 2002, Vladimir Kramnik se enfrentó a Deep Fritz, en un encuentro de ocho partidas en Bahrain, el cual finalizó con empate. Kramnik ganó las partidas 2 y 3, y Fritz hizo lo propio en la 5. En la sexta partida, Kramnik, que venía de llevar ventaja al iniciarse el mediojuego, sacrificó una pieza para lograr una buena posición táctica. Este tipo de sacrificios son muy arriesgados, y ´más todavía contra las computadoras, y, en efecto, Fritz encontró una sólida defensa al ataque de Kramnik, dejándole en una mala posición. Kramnik se rindió, dando la partida por perdida. Las últimas partidas acabaron en tablas.

Hydra es una computadora de ajedrez que funciona bajo sesenta y cuatro procesadores y que es capaz de calcular 40 millones de posiciones por segundo, ha derrotado a los mejores programas de ajedrez, y es, probablemente, la computadora más fuerte que se haya creado. Ganó a Michael Adams con un contundente 5.5-0.5, el encuentro tuvo lugar en el centro de conferencias de Wembley (Londres).

Otras computadoras que se han enfrentado a humanos:

• En enero del 2003, Kasparov contra Deep Junior, en Nueva York. El encuentro acabó 3-3
• En noviembre de 2003, Kasparov se enfrentó a X3D Fritz. El encuentro acabó con empate a 2.

[editar] Tablas de finales

Las computadoras, desde sus inicios, analizaban completamente las posiciones de los finales. Las bases de datos de finales ^[7] están generadas por adelantado usando el análisis retrospectivo, empezando con posiciones donde el resultado final es conocido (por ejemplo en posiciones donde un bando ha ganado por jaque mate), y analizar qué movimientos han conducido a la combinación final de piezas. Ken Thompson, más conocido por ser uno de los creadores del sistema operativo UNIX, fue uno de los pioneros en este tema.

Durante mucho tiempo, los programas de ajedrez tuvieron graves problemas al jugar los finales, y eran muy débiles en dicho tramo de la partida, debido a la necesidad de una alta profundidad de búsqueda. Con distintos programas de alto nivel fueron incapaces de vencer en posiciones que cualquier humano de nivel intermedio sería capaz de ganar.

A veces, los resultados de los análisis de las computadoras sorprenden a las personas. En 1977, Belle, la máquina de ajedrez de Ken Thompson, usando la tabla de finales KQKR, logró empatar una posición, en teoría perdida, de Rey y Torre contra Rey y Dama, contra varios jugadores norteamericanos profesionales.

Muchos Grandes Maestros rehusaron jugar contra la computadora en los finales de dama contra torre, pero Walter Browne aceptó el desafío. En la partida se produjo un final de dama contra torre, donde la dama podía ganar en treinta movimientos, con un juego perfecto. Browne disponía de dos horas y media para jugar cincuenta movimientos. Después de cuarenta y cinco movimientos, Browne aceptó las tablas, siendo incapaz de forzar el mate o ganar la torre en los siguientes cinco movimientos. En la posición final, Browne estaba todavía a diecisiete movimientos de conseguir el jaque mate, pero no muy lejos de capturar la torre. Browne analizó el final, y jugó contra la computadora una semana más tarde. Esta vez, capturó la torre en el movimiento cincuenta, finalizando con una posición ganadora.

Los avances en las tablas de finales de Ken Thompson, produjeron que a principios de los años 80, se cambiara la regla de los cincuenta movimientos, al demostrar que ciertos finales necesitaban más de cincuenta movimientos para poder vencer, como el final de rey, torre y alfil, contra rey y torre.

Con el paso del tiempo se han ido publicando otros formatos de bases de datos de finales, incluyendo la base de datos Edward, la base de datos De Koning (publicada en 2002) y las Bases de Datos Nalimov, que es el formato más utilizado en la actualidad, soportado por la mayoría de los programas de ajedrez como Shredder y Fritz. Casi todos los finales de seis o menos de seis piezas, y varios de siete piezas, han sido analizados por completo.

Las bases de datos se crean almacenando en la memoria valores de las posiciones, y usando estos resultados para podar los finales de los árboles de búsqueda si surgieran de nuevo. Aunque el número de posibles partidas después de que un número de movimientos aumente exponencialmente con el número de jugadas, el número de las posibles posiciones con unas pocas piezas es exponencial solamente en el número de piezas - y eficazmente limitado, sin embargo algunas jugadas de los finales son analizadas. The simple expediency of remembering the value of all previously reached positions means that the limiting factor in solving end games is simply the amount of memory available in the computer. While computer memory sizes are increasing exponentially, there is no reason why end games of increasing complexity should not continue to be solved.

A computer using these databases will, upon reaching a position in them, be able to play perfectly, and immediately determine whether the position is a win, loss or draw, plus the fastest way of getting to that result. Knowledge of whether a position is a win, loss or draw is also helpful in advance since this can help the computer avoid or head towards such positions depending on the situation.

Endgame databases featured prominently in 1999, when Kasparov played an exhibition match on the Internet against the Rest of the World. A seven piece Queen and pawn endgame was reached with the World Team fighting to salvage a draw. Eugene Nalimov helped by generating the six piece ending tablebase where both sides had two Queens which was used heavily to aid analysis by both sides.

[editar] Referencias

• David Levy y Monty Newborn (1991). How Computers Play Chess. ISBN 0-7167-8121-2.
• John Nunn (2002). Secrets of Pawnless Endings. ISBN 1-901983-65-X.

[editar] Notas