Algoritmo Minimax

Question

Tenho uma pergunta simples sobre o algoritmo Minimax:por exemplo, para o jogo da velha, como determino as funções de utilidade para cada jogador?Isso não acontece automaticamente, não é?Devo codificar os valores do jogo, ele não consegue aprendê-los sozinho, não é?

Answer 1

Não, um minimax não aprende. É uma versão mais inteligente de uma pesquisa de árvore de força bruta.

Answer 2

Normalmente, você implementaria a função de utilitário diretamente. Nesse caso, o algoritmo não aprenderia a jogar o jogo, ele usaria as informações que você tinha explicitamente codificado na implementação.

No entanto, seria possível usar Programação genética (GP) ou alguma técnica equivalente para derivar automaticamente uma função de utilidade. Nesse caso, você não precisaria codificar nenhuma estratégia explícita. Em vez disso, a evolução descobriria sua própria maneira de jogar bem o jogo.

Você pode combinar seu código Minimax e o código GP em um único (provavelmente muito lento) programa adaptativo, ou pode executar o GP primeiro, encontrar uma boa função de utilidade e depois adicionar essa função ao seu código mínimo, assim como você faria qualquer mão -função codificada.

Answer 3

O Tic-Tac-Toe é pequeno o suficiente para executar o jogo até o final e atribuir 1 para Win, 0 para empatar e -1 para perder.

Caso contrário, você deve fornecer uma função que determine o valor de uma posição heuristicamente. No xadrez, por exemplo, um grande fator é o valor do material, mas também quem controla o centro ou com que facilidade as peças podem se mover.

Quanto ao aprendizado, você pode adicionar fatores de peso a diferentes aspectos da posição e tentar otimizá -los jogando repetidamente jogos.

Answer 4

Como determinar a função de utilidade para cada peça?

Com cuidado ;-) Isso artigo mostra como uma função de avaliação ligeiramente falha (uma por ex.que não vai "fundo" o suficiente ao olhar para frente na árvore de possíveis camadas, ou que não consegue capturar a força relativa de algumas posições do tabuleiro) resulta em um algoritmo geral fraco (que perde com mais frequência).

ele não pode aprendê-los sozinho, não é?

Não, isso não acontece.Existem maneiras, entretanto, de fazer o computador aprender a força relativa das posições no conselho.Por exemplo, examinando Donald Mitchie e seu programa MENACE você verá como um processo estocástico pode ser usado para aprender o tabuleiro sem qualquer a priori conhecimento, mas as regras do jogo.O engraçado é que, embora isso possa ser implementado em computadores, bastam algumas centenas de contas coloridas e caixas de fósforos, graças ao tamanho relativamente pequeno do espaço de jogo e também às várias simetrias.

Depois de aprender uma maneira tão legal de ensinar o computador a jogar, podemos não estar tão interessados ​​em voltar ao MinMax aplicado ao Tic-Tac-Toe.Afinal MinMax é uma maneira relativamente simples de podar uma árvore de decisão, o que dificilmente é necessário com o pequeno espaço de jogo do jogo da velha.Mas, se for preciso ;-) [voltar para MinMax]...

Podemos olhar para a “caixa de fósforos” associada à próxima jogada (ou seja,sem ir fundo) e use a porcentagem de contas associadas a cada quadrado, como um fator adicional.Podemos então avaliar uma árvore tradicional, mas indo apenas, digamos, 2 ou 3 movimentos de profundidade (uma profundidade superficial de antecipação que normalmente terminaria em perdas ou empates) e avaliar cada movimento seguinte com base no simples -1 ( derrota), classificação 0 (empate/desconhecido), +1 (vitória).Combinando então a porcentagem de contas e a classificação simples (por exemplo, adição, certamente não por multiplicação), somos capazes de usar efetivamente o MinMax de uma forma que é mais semelhante à forma como é usado nos casos em que não é possível avaliar a árvore do jogo até o fim.

Conclusão:No caso do Tic-Tac-Toe, o MinMax só se torna mais interessante (por exemplo, para nos ajudar a explorar a eficácia de uma determinada função de utilidade) quando removemos a natureza determinística do jogo, associada à fácil avaliação da árvore completa.Outra forma de tornar o jogo [matematicamente] interessante é jogar com um adversário que comete erros...