It is a notoriously difficult task to find winningstrategies for multi-agent games. Especially if one or multipleagents lack the information required to determine which statethe game is in. When this type of uncertainty arises in a gameit is referred to as a multi-agent game of imperfect information.In this project we designed and built a tool for strategysynthesis of multi-agent games against nature. The strategysynthesis was knowledge-based and therefore a multi-agentextension of the Knowledge Based Subset Construction, builtby a previous project group, was applied to the input games.This construction creates a new knowledge-based game, withreduced uncertainty compared to the initial multi-agent game ofimperfect information. We constructed the tool using a forwardsearch heuristic which meant that it would locate all existingwinning strategies.We study the performance of the tool by comparing itto a baseline approach relying solely on randomisation. Thiscomparison was performed on five different games. Our toolfound every relevant strategy for each game at least 35% fasterthan the baseline found the same amount of unique winningstrategies. If a strategy can win without transitioning througha state, then that state is not relevant and is not part of thestrategy. The comparison test for this game shows that the toolis working very well. / Det är ökänt svårt att hitta strategier för spel för fleragentspel. Speciellt om en eller flera agenter saknar informationen som krävs för att avgöra vilket tillstånd de befinner sig i. Dessa spel kallas för spel av imperfekt information. I det här projektet designade och byggde vi ett verktyg för att syntetisera en strategi för fleragentspel mot naturen. Syntetisering var kunskapsbaserad och därför applicerades ett verktyg, Knowledge Based Subset Construction för fleragentspel som skapats av en tidigare grupp, på det önskade spelet. Denna konstruktion skapar ett nytt kunskapsbaserat spel, med minskad osäkerhet jämfört med det initiala flerspelarspelet av imperfekt information. Vi skapade vårt verktyg med en heuristik som bygger på framåt-sök. Detta resulterar i att den hittar alla vinnande strategier. Vi valde att jämföra vårt verktyg med en slumpbaserad strategisyntes, för att undersöka hur snabbt verktyget är. Vi jämförde med fem olika spel. Verktyget fann alla relevanta vinnande strategier för spelen minst 35% snabbare än vad den slumpbaserade metoden kunde finna lika många unika vinnande strategier som vi. Om en strategi var vinnande utan att passera ett tillstånd var det tillståndet inte relevant och därför inte med i strategien Detta gör att vi anser verktyget som väl fungerande. / Kandidatexjobb i elektroteknik 2020, KTH, Stockholm
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-297694 |
| Date | January 2020 |
| Creators | Lycken, Jakob, Westerlund, Simon |
| Publisher | KTH, Skolan för elektroteknik och datavetenskap (EECS) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-EECS-EX ; 2020:171 |
Page generated in 0.0023 seconds