Algoritmo Min-Max (parte 2)

E se limitarmos a busca até uma determinada profundidade \(p\)?

Por exemplo, no caso abaixo em \(p=2\)?

O que está faltando?

Função de utilidade

• A ideia é substituir a avaliação de estados terminais pela avaliação de estados intermediários.

• A função de avaliação deve retornar um valor alto para estados que tem uma utilidade maior para o nosso robô e valores baixos para estados que tem um utilidade menor.

• Podemos utilizar as mesmas regras vistas em Definindo algumas verificações.

Versão Min-Max com limite de profundidade

def max_value(estado, p):
    if p == 0:
        return estado.eval()
    v = -math.inf
    for s in estado.sucessores():
        v = MAX(v, min_value(s, p-1))
    return v

def min_value(estado, p):
    if p == 0:
        return estado.eval()
    v = math.inf
    for s in estado.sucessores():
        v = MIN(v, max_value(s, p-1))
    return v

Humano versus Min-Max com limite de profundidade

Vamos testar o desempenho de um Min-Max com profundidade 1, 3, 5 e 7? Digite:

python connect4_with_ai.py minmax 1

python connect4_with_ai.py minmax 3

python connect4_with_ai.py minmax 5

python connect4_with_ai.py minmax 7

Quais foram as diferenças observadas?

• Teve alguma diferença em termos de tempo de processamento?
• Teve alguma diferença em termos de desempenho?
• Alguma das configurações chega a ter um desempenho similar ao de um humano?