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?