Como criar uma boa função de avaliação para um jogo?

https://stackoverflow.com/questions/1291377

18-09-2019
|

Pergunta

Eu escrevo programas para jogar jogo de tabuleiro variantes, por vezes,.A estratégia básica é padrão alfa-beta de poda ou pesquisas semelhantes, às vezes aumentada pelo abordagens usuais para finais ou aberturas.Eu já joguei em torno de xadrez com variantes, por isso, quando chega a hora de escolher a minha função de avaliação, eu uso uma base de xadrez função de avaliação.

No entanto, agora eu estou escrevendo um programa para executar um completamente novo jogo de tabuleiro.Como faço para escolher um bom ou até decente função de avaliação?

Os principais desafios são que as peças são sempre no tabuleiro, de modo habitual função de material não vai mudar, com base na posição, e o jogo foi jogado menos de mil vezes ou mais, para que os humanos não necessariamente jogar bem o suficiente ainda para dar a introspecção.(PS.Eu considerava um MoGo abordagem, mas jogos aleatórios não são susceptíveis de terminar.)

Detalhes do jogo:O jogo é jogado em um de 10 por 10 placa fixa com seis peças de cada lado.As peças possuem certas regras de deslocamento e interagir em determinadas maneiras, mas nenhuma peça já capturada.O objetivo do jogo é ter o suficiente de suas peças, em certos quadrados no tabuleiro.O objetivo do programa de computador é a de proporcionar um jogador que é competitivo com ou melhor que os atuais jogadores humanos.

Solução

Encontre alguns candidatos para sua função de avaliação, como mobilidade (nº de movimentos possíveis), menos a mobilidade do oponente e tente encontrar o peso ideal para cada métrica. Os algoritmos genéticos parecem funcionar muito bem para otimizar pesos em uma função de avaliação.

Crie uma população com pesos aleatórios, lute com eles um contra o outro com uma profundidade limitada e curvas, substitua os perdedores por combinações aleatórias dos vencedores, embaralham e repita, imprimindo a média da população após cada geração. Deixe -o funcionar até que você esteja satisfeito com o resultado ou até ver a necessidade de ajustar o intervalo para algumas das métricas e tentar novamente, se parecer que o valor ideal para uma métrica pode estar fora do seu intervalo inicial.

Edição tardia: Uma abordagem mais aceita, estudada e compreendida que eu não sabia na época é algo chamado "evolução diferencial". Os filhos são criados a partir de três pais em vez de 2, de tal maneira que evite o problema da convergência prematura em relação à média.

Outras dicas

Vou começar com alguns conceitos básicos e mover-se para mais coisas mais tarde.

Básica do agente e um framework de testes

Não importa o que você fizer você precisa para começar com algo bem simples e mudo.A melhor abordagem para um mudo agente é um aleatório (gerar todos os movimentos possíveis, selecione um ao acaso).Isso vai servir como um ponto de partida para comparar todos os outros agentes.Você precisa de um forte quadro de comparação.Algo que leva a vários agentes, permite jogar alguns jogos entre eles e retorna a matriz de desempenho.Com base nos resultados, calcular a aptidão de cada agente.Por exemplo, a sua função tournament(agent1, agent2, agent3, 500) vai jogar de 500 jogos entre cada par de agente (jogando o primeiro/segundo) e retorna algo como:

  x         -0.01       -1.484   |  -1.485
0.01          x         -1.29    |  -1.483
1.484       1.29          x      |  2.774

Aqui, por exemplo, eu uso 2 pontos por vitória, 1 ponto por empate de pontuação de função, e no fim apenas a soma de tudo para encontrar o fitness.Esta tabela imediatamente me diz que agent3 é a melhor, e agent1 não é muito diferente do agent2.

Assim, uma vez que estas duas coisas importantes são configurado, você está pronto para experimentar com suas funções de avaliação.

Vamos começar com a seleção de recursos

Primeiro de tudo você precisa para criar not a terrible função de avaliação.Com isto quero dizer que esta função deve identificar corretamente 3 aspectos importantes (vitória/empate/derrota).Isto parece óbvio, mas eu tenho visto quantidade significativa de robôs, onde os criadores não foram capazes de configurar corretamente estes 3 aspectos.
Em seguida, você use o seu engenho humano para encontrar algumas características do jogo do estado.A primeira coisa a fazer é falar com um jogo de especialistas e perguntar a ele como ele acessar a posição.
Se você não tiver o perito, ou você mesmo acabou de criar as regras de seu jogo de 5 minutos atrás, não subestime a humana capacidade para procurar padrões.Mesmo depois de jogar um par de jogos, uma pessoa inteligente pode dar-lhe algumas ideias de como ele deve ter jogado (o que não significa que ele pode implementar as idéias).Use essas idéias como recursos.
Neste ponto, você realmente não precisa saber como essas características afetam o jogo.Exemplo de características:valor das peças, peças de mobilidade, controle de posições importantes, a segurança, o número total de movimentos possíveis, a aproximação para um término.
Depois de o código para esses recursos, e usou-as separadamente para ver o que funciona melhor (não se apresse a rejeitar os recursos que não realizar razoável, por si só, eles podem ser úteis em conjunto com os outros), você está pronto para experimentar com combinações.

A construção de uma melhor avaliação pela combinação e ponderação de recursos simples. Há um par de abordagens padrão.

Criar um uber função com base em várias combinações de seus recursos.Ele pode ser linear eval = f_1 * a_1 + ... f_n * a_n (f_i recursos a_i coeficientes), mas pode ser qualquer coisa.Em seguida, instanciar vários agentes com absolutamente aleatório pesos para esta função de avaliação e utilização de algoritmo genético para jogá-los contra os outros.Comparar os resultados obtidos utilizando o framework de testes, descartar alguns perdedores e se transformar um par de vencedores.Continue o mesmo processo.(Este é um esboço, leia mais sobre GA)
Usar o back-propagação da idéia de redes neurais para fazer propagar o erro do final do jogo para atualizar os pesos da rede.Você pode ler mais sobre como ele foi feito com backgammon (Eu não tenha escrito algo semelhante, então desculpem a falta).

Você pode trabalhar sem avaliação da função! Isso pode soar insano para uma pessoa que apenas ouviu falar sobre minimax/alfa-beta, mas existem métodos que não necessitam de uma avaliação em tudo.Um deles é chamado de Monte Carlo Árvore De Pesquisa e, como um de Monte Carlo em um nome sugere, ele usa um monte de aleatório (não deve ser aleatório, ele pode usar o seu antigo bom agentes) jogo joga para gerar uma árvore.Este é um tópico enorme, por si só, então eu vou dar-lhe a mina realmente de alto nível de explicação.Você começa com uma raiz, crie a sua fronteira, que tenta se expandir.Uma vez que você expanda algo, você só aleatoriamente ir para a folha.Ficando o resultado da folha, você backpropagate o resultado.Fazer isso muitas vezes, e coletar estatísticas sobre cada criança da atual fronteira.Selecionar o melhor.Há significativa de teoria que se relaciona com a forma como você o equilíbrio entre a exploração e o aproveitamento e uma boa coisa para ler há UCT (Superior de Confiança Vinculados algoritmo)

Eu examinaria um algoritmo de aprendizado de máquina supervisionado, como o aprendizado de reforço. Verificação de saída Aprendizagem de reforço em jogos de tabuleiro. Eu acho que isso lhe dará algumas boas direções para analisar.

Além disso, confira Aquisição de estratégia para o jogo Otelo com base no aprendizado de reforço (Link PDF) Onde, dadas as regras do jogo, uma boa "função de pagamento" pode ser aprendida. Isso está intimamente relacionado a TD-Gammon ...

Durante o treinamento, a própria rede neural é usada para selecionar movimentos para ambos os lados ... A descoberta bastante surpreendente foi que uma quantidade substancial de aprendizado realmente ocorreu, mesmo nos zero experimentos iniciais de conhecimento que utiliza uma codificação de placa bruta.

Se ninguém entende o jogo ainda, não há como obter uma função de avaliação decente. Não me diga que o alfa-beta padrão com contagem de materiais é bom ou mesmo decente para o xadrez ou suas variantes (talvez o xadrez dos perdedores seja uma exceção).

Você pode experimentar redes neurais com feedback ou algoritmos similares de aprendizado de máquina, mas eles geralmente são péssimos até que tenham toneladas de treinamento, o que neste caso provavelmente não está disponível. E mesmo assim, se eles não são péssimos, você não pode obter conhecimento deles.

Eu acho que não há como entender o jogo da melhor maneira possível e, para iniciantes, deixar as incógnitas como aleatórias na função de avaliação (ou apenas fora de cena até que as incógnitas se tornem mais conhecidas).

Obviamente, se você compartilhar mais informações sobre o jogo, poderá obter melhores idéias da comunidade.

Pelo que entendi, você deseja uma boa função de avaliação estática para usar nas folhas da sua árvore Min-Max. Nesse caso, é melhor lembrar que o objetivo dessa função de avaliação estática é fornecer uma classificação sobre o quão bom é o quadro para o player de computador. Assim é

F (Board1)> F (Board2)

Então deve ser verdade que o Board1 é melhor para o computador (é mais provável que eventualmente vença) do que no Board2. Obviamente, nenhuma função estática está completamente correta para todas as placas.

Então, você diz que "o objetivo do jogo é ter suas peças suficientes em certos quadrados especiais no quadro", então uma primeira facada no f (placa) seria simplesmente contar o número de peças que o computador tem nelas quadrados especiais. Você pode então refiná -lo mais.

Sem conhecer as especificidades do jogo, é impossível dar melhores suposições. Se você nos deu as regras do jogo, tenho certeza de que os usuários do Stackoverflow poderiam vir com toneladas de idéias originais para essas funções.

Embora você possa usar vários métodos de aprendizado de máquina para criar uma função de avaliação (aprendizado de TD, usado em projetos como o GnubackGammon, é um exemplo), os resultados dependem definitivamente do próprio jogo. Para o Backgammon, funciona muito bem, porque a natureza estocástica do jogo (Rolling Dice) força o aluno a explorar o território que pode não querer fazer. Sem um componente crucial, você provavelmente acabará com uma função de avaliação que é boa contra si mesma, mas não contra os outros.

Como a diferença material pode não ser aplicável, o conceito de mobilidade é importante - ou seja, quantos movimentos possíveis você tem disponível? O controle de uma determinada área da placa geralmente é melhor do que não? Converse com as pessoas que jogam o jogo para descobrir algumas pistas.

Embora seja preferível ter uma função de avaliação o mais boa possível, você também precisa ajustar seu algoritmo de pesquisa para poder pesquisar como profundamente que possível. Às vezes, isso é realmente mais uma preocupação, uma vez que um pesquisador profundo com uma função de avaliação de medicamentos pode superar as pesquisas superficiais com uma boa função de avaliação. Tudo depende do domínio. (Gnubackgammon joga um jogo especializado com uma pesquisa de 1 anda, por exemplo)

Existem outras técnicas que você pode usar para melhorar a qualidade da sua pesquisa, o mais importante, para ter uma tabela de transposição para os resultados da pesquisa em cache para ter a verdadeira poda para a frente.

Eu recomendo olhar esses slides.

Você também precisa ter cuidado em sua escolha.Se o algoritmo não tem um conhecido relação ao valor real, o padrão AI funções não funcionará corretamente.Para ser válida, a função de avaliação, ou heurística tem de ser igual ou abaixo do valor real de forma consistente ou ele irá guiar suas decisões de uma maneira estranha (o que poderia argumentar a favor de xadrez, mesmo que eu acho que o padrão de pontos são muito bem).

O que eu geralmente faço é descobrir o que é capaz e do que é necessário.Para alguns jogos, como sokoban, eu tenho usado o número mínimo de movimentações de caixa necessárias para levar uma caixa (em isolamento), a partir da sua localização actual para qualquer objetivo locais.Esta não é uma resposta exata para o número de movimentos, mas eu acho que é uma boa heurística, pois nunca pode superestimar e pode ser pré-calculadas para todo o conselho.Quando somar a pontuação de uma placa, ele é apenas a soma dos valores para cada caixa de localização.

Em uma vida artificial simulação que eu escrevi para evoluir pack de caça e pack de defesa, o sistema de pontuação utilizado apenas para guiar a evolução e não executar nenhuma poda.Eu dei a cada criatura um ponto por ter nascido.Para cada ponto de energia que são consumidos em sua vida, dei-lhes um ponto adicional.Então, usei a soma de seus pontos de geração para determinar qual a probabilidade de cada um foi para se reproduzir.No meu caso, eu simplesmente usou a proporção do total de pontos da sua geração, que tinham adquirido.Se eu quisesse evoluir criaturas que foram grandes em fugir, eu teria marcou para baixo para obter pontos comido fora delas.

Você também deve ter cuidado para que a sua função não é muito difícil de um gol para bater.Se você está tentando evoluir alguma coisa, você quer certificar-se de que o espaço de solução tem uma boa inclinação.Você deseja guiar a evolução em um sentido, não basta declarar uma vitória, se isso acontece aleatoriamente bater.

Sem saber mais sobre o jogo eu seria duramente pressionado para dizer a você como criar uma função.Existem valores claros de algo que indicam uma vitória ou uma perda?Você tem uma maneira de se estimar um custo mínimo para fechar a lacuna?

Se você fornecer mais informações, eu seria feliz ao tentar fornecer mais informações.Existem muitos livros excelentes sobre o tema também.

Jacó

Lembre -se de que não é necessário que exista uma função de avaliação decente. Para esta afirmação, presumo que uma função de avaliação deve ser de baixa complexidade (P).

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow