A cross-platform implementation of Russian draughts (Shashki) with a computer player, developed as my bachelor's degree project in 2011.
The project was built not only as a playable game, but also as an experimental environment for implementing and comparing game-tree search algorithms, multithreaded search and different time-control strategies.
- Full implementation of Russian draughts rules
- Human vs. human and human vs. computer games
- Computer players based on MiniMax, Alpha-Beta pruning and NegaScout
- Configurable search depth
- Multithreaded versions of search algorithms
- Game-level time control with different time allocation strategies
- Tournament runner for comparing computer players
- Performance experiments for benchmarking search algorithms
- Cross-platform Qt4 GUI for desktop Linux and Maemo
- MVC-based architecture
- Unit tests for the game model
The computer player searches a tree of possible moves and evaluates game positions at a configurable search depth.
Three search algorithms were implemented and compared:
- MiniMax — baseline full game-tree search
- Alpha-Beta pruning — reduces the number of positions that need to be evaluated by pruning branches that cannot affect the result
- NegaScout — improves Alpha-Beta search using narrow search windows
The project included experiments for comparing algorithm performance at different search depths. NegaScout showed the best performance among the three implementations.
At the search depth limit, board positions were evaluated using a heuristic evaluation function. Different evaluation parameters were tested experimentally, including different relative weights for regular pieces and kings.
The same evaluation function provided the basis for comparing the different search algorithms independently from the position-scoring heuristic.
Multithreaded versions of the search algorithms were implemented for desktop systems.
Search work could be distributed between several threads, allowing the computer player to explore the game tree faster on multi-core processors while keeping the GUI independent from move calculation.
The experiments compared configurations with different thread counts and measured how parallelism affected search performance on multi-core processors.
The game supported a time limit for the entire match rather than a fixed limit for each move.
Several strategies for allocating the remaining time were implemented and compared:
- Simple — uses approximately the same amount of time for each move
- Defensive — becomes increasingly conservative as the remaining match time decreases
- Aggressive — saves more time early in the game for deeper searches later
Tournament experiments were used to compare these strategies under equal time limits.
The project included two tools for evaluating computer players:
- Tournaments ran large numbers of games between different player configurations and recorded wins, losses and draws. This made it possible to compare playing strength rather than relying only on theoretical properties of the algorithms.
- Experiments repeatedly measured move calculation time to compare the performance of search algorithms, search depths and thread counts.
This separation allowed the project to evaluate both computational performance and actual playing results.
The application follows an MVC-style architecture.
The game model contains the board state, game rules and two players. Human and computer players share a common abstraction, while different computer-player implementations can use different search algorithms.
Qt's observer-style signals and slots keep the views synchronized with changes in the game model. Move calculation is separated from the GUI so that longer searches do not block the interface.
The Qt4 interface running on Maemo.
- C++
- Qt4
- Multithreading
- MVC
- Unit testing
- Linux
- Maemo
Historical university project developed in 2011 as my bachelor's degree work.
It is no longer maintained; this repository preserves the original implementation.
Valery Kirkizh