| Course Unit Code | 460-4152/01 |
|---|
| Number of ECTS Credits Allocated | 4 ECTS credits |
|---|
| Type of Course Unit * | Optional |
|---|
| Level of Course Unit * | Second Cycle |
|---|
| Year of Study * | Second Year |
|---|
| Semester when the Course Unit is delivered | Winter Semester |
|---|
| Mode of Delivery | Face-to-face |
|---|
| Language of Instruction | Czech |
|---|
| Prerequisites and Co-Requisites | |
|---|
| Prerequisities | Course Unit Code | Course Unit Title |
|---|
| 460-4086 | Biologically Inspired Algorithms |
| 9600-0009 | Unconvential Algorithms and Computations |
| Name of Lecturer(s) | Personal ID | Name |
|---|
| SKA206 | doc. Ing. Lenka Skanderová, Ph.D. |
| Summary |
|---|
The fundamental algorithms used in computer games will be introduced. The subject deals with topics as game theory, algorithms used in board games, motion of a character, game physics, pathfinding, decision making and decision algorithms, artificial intelligence in tactical and strategic games, learning.
|
| Learning Outcomes of the Course Unit |
|---|
| The subject aims to introduce the fundamental techniques of artificial intelligence in computer games regarding the techniques and algorithms presented in other subjects (Theoretical informatics, Algorithms I and II, Neural networks, Unconventional algorithms and computing, etc.). The subject deals with the crucial topics in AI for PC games as movement, pathfinding, decision making, tactical and strategic AI, learning, and board games. At the end of the semester, students should be capable to select an appropriate technique and apply it within the computer game regardless of the programming platform. |
| Course Contents |
|---|
1. Board games (2 lectures)
- Game theory
- Minmax Search
- Alpha-Beta Search
- Monte Carlo Tree Search
2. Movement (2 lectures)
- Steering behaviors
- Kinematic movement algorithms
- Game physics
- Coordinated movement
3. Pathfinding (2 lectures)
- Bread-first and Depth-First search algorithms
- Dijkstra
- A* - IDA (Iterative Deepening A*), SMA* (Simplified Memory-Bounded A*
- Hierarchical pathfinding
- Multi-agent pathfinding
- Flood fill algorithm
4. Decision making (2 lectures)
- Spatial data structures for (faster) Collision calculations – Multi-resolution maps, quad or octrees, binary space partition - BSP) trees
- Decision trees – ID3, C4.5 CART (Classification And Regression Tree), CHAID (Chi-square automatic interaction detection), MARS (multivariate adaptive regression splines)
- State machines, Stack-based finite state machines
- Fuzzy logic
5. Tactical and strategic AI (2 lectures)
- Waypoint tactics – influence maps
- Tactical analysis – map flooding, convolution filters, Gaussian blur
- Tactical Pathfinding – structuring multi-tier AI
- Coordinated actions
6. Learning (3 lectures)
- Learning basics – N-grams, string matching
- Parameter modification
- Action prediction
- Reinforcement learning |
| Recommended or Required Reading |
|---|
| Required Reading: |
|---|
[1] Millington, Ian, and John Funge. Artificial intelligence for games. CRC Press, 2018.
|
[1] Millington, Ian, and John Funge. Artificial intelligence for games. CRC Press, 2018.
|
| Recommended Reading: |
|---|
[1] Yannakakis, Georgios N., and Julian Togelius. Artificial intelligence and games. Springer, 2018.
[2] Buckland, Mat. Programming Game AI by Example. Wordware Publishing, Inc., 2005 |
[1] Yannakakis, Georgios N., and Julian Togelius. Artificial intelligence and games. Springer, 2018.
[2] Buckland, Mat. Programming Game AI by Example. Wordware Publishing, Inc., 2005 |
| Planned learning activities and teaching methods |
|---|
| Lectures, Tutorials |
| Assesment methods and criteria |
|---|
| Task Title | Task Type | Maximum Number of Points
(Act. for Subtasks) | Minimum Number of Points for Task Passing |
|---|
| Graded credit | Graded credit | 100 | 51 |