Change search
ReferencesLink to record
Permanent link

Direct link
Minimax Based Kalaha AI
Blekinge Institute of Technology, School of Computing.
2013 (English)Independent thesis Basic level (degree of Bachelor)Student thesis
Abstract [en]

To construct an algorithm which does well in a board game, one must take into account the time spent on each move and the ability to evaluate the state of the board. There are multiple ways to handle these issues, but only a few are covered in this analysis. AIs using the algorithms minimax, minimax with alpha-beta pruning and minimax with knowledge-based alpha-beta pruning are being compared when playing Kalaha with a 30 second time limit per move. Each algorithm is in addition paired up with two different methods of evaluating the games state. The first one only compares the amount of counters in each players store, while the second, knowledge-based method, extends this with an evaluation of the counters in play. A tournament was held between the AIs where each match-up played twelve games against each other. The regular minimax algorithm is appearing to be inferior to the improved variations. The knowledge-based alpha-beta pruning is unexpectedly unsuccessful in outperforming the regular alpha-beta pruning and a discussion covers possible errors with the implementation and possible improvements. The knowledge-based evaluation method is appearing to be slightly more successful than the simple variant, but a discussion questions the real usefulness of it when paired with more advanced search algorithms than the ones covered in this study.

Place, publisher, year, edition, pages
2013. , 24 p.
Keyword [en]
minimax, alpha, beta, pruning, kalaha, ai, programming, knowledge, based
National Category
Computer Science
URN: urn:nbn:se:bth-5333Local ID: diva2:832707
Available from: 2015-04-22 Created: 2013-09-01 Last updated: 2015-06-30Bibliographically approved

Open Access in DiVA

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

By organisation
School of Computing
Computer Science

Search outside of DiVA

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

Direct link