Construindo um bot NetHack:a análise bayesiana é uma boa estratégia?

Question

Um amigo meu está começando a construir um bot NetHack (um bot que joga o jogo Roguelike:NetHack).Existe um bot que funciona muito bem para o jogo semelhante Angband, mas funciona parcialmente pela facilidade de voltar para a cidade e sempre poder escalar níveis baixos para ganhar itens.

No NetHack, o problema é muito mais difícil, porque o jogo recompensa a experimentação corajosa e é construído basicamente como 1.000 casos extremos.

Recentemente sugeri usar algum tipo de análise bayesiana ingênua, da mesma forma que o spam é criado.

Basicamente, o bot construiria inicialmente um corpus, tentando todas as ações possíveis com cada item ou criatura que encontrasse e armazenando essas informações com, por exemplo, o quão próximo de uma morte, ferimento ou efeito negativo estava.Com o tempo, parece que você poderia gerar um modelo razoavelmente jogável.

Alguém pode nos indicar a direção certa sobre o que seria um bom começo?Estou latindo para a árvore errada ou entendendo mal a ideia da análise bayesiana?

Editar: Meu amigo colocou um repositório github de seu patch NetHack que permite ligações python.Ainda está em um estado bastante primitivo, mas se alguém estiver interessado...

Answer 1

Embora a análise bayesiana abranja muito mais, o algoritmo Naive Bayes, bem conhecido dos filtros de spam, é baseado em uma suposição fundamental:todas as variáveis ​​são essencialmente independentes umas das outras.Assim, por exemplo, na filtragem de spam, cada palavra é geralmente tratada como uma variável, o que significa assumir que se o e-mail contém a palavra 'viagra', esse conhecimento afeta a probabilidade de que também contenha a palavra 'remédio' (ou 'foo ' ou 'spam' ou qualquer outra coisa).O interessante é que essa suposição é obviamente falsa quando se trata de linguagem natural, mas ainda assim consegue produzir resultados razoáveis.

Agora, uma maneira pela qual as pessoas às vezes contornam a suposição de independência é definir variáveis ​​que são tecnicamente combinações de coisas (como pesquisar pelo token “comprar viagra”).Isso pode funcionar se você conhece casos específicos para procurar, mas em geral, em um ambiente de jogo, significa que geralmente você não consegue se lembrar de nada.Portanto, cada vez que você precisa se mover, realizar uma ação, etc., é completamente independente de qualquer outra coisa que você tenha feito até agora.Eu diria que mesmo para os jogos mais simples, esta é uma forma muito ineficiente de aprender o jogo.

Eu sugeriria usar o q-learning.A maioria dos exemplos que você encontrará geralmente são apenas jogos simples (como aprender a navegar em um mapa evitando paredes, armadilhas, monstros, etc.).A aprendizagem por reforço é um tipo de aprendizagem online não supervisionada que funciona muito bem em situações que podem ser modeladas como um agente interagindo com um ambiente, como um jogo (ou robôs).Ele faz isso tentando descobrir qual é a ação ideal em cada estado do ambiente (onde cada estado pode incluir quantas variáveis ​​forem necessárias, muito mais do que apenas “onde estou”).O truque então é manter o estado suficiente para ajudar o bot a tomar boas decisões sem ter um ponto distinto em seu 'espaço' de estado para cada combinação possível de ações anteriores.

Para colocar isso em termos mais concretos, se você construísse um robô de xadrez, provavelmente teria problemas se tentasse criar uma política de decisão que tomasse decisões com base em todos os movimentos anteriores, uma vez que o conjunto de todas as combinações possíveis de movimentos de xadrez cresce muito rapidamente .Mesmo um modelo mais simples de onde cada peça está no tabuleiro ainda é um espaço de estado muito grande, então você precisa encontrar uma maneira de simplificar o que você acompanha.Mas observe que você consegue acompanhar algum estado para que seu bot não fique apenas tentando transformar um termo esquerdo em uma parede repetidas vezes.

A Wikipédia artigo é um jargão bastante pesado, mas isso tutorial faz um trabalho muito melhor traduzindo os conceitos em exemplos do mundo real.

O único problema é que você precisa ser capaz de definir as recompensas a serem fornecidas como o 'reforço' positivo.Ou seja, você precisa ser capaz de definir os estados que o bot está tentando atingir, caso contrário, ele continuará para sempre.

Answer 2

Há precedentes: o monstruoso programa Rog-O-Matic conseguiu jogar Rogue e até voltou com o amuleto de Yendor algumas vezes. Infelizmente, o Rogue foi lançado apenas um binário, não fonte, por isso morreu (a menos que você possa configurar um sistema 4.3BSD em um Microvax), deixando Rog-o-Matic incapaz de tocar nenhum dos clones. Apenas fica pendurado porque eles não são emulações próximas o suficiente.

No entanto, o ROG-O-MATIC é, eu acho, meu programa favorito de todos os tempos, não apenas por causa do que alcançou, mas por causa da legibilidade do código e da inteligência compreensível de seus algoritmos. Ele usou "herança genética": um novo jogador herdaria uma combinação de preferências de um par anterior de jogadores de sucesso, com algum deslocamento aleatório e depois seria colocado contra a máquina. Preferências mais bem -sucedidas migrariam para o pool de genes e as menos bem -sucedidas para baixo.

A fonte pode ser difícil de encontrar hoje em dia, mas pesquisar "rogomáticos" o colocará no caminho.

Answer 3

Duvido que a análise bayesiana o leve longe porque a maior parte do Nethack é altamente contextual. Existem muito poucas ações que são sempre Uma má ideia; A maioria também economiza a vida na situação "certa" (um exemplo extremo é comer um cockatrice: isso é ruim, a menos que você esteja morrendo de fome e atualmente polimorfo em um monstro resistente a pedra; nesse caso, comer o cockatrice é a coisa certa a fazer ). Algumas dessas ações "quase ruins" são obrigadas a vencer o jogo (por exemplo, subindo as escadas no nível 1 ou deliberadamente caindo em armadilhas para chegar a Gehennom).

O que você poderia tentar seria tentar fazê -lo no nível "meta". Projete o bot como escolher aleatoriamente entre uma variedade de "comportamentos elementares". Em seguida, tente medir como esses bots se saem. Em seguida, extraia as combinações de comportamentos que parecem promover a sobrevivência; A análise bayesiana poderia fazer isso entre um amplo corpus de jogos, juntamente com seu "nível de sucesso". Por exemplo, se houver comportamentos "pegam punhais" e "evite envolver monstros em corpo a corpo", eu assumiria que a análise mostraria que esses dois comportamentos se encaixam bem: bots que colhem punhais sem usá -los e bots que tentam Jogue mísseis em monstros sem reunir esses mísseis, provavelmente se sairá pior.

De alguma forma, isso imita o que os jogadores de aprendizagem costumam pedir em rec.games.roguelike.nethack. A maioria das perguntas é semelhante a: "Devo beber poções desconhecidas para identificá -las?" ou "Que nível deve ser meu personagem antes de ir tão profundo na masmorra?". As respostas a essas perguntas dependem fortemente do que mais o jogador está fazendo, e não há uma boa resposta absoluta.

Um ponto difícil aqui é como medir o sucesso na sobrevivência. Se você simplesmente tentar maximizar o tempo gasto antes de morrer, favorecerá os bots que nunca deixarão os primeiros níveis; Esses podem viver muito, mas nunca ganharão o jogo. Se você medir o sucesso pela profundidade do personagem antes de morrer, os melhores robôs serão arqueólogos (que começam com um machado) em um frenesi de escavação.

Answer 4

Aparentemente, há um bom número de bots Nethack por aí. Confira esta lista:

Answer 5

Em Nethack, ações desconhecidas geralmente têm um efeito booleano - você ganha ou você perde. As redes bayesianas se baseiam em torno dos valores "lógicos difusos" - uma ação pode dar um ganho com uma determinada probabilidade. Portanto, você não precisa de uma rede bayesiana, apenas uma lista de "efeitos descobertos" e se eles são bons ou ruins.

Não há necessidade de comer o Cockatrice novamente, existe?

Em suma, depende de quanto "conhecimento" você deseja dar ao bot como entradas. Você quer que ele aprenda tudo "da maneira mais difícil", ou você vai alimentar spoilers dele até que ele esteja recheado?