Construire un bot NetHack: l'analyse bayésienne est-elle une bonne stratégie?

Question

Un de mes amis commence à construire un bot NetHack (un bot qui joue au jeu Roguelike: NetHack). Il y a un très bon bot qui fonctionne pour le même jeu Angband, mais ça marche en partie à cause de la facilité de retourner en ville et d'être toujours capable d'écumer les niveaux bas pour gagner des objets.

En NetHack, le problème est beaucoup plus difficile, parce que le jeu récompense l'expérimentation ballsy et est construit essentiellement 1.000 cas de pointe.

Récemment, je a suggéré d'utiliser une sorte d'analyse bayésienne naïve, dans beaucoup de la même façon le spam est créé. Fondamentalement, le bot devait d'abord construire un corpus, en essayant toutes les actions possibles avec chaque objet ou créature qu'il trouve et en stockant cette information avec, par exemple, à quel point il était proche d'un décès, une blessure d'effet négatif. Au fil du temps, il semble que vous pourriez générer un modèle raisonnablement jouable.

Quelqu'un peut-il nous diriger dans la bonne direction de ce que serait un bon départ? Suis-je aboyant le mauvais arbre ou mal compris l'idée de l'analyse bayésienne?

Modifier: Mon ami a mis en place un github repo of his NetHack patch qui permet les liaisons python. Il est toujours dans un état assez primitif, mais si quelqu'un est intéressé ...

Answer 1

Bien que l'analyse bayésienne englobe beaucoup plus, l'algorithme Naive Bayes bien connu de filtres anti-spam est basé sur une hypothèse fondamentale: toutes les variables sont essentiellement indépendantes les unes des autres. Par exemple, dans le filtrage du spam, chaque mot est généralement traité comme une variable, ce qui signifie que si le courriel contient le mot «viagra», cette connaissance affecte la probabilité qu'il contienne aussi le mot «médecine» (ou «foo» 'ou' spam 'ou autre chose). Ce qui est intéressant, c'est que cette hypothèse est manifestement fausse quand il s'agit de langage naturel, mais parvient toujours à produire des résultats raisonnables.Maintenant, les gens peuvent parfois contourner l'hypothèse d'indépendance en définissant des variables qui sont techniquement des combinaisons de choses (comme la recherche du jeton 'buy viagra'). Cela peut fonctionner si vous connaissez des cas spécifiques à rechercher, mais en général, dans un environnement de jeu, cela signifie que vous ne pouvez généralement pas vous souvenir de quoi que ce soit. Donc, chaque fois que vous devez vous déplacer, effectuer une action, etc., c'est complètement indépendant de tout ce que vous avez fait jusqu'à présent. Je dirais que même pour les jeux les plus simples, c'est un moyen très inefficace d'apprendre le jeu.

Je suggérerais d'utiliser plutôt q-learning. La plupart des exemples que vous trouverez sont généralement de simples jeux simples (comme apprendre à naviguer sur une carte tout en évitant les murs, les pièges, les monstres, etc.). L'apprentissage par renforcement est un type d'apprentissage en ligne non supervisé qui fonctionne très bien dans des situations qui peuvent être modélisées comme un agent interagissant avec un environnement, comme un jeu (ou des robots). Il essaie de comprendre quelle est l'action optimale à chaque état de l'environnement (où chaque état peut inclure autant de variables que nécessaire, bien plus que simplement «où suis-je»). L'astuce consiste alors à maintenir juste assez d'état pour aider le bot à prendre de bonnes décisions sans avoir un point distinct dans l'espace de votre état pour chaque combinaison possible d'actions précédentes. En termes plus concrets, si vous deviez construire un bot d'échecs, vous auriez probablement des problèmes si vous essayiez de créer une politique de décision qui prendrait des décisions basées sur tous les mouvements précédents, depuis l'ensemble des combinaisons possibles d'échecs. Les mouvements se développent très rapidement. Même un modèle plus simple d'où chaque pièce est sur le tableau est toujours un très grand espace d'état, donc vous devez trouver un moyen de simplifier ce que vous gardez la trace. Mais remarquez que vous gardez une trace de l'état de sorte que votre bot ne continue pas à essayer de créer un terme à gauche dans un mur encore et encore.

Le wikipedia article est assez lourd de jargon mais ce tutorial fait un bien meilleur travail en traduisant les concepts en exemples concrets. Le seul hic, c'est que vous devez être en mesure de définir des récompenses pour fournir le «renforcement» positif. C'est-à-dire que vous devez être en mesure de définir les états que le robot essaie d'atteindre, sinon il continuera juste pour toujours.

Answer 2

Dans nethack actions inconnues ont généralement un effet booléen - soit vous gagnez ou vous perdez. Les réseaux bayésiens s'appuient sur des valeurs de «logique floue» - une action peut donner un gain avec une probabilité donnée. Par conséquent, vous n'avez pas besoin d'un réseau bayésien, juste une liste des "effets découverts" et qu'ils soient bons ou mauvais.

Pas besoin de manger la Cockatrice à nouveau, n'est-ce pas? Dans l'ensemble, tout dépend de la «connaissance» que l'on veut donner au bot en tant que starter. Voulez-vous qu'il apprenne tout "à la dure", ou allez-vous le nourrir spoilers jusqu'à ce qu'il soit bourré?

Answer 3

Il existe un précédent: le monstrueux programme Rog-o-matic a réussi à jouer voyous et même retourné avec l'amulette de Yendor quelques fois. Malheureusement, Rogue n'était sorti que d'un binaire, pas de source, donc il est mort (sauf si vous pouvez installer un système BSD 4.3 sur un MicroVAX), laissant rog-o-matic incapable de jouer l'un des clones. Il se bloque parce qu'ils ne sont pas assez proches des émulations.

Cependant, rog-o-matic est, je pense, mon programme préféré de tous les temps, non seulement en raison de ses performances mais aussi grâce à la lisibilité du code et à l'intelligence compréhensible de ses algorithmes. Il a utilisé "l'héritage génétique": un nouveau joueur hériterait d'une combinaison de préférences d'une précédente paire de joueurs réussies, avec un certain décalage aléatoire, puis serait opposé à la machine. Les préférences les plus réussies migreraient dans le pool génétique et les moins réussies.

La source peut être difficile de trouver ces jours-ci, mais la recherche « rogomatic » vous mettre sur le chemin.

Answer 4

Je doute que l'analyse bayésienne vous mènera loin car la plupart de NetHack est hautement contextuelle. Il y a très peu d'actions qui sont toujours une mauvaise idée; la plupart sont également des sauveteurs dans la «bonne» situation (un exemple extrême est de manger un cockatrice: c'est mauvais, sauf si vous êtes affamé et actuellement polymorphisé en un monstre résistant aux pierres, auquel cas manger le cockatrice est la bonne chose à faire). Certaines de ces actions "presque mauvaises" sont nécessaires pour gagner le jeu (par exemple monter les escaliers au niveau 1, ou tomber délibérément dans des pièges pour atteindre Gehennom).

Ce que vous pourriez essayer serait d'essayer de le faire au niveau "méta". Concevoir le bot comme choisissant au hasard parmi une variété de «comportements élémentaires». Ensuite, essayez de mesurer comment ces robots gagnent. Puis extraire les combinaisons de comportements qui semblent favoriser la survie; l'analyse bayésienne pourrait faire cela parmi un large corpus de jeux avec leur «niveau de succès». Par exemple, s'il y a des comportements «ramasser des dagues» et «éviter d'engager des monstres dans la mêlée», je suppose que l'analyse montrerait que ces deux comportements vont bien ensemble: les robots qui choisissent les dagues sans les utiliser, et les bots lancer des missiles sur des monstres sans ramasser de tels missiles, sera probablement pire. Cela imite en quelque sorte ce que les joueurs d'apprentissage demandent souvent dans rec.games.roguelike.nethack. La plupart des questions sont similaires à: "Devrais-je boire des potions inconnues pour les identifier?" ou "quel niveau devrait être mon personnage avant d'aller aussi loin dans le donjon?". Les réponses à ces questions dépendent fortement de ce que le joueur fait d'autre, et il n'y a pas de bonne réponse absolue.

Un point difficile ici est de savoir comment mesurer le succès à la survie. Si vous essayez simplement de maximiser le temps passé avant de mourir, alors vous favoriserez les bots qui ne quittent jamais les premiers niveaux; ceux-ci peuvent vivre longtemps mais ne gagneront jamais la partie. Si vous mesurez le succès en fonction de la profondeur du personnage avant de mourir, alors les meilleurs bots seront des archéologues (qui commencent avec une pioche) dans une frénésie de fouille.

Answer 5

Apparemment, il existe un bon nombre de robots Nethack. Check out this listing: