Guess the Word — Minimax con Eliminación de Candidatos

Tesis del Problema

Guess the Word es un problema de búsqueda adversaria con retroalimentación parcial: se debe descubrir una palabra secreta de 6 letras elegida de una lista, usando una API Master que responde solo el número de posiciones correctas.

• master.guess(word) — devuelve un entero entre 0 y 6 con cuántas letras coinciden en la posición correcta con la palabra secreta.

El objetivo es encontrar la palabra secreta con la menor cantidad de intentos posible en el peor caso. La estructura del problema —consulta → respuesta parcial → filtrado del espacio de búsqueda— es la firma de un algoritmo Minimax: cada intento es una decisión bajo incertidumbre, y la métrica a optimizar es el tamaño del peor grupo residual de candidatos.

Desglose del Algoritmo

1. Inicialización: todas las palabras de la lista son candidatos posibles.
2. Evaluación por turno: cada candidato se evalúa como posible siguiente intento.
3. Agrupación: para cada intento candidato se calcula cuántas palabras quedarían en cada grupo posible de coincidencias (0 a 6).
4. Selección Minimax: se elige la palabra que minimiza el peor caso (el grupo más grande posible).
5. Consulta: se pregunta al Master cuántas coincidencias obtuvo el intento elegido.
6. Poda: se conservan solo los candidatos consistentes con la respuesta.

Implementación

/**
 * // This is the Master's API interface.
 * // You should not implement it or speculate about its implementation.
 * function Master() {
 *     this.guess = function(word) { ... } // 0..6 posiciones correctas
 * };
 */

var findSecretWord = function(words, master) {
    // Número de caracteres que coinciden en la misma posición.
    function match(a, b) {
        let cnt = 0;
        for (let i = 0; i < 6; i++) {
            if (a[i] === b[i]) cnt++;
        }
        return cnt;
    }

    let candidates = words;

    while (candidates.length > 0) {
        let bestWord = candidates[0];
        let bestScore = Infinity;

        // Minimax: minimizar el mayor grupo residual.
        for (const guess of candidates) {
            const groups = new Array(7).fill(0);
            for (const word of candidates) {
                groups[match(guess, word)]++;
            }
            const worst = Math.max(...groups);
            if (worst < bestScore) {
                bestScore = worst;
                bestWord = guess;
            }
        }

        const res = master.guess(bestWord);

        // Las seis posiciones coinciden -> secreto encontrado.
        if (res === 6) return;

        // Poda: descartar todo candidato inconsistente con la respuesta.
        const next = [];
        for (const word of candidates) {
            if (match(word, bestWord) === res) {
                next.push(word);
            }
        }
        candidates = next;
    }
};

Trade-offs y Detalles de Diseño

• Coste cuadrático por turno: evaluar cada candidato contra todos los demás es O(n²) por iteración. En la práctica la poda reduce n drásticamente tras cada consulta, haciendo el coste aceptable para las listas del problema.
• Elección de bestWord inicial: al tomar candidates[0] como semilla se garantiza que el primer intento también pasa por la evaluación Minimax completa, no un heurístico arbitrario.
• Criterio de parada: res === 6 corta el bucle; si la lista se agota sin encontrarla, el bucle termina sin más intentos.
• Naturaleza adversarial: el enfoque es pesimista por diseño — se optimiza el peor escenario, no el esperado. Esa es exactamente la garantía que necesita un problema donde el Master puede responder el grupo que más convenga a la dificultad.

Takeaways

1. Evaluación exhaustiva: cada movimiento posible se modela como un conjunto de escenarios discretos (los 7 grupos de coincidencias).
2. Optimización del peor caso: elegir la opción que deja el grupo residual más pequeño es la garantía de progreso garantizado.
3. Poda progresiva: la retroalimentación parcial se usa como test de consistencia para reducir el espacio de búsqueda en cada iteración.
4. Aplicabilidad: la técnica es genérica para problemas de descubrimiento con consultas de retroalimentación parcial — juegos de adivinanza, diagnóstico de sistemas, búsqueda multidimensional, sistemas de detección de fallas.

El algoritmo encuentra la palabra secreta en un número limitado de intentos (típicamente 6–10 en el peor caso), lo que lo convierte en la solución óptima para búsqueda adversaria con feedback parcial.