Monte-Carlo de l'Arbre à la Recherche de l'UCT de mise en œuvre

Pouvez-vous m'expliquer comment construire l'arbre?

J'ai tout à fait compris comment les nœuds sont choisis, mais une belle explication serait vraiment m'aider à la mise en œuvre de cet algorithme. J'ai déjà un conseil représentant l'état de la partie, mais je ne sais pas (comprendre) comment générer l'arbre.

Quelqu'un peut-points-moi à bien commenté la mise en œuvre de l'algorithme (j'ai besoin de l'utiliser pour IA)? Ou mieux, des explications, des exemples?

Je n'ai pas trouvé beaucoup de ressources sur le net, cet algorithme est assez nouveau...

Implémentation C++: github.com/AdamStelmaszczyk/gtsa la divulgation Complète: je suis l'auteur.

InformationsquelleAutor Makers_F | 2012-01-29

24

Le meilleur moyen de générer de l'arbre est une série aléatoire de playouts. Le truc est d'être capable de trouver un équilibre entre l'exploration et de l'exploitation (c'est là que l'UCT est livré dans). Il y a quelques bons exemples de code et beaucoup de papier de recherche références ici : https://web.archive.org/web/20160308043415/http://mcts.ai:80/index.html

Quand j'ai implémenté l'algorithme, j'ai utilisé random playouts jusqu'à ce que j'ai touché un point de fin ou la résiliation de l'état. J'ai eu une statique de la fonction d'évaluation qui permettrait de calculer le gain à ce moment, le score de ce point est retournée en haut de l'arborescence. Chaque joueur ou équipe "" suppose que l'autre équipe va jouer le meilleur coup pour eux-mêmes, et le pire déplacer possible pour leur adversaire.

Je voudrais également vous recommandons de vérifier les papiers par Chaslot et sa thèse de doctorat, ainsi qu'une partie de la recherche qui fait référence à son travail (en fait, tous les SCTM de travail depuis).

Par exemple: 1 Joueur de la première mesure pourrait simuler 10 se déplace dans l'avenir, l'alternance entre le joueur 1 se déplace et le joueur 2 se déplace. Chaque fois que vous devez supposer que le joueur adverse va essayer de réduire votre score, tout en optimisant leur propre partition. Il y a tout un champ basé sur ce que la Théorie des jeux. Une fois que vous simuler à la fin des 10 jeux, vous itération de point de départ à nouveau (car il n'est point seulement en train de simuler un ensemble de décisions). Chacune de ces branches de l'arbre doit être marqué où le score est propagée haut de l'arbre et le score représente le meilleur possible récompense pour le joueur de faire la simulation en supposant que l'autre joueur est aussi de choisir les meilleurs coups pour eux-mêmes.

SCTM se compose de quatre étapes stratégiques, répété tant qu'il est temps de gauche. Les étapes sont comme suit.
1. Dans l'étape de sélection de l'arbre est parcouru de l'
  nœud racine jusqu'à ce que nous atteignons un nœud E, où nous avons sélectionner une position qui n'est pas ajouté à l'arbre encore.
2. Ensuite, pendant le play-out étape coups sont joués dans l'auto-jouer jusqu'à la fin du jeu est atteint. Le résultat R de cette “simulé” le jeu est de +1 en cas de victoire pour le Noir (le premier joueur en LOA), 0 en cas d'égalité, et -1 en cas d'une victoire pour le Blanc.
3. Par la suite, dans l'expansion de l'étape d'enfants de E sont ajoutés à l'arbre.
4. Enfin, R est propagée le long du chemin de E à la racine le nœud dans le les pas. Lorsque le temps est écoulé, le coup joué par le programme est l'enfant de la racine avec la valeur la plus élevée.
  (Cet exemple est tiré de ce livre - PDF
http://www.ru.is/faculty/yngvi/pdf/WinandsBS08.pdf

Voici quelques implémentations:

Une liste des bibliothèques et des jeux à l'aide de certains des SCTM implémentations
http://senseis.xmp.net/?MonteCarloTreeSearch

et un jeu indépendant open source UCT des SCTM de la bibliothèque appelée Fuego
http://fuego.sourceforge.net/fuego-doc-1.1/smartgame-doc/group__sguctgroup.html
- C'est assez clair. Mais l'arbre est construit, tandis que la prise de décision, ou est-il construire avant, et puis l'IA utilise pour déterminer le droit de se déplacer? Pouvez-vous écrire point par point depuis le début (rien dans la mémoire) pour le déplacer vers la droite décision les étapes de l'algorithme?
- Généralement, l'arbre est construit tout en faisant une série de simulation de décisions, et puis le "réel" jouer par est faite sur la base de ces décisions antérieures. Un moyen facile de le faire est d'avoir une méthode qui permet de stocker l'état du jeu - je remarque que vous avez déjà présent, puis un montant de x fois (cela dépend sur combien de temps de calcul que vous avez, ou la qualité de ses choix), puis de restaurer le jeu initial de l'état vous simulées à partir et à faire un choix à partir de là, en utilisant le construit et a marqué l'arbre.
- J'ai aussi mis ma réponse avec les principales étapes de la SCTM et un lien
- J'ai besoin de l'exécuter sur un appareil mobile (lire: pas beaucoup de mémoire, pas de fast cpu). Alors j'ai pensé à lancer plusieurs simulations sur mon pc, sauver l'arbre(légèrement modifié) dans un fichier, et dans mon appli de mettre en œuvre une méthode qui peut facilement lire le fichier enregistré (modifié afin d'être plus facilement lisible sans le charger tous en mémoire).[si je ne suis pas d'enregistrer les modifications apportées au fichier] je vais perdre la partie d'apprentissage de l'informatique (depuis les matches, les vrai joueur ne ne pas mettre à jour l'arbre), mais je vais obtenir une assez bonne ia pour peu de frais. Ce droit est-il/est-elle réalisable?
- Dépend de la taille de l'arborescence possible. Même un tic-tac-toe jeu peut avoir un surprenant jeu de l'arbre et vous serait essentiellement le brute force tous les coups possibles. Cela prendrait une éternité pour quelque chose comme les échecs. Une mise en œuvre possible serait de mettre en place un serveur de l'exécution d'un service en fonction des SCTM de la mise en œuvre. Trouvé! Voici quelques implémentations existantes: senseis.xmp.net/?MonteCarloTreeSearch et un jeu indépendant de l'UCT des SCTM de la bibliothèque appelée Fuego fuego.sourceforge.net/fuego-doc-1.1/smartgame-doc/...
- Je suis un étudiant, je n'ai pas d'argent pour mettre en place un serveur 😉 En outre, l'utilisateur devra toujours être en ligne pour jouer. Si le jeu va très bien, je peux envisagez d'ajouter une nouvelle catégorie. Btw, mon jeu n'a pas trop de membres(juste n_playern_total_element), cela signifie que dans une situation comme 210 (dans mon jeu, ce n'est pas si restrictif), si je construis dans une manière intelligente de l'arbre (pas de nœuds dupliqués) je vais avoir 1024 nœuds représentant tous les états possibles. Ce n'est pas tellement. En outre, je ne pense pas que je vais jamais atteindre 315 = 14,34 M états, 312 = 0,5 M est vraiment acceptable
- Cela devrait fonctionner assez bien, bonne chance 🙂
- j'ai fait une "petite" erreur: chaque élément a beaucoup plus de membres que ce que je pensais, donc certainement la construction d'une arborescence complète est impossible. Je vais m'en tenir à la norme des sctm. Puis-je faire durer quelques questions au sujet de centre des sctm.ai/?q=code/simple_java ? Pourquoi nAction statique et = 5? D'où l'algorithme de demander à mon conseil pour le possible déménagement ou la déplacer vers la droite pour le faire? Ce qui devrait revenir déploiement(TreeNode tn)? Merci beaucoup!
- Le Déploiement de la méthode est l'endroit où vous jouez votre jeu, nActions est le nombre de nœuds enfants de créer et d'ajouter à un nœud existant.
- combien de nœuds enfants à créer = possible (intelligent) passer de l'état actuel?
- Je ne comprends pas comment cette approche simulée est une amélioration. Si vous êtes à la recherche par le biais de l'ensemble de l'arborescence à plusieurs reprises, pourquoi ne pas simplement utiliser une normale min/max, qui aurait seulement besoin d'une visite de chaque nœud?
- L'ensemble de Monte-Carlo méthode est pour quand les résultats ne sont pas déterministes (j'.e ils ont un peu de hasard), ou lorsqu'il est difficile de construire une bonne heuristique de l'algorithme de scoring, ou lors de simulations sont en continu (pas de tour par tour). Minimax ne fonctionne pas quand les jeux ne sont pas au tour par tour dans la nature. Plus qu'une visite des tentatives pour donner une "moyenne" des résultats.
InformationsquelleAutor danielbeard

De http://mcts.ai/code/index.html:

Below are links to some basic MCTS implementations in various
programming languages. The listings are shown with timing, testing
and debugging code removed for readability.

Java

Python

InformationsquelleAutor Thomas Ahle