Change search
ReferencesLink to record
Permanent link

Direct link
EVOLUTIONARY AI IN BOARD GAMES: An evaluation of the performance of an evolutionary algorithm in two perfect information board games with low branching factor
University of Skövde, School of Informatics.
2015 (English)Independent thesis Basic level (degree of Bachelor), 15 credits / 22,5 HE creditsStudent thesis
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.

Place, publisher, year, edition, pages
2015. , 39 p.
Keyword [en]
Branching factor, game tree, artificial intelligence, ai, evolutionary algorithm, minimax, alpha-beta
National Category
Computer Science
URN: urn:nbn:se:his:diva-11175OAI: diva2:823737
Subject / course
Computer Science
Educational program
Computer Science - Specialization in Systems Development
Available from: 2015-08-10 Created: 2015-06-18 Last updated: 2015-08-10Bibliographically approved

Open Access in DiVA

fulltext(1298 kB)284 downloads
File information
File name FULLTEXT01.pdfFile size 1298 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
School of Informatics
Computer Science

Search outside of DiVA

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

Direct link