I was surprised to learn yesterday from Tesla’s AI Day event that the cars use Monte Carlo Tree Search (MCTS) to determine pathing, a strategy-searching algorithm originally developed to play games like Chess or Go. While MCTS is part of Alpha Go, the premier Go-playing AI (which famously uses machine learning to evaluate states of the game), MCTS itself has more in common with Deep Blue than with modern ML systems.
If MCTS is valuable in something as simple as pathing for a self-driving car, this makes me wonder what else it is good for, and makes me suspect we can likely find something similar inside of human brains.
It’s less surprising if you’re familiar with the history of MCTS. MCTS is a generic MDP or decision-tree solver: you can use it for pretty much any kind of non-adversarial discrete fully-observed planning process where you have a model; you can extend it to non-fully-observed POMDP and continuous observations fairly easily, and that was done back in the 2000s. (Adversarial is also easy—minimax it—but adversarial+POMDP mostly breaks MCTS which is why you don’t see it but other methods solving poker.) Path planning is a classic tree search problem which comes up all the time in robotics and other planning domains like planning movement paths in simulations/games, and so if you go back and look, you’ll find plenty of pre-AlphaGo applications of MCTS to path planning.
I was surprised to learn yesterday from Tesla’s AI Day event that the cars use Monte Carlo Tree Search (MCTS) to determine pathing, a strategy-searching algorithm originally developed to play games like Chess or Go. While MCTS is part of Alpha Go, the premier Go-playing AI (which famously uses machine learning to evaluate states of the game), MCTS itself has more in common with Deep Blue than with modern ML systems.
If MCTS is valuable in something as simple as pathing for a self-driving car, this makes me wonder what else it is good for, and makes me suspect we can likely find something similar inside of human brains.
It’s less surprising if you’re familiar with the history of MCTS. MCTS is a generic MDP or decision-tree solver: you can use it for pretty much any kind of non-adversarial discrete fully-observed planning process where you have a model; you can extend it to non-fully-observed POMDP and continuous observations fairly easily, and that was done back in the 2000s. (Adversarial is also easy—minimax it—but adversarial+POMDP mostly breaks MCTS which is why you don’t see it but other methods solving poker.) Path planning is a classic tree search problem which comes up all the time in robotics and other planning domains like planning movement paths in simulations/games, and so if you go back and look, you’ll find plenty of pre-AlphaGo applications of MCTS to path planning.