Construire un robot NetHack: analyse bayésienne est une bonne stratégie?

Question

Un de mes amis commence à construire un bot NetHack (un bot qui joue le jeu Roguelike: NetHack). Il y a un très bon bot de travail pour le Angband de jeu similaire, mais cela fonctionne en partie à cause de la facilité à retourner à la ville et toujours être en mesure d'écume bas niveaux 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 comme 1000 cas limite.

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 serait d'abord construire un corpus, en essayant toutes les actions possibles avec chaque élément ou de la créature qu'il trouve et stocker cette information avec, par exemple, la proximité de la mort, des blessures de l'effet négatif était. Au fil du temps, il semble que vous pouvez générer un modèle raisonnablement jouable.

Quelqu'un peut-il nous indiquer la bonne direction de ce qu'est un bon point de départ serait? Suis-je aboiements le mauvais arbre ou l'incompréhension de l'idée de l'analyse bayésienne?

Modifier Mon ami a mis en place href="http://github.com/BenSmith/NetHack343/tree/python-ubuntu" rel="noreferrer"> github un qui permet des liaisons de 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. Ainsi, par exemple, dans le filtre anti-spams chaque mot est généralement considéré comme une variable si cela signifie en supposant que si le message contient le mot « viagra », cette connaissance n'a aucune incidence sur la probabilité qu'il contiendra aussi le mot « médecine » (ou « foo »ou « spam » ou quoi que ce soit d'autre). La chose intéressante est que cette hypothèse est tout à fait évidemment faux en matière de langage naturel, mais parvient toujours à produire des résultats raisonnables.

une façon dont les gens se parfois autour de l'hypothèse de l'indépendance est de définir des variables qui sont techniquement combinaisons de choses (comme la recherche du jeton 'acheter viagra). Cela peut fonctionner si vous connaissez des cas particuliers à rechercher, mais en général, dans un environnement de jeu, cela signifie que vous ne me souviens pas en général rien. Donc, chaque fois que vous devez déplacer, effectuer une action, etc., son tout à fait indépendant de tout ce que vous avez fait jusqu'à présent. Je dirais même pour les jeux les plus simples, c'est une façon très inefficace d'aller sur l'apprentissage du jeu.

Je suggère à la recherche en utilisant q-apprentissage à la place. La plupart des exemples que vous trouverez sont habituellement juste des jeux simples de toute façon (comme apprendre à naviguer dans une carte tout en évitant les murs, les pièges, monstres, etc.). Le renforcement de l'apprentissage est un type d'apprentissage non supervisé en ligne qui fait vraiment bien dans des situations qui peuvent être modélisés comme agent d'interaction avec un environnement, comme un jeu (ou robots). Elle le fait d'essayer de comprendre ce que l'action optimale est à chaque état dans l'environnement (où chaque état peut inclure autant de variables que nécessaire, bien plus que « Où suis-je »). L'astuce est alors maintenir juste assez état qui aide le bot prendre de bonnes décisions sans avoir un point distinct dans votre état « espace » pour toutes les combinaisons possibles des actions précédentes.

Pour mettre cela en des termes plus concrets, si vous deviez construire un robot d'échecs que vous auriez probablement du mal si vous avez essayé de créer une politique de décision qui a pris des décisions en fonction de tous les mouvements précédents depuis l'ensemble de toutes les combinaisons possibles de mouvements d'échecs croît très rapidement. Même un modèle plus simple où chaque pièce est sur la carte est encore un espace d'état très grand, donc vous devez trouver un moyen de simplifier ce que vous garder la trace. Mais remarquez que vous ne recevez pas de garder une trace d'un état afin que votre robot ne se contente pas de continuer à essayer de faire un terme à gauche dans un mur encore et encore.

Le article est assez lourd jargon mais

Answer 2

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, voyous n'a été libéré d'un binaire, pas à la source, il est mort (à moins que vous pouvez mettre en place un système 4.3BSD sur un MicroVAX), laissant Rog-o-matic est incapable de jouer l'un des clones. Il se bloque juste cos ils sont pas assez près émulations.

Cependant, Rog-o-matic est, je pense, mon programme préféré de tous les temps, non seulement à cause de ce qu'il a réalisé, mais en raison de la lisibilité du code et l'intelligence compréhensible de ses algorithmes. Il fut « l'héritage génétique »: un nouveau joueur hérite d'une combinaison de préférences d'une paire précédente de joueurs réussis, avec un certain décalage aléatoire, alors dénoyautées contre la machine. préférences plus de succès migraient dans le pool génétique et les moins réussies vers le bas.

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

Je doute analyse bayésienne vous obtenez bien parce que la plupart des NetHack est très contextuel. Il y a très peu d'actions qui sont toujours une mauvaise idée; la plupart sont aussi sauver la vie dans la situation « droit » (un exemple extrême est de manger une vipère: qui est mauvais, à moins que vous mourir de faim et actuellement métamorphosé en un monstre résistant à la pierre, auquel cas manger le cockatrice est la bonne chose à faire ). Certains de ces « presque mauvais » des actions sont nécessaires pour gagner le jeu (par exemple monter l'escalier au niveau 1, ou de tomber dans des pièges délibérément pour atteindre Gehennom).

Qu'est-ce que vous pourriez essayer serait d'essayer de le faire au niveau « méta ». Concevoir le bot comme le choix au hasard parmi une variété de comportements « élémentaires ». Ensuite, essayez de mesurer à quel point ces robots tirent. extraire ensuite les combinaisons de comportements qui semblent favoriser la survie; analyse bayésienne pourrait faire partie d'un vaste corpus de jeux le long de leur « niveau de succès ». Par exemple, s'il y a des comportements « ramasser des poignards » et « éviter des monstres engageant dans la mêlée », je suppose que l'analyse montrerait que ces deux comportements vont bien ensemble: les robots qui ramassent des poignards sans les utiliser, et les robots qui tentent de jeter des missiles sur des monstres sans recueillir de tels missiles, s'en trouvera probablement pire.

en quelque sorte imite ce que les joueurs d'apprentissage demandent souvent dans rec.games.roguelike.nethack. La plupart des questions sont similaires à: « dois-je boire des potions inconnues pour les identifier? » ou « quel niveau devrait être mon personnage avant d'aller que profondément dans le donjon? ». Les réponses à ces questions dépendent fortement de quoi d'autre le joueur est en train de faire, et il n'y a pas de bonne réponse absolue.

Un point difficile est ici comment mesurer le succès à la survie. Si vous essayez simplement de maximiser le temps passé avant de mourir, alors vous privilégiera les robots qui ne quittent jamais les premiers niveaux; ceux-ci peuvent vivre longtemps, mais ne sera jamais gagner le match. Si vous mesurez le succès par la profondeur du personnage va avant de mourir alors les meilleurs robots seront (qui commencent les archéologues avec une pioche) dans une frénésie de creuser.

Apparemment, il y a un bon nombre de Nethack bots là-bas. Consultez cette annonce:

Dans nethack actions inconnues ont généralement un effet booléen - soit vous gagnez ou vous perdez. base de réseaux bayésiens autour de valeurs « 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 wether ils sont bons ou mauvais.

Pas besoin de manger à nouveau le Cocatrix, est-il?

Dans tout dépend combien la « connaissance » que vous voulez donner le bot comme entrées. Voulez-vous lui apprendre tout « à la dure », ou allez-vous le nourrir spoilers « jusqu'à ce qu'il est 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, voyous n'a été libéré d'un binaire, pas à la source, il est mort (à moins que vous pouvez mettre en place un système 4.3BSD sur un MicroVAX), laissant Rog-o-matic est incapable de jouer l'un des clones. Il se bloque juste cos ils sont pas assez près émulations.

Cependant, Rog-o-matic est, je pense, mon programme préféré de tous les temps, non seulement à cause de ce qu'il a réalisé, mais en raison de la lisibilité du code et l'intelligence compréhensible de ses algorithmes. Il fut « l'héritage génétique »: un nouveau joueur hérite d'une combinaison de préférences d'une paire précédente de joueurs réussis, avec un certain décalage aléatoire, alors dénoyautées contre la machine. préférences plus de succès migraient dans le pool génétique et les moins réussies vers le bas.

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

Answer 4

Je doute analyse bayésienne vous obtenez bien parce que la plupart des NetHack est très contextuel. Il y a très peu d'actions qui sont toujours une mauvaise idée; la plupart sont aussi sauver la vie dans la situation « droit » (un exemple extrême est de manger une vipère: qui est mauvais, à moins que vous mourir de faim et actuellement métamorphosé en un monstre résistant à la pierre, auquel cas manger le cockatrice est la bonne chose à faire ). Certains de ces « presque mauvais » des actions sont nécessaires pour gagner le jeu (par exemple monter l'escalier au niveau 1, ou de tomber dans des pièges délibérément pour atteindre Gehennom).

Qu'est-ce que vous pourriez essayer serait d'essayer de le faire au niveau « méta ». Concevoir le bot comme le choix au hasard parmi une variété de comportements « élémentaires ». Ensuite, essayez de mesurer à quel point ces robots tirent. extraire ensuite les combinaisons de comportements qui semblent favoriser la survie; analyse bayésienne pourrait faire partie d'un vaste corpus de jeux le long de leur « niveau de succès ». Par exemple, s'il y a des comportements « ramasser des poignards » et « éviter des monstres engageant dans la mêlée », je suppose que l'analyse montrerait que ces deux comportements vont bien ensemble: les robots qui ramassent des poignards sans les utiliser, et les robots qui tentent de jeter des missiles sur des monstres sans recueillir de tels missiles, s'en trouvera probablement pire.

en quelque sorte imite ce que les joueurs d'apprentissage demandent souvent dans rec.games.roguelike.nethack. La plupart des questions sont similaires à: « dois-je boire des potions inconnues pour les identifier? » ou « quel niveau devrait être mon personnage avant d'aller que profondément dans le donjon? ». Les réponses à ces questions dépendent fortement de quoi d'autre le joueur est en train de faire, et il n'y a pas de bonne réponse absolue.

Un point difficile est ici comment mesurer le succès à la survie. Si vous essayez simplement de maximiser le temps passé avant de mourir, alors vous privilégiera les robots qui ne quittent jamais les premiers niveaux; ceux-ci peuvent vivre longtemps, mais ne sera jamais gagner le match. Si vous mesurez le succès par la profondeur du personnage va avant de mourir alors les meilleurs robots seront (qui commencent les archéologues avec une pioche) dans une frénésie de creuser.

Answer 5

Apparemment, il y a un bon nombre de Nethack bots là-bas. Consultez cette annonce:

Answer 6

Dans nethack actions inconnues ont généralement un effet booléen - soit vous gagnez ou vous perdez. base de réseaux bayésiens autour de valeurs « 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 wether ils sont bons ou mauvais.

Pas besoin de manger à nouveau le Cocatrix, est-il?

Dans tout dépend combien la « connaissance » que vous voulez donner le bot comme entrées. Voulez-vous lui apprendre tout « à la dure », ou allez-vous le nourrir spoilers « jusqu'à ce qu'il est bourré?