Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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
Attacking SameGame using Monte-Carlo Tree Search: Using randomness as guidance in puzzles
KTH, School of Computer Science and Communication (CSC).
2015 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

Since the birth of the computer, the creation of algorithms to beat humans in games has been a hot topic, algorithms that if successful often have vast implications. For some games and problems however, it has been notoriously difficult for computers to perform well. But in 2006 an algorithm known as Monte-Carlo Tree Search (MCTS) was invented that boosted the performance of computers in some of the difficult two-player games, e.g. computer Go. Around the same time researchers started to look into how MCTS could be applied to single-player domains, one of them was the puzzle of SameGame.

This thesis will continue the work on SameGame to further improve algorithms, ideas and knowledge on how to attack puzzles using MCTS. We mainly used a test set consisting of 250 randomly generated SameGame instances to evaluate the performance of various techniques. Doing this we managed to devise - among many things - a number of MCTS variations dynamically updating their explorative factor, leading not only to a clear improvement in performance but also mitigating the task of manually tuning parameters for the programmer. By combining ideas that empirically proved themselves successful in isolation, an algorithm matching (and sometimes outperforming) the performance of the previous NMCTS algorithm while using only a fraction of the resources was created, and on a different well known test set two competitive scores of 78936 and 80146 points were achieved.

The results suggest that there are still many ways in which MCTS for single-player domains may be improved, and many unexplored lines of thought remain. This work's contribution lies not in a single algorithmic idea tuned to perfection, but in the survey of several ideas and their combination, providing a solid foundation for future research to build upon.

Abstract [sv]

Sedan datorns skapelse har algoritmer för att besegra människor i spel varit ett hett forskningsämne, algoritmer som när de är lyckade ofta får brett genomslag. För vissa spel har det dessvärre visat sig vara oerhört svårt för datorer att slå människor. Men år 2006 uppfanns en algoritm vid namn Monte-Carlo Tree Search (MCTS) som förbättrade datorernas spelförmåga i några av de svåra spelen, bl.a. Go. Omkring ungefär samma tidpunkt började forskare även undersöka hur MCTS kunde tillämpas på enspelar-problem, ett av dem var pusslet SameGame.

Detta arbete kommer att fortsätta forskningen på SameGame för att förbättra algoritmer, idéer och kunskap om hur pussel kan angripas med MCTS. Vi använde huvudsakligen en testuppsättning bestående av 250 slumpgenererade SameGame-instanser för att utvärdera hur olika metoder presterar. Genom detta tillvägagångssätt lyckades vi bl.a. skapa ett antal MCTS-varianter som dynamiskt uppdaterar sin explorativa faktor, vilket inte bara bidrar till förbättrad prestationsförmåga, utan också lättar programmerarens arbetsbörda att manuellt justera parametrar. Genom att kombinera idéer som empiriskt var för sig visade sig fungera bra, skapades en algoritm som matchar (och ibland överträffar) den tidigare NMCTS-algoritmen och som därtill bara använder en bråkdel lika stora resurser, och på en annan välanvänd testuppsättning lyckades två konkurrenskraftiga resultat om 78936 och 80146 poäng åstadkommas.

Resultaten tyder på att det fortfarande finns många sätt på vilka MCTS inriktat på enspelar-problem kan förbättras, och många tankegångar att utforska återstår. Detta arbetes bidrag till forskningsvärlden består inte av en enstaka finputsad algoritmisk idé dragen till sin spets, utan av undersökandet av många idéer och dess kombination, vilket bistår framtida forskning med en stabil grund att bygga vidare på.

Place, publisher, year, edition, pages
2015.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-167145OAI: oai:DiVA.org:kth-167145DiVA: diva2:813153
Subject / course
Computer Science
Educational program
Master of Science in Engineering - Computer Science and Technology
Supervisors
Examiners
Available from: 2015-05-28 Created: 2015-05-21 Last updated: 2015-05-28Bibliographically approved

Open Access in DiVA

fulltext(1462 kB)457 downloads
File information
File name FULLTEXT01.pdfFile size 1462 kBChecksum SHA-512
acb9ef5d95114f7e476866497b0734be197837cd1028944bee705a44d84681d5aa31fb50e5e55567f19e1d5f8bf5aa3fde0fbed01f50c78aa3642daf5b0a87ff
Type fulltextMimetype application/pdf

By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 457 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: 186 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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