Applications des SCTM / UCT

MCTS / UCT est une méthode de recherche d'arbre de jeu qui utilise un algorithme de bandit pour sélectionner les nœuds prometteurs à explorer. Les jeux sont joués de manière aléatoire et les nœuds menant à plus de victoires sont explorés plus en profondeur. L'algorithme de bandit maintient un équilibre entre l'exploration des nœuds avec des taux de gain élevés et l'exploration des nœuds inconnus (et dans sa forme pure n'utilise pas nécessairement une fonction d'évaluation heuristique). Les programmes basés sur cette technique générale ont obtenu des résultats assez étonnants dans Computer Go .

Des recherches de monte-carlo menées par des bandits ont-elles été appliquées à d'autres problèmes de recherche? Par exemple, serait-ce une approche utile pour approximer des solutions à MAX-SAT, BKP ou à d'autres problèmes d'optimisation combinatoire? Existe-t-il des caractéristiques particulières d'un problème (structurel / statistique / etc.) qui suggéreraient si une approche de type bandit serait efficace?

Existe-t-il des problèmes déterministes connus qui seraient totalement résistants aux méthodes de bandit, en raison de la nature de l'espace de solution?

Ce n'est pas une réponse complète, mais quelques observations de base sur l'application de ceci à MAX-SAT.

À un niveau élevé, il semble que cette approche heuristique (lorsqu'elle est appliquée à MAX-SAT) serait similaire à un algorithme de branchement basé sur la méthode de "l'attente conditionnelle", une méthode standard de dérandomisation. Par exemple, pour obtenir une approximation déterministe pour MAX 3-SAT (avec 3 variables par clause), on définit une variable , estime la fraction attendue des clauses qui seront satisfaites par une affectation aléatoire dans le reste formule, puis définit et fait le même calcul. (Cela ressemble extrêmement à «jouer un jeu jusqu'à son terme au hasard».) Le paramètre de variable avec la fraction attendue la plus élevée de clauses ( ou ) sera choisi. Cet algorithme de temps polynomial donne un$7/8$$x=0$$x=1$$x=0$$x=1$$7/8$ -approximation et est connu pour être serré (vous pouvez le tromper en satisfaisant seulement des clauses). Cette connexion devrait permettre de prouver des bornes inférieures sur la capacité de cette heuristique.$7/8$

Il est connu qu'approcher MAX 3-SAT mieux que est dur, donc nous ne nous attendons pas à ce qu'une heuristique efficace fasse mieux que cela. Il serait intéressant de montrer (et je suppose qu'il est vrai) qu'un algorithme de branchement basé sur l'heuristique de choix de variable ci-dessus nécessite exponentiellement de nombreuses étapes pour trouver une approximation meilleure que . Il existe déjà des bornes inférieures sur retours en arrière qui disent que peu importe ce que heuristique vous utilisez, même si vous devinez parfaitement, il y a encore des formules insatisfiables pour lesquelles retours en arrière ne concluent - ils insatisfiables après exponentiellement êtes la nombreuses étapes. Des bornes inférieures sur les longueurs des épreuves de résolution donnent ces résultats. Une référence est:$7/8$$NP$$7/8$

Pavel Pudlák, Russell Impagliazzo: une borne inférieure pour les algorithmes DLL pour k-SAT (version préliminaire). SODA 2000: 128-136

Quant à la question de savoir quelles caractéristiques rendent un problème susceptible d'approches basées sur les bandits, cet article décrit le comportement de l'UCT dans divers espaces de recherche:

http://www.cs.cornell.edu/~raghu/Raghuram_Ramanujan_files/mcts11.pdf

Cordialement, Cameron

Ce récent document d'enquête énumère l'application des SCTM à un certain nombre de problèmes de recherche et d'optimisation autres que les jeux, à la section 7.8:

http://pubs.doc.ic.ac.uk/survey-mcts-methods/survey-mcts-methods.pdf

http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=6145622

En ce qui concerne les domaines qui sont totalement résistants aux méthodes basées sur les bandits, je n'en connais aucun. Les échecs sont une omission flagrante de la littérature des SCTM, peut-être en raison des «états pièges» qui nuisent à la recherche, mais aussi peut-être du fait que les joueurs d'échecs informatiques sont tellement optimisés et bons de nos jours qu'il est peu probable qu'une nouvelle approche une bosse sur eux.

Cordialement, Cameron