Búsqueda por ganancia de información

Tema: Interactivos · Catálogo de recetas · temario: Syllabus IOAI

📍 Dónde se aprende: módulo 22 de la Ruta de Aprendizaje.

Qué hace

Elige, entre las preguntas disponibles, la que más reduce la incertidumbre sobre el candidato oculto.

Cuándo usarla

En los interactivos de adivinanza con presupuesto de turnos: The Analytical Language of John Wilkins (2026) daba 15 preguntas para ~1.400 animales, y Potato 30 turnos para 1.602 palabras.

Implementación

Necesita: solo la biblioteca estándar.

import math
 
 
def entropia(pesos):
    """Entropía en bits de una distribución dada por pesos no normalizados."""
    total = sum(pesos)
    if total <= 0:
        return 0.0
    return -sum((p / total) * math.log2(p / total) for p in pesos if p > 0)
 
 
def mejor_pregunta(candidatos, preguntas, responde):
    """Elige la pregunta que más reduce la incertidumbre.
 
    `responde(pregunta, candidato)` devuelve la respuesta que daría ese
    candidato. La mejor pregunta es la que parte el conjunto de candidatos lo
    más parejo posible: con respuestas sí/no, la que deja ~mitad y mitad
    elimina un bit entero por turno, y 1.400 candidatos caben en 11 preguntas.
 
    Es la estrategia de The Analytical Language of John Wilkins (IOAI 2026),
    que daba 15 preguntas para ~1.400 animales.
    """
    mejor, mejor_esperada = None, None
    for q in preguntas:
        grupos = {}
        for c in candidatos:
            grupos.setdefault(responde(q, c), []).append(c)
        if len(grupos) < 2:
            continue                      # no distingue nada: no sirve
        n = len(candidatos)
        esperada = sum((len(g) / n) * entropia([1] * len(g))
                       for g in grupos.values())
        if mejor_esperada is None or esperada < mejor_esperada:
            mejor, mejor_esperada = q, esperada
    return mejor
 
 
def filtrar(candidatos, pregunta, respuesta, responde):
    """Se queda solo con los candidatos compatibles con lo que contestó el juez."""
    return [c for c in candidatos if responde(pregunta, c) == respuesta]

⚠️ Notas

La aritmética que hay que tener en la cabeza: una pregunta sí/no que parte el conjunto por la mitad elimina un bit por turno. 1.400 candidatos son ~10.5 bits, así que 15 preguntas alcanzan de sobra si cada una parte bien. Preguntar «¿es un ornitorrinco?» gasta un turno para eliminar uno.

Esta versión evalúa todas las preguntas contra todos los candidatos: es O(|preguntas| × |candidatos|) por turno. Si eso no cabe en el límite de tiempo, muestrea un subconjunto de preguntas — pero mide antes de optimizar.

Cuando el juez puede equivocarse o usa una representación distinta de la tuya (como en Potato), filtrar duro deja el conjunto vacío. Ahí hay que pasar de filtrar a puntuar: mantener pesos por candidato en vez de eliminarlos.

🔗 Relacionadas


Verificada

Este código se ejecuta en cada publicación, contra una referencia obviamente correcta, en herramientas/pruebas/basicas.py. Si se rompe, el sitio no se actualiza.

Las otras puertas del vault: Ruta de Aprendizaje · Referencia · IOAI