Búsqueda con adversarios

Juegos

• Hasta ahora, en nuestros problemas de búsqueda, el entorno era determinista y totalmente observable.
  • Solo había que planificar una secuencia de acciones para llegar al estado objetivo.
• En los juegos hay adversarios: cada jugador tiene un objetivo diferente.
  • Los jugadores modifican el estado del entorno en beneficio propio.
  • Puede haber cooperación, pero solo si resulta beneficiosa para todos los jugadores.
• Los juegos son un ámbito muy importante de la inteligencia artificial.
  • Son un ámbito muy común, complejo y útil para la investigación.

Propiedades

Tendremos en cuenta las siguientes propiedades:

• Dos jugadores: uno puede ser la máquina y el otro una persona.
• Finito: número finito de estados. Si es muy grande, pueden utilizarse aproximaciones.
• Suma cero: la ganancia de un jugador es la pérdida del otro.
• Determinista: no hay azar.
• Información perfecta: los jugadores conocen el estado del juego en todo momento (ajedrez, Go, etc.).

Dos jugadores y suma cero

• Dos jugadores: y .
• Un conjunto de posiciones (estados)
• Una posición inicial
• Un conjunto de posiciones terminales
• Un conjunto de aristas dirigidas y entre las posiciones.
  • Representan los movimientos posibles de cada jugador.
• Una función de utilidad que asigna a cada posición terminal un valor para .

Árbol de juego (I)

Características:

• Árbol de juego: capas de estados que alternan entre los jugadores.
• Raíz: estado inicial.
• Estado del juego: posición y jugador al que le toca mover.
• Final del juego: cuando un jugador llega a una posición terminal.
• Función de utilidad: junto con los estados terminales, permite valorar los resultados.
  • Cada nodo terminal se etiqueta según su utilidad .
  • Para será ; para , .
  • En la mayoría de los juegos que veremos, .

Árbol de juego (II): ejemplo

Estrategias

• quiere maximizar su utilidad.
• quiere minimizar la utilidad de .
• no decide por sí solo a qué estado terminal llegará.
  • Cuando mueve, decide a qué estado siguiente se llegará.
• necesita una estrategia:
  • Debe decidir qué hacer ante cada posible movimiento de .
  • No basta con una secuencia de acciones predefinida: la estrategia depende de las acciones de .

MiniMax

• Estrategia recursiva.
• Suponiendo que siempre juega su mejor movimiento,
  • ¿qué movimiento debe elegirse para minimizar la utilidad de ?
• Cada nodo tendrá una puntuación minimax.
  • Será la utilidad mínima que puede obtener si juega de forma óptima.

Al minimizar la ganancia de , maximizamos la nuestra.

Ejemplo

• En el ejemplo de la derecha, los nodos son y los son .
• Los nodos terminales muestran la utilidad para .
• El resto de nodos muestra su puntuación minimax
• En la raíz, la mejor opción para es , porque conduce al nodo con la mejor puntuación minimax.
• En el segundo nivel, la mejor opción para es , porque conduce al nodo con la puntuación más baja.

Algoritmo

• Entrada: un árbol de juego , un nodo y un jugador .
• Salida: la puntuación minimax del nodo .
• Algoritmo: recursivo.
  • Si es un nodo terminal, devolver su utilidad.
  • Si es , devolver la puntuación máxima de sus hijos.
  • Si es , devolver la puntuación mínima de sus hijos.

Implementaciónnn (I)

def cerca_minimax(joc, estat):
    jugador = estat.a_moure
    return valor_maxim(joc, jugador, estat)

def valor_maxim(joc, jugador, estat):
    if joc.es_terminal(estat):
        return joc.utilitat(estat, jugador), None
    v, moviment = float('-inf'), None
    for a in joc.accions(estat):
        v2, _ = valor_minim(joc, jugador, joc.resultat(estat, a))
        if v2 > v:
            v, moviment = v2, a
    return v, moviment

Implementaciónnn (II)

def valor_minim(joc, jugador, estat):
    if joc.es_terminal(estat):
        return joc.utilitat(estat, jugador), None
    v, moviment = float('inf'), None
    for a in joc.accions(estat):
        v2, _ = valor_maxim(joc, jugador, joc.resultat(estat, a))
        if v2 < v:
            v, moviment = v2, a
    return v, moviment

Problemas

• Complejidad:
  • donde es el número de ramas por nodo y la profundidad del árbol.
• La complejidad puede ser enorme.
  • En ajedrez, y .
  • En Go, y .
• Por eso es imposible explorar todo el árbol de juego en juegos complejos.
  • Veremos técnicas que pueden ayudarnos.

Introducciónn

• Poda alfa-beta: técnica para reducir el número de nodos que hay que explorar en el árbol de juego.
• Poda: eliminar nodos del árbol de juego sin explorarlos.
• Alfa: valor mínimo que tiene garantizado que podrá obtener.
• Beta: valor máximo que tiene garantizado que podrá obtener.
• Nodos que se podan: nodos que, independientemente de su valor, no modificarán el nivel superior.

Ejemplo (I)

• La primera hoja bajo tiene valor . Por tanto, (nodo ) tiene un valor máximo de .
• La segunda hoja bajo tiene valor .
  • evitaría este movimiento, así que sigue teniendo un valor máximo de .
• La tercera hoja bajo tiene valor . El valor final de es .
  • Podemos deducir que el valor mínimo de es , ya que tiene un nodo terminal con valor .

Ejemplo (II)

• La primera hoja bajo tiene valor . Por tanto, , que es un nodo , tiene un valor máximo de .
  • Sabemos que tiene un valor de , así que nunca elegirá .
    • Por tanto, sabemos que no hace falta explorar los demás nodos hijos de .
  • Esto es la poda alfa-beta.
• Al terminar la exploración conocemos los valores de los nodos necesarios.

Reglas

• La poda alfa-beta no afecta al resultado del algoritmo.
• Se puede aplicar a cualquier profundidad del árbol.
  • A menudo se pueden podar incluso árboles enteros.
• Principio general para un nodo :
  • Si hay una opción mejor en el mismo nivel m' o en uno superior m, no se visitará .

Implementaciónn (I)

def busqueda_alfa_beta(joc, estat):
    jugador = estat.a_moure
    return valor_maxim_ab(joc, jugador, estat, float('-inf'), float('inf'))

def valor_maxim_ab(joc, jugador, estat, alfa, beta):
    if joc.es_terminal(estat):
        return joc.utilitat(estat, jugador), None
    v, moviment = float('-inf'), None
    for a in joc.accions(estat):
        v2, _ = valor_minim_ab(joc, jugador, joc.resultat(estat, a), alfa, beta)
        if v2 > v:
            v, moviment = v2, a
        if v >= beta:
            return v, moviment
        alfa = max(alfa, v)
    return v, moviment

Implementaciónn (II)

def valor_minim_ab(joc, jugador, estat, alfa, beta):
    if joc.es_terminal(estat):
        return joc.utilitat(estat, jugador), None
    v, moviment = float('inf'), None
    for a in joc.accions(estat):
        v2, _ = valor_maxim_ab(
          joc, jugador, joc.resultat(estat, a), alfa, beta
        )
        if v2 < v:
            v, moviment = v2, a
        if v <= alfa:
            return v, moviment
        beta = min(beta, v)
    return v, moviment

Mejoras

• Ordenación de nodos: ordenar correctamente los nodos hijos permite podar más.
  • Una buena ordenación puede reducir la exploración de a .
    • En ajedrez, es más probable que sean buenos los movimientos que capturan piezas.
• Para no explorar estados repetidos, se puede utilizar una tabla de transposiciones, parecida al conjunto de visitados, pero que guarde los valores de cada nodo.
• Aplicar heurísticas para limitar la evaluación: aplicar una función de evaluación a las posiciones no terminales para tratarlas como terminales.

Funciones de evaluación

Introducciónn

• En juegos complejos no se puede explorar todo el árbol de juego.
• En su lugar, se puede utilizar una función de evaluación para estimar la utilidad de un estado.
• La función de evaluación no tiene que ser perfecta.
  • Debe ser rápida de calcular.
  • Debe ser coherente con la utilidad real.

Funciones de evaluación

Ejemplo: tres en raya

• En el tres en raya podemos utilizar la siguiente función de evaluación:
  • Explicación: sumamos 1 por cada ficha de y restamos 1 por cada ficha de .

Funciones de evaluación

Implementaciónn

def avalua_tres_en_ratlla(joc, estat):
    jugador = estat.a_moure
    utilitat = 0
    for i in range(3):
        for j in range(3):
            if estat.tauler[i][j] == jugador:
                utilitat += 1
            elif estat.tauler[i][j] == joc.jugador_contrari(jugador):
                utilitat -= 1
    return utilitat