How do we handle really large games?

Although Alpha-Beta pruning is efficient and guaranteed to still give an optimal answer, it is not sufficient to enable search in very large games such as Go.  Here, we examine the approach used by Alpha Go called Monte Carlo Tree Search.  Although I draw on material from the book in this section, I also reference a paper (linked below) which gives an excellent overview of MCTS. 

• Read Section 5.4 of Chapter 5 (Monte Carlo Tree Search)
  • Optional:  If you are eagerly wanting to learn more about MCTS, I highly recommend this overview paper.  It is a free PDF download.
  • Optional: If you are still confused by MCTS after the videos, here are some other resources
    • https://www.cs.swarthmore.edu/~mitchell/classes/cs63/f20/reading/mcts.html
    • https://towardsdatascience.com/monte-carlo-tree-search-an-introduction-503d8c04e168

Monte Carlo Tree Search

• Watch the video on MCTS 
  • Copy of the slides

Assignment

• Complete the exercise on MCTS
• What is the game solution that has been in the news lately that has excited you the most?  Post on #random and share!

Next Topic

• Closely related to MCTS is the concept of rollouts.  Let’s jump into those next.