Applications of MCTS/UCT

Question

MCTS/UCT is a game tree search method that uses a bandit algorithm to select promising nodes to explore. Games are played to their completion randomly and nodes leading to more wins are explored more heavily. The bandit algorithm maintains a balance between exploring nodes with high win rates and exploring unknown nodes (and in its pure form doesn't necessarily use a heuristic evaluation function). Programs based on this general technique have achieved pretty amazing results in computer Go.

Have bandit-driven monte-carlo searches been applied to any other search problems? For instance, would it be a useful approach in approximating solutions to MAX-SAT, BKP, or other combinatorial optimization problems? Are there any particular characteristics of a problem (structural/statistical/etc.) that would suggest whether or not a bandit-style approach would be effective?

Are there any known deterministic problems that would be totally resistant to bandit methods, due to the nature of the solution space?

Answer 1

This is not a complete answer, but some basic observations about applying this to MAX-SAT.

At a high level, it looks like this heuristic approach (when applied to MAX-SAT) would be similar to a branching algorithm based on the method of "conditional expectation", a standard method in derandomization. For example, to get a deterministic $7/8$-approximation for MAX 3-SAT (with 3 variables per clause), one sets a variable $x=0$, estimates the expected fraction of clauses that will be satisfied by a random assignment in the remaining formula, then sets $x=1$ and does the same calculation. (This looks extremely similar to "playing a game to completion randomly".) The variable setting with the higher expected fraction of clauses ($x=0$ or $x=1$) will be chosen. This polynomial time algorithm gives a $7/8$-approximation and is known to be tight (you can fool it into satisfying only $7/8$ of the clauses). This connection should make it possible to prove lower bounds on the ability of this heuristic.

It is known that approximating MAX 3-SAT better than $7/8$ is $NP$-hard, so we don't expect an efficient heuristic to do better than this. It would be interesting to show (and I conjecture it is true) that a branching algorithm based on the above variable choice heuristic requires exponentially many steps to find a better-than-$7/8$ approximation. There are already lower bounds on backtracking which say that no matter what heuristic you use, even if you guess perfectly, there are still unsatisfiable formulas for which backtracking will only conclude they're unsatisfiable after exponentially many steps. Lower bounds on the lengths of resolution proofs yield these results. One reference is:

Pavel Pudlák, Russell Impagliazzo: A lower bound for DLL algorithms for k-SAT (preliminary version). SODA 2000: 128-136

Answer 2

As for the question of what characteristics make a problem amenable to bandit-based approaches, this paper describes the behaviour of UCT in various search spaces:

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

Regards, Cameron

Answer 3

This recent survey paper lists the application of MCTS to a number of search and optimisation problems other than games, in 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

As for domains that are totally resistant to bandit-based methods, I'm not aware of any off-hand. Chess is one glaring omission from the MCTS literature, possibly due to "trap states" that hurt the search, but also possibly due to the fact that computer Chess players are just so highly optimised and good these days that any new approach is unlikely to make a dent on them.

Regards, Cameron