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.
Last update: doc. RNDr. Pavel Töpfer, CSc. (24.01.2019)
Prostředí strategických počítačových her jsou z hlediska umělé inteligence často složítá a dají se charakterizovat
jako částečně pozorovatelná, nedeterministická, simulovaná v reálné času a obecně velmi rozsáhlá co do velikosti
herních stromů. V rámci přednášky se zaměříme na problémy implementací tradičních prohledávacích algoritmů v
těchto počítačových hrách, představíme prostor skriptů jako alternativu k prostoru akcí, algoritmy pracující s
durativností herních akcí a rodinu algoritmů Monte-carlo Tree Search a možnosti využití evolučních algoritmů pro
pruning herních stromů.
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.
Last update: doc. RNDr. Pavel Töpfer, CSc. (24.01.2019)
Získání přehledu o technikách a algoritmech, které se používají při implementaci umělé inteligence pro počítačové hry typu strategie.
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.
Last update: Mgr. Jakub Gemrot, Ph.D. (15.07.2020)
Předmět je zakončen úspěšným složením zkoušky a získáním zápočtu.
Ke složení zkoušky není nutné získat zápočet.
K získání zápočtu se požaduje aktivní participace na cvičení a implementace vybraného algoritmu prezentovaném v rámci přednášky.
Literature -
Last update: doc. RNDr. Pavel Töpfer, CSc. (24.01.2019)
Books:
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: https://archives.nucl.ai/recording/divide-and-conquer-the-campaign-ai-of-total-war-rome-ii/
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
Last update: doc. RNDr. Pavel Töpfer, CSc. (24.01.2019)
Knihy:
RUSSEL, Stuart J. and NORVIG, Peter, 2010. Artificial Intelligence: A Modern Approach. 3rd. Upper Saddle River: Prentice Hall. ISBN 978-0-13-604259-4.
Vědecké články:
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: https://archives.nucl.ai/recording/divide-and-conquer-the-campaign-ai-of-total-war-rome-ii/
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.
Sborníky konferencí:
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.
Last update: Mgr. Jakub Gemrot, Ph.D. (15.07.2020)
V rámci přednášky budou jednotlivé oblasti představeny teoreticky, které budou poté v rámci cvičení implementovány a empiricky evaluovány.
Requirements to the exam -
Last update: Mgr. Jakub Gemrot, Ph.D. (15.07.2020)
Knowledge of algorithms presented during lectures.
Last update: Mgr. Jakub Gemrot, Ph.D. (15.07.2020)
Znalost látky probírané během přednášek.
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
Last update: doc. RNDr. Pavel Töpfer, CSc. (24.01.2019)
Charakterizace prostředí strategických her z pohledu umělé inteligence
Monte Carlo Tree Search a jeho modifikace
Prohledávací algoritmy pracující s durativnost herních akcí - Alpha-beta Considering Durations, Monte Carlo Tree Search considering Durations
Prostor herních skriptů a jejich exploitibilita; Portfolio Greedy Search, Nested Greedy Search
Využití evolučních algoritmů pro pruning herních stromů
