Eu tenho jogado com um algoritmo que aprende a jogar tictactoe. O pseudocódigo básico é:
repeat many thousand times {
repeat until game is over {
if(board layout is unknown or exploring) {
move randomly
} else {
move in location which historically gives highest reward
}
}
for each step in the game {
determine board layout for current step
if(board layout is unknown) {
add board layout to memory
}
update reward for board layout based on game outcome
}
}
now play a human and win :-)
Exploração: no início, o algoritmo explora agressivamente, e isso reduz linearmente. Depois de dizer mil jogos, ele explora apenas 10% dos movimentos. Todos os outros movimentos são baseados na exploração de recompensas anteriores.
Recompensas: se o jogo resultou em vitória, conceda 10 pontos. Se o jogo resultou em empate, 0 pontos, caso contrário, -5 pontos. Na verdade, essas recompensas podem ser "ajustadas", de modo que, se o jogo foi mais curto e venceu, conceda mais pontos ou, se for mais longo, conceda menos pontos. Dessa forma, o algoritmo prefere ganhar rapidamente. Isso significa que aprende a vencer o mais rápido possível, em vez de tentar vencer mais tarde. Isso é importante para que ele não perca a vitória imediatamente - se ele perdesse tal jogada, o oponente provavelmente a) se mudaria para lá para evitar que a IA vencesse da próxima vez eb) achasse que o algoritmo era estúpido porque perdeu uma "óbvia". " ganhar.
Esse algoritmo realmente aprende, para que eu possa classificá-lo como um algoritmo de aprendizado de maching.
Eu acho, mas não tenho certeza, que é um algoritmo de aprendizado reforçado. No entanto, de acordo com https://www.cse.unsw.edu.au/~cs9417ml/RL1/tdlearning.html , não se trata de aprendizado de diferenças temporais, porque não estima as recompensas até o final, e deve estar estimando a recompensa à medida que avança. Isso pode significar que não é um aprendizado reforçado.
Pergunta 1: Posso argumentar com sucesso que estou estimando a recompensa com base na história e ainda afirmar que o algoritmo é um aprendizado reforçado ou mesmo um Q-learning?
Pergunta 2: Se eu substituir a pesquisa de recompensa que é baseada no layout da placa, por uma rede neural, onde o layout da placa é a entrada e a recompensa é a saída, o algoritmo poderia ser considerado um aprendizado de reforço profundo?
Pergunta 3: Eu não acho que tenho uma taxa de aprendizado ou um fator de desconto. Isso é importante?
Percebi que o algoritmo é bastante inútil, a menos que eu o treine com pelo menos todos os movimentos que um oponente tente. Então, de certa forma, parece que estamos usando força bruta em vez de realmente "aprender". Isso me faz questionar se o tictacto de aprendizado de máquina é realmente um aprendizado. Concordo que o uso de uma rede neural para aprender o reconhecimento de imagem pode ser classificado como aprendizado porque, quando vê uma imagem desconhecida, é capaz de declarar sua classificação. Mas isso é bastante inútil para jogos como o tictactoe, onde layouts semelhantes de painéis de aparência não são totalmente relacionados (um pode levar a uma vitória, o outro pode levar a uma perda). Assim...
Pergunta 4: Os algoritmos de tictacto podem ser classificados como aprendizado real e não como força bruta?
Atualização: em relação às recompensas ... quando o algoritmo está decidindo para onde ir, calcula a recompensa para cada posição da seguinte maneira:
var total = winRewards + drawRewards + lossRewards;
move.reward = (100*(winRewards/total)) + (10*(drawRewards/total)) + (-1*(lossRewards/total));
Eu divido pelo número total de pontos (para cada jogada), porque, caso contrário, parece aprender que um lugar é GRANDE e não dá chance aos outros. Dessa forma, calculamos a proporção de vitórias, independentemente da frequência com que elas foram jogadas. É normalizado em comparação com os outros.
O código está disponível aqui: https://github.com/maxant/tictactoe/blob/master/ai.js
ATUALIZAÇÃO # 2: Desde então, descobri que esse algoritmo não pode ser classificado como força bruta, porque na verdade ele não aprende muitos jogos antes de se tornar um especialista. Detalhes aqui: http://blog.maxant.co.uk/pebble/2018/04/11/1523468336936.html
fonte
Parabéns por descobrir um algoritmo de jogo do jogo da velha!
Primeiras coisas primeiro, isso definitivamente não é Q-learning.
No entanto, acho que é classificado como Aprendizado por Reforço. Você implementou estes componentes principais do RL:
Um estado (a placa atual), usada como entrada em cada etapa.
Uma ação (próxima disposição da placa desejada), usada como saída. Quando a ação é efetivamente escolher o próximo estado diretamente, isso às vezes é chamado de representação pós-estado. É comumente usado em RL para jogos determinísticos.
Recompensas geradas pelo ambiente, onde o objetivo do agente é maximizar a recompensa esperada.
Um algoritmo que pode obter dados sobre estados, ações e recompensas e aprender a otimizar a recompensa esperada através da aquisição de experiência no ambiente.
Seu algoritmo é o IMO mais próximo do Monte Carlo Control , que é uma abordagem RL padrão.
Uma das grandes vantagens do Q Learning é que ele aprende uma política ideal mesmo enquanto explora - isso é conhecido como aprendizado fora da política , enquanto seu algoritmo está dentro da política, ou seja, aprende sobre os valores de como está se comportando atualmente. É por isso que você precisa reduzir a taxa de exploração ao longo do tempo - e isso pode ser um problema, porque o cronograma da taxa de exploração é um hiperparâmetro do seu algoritmo de aprendizado que pode precisar de ajustes cuidadosos.
Sim, suponho que seria tecnicamente. No entanto, é improvável que se dimensione bem a problemas mais complexos apenas com a adição de uma rede neural para estimar valores de ação, a menos que você inclua alguns dos elementos mais sofisticados, como o uso de aprendizado de diferença temporal ou gradientes de políticas.
Um fator de desconto não é importante para problemas episódicos. Isso é necessário apenas para problemas contínuos, nos quais você precisa ter algum tipo de horizonte temporal, caso contrário, a recompensa prevista seria infinita (embora você também possa substituir o mecanismo de desconto por uma abordagem de recompensa média na prática).
A taxa de aprendizado é uma omissão importante. Você não explica o que tem em seu lugar. Você colocou
update reward for board layout based on game outcome
- essa etapa de atualização normalmente possui a taxa de aprendizado. No entanto, para o jogo da velha e o Q-Learning, você pode realmente definir a taxa de aprendizado para 1,0, o que eu acho que é o mesmo que a sua abordagem, e funciona. Eu escrevi um código de exemplo que faz exatamente isso - veja esta linha que define a taxa de aprendizado para 1,0 . No entanto, cenários mais complexos, especialmente em ambientes não determinísticos, aprenderiam mal com uma taxa de aprendizado tão alta.Seu algoritmo definitivamente está aprendendo algo com a experiência, embora ineficientemente comparado a um humano. Muitos dos algoritmos de RL mais básicos têm problemas semelhantes e geralmente precisam ver cada estado possível de um sistema várias vezes antes de convergir para uma resposta.
Eu diria que uma busca exaustiva da árvore na posição atual durante o jogo foi "força bruta". Em um jogo simples como o tictactoe, isso provavelmente é mais eficiente que o RL. No entanto, à medida que os jogos se tornam cada vez mais sofisticados, a abordagem de aprendizado de máquina se torna competitiva com a pesquisa. Geralmente, RL e alguma forma de pesquisa são usadas juntas.
fonte