Undersökning av en kunskapsbaserad delmängdskonstruktion för flerspelarspel med ofullständig information

Games can be used to model different autonomous decision problems to find strategies ac- cording to which the involved agents should act. When the agents in these problems cannot differentiate between certain states, for example due to a damaged sensor, the modeled game is said to be of imperfect information. The strategies in these types of games are much harder to find compared to games of perfect information, and it becomes even harder to find strategies when several agents are cooperating to solve a specific task in a so-called multi-player game of imperfect information. We study a multi-player variant of a well known knowledge-based subset construction for games of imperfect information, which now considers a coalition of players working towards a common goal. This generalized construction reduces uncertainty in a multi-player game of imperfect information by creating a new, knowledge-based game. This reduction is useful since winning strategies found in the knowledge-based game can be translated back into winning strategies in the original game. The properties of this multi-player knowledge-based subset construction (MKBSC) are still not fully known. Unlike the single-player knowledge-based subset construction, the MKBSC is not guaranteed to give knowledge-based games of perfect information, which complicates the strategy synthesis. It is possible to apply the construction to the new game, creating another knowledge-based game of increased epistemic depth. It- erating the construction on the knowledge-based games may cause an unbounded increase in the number of states, causing the game to diverge. We investigate the MKBSC by applying the construction to different multi-player games of imperfect information and classify the properties in the original game that may cause the constructed game to behave in certain ways. We observe that games which do not contain any observation overlaps or cycles within the game graph always stabilize when the construction is iterated on the game. These types of games are preferred when using the construction to create games which simplify strategy synthesis, since the number and size of created knowledge-based games is limited.Spel kan användas för att modellera olika typer av autonoma beslutsproblem för att hitta strategier enligt vilka de ingående agenterna bör agera. När agenterna i problemen inte kan skilja på specifika tillstånd, exempelvis på grund av en skadad sensor, säger vi att det mod- ellerade spelet har ofullständig information. Strategierna i dessa spel är mycket svårare att hitta jämfört med spel med fullständig information, och det blir ännu svårare när det är flera samverkande agenter i ett så kallat flerspelarspel med ofullständig information. Vi undersöker en flerspelarvariant av en välkänd kunskapsbaserad delmängdskonstruktion för spel med ofullständig information, som istället behandlar koalitioner av spelare som sam- marbetar mot ett gemensamt mål. Den här generaliserade konstruktionen reducerar osäker- heten i ett flerspelarspel med ofullständig information genom att skapa ett nytt, kunskaps- baserat spel. Denna reduktion är användbar eftersom vinnande strategier i det kunskapsbaser- ade spelet kan översättas tillbaka till vinnande strategier i orginalspelet. Egenskaperna hos denna kunskapsbaserade delmängdskonstruktion för flerspelarspel (MKBSC) är fortfarande inte helt kända. Till skillnad från konstruktionen för enspelarspel är inte MKBSC:n garan- terad att ge kunskapsbaserade spel av perfekt information, vilket komplicerar strategisyntesen. Det är dessutom möjligt att applicera konstruktionen på det nya spelet och skapa ett nytt kunskapsbaserat spel med ökat epistemsikt djup. Att iterera konstruktionen på de kunskaps- baserade spelen kan orsaka en obegränsad ökning av mängden tillstånd, och få spelet att divergera. Vi undersöker MKBSC:n genom att applicera den på olika flerspelarspel med ofullständig information och kategorisera egenskaper i det originalspelet som kan få det konstruerade spelet att bete sig på vissa sätt. Vi observerar att spel som inte innehåller några överlappande observationer eller cykler i spelgrafen alltid stabiliseras när konstruktionen itereras på spelet. De här typen av spel föredras när konstruktionen används för att skapa spel som förenklar strategisyntes, då antalen och storleken på de kunskapsbaserade spelen är begränsade