Algoritmos Esenciales en IA: Búsqueda en Profundidad, Heurísticas y Estrategias de Juego

Búsqueda en Profundidad (DFS)

Una Búsqueda en Profundidad (en inglés DFS o Depth First Search) es un algoritmo que permite recorrer recursivamente todos los nodos de un grafo o árbol de manera ordenada, aunque no uniforme. Su funcionamiento consiste en expandir de forma recurrente cada uno de los nodos que va localizando en un camino concreto. Cuando ya no quedan más nodos que visitar en dicho camino, *regresa* (mediante *backtracking*), repitiendo el mismo proceso con cada uno de los hermanos del nodo ya procesado.

Heurísticas

Definición

Es una técnica que aumenta la eficiencia de un proceso de búsqueda. Es el análisis y extrapolación de datos basados en experiencias pasadas y en sus consecuencias; este apartado es importante para la IA de juegos.

Son métodos o algoritmos exploratorios para la resolución de problemas, en los cuales las soluciones se descubren mediante la evaluación del progreso logrado en la búsqueda de un resultado final.

Es el dato 'extra' que nos permite llegar a la solución con más rapidez.

Objetivo

Guiar el proceso de búsqueda en la dirección más provechosa, sugiriendo el camino a seguir cuando hay más de una opción.

Tipos de Heurísticas

• Generales: Son adecuadas para una amplia variedad de dominios.
• De Propósito Específico: Explotan el conocimiento específico de un dominio para resolver problemas particulares.

Evaluación de Heurísticas

Heurísticas Admisibles

Son optimistas por naturaleza. En todas las heurísticas admisibles, el costo de *f* nunca decrece a lo largo de todos los caminos del árbol. Se dice que estas heurísticas tienen un comportamiento monótono.

Cuando no es monótona, se puede corregir *f* para que lo sea:

• Consideremos dos nodos, *n* y *n'*.
• *n* es el nodo padre de *n'*.
• *g(n)* = 3, *h(n)* = 4 → *f(n)* = 7.
• *g(n')* = 4, *h(n')* = 2 → *f(n')* = 6.

Todos los caminos que pasan por *n'* también pasan por *n*, por lo que el valor de *f(n')* no es relevante en este contexto. Por lo tanto, cada vez que se genera un nodo nuevo, deberíamos confirmar que su costo sea menor o igual que el de su padre.

f(n') = max(f(n), g(n') + h(n'))

Heurísticas Dominantes

Tenemos dos funciones heurísticas (*h1* y *h2*). Si *h2(n)* >= *h1(n)* para cualquier nodo *n*, decimos que *h2* domina a *h1*. La dominación se traduce en eficiencia: una heurística dominante expande menos nodos. Es preferible el uso de una función heurística dominante siempre y cuando sea admisible.

Teoría de Juegos

El objetivo no es el análisis de los elementos aleatorios, sino de los comportamientos estratégicos de los jugadores.

La posibilidad de clasificar los juegos es amplia, pero nosotros hemos estudiado los que se clasifican por el resultado. Pueden ser de suma cero, cuando el aumento en las ganancias de un jugador implica una disminución igual en el otro jugador; o de suma no nula, cuando la suma de las ganancias de los jugadores puede aumentar o disminuir en función de sus decisiones.

Algoritmo Minimax

Este algoritmo se aplica generalmente en juegos de dos participantes, donde la ganancia de uno es igual a la pérdida del otro. Este algoritmo parte del supuesto de que el programa dispone de todo el tiempo necesario hasta que llegue a los estados terminales.

Pasos del Algoritmo Minimax:

1. Generar el árbol hasta los estados terminales.
2. Aplicar la función de evaluación y obtener el valor respectivo.
3. Usar la utilidad de los estados terminales para calcular el valor de los nodos del siguiente nivel.
4. Finalmente, los valores respaldados llegan a la parte superior del árbol; en el nivel Max se elige el valor máximo y en el nivel Min el mínimo.

Algoritmo Alfa-Beta (α-β)

Es una mejora del algoritmo Minimax. Este algoritmo nos da la oportunidad de podar las ramas que no son eficientes. La eficiencia de Alfa-Beta dependerá del orden en que se analicen los sucesores que aparentemente tienen más posibilidad de ser los mejores. Suponiendo que esto es posible llevarlo a cabo, Alfa-Beta puede anticipar el doble que Minimax.

Pseudocódigo del Algoritmo Alfa-Beta

algoritmo alfa-beta(nodo, profundidad, α, β)
    if (nodo es terminal) or (profundidad == 0)
        return evaluacion(nodo)

    if nodo es maximizador:
        for cada hijo i de nodo:
            α = max(α, alfa-beta(hijo_i, profundidad - 1, α, β))
            if α >= β:
                return β  // Poda: se puede podar el resto de hijos
        return α
    else (nodo es minimizador):
        for cada hijo i de nodo:
            β = min(β, alfa-beta(hijo_i, profundidad - 1, α, β))
            if &beta; <= &alpha;:
                return &alpha; // Poda
        return &beta;