Algumas dúvidas sobre a aplicação do aprendizado por reforço em jogos como xadrez

9

Eu inventei um jogo de tabuleiro semelhante ao xadrez. Eu construí um mecanismo para que ele possa funcionar de forma autônoma. O mecanismo é basicamente uma árvore de decisão. É composta por:

  1. Uma função de pesquisa que em cada nó encontra todos os movimentos legais possíveis
  2. Uma função de avaliação que atribui um valor numérico à posição do tabuleiro (positivo significa que o primeiro jogador está ganhando vantagem, negativo significa que o segundo jogador está ganhando)
  3. Um algoritmo de negamax de poda de alphabeta

O principal problema desse mecanismo é que a otimização da função de avaliação é realmente complicada. Não sei quais fatores considerar e quais pesos colocar. A única maneira que vejo para melhorar o mecanismo é repetir os jogos, tentando cada vez diferentes combinações de fatores e pesos. No entanto, computacionalmente, parece um feito muito difícil (posso retropropagar sem usar o deeplearning?).

Eu gostaria de usar o aprendizado por reforço para melhorar o mecanismo jogando contra ele mesmo. Eu tenho lido sobre o assunto, mas ainda estou bastante confuso.

Que outra recompensa existe em um jogo como parte da produção ganha ou perde (1 ou 0)? Se eu usar outras recompensas, como a saída da função de avaliação a cada turno, como implementá-la? Como modifico a função de avaliação para oferecer melhores iterações de recompensas após a iteração?

Pigna
fonte

Respostas:

6

Eu gostaria de usar o aprendizado por reforço para melhorar o mecanismo jogando contra ele mesmo. Eu tenho lido sobre o tópico, mas ainda estou bastante confuso.

Esteja avisado: o aprendizado por reforço é um assunto grande e complexo. Embora você possa desviá-lo dos bots para jogar, você pode estudar os conceitos básicos de RL. Um bom lugar para começar é Sutton & Barto Reinforcement Learning: Uma Introdução

Que outra recompensa existe em um jogo como parte da produção ganha ou perde (1 ou 0)?

Dependendo do seu jogo, geralmente é isso. Na verdade, para um jogo de ganhar / empatar / perder como xadrez, a recompensa de cada ação é 0, exceto por vencer (+1) ou perder (-1) no final. Em um jogo de soma zero, isso se alinha perfeitamente com o mínimo, a poda alfabética etc.

O aprendizado por reforço destina-se a abordar ambientes com recompensas atrasadas. Adicionar recompensas "auxiliares" para não-metas provisórias geralmente é contraproducente.

Se eu usar outras recompensas, como a saída da função de avaliação a cada turno, como implementá-la?

Normalmente você não. O que a aplicação de RL de reprodução automática fará é aprender uma função de retorno (às vezes chamada de utilitário ) que prevê a expectativa de sua recompensa total de + 1/0 / -1 até o final do jogo. Você usaria isso no lugar de sua heurística atual para pesquisa minimax. Ou, potencialmente, você ajustaria sua função heurística atual para produzir na mesma faixa e usaria RL para otimizar seus pesos para fazer a melhor aproximação à verdadeira função de retorno de reprodução ideal (que provavelmente é muito complexa para calcular exatamente).

Como modifico a função de avaliação para oferecer melhores iterações de recompensas após a iteração?

É isso que as diferentes RL abordam todas as tentativas de fazer; há uma variedade de solucionadores diferentes. Não há uma maneira curta de explicar isso. Você pode começar com um método simples, como o Q-Learning . O Q-Learning aprende estimativas de Q (s, a) (chamado de valor da ação), que é o retorno esperado quando no estado s e tomando a ação a, e depois seguindo uma política ótima. Ele faz um palpite arbitrário para começar e o refina mais próximo do valor real a cada passo dado no ambiente de aprendizado. Os alunos com Q-tabular simples fazem esse refinamento simplesmente armazenando uma grande tabela de todos os estados e ações com a melhor estimativa até o momento do valor verdadeiro e calculando a média de cada nova estimativa, conforme é experimentada.

Também é possível combinar um método RL para heurística com a pesquisa minimax antecipada - foi o que o AlphaGo original fez e o que o AlphaGo Zero faz durante o treinamento. Essa é uma abordagem poderosa, porque a pesquisa minimax funcionará para verificar novamente as heurísticas geradas por RL. Embora para jogos simples o suficiente, o RL possa aprender heurísticas perfeitas e você só precisará de pesquisa local (qual deve ser a próxima jogada).

A menos que seu jogo seja muito simples (todos os estados possíveis caberiam na memória), você precisará de algum tipo de aproximação de função dentro do algoritmo RL. Redes neurais são uma escolha padrão. Ter algo para essa parte é inevitável - embora outra boa opção seja definir vários recursos de proxy (que você pode usar para construir uma heurística manualmente) e usar um aproximador linear - apenas uma soma ponderada de todos os recursos. Isso pode funcionar bem o suficiente e tem sido usado, por exemplo, em damas (rascunhos) jogadores treinados usando RL.

De fato, desde que sua própria função heurística não seja muito incomum, você provavelmente poderá tratá-la como uma aproximação linear e usar RL para aprender os melhores pesos para ela.

Neil Slater
fonte
"O aprendizado por reforço destina-se a abordar ambientes com recompensas atrasadas. A adição de recompensas" auxiliares "para não-metas provisórias geralmente é contraproducente". Gostaria de observar que existe um artigo que tenta resolver o problema de recompensas esparsas, introduzindo metas intermediárias " Hindsight Experience Replay ".
Nbro
11
@ nbro: Existem muitas tentativas de resolver recompensas esparsas, é uma grande questão em aberto na RL, uma maneira de aumentar o desafio de um problema é tornar as recompensas mais esparsas. Os traços de elegibilidade são outra tentativa, a RL hierárquica é outra área promissora. . . Eu não acho que eu quero adicionar estas técnicas para a resposta aqui, porém, como é mais sobre a viabilidade para o problema do OP e uma introdução ao assunto
Neil Slater