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 ordenador 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)”