Estrategia de la mente maestra

19

Solo pude encontrar desafíos de código de golf para Mastermind, así que aquí hay una versión de desafío de código que me hubiera gustado asumir.

Koyama y Lai encontraron una estrategia óptima para el juego Mastermind normal, MM (4,6) en 1993, con un número promedio de conjeturas = 5625/1296 ~ 4.34. MM (5,8) aún no se ha resuelto, pero se estima que tiene un número promedio de conjeturas ~ 5.5.

Su tarea es crear una estrategia MM (5,8), es decir, para 5 agujeros y 8 colores, que cubra todas las pow(8,5) = 32768posibles soluciones distintas. Obviamente, no tiene que ser óptimo. Tienes dos opciones:

  1. Publique un programa determinista que genere la estrategia. El programa debe ser compilable / ejecutable en Windows 7, Mac OS X o Linux sin ningún software adicional no libre.
  2. Publique su estrategia (junto con su nombre de StackExchange) en algún lugar de Internet y publique la URL aquí.

En ambos casos, indique el puntaje (ver abajo) en el encabezado de la respuesta.

La estrategia debe codificarse de acuerdo con la siguiente gramática:

strategy : guessing-strategy | known-solution-strategy
guessing-strategy : '{' guess ':' branches '}'
known-solution-strategy : guess
guess : color color color color color
color : 'A'..'H'
branches : '{' branch (',' branch)* '}'
branch : reply ':' strategy
reply : number-of-blacks number-of-whites
number-of-blacks : number-of-key-pegs
number-of-whites : number-of-key-pegs
number-of-key-pegs : '0'..'5'

El algoritmo utilizado para decidir el número de clavijas de teclas en blanco y negro se describe en http://en.wikipedia.org/wiki/Mastermind_(board_game)

Tenga en cuenta que la respuesta "50" (es decir, la suposición correcta) está implícita y no forma parte de la gramática.

Puntuación: N = la suma del número de conjeturas para cada una de las 32768 rutas / soluciones. La estrategia con la N más baja gana. Primer desempate: el número máximo más bajo de conjeturas. Segundo tie-break: la primera respuesta publicada. La competencia termina el 1 de agosto de 2014 a las 0:00 GMT .


Un ejemplo de una estrategia para MM (2,3) con puntaje = 21:

{AB:{10:{AC:{10:AA,01:CB,00:BB}},02:BA,01:{BC:{01:CA}},00:CC}}

Usando esta estrategia, los 9 juegos posibles serán así:

  • AB 20
  • AB 10, AC 20
  • AB 10, AC 10, AA 20
  • AB 10, AC 01, CB 20
  • AB 10, AC 00, BB 20
  • AB 02, BA 20
  • AB 01, BC 20
  • AB 01, BC 01, CA 20
  • AB 00, CC 20

Pronto publicaré un verificador de estrategia MM (5,8) basado en Java para su conveniencia.

MrBackend
fuente
Me está costando entender cómo se aplica la estrategia de ejemplo de MM (2,3). ¿Puedes publicar un juego de muestra que explique la estrategia?
@tolos agregué los 9 :)
MrBackend
¡Sería genial si tu verificador también pudiera generar una puntuación!
No es que Charles
@Charles lo hará!
MrBackend
2
¿Estaría dispuesto a cambiar su gramática para permitir la misma respuesta a múltiples combinaciones de clavijas clave? Al igual que {AB:{10|01:BB}}? Tengo una respuesta, pero es bastante ingenua y, debido a la estructura de árbol de la gramática, no se escala bien en absoluto (4 agujeros, 3 colores, genera una estrategia de 147 MB, que podría reducir significativamente combinando partes de el árbol).
Martin Ender

Respuestas:

6

Java

Mi algoritmo para puntajes MM (5,8) con 177902 178006 182798 182697 con una profundidad máxima de 8 9 y solo necesita unos segundos (en mi computadora lenta).

Un resultado de ejemplo de una estrategia para MM (2,3) con puntaje = 21 encontrado por este algoritmo se ve así:

{BC:{00:AA,01:AB:{01:CA},02:CB,10:AC:{00:BB,01:BA,10:CC}}}

No hay nada emocionante con mi algoritmo. No invento. Simplemente seguí las recetas encontradas en la red y las comprimí en este código Java. La única optimización que hice fue tratar de optimizar las líneas de código (de alguna manera). Dice así:

  1. Cree el conjunto inicial S0 de todos los códigos posibles para que sea el conjunto actual S.
  2. Codebreaker encuentra una buena (codiciosa) suposición para S. Cada suposición conduce a una partición P de S, donde cada subconjunto S 'recoge todos los códigos (de S) que tienen la misma respuesta en la suposición. Una buena suposición tiene una buena partición, como la que da más información para la suposición.
  3. Adivine bien y es P. Para cada S 'no vacío en P, aplique el descifrador recursivo (paso 2).

@ MrBackend: Supongo que escribir un verificador es difícil. ;-)

import java.util.TreeMap;
import java.util.Vector;

public class MM {
    Vector<String> codeset = new Vector<String>();
    String guess;
    TreeMap<Integer, MM> strategy = new TreeMap<Integer, MM>();

    public String toString() {
        String list="";
        for (Integer reply: strategy.keySet()) {
            if (strategy.get(reply)!=null) list+=(list.length()>0?",":"")+(reply<10?"0":"")+reply+":"+strategy.get(reply);
        }
        if (list.length()>0) return guess+":{"+list+"}"; else return guess;
    }

    MM() { }

    MM(int h, int c) {
        for (int i = 0; i < Math.pow(c, h); i++) {
            String code = "";
            for (int j = 0, p=i; j < h; j++) {
                code+="ABCDEFGH".charAt(p%c);
                p/=c;
            }
            codeset.add(code);
        }
    }

    int replyAccordingToDonaldKnuth(String secret, String guess) {
        int black=0;
        int totalHitsBlackAndWhite=0;
        for (char n = 'A'; n <= 'H'; n++) {
            int a=0, b=0;
            for (int i = 0; i < secret.length(); i++) {
                if (secret.charAt(i)==n) a++;
                if ( guess.charAt(i)==n) b++;
            }
            totalHitsBlackAndWhite+=Math.min(a, b);
        }
        for (int i = 0; i < secret.length(); i++) {
            if (secret.charAt(i) == guess.charAt(i)) black++;
        }
        return 10 * black + (totalHitsBlackAndWhite-black);
    }

    int reply(String secret, String guess) {
        return replyAccordingToDonaldKnuth(secret, guess);
    }

    MM codebreaker(Vector<String> permuts) {
        int fitness=0;
        MM protostrategy=null;
        for (int greedy = 0; greedy < Math.min(permuts.size(), 200); greedy++) {
            MM tmp=partition(permuts, permuts.get(greedy));
            int value=tmp.strategy.size();
            if (fitness<=value) {
                fitness=value;
                protostrategy=tmp;
                protostrategy.guess=permuts.get(greedy);
            }
        }
        if (protostrategy!=null) {
            for (Integer reply: protostrategy.strategy.keySet()) {
                protostrategy.strategy.put(reply, codebreaker(protostrategy.strategy.get(reply).codeset));
            }
        }
        return protostrategy;
    }

    MM partition(Vector<String> permuts, String code) {
        MM protostrategy=new MM();
        for (int c = 0; c < permuts.size(); c++) {
            int reply=reply(permuts.get(c), code);
            if (!protostrategy.strategy.containsKey(reply)) protostrategy.strategy.put(reply, new MM());
            if (permuts.get(c)!=code) protostrategy.strategy.get(reply).codeset.add(permuts.get(c));
        }
        return protostrategy;
    }

    public static void main(String[] args) {
        MM mm = new MM(5,8);
        System.out.println("{"+mm.codebreaker(mm.codeset)+"}");
    }
}

Algunas observaciones:

  1. No es necesario verificar la consistencia porque los conjuntos S y sus particiones se construyen de manera (auto) consistente.
  2. Elegir una buena suposición de S0 (en lugar de S) tiene sentido. Pero no sigo este enfoque en el código actual.
  3. Mi búsqueda codiciosa se reduce artificialmente a 200 intentos.
  4. Lo sé, "dar la mayoría de la información para la conjetura" no es muy preciso. La idea simple es elegir la partición con la mayor cantidad de subconjuntos.
  5. El resultado depende en gran medida de cómo calcule la respuesta (..). Finalmente adapté la expresión de Donald Knuth.

La estrategia para MM(5,8) se puede encontrar aquí . GitHub tiene algunos problemas para mostrar líneas tan largas, así que haga clic en el botón Sin formato .

Bob Genom
fuente
hola cómo imprimir bastante el texto github para que los resultados se puedan convertir en una guía de búsqueda ... desde el primer punto de partida 'HHCAA' ... y el siguiente paso dependiendo de la respuesta ... y hasta el siguiente y así sucesivamente. El formato de texto sin formato actual no es más fácil para el escaneo manual ... la técnica que estoy buscando es cómo analizar los corchetes anidados y obtener un diseño de tabla agradable que sea más fácil de seguir hasta el final, similar a la lista con viñetas en la pregunta para MM (2,3). Gracias. Espero que puedas entender lo que busco. (prefiero python para analizar str)
ihightower
2

Rubí

EDITAR: se agregó algo de lógica para excluir conjeturas imposibles. Por lo tanto, las estrategias ahora cumplen con el formato dado y son mucho más manejables.

Así que aquí hay un intento de poner esto en marcha. Es bastante ingenuo (y no muy legible; ayuda leer la rama if / elsif / else de abajo hacia arriba).

Holes, Colors = ARGV.map &:to_i

ColorChars = ('A'..'H').to_a

def is_possible(guess, blacks, result)
    blacks == guess.chars.zip(result.chars).count {|chars| chars[0] == chars[1]}
end

def print_strategy(known_colors, remaining_permutations, next_color)
    char = ColorChars[next_color]
    if remaining_permutations
        guess = remaining_permutations[0]
        print guess
        if remaining_permutations.length > 1
            print ':{'
            (Holes-1).times do |i|
                new_permutations = (remaining_permutations - [guess]).select { |perm| is_possible(guess, i, perm) }
                next if new_permutations.empty?
                print "#{i}#{Holes-i}:"                
                print '{' if new_permutations.length > 1
                print_strategy(known_colors, new_permutations, next_color)
                print '}' if new_permutations.length > 1
                print ',' if i < Holes-2
            end
            print '}'
        end
    elsif known_colors.length == Holes
        print_strategy(known_colors, known_colors.chars.permutation.map(&:join).uniq, next_color)
    elsif next_color == Colors-1
        print_strategy(known_colors+char*(Holes - known_colors.length), remaining_permutations, next_color+1)
    else
        print char*Holes, ':{'

        (Holes - known_colors.length + 1).times do |i|
            break if i == Holes
            print "#{i}0:"
            print '{' if next_color < Colors-2 || i > 0 || known_colors.length > 0
            print_strategy(
                known_colors+char*i,
                remaining_permutations,
                next_color+1
            )
            print '}' if next_color < Colors-2 || i > 0 || known_colors.length > 0
            print ',' if i < (Holes - known_colors.length) && i < Holes-1
        end
        print '}'
    end
end

print '{'
print_strategy('', nil, 0)
puts '}'

En primer lugar, trato 5 de cada color: AAAAA, BBBBB, etc. A partir de esa cifra que qué colores se utilizan realmente en el patrón. Y luego simplemente intento todas las permutaciones de los colores dados, omitiendo los que ya han sido descartados por las clavijas negras.

Aquí está el MM(2,3) estrategia:

{AA:{00:{BB:{00:CC,10:{BC:{02:CB}}}},10:{BB:{00:{AC:{02:CA}},10:{AB:{02:BA}}}}}}

La estrategia para MM(5,8)toma 376 KB y se puede encontrar aquí . GitHub tiene algunos problemas para mostrar líneas tan largas, así que haga clic en el botón Sin formato .

Ahora, si obtengo un verificador, también puedo decirte cuál es mi puntaje real. :)

Martin Ender
fuente
Sentirse mal por el verificador aún no publicado, pero está en camino ... Hay algo mal con su (primera) estrategia MM (2,3), por ejemplo si la solución es AB: Guess = AA; respuesta = 10; adivinar = BB; respuesta = 10, para lo cual no hay estrategia. Analizaré su sugerencia de agrupar respuestas, pero no debería ser necesario para buenas estrategias, ya que el conjunto de posibles soluciones son disjuntas para diferentes respuestas.
MrBackend
@ MrBackend Buena captura, me salté un caso allí. Debería arreglarse ahora. En cuanto a la gramática, por supuesto, no es necesario para buenas estrategias, pero pensé que podría estar dispuesto a bajar un poco el listón. ;) Si las personas pueden enviar entradas más simples (como la mía), es posible que tenga un poco más de suerte al obtener presentaciones interesantes que mejoren gradualmente, en lugar de tener que incluir todas las combinatorias desde el principio.
Martin Ender
Aquí está el trato: terminaré el verificador actual y lo publicaré (como una aplicación web, es demasiado grande para pegar aquí). Desafortunadamente, puede ser demasiado estricto, ya que considera que las respuestas imposibles son un error. Después, lo adaptaré para admitir múltiples respuestas y solo emitir advertencias para respuestas imposibles. Dicho esto, su estrategia 1.3G MM (4,4) debe contener muchas respuestas imposibles y / o conjeturas no reductoras, ya que el tamaño estimado de una estrategia MM (5,8) decente es un puñado de megas.
MrBackend
@ MrBackend Por supuesto, mis estrategias contienen un montón de respuestas imposibles. Eso es lo que quise decir con "No estoy haciendo la combinatoria". ;) Si es demasiado complicado para ti apoyar eso y agrupar respuestas, no te preocupes, entonces analizaré cómo omitir conjeturas imposibles.
Martin Ender
@ MrBackend Buenas noticias, lo arreglé. :) Espero que la estrategia sea válida ahora. Avíseme si todavía hay algún problema con él.
Martin Ender