Bridging the Gap: Towards Unified Approach to Perfect and Imperfect Information Games

Abstract

From the onset of AI research, games have played an important part, serving as a benchmark for progress in artificial intelligence. Recent approaches using search in combination with learning from self-play have shown strong performance and the ability to generalize across a wide range of perfect information games. In contrast, the leading algorithms for imperfect information traditionally used a small, abstract version of a game and solved this abstraction in one go. This thesis introduces a chain of improvements for imperfect information algorithms that culminates in two significant milestones that helped bridge the gap between perfect and imperfect information games. The first milestone is DeepStack - the first agent that successfully used a combination of sound search and a learned value function in imperfect information games. This led to the first AI to achieve victory over human professional players in no-limit poker. The second milestone is Player of Games - a universal algorithm that can master both perfect and imperfect information games starting from scratch. 1

Od začiatku výskumu umelej inteligencie zohrávali hry dôležitú úlohu a slúžili ako ukazo- vatel'pokroku v oblasti umelej inteligencie. Algoritmy, ktoré kombinovali prehl'adávanie so strojovým učením z vlastných skúseností, ukázali dobré výsledky a schopnost' gene- ralizovat' v širokej škále hier s úplnou informáciou. Na druhej strane, tradične najlepšie algoritmy pre hry s neúplnou informáciou používali zjednodušenú, abstraktnú verziu hry, ktorú potom riešili ako celok. Táto práca predstavuje rad vylepšení algoritmov s neúplnou informáciou a vyvrcholí dvoma významnými míl'nikmi, ktoré pomohli preklenút' rozdiel medzi hrami s úplnou a neúplnou informáciou. Prvým míl'nikom je DeepStack - prvý agent, ktorý úspešne kombinoval teoreticky korektné prehl'adávanie s evalučnou funkciou natrénovanou pomocou strojového učenia v hrách s neúplnou informáciou. DeepStack po- tom dosiahol historicky prvé vít'azstvo umelej inteligencie nad profesionálnymi hráčmi v pokri s neobmedzenými stávkami. Druhým míl'nikom je "Player of Games" - univerzálny algoritmus schopný ovládnut' oba typy hier, s úplnou aj neúplnou informáciou. 1