Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Epistemic Structures for Strategic Reasoning in Multi-Player Games
KTH, School of Electrical Engineering and Computer Science (EECS).
KTH, School of Electrical Engineering and Computer Science (EECS).
2019 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesisAlternative title
Kunskapsstrukturer för strategiska resonemang i flerspelarspel (Swedish)
Abstract [en]

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.

Abstract [sv]

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.

Place, publisher, year, edition, pages
2019.
Series
TRITA-EECS-EX ; 2019:325
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:kth:diva-255156OAI: oai:DiVA.org:kth-255156DiVA, id: diva2:1338657
Subject / course
Computer and Systems Sciences
Supervisors
Examiners
Available from: 2019-07-29 Created: 2019-07-23 Last updated: 2019-07-29Bibliographically approved

Open Access in DiVA

fulltext(2963 kB)11 downloads
File information
File name FULLTEXT01.pdfFile size 2963 kBChecksum SHA-512
a23c8ddd84080619ac5123227de8e2924b2d80b327c228679c73d29c77ee7b73a9b91b3370d6cd003ff779954a53977798f9dbd6a57958110e93d36c13a5bb2c
Type fulltextMimetype application/pdf

By organisation
School of Electrical Engineering and Computer Science (EECS)
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 11 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 37 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf