I recently saw the AlphaGo documentary film and it blew my mind. Essentially, a computer was able to beat a world champion in a best of five match of Go, a game with an overwhelmingly large search space—a 19 x 19 board. One of the principal techniques of its success was Monte Carlo Tree Search (MCTS). While it has received adequate exposition elsewhere,1 I thought that a video could be a nice addition to what’s already out there.
Each year, hundreds of thousands of kids apply1 to New York City’s public school system with a ranking of up to twelve schools. The Department of Education then matches all of these students up with a single offer from one of NYC’s 1,800 public schools,2 ensuring maximum satisfaction for the applicants. How does it work?
At first glance, my intuition was that this was a really complex problem. After watching this fantastic video, I then sketched out the algorithm in a notebook and came to believe that it was pretty simple.