PředmětyPředměty(verze: 680)
Předmět, akademický rok 2013/2014
.
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 2012
Semestr: zimní
Rozsah, examinace: zimní s.:0/2 Z [hodiny/týden]
Body: zimní s.:2
E-Kredity: zimní s.:3
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština
Další informace: http://pasky.or.cz/vyuka/2012-AIL103/
Garant: Mgr. Petr Baudiš
RNDr. Jan Hric
Třída: Informatika Mgr. - Teoretická informatika
Klasifikace: Informatika > Teoretická informatika
Anotace -
Poslední úprava: 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.
Cíl předmětu
Poslední úprava: 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.

Literatura -
Poslední úprava: 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

Sylabus -
Poslední úprava: T_KTI (04.05.2012)

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.

 
Univerzita Karlova v Praze | Informační systém UK