Change search
ReferencesLink to record
Permanent link

Direct link
Reinforcement Learning on the Combinatorial Game of Nim.
KTH, School of Computer Science and Communication (CSC).
2011 (English)Independent thesis Advanced level (professional degree), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

This paper will investigate the implementation of the Q-learning reinforcement algorithm on an impartial, combinatorial game known as Nim. In our analysis of impartial games and Nim, an already established optimal strategy for playing Nim will be presented. This strategy will then be used as an exact benchmark for the evaluation of the learning process.

It is shown that the Q-learning algorithm does indeed converge to the optimal strategy under certain assumptions. A parameter analysis of the algorithm is also undertaken and finally the implications of the results are discussed. It is asserted that it is highly likely that the Q-learning algorithm can be effective in learning the optimal strategy for any impartial game.

Abstract [sv]

Denna kandidatuppsats undersöker en implementation av Q-inlärningsalgoritmen på ett impartiellt, kombinatoriskt spel kallat Nim. Under analysen av impartiella spel och Nim presenteras en redan etablerad optimal strategi för att spela Nim. Denna strategi används sedan som jämförelse för att evaluera inlärningsprocessen.

Det visas att Q-lärningsalgoritmen konvergerar till den optimala strategin under vissa antaganden. En parameteranalys åtas även och slutligen diskutera implikationerna av resultatet. Det är troligt att Q-läringsalgoritmen är effektiv i lärandet av optimala strategier för även andra impartiella spel.

Place, publisher, year, edition, pages
Kandidatexjobb CSC, K11054
National Category
Computer Science
URN: urn:nbn:se:kth:diva-130837OAI: diva2:654284
Educational program
Master of Science in Engineering - Computer Science and Technology
Available from: 2013-10-07 Created: 2013-10-07

Open Access in DiVA

No full text

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

Search outside of DiVA

GoogleGoogle Scholar
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: 47 hits
ReferencesLink to record
Permanent link

Direct link