5 ms·

Nice write-up & demo. MCTS—UCT particularly—is a hidden gem of symbolic AI that hasn’t found it’s deserved notoriety; I suspect because it’s not as flashy as t

Nice write-up & demo. MCTS—UCT particularly—is a hidden gem of symbolic AI that hasn’t found it’s deserved notoriety; I suspect because it’s not as flashy as the successes of deep learning. I think we’ll be seeing a lot more of it in the future though, as it has proven to be a remarkably flexible general search algorithm with simple, tunable mechanics to balance exploration/exploitation. It also works well in both classical search and adversarial search with minor modifications. A lesser-known example of its use in classical search is that at the time DeepMind made waves with performance on Atari games with Deep Q-Learning, the state of the art results (better than deep-q results on most games) were actually MCTS-UCB for planning/policy learning.

toxik 8y ago
It is true that AI researchers are drawn to DNNs like moths to the flame, but AlphaGo garnered quite a bit of attention and it uses MCTS in a very interesting way
2bitencryption 8y ago
it's wonderful in situations where the breadth of search is impractically enormous, but the depth limited. like complex games :)
- throwawa123412 8y ago
  Is this some sort of "accepted wisdom" ?? (i.e. Does MTCS handles breadth better than depth) I understand the MCTS rollout becomes difficult with 1000s of moves ahead. But we can "learn" a leaf evaluator, or "learn" to limit the branch out at deeper levels, etc etc. Are there key papers or conclusions on this issue?
  - 2bitencryption 8y ago
    the reasoning for that thinking is simply because MCTS is comparable to DFS while something like minimax is comparable to BFS. Of course, because MCTS searches in a depth-first manner, the deeper the depth the less effective it is, because you have less time for your rollouts (as your rollouts are more expensive). But not many board games (if we are limiting ourselves to this example) will have thousands of moves until end of game -- they may, however, have an exponentially large breadth of moves. For a game like Go, MCTS could simulate thousands of rollouts in the amount of time it would take minimax to evaluate two plies ahead.

toxik 8y ago

It is true that AI researchers are drawn to DNNs like moths to the flame, but AlphaGo garnered quite a bit of attention and it uses MCTS in a very interesting way

2bitencryption 8y ago

it's wonderful in situations where the breadth of search is impractically enormous, but the depth limited. like complex games :)

throwawa123412 8y ago
Is this some sort of "accepted wisdom" ?? (i.e. Does MTCS handles breadth better than depth) I understand the MCTS rollout becomes difficult with 1000s of moves ahead. But we can "learn" a leaf evaluator, or "learn" to limit the branch out at deeper levels, etc etc. Are there key papers or conclusions on this issue?
- 2bitencryption 8y ago
  the reasoning for that thinking is simply because MCTS is comparable to DFS while something like minimax is comparable to BFS. Of course, because MCTS searches in a depth-first manner, the deeper the depth the less effective it is, because you have less time for your rollouts (as your rollouts are more expensive). But not many board games (if we are limiting ourselves to this example) will have thousands of moves until end of game -- they may, however, have an exponentially large breadth of moves. For a game like Go, MCTS could simulate thousands of rollouts in the amount of time it would take minimax to evaluate two plies ahead.