Short answers, pulled from the story.
Monte Carlo tree search (MCTS) is a heuristic search algorithm that evaluates game positions by running large numbers of random simulations, called playouts, to the end of the game. Each cycle consists of four steps: selection, expansion, simulation, and backpropagation. The algorithm repeats these cycles until time runs out, then selects the move with the most simulations as its answer.
The name and formal description were established in 2006, when Remi Coulom coined the term and Kocsis and Szepesvar developed the UCT algorithm. The underlying Monte Carlo method dates to the 1940s, and B. Brugmann first applied it to a Go-playing program in 1992.
AlphaGo used Monte Carlo tree search combined with deep neural networks to master the board game Go. In October 2015 it became the first computer program to beat a professional human Go player without handicaps on a full 19x19 board. In March 2016, it defeated Lee Sedol 4-1 and was awarded an honorary 9-dan ranking.
UCT, or Upper Confidence bounds applied to Trees, is a formula introduced by Levente Kocsis and Csaba Szepesvar in 2006 for balancing exploitation of strong moves with exploration of rarely-tried moves. It traces back to the UCB1 formula by Auer, Cesa-Bianchi, and Fischer, and to the AMS algorithm by Chang and colleagues from 2002.
MCTS can fail to detect "trap states": moves that appear strong but lead to a loss through a subtle sequence of play. Because the algorithm concentrates on promising branches and prunes less-explored lines, it can overlook specific but critical sequences. It is believed this contributed to AlphaGo's loss in its fourth game against Lee Sedol.
MCTS has been applied to Chess, Shogi, Checkers, Backgammon, Contract Bridge, Scrabble, Clobber, Hex, Havannah, Game of the Amazons, Arimaa, and nondeterministic games such as poker, Magic: The Gathering, and Settlers of Catan. It has also been used in real-time video games including Ms. Pac-Man and Fable Legends, and in the campaign AI for Total War: Rome II.