Algoritmo Minimax: Função de Custo/Avaliação?

Question

Um projeto escolar me faz escrever um jogo de data em C ++ (exemplo em http://www.cut-the-knot.org/curriculum/games/date.shtml) onde o player de computador deve implementar um algoritmo mínimo com a poda alfa-beta. Até agora, entendo qual é o objetivo por trás do algoritmo em termos de maximizar ganhos em potencial, enquanto assumiu que o oponente os minimize.

No entanto, nenhum dos recursos que li me ajudou a entender como projetar a função de avaliação que o mínimo baseia tudo o que suas decisões. Todos os exemplos tiveram números arbitrários atribuídos aos nós da folha, no entanto, preciso atribuir valores significativos a esses nós.

A intuição me diz que seria algo como +1 para um nó de folha de vitória e -1 para uma perda, mas como os nós intermediários avaliam?

Qualquer ajuda seria muito apreciada.

Answer 1

O mínimo mais básico avalia apenas nós foliares, marcando vitórias, perdas e desenhos e apóia esses valores na árvore para determinar os valores de nó intermediários. No caso de a árvore do jogo ser intratável, você precisa usar uma profundidade de corte como um parâmetro adicional para suas funções mínimas. Uma vez atingida a profundidade, você precisa executar algum tipo de função de avaliação para estados incompletos.

A maioria das funções de avaliação em uma pesquisa mínima é específica do domínio; portanto, encontrar ajuda para o seu jogo em particular pode ser difícil. Lembre -se de que a avaliação precisa retornar algum tipo de expectativa percentual de a posição ser uma vitória para um jogador específico (normalmente no máximo, embora não ao usar uma implementação da Negamax). Quase qualquer jogo menos pesquisado se parecerá com outro jogo mais pesquisado. Este se vincula muito de perto com o jogo palitos de coleta. Usando apenas o Minimax e o Alpha Beta, acho que o jogo é tratável.

Se você estiver, deve criar uma função de avaliação para posições não terminais, aqui está uma pequena ajuda com a análise do jogo Sticks, que você pode decidir se é útil para o jogo da data ou não.

Comece a procurar uma maneira de forçar um resultado olhando para uma posição terminal e todos os movimentos que podem levar a essa posição. No jogo Sticks, uma posição de terminal é com 3 ou menos paus restantes no último movimento. A posição que prossegue imediatamente que a posição do terminal está, portanto, deixando 4 paus no seu oponente. O objetivo agora é deixar seu oponente com 4 paus, não importa o quê, e isso pode ser feito a partir de 5, 6 ou 7 paus sendo deixados para você, e você gostaria de forçar seu oponente a deixá -lo em uma dessas posições. O local em que seu oponente precisa estar para que você esteja em 5, 6 ou 7 é 8. Continue essa lógica e um padrão fica disponível muito rapidamente. Sempre deixe seu oponente com um número divisível por 4 e você ganha, qualquer outra coisa, perde.

Este é um jogo bastante trivial, mas o método para determinar a heurística é o que é importante porque pode ser aplicado diretamente à sua tarefa. Como o último a se mover é o primeiro, e você pode alterar apenas um atributo de data por vez, você sabe que vencer, é necessário que haja exatamente 2 movimentos ... e assim por diante.

Boa sorte, deixe -nos saber o que você acaba fazendo.

Answer 2

O caso mais simples de uma função de avaliação é +1 para uma vitória, -1 para uma perda e 0 para qualquer posição não acabada. Dado que sua árvore é profunda o suficiente, mesmo essa função simples lhe dará um bom jogador. Para quaisquer jogos não triviais, com alto fator de ramificação, normalmente você precisa de uma função melhor, com algumas heurísticas (por exemplo, para xadrez, você pode atribuir pesos a pedaços e encontrar uma soma etc.). No caso do jogo de data, eu usaria a função de avaliação mais simples, com 0 para todos os nós intermediários.

Como nota lateral, o MinMAX não é o melhor algoritmo para este jogo em particular; Mas acho que você já sabe disso.

Answer 3

Pelo que eu entendo do jogo de data que você vinculou, parece que os únicos resultados possíveis para um jogador são vencedores ou perdem, não há intermediário (por favor me corrija se eu estiver errado).

Nesse caso, é apenas uma questão de atribuir um valor de 1 a uma posição vencedora (o jogador atual chega a 31 de dezembro) e um valor de -1 para as posições perdidas (outro jogador chega a 31 de dezembro).

Seu algoritmo minimax (sem poda alfa-beta) ficaria assim:

A_move(day):
   if day==December 31:
       return +1
   else:
       outcome=-1
       for each day obtained by increasing the day or month in cur_date:
           outcome=max(outcome,B_move(day))
       return outcome

B_move(day):
   if day==December 31:
       return -1
   else:
       outcome=+1
       for each day obtained by increasing the day or month in cur_date:
           outcome=min(outcome,A_move(day))
       return outcome