Many problems involving decision making withimperfect information can be modeled as extensive games. Onefamily of state-of-the-art algorithms for computing optimal playin such games is Counterfactual Regret Minimization (CFR).The purpose of this paper is to explore the viability of CFRalgorithms on the board game Stratego. We compare differentalgorithms within the family and evaluate the heuristic method“imperfect recall” for game abstraction. Our experiments showthat the Monte-Carlo variant External CFR and use of gametree pruning greatly reduce training time. Further, we show thatimperfect recall can reduce the memory requirements with only aminor drop in player performance. These results show that CFRis suitable for strategic decision making. However, solutions tothe long computation time in high complexity games need to beexplored. / Många beslutsproblem med dold informationkan modelleras som spel på omfattande form. En familj avledande algoritmer för att beräkna optimal strategi i sådana spelär Counterfactual Regret Minimization (CFR). Syftet med dennarapport är att undersöka effektiviteten för CFR-algoritmer ibrädspelet Stratego. Vi jämför olika algoritmer inom familjen ochutvärderar den heuristiska metoden “imperfekt minne” för spelabstraktion.Våra experiment visar att Monte-Carlo-variantenExternal CFR och användning av trimning av spelträd kraftigtminskar träningstiden. Vidare visar vi att imperfekt minne kanminska algoritmens lagringskrav med bara en mindre förlust ispelstyrka. Dessa resultat visar att CFR är lämplig för strategisktbeslutsfattande. Lösningar på den långa beräkningstiden i spelmed hög komplexitet måste dock undersökas. / Kandidatexjobb i elektroteknik 2021, KTH, Stockholm

We study games where a team of agents needs to collaborate against an adversary to achieve a common goal. The agents make their moves simultaneously, and they have different perceptions about the system state after each move, due to different sensing capabilities. Each agent can only act based on its own experiences, since no communication is assumed during the game. However, before the game begins, the agents can agree on some strategy. A strategy is winning if it guarantees that the agents achieve their goal regardless of how the opponent acts. Identifying a winning strategy, or determining that none exists, is known as the strategy synthesis problem. In this thesis, we only consider a simple objective where the agents must force the game into a given state. Much of the literature is focused on strategies that either rely on that the agents (a) can remember everything that they have perceived or (b) can only remember the last thing that they have perceived. The strategy synthesis problem is (in the general case) undecidable in (a) and has exponential running time in (b). We are interested in the middle, where agents can have finite memory. Specifically, they should be able to keep a finite-state machine, which they update when they make new observations. In our case, the internal state of each agent represents its knowledge about the state of affairs. In other words, an agent is able to update its knowledge, and act based on it. We propose an algorithm for constructing the finite-state machine for each agent, and assigning actions to the internal states before the game begins. Not every winning strategy can be found by the algorithm, but we are convinced that the ones found are valid ones. An important building block for the algorithm is the knowledge-based subset construction (KBSC) used in the literature, which we generalise to games with multiple agents. With our construction, the game can be reduced to another game, still with uncertain state information, but with less or equal uncertainty. The construction can be applied arbitrarily many times, but it appears as if it stabilises (so that no new knowledge is gained) after only a few steps. We discuss this and other interesting properties of our algorithm in the final chapters of this thesis. / Vi studerar spel där ett lag agenter behöver samarbeta mot en motståndare för att uppnå ett mål. Agenterna agerar samtidigt, och vid varje steg av spelet så har de olika uppfattning om spelets tillstånd. De antas inte kunna kommunicera under spelets gång, så agenterna kan bara agera utifrån sina egna erfarenheter. Innan spelet börjar kan agenterna dock komma överrens om en strategi. En sådan strategi är vinnande om den garanterar att agenterna når sitt mål oavsett hur motståndaren beter sig. Att hitta en vinnande strategi är känt som syntesproblemet. I den här avhandlingen behandlar vi endast ett enkelt mål där agenterna måste tvinga in spelet i ett givet tillstånd. Mycket av litteraturen handlar om strategier där agenterna antingen antas (a) kunna minnas allt som de upplevt eller (b) bara kunna minnas det senaste de upplevt. Syntesproblemet är (i det generella fallet) oavgörbart i (a) och tar exponentiell tid i (b). Vi är intressede av fallet där agenter kan ha ändligt minne. De ska kunna ha en ändlig automat, som de kan uppdatera när de får nya observationer. I vårt fall så representerar det interna tillståndet agentens kunskap om spelets tillstånd. En agent kan då uppdatera sin kunskap och agera utifrån den. Vi föreslår en algoritm som konstruerar en ändlig automat åt varje agent, samt instruktioner för vad agenten ska göra i varje internt tillstånd. Varje vinnande strategi kan inte hittas av algoritmen, men vi är övertygade om att de som hittas är giltiga. En viktig byggsten är den kunskapsbaserade delmängskonstruktionen (KBSC), som vi generaliserar till spel med flera agenter. Med vår konstruktion kan spelet reduceras till ett annat spel som har mindre eller lika mycket osäkerhet. Detta kan göras godtyckligt många gånger, men det verkar som om att ingen ny kunskap tillkommer efter bara några gånger. Vi diskuterar detta vidare tillsammans med andra intressanta egenskaper hos algoritmen i de sista kapitlen i avhandlingen.