On January 27th, SAIG will be hosting a seminar given by University of Bradford’s Peter Cowling. The title of the session is “Graph Search + Machine Learning = Monte Carlo Tree Search” and the abstract is attached below. This is a rescheduling of the session that was originally meant to take place on December 9th, which was postponed due to poor weather conditions disrupting travel. Fingers crossed that Peter will be able to join us this time!
Search in (very large) directed graphs has proven a very productive model for creating intelligent behaviours, in areas such as computer Chess, planning, scheduling and optimisation. For other problems that can be modelled using directed graphs, such as creating computer players for the traditional board game Go, search in these graphs has proved intractable. There is considerable current excitement over the potential of Monte Carlo Tree Search algorithms (particularly UCT (http://senseis.xmp.net/?UCT)), which have integrated machine learning and graph search methods to beat human professional Go players in the past couple of years. This represents a significant step towards an outstanding research question in Artificial Intelligence (http://oase.nutn.edu.tw/FUZZ_IEEE_2009/result.htm).
In addition to its success in computer Go, Monte Carlo Tree Search has proven to be more effective than other graph search algorithms in a wide range of decision problems. In the first part of this talk we will discuss very recent work on Monte Carlo Tree Search as a general-purpose way of searching minimax trees (e.g. for Go) and other trees (e.g. for multiplayer games and decision problems with uncertainty and incomplete information).
When dealing with uncertainty and incomplete information, a common approach is to use a particular determinization, by assuming that all players know all information and that all random events are known in advance. We average over a number of determinizations, and choose the move with the best average score, yielding strong play for games such as Bridge and Scrabble. We will discuss the advantages and shortcomings of determinization, by reviewing our own work on searching the decision trees for the card games Dou Dhi Zhu and Magic:The Gathering and the board game Lord of the Rings:The Confrontation. We will discuss approaches to handling decision trees with uncertainty and hidden information,
culminating in our recent work on Information Set Monte Carlo Tree Search. as well as the work of others to create strong players for other games.
After a brief explanation of the algorithms, and a survey of some highlights of the work to date, we will discuss the rich set of open questions surrounding Monte Carlo Tree Search, which will allow us to understand this family of algorithms and the range of applications for which they might prove effective.