umu.sePublications
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
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
Identifiers
URN: urn:nbn:se:umu:diva-88363OAI: oai:DiVA.org:umu-88363DiVA: diva2:715317
Subject / course
Examensarbete i teknisk fysik
Educational program
Master of Science Programme in Engineering Physics
Presentation
2014-04-16, Umeå, 11:00 (English)
Supervisors
Examiners
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)216 downloads
File information
File name FULLTEXT01.pdfFile size 394 kBChecksum SHA-512
d6ec16f94e7becc5dd55dfcafdc450b8707729066a11321c336a95060b254a9c35664c77b6687b0d459425441df7712d2c91c2285623f33ed05b88e442cde35a
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: 216 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: 403 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