Lab for Artificial Intelligence I (NAIL069), Winter 2018-9

Instructor: Adam Dingle

This is the lab (cvičení) in English for the Artificial Intelligence I course taught by Prof. Roman Barták. In this lab 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 lab happens from 9:00 – 10:30 on Thursdays in room SU2. You can register for the lab 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 4. If you have signed up for even weeks (group B), your first session is Oct 11.

textbook

You may optionally consult the following textbook, which gives a nice overview of AI in gaming including some of the ideas we'll be exploring:

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

requirements

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

programming assignments

We will have 5 programming assignments throughout the semester. 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. You can write your agent in Java or in any other JVM-compatible language (e.g. Kotlin, Scala). 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!)

The game assignments are

game

points

soft deadline

Git repository

suggested approach

Super Mario Bros.

10

Oct 28

MarioAI

simple reflex agent

Ms. Pac-Man

20

Nov 25

MsPacMan-vs-Ghosts-AI

uninformed graph search

Sokoban

20

Dec 18

Sokoban4J

A* with custom heuristic

Warlight

30

Jan 20

conquest-engine-gui

expectiminimax or Monte Carlo tree search

Minesweeper

20

Feb 3

Minesweeper4J

backtracking search for CSPs

The deadlines above are soft. If you submit an assignment by its deadline, you will receive 2 bonus points. If you submit it late, you will receive neither a bonus nor a penalty.

Also, for the first four of these games 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 soft deadline.

semester project

You may complete an optional semester project to earn 40 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 (soft) deadline for submitting your semester project is Sun Jan 27. I will award 5 bonus points if it's submitted on time.

other notes

The final deadline for submitting all work for this lab is Wed Feb 13 in the last week of the exam period. But I suggest that you try to complete all work well before that, to avoid running into trouble at the end.

resources

course syllabus by week

Oct 1
Introduction, major topics, context, history, and applications of AI.
Oct 8
Intelligent agents, environment, structure of agents.
Oct 15 (exercises)
Problem solving, uninformed search algorithms.
Oct 22 (exercises)
Informed search algorithms and heuristics.
Oct 29
Local and on-line search algorithms. Constraint satisfaction.
Nov 5
Adversarial search (games).
Nov 12
Knowledge representation, propositional logic.
Dec 3
First-order logic.
Dec 10
First-order logic – continued.
Dec 17
Knowledge engineering.
Jan 7
Automated planning.