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
Investigation of a Knowledge-Based Subset Construction for Multi-Player Games of Imperfect Information
KTH, School of Engineering Sciences (SCI).
KTH, School of Engineering Sciences (SCI).
2018 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesisAlternative title
Undersökning av en kunskapsbaserad delmängdskonstruktion för flerspelarspel med ofullständig information (Swedish)
Abstract [en]

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.

Abstract [sv]

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.

Place, publisher, year, edition, pages
2018. , p. 30
Series
TRITA-SCI-GRU ; 2018-119
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:kth:diva-231026OAI: oai:DiVA.org:kth-231026DiVA, id: diva2:1221520
Supervisors
Examiners
Available from: 2018-06-20 Created: 2018-06-20 Last updated: 2018-06-20Bibliographically approved

Open Access in DiVA

fulltext(2061 kB)8 downloads
File information
File name FULLTEXT01.pdfFile size 2061 kBChecksum SHA-512
ac2095b1a286f1deee265ad32afb026d8d5c51c848fb318e8f857d2b74fb5ffbaeb8fd5c217f73338b50fb9a04ed918c706314423adb3a9ebc6067ec041f83c7
Type fulltextMimetype application/pdf

By organisation
School of Engineering Sciences (SCI)
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 8 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: 19 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