Analogous to how the Knowledge-Based Subset Construct (KBSC) can transform games of imperfect information against nature into games of perfect information, making it easier to find winning strategies for objectives in these games, the multi-agent knowledge-based subset construct (MKBSC) can be used to find winning strategies in multi-agent games of imperfect information. The difference between the two algorithms is that the generalized version can be applied multiple times, which is interpreted as the agent’s considering not just their own knowledge of the game, but also their knowledge of the other agents, and the knowledge of the other agent’s knowledge about their own knowledge, etc... Why higher-level knowledge is required to achieve some objectives is intuitive when the level of knowledge is low. However, we do not know yet of any meaningful objective in a game that requires higher than level two knowledge in order to be achievable, and why this higher level of knowledge is needed. In this report, we try to find an objective that only has a winning strategy for more than level two knowledge and interpret what type of objective this is. A large portion of the work went into finding a way to represent all possible sets of outcomes of a game in a finite manner. This allows us to distinguish the strategic abilities that emerge when considering higher-level knowledge from the strategic abilities that were available at lower levels of knowledge. In the results section, we introduced an approach to analyzing multi-agent games of imperfect information by presenting the outcomes as a graph, termed the graph of outcomes. This representation was applied to a game called the Cart-pushing to illustrate the variation in outcomes of different levels of knowledge. We then listed the graphs of outcomes for knowledge levels 0, 1, 2, 3, and 4. One interesting thing we found is that only the players who consider level-4 knowledge can have a winning strategy for a certain reachability objective, and this objective was not achievable in earlier levels of knowledge.

Liksom Knowledge-Based Subset Construct (KBSC) kan omvandla spel med ofullständig information mot naturen till spel med perfekt information, vilket gör det lättare att hitta vinnande strategier för ett mål i dessa spel, så kan Multi-agent knowledge-based subset construct (MKBSC) användas för att hitta vinnande strategier i multi-agent spel med ofullständig information. Skillnaden mellan de två algoritmerna är att den generaliserade versionen kan tillämpas flera gånger, vilket tolkas som att agenten inte bara överväger sin egen kunskap om spelet, utan också sin kunskap om de andra agenterna, och kunskapen om de andra agenternas kunskap om sin egen kunskap, etc... Varför agenterna behöver överväga kunskaper på högre nivå för att ha en vinnande strategi kan vara intuitivt när kunskapsnivån som används är låg. Vi känner dock inte till ett meningsfullt mål som kräver en kunskapsnivå högre än nivå 2 för att en vinnande strategi ska finnas, och vi vet inte varför denna högre kunskapsnivå blir nödvändig. I denna rapport försöker vi hitta ett mål som endast har en vinnande strategi för mer än nivå två kunskap och tolka vilken typ av mål detta är. En stor del av arbetet gick till att hitta ett sätt att representera alla möjliga uppsättningar av resultat av ett spel på ett ändligt sätt. Detta gjordes för att skilja de strategiska förmågorna som dyker upp när man tänker på högre kunskapsnivåer, från de strategiska förmågorna som finns tillgängliga på lägre kunskapsnivåer. I resultatet introducerade vi ett tillvägagångssätt för att analysera multi-agent spel med ofullständig information genom att presentera resultaten som en graf som vi kallar resultatsgrafen. Denna representation tillämpades på spelet som används i projeket cart-pushing game och illustrerar variationen i resultat för olika kunskapsnivåer. Våra resultat visar resultatgrafer för kunskapsnivåer 0, 1, 2, 3 och 4. Ett intressant resultat som vi upptäckte är att endast spelare som använder kunskapsnivå 4 kan ha en vinnande strategi för ett reachability objective, vilket inte var möjligt på de lägre kunskapsnivåer.