Tutorial for Artificial Intelligence 1 (NAIL069),
Winter 2020-1

Instructor: Adam Dingle

This is the tutorial (cvičení) in English for the Artificial Intelligence 1 course taught by Prof. Roman Barták. In this tutorial we'll review concepts from Prof. Barták's lectures and apply them to various exercises and problems. We will especially focus on using AI techniques and algorithms to play games and solve puzzles.

The tutorial happens from 10:40 – 12:10 on Tuesdays. You can register for the tutorial in one of two groups, each of which meets every other week. If you have signed up for odd weeks (group A), your first session is on Oct 13. If you have signed up for even weeks (group B), your first session is Oct 6.

For at least the month of October, all tutorials will take place on Zoom.


The course uses this textbook:

You may optionally also consult the following books, which cover some of the ideas we'll be exploring:

You can download a PDF of the Yannakakis text for free from the book's site linked above.

For learning Java, I recommend these books:

The Beginner's Guide book is a gentle introduction. If you are an experienced programmer in C# or other languages, you can probably skip the Beginner's Guide and just dive into the Complete Reference book.

You don't necessarily need the latest versions of these Java books, since we will not be using the latest language features much or at all.


To earn a credit (zápočet) for the tutorial you will need to earn at least 70 points. You can earn points in two ways:

programming assignments

We will have 5 programming assignments throughout the semester, worth a total of (at least) 100 points. In each assignment you will write an AI agent that plays a particular game. I'll provide an implementation of each game in Java along with an API for your agent to use, and you will also write your agent in Java. For each game I will provide a suggested algorithm or approach, which we will discuss in class. You are however welcome to use any approach you like in your implementation as long as it performs just as well (or better!)

Here is a tentative plan for the assignments in this course.



deadline (#2)

suggested approach

Super Mario Bros.


Nov 1 (Nov 22)

rule-based agent

Ms. Pac-Man


Nov 15 (Dec 6)

uniform-cost search



Nov 29 (Dec 20)

A* with custom heuristic



Jan 3 (Jan 17)

minimax or Monte Carlo tree search



Jan 17 (Jan 31)

backtracking search for CSPs

Submit your assignment solutions to our ReCodEx server. Every assignment will have two deadlines: a normal deadline and a second deadline that will generally be several weeks later. Submit by the normal deadline to earn up to 100% of the possible points, or by the second deadline for up to 80% of the possible points. I will award no credit for assignments submitted after the second deadline, so please plan accordingly.

For most of these assignments we will have tournaments: I will compare all student submissions and will award extra points to the top performers. First place wins 15 bonus points; second place wins 10 points; third place wins 8 points; all other programs in the top 30% win 5 points. Your program will automatically be entered in the tournament if you submit it by the (normal) deadline.

semester project

You may complete an optional semester project to earn up to 30 points. In the semester project you will write an AI agent that plays a game of your choice using the techniques discussed in this course. Ideally you will be able to interface with an existing game implementation, but if necessary you can implement the game yourself (which is probably feasible only if it is relatively simple). Your semester project can be written in any language you like.

Before beginning your project you must send me a 1-paragraph proposal that explains the game implementation you will use, how you will interface to it, your overall algorithmic approach, and how you will evaluate your program's performance. I will approve your proposal if it seems reasonable, or may want to discuss it more first.

The deadline for submitting your semester project is Sun Feb 21.



To access any of the videos below, use our Zoom meeting ID and passcode (not your CAS login) as the username/password.

September 29
No tutorial since there was no lecture this week.
October 6 (group B video) (Java overview video)
October 13 (group A video)
Course overview. AI subdomains. Games and AI. Game characteristics. Agents. Building a rule-based agent.
October 20 (group B video) (exercises)
October 27 (group A video)
Searching in state spaces. Breadth-first search. Uniform-cost search.
November 3 (group B video) (exercises)
November 10 (group A video)
Uninformed search. A*.
November 17
No tutorial (International Students' Day).
November 24 (group A video)
December 1 (group B video)
Games. Minimax. Alpha-beta pruning.
December 8 (group A video)
December 15 (group B video)
Designing heuristic functions. Monte Carlo tree search.
January 5 (video)
Constraint satisfaction problems.