Finding strategies for games have been of interest tohumans throughout history. With the advancement of technologyand the way the financial market is compounded, enormous timeand resources are spent on modelling real world problems asgames and searching for strategies modelled to enhance produc-tivity and rule out inefficiencies. This thesis aims to investigate the existence of strategies that would allow players (agents)to complete common objectives when one category of agentsalready have a given strategy. This is done through studyingan example and investigating the application and implicationof the introduction of an abstraction function. The performedstudy concluded that if such a function could be more rigorouslymathematically formulated, it could increase the effectiveness ofstrategy searches and synthesis in the field. / Människor har alltid varit intresserade avatt hitta strategier för spel. I och med teknikens utveckling ochfinansmarknadens uppbyggnad läggs enorm tid och resurser påatt modellera verkliga problem som spel och söka efter strategierför att öka produktiviteten och minska ineffektivitet. Syftet medrapporten är att undersöka om det finns strategier som gör detmöjligt för spelarna (agenterna) att uppnå gemensamma mål nären kategori av agenter redan har en given strategi. Detta görsgenom att studera ett exempel och undersöka tillämpningar ochkonsekvenserna av att införa en abstraktionsfunktion. I studiendrogs slutsatsen att om en sådan funktion kunde formulerasstrikt matematiskt skulle den kunna öka effektiviteten i strate-gisökningar inom området. / Kandidatexjobb i elektroteknik 2022, KTH, Stockholm

It is a notoriously difficult task to find winningstrategies for multi-agent games. Especially if one or multipleagents lack the information required to determine which statethe game is in. When this type of uncertainty arises in a gameit is referred to as a multi-agent game of imperfect information.In this project we designed and built a tool for strategysynthesis of multi-agent games against nature. The strategysynthesis was knowledge-based and therefore a multi-agentextension of the Knowledge Based Subset Construction, builtby a previous project group, was applied to the input games.This construction creates a new knowledge-based game, withreduced uncertainty compared to the initial multi-agent game ofimperfect information. We constructed the tool using a forwardsearch heuristic which meant that it would locate all existingwinning strategies.We study the performance of the tool by comparing itto a baseline approach relying solely on randomisation. Thiscomparison was performed on five different games. Our toolfound every relevant strategy for each game at least 35% fasterthan the baseline found the same amount of unique winningstrategies. If a strategy can win without transitioning througha state, then that state is not relevant and is not part of thestrategy. The comparison test for this game shows that the toolis working very well. / Det är ökänt svårt att hitta strategier för spel för fleragentspel. Speciellt om en eller flera agenter saknar informationen som krävs för att avgöra vilket tillstånd de befinner sig i. Dessa spel kallas för spel av imperfekt information.  I det här projektet designade och byggde vi ett verktyg för att syntetisera en strategi för fleragentspel mot naturen. Syntetisering var kunskapsbaserad och därför applicerades ett verktyg, Knowledge Based Subset Construction för fleragentspel som skapats av en tidigare grupp, på det önskade spelet. Denna konstruktion skapar ett nytt kunskapsbaserat spel, med minskad osäkerhet jämfört med det initiala flerspelarspelet av imperfekt information. Vi skapade vårt verktyg med en heuristik som bygger på framåt-sök. Detta resulterar i att den hittar alla vinnande strategier.  Vi valde att jämföra vårt verktyg med en slumpbaserad strategisyntes, för att undersöka hur snabbt verktyget är. Vi jämförde med fem olika spel. Verktyget fann alla relevanta vinnande strategier för spelen minst 35% snabbare än vad den slumpbaserade metoden kunde finna lika många unika vinnande strategier som vi. Om en strategi var vinnande utan att passera ett tillstånd var det tillståndet inte relevant och därför inte med i strategien Detta gör att vi anser verktyget som väl fungerande. / Kandidatexjobb i elektroteknik 2020, KTH, Stockholm

We study games on graphs, where a coalition of agents work against an adversarial nature to achieve an objective. The agents have to collaborate while making their moves simultaneously, while receiving differing information about the state of the game and without a means of agent-to-agent communication. Before the game starts the coalition agrees on a strategy profile, where each agent is provided with a strategy which it acts in accordance to. The challenge of finding a winning strategy profile, wherein the coalition achieves their objective regardless of any influence from the adversarial nature, is called the strategy synthesis problem. For games with coalitions consisting of more than one agent, the general case of the synthesis problem is undecidable. We formalize an abstraction construction of a game where a subset of agents with predetermined strategies are abstracted into the adversarial nature of another game, for the purpose of reducing the size of the coalition of agents and in turn reduce the complexity of the strategy synthesis problem. We then prove that any winning strategy profile in the new game with fewer agents is also winning in the original game when combined with the predetermined strategies. The most interesting case is reducing a game with a coalition of two agents into a game with a single agent, since the strategy synthesis problem is decidable for games with a single agent. This allows us to test the predetermined strategy of the abstracted agent to see if it is possible to create a winning strategy profile using it. If it is not possible then we can try a different strategy. This enables an iterative approach for solving the strategy synthesis problem instead of a deductive one. / I rapporten studeras spel på grafer där ett lag av agenter samarbetar mot en fientlig omvärld för att uppnå ett mål. Agenterna måste samarbeta och göra sina drag på samma gång trots att de inte kan kommunicera med varandra och att de har olika perspektiv på lagets situation. För att lyckas med detta kommer laget överens om en gemensam strategi som består av en specifik strategi för varje individuell agent. Utmaningen att hitta en vinnande gemensam strategi för laget kallas strategisyntesproblemet och är oavgörbart i det allmänna fallet, det finns bevisat ingen algoritm som löser problemet. Vi formaliserar en abstraktionskonstruktion som tar ett spel där en delmängd av agenterna har blivit tilldelade en strategi för att sedan abstrahera de agenterna in i omvärlden i ett annat spel. Tanken är att i-och-med att agenterna redan har strategier vet vi hur de kommer agera och därmed kan vi se dem som en förutsägbar variabel i det nya spelet vi konstruerar. I det nya spelet har vi då färre agenter att skapa strategier för vilket minskar komplexiteten av strategisyntesproblemet. Vi bevisar också att en vinnande gemensam strategi i det nya spelet kan användas tillsammans med de förbestämda strategierna för att vinna det originella spelet. Det mest intressanta fallet för rapporten är om det originella spelet har två agenter i laget, då det finns algoritmer för att lösa strategisyntesproblemet för ensamma agenter. När en agent abstraheras bort och ett spel med en agent kvarstår betyder det att dessa algoritmer kan appliceras. Om en vinnande strategi hittas har problemet lösts, om inte kan man utesluta de förbestämda strategin som den abstraherade agenten använde. Det möjliggör en iterativ testning och uteslutning av strategier som inte funnits tidigare.

Many real life problems can be modelled using multi-agent games played on finite graphs. When an agent cannot differentiate between game states, for example when a robot operates with a broken sensor, the game is classified as a game of imperfect information. This report focuses on non-deterministic multi-agent games of imperfect information or Multi-Agent Games of Imperfect Information Against Nature (MAGIIAN). Finding optimal strategies for these games is very hard due to the element of imperfect information as well as taking into account the multiple cooperating agents. Using a generalised version for multi-agent games of the known Knowledge Based Subset Construction (KBSC) algorithm may solve the problem of strategy synthesis for MAGIIAN. While the KBSC transforms the game into a game with perfect information, the multi-agent variant (MKBSC) instead yields another MAGIIAN. When applying the algorithm iteratively some games stop expanding while others expand seemingly boundlessly. This is referred to as stability and divergence respectively. Our research focuses on different patterns, called structural conditions, in the MAGIIAN and how they affect stability. By using an existing implementation of the MKBSC along with some newly developed algorithms we were able to iterate over different games and analyse different structural conditions. We have identified several structural conditions which affect stability. By reducing divergent games to only their core components with respect to divergence, a more careful examination of what causes divergence could be done. It reaffirmed earlier research that cycles are necessary in order for games to diverge. Observation overlap was found to not be a necessary condition for divergent games as counter examples to this was found. Games containing well formed observations were found to stabilise within one iteration. Our research has also lead us to believe that it is impossible for structural conditions to properly classify divergence. / Olika typer av autonoma problem kan modelleras med hjälp av fleragentsspel spelade på ändliga grafer. Spel där en agent ej kan urskilja mellan två tillstånd, till exempel när en robot arbetar med trasiga sensorer, klassas som spel med ofullständig information. Vår rapport fokuserar på ickedeterministiska fleragentsspel med ofullständig information, även kallat Multi-Agent Games of Imperfect Information Against Nature (MAGIIAN). Att hitta optimala strategier för dessa spel är mycket svårt både på grund av den ofullständiga informationen och på grund av flertalet agenter som ska samarbeta. Användandet av en generaliserad variant för fleragentspel av den kända Knowledge Based Subset Construction (KBSC) algoritmen kan hjälpa att hitta vinnande strategier för MAGIIAN. Medan KBSC algoritmen transformerar spelet till ett spel med fullständig information, så ger fleragentsvarianten istället ännu ett MAGIIAN. Om man applicerar algoritmen många gånger kommer vissa spel sluta att växa medan andra fortsätter växa gränslöst. Detta kallas att spelen är stabila eller divergeranta. Vår rapport fokuserar på olika strukturer i dessa spel och hur dessa påverkar stabiliteten. Genom att använda en implementation av MKBSC tillsammans med nya algoritmer har vi itererat över många olika spel och analyserat olika strukturer. Vi har hittat flertalet strukturer som påverkar stabiliteten. Genom att reducera divergenta spel så att alla kvarvarande komponenter krävs för divergens, kunde divergenses orsaker noggrannt undersökas. Detta bekräftade tidigare påståenden om att cykler krävs för divergens. Därefter motbevisades att överlappande observationer krävdes för divergens med hjälp av motexempel. Spel innehållandes välformade observationer visades stabilisera efter en iteration av MKBSC:n.

When analyzing situations involving intelligent agents with objectives, it can be helpful to use discrete games as models. Within such game models the synthesis of winning strategies is of interest, and many algorithmic methods have been developed for this purpose. This project focused on a less tractable game type, involving a coalition of players without the ability to communicate. For this type of game we propose two methods for exploring knowledge-based strategies. One is an extension of the previously developed Multiplayer Knowledge- Based Subset Construction with the additional assumption of action observability within the coalition. The other is a novel method called Epistemic Expansion, which assumes that the coalition coordinates before playing the game. We demonstrate how these methods can be used to help find winning strategies in example games with relevant properties. / Diskreta spel kan utgöra lämpliga modeller för många situationer där intelligenta spelare är inblandade. I dessa modellspel är det av intresse att hitta vinnande strategier och många algoritmer har utvecklats i detta syfte. I detta projekt undersöker vi spel i vilka en koalition av spelare med ett gemensamt mål ska samarbeta utan kommunikation. För att underlätta syntesen av vinnande strategier är det lämpligt att följa hur spelarnas kunskapsläge utvecklas under spelets gång. Vi föreslår två kunskapsbaserade konstruktioner för att modellera två skilda antaganden. Det första är att spelarna kan observera varandras handlingar, och det andra är att koalitionen har möjlighet att skapa en koordinerad strategi innan spelet börjar. Vi visar hur dessa konstruktioner kan användas för att syntetisera vinnande strategier i utvalda exempelspel. / Kandidatexjobb i elektroteknik 2020, KTH, Stockholm

The aim of this project was to improve upon a toolfor strategy synthesis for multi-agent games of imperfect informationagainst nature. Another objective was to compare the toolwith the original tool we improved upon and the Strategic ModelChecker (SMC). For the strategy synthesis, an existing extensionfor expanding the games called the Multi-Agent Knowledge-Based Subset Construction was used. The construction creates anew knowledge-based game where strategies can be tested. Thestrategies were synthesized for the individual agents and thenjoint profiles of the individual strategies were tested to see ifthey were winning.Four different algorithms for going through the game graphswere tested against the other existing tools. The new andimproved tool was faster at synthesizing a strategy than both theold tool and the SMC for almost all games tested. Although forthe games where the new tool is out-performed, results indicateit to be due to a combination of chance and how the games areperceived by the tools. No algorithm or tool proved to be thebest performing for all games. / Syftet med detta projekt var att förbättra ettexisterande verktyg för att syntetisera strategier för fleragentspelav imperfect information mot naturen. Därefter också jämföraverktyget med original verktyget och med ett verktyg somheter the strategic model checker (SMC). För syntetiseringenav strategier användes ett existerande verktyg för att expanderaspel, som kallas Multi-Agent Knowledge-Based Subset Construction.Konstruktionen skapar ett kunskapsbaserat spel därstrategierna kan bli testade. Strategierna syntetiserades för deenskilda agenterna och därefter skapades en sammansatt profilav strategier, som då testades för att se om det var en vinnandestrategi.Fyra olika algoritmer för att gå igenom spelgrafen testadesoch jämfördes med de andra verktygen. Det nya och förbättradeverktyget var snabbare att syntetisera en strategi än både detgamla verktyget och SMC verktyget för nästan alla spel somtestades. Fast, för spelen då nya verktyget inte var snabbast så indikerar resultaten på att detta är p.g.a. en kombination avslump och hur spelen ses på av verktygen. Ingen algoritm ellerverktyg visade sig vara det snabbaste för samtliga spel. / 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.