When analyzing situations involving intelligent agents with objectives, it can be helpful to use discrete games as models. Within such game models the synthesis of winning strategies is of interest, and many algorithmic methods have been developed for this purpose. This project focused on a less tractable game type, involving a coalition of players without the ability to communicate. For this type of game we propose two methods for exploring knowledge-based strategies. One is an extension of the previously developed Multiplayer Knowledge- Based Subset Construction with the additional assumption of action observability within the coalition. The other is a novel method called Epistemic Expansion, which assumes that the coalition coordinates before playing the game. We demonstrate how these methods can be used to help find winning strategies in example games with relevant properties. / Diskreta spel kan utgöra lämpliga modeller för många situationer där intelligenta spelare är inblandade. I dessa modellspel är det av intresse att hitta vinnande strategier och många algoritmer har utvecklats i detta syfte. I detta projekt undersöker vi spel i vilka en koalition av spelare med ett gemensamt mål ska samarbeta utan kommunikation. För att underlätta syntesen av vinnande strategier är det lämpligt att följa hur spelarnas kunskapsläge utvecklas under spelets gång. Vi föreslår två kunskapsbaserade konstruktioner för att modellera två skilda antaganden. Det första är att spelarna kan observera varandras handlingar, och det andra är att koalitionen har möjlighet att skapa en koordinerad strategi innan spelet börjar. Vi visar hur dessa konstruktioner kan användas för att syntetisera vinnande strategier i utvalda exempelspel. / Kandidatexjobb i elektroteknik 2020, KTH, Stockholm
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-297693 |
| Date | January 2020 |
| Creators | Janson, Axel, Du Rietz, Marc |
| Publisher | KTH, Skolan för elektroteknik och datavetenskap (EECS) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-EECS-EX ; 2020:170 |
Page generated in 0.0016 seconds