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?
Applications of MCTS/UCT
optimization;ai.artificial intel;board games
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 Pudlk, Russell Impagliazzo: A lower bound for DLL algorithms for k-SAT (preliminary version). SODA 2000: 128-136