Para que servem os valores mínimos em árvores minimax?

8

Considere uma árvore minimax para um problema de pesquisa adversário. Por exemplo, nesta figura (poda alfa-beta):

insira a descrição da imagem aqui

Ao marcar a árvore com baixo para cima, primeiro atravessamos o nó 3 e atribuímos B. \ max = 3 . Depois, atravessamos 12 e 8 nesta ordem, para garantir que B.max = 3 .[min,max]3B.max=3128B.max=3

Mas por que B.min=3 ? Qual é a utilidade desse valor?

sam
fonte
De onde é a foto? É um exemplo artificial?
uli
Sim, é apenas um exemplo de caso especial. Também edito a imagem para adicionar o texto de min e max. Se aparecer algum erro, fique à vontade para dizer. Obrigado ~
sam
1
No artigo (horrível) da Wikipedia, a árvore que você fornece não parece ser uma árvore min-max. Em particular, deve ser ; , por outro lado, parece completamente certo. Então, qual é a questão aqui, realmente? Você está confuso com o exemplo ou deseja aplicações de árvores min-max? De qualquer forma, inclua uma definição precisa (!) De árvores min-max e / ou uma referência a uma. B.max12B.min
Raphael
1
Por favor, inclua uma referência para a imagem; Tenho motivos para acreditar que você não o criou. Os slides vinculados também podem responder a algumas perguntas suas; eles parecem usar árvores diferentes das suas.
Raphael
1
A imagem parece enganosa ..
Strin

Respostas:

7

Esta figura (que é de fato correta) é usada na explicação do algoritmo de poda alfa-beta em uma árvore minimax. A poda alfa-beta é um método usado para podar partes da árvore minimax em um problema de pesquisa adversário. No contexto de um jogo da velha, as árvores minimax destinam-se a permitir que o computador procure no espaço de todos os tabuleiros de jogos possíveis (configurações de x e o) assumindo que os movimentos do jogador são ideais. Isso permite que o computador proponha uma mudança que forneça o melhor resultado (é por isso que o jogo de conectar-quatro no seu computador é incrivelmente difícil de vencer!). Para uma descrição mais completa, sugiro "AI a Modern Approach", de Stuart e Norvig (pág. 162-170 ish, na 2ª ed.).

Agora que esclarecemos alguma confusão sobre o algoritmo. A poda alfa-beta tenta evitar a expansão de subárvores com base em como o algoritmo minimax funciona. Sabemos que o nó máximo no nível superior terá o maior valor de todos os seus filhos. Portanto, o nó encontra o valor e, até o momento, esse é o valor máximo que ele deseja passar para o pai, para que ele coloque esse valor no slot MAX. Então ele encontra . Lembre-se de que é um nó MIN, portanto, ele deseja minimizar o valor que passa para seu pai, mantendo assim o valor no slot MAX. Novamente para . Quando pesquisou todos os seus filhos, ele conhece o limite inferior máximo (B312B38Bα) e a solução de limite superior mínimo ( ) de sua subárvore e mantém esses valores em MIN ( ) e MAX ( ) (como [3, 3]).βαβ

Nota: min e max rotulados na figura NÃO são os valores mínimo e máximo da subárvore! Eles são (rotulados de maneira bastante confusa) os limites alfa-beta das soluções da subárvore (lembre-se de que este é um problema de pesquisa contraditório).

Em seguida, mover para o nó . Aqui nos deparamos com um na primeira posição. O nó , que deseja selecionar o valor mais baixo de sua subárvore, SABE agora que seu pai não selecionará seu valor, pois o nó encontrou um valor maior. Portanto, podemos podar o resto da sub-árvore e continue para .C2CBD

Finalmente, para responder à pergunta específica: Por que .min = 3? Um valor para (o limite inferior máximo de soluções neste nó) e (o limite superior mínimo de soluções neste nó) é mantido em cada nó para executar a remoção. Esses valores vinculam os possíveis casos em que o valor de um nó (ou sua subárvore) pode fazer parte da solução.Bαβ

Neste exemplo, ele não parece ter um papel, no entanto, tente olhar para exemplos mais complicados (ou seja, árvores com uma altura> 3) como esta e veja se você consegue entender isso.

Não posso fazer justiça à poda minimax ou alfa-beta aqui (principalmente porque não as uso há anos); portanto, se você realmente quiser entender isso, consulte um livro sobre IA como o de Stuart e Norvig (o surpreendentemente, a página da Wikipedia também não tem visualização).

usuario
fonte
Sim, como você disse, acho que concorda totalmente com a correção da imagem, certo? Obrigado por compartilhar um processo tão detalhado da verificação do AlphaBeta, e minha pergunta é: qual é a utilidade do valor mínimo? Os valores mínimos são sempre os mesmos que os valores máximos? Nesse caso, são os 3 primeiros de [3,3].
31412 Sam
@ sam, sim, a imagem está definitivamente correta. Editei minha resposta para (parcialmente) responder a sua pergunta específica. Espero que isto ajude.
6124 Nick
"Quando B pesquisou todos os seus filhos, ele conhece os valores mínimos e máximos de sua subárvore e mantém esses valores em MIN e MAX (como [3, 3])" - mas obviamente não é isso que acontece (deve ser então). Sua explicação mais tarde faz mais sentido. [3,12]
Raphael
@ Rafael, eu deveria ter sido mais claro. Esses não são os valores mínimo e máximo da subárvore, são o limite mínimo e o limite máximo máximo que o nó pode propagar para o pai.
6124 Nick
@ Nick: Isto é como eu entendi minimax também. Como o OP confundiu minimax e min-max inicialmente, talvez você deva deixar isso muito claro em sua resposta e incluir um exemplo não trivial (que não seja vinculado).
Raphael