GSoC/2024/StatusReports/JoaoGouveia: Difference between revisions
Joaotgouveia (talk | contribs) Add images |
Joaotgouveia (talk | contribs) Add information about the benchmark utility and the Bohnenspiel TUI |
||
| Line 13: | Line 13: | ||
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. | 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. | ||
A benchmark utility was developed to compare how different move selection functions fare against each other. This is very useful for identifying problems in the move selection functions and guaranteeing that both Minimax and MTD-f consistently outperform the random selection opponent. Additionally, I implemented a TUI that allows a user to play against an opponent using Minimax selection, serving as a usage example for the library. | |||
An effort was made to guarantee that this project meets KDE's standards. ECM modules such as [https://api.kde.org/ecm/kde-module/KDECompilerSettings.html| KDECompilerSettings], [https://api.kde.org/ecm/kde-module/KDECMakeSettings.html| KDECmakeSettings] and [https://api.kde.org/ecm/kde-module/KDEInstallDirs6.html| KDEInstallDirs6] were used to align this project build process with what's expected from KDE. All source files have their licensing information documented in accordance with [https://community.kde.org/Guidelines_and_HOWTOs/Licensing| KDE's licensing guidelines], and classes were implemented using the PImpl idiom, following the [https://community.kde.org/Policies/Binary_Compatibility_Issues_With_C%2B%2B| policies regarding binary compatibility issues with C++]. | An effort was made to guarantee that this project meets KDE's standards. ECM modules such as [https://api.kde.org/ecm/kde-module/KDECompilerSettings.html| KDECompilerSettings], [https://api.kde.org/ecm/kde-module/KDECMakeSettings.html| KDECmakeSettings] and [https://api.kde.org/ecm/kde-module/KDEInstallDirs6.html| KDEInstallDirs6] were used to align this project build process with what's expected from KDE. All source files have their licensing information documented in accordance with [https://community.kde.org/Guidelines_and_HOWTOs/Licensing| KDE's licensing guidelines], and classes were implemented using the PImpl idiom, following the [https://community.kde.org/Policies/Binary_Compatibility_Issues_With_C%2B%2B| policies regarding binary compatibility issues with C++]. | ||
Revision as of 22:03, 21 August 2024
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++ library called MankalaEngine, 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.
A benchmark utility was developed to compare how different move selection functions fare against each other. This is very useful for identifying problems in the move selection functions and guaranteeing that both Minimax and MTD-f consistently outperform the random selection opponent. Additionally, I implemented a TUI that allows a user to play against an opponent using Minimax selection, serving as a usage example for the library.
An effort was made to guarantee that this project meets KDE's standards. ECM modules such as KDECompilerSettings, KDECmakeSettings and KDEInstallDirs6 were used to align this project build process with what's expected from KDE. All source files have their licensing information documented in accordance with KDE's licensing guidelines, and classes were implemented using the PImpl idiom, following the policies regarding binary compatibility issues with C++.
MankalaEngine is multiplatform, the CI currently builds and tests the project on Linux, FreeBSD, Alpine, Android, and Windows. Linting and formatting utilities are also employed to guarantee code quality and consistency throughout the project.
I believe this project lays the groundwork for Mancala games within KDE. To put MankalaEngine to use, I am developing a GUI, Mankala, which will offer a selection of games from the Mancala family. I plan to continue working on this project after GSoC concludes and eventually integrate both Mankala and MankalaEngine into KDE.
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.
- August Weeks 3-4
- Implemented Oware's rules.
- Learned QtQuick to begin developing Mankala, a GUI that uses MankalaEngine.
- Prepared the repository for Mankala.
- Took a week of vacation, so I had less time to work.