Convergence of UCT in Imperfect Information Games

Táto práca sa zaoberá algoritmom the Upper confidence Tree, v skratke UCT, ktorý patrí do velkej rodiny the Monte Carlo Tree Search algoritmov. Zamerali sme sa na zero-sum hry pre dvoch hrácov. Pozorovali sme vlastnosti UCT, aby sme zistili, preco konverguje tak rýchlo a kedy UCT nekonverguje k Nashovmu equilibriu. Empiricky sme analyzovali konvergenciu UCT v jednoduchých maticových hráca v sekvencných hrách so simultánnymi tahmi rôznej komplexnosti. Použili sme náhodne generované hry na hladanie problémov konvergencie UCT. Priamo sme porovnali dve modifikácie, menovite Sliding Window a nedeterministickú modifikáciu. Obidve majú svoje plusy a mínusy. Navrhli sme zlepšenie nedeterministickej modifikácie.This thesis deals with the Upper confidence Tree algorithm, which belongs to the big family of the Monte Carlo Tree Search algorithms. We focused on two-player zero-sum games. We observed properties of UCT to find out, why it converges so fast and when UCT doesn't converge to the Nash equilibria. We empirically analyzed a convergence of UCT in simple matrix games and sequential simultaneous move games of various complexity. We used randomly generated games for finding problems of a covergence of UCT. We directly compared two modifications, namely the sliding window and the non-deterministic modification. Both of them have their pros and cons. We propose an improvement of the non-deterministic modification