SubjectsSubjects(version: 901)
Course, academic year 2021/2022
Artificial Intelligence for Computer Games - NAIL122
Title: Umělá inteligence pro počítačové hry
Guaranteed by: Department of Software and Computer Science Education (32-KSVI)
Faculty: Faculty of Mathematics and Physics
Actual: from 2021
Semester: winter
E-Credits: 3
Hours per week, examination: winter s.:1/1 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
Virtual mobility / capacity: no
State of the course: taught
Language: Czech
Teaching methods: full-time
Guarantor: Mgr. Jakub Gemrot, Ph.D.
Annotation -
Last update: doc. RNDr. Pavel Töpfer, CSc. (24.01.2019)
Environments of strategic video games are complex and they can be characterized (not only) as non-deterministic, simulated in real-time and having extremely large game trees. This course focuses on problems of using traditional search algorithms in such environments. A script space will be presented as an alternative to an action space, search algorithms suitable for durative actions are discussed and Monte-Carlo Tree Search family of algorithms will be presented. The possibility of using artificial evolution for game tree pruning.
Aim of the course -
Last update: doc. RNDr. Pavel Töpfer, CSc. (24.01.2019)

To gain overview about algorithms and techniques which can be used for the implementation of artificial intelligence for strategic videogames.

Course completion requirements -
Last update: Mgr. Jakub Gemrot, Ph.D. (15.07.2020)

The course ends with successfully completing an exam and gaining a credit from the labs.

The credit from the labs is not required for taking the exam.

To gain a credit from labs, an active participation on labs is required as well as an implementation of chosen algorithm presented during lectures.

Literature -
Last update: doc. RNDr. Pavel Töpfer, CSc. (24.01.2019)


RUSSEL, Stuart J. and NORVIG, Peter, 2010. Artificial Intelligence: A Modern Approach. 3rd. Upper Saddle River: Prentice Hall. ISBN 978-0-13-604259-4.

Scientific articles:

AUER, Peter, CESA-BIANCHI, Nicolo and FISCHER, Paul, 2002. Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning. 2002. Vol. 47, p. 235-256.

BRANAVAN, S. R. K.; SILVER, David; BARZILAY, Regina. Non-linear monte-carlo search in civilization ii. In: IJCAI. 2011. p. 2404-2410.

BROWNE, Cameron B., et al. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in games, 2012, 4.1: 1-43.

CHURCHILL, David; BURO, Michael. Portfolio greedy search and simulation for large-scale combat in StarCraft. In: Computational Intelligence in Games (CIG), 2013 IEEE Conference on. IEEE, 2013. p. 1-8.

CHURCHILL, David; SAFFIDINE, Abdallah; BURO, Michael. Fast Heuristic Search for RTS Game Combat Scenarios. In: AIIDE. 2012. p. 112-117.

FURTAK, Timothy; BURO, Michael. On the Complexity of Two-Player Attrition Games Played on Graphs. In: AIIDE. 2010.

GOSLING, Tim and ANDRUSZKIEWICZ, Piotr, 2014. Divide and Conquer, The Campaign AI of Total War: ROME II. Game/AI Conference Vienna [online]. 2014. [Accessed 20 May 2016]. Available from:

JUSTESEN, Niels, et al. Script-and cluster-based UCT for StarCraft. In: Computational Intelligence and Games (CIG), 2014 IEEE Conference on. IEEE, 2014. p. 1-8.

ONTANÓN, Santiago. Informed monte carlo tree search for real-time strategy games. In: Computational Intelligence and Games (CIG), 2016 IEEE Conference on. IEEE, 2016. p. 1-8.

ONTANÓN, Santiago. The combinatorial multi-armed bandit problem and its application to real-time strategy games. In: Ninth Artificial Intelligence and Interactive Digital Entertainment Conference. 2013.

Conference proceedings:

Artificial Intelligence and Interactive Digital Entertainment

Computational Intelligence and Games

Teaching methods -
Last update: Mgr. Jakub Gemrot, Ph.D. (15.07.2020)

Respective algorithms will be presented theoretically during lectures; these will be implemented and empirically evaluated during labs.

Requirements to the exam -
Last update: Mgr. Jakub Gemrot, Ph.D. (15.07.2020)

Knowledge of algorithms presented during lectures.

Syllabus -
Last update: doc. RNDr. Pavel Töpfer, CSc. (24.01.2019)

Environment of strategic video games from the artificial intelligence point of view

Monte-Carlo Tree Search algorithm and its variants and modifications

Search algorithms working with durative actions - Alpha-Beta Considering Durations, Monte-Carlo Tree Search Considering Duration

Script space and scripts exploiotability; Portfolio Greedy Search, Nested Greedy Search

Using artificial evolution algorithms for game tree pruning

Performant implementation of search algorithms

Charles University | Information system of Charles University |