Algorithms for Computer Games TKO_5710

News

2004-03-30: The results of the third examination are announced.
2004-02-03: The results of the second examination are announced.
2003-12-02: Coming attractions: Special Course on Networked Virtual Environments, January-February, 2004.
2003-11-25: The results of the first examination can be found on the noticeboard in the fifth floor and in the Wentti system.
2003-11-18: The bonus on grades competition is over. The highest score was 31 points. Thanks to all who participated and congratulations to the winners.
2003-10-30: The final versions of the table of contents and bibliography of the lecture notes are now available.
2003-10-07: The lecture on October 8 (Wednesday) is held in Etäluokka. Since there are no lectures on week 42, the next lecture date after that is October 21 (Tuesday).
2003-09-19: The examination dates have been confirmed: (1) November 24, 2003 (2) February 2, 2004 (3) March 29, 2004.
2003-09-16: Information on the voluntary exercise project.
2003-09-04: Information on the timetable and the lecture notes.
2003-08-06: Tentative information on the course: Lectures are held on Tuesdays and Wednesdays 2-4 p.m. in Auditorium (DataCity, 2nd floor). Course begins September 9 and ends October 29.

Timetable

Lectures

	Date	Topics (lecture note pages)	Additional material and links of interest	Note
1.	Tue, Sep. 9	Introduction, definitions, MVC (pp. 1-5)	Slides, Spacewar	Chapter 1 of the lecture notes distributed.
2.	Wed, Sep. 10	Sought-after features, notations, definition of random numbers (pp. 6-17)	Slides	Chapter 2 of the lecture notes distributed.
3.	Tue, Sep. 16	Linear congruential method, choice of parameters, tests (pp. 18-23)	Slides
4.	Wed, Sep. 17	Spectral test, shuffling, uses for random numbers (pp. 23-30)	Slides, Spectral test applet, Elite, AOE
5.	Tue, Sep. 23	Game trees, minimax (pp. 31-36)	Slides	Chapter 3 of the lecture notes distributed.
6.	Wed, Sep. 24	Alpha-beta pruning, prisoner's dilemma (pp. 36-39)	Slides, Alpha-beta pruning applet
7.	Tue, Sep. 30	Path finding, grid, navigation mesh, graph algorithms (pp. 41-47)	Slides, Triangulation applet	Chapter 4 of the lecture notes distributed.
8.	Wed, Oct. 1	Evaluation function, A*, movement realization (pp. 47-54)	Slides, A* applet
9.	Tue, Oct. 7	Decision-making in computer games, influence maps (pp. 55-62)	Slides, Influence map applet	Chapter 5 of the lecture notes distributed.
10.	Wed, Oct. 8	Generalized influence maps, flocking algorithms, soft computing (pp. 62-69)	Slides, Hunt the Wumpus, Boids	Lecture is held in Etäluokka.
11.	Tue, Oct. 21	Goals of cheating prevention, tampering network traffic, illicit information, design defects, collusion (pp. 71-75)	Slides, Inferring internet denial-of-service activity, Interactive multi-user computer games, Aspects of networking in multiplayer computer games	Chapter 6 of the lecture notes distributed.
12.	Wed, Oct. 22	Offending other players, MD5 algorithm, lockstep protocol (pp. 75-80)	Slides, MD5 algorithm
13.	Tue, Oct. 28	Optimization, bit fiddling (pp. 81-99)	Slides	Chapter 7 of the lecture notes distributed.
14.	Wed, Oct. 29	Integer functions, low-level data structures (pp. 99-107)	Slides, Knuth's lectures, Independent Games Festival	Bibliography and index of the lecture notes distributed.

Examinations
The examination dates are:

November 24, 2003.

February 2, 2004.

March 29, 2004.

Check the exact times and places here, and remember to enrol in time.
Note: If you are not a student of University of Turku, you must follow these instructions to receive credits.

Lecture notes
Paper copies of the lecture notes (Jouni Smed and Harri Hakonen: Algorithms for Computer Games, University of Turku, 2003) are distributed in the lectures throughout the course. No electronic version of the lecture notes is made publicly avaible.
Contents

1. Introduction
2. Random Numbers
3. Game Trees
4. Path Finding
5. Decision-Making
6. Cheating Prevention
7. Code Tweaking
Bibliography

Errata
A list of known bugs and errors in the lecture notes is available here.

Syllabus
Outline: The course concentrates on algorithmic problems present in computer games. The topics cover among other things random numbers, game trees, path finding, decision-making, and code tweaking.
Aims: The aim of the course is to review common solution methods, analyse their usability, and describe possible improvements.
Credits: 2 cu
Prerequisites: Tietorakenteet ja algoritmit [Data Structures and Algorithms] (mandatory), Ohjelmointi II [Programming II] (recommended)
Teaching methods: Lectures (28 h), Tuesdays and Wednesdays 2-4 p.m.
Assessment: Examination
Literature: Lecture notes
Lecturer: Jouni Smed
Schedule: September 9 - October 29