Change search
ReferencesLink to record
Permanent link

Direct link
Exact and Monte-Carlo algorithms for combinatorial games
Umeå University, Faculty of Science and Technology, Department of Physics.
2014 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Exakta och Monte-Carlo algoritmer för kombinatoriska spel (Swedish)
Abstract [en]

This thesis concerns combinatorial games and algorithms that can be used to play them.Basic definitions and results about combinatorial games are covered, and an implementation of the minimax algorithm with alpha-beta pruning is presented.Following this, we give a description and implementation of the common UCT (Upper Confidence bounds applied to Trees) variant of MCTS (Monte-Carlo tree search).Then, a framework for testing the behavior of UCT as first player, at various numbers of iterations (namely 2,7, ... 27), versus minimax as second player, is described.Finally, we present the results obtained by applying this framework to the 2.2 million smallest non-trivial positional games having winning sets of size either 2 or 3.It is seen that on almost all different classifications of the games studied, UCT converges quickly to near-perfect play.

Abstract [sv]

Denna rapport handlar om kombinatoriska spel och algoritmer som kan användas för att spela dessa.Grundläggande definitioner och resultat som berör kombinatoriska spel täcks, och en implementation av minimax-algoritmen med alpha-beta beskärning ges.Detta följs av en beskrivning samt en implementation av UCT varianten av MCTS (Monte-Carlo tree search).Sedan beskrivs ett ramverk för att testa beteendet för UCT som första spelare, vid olika antal iterationer (nämligen 2, 7, ... 27), mot minimax som andra spelare.Till sist beskrivs resultaten vi funnit genom att använda detta ramverk för att spela de 2,2 miljoner minsta icke triviala positionella spelen med vinstmängder av storlek antingen 2 eller 3.Vi finner att, för nästan alla olika klassificeringar av spel vi studerar, så konvergerar UCT snabbt mot nära perfekt spel.

Place, publisher, year, edition, pages
2014. , 52 p.
Keyword [en]
monte carlo algorithm, combinatorial game theory, computational, haskell
National Category
Discrete Mathematics
URN: urn:nbn:se:umu:diva-88363OAI: diva2:715317
Subject / course
Examensarbete i teknisk fysik
Educational program
Master of Science Programme in Engineering Physics
2014-04-16, Umeå, 11:00 (English)
Available from: 2014-06-10 Created: 2014-05-03 Last updated: 2014-06-10Bibliographically approved

Open Access in DiVA

thesis_msc_engphys.pdf(394 kB)120 downloads
File information
File name FULLTEXT01.pdfFile size 394 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Leino, Anders
By organisation
Department of Physics
Discrete Mathematics

Search outside of DiVA

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

Total: 78 hits
ReferencesLink to record
Permanent link

Direct link