Mastermind

Mastermind es una versión comercial de un antiguo juego llamado ``toros y vacas'' (bulls and cows), en el cual participan dos jugadores, el que establece la combinación que debe descubrir el otro. El primero piensa una combinación secreta de piedras de colores que está oculta a los ojos del segundo jugador. Éste debe hacer un intento de adivinar la combinación generando una que será contestada por el primer jugador poniendo una marca negra (``toro'') por cada piedrecita de color que se encuentra en la posición correcta y con el color correcto (en la combinación del segundo jugador), y una marca blanca (``vaca'') por cada piedrecita de color que se encuentra en la combinación a adivinar, pero en una posición diferente [#!MereloGECCO99!#].

El segundo jugador tiene un número máximo de intentos (hacer combinaciones) para adivinar la combinación que ideó el primer jugador.

En general, el problema de Mastermind se formula como la búsqueda de un código oculto, utilizando la ayuda que ofrece una ``caja negra''. En particular, el código y los intentos de adivinarlo se obtienen a partir de un alfabeto con cardinalidad $N$; cada intento (combinación) y el código tienen longitud $L$. Así pues, el espacio de búsqueda es $N^L$.

El ``tablero de juego'' típico tiene dos versiones de diferente dificultad: $N=6 , L=4$ y $N=8 , L=5$; de forma que en el primer caso, el espacio de búsqueda es 1296 y en el segundo 32768.

Cada información de ayuda por parte del jugador que establece el código oculto en la forma de marcas negras o blancas restringe el espacio, eliminando varias de las posibles combinaciones que aún no se habían tenido en cuenta. De cualquier forma, puesto que el espacio de búsqueda es multidimensional, no es fácil determinar el sub-espacio que se ha descartado con la última información de ayuda.

Para resolver este otro problema se ha modificado el programa desarrollado en la sección implementando la función de evaluación de forma que actúe como se describe anteriormente.

En las tablas y podemos ver los resultados obtenidos al resolver este problema utilizando las versiones secuencial y paralelas (con las diferentes estrategias de migración) del programa desarrollado.

Tabla: Resultados (media y desviación estándard) para el problema del Mastermind utilizando la versión secuencial del programa desarrollado.

p=100 / g=100	Tiempo
65.5	0.21 $\pm$ 0.03
p=400 / g=100	Tiempo
95	0.46 $\pm$ 0.03
p=800 / g=100	Tiempo
100	1.15 $\pm$ 0.02
p=1600 / g=100	Tiempo
100	5.59 $\pm$ 0.05

Tabla: Resultados (media y desviación estándard) para el problema del Mastermind utilizando la versión paralela (con diferentes estrategias de migración) del programa desarrollado.

Migración	4 proc.	Tiempo	8 proc.	Tiempo	16 proc.	Tiempo
Simple	73.4 $\pm$ 2.6	0.33 $\pm$ 0.04	76.4 $\pm$ 2.2	0.46 $\pm$ 0.04	78.3 $\pm$ 2.5	0.74 $\pm$ 0.01
Estrella	97.1 $\pm$ 4.3	0.37 $\pm$ 0.05	99 $\pm$ 2	0.6 $\pm$ 0.1	100	1.03 $\pm$ 0.04
Broadcast	98 $\pm$ 3	0.42 $\pm$ 0.02	100	0.61 $\pm$ 0.05	100	1.3 $\pm$ 0.2
Anillo	94.1 $\pm$ 4.1	0.35 $\pm$ 0.04	99 $\pm$ 2	0.47 $\pm$ 0.06	100	0.8 $\pm$ 0.1