Deep-Hedge MCCFR: An algorithm for solving imperfect information games.
Marcin Ziemiński · Jagiellonian University Repository (Jagiellonian University) · 2020
W ostatnim czasie poczyniono znaczne postępy w dziedzinie algorytmów uczących się rozwiązywać trudne problemy decyzyjne. Dominujące rozwiązania oparte o deep reinforcement learning (Deep RL) okazały się niezwykle skuteczne, pokonując najlepszych ludzkich graczy w gry takie jak Go, StarCraft II lub te pochodzące z Atari. Algorytmy te dostosowują swoje zachowania na podstawie zgromadzonego doświadczenia i otrzymywanych sygnałów.Jednak z drugiej strony, metody te nie są dobrze dostosowane do środowisk wieloagentowych, które z natury są niestacjonarne. Agenci funkcjonujący w takim kontekście równolegle kształtują swoje strategie, wpływając na zmienny charakter całego środowiska. Ponadto, działają oni w realiach niepełnej informacji, gdyż nie mają wglądu w wiedzę, do której dostęp mają wyłącznie ich przeciwnicy. To wszystko sprawia, że problem optymalizacji jest trudniejszy, ale przy tym podatny na analizę z punktu widzenia teorii gier.Teoria gier znajduje się u podstaw dominujących algorytmów dla gier o niepełnej informacji. Program o nazwie Pluribus, bazujący na algorytmie Counterfactual Regret Minimization (CFR), pokonał czołowych profesjonalnych graczy w sześcioosobowym No-Limit Texas Hold'em. CFR to adaptacyjny algorytm, który agreguje informacje dla każdego stanu gry w sposób tabelaryczny, co służy do usprawnienia strategii w następujących po sobie iteracjach. Jednak zastosowanie tego algorytmu w przypadku gier o dużym rozmiarze wymaga szerokiej wiedzy eksperckiej i przeszukiwania drzewa gry w czasie wykonania.W tej pracy staramy się połączyć dwa powyższe paradygmaty. Proponujemy rozwiązanie oparte o CFR, które nawiązuje do rozwoju dokonanego w dziedzinie, którą jest deep learning. Nasz algorytm, który nazywamy Deep-Hedge MCCFR, modeluje strategie poszczególnych agentów przy użyciu sieci neuronowych. Strategie te są ulepszane dzięki doświadczeniu zdobytemu podczas symulowanej gry. Pokazujemy, że proponowany algorytm osiąga w praktyce dobre wyniki dla różnych gier, nie wymagając przy tym wiedzy eksperckiej.