Implementación de Algoritmos de Búsqueda Heurística y Minimax en Python

Algoritmos de Búsqueda Informada y Estratégica

1. Búsqueda Voraz (Greedy Search)

Propiedades: Completo, no óptimo. Complejidad de tiempo y espacio: O(b*m).

def busquedavoraz(nodoInicial):
    objetivo = False
    abiertos = []
    sucesores = []

    raiz = nodoInicial()
    abiertos.append(raiz)

    while not objetivo and len(abiertos) != 0:
        nodo = abiertos.pop(0)

        if testObjetivo(nodo.estado):
            objetivo = True
        else:
            sucesores = expandir(nodo)

            for nodosucesor in sucesores:
                posicion = 0
                heu = heuristica(nodosucesor.estado)
                while posicion < len(abiertos) and (heuristica(abiertos[posicion].estado) < heu):
                    posicion += 1

                abiertos.insert(posicion, nodosucesor)

    if objetivo:
        dispSolucion(nodo)
    elif not objetivo:
        print("No se ha encontrado una solución\n")

    return objetivo

2. Búsqueda Voraz con Control de Repetidos

Implementación que utiliza un conjunto de cerrados para gestionar la exploración de estados ya visitados mediante hashing.

def busquedavorazrepetidos() -> bool:  # f(n) = h(n)
    objetivo = False
    abiertos = []
    sucesores = []
    cerrados = set()

    raiz = nodoInicial()
    abiertos.append(raiz)

    while not objetivo and len(abiertos) != 0:
        nodo = abiertos.pop(0)

        if testObjetivo(nodo.estado):
            objetivo = True
        else:
            # Se añade el hash del nodo a la lista de cerrados
            cerrados.add(nodo.estado.calcular_hash())
            sucesores = expandir(nodo)

            for nodosucesor in sucesores:
                # Se comprueba que el hash del nodo sucesor no esté en dicha lista
                if nodosucesor.estado.calcular_hash() not in cerrados:
                    posicion = 0
                    heu = heuristica(nodosucesor.estado)

                    while posicion < len(abiertos) and (heuristica(abiertos[posicion].estado) < heu):
                        posicion += 1

                    abiertos.insert(posicion, nodosucesor)

    if objetivo:
        dispSolucion(nodo)
    elif not objetivo:
        print("No ha sido posible encontrar una solución\n")

    return objetivo

3. Búsqueda A* con Distancia Manhattan

Propiedades: Completo y óptimo cuando la heurística es admisible (no sobreestima el coste real).

Complejidad de tiempo y espacio: O(b*m); si la heurística es admisible, se define como O(b^d).

def busquedaAmanhattan():  # f(n) = g(n) + h(n)
    objetivo = False
    abiertos = []
    sucesores = []
    cerrados = {}

    raiz = nodoInicial()
    abiertos.append(raiz)

    while not objetivo and len(abiertos) != 0:
        nodo = abiertos.pop(0)

        if testObjetivo(nodo.estado):
            objetivo = True
        else:
            # Si el estado no está en cerrados o se encuentra un camino mejor (menor coste total)
            if (nodo.estado.calcular_hash() not in cerrados or
                cerrados[nodo.estado.calcular_hash()] > (nodo.costeCamino + manhattan(nodo.estado))):
                
                sucesores = expandir(nodo)
                abiertos += sucesores
                abiertos.sort()  # Ordena la lista según f(n) = g(n) + h(n)

                # Guarda el mejor coste encontrado para ese estado
                cerrados[nodo.estado.calcular_hash()] = nodo.costeCamino + manhattan(nodo.estado)

    if objetivo:
        dispSolucion(nodo)
    elif not objetivo:
        print("No ha sido posible encontrar la solución\n")

    return objetivo

4. Algoritmo Minimax para Juegos

Complejidad: O(b^m). Este algoritmo es fundamental en la toma de decisiones para juegos de suma cero.

def minimax(nodo: Nodo) -> Nodo:
    mejor_accion = None
    mejor_utilidad = float('-inf')
    inicial = estadoinicial(nodo)

    # Por cada acción posible desde el nodo inicial
    for accion in nodo.acciones(inicial):
        resultado = nodo.resultado(inicial, accion)
        utilidad = valormin(resultado)  # Valor del nivel MIN

        if utilidad > mejor_utilidad:
            mejor_accion = accion
            mejor_utilidad = utilidad

    return mejor_accion

def valormin(nodo: Nodo) -> int:
    if terminal(nodo):
        return utilidad(nodo)

    valor_min = float('inf')

    for jugada in jugadas:
        if esvalida(nodo, jugada):
            valor_min = min(
                valor_min,
                valormax(aplicaJugada(nodo, jugada), opuesto(jugador))
            )

    return valor_min

def valormax(nodo: Nodo, jugador: int) -> int:
    if terminal(nodo):
        return utilidad(nodo)

    valor_max = float('-inf')

    for jugada in jugadas:
        if esvalida(nodo, jugada):
            valor_max = max(
                valor_max,
                valormin(aplicaJugada(nodo, jugada), opuesto(jugador))
            )

    return valor_max