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
Självinlärning av fyra-i-rad.
KTH, School of Computer Science and Communication (CSC).
KTH, School of Computer Science and Communication (CSC).
2011 (Swedish)Independent thesis Advanced level (professional degree), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

Self-learning of the Connect 4 game

We have implemented a self-learning computer player for the board game Connect 4. The idea has been to only provide the player with information about the board state and allowed moves in order to force it to learn all the relevant game concepts on its own. The learning is done with the reinforcement learning method TD(λ) using a artificial neural net as a function approximator for the value function. We have used a two-layer net that has been trained by the BackProp algorithm.

During training, the computer player has been evaluated against a random player and four players who were using the minimax-algorithm with a simple board evaluation function to search the game tree at different depths. The player has also been evaluated against specific board states to determine if it is learning important game concepts such as attack and defense, but also more specific ones such rows, columns and diagonals.

We have been able to train a computer player that manages to beat a random player in nearly all games. The computer player also shows strong developement against the best minimax-player (the one with depth 4). In the beginning of the training our player is beaten nearly every game, but towards the end it manages to win almost 60% of the games.

Abstract [sv]

Själv-inlärning av fyra-i-rad

Vi har implementerat en självinlärande datorspelare för spelet fyra-i- rad. Utgångspunkten är att spelaren endast får veta spelbrädets ut- seende och möjliga drag, och därför själv måste lära sig de relevanta spelkoncept som behövs för att spela framgångsrikt. Inlärningen sker med belöningsbaserad inlärning med TD(λ) där värdesfunktionen ap- proximeras med att artificiellt neuralt nät. Vi har använt ett tvålagers nät som tränats med BackProp-algoritmen.

Spelaren har under inlärning utvärderats mot en slumpspelare och fyra spelare som använder minimax-algoritmen med en enkel evalue- ringsfunktion, som söker på olika djup i spelträdet. Dessutom har spe- laren utvärderats mot specifika speltillstånd för att undersöka om den lär sig viktiga spelkoncept så som attack och försvar, men även mer specifika begrepp så som rader, kolumner och diagonaler.

Vi lyckas träna upp en datorspelare som slår en slumpmässig spelare i nästan samtliga matcher. Mot den svåraste förprogrammerade taktiken (den som söker djupast) utvecklas agenten ifrån att förlora nästan alla matcher till att vinna ungefär 60% av matcherna.

Place, publisher, year, edition, pages
2011.
Series
Kandidatexjobb CSC, K11059
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-130813OAI: oai:DiVA.org:kth-130813DiVA: diva2:654260
Educational program
Master of Science in Engineering - Computer Science and Technology
Uppsok
Technology
Supervisors
Examiners
Available from: 2013-10-07 Created: 2013-10-07

Open Access in DiVA

No full text

Other links

http://www.csc.kth.se/utbildning/kandidatexjobb/datateknik/2011/rapport/dalenius_johan_OCH_lofroth_bjorn_K11059.pdf
By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 145 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