2018/12/18 by Michal Šustr, Sustr, Michal, Vojtěch Kovařík +3 · 2 citations
Computer Science · Economics, Econometrics and Finance · #Artificial Intelligence in Games #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Reinforcement Learning in Robotics #Sports Analytics and Performance
paper · pdf · doi:10.48550/arxiv.1812.07351
openalex publication_date 2018/12/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Online game playing algorithms produce high-quality strategies with a\nfraction of memory and computation required by their offline alternatives.\nContinual Resolving (CR) is a recent theoretically sound approach to online\ngame playing that has been used to outperform human professionals in poker.\nHowever, parts of the algorithm were specific to poker, which enjoys many\nproperties not shared by other imperfect information games. We present a\ndomain-independent formulation of CR applicable to any two-player zero-sum\nextensive-form games that works with an abstract resolving algorithm. We\nfurther describe and implement its Monte Carlo variant (MCCR) which uses Monte\nCarlo Counterfactual Regret Minimization (MCCFR) as a resolver. We prove the\ncorrectness of CR and show an O(T-1/2)-dependence of MCCR's exploitability\non the computation time. Furthermore, we present an empirical comparison of\nMCCR with incremental tree building to Online Outcome Sampling and\nInformation-set MCTS on several domains.\n