GSoC/2024/StatusReports/JoaoGouveia

Implementing a computerized opponent for the Mancala variant Bohnenspiel

Games within the Mancala family are played all over the world. However, as of now, KDE doesn’t offer any Mancala games for those looking for a challenging opponent. This project aimed to begin changing that.

Work report

Throughout this summer, I've developed a C++ API, implementing three opponents for the games of Bohnenspiel and Oware.

The current library is highly extensible. After implementing all the base classes and Bohnenspiel, adding Oware to the library was fairly fast and straightforward. This focus on extensibility has been a priority since the beginning of the project. Given that the Mancala family of games comprises numerous variants, designing the API with this in mind has proven valuable.

The three provided opponents use a random selection algorithm, Minimax, and MTD-f. The Minimax and MTD-f opponents were implemented with optimizations like alpha-beta pruning and transposition tables, making them both very capable, consistently outperforming the random opponent. However, I faced some challenges implementing the MTD-f opponent. While it outperforms the random opponent, it performs worse than the Minimax opponent despite conducting deeper searches. This leads me to believe there may be an issue with my implementation, but I haven't been able to identify it even after several reviews.

I believe this project lays the groundwork for Mancala games within KDE. I intend to continue contributing, particularly by developing a GUI that utilizes the computerized opponents I’ve developed.

Work breakdown

• June Weeks 1-2:
  • Implemented the base engine classes.
  • Implemented Bohnenspiel's rules.
  • Wrote tests for all implemented functionality using GoogleTest.

• June Weeks 3-4:
  • Implemented a basic Minimax move selection algorithm.
  • Implemented a random selection algorithm.
  • Developed a benchmark utility to compare different move selection functions.
  • Developed a simple Bohnenspiel TUI as a usage example.
  • Added documentation using Doxygen.
  • Added licensing information according to KDE's licensing policies.
  • Enabled CI using the Linux, FreeBSD and Windows pipelines.

• July Weeks 1-2
  • Implemented alpha-beta pruning and transposition tables to improve Minimax.
  • Implemented the MTD-f move selection function.

• July Weeks 3-4
  • Refactored the library to use PImpl.
  • Improved the project build process, namely by enabling shared library building by default.
  • Fixed issues related with building a shared library on Windows.
  • Began using CMake's export macros to control function and class visibility.
  • Added the Android pipeline to the CI. GoogleTest wasn't building on Android, so tests were disabled on this platform.

• August Weeks 1-2
  • Improved the project build process by incorporating several ECM modules.
  • Switched from GoogleTest to QtTest.
  • Enabled testing on Android.
  • Added the Alpine pipeline to the CI.

Links to Blogs and other writing

My blog posts tagged with GSoC