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