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”