On the gameplay of Afrikan tähti

Thumbnail Image

Files

master_Etzell_Peik_2025.pdf (1.47 MB)

URL

Journal Title

Journal ISSN

Volume Title

School of Science | Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2025-07-16

Department

Major/Subject

Computer Science

Mcode

Degree programme

Master's Programme in Computer, Communication and Information Sciences

Language

en

Pages

50

Series

Abstract

This thesis studies the gameplay of the Finnish board game Afrikan tähti (The star of Africa), and aims to investigate the effects of its inherent randomness on expected game outcomes. Using an advanced policy based on paranoid expectiminimax search, and a handful of simpler deterministic and random strategies, large-scale simulations are run to generate statistical data on the expected pairwise outcomes. The results show that even basic strategies remain competitive due to the game's randomness, with only a limited advantage to the more advanced policies. Using a reduction from the Hamiltonian cycle problem, a decision problem regarding optimal play of Afrikan Tähti is shown to be NP-hard, proving that a truly optimal policy is infeasible. Conservative upper bounds on the state-space complexity of the game are computed using combinatorial methods, at $10^23.2$ and $10^37.0$ for two and five player games respectively. Finally, simple reasoning shows that the intuitive decision turns out to be a losing move in some situations, which can even come up in normal play.

Denna avhandling studerar det finska bordsspelet Afrikas stjärna, med syftet att undersöka effekterna av dess slumpmässighet på förväntade spelresultat. Genom att använda en avancerad strategi baserad på paranoid expectiminimax, samt ett antal enkla deterministiska och icke-deterministiska strategier, genomförs omfattande simuleringar för att generera statistiska data om förväntade vinnare i parvisa matcher. Resultaten visar att även enkla strategier är konkurrenskraftiga tack vare spelets slumpmässighet, med endast en begränsad fördel för mer avancerade strategier. En reduktion från det hamiltonska cykelproblemet visar att ett beslutsproblem centralt till optimala spelstrategier för Afrikas stjärna är NP-svårt. En optimal strategi är därmed omöjlig givet nuvarande förståelse inom datavetenskap. Konservativa övre gränser på mängden konfigurationer av spelet räknas ut att vara $10^23.2$ konfigurationer för spel med två spelare, och $10^37.0$ för fem spelare. Slutligen visar ett enkelt resonemang att det intuitiva valet att öppna en lucka kan vara ett förlorande drag i vissa situationer. Intressant nog kan sådana situationer också förekomma i vanligt spel.

Description

Supervisor

Rintanen, Jussi

Keywords

game theory, expectiminimax, board game, star2, multiplayer, randomness

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202508196532

Collections

[dipl] Perustieteiden korkeakoulu / SCI