his.sePublikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
EVOLUTIONARY AI IN BOARD GAMES: An evaluation of the performance of an evolutionary algorithm in two perfect information board games with low branching factor
Högskolan i Skövde, Institutionen för informationsteknologi.
2015 (engelsk)Independent thesis Basic level (degree of Bachelor), 15 poäng / 22,5 hpOppgave
Abstract [en]

It is well known that the branching factor of a computer based board game has an effect on how long a searching AI algorithm takes to search through the game tree of the game. Something that is not as known is that the branching factor may have an additional effect for certain types of AI algorithms.

The aim of this work is to evaluate if the win rate of an evolutionary AI algorithm is affected by the branching factor of the board game it is applied to. To do that, an experiment is performed where an evolutionary algorithm known as “Genetic Minimax” is evaluated for the two low branching factor board games Othello and Gomoku (Gomoku is also known as 5 in a row). The performance here is defined as how many times the algorithm manages to win against another algorithm.

The results from this experiment showed both some promising data, and some data which could not be as easily interpreted. For the game Othello the hypothesis about this particular evolutionary algorithm appears to be valid, while for the game Gomoku the results were somewhat inconclusive. For the game Othello the performance of the genetic minimax algorithm was comparable to the alpha-beta algorithm it played against up to and including depth 4 in the game tree. After that however, the performance started to decline more and more the deeper the algorithms searched. The branching factor of the game may be an indirect cause of this behaviour, due to the fact that as the depth increases, the search space increases proportionally to the branching factor. This increase in the search space due to the increased depth, in combination with the settings used by the genetic minimax algorithm, may have been the cause of the performance decline after that point.

sted, utgiver, år, opplag, sider
2015. , s. 39
Emneord [en]
Branching factor, game tree, artificial intelligence, ai, evolutionary algorithm, minimax, alpha-beta
HSV kategori
Identifikatorer
URN: urn:nbn:se:his:diva-11175OAI: oai:DiVA.org:his-11175DiVA, id: diva2:823737
Fag / kurs
Computer Science
Utdanningsprogram
Computer Science - Specialization in Systems Development
Veileder
Examiner
Tilgjengelig fra: 2015-08-10 Laget: 2015-06-18 Sist oppdatert: 2018-01-11bibliografisk kontrollert

Open Access i DiVA

fulltext(1298 kB)1572 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 1298 kBChecksum SHA-512
ad53f8ecbdcf9f076e0aacd612cd4919234192b7ada2ae4d59f5d54d1d156ccbcf138e38515c04c45e9bc6b71c2bd1dfa7ccb51f065316688ab4f968314b161f
Type fulltextMimetype application/pdf

Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 1572 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

urn-nbn

Altmetric

urn-nbn
Totalt: 1053 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf