Home Courses Research Publications CV UAlbertaBot


COMP 4752 - Computational Intelligence

Updates - Course Outline - Resources - Lectures - Project - Assignments (A1 A2 A3 A4 A5)



Course Updates

Course Updates are posted on D2L via the "News" section of the 4752 Course Website



Course Outline

Computational Intelligence comprises concepts, paradigms, algorithms and implementations of systems that exhibit intelligent behaviour in complex environments. This course offers an introduction to algorithms in the following 4 fields in the area of Computational Intelligence: Heuristic Search, Reinforcement Learning, Evolutionary Algorithms, and Neutral Networks.

I have always believed that in order to fully understand a concept, you have to implement it yourself. This course will have a heavy focus on programming and implementing algorithms in fun and interesting domains. The course will consist of 5 assignments totalling 55% of the total grade, with a final project worth the other 45%. There will be no exams in the course. Here is a breakdown of all marks:

Description Grade

Assignment 1: A* Path-Finding 15%
Assignment 2: Minimax / Alpha Beta 10%
Assignment 3: Reinforcement Learning 10%
Assignment 4: Genetic Algorithms 10%
Assignment 5: Take-Home Quiz 10%

Final Project Proposal 5%
Final Project Report 40%

Total 100%



Course Resources

The following text books are useful for the course, but are not required:

Computational Intelligence: A Methodological Introduction
R. Kruse, C. Borgelt, F. Klawonn, C. Moewes, M. Steinbrecher, and P. Held, Springer, 2013.

Reinforcement Learning: An Introduction, R. Sutton and A. Barto, MIT Press, 1998


Course Notes / Lectures

All class lecture notes are available for download.



Project

The final project of this course will be to implement one of the topics taught in this course to solve a problem in a slightly more complicated domain than those in the assignments. Projects may be completed in groups of up to 3 students. Any programming language can be used to implement the final project, however Python is recommended as it is the language that is required for the course assignments. The project will consist of three stages:

Proposal: (5%)
Students will submit a maximum 2-page proposal for the final project, including the algorithm they wish to use, and the domain they plan to apply it to. I will then give feedback to the students on the scope, relevance, and feasibility of the project.

Report + Code: (30%)
Students will submit their project demo code, along with a written report on what they have implemented.

Presentation: (10%)
Students will give a short presentation and demo of their project to the class.


Possible ideas for the final project include (but are not limited to):

- Implementing additional heuristic enhancements to the A* pathfinding assignment
- Implementing additional enhancements to alpha-beta for Connect 4 (or similar game)
- Using RL to learn policies for single-player games like Blackjack
- Implement the RL temporal difference learning algorithm for grid world path-finding
- Using Genetic Algorithms to learn policies for a game like Connect 4
- Using Neural Networks for Image Classification / Recognition
- Using Neural Networks to learn heuristic distance for pathfinding
- Investigate the effect of parameter settings on the performance of assignment algorithms
- Apply assignment algorithms to the same domain + compare performance
- Implement one of the assignments in C/C++, optimize it and compare performance
- Investigate and implement specialized data structures for increasing assignment algorithm efficiency



Assignments

All assignments in this course will be written in Python 3.5.2, using the pygame library as a graphical interface. Using Python to write AI code (which is supposed to run as fast as possible) may be viewed as sacrilegious, but this course is intended to teach algorithms and learn as much as possible. Python is ideal for writing, debugging, and testing this type of code as quickly and easily as possible. Python 3 and all required libraries will be available on computer lab machines, however you may feel free to work on your own machines as well. Python 3.6.0 has been released, but currently has some issues with library support. Additional python libraries which may be useful are: matplotlib (for plotting graphs), numpy (for some numerical methods), and pybrain (AI library final assignment). Once Python 3.5.2 is installed, you can install all of these libraries with a single command: pip install pygame matplotlib numpy pybrain

Assignments can be completed solo, or with a partner (2 people max per group). Students may not choose the same partner more than once for different assignments, however they are allowed to choose any partners they wish for the project. I highly recommend finding a partner for the assignments as it will be (ideally) half the work per person. Also, having someone else to bounce ideas off for algorithm implementation will probably lead to much more efficient code!

Each assignment will be distributed with a working solution, given in Python compiled byte code, so that you can test your implementation to see how it compares. Any attempt to disassemble the solution byte code and copy the underlying obfuscated code will be (a) a very frustrating process for you, and (b) very obvious when you try to hand it in, and will lead to severe academic penalties. I don't recommend it. Also, you wouldn't be learning the material and it's really cool stuff so that would be sad.

Assignments must be submitted by 11:59pm on the day that they are due. All assignment files must be included in a single .zip file, which includes a README.txt file detailing who is working on the assignment, and any notes about the assignment such as parts you didn't get working, and what you tried. Partial marks will be given for these explanations so I recommend taking some time on them.


Assignment 1: A* Path-Finding [ Download ] (Due: February 8th, 2017)

Students must submit a .zip file including their grid_student.py file as well as a README.txt explaining who was in the group, and which parts of the assignment you think you got working / which didn't work. Explaining what didn't work, what you tried, and why you think it didn't work will get you partial marks. Assingments must be emailed to me no later than 11:59pm on the due date. Only submit one per group.

In this assignment, students will implement the A* algorithm to perform optimal path-finding in a 2D grid world setting. Students will be given a graphical interface (shown in the video below) which reads in a given map file and provides a mouse interface to click and drag to select start and end points for path-finding. Students will be asked to implement the A* algorithm to compute optimal paths between given points on the map. Full marks will be awarded to students if their A* implementation correctly computes the shortest paths, and (small) prizes will be given to the 3 students whose implementation runs the fastest!



Assignment 2: Connect 4 AI with Alpha-Beta [ Download ] (Due: February 27, 2017)

In this assignment, students will implement the Alpha-Beta heuristic search algorithm to make an AI that plays Connect 4. Students will be given a graphical interface to play Connect 4 (shown in the video below), which makes calls to a Player object's "get_move" function (initially returning a random move) that the student will need to replace with Alpha-Beta. Students will be expected to correctly implement an Alpha-Beta algorithm which is capable of always beating a random AI player. I will hold a round-robin tournament between all submissions in the class and the top 3 finishers will receive (small) prizes!



Assignment 3: Reinforcement Learning (GridWorld + DP) [ Download ] (Due: March 15th, 2017)

In this assignment, students will implement a reinforcement learning algorithm for path-finding in a gridworld environment. This algorithm will use dynamic programming and will consist of two main steps: value iteration, and policy iteration. The value iteration step updates the estimated value of a cell based on its 4 cardinal direction neighbours, and the policy iteration step updates the current path-finding policy using greedy selection. The result is a shortest path of best reward through the gridworld environment. Shown below is a video of this algorithm computing a path on a sample 10x10 map.



Assignment 4: Genetic Algorithms [ Download ] (Due: March 24, 2017)

In this assignment, students will implement the evolutionary stage of a simple genetic algorithm. Students will implement a function named 'evolve' which, given a population, selects candidate parents from the population using a given fitness function, performs mutation, and then cross-breeding of the parents to form a new generation. This process will be iterated to solve a problem in a given domain. Shown in the video below is the real-time evolution output of this assignment, a fitness over time graph as the population evolves over 100 generations. Max individual fitness of a population is shown in red, and average fitness of the entire population is shown in blue.



Assignment 5: Class Overview Take-Home Quiz [ Download ] (Due: April 5, 2017)

Students will be given a short take-home quiz on all topics covered in course lectures. Don't worry, it won't be hard... it just forces you to remember some things you forgot!