Depth-limited approaches in adversarial team games

Zero-sum extensive-form games have been widely studied in the scientific literature. For instance, the Libratus bot defeated the top 4 human players of Texas Hold’em Poker on January 2017. However, these techniques do not directly apply to games with 3 or more players, which represent nowadays one of the most challenging problems in artificial intelligence. In this work, we will focus on the Bridge game which presents 2 teams, each composed of 2 players. We will consider parametric versions of Bridge, where the parameter is the number of cards. We will study the limits of counter-factual regret minimization algorithms when applied to these games and we will develop alternative techniques to compute an equilibrium. We will focus on testing ways to estimate subgame values efficiently and effectively. With these results, we will adapt depth-limited techniques to the team vs opponent environment of Bridge playing phase. We will use this innovative approach to solve nested subgames and simulate games between bots.

I giochi extensive-form a somma zero sono stati studiati a lungo nella letteratura scientifica. Per esempio, il bot Libratus è riuscito a sconfiggere i 4 migliori giocatori di Poker Texas Hold’em nel gennaio 2017. Tuttavia, le tecniche sviluppate finora non possono essere applicate direttamente ai giochi con 3 o più giocatori, rappresentando quindi una delle sfide moderne più difficili per l’intelligenza artificiale. In questa tesi ci concentreremo su Bridge, un gioco di carte giocato da 4 giocatori divisi in 2 squadre. Utilizzeremo delle versioni parametriche del gioco con un numero variabile di carte nel mazzo. Studieremo i limiti degli algoritmi di counterfactual regret minimization quando applicati ai giochi a più di 2 giocatori e svilupperemo tecniche alternative per il calcolo di un equilibrio. Ci concentreremo sul calcolo del valore di un generico subgame in maniera efficace ed efficiente. Noti questi risultati, adatteremo le tecniche di depth-limited solving allo scenario team contro avversario della fase di gioco di Bridge. Useremo questo approccio innovativo per risolvere i cosiddetti nested subgames e simuleremo delle partite giocate dai nostri bot per valutarne le performance.