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)»