582329 AI for Games (3 cr) Autumn 2009
Congratulations Winners!!!
News
- Pieter's final notes (Competition module)
- slides 1, 2, 3, 4, 5, 6, 7, 8, 9, 10a, 10b, 10c, 11
- In order to pass the course you should write a report (in Finnish, maximum length 2 pages) describing your AI: what you have done, how you have done it, how it was tested, and how it was found to perform. Send the report to Tomi with group members information (names and student numbers).
- note that we start at 10.15, also others times are delayd by 15 minutes in the scedule below
- registration is open for the course
- lectures are hold in class C222, and Practicals in B221 (except on Monday Practicals are hold in B121)
Lecturer Pieter Spronck and course coordinator Tomi Pasanen.
The course takes place between 31.8.-4.9.2009 (week 36) and discusses artificial intelligence (AI) in modern video games. The course focus is on behavior of video game characters (agents). The following topics are covered:- An introduction to game AI
- Decision making
- Tactics and strategies
- Learning
- Designing game AI
- An introduction to game theory
- AI for classic board games
- AI for modern board games
The course focusses on the problems of creating AI for video games, and the requirements and restrictions for such AI. The course discusses how game developers deal with these problems in practice. It also discusses where the currently used techniques fail, what goals game developers want to achieve, and how more modern techniques can actually achieve these goals.
The course is aimed at computer-science students in their third or fourth year. The students are expected to be able to program with ease, and must be able to deal with basic computer science knowledge. Some knowledge of artificial intelligence helps.
Practical
It is expected that students can use the course material immediately in a practical. The course will consist for 60% of practical exercises (or actually, one big practical exercise). The practical will be done with the Neverwinter Nights environment. The programming language used in this environment is NWScript. This is a relatively simple but powerful language, which a student who is familiar with any 3rd-generation language (e.g., Java, C++, Pascal, Python) can use with ease.
Neverwinter Nights was used in the period 2002-2005 to develop successful commercial games, and is still comparable to the most advanced game-development tools known today; only the graphics are no longer up to the level that we are used to now. Since graphics are unimportant for the course, NWN is a suitable tool for the course's purpose.
During the practical, the students must, in small groups, design and program AI for a team of characters within a Neverwinter Nights game area that is reminiscent of a World of Warcraft Battleground. In the battleground the teams attempt to score points by capturing and holding several tactical locations. The environment is suitable to play around with every aspect of game AI that is dealt with during the course, from the AI of individual agents to team AI, tactics, strategies, and even adaptive AI.
On the last course day, a tournament will be held in which the AIs of the different student groups will have to take each other on. The students will give a short presentation on what they tried to accomplish with their AIs, and during a live session the winner of the tournament will be discovered.
The lecturer will bring several copies of NWN for use during the course. During the practical, the course lecturer will be available to the students for guidance and assistance.
Course material
The course is based on parts of the book "Artificial Intelligence for Games" by Ian Millington, with some extra material added by the lecturer. It helps if the students have this book for the course, although it is not a necessity. The lecturer provides extensive sheets. There is some additional material available, in the form of papers in English.
Preliminary course setup
The course will be taught over a period of five days. In the mornings, there will be a two-hour lecture. In the afternoon, the students will work on the practical.- 10:00-10:45 Introduction to game AI: What is AI - What are games - How are video games constructed - The current state of the games industry - The goals of game AI - A model for game AI - Why game AI research
- 11:00-11:45 Introduction to the Practical: What is Neverwinter Nights - How to design an NWN module - How to program in NWScript - The goal of the practical - Some tips
- 13:00- Practical
- 10:00-10:45 Decision Making I: Complexity fallacy - Heuristics and cheats - Decision trees - State machines - Fuzzy logic
- 11:00-11:45 Decision Making II: Markov systems - Goal-oriented behaviour - Rule-based systems - Blackboard systems - Scripting
- 13:00- Practical
- 10:00-10:45 Tactics and Strategies: Waypoint tactics - Tactical movement (NOT pathfinding) - Tactical analyses - Influence maps - Group decisions and cooperation
- 11:00-11:45 Learning in games: Parameter modification - Hillclimbing - Annealing - N-grams - Decision tree learning - Reinforcement learning
- 13:00- Practical
- 10:00-10:45 Game AI research–A detailed discussion of dynamic scripting: How was it designed - How was it tested - - Why does it work - What kind of extensions are there - Which open questions still exist
- 11:00-11:45 Designing game AI: AI design - Selection of techniques - Shooters - Strategy games
- 13:00- Practical
- 17:00 the students deliver a working version of their AI to the lecturer, who will test the AIs against each other (without the students looking). If there are still blatant errors in any of the AIs, these will be communicated to the students, so that they can still fix them during the following day.
- 10:00-10:45 and 11:00-11:45
- If the time available in the previous days was insuffient, the fifth day is used to go through the remaining material. If the time WAS sufficient, there are several subjects which can be discussed, depending on the students' interests:
- Game theory (90 minutes): Game classification - Solving static games of complete information (Nash equilibrium) - Prisoners' dilemma - The battle of the sexes - Rock-paper-scissors - Mixed strategies - Solving dynamic games of complete information (subgame perfect Nash Equilibrium) - The blow-up game - The iterated prisoners' dilemma - Infinite games - Human play - Solving static games of incomplete information (Bayesian Nash Equilibrium) - Solving dynamic games of incomplete information (perfect Bayesian Equilibrium) - Video games
- AI for classic board games (90 minutes): Classic board games - AI goals - Game trees - Game complexity - Evaluation function - Minimaxing - Negamaxing - Alpha-beta pruning - Move ordering - Aspiration search - Transposition tables - Opening books - Turn-based strategy games
- AI for modern board games (45 minutes): Modern board games - Decision making techniques - Monte Carlo - Monte Carlo Tree Search - Opponent modelling
- 13:00-14:00: The students can make the final changes to their AIs, and deliver them to the lecturer.
- 14:00-15:00: The lecturer integrates the student AIs in a tournament module, while the students prepare their short presentations.
- 15:00-15:45: The students give short presentations on their AIs: - What was their idea - What implementation issues did they encounter - How did they evaulate their AI - What were their evaluation results
- 16:00-17:30: The tournament is played. Each AI battles each other AI for a specific period of time (10 or 15 minutes for each battle). An AI's score is the sum of all the points it scores against all the other AIs. The battles will run in parallel on several systems. The final victor will also be pitted against the winner of a previous tournament, in a single fight that may be commented by the lecturer. A small prize will be awarded to the winning team.