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
DQN Tackling the Game of Candy Crush Friends Saga: A Reinforcement Learning Approach
KTH, School of Electrical Engineering and Computer Science (EECS).
2019 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
DQN applicerad på Candy Crush Friends Saga : Ett tillvägagångssätt med förstärkande inlärning (Swedish)
Abstract [en]

This degree project presents a reinforcement learning (RL) approach called deep Q-network (DQN) for learning how to play the game Candy Crush Friends Saga (CCFS). The DQN algorithm is implemented together with three extensions, which in 2015 resulted in a new state-of-the-art on the Atari 2600 domain. This thesis shows that DQN in combination with the three extensions is an appropriate method for learning how to play CCFS. The influence that each of the extensions has on the performance is investigated separately, and reasoning for why or why not these extensions make sense in this environment is provided.

CCFS is a stochastic game environment with many new features per level. This leads to a challenge when designing the reward function. This thesis investigates the impact of three different reward functions and reflects over why a certain type of design is more relevant.

The results presented show that the DQN approach is able to learn a policy that increases its performance compared to that of random game-play. However, at this stage the performance is not yet reaching that of human game-play, but with further research we believe that it is possible.

Abstract [sv]

Det här examensarbetet introducerar djupt Q-nätverk (DQN), ett tillvägagångssätt med förstärkande inlärning (RL), för att lära sig att spela spelet Candy Crush Friends Saga (CCFS). DQN implementeras tillsammans med tre tillägg, som 2015 resulterade i ett nytt toppresultat på Atari 2600-domänen. Detta examensarbete visar att DQN i kombination med de tre tilläggen är en lämplig metod för att lära sig att spela CCFS. Inverkan varje tillägg har på prestationen analyseras separat, och argument för och emot varför dessa tillägg är bra alternativ presenteras.

CCFS är ett stokastiskt spel med flera nya element per nivå. Detta inför svårigheter i modelleringen av belöningsfunktionen. Detta examensarbete undersöker tre olika belöningsfunktioner och reflekterar över varför en viss typ av design är mer lämplig.

Resultaten visar att DQN kan lära sig beslutstaganden som ökar dess prestation i jämförelse med slumpmässigt spel. Resultaten når i nuläget inte upp till mänsklig prestanda, men medytterligare forskning så tror vi att detta går att uppnå.

Place, publisher, year, edition, pages
2019. , p. 70
Series
TRITA-EECS-EX ; 2019:560
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:kth:diva-263313OAI: oai:DiVA.org:kth-263313DiVA, id: diva2:1368129
External cooperation
King
Supervisors
Examiners
Available from: 2019-11-18 Created: 2019-11-06 Last updated: 2019-11-18Bibliographically approved

Open Access in DiVA

fulltext(18210 kB)17 downloads
File information
File name FULLTEXT01.pdfFile size 18210 kBChecksum SHA-512
d75730557e8adc63e5175b602bb8f80c58f933fc3ee93996d0dec7ba7ccda3e8f5b111585abd4b4463c1b4e7991d01cb4acbc7c5fd8ad082d076a8238ed507d2
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: 17 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: 50 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