Monte Carlo Tree Search
The Monte Carlo Tree Search (MCTS) is a search algorithm that an AI can use to make optimal decisions and reach its goals. Unlike minimax, the MCTS can work in very open-ended environments with a high branching factor, making it much more effective in games like Go, where the sheer amount of possibilities and choices are just too great for the brute force approach. It also does not require an evaluation function to determine the value of a game state, making it much more "adaptable" to different environments. The MCTS uses 4 main functions (Select, Expand, Simulate, and Update) to create an asymmetric statistics tree which maps onto a game tree, which an AI can then use to ultimately make the "right decision." This tech talk goes into detail how the MCTS determines which function to call in what situation, and how exactly it builds its stats tree.
Project Members: Charles Long