4. Tree-of-Thought: Exploración de Soluciones

Descripción

Tree-of-Thought (ToT) es una técnica propuesta por Yao et al. en 2023 que lleva el razonamiento de los LLMs a un nuevo nivel de complejidad. Mientras que CoT genera una única cadena lineal de pensamientos, ToT organiza el razonamiento como un árbol: cada nodo es un "pensamiento" o estado parcial de la solución, y el árbol se explora sistemáticamente para encontrar el mejor camino hacia la respuesta.

La analogía es con cómo un ajedrecista piensa: no simplemente juega el primer movimiento que se le ocurre, sino que considera múltiples opciones, evalúa las consecuencias de cada una varios movimientos adelante, y elige la línea más prometedora.

Limitaciones que ToT Resuelve

CoT falla en problemas que requieren exploración

Considera el problema del "Juego del 24" (usar exactamente las operaciones +, -, ×, ÷ con 4 números para obtener 24):

Input: [4, 9, 10, 13]

CoT puro:
Thought: Intento 4 + 9 = 13, luego 13 + 13 = 26... no funciona.
Respuesta: No puedo encontrar la solución.  ← FALLA

ToT:
Rama A: 4 + 9 = 13 → (13 × 13 = 169... no) → PODA
Rama B: 10 - 9 = 1 → (1 × 4 = 4 → 4 × ... no) → PODA
Rama C: 13 - 9 = 4 → (4 × 4 = 16... 10 + 16 = 26... no) → PODA
Rama D: 10 + 4 = 14 → (14 - 9 = 5... 5 × 13 = 65... no) → PODA
Rama E: 9 - 4 = 5 → (5 × 13 = 65... no) → PODA
Rama F: 13 × 4 = 52 → (52 - 9 = 43... no) → PODA
Rama G: (10 - 4) × (13 - 9) = 6 × 4 = 24 ✓ → SOLUCIÓN ENCONTRADA

Arquitectura de ToT

                    [PROBLEMA]
                   /     |     \
           [Rama A]  [Rama B]  [Rama C]
            (0.3)    (0.8✓)    (0.5)
                      |  \
               [Rama B1]  [Rama B2]
                (0.9✓)     (0.4)
                   |
            [SOLUCIÓN FINAL]

Componentes clave

1. Thought generator: Genera K pensamientos candidatos desde un estado
2. State evaluator: Evalúa qué tan prometedor es cada estado (0-1 o "sure/likely/impossible")
3. Search algorithm: BFS, DFS, o Beam Search para explorar el árbol
4. Terminal check: Detecta cuándo se llegó a una solución completa

Implementación Base

from openai import OpenAI
from dataclasses import dataclass, field
from typing import Optional
import json

client = OpenAI()

@dataclass
class Nodo:
    """Representa un nodo en el árbol de pensamientos."""
    contenido: str                    # El pensamiento en este nodo
    padre: Optional['Nodo'] = None    # Nodo padre
    hijos: list['Nodo'] = field(default_factory=list)
    score: float = 0.0                # Evaluación del nodo (0-1)
    es_solucion: bool = False
    
    def ruta_completa(self) -> list[str]:
        """Obtiene la ruta desde la raíz hasta este nodo."""
        if self.padre is None:
            return [self.contenido]
        return self.padre.ruta_completa() + [self.contenido]
    
    def __repr__(self):
        return f"Nodo('{self.contenido[:40]}...', score={self.score:.2f})"


def generar_pensamientos(
    problema: str,
    contexto_actual: str,
    k: int = 3,
    temperatura: float = 0.8
) -> list[str]:
    """
    Genera K pensamientos candidatos para el siguiente paso.
    
    Args:
        problema: El problema original
        contexto_actual: Los pasos tomados hasta ahora
        k: Número de pensamientos a generar
        temperatura: Mayor temperature = más diversidad
    """
    prompt = f"""Problema: {problema}

Pasos previos tomados:
{contexto_actual if contexto_actual else "Ninguno (primer paso)"}

Genera EXACTAMENTE {k} ideas o pasos diferentes para avanzar hacia la solución.
Cada idea debe ser diferente de las demás.
Formato: una idea por línea, comenzando con número: "1.", "2.", "3."
Solo los pasos, sin explicaciones adicionales."""
    
    response = client.chat.completions.create(
        model="gpt-4o-mini",
        messages=[{"role": "user", "content": prompt}],
        temperature=temperatura,
        max_tokens=400
    )
    
    texto = response.choices[0].message.content
    lineas = [l.strip() for l in texto.split('\n') if l.strip()]
    
    # Extraer solo las líneas numeradas
    pensamientos = []
    for linea in lineas:
        if linea and (linea[0].isdigit() or linea.startswith('-')):
            # Remover numeración
            pensamiento = linea.lstrip('0123456789.-) ').strip()
            if pensamiento:
                pensamientos.append(pensamiento)
    
    return pensamientos[:k]


def evaluar_estado(
    problema: str,
    ruta: list[str],
    verificar_solucion: bool = True
) -> dict:
    """
    Evalúa qué tan prometedora es una ruta de pensamientos.
    
    Returns:
        dict con 'score' (0-1), 'es_solucion' (bool), 'razon'
    """
    ruta_str = "\n".join([f"Paso {i+1}: {paso}" for i, paso in enumerate(ruta)])
    
    prompt = f"""Problema: {problema}

Ruta de razonamiento:
{ruta_str}

Evalúa esta ruta:
1. ¿Es correcta esta solución/respuesta? (solo si parece completa)
2. Si no está completa, ¿qué tan prometedora es para llegar a la solución?

Responde en JSON:
{{
    "es_solucion": true/false,
    "score": 0.0-1.0,
    "razon": "explicación breve (máx 20 palabras)"
}}
Si es solución, score debe ser 1.0."""
    
    response = client.chat.completions.create(
        model="gpt-4o-mini",
        messages=[{"role": "user", "content": prompt}],
        temperature=0,
        max_tokens=150,
        response_format={"type": "json_object"}
    )
    
    try:
        evaluacion = json.loads(response.choices[0].message.content)
        return {
            "score": float(evaluacion.get("score", 0.5)),
            "es_solucion": bool(evaluacion.get("es_solucion", False)),
            "razon": evaluacion.get("razon", "")
        }
    except (json.JSONDecodeError, KeyError):
        return {"score": 0.5, "es_solucion": False, "razon": "Error en evaluación"}

Estrategia BFS (Breadth-First Search)

def tot_bfs(
    problema: str,
    profundidad_max: int = 3,
    amplitud: int = 3,
    beam_size: int = 2
) -> dict:
    """
    Tree-of-Thought con Breadth-First Search + Beam Search.
    
    Mantiene los beam_size mejores nodos en cada nivel.
    Esto limita la explosión combinatoria.
    
    Args:
        problema: El problema a resolver
        profundidad_max: Máxima profundidad del árbol
        amplitud: Pensamientos generados por nodo
        beam_size: Mejores nodos a mantener por nivel
    
    Returns:
        dict con 'solucion', 'ruta', 'nodos_explorados'
    """
    # Nivel inicial: explorar desde el problema directamente
    nivel_actual = [Nodo(contenido="Inicio")]
    nodos_explorados = 0
    mejor_solucion = None
    
    for profundidad in range(profundidad_max):
        nivel_siguiente = []
        
        for nodo_padre in nivel_actual:
            # Generar pensamientos desde este nodo
            contexto = "\n".join(nodo_padre.ruta_completa()[1:])  # Excluir "Inicio"
            nuevos_pensamientos = generar_pensamientos(
                problema=problema,
                contexto_actual=contexto,
                k=amplitud
            )
            
            # Evaluar cada pensamiento
            for pensamiento in nuevos_pensamientos:
                nodos_explorados += 1
                nuevo_nodo = Nodo(
                    contenido=pensamiento,
                    padre=nodo_padre
                )
                nodo_padre.hijos.append(nuevo_nodo)
                
                # Evaluar el estado
                ruta = nuevo_nodo.ruta_completa()[1:]  # Sin "Inicio"
                evaluacion = evaluar_estado(problema, ruta)
                nuevo_nodo.score = evaluacion["score"]
                nuevo_nodo.es_solucion = evaluacion["es_solucion"]
                
                if nuevo_nodo.es_solucion:
                    mejor_solucion = nuevo_nodo
                    # Continuar buscando para encontrar la MEJOR solución
                
                nivel_siguiente.append(nuevo_nodo)
        
        if mejor_solucion:
            # Encontramos solución, podemos terminar
            break
        
        # Beam Search: mantener solo los beam_size mejores
        nivel_siguiente.sort(key=lambda n: n.score, reverse=True)
        nivel_actual = nivel_siguiente[:beam_size]
        
        if not nivel_actual:
            break
    
    # Si no encontramos solución explícita, usar el mejor nodo
    if mejor_solucion is None:
        todos_nodos = []
        def recopilar_nodos(nodo):
            todos_nodos.append(nodo)
            for hijo in nodo.hijos:
                recopilar_nodos(hijo)
        for nodo in nivel_actual:
            recopilar_nodos(nodo)
        
        if todos_nodos:
            mejor_solucion = max(todos_nodos, key=lambda n: n.score)
    
    if mejor_solucion:
        ruta_final = mejor_solucion.ruta_completa()[1:]  # Sin "Inicio"
        return {
            "solucion_encontrada": mejor_solucion.es_solucion,
            "ruta": ruta_final,
            "score": mejor_solucion.score,
            "nodos_explorados": nodos_explorados,
            "profundidad": len(ruta_final)
        }
    
    return {
        "solucion_encontrada": False,
        "ruta": [],
        "score": 0.0,
        "nodos_explorados": nodos_explorados
    }

Estrategia DFS (Depth-First Search)

def tot_dfs(
    problema: str,
    profundidad_max: int = 4,
    amplitud: int = 2,
    umbral_poda: float = 0.3
) -> dict:
    """
    Tree-of-Thought con DFS y poda por score bajo.
    
    Más eficiente en memoria que BFS pero puede perderse
    en ramas largas no prometedoras.
    """
    mejor_ruta = {"ruta": [], "score": 0.0, "es_solucion": False}
    nodos_explorados = [0]  # Lista para mutable en closure
    
    def dfs_recursivo(nodo_actual: Nodo, profundidad: int):
        if profundidad >= profundidad_max:
            return
        
        contexto = "\n".join(nodo_actual.ruta_completa()[1:])
        pensamientos = generar_pensamientos(
            problema=problema,
            contexto_actual=contexto,
            k=amplitud
        )
        
        for pensamiento in pensamientos:
            nodos_explorados[0] += 1
            nuevo_nodo = Nodo(contenido=pensamiento, padre=nodo_actual)
            
            ruta = nuevo_nodo.ruta_completa()[1:]
            evaluacion = evaluar_estado(problema, ruta)
            nuevo_nodo.score = evaluacion["score"]
            nuevo_nodo.es_solucion = evaluacion["es_solucion"]
            
            # Poda: no explorar ramas poco prometedoras
            if nuevo_nodo.score < umbral_poda:
                continue
            
            if nuevo_nodo.es_solucion:
                if nuevo_nodo.score > mejor_ruta["score"]:
                    mejor_ruta.update({
                        "ruta": ruta,
                        "score": nuevo_nodo.score,
                        "es_solucion": True
                    })
                return  # Parar en la primera solución encontrada
            
            # Continuar explorando si hay promesa
            if nuevo_nodo.score > mejor_ruta["score"] - 0.1:
                mejor_ruta.update({"ruta": ruta, "score": nuevo_nodo.score})
            
            dfs_recursivo(nuevo_nodo, profundidad + 1)
    
    raiz = Nodo(contenido="Inicio")
    dfs_recursivo(raiz, 0)
    
    return {
        **mejor_ruta,
        "nodos_explorados": nodos_explorados[0]
    }

Implementación Simplificada (Práctica)

Para la mayoría de casos de uso, una versión simplificada es suficiente y mucho más eficiente en tokens:

def tot_simplificado(
    problema: str,
    breadth: int = 3,
    depth: int = 2,
    verbose: bool = True
) -> str:
    """
    ToT simplificado para uso práctico.
    
    1. Genera breadth enfoques iniciales
    2. Evalúa cuál es más prometedor
    3. Continúa con CoT desde el mejor enfoque
    """
    # Paso 1: Generar enfoques iniciales
    prompt_enfoques = f"""Problema: {problema}

Genera {breadth} enfoques DIFERENTES para resolver este problema.
Cada enfoque debe ser el PRIMER PASO clave de una estrategia distinta.
Formato: una línea por enfoque, comenzando con número."""
    
    response = client.chat.completions.create(
        model="gpt-4o-mini",
        messages=[{"role": "user", "content": prompt_enfoques}],
        temperature=0.8,
        max_tokens=300
    )
    
    lineas = [l.strip() for l in response.choices[0].message.content.split('\n') if l.strip()]
    enfoques = [l.lstrip('0123456789.-) ').strip() for l in lineas if l[:1].isdigit() or l[:1] == '-'][:breadth]
    
    if not enfoques:
        enfoques = lineas[:breadth]  # Fallback
    
    if verbose:
        print(f"Enfoques generados:")
        for i, e in enumerate(enfoques, 1):
            print(f"  {i}. {e}")
    
    # Paso 2: Evaluar cada enfoque
    scores = []
    for enfoque in enfoques:
        prompt_eval = f"""Problema: {problema}
Primer paso propuesto: {enfoque}

¿Qué tan prometedor es este enfoque para llegar a la solución correcta?
Responde SOLO con un número entre 0.0 y 1.0 (ej: 0.8)"""
        
        eval_resp = client.chat.completions.create(
            model="gpt-4o-mini",
            messages=[{"role": "user", "content": prompt_eval}],
            temperature=0,
            max_tokens=10
        )
        
        try:
            score = float(eval_resp.choices[0].message.content.strip()[:5])
            score = max(0.0, min(1.0, score))
        except ValueError:
            score = 0.5
        
        scores.append(score)
        if verbose:
            print(f"  Score de '{enfoque[:40]}...': {score:.2f}")
    
    # Paso 3: Continuar con el mejor enfoque
    if not scores:
        mejor_enfoque = enfoques[0] if enfoques else "razonamiento directo"
    else:
        idx_mejor = scores.index(max(scores))
        mejor_enfoque = enfoques[idx_mejor]
    
    if verbose:
        print(f"\nMejor enfoque seleccionado: {mejor_enfoque}")
    
    # Paso 4: Resolver usando CoT desde el mejor enfoque
    prompt_final = f"""Problema: {problema}

Empezando con este enfoque: {mejor_enfoque}

Continúa razonando paso a paso hasta llegar a la solución final.
Muestra todo tu razonamiento y concluye con "Respuesta final: [respuesta]"."""
    
    final = client.chat.completions.create(
        model="gpt-4o-mini",
        messages=[{"role": "user", "content": prompt_final}],
        temperature=0,
        max_tokens=500
    )
    
    return final.choices[0].message.content


# Ejemplo de uso:
if __name__ == "__main__":
    print("=== Tree-of-Thought: Problema Complejo ===\n")
    
    problema = """Una empresa tiene tres proyectos posibles:
    - Proyecto A: inversión $100K, retorno esperado 30%
    - Proyecto B: inversión $150K, retorno esperado 25%
    - Proyecto C: inversión $80K, retorno esperado 35%
    
    Tienen presupuesto de $200K. ¿Qué combinación maximiza el retorno total?"""
    
    solucion = tot_simplificado(problema, breadth=3, depth=2, verbose=True)
    print(f"\nSolución:\n{solucion}")

Comparación: CoT vs Self-Consistency vs ToT

Casos de Uso Ideales

Planificación de Proyectos

problema_planeacion = """
Necesito lanzar un producto de software en 3 meses con un equipo de 4 personas.
Las tareas son: desarrollo del backend, frontend, testing, deployment, marketing.
¿Cuál es la mejor estrategia de planning?
"""
solucion = tot_simplificado(problema_planeacion, breadth=4, verbose=True)

Diagnóstico de Problemas Técnicos

problema_debug = """
Una API REST devuelve código 200 pero los datos son inconsistentes.
A veces muestra datos de cache, a veces datos frescos. El problema es intermitente.
¿Cómo lo diagnosticarías y solucionarías?
"""
solucion = tot_simplificado(problema_debug, breadth=3, verbose=True)

Estrategia de Negocio

problema_negocio = """
Una startup de fintech con $500K de capital quiere crecer a 10,000 usuarios 
en 6 meses. Actualmente tienen 500 usuarios y una tasa de churn del 8% mensual.
¿Qué estrategia de growth deben seguir?
"""
solucion = tot_simplificado(problema_negocio, breadth=3, verbose=True)

Tree-of-Thought con Anthropic

import anthropic

client_anthropic = anthropic.Anthropic()

def tot_claude(problema: str, breadth: int = 3) -> str:
    """
    Tree-of-Thought simplificado usando Claude.
    Claude tiende a ser más explícito en su razonamiento.
    """
    # Generar enfoques
    message = client_anthropic.messages.create(
        model="claude-3-5-haiku-20241022",
        max_tokens=400,
        messages=[{
            "role": "user",
            "content": f"Genera {breadth} enfoques distintos para: {problema}\nUn enfoque por línea, numerados."
        }]
    )
    enfoques_raw = message.content[0].text
    enfoques = [l.lstrip('0123456789.-) ').strip() 
                for l in enfoques_raw.split('\n') 
                if l.strip() and l.strip()[0].isdigit()][:breadth]
    
    # Evaluar y seleccionar el mejor
    mejores_scores = []
    for enfoque in enfoques:
        eval_msg = client_anthropic.messages.create(
            model="claude-3-5-haiku-20241022",
            max_tokens=20,
            messages=[{
                "role": "user",
                "content": f"Problema: {problema}\nEnfoque: {enfoque}\n¿Qué tan prometedor es (0.0 a 1.0)? Solo el número."
            }]
        )
        try:
            score = float(eval_msg.content[0].text.strip()[:4])
        except ValueError:
            score = 0.5
        mejores_scores.append((score, enfoque))
    
    mejor_score, mejor_enfoque = max(mejores_scores, key=lambda x: x[0])
    
    # Resolver desde el mejor enfoque
    solucion_msg = client_anthropic.messages.create(
        model="claude-3-5-haiku-20241022",
        max_tokens=600,
        messages=[{
            "role": "user",
            "content": f"Problema: {problema}\n\nEmpezando con: {mejor_enfoque}\n\nContinúa paso a paso hasta la solución final."
        }]
    )
    
    return solucion_msg.content[0].text

Troubleshooting

Problema 1: El evaluador es inconsistente

Síntoma: El mismo pensamiento recibe scores muy diferentes en cada llamada.

Causas:

• Temperature > 0 en el evaluador
• Prompt de evaluación ambiguo

Solución:

def evaluar_con_consistencia(problema: str, ruta: list[str], n_eval: int = 3) -> float:
    """Promediar múltiples evaluaciones para mayor consistencia."""
    scores = []
    for _ in range(n_eval):
        evaluacion = evaluar_estado(problema, ruta)
        scores.append(evaluacion["score"])
    return sum(scores) / len(scores)

# En las funciones de ToT, reemplazar:
# evaluacion = evaluar_estado(problema, ruta)  # Score único
# por:
# score = evaluar_con_consistencia(problema, ruta, n_eval=3)  # Promedio de 3

Problema 2: Demasiadas llamadas API (explosión combinatoria)

Síntoma: Con breadth=4 y depth=3, necesitas hasta 4³ = 64 evaluaciones + 4² + 4 = 84 generaciones = 148+ llamadas.

Solución: Usar poda agresiva y beam search limitado:

def tot_eficiente(problema: str, presupuesto_llamadas: int = 20) -> str:
    """ToT con presupuesto fijo de llamadas API."""
    # Con presupuesto de 20 llamadas:
    # 3 enfoques iniciales = 3 llamadas generación + 3 evaluaciones = 6
    # Top 2 → 2 enfoques continuados = 2 + 2 = 4
    # 1 solución final = 1
    # Total: ~11 llamadas
    
    breadth = min(3, presupuesto_llamadas // 4)
    return tot_simplificado(problema, breadth=breadth, depth=1, verbose=False)

Problema 3: Pensamientos generados son muy similares entre sí

Síntoma: Los 3 enfoques generados son básicamente el mismo enfoque con palabras distintas.

Solución:

def generar_pensamientos_diversos(problema: str, k: int = 3) -> list[str]:
    """Fuerza diversidad usando roles diferentes."""
    roles = [
        "un ingeniero de software que piensa en términos de algoritmos y eficiencia",
        "un matemático que busca patrones y demostraciones formales",
        "un empresario que busca la solución más práctica y rápida"
    ]
    
    pensamientos = []
    for i, rol in enumerate(roles[:k]):
        prompt = f"Eres {rol}. ¿Cuál sería TU primer paso para: {problema}? Solo el primer paso, en una oración."
        resp = client.chat.completions.create(
            model="gpt-4o-mini",
            messages=[{"role": "user", "content": prompt}],
            temperature=0.7,
            max_tokens=100
        )
        pensamientos.append(resp.choices[0].message.content.strip())
    
    return pensamientos

Ejercicios

Ejercicio 1: ToT para un problema de Sudoku

Implementa una versión simplificada de ToT para resolver un Sudoku 4×4. El árbol debe:

1. Generar 3 posibles valores para la celda vacía más constrained
2. Evaluar cuál viola menos reglas
3. Continuar desde el más prometedor

def tot_sudoku_4x4(grid: list[list[int]]) -> list[list[int]]:
    """
    Resuelve un Sudoku 4x4 usando ToT.
    0 representa celda vacía.
    """
    grid_str = "\n".join([" ".join(map(str, row)) for row in grid])
    
    # Encontrar la celda más constrained
    prompt_analisis = f"""Sudoku 4x4 (0=vacío):
{grid_str}

Identifica qué celda vacía tiene menos valores posibles válidos.
Luego sugiere 3 posibles valores para esa celda (puede haber menos si es muy constrained).
Formato JSON: {{"celda": [fila, columna], "valores_posibles": [1, 2, 3]}}"""
    
    response = client.chat.completions.create(
        model="gpt-4o-mini",
        messages=[{"role": "user", "content": prompt_analisis}],
        temperature=0,
        response_format={"type": "json_object"}
    )
    
    try:
        analisis = json.loads(response.choices[0].message.content)
        celda = analisis["celda"]
        valores = analisis["valores_posibles"]
    except Exception:
        return grid  # Fallback
    
    # Evaluar cada valor posible
    mejor_score = -1
    mejor_valor = valores[0] if valores else 0
    
    for valor in valores:
        grid_copy = [row[:] for row in grid]
        grid_copy[celda[0]][celda[1]] = valor
        grid_str_new = "\n".join([" ".join(map(str, row)) for row in grid_copy])
        
        eval_prompt = f"""Sudoku 4x4 con valor {valor} en posición {celda}:
{grid_str_new}
¿Este valor es válido (no viola reglas)? ¿Qué tan buena es esta elección (0.0-1.0)?
Responde solo con el número."""
        
        eval_resp = client.chat.completions.create(
            model="gpt-4o-mini",
            messages=[{"role": "user", "content": eval_prompt}],
            temperature=0,
            max_tokens=10
        )
        
        try:
            score = float(eval_resp.choices[0].message.content.strip()[:4])
        except ValueError:
            score = 0.5
        
        if score > mejor_score:
            mejor_score = score
            mejor_valor = valor
    
    # Aplicar el mejor valor y continuar
    resultado = [row[:] for row in grid]
    resultado[celda[0]][celda[1]] = mejor_valor
    
    # Verificar si está completo
    if all(cell != 0 for row in resultado for cell in row):
        return resultado
    
    # Si no, continuar recursivamente (simplificado: solo 1 nivel más)
    return resultado

# Test con un Sudoku 4x4 simple:
sudoku = [
    [1, 0, 3, 0],
    [0, 3, 0, 1],
    [3, 0, 1, 0],
    [0, 1, 0, 3]
]
print("Sudoku original:")
for row in sudoku:
    print(row)
resultado = tot_sudoku_4x4(sudoku)
print("\nSudoku resuelto (un paso):")
for row in resultado:
    print(row)

Ejercicio 2: Comparar BFS vs DFS

Para el mismo problema, ejecuta tot_bfs y tot_dfs y compara:

• Número de nodos explorados
• Tiempo de ejecución
• Calidad de la solución

¿Cuándo es mejor BFS? ¿Cuándo DFS?

import time

problema = "Diseña una arquitectura de microservicios para un e-commerce con 100K usuarios diarios."

print("=== BFS ===")
start = time.time()
resultado_bfs = tot_bfs(problema, profundidad_max=2, amplitud=3, beam_size=2)
tiempo_bfs = time.time() - start
print(f"Nodos explorados: {resultado_bfs['nodos_explorados']}")
print(f"Tiempo: {tiempo_bfs:.2f}s")
print(f"Score: {resultado_bfs['score']:.2f}")

print("\n=== DFS ===")
start = time.time()
resultado_dfs = tot_dfs(problema, profundidad_max=3, amplitud=2, umbral_poda=0.4)
tiempo_dfs = time.time() - start
print(f"Nodos explorados: {resultado_dfs['nodos_explorados']}")
print(f"Tiempo: {tiempo_dfs:.2f}s")
print(f"Score: {resultado_dfs['score']:.2f}")

# Conclusiones esperadas:
# BFS con beam: Explora más nodos pero encuentra mejor solución global
# DFS con poda: Más rápido pero puede quedar atrapado en rutas largas
# BFS mejor para: problemas donde la profundidad es corta y el breadth importa
# DFS mejor para: problemas profundos donde la primera rama correcta suele ser la buena

Ejercicio 3: Diseño de un evaluador especializado

El evaluador genérico funciona para muchos casos, pero un evaluador especializado para tu dominio es mucho más preciso. Crea un evaluador para "código Python":

• Evalúa si el código es sintácticamente correcto
• Si resuelve el problema planteado
• Si es eficiente (big O)

def evaluar_codigo_python(problema: str, codigo: str) -> dict:
    """Evaluador especializado para código Python en ToT."""
    
    # Prueba de sintaxis
    try:
        compile(codigo, "<string>", "exec")
        sintaxis_ok = True
    except SyntaxError:
        sintaxis_ok = False
    
    if not sintaxis_ok:
        return {"score": 0.1, "es_solucion": False, "razon": "Error de sintaxis"}
    
    # Evaluación semántica
    prompt = f"""Código Python:
```python
{codigo}

response = client.chat.completions.create(
    model="gpt-4o-mini",
    messages=[{"role": "user", "content": prompt}],
    temperature=0,
    response_format={"type": "json_object"}
)

try:
    metricas = json.loads(response.choices[0].message.content)
    score_promedio = (
        metricas.get("correcto", 0) * 0.5 +
        metricas.get("eficiente", 0) * 0.3 +
        metricas.get("robusto", 0) * 0.2
    )
    return {
        "score": score_promedio,
        "es_solucion": score_promedio > 0.7,
        "razon": f"Correcto:{metricas.get('correcto', 0):.1f} Eficiente:{metricas.get('eficiente', 0):.1f}"
    }
except Exception:
    return {"score": 0.5, "es_solucion": False, "razon": "Error evaluación"}

</details>

---

## Resumen

- **Tree-of-Thought:** Organiza el razonamiento como un árbol donde cada nodo es un pensamiento/estado parcial
- **Componentes:** Generador de pensamientos + Evaluador + Algoritmo de búsqueda (BFS/DFS)
- **Cuándo usar:** Problemas con múltiples estrategias, cuando CoT falla sistemáticamente, cuando tienes presupuesto para muchas llamadas
- **BFS:** Mejor cuando la solución puede estar en cualquier rama; garantiza encontrar la óptima en el nivel dado
- **DFS con poda:** Más eficiente en tokens; puede quedar atrapado en rutas largas
- **Versión simplificada:** Para el 80% de casos prácticos: generar K enfoques → evaluar → continuar con el mejor

---

## Recursos adicionales

1. [Tree of Thoughts: Deliberate Problem Solving with Large Language Models (Yao et al., 2023)](https://arxiv.org/abs/2305.10601) - Paper original
2. [Large Language Model Guided Tree-of-Thought](https://arxiv.org/abs/2305.08291) - Variante guiada
3. [GitHub: princeton-nlp/tree-of-thought-llm](https://github.com/princeton-nlp/tree-of-thought-llm) - Implementación de referencia
4. [OpenAI response_format JSON mode](https://platform.openai.com/docs/guides/text-generation/json-mode)
5. [Prompt Engineering Guide - Tree of Thoughts](https://www.promptingguide.ai/techniques/tot)
6. [Graph of Thoughts - extensión de ToT](https://arxiv.org/abs/2308.09687)