El primer juego de ordenador de la historia

El Ajedrecista de Leonardo Torres Quevedo, presentado en 1912, está considerado como el primer juego de ordenador de la historia. En esta entrada se puede jugar contra un programa que implementa el mismo algoritmo usado en El Ajedrecista.

El autor
Leonardo Torres Quevedo por Eulogia Merle MUNCYT
Leonardo Torres Quevedo por Eulogia Merle MUNCYT

Leonardo Torres Quevedo (1852-1936) fue un ingeniero e inventor español nacido en Santa Cruz de Iguña (Cantabria).
Dedicó la mayor parte de su vida a diseñar y elaborar una amplia variedad de inventos geniales. Por citar alguno de los que han tenido más repercusión mediática:
El telekino: un mando a distancia que utilizaba ondas electromagnéticas. El 7 de noviembre de 1905, en el puerto de Bilbao, con la asistencia del rey Alfonso XIII y una gran multitud, demostró su funcionamiento gobernando un bote desde la orilla.
Transbordadores: El Spanish Aerocar es un transbordador que cruza las cataratas del Niagara. Inaugurado en 1916, sigue en funcionamiento en la actualidad.
Ordenadores Analógicos. En estos dispositivos, un proceso matemático se transforma en un proceso físico representando los números mediante magnitudes físicas como tensiones o intensidades eléctricas, rotaciones en un eje, etc. Torres Quevedo construyó varias máquinas de este tipo, por ejemplo una que resolvía ecuaciones de segundo grado con coeficientes complejos.

En su artículo Ensayos de automática. Su definición . Extensión teórica de sus aplicaciones publicado en 1914 en la Revista de la Real Academia de Ciencias, presenta muchas de sus ideas sobre la realización de los autómatas. Se incluye el diseño completo de una máquina capaz de calcular a(y-z)^2 para un conjunto de valores de las variables presentes, lo que implica dispositivos electromecánicos para almacenar dígitos decimales, realizar operaciones aritméticas utilizando tablas o comparar el valor de dos cantidades. Incluso aparece por primera vez la idea de una aritmética usando coma flotante. (Ver el artículo de Randell, Brian de 1992 basado en una conferencia dada en el MIT)

El primer juego de ordenador
El Ajedrecista (2º modelo)
El Ajedrecista (2º modelo)

En 1912 Torres Quevedo presentó un autómata que jugaba al ajedrez: El Ajedrecista. Considerado el primer juego de ordenador de la historia, ganaba de forma inexorable un final de rey y torre contra rey. El autómata movía la torre y el rey blancos y el humano el rey negro.
En esta primera versión el tablero estaba dispuesto en posición vertical y el autómata detectaba los movimientos del rey blanco por unos contactos que las piezas tenían en su base. Las piezas blancas se movían usando brazos articulados. En 1920 y con la colaboración de su hijo Gonzalo diseño una versión mejorada. El tablero estaba ahora en posición horizontal, y las piezas se movían mediante electro-imanes ocultos bajo el mismo. Si detectaba que el jugador hacía trampas se encendía una luz roja y a la tercera dejaba de jugar. En un gramófono, que se ve en la fotografía en la parte superior izquierda, se oía “Jaque al rey” en cada jaque de la torre y “Mate” al final de la partida.

La posición inicial de las piezas blancas era rey en a8 y torre en h7. El jugador humano podía situar el rey negro en cualquier fila inferior a la séptima, con la única condición de que no se pusiese en jaque. Continuar leyendo “El primer juego de ordenador de la historia”

El ajedrez de Ray y Smull

Un poco de historia
Asimovs_v05n03_1981_03_16
Número del 16 de marzo de 1981

Asimov’s Science Fiction, inicialmente denominada Isaac Asimov’s Science Fiction Magazine, es una revista estadounidense de Ciencia Ficción que se publica desde 1977.
Martin Gardner fue columnista de la revista entre 1977 y 1986. En cada columna planteaba un rompecabezas con la forma de una pequeña historia con un ambiente o personajes relacionados con la Ciencia Ficción. En la solución se resolvía el problema y se planteaba uno relacionado con el anterior que se resolvía en la segunda solución. Esta mecánica a veces se repetía hasta la cuarta solución.

En el número publicado el 16 de marzo de 1981 la columna se titulaba Chess by Ray and Smull. Dos matemáticos Ray y Smull que viajan a bordo de la nave espacial Bagel  juegan con el ordenador de abordo, VOZ, a un juego en que VOZ sitúa, aleatoriamente, las 5 figuras negras sobre un tablero de ajedrez. En la pantalla, VOZ muestra el tablero con estrellas en las 5 casillas que contienen las piezas. Ray y Smull intentan deducir la posición de las 5 piezas y para ello van preguntando a VOZ el número de piezas que amenazan ciertas casillas del tablero.

Los problemas originales

Continuar leyendo “El ajedrez de Ray y Smull

Muertos y Heridos: Un juego de lógica (y II)

En esta entrada se describen algunas posibles estrategias paras que un programa de ordenador haga de descifrador en el juego de Muertos y Heridos.

En la entrada anterior de la que esta es una continuación se describe el juego y se analizan dos estrategias para descifradores humanos.

Estrategias para Ordenadores

El juego  Muertos y Heridos especialmente en su variante conocida como Mastermind ha dado lugar a mucha bibliografía en la que  se describen estrategias para programas informáticos que sean eficientes, tanto en el número, máximo y promedio, de jugadas empleado para deducir la clave, como en los recursos informáticos, capacidad de cálculo o memoria, necesarios.

Andy Pepperdine[1] en The game of MOO describe 11 estrategias para la variante conocida como MOO ,  e indica para cada una de ellas el número promedio y máximo de preguntas necesarias para deducir la clave. MOO o Bulls and Cows es como Muertos y Heridos pero sin repetición de dígitos.
A continuación se analizan  dos estrategias intuitivas y muy fáciles de implementar en especial la primera.

Estrategia Simple

Propuesta por Ehud Shapiro[2] en 1983, el único criterio para elegir una nueva pregunta es que ésta se encuentre entre las claves posibles en ese momento. Inicialmente, antes de hacer la primera pregunta, hay 10000 posibles claves, los números del 0000 al 9999.  Como cada pregunta que se hace reduce ese número, es inevitable que en algún momento se acierte la clave.
Continuar leyendo “Muertos y Heridos: Un juego de lógica (y II)”

Muertos y Heridos: un juego de lógica (I)

Descripción del juego

Muertos y Heridos es un juego de lógica para el que solo se necesita lápiz y papel. Se juega entre dos jugadores, el cifrador que piensa un número de 4 cifras del 0 al 9999, la clave, y el descifrador que trata de deducirlo.
En cada intento el descifrador pregunta un número de cuatro cifras. El cifrador responde con un número de dos cifras. La primera, los muertos, representa el número de dígitos de la pregunta que coinciden con alguno de la clave y además se encuentran en la misma posición. La segunda, los heridos, representa el número de dígitos de la pregunta que coinciden con alguno de la clave pero que no están en la misma posición. Se muestran a continuación dos ejemplos. La clave es la última pregunta, la que tiene como respuesta 40.

Fig. 1 Partida Ejemplo
Fig. 1 Partida Ejemplo
Fig. 2 Partida Ejemplo
Fig. 2 Partida Ejemplo

Si en una pregunta hay un dígito que se repite y en la clave ese dígito aparece una sola vez o al revés, muerto tiene prioridad sobre herido. Un ejemplo de estas situaciones se da en las partidas anteriores en la preguntas nº 6.

Antes de continuar , sino conoces el juego, conviene familiarizarse con él.  He escrito un pequeño script en Python en el que está implementada una versión sencilla del mismo.
Continuar leyendo “Muertos y Heridos: un juego de lógica (I)”

Ajedrez: el Análisis Retrospectivo

El análisis retrospectivo en ajedrez tiene como objetivo obtener información sobre el desarrollo pasado de una partida utilizando normalmente como única información la posición que refleja el tablero en un determinado instante. Evidentemente es muy diferente del análisis que hay que hacer en una partida de ajedrez convencional donde conocemos el pasado y lo que tratamos de analizar es el futuro. El análisis retrospectivo trata de dar respuesta a preguntas del tipo: ¿puede el rey blanco enrocarse?, ¿ha promocionado algún peón? ¿qué ha jugado el negro en la última jugada. En el caso extremo, en las llamadas partidas justificativas, el objetivo es reconstruir, conocido el número de jugadas, el desarrollo completo de la partida desde la posición inicial, teniendo como única información la posición final.

A continuación se ve con un ejemplo el tipo de razonamiento que hay que realizar en el análisis retrospectivo. El objetivo del problema que se plantea, cuyo autor es Geza Schweig, es una partida justificativa en 4.0 jugadas:
¿Qué 4 jugadas de las blancas y otras tantas de las negras han dado lugar a la posición que refleja el tablero?.
Todas las jugadas han seguido estrictamente las reglas del juego aunque no necesariamente se ha jugado bien en el sentido convencional.

Partida Justificativa. 4.0 .Geza Schweig. Tukon, 1938
Partida Justificativa. 4.0 .Geza Schweig. Tukon, 1938

Se ilustra el razonamiento con un conjunto de preguntas.
Continuar leyendo “Ajedrez: el Análisis Retrospectivo”