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.
Last update: T_KTI (16.05.2011)
Seminář zaměřený na algoritmy pro hraní her různých typů, zejména však
tahových her dvou hráčů s úplnou informací (šachy, go, hex, ...).
Důraz bude kladen především na praktické techniky a reálně používané
algoritmy dosahující dobrého herního výkonu.
Diskutovat budeme i nad nejnovějšími výsledky a současnými otevřenými
problémy.
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. http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=true&arnumber=6145622
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 a další časopisecké články.
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. http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=true&arnumber=6145622
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
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.
Last update: T_KTI (30.04.2016)
Na části seminářů jsou formou přednášky vysvětleny základní techniky z oblasti. Další část je referativní seminář založený na publikovaných článcích z oblasti.
Standardní algoritmy pro řešení her dvou hráčů s úplnou informací - minimax, alfa-beta prořezávání, historická heuristika a další heuristiky.
Monte Carlo metoda - multi-armed bandit problem a strategie jeho řešení, Monte Carlo stromy a strategie jejich procházení (UCT, RAVE), strojové učení a vyvažování v simulacích.
Exaktní prohledávání - proof number search, koncovky a lokální cíle.
Prohledávání založené na hrozbách - null move search, lambda search.
Implementační techniky - efektivní implementace herního stromu, transpoziční tabulky, paralelizace.
Nestandardní aplikace - hraní za nejistoty a s neúplnou informací (bridge, poker), hraní obecných her, paralelizace stromového prohledávání, optimalizační problémy jako hry jednoho hráče. General Game Playing.
