Epistemic Structures for Strategic Reasoning in Multi-Player Games

Sammanfattning: 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.