Guess the Word — Minimax con Eliminación de Candidatos

Planteamiento del Problema

El problema Guess the Word de LeetCode consiste en adivinar una palabra secreta de 6 letras seleccionada de una lista de palabras. Contamos con una API Master que nos permite hacer intentos:

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

El reto es encontrar la palabra secreta con la menor cantidad de intentos posible en el peor de los casos.

Estrategia de Resolución

Para resolverlo aplicamos un enfoque Minimax combinado con eliminación progresiva de candidatos:

1. Comenzamos con todas las palabras como candidatos posibles
2. En cada turno, evaluamos cada candidato como posible siguiente intento
3. Para cada intento candidato, calculamos cuántas palabras quedarían en cada grupo posible (0 a 6 coincidencias)
4. Elegimos la palabra que minimiza el peor caso (el grupo más grande posible)
5. Preguntamos al Master cuántas coincidencias obtuvo nuestro intento
6. Filtramos los candidatos: solo conservamos las palabras consistentes con la respuesta

Implementación en JavaScript

/**
 * // This is the Master's API interface.
 * // You should not implement it or speculate about its implementation.
 * function Master() {
 *
 *     * @param {string} word
 *     * @return {integer} Number of matching characters in the correct positions.
 *     this.guess = function(word) {
 *         ...
 *     };
 * };
 */

/**
 * @param {string[]} words
 * @param {Master} master
 * @return {void}
 */
var findSecretWord = function(words, master) {

    // Returns how many characters match in the same position.
    function match(a, b) {
        let cnt = 0;
        for (let i = 0; i < 6; i++) {
            if (a[i] === b[i]) cnt++;
        }
        return cnt;
    }

    // Initially every word is a possible secret.
    let candidates = words;

    // Continue until the secret is found or no candidates remain.
    while (candidates.length > 0) {

        let bestWord = candidates[0];
        let bestScore = Infinity;

        // Evaluate every candidate as the next guess.
        for (const guess of candidates) {

            // groups[i] = number of words that would produce i matches
            // if "guess" were compared against them.
            const groups = new Array(7).fill(0);

            for (const word of candidates) {
                groups[match(guess, word)]++;
            }

            // Worst-case number of remaining candidates after this guess.
            const worst = Math.max(...groups);

            // Minimax:
            // Choose the guess that minimizes the largest possible group,
            // guaranteeing the best worst-case reduction.
            if (worst < bestScore) {
                bestScore = worst;
                bestWord = guess;
            }
        }

        // Ask the Master how many positions match.
        const res = master.guess(bestWord);

        // All six characters match -> secret found.
        if (res === 6) return;

        // Keep only words that are consistent with the Master's response.
        // Any word producing a different match count cannot be the secret.
        const next = [];

        for (const word of candidates) {
            if (match(word, bestWord) === res) {
                next.push(word);
            }
        }

        // Search only within the remaining valid candidates.
        candidates = next;
    }
};

Explicación del Código

Función de Coincidencia (match)

function match(a, b) {
    let cnt = 0;
    for (let i = 0; i < 6; i++) {
        if (a[i] === b[i]) cnt++;
    }
    return cnt;
}

Compara dos palabras carácter por carácter y devuelve cuántas posiciones tienen el mismo carácter. Dado que todas las palabras tienen exactamente 6 letras, iteramos de 0 a 5.

Selección Minimax

La clave del algoritmo está en esta sección:

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;
    }
}

Para cada posible intento (guess), simulamos cómo se agruparían los candidatos según cuántas coincidencias tendrían con guess. El grupo más grande representa el peor caso: si el Master devuelve ese valor, nos quedaremos con más candidatos.

El algoritmo elige la palabra que minimiza ese peor caso posible. Esto garantiza el progreso más rápido posible en el escenario más desfavorable.

Poda de Candidatos

const next = [];
for (const word of candidates) {
    if (match(word, bestWord) === res) {
        next.push(word);
    }
}
candidates = next;

Después de cada intento, descartamos todas las palabras que no son consistentes con la respuesta del Master. Si el Master indicó que nuestra palabra bestWord tiene res coincidencias con la secreta, entonces cualquier candidato que tenga un número diferente de coincidencias con bestWord no puede ser la palabra secreta.

Este filtrado reduce drásticamente el espacio de búsqueda en cada iteración.

Conclusión

Este problema demuestra cómo aplicar Minimax —un concepto clásico de teoría de juegos— a un problema de búsqueda y eliminación:

1. Evaluación exhaustiva: analizamos cada posible movimiento
2. Modelado de escenarios: agrupamos resultados posibles
3. Optimización del peor caso: elegimos la opción más segura
4. Poda progresiva: eliminamos candidatos inconsistentes

El algoritmo garantiza encontrar la palabra secreta en un número limitado de intentos (generalmente 6-10 en el peor caso), siendo una solución óptima para este tipo de problemas de búsqueda adversaria.

La técnica es aplicable a muchos otros problemas donde se necesita descubrir información oculta mediante consultas con retroalimentación parcial: juegos de adivinanza, diagnóstico de sistemas, búsqueda binaria multidimensional, entre otros.