SubjectsSubjects(version: 875)
Course, academic year 2020/2021
Game Algorithms - NAIL103
Title: Herní algoritmy
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2017
Semester: winter
E-Credits: 3
Hours per week, examination: winter s.:0/2 C [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: not taught
Language: Czech
Teaching methods: full-time
Additional information:
Guarantor: RNDr. Jan Hric
Class: Informatika Mgr. - Teoretická informatika
Classification: Informatics > Theoretical Computer Science
Annotation -
Last update: T_KTI (16.05.2011)
Seminar on algorithms for playing games of various types, especially turn-based games with full information (chess, go, hex, etc.). We will focus on practical algorithms and techniques reaching high real-world strength. We will be also discussing latest results and current open problems.
Aim of the course - Czech
Last update: T_KTI (04.05.2012)

Naučit algoritmické techniky a metody používané při hraní her a ukázat jejich aplikovatelnost na podobné úlohy.

Literature -
Last update: RNDr. Jan Hric (16.10.2013)
  • Russel, Norvig: Artificial Intelligence: A Modern Approach
  • Gelly, Silver: Achieving Master Level Play in 9×9 Computer Go
  • Gelly, Wang, Munos, Teytaud: Modification of UCT with Patterns in Monte-Carlo Go
  • ICGA Journal, IEEE Transactions on Computational Intelligence and AI in Games
  • C.B.Browne, E.Powley, D.Whitehouse et al.; A Survey of Monte Carlo Tree Search Methods, IEEE Transactions on Computational Intelligence and AI in Games, vol 4, No 1, pp.1-43, IEEE, 2012.

Syllabus -
Last update: T_KTI (30.04.2016)

Basic methods and techniques of a domain are explained on a part of seminars. Next seminars are student's lectures to relevant topics based on published papers.

  • Standard algorithms for two-player games with perfect information - minimax, alfa-beta pruning, history heuristics and other heuristics

  • Monte Carlo method - multi-armed bandit problem and strategies for its solution, Monte Carlo Tree Search and various strategies (UCT, RAVE), machine learning and balancing in simulations

  • Exact search - proof number search, endgame search and search for local goal

  • Threat-based search - null move search, lambda search

  • Implementation techniques - effective implementation of game tree, transposition tables, parallelisation

  • Nonstandard applications - games with uncertainity and without perfect information (bridge, poker), general game playing, parallelization of tree search, optimisation problems as single-player games. General Game Playing.

Charles University | Information system of Charles University |