A game can be visualised with a directed graph, where each node is a game state and the edges are the players’ actions that lead to new game states. To obtain the winning condition of the game whilst avoiding the losing condition, the players must perform the correct actions in coalition. The goal is thus to find winning strategies for these games, which ensure that the winning condition is reached. For games with imperfect information, the players might not be able to distinguish some game states from each other, which makes finding strategies harder. With the multiplayer knowledge subset construction (MKBSC), one may reduce the original graph to an “expanded” graph, and from this new graph try to find winning strategies, that can later be translated back into the original game graph. In this report, we have investigated how we gain information in each iteration of the MKBSC. This was done by introducing e-trees, a mathematical tree construction that can visualise knowledge of the current game state for each player in the game. It was found that these e-trees can display how the knowledge develops for each player given any iteration of the MKBSC, and that they can provide an intuitive way of understanding how strategies are found in a game.

Ett spel kan visualiseras med en riktad graf, där varje nod är ett speltillstånd. Kanterna är spelarnas möjliga drag i spelet, där dragen leder till nya speltillstånd. För att vinna spelet utan att hamna i det förlorande tillståndet måste spelarna utföra de rätta dragen tillsammans. Målet är därför att hitta vinnande strategier i sådana spel, som garanterar att spelarna vinner. För spel med imperfekt information kan spelarna inte nödvändigtvis urskilja vissa speltillstånd från varandra, vilket gör det svårare att hitta vinnande strategier. Med den så kallade multiplayer knowledge subset construction (MKBSC) kan man reducera grafen för det imperfekta spelet till en enklare graf, och försöka hitta strategier i den nya grafen istället, för att sedan översätta den strategin så att den passar originalgrafen. I den här rapporten har vi undersökt hur man får information när man använder MKBSC, och vad man kan använda den informationen till. Det här gjordes genom att introducera “e-trees”, en matematisk trädkonstruktion som kan visualisera kunskapen för varje spelare i spelet. Vi kom fram till att MKBSC kan visualisera hur kunskapen för varje spelare utvecklas vid varje iteration av MKBSC, och att träden ger en mer intuitiv bild över hur strategier kan framställas ur ett spel.