Herní algoritmy - NAIL103

• Anglický název: Game Algorithms
• Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2022
• Semestr: zimní
• E-Kredity: 3
• Rozsah, examinace: zimní s.:0/2, Z [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: zrušen
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• Další informace: http://pasky.or.cz/vyuka/2012-AIL103/
• Garant: RNDr. Jan Hric
• Třída: Informatika Mgr. - Teoretická informatika
• Kategorizace předmětu: Informatika > Teoretická informatika

Anotace

čeština

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.

Poslední úprava: T_KTI (16.05.2011)

angličtina

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.

Poslední úprava: T_KTI (16.05.2011)

Cíl předmětu

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

Poslední úprava: T_KTI (04.05.2012)

Literatura

čeština

• 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

Poslední úprava: Hric Jan, RNDr. (16.10.2013)

angličtina

• 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

Poslední úprava: Hric Jan, RNDr. (16.10.2013)

Sylabus

čeština

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.

Poslední úprava: T_KTI (30.04.2016)

angličtina

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.

Poslední úprava: T_KTI (30.04.2016)