# CMPUT657: Monte Carlo Methods in Games, Planning and Heuristic Search

### Basic Information

• Start: January 6, 2015
• Time: Tuesday and Thursday, 3:30PM - 4:50PM
• Room: CSC B 41
• Instructor: Martin MÃ¼ller

### Prerequisites

• Strong programming skills, ability to work with and extend existing C++ code
• Undergraduate level AI course (CMPUT 366) or equivalent.

### Overview

In this course you will get a broad overview of heuristic search, with a special focus on modern exploration-based methods including Monte Carlo simulation. The course includes a large hands-on component, where you will work on concrete examples and program your own algorithms.

### Objectives

• Learn classical algorithms for single agent search (puzzles), games and planning
• Understand heuristic search paradigms such as divide and conquer, abstraction, relaxation, exact and approximate solution methods
• Study in detail the three components of modern heuristic search algorithms: search, knowledge, and simulation
• Read about and apply techniques of Monte Carlo Tree Search for games and probabilistic planning
• Find out about exploration-based methods and how they are used in classical planning
• Understand modern methods for motion planning such as probabilistic roadmaps and rapidly exploring random trees
• Define, implement and document a small-group course project in one of the topics above

## Course Outline

Using exploration techniques, and especially Monte Carlo Methods has recently become a very popular approach in many areas of heuristic search, such as games, planning and robotics. The goal of this course is an in-depth study of the main approaches to using exploration in heuristic search. The course includes a large hands-on component, where Students will work on concrete examples and program their own algorithms.

This course begins with a short introduction to the standard "classical" heuristic search algorithms, and motivates the need for exploration techniques. The main three components of current algorithms: search, knowledge and simulation, are introduced. This will be accomplished by reading, lectures, discussions and by practical exercises.

In the later part of the course, you will deepen and apply your knowledge in planning by doing a software project in a small group. You will have a large degree of freedom in choosing your topic as long as it is relevant to the course.

This course can be a good preparation if you are considering doing an MSc or PhD. The course project could be a starting point for a thesis in this area. (Unfortunately, at this point in time, funding for positions in my group is unclear. But I will know later during the term.)

#### Course Details

There is a detailed outline on a separate page, and an up-to date course schedule is always on the main eclass course page.

### Readings, Course Notes, Slides and Literature

• References from the literature will be provided for each topic, and required reading will be assigned in some weeks.
• There is no required textbook. No single book covers a good fraction of the topics in this class.
• Lecture slides will be provided.
• For a book-in-progress, I will be working on detailed course notes for the game-related parts of this course. Drafts will be distributed as they are created.

### Course Work, Project, and Grading

There will be two programming assignments, two take-home quizzes, and one course project. The course project is split into five steps, some of them quite small. Projects will be done in groups of two or three. Finally, there are assessment components for several different ways of course participation.
• 40% Project, including written proposal, in-class presentation, implementation and evaluation, final presentation including software demo, intermediate and final report.
• 30% Assignments (2x15%)
• 20% Take-home Quizzes (2x10%)
• 10% Course participation including pre-class online quizzes and discussion forum

Final grades will be based on the 4-point grading system and assigned in accordance with the University of Alberta grade distribution guidelines for graduate courses as specified in the University of Alberta Marking and Grading Guidelines.

### Plagiarism and Cheating

Make sure you have read and are familiar with the Code of Student Behaviour for the University of Alberta, especially with Section 30.3.2 Inappropriate Academic Behaviour. Plagiarism and other forms of cheating are considered to be serious academic offences. In case of doubt, consult with your instructor before choosing an action.