The purpose of this document is to describe application architecture,algorithms and data structures
used throughout the Congo project.
To run unit tests, execute dotnet test from the solution root folder.
To generate source code documentation, doxygen should be
installed on the target system. Doxymentation as html is generated by running doxygen in the
solution root folder. Files are dumped into ./Congo.Assets/Resources/Doxygen/.
The solution is divided into several projects. Functional projects are tested within supporting
projects with .MSTest suffix in the name, such as Congo.Utils.MSTest, Congo.Core.MSTest and
Congo.CLI.MSTest. Congo.CLI.Installer and Congo.GUI.Installer generate .msi files.
| Project | Dependencies |
|---|---|
| Congo.Core | - |
| Congo.Utils | Congo.Core |
| Congo.Server | Congo.Core |
| Congo.CLI | Congo.Core, Congo.Utils, Congo.Server |
| Congo.GUI | Congo.Core, Congo.Utils, Congo.Server |
Both Congo.CLI and Congo.GUI reference the same congo.proto service file from Congo.Server
project. Denendencies on third party NuGet packages can be consulted
here.
The project accomodates only non-code artifacts, such as documentation and pictures.
Congo.Core provides implementations of all essential parts for constructing an instance of the
game, such as CongoPiece, CongoPlayer, CongoBoard, CongoGame and CongoUser.
Most of the implemented data structures are immutable to provide better programmer experience and
completely avoid do/undo operations, that could cause annoying bugs. Possibly expensive operations
on types, such as typeof(..), are generally avoided within this project.
Read Core algorithms and data structures to learn more about algorithmic aspects of the project.
This is an abstract class used for valid move generation for each kind of piece in the game.
CongoPiece descendants implement Singleton pattern. The basic functionality is to calculate
valid moves being provided with the color, board and current position. Each descendant has its own
specific procedure to calculate moves.
Instances of this class used for collecting moves valid for a particular player color and current
board. In the constructor, player iterate over all pieces on the board and concatenate results into
a larger list of moves. It finds where the lion is located. The .Accept(move) has special meaning,
the method looks for a similar move in the list of all available moves and return it upon success,
otherwise null is returned. Move replacement enables retrieving proper monkey jumps. Therefore,
any final move should be accepted before the result is passed to CongoGame.Transition(...).
This class simulates a Congo board with pieces on it. Internally, the instance of the board is
represented by three items. First two are ulong words white- and blackOccupied telling,
whether particular square is occupied and by which player. The third is an immutable array with uint representing one rank of the board. There are
The board class contains precalculated possible leaps for each type of piece and each position. Lambda functions are heavily used in this calculation. As a consequence, generation of the valid leaps is a simple iteration over all possible for a given position and piece. Not all valid moves are leaps, some of the pieces slide and such moves are generated additionally by a particular piece based on the current position on the board.
Class is a container for a game snapshot with references to the current board and players. The most
important instance method of this class is .Transition(). Given valid (or accepted) move it
constructs new game with new board and new players. Instances of the game class are immutable. Such
property is a great helper in concurrent calculations.
CongoUser is a typed representation of the playing user. Three types are distinguished, namely
Hi, Ai and Net. Each user may enforce the board to advise using an algorithm delegate provided
in the constructor. Artificial agent picks this move to proceed. Implementation of a Net user
behavior is a responsibility of a user interface.
Congo.Utils implements simple supporting functions shared by user interface implementations.
This project uses gRPC library. Typed remote calls and messages are defined in the congo.proto
file, which transpiles into C# source code during compilation. Other projects, such as Congo.CLI
and Congo.GUI reference congo.proto instantiating Client types and functionality.
Internally, source code follows simplified MVC pattern. This could be suboptimal in terms of
transparency and code understandability. Extensive refactoring implementing full MVC is considered.
We use simple SQLite database on the background. C# code accesses structures using lightweight
ADO.NET provider, in particular Microsoft.Data.Sqlite library. Static class CongoState is
a single source of truth, the only model of the Congo server.
Database main.db contains games table with columns gameId, firstFen and lastFen.
gameId is generated by the application logic. All new games obtain a unique identifier. firstFen
could be any valid Congo FEN string provided by the user on game creation (e.g. standard game)
or non-standard. lastFen contains the latest known reached game state.
Moves posted by the players are stored in a separated databases named #.db, where # is a unique
game identifier. Game-specific database contains moves table with columns moveId, fromSquare
and toSquare. Moves are ordered, moveId is used for game consistency verification. Only valid
moves change database state/records.
CongoGrpcService class provides an access to the task-based API for processing calls
asynchronously. Each call is treated within dedicated method. Transactions are generally avoided,
because SQLite offers very limited capabilities. Atomicity of database accesses is ensured via
mutual exclusion.
if (CongoState.lockDb.TryGetValue(request.GameId, out var l)) {
lock (l) {
...
}
}Congo.CLI project implements simple terminal-based user interface. The game is configured
in the arguments, malformed arguments are reported.
Commands issued by the user are parsed, validated and executed by the corresponding delegates. Lambda functions are heavily used in verification. Each user decision is processed immediately, e.g. posting new moves on the server and validation of the response.
This project is platform-independent and could handle local games or games via network.
The project implements graphical user interface based on WPF technology. It provides functionality
similar to the Congo.CLI project. The project is inherently platform-dependent and could handle
both local and network games.
MainWindow contains of the board and control
panels. LocalPopup is used for configuring local games, and NetworkPopup for network games.
Some of the user or program actions could last long. To avoid hanging the main window, heavy tasks
are evaluated separately within BackgroundWorker. There are
Hiplayer requests an algorithmic advice,Aiplayer decides its move,- remote
Netplayer decides its move.
Evaluation is interrupted upon Reset, and Exit. Finished worker call _Complete function and
enforce global state updates based on the results. Results of any calculation can be abandoned
via step variable.
MainWindow is stateful, this brings additional obstacles. We decided to follow a rule that the
game state (variables _moveFr, _game, _state, _whiteUser and _blackuser) could be updated
only in applyStep method. Items relevant for the worker (variables _netPack, movesOut and
_job) are updated in the _Init() or _Complete() methods. Other data structures cannot be
changed from outside.
To make the game more challenging, we have implemented a standard fail-hard beta cut-off Negamax algorithm with alpha-beta pruning and several performance enhancements. These primitives are used for advising next move to the human player and enables smarter decision-making by the artificial player.
Some of the moves don't change the color of the active player (e.g. monkey jumps). Our implementation treat such situations well.
Hash table is used for identifying transposed boards in the Negamax decision tree. Such boards
could appear in case the board returns to the original state after a cycle of moves. Hash table
enables an algorithm traversing game tree to recognize such boards and use already precalculated
best score and move. The hashed cell is recognized as hash hit in case current board has equal or
smaller sub-tree in terms of recursion depth than the board found in the hash. Otherwise, the
current board traverses all valid moves leading to the recursion call.
Internally, the hash table has R/W operations on the cells.
Hash eviction policy is implemented based on the board equality. Once the best move is found in
Negamax, the method .SetSolution(...) is called on the table instance. The board, move and score
are stored in case boards are not equal or better solution is found. Board equality is an efficient
operation, it compares ulong values and uint values.
The hash code of the cell is determined based on a board hash value. Hash is calculated as proposed
by Albert Lindsey Zobrist. First,
pseudo-random values are generated for each (color, piece, square) triple. Consider moving white
pawn from A1 to A3. We remove hash of triple (white, pawn, A1) from the current board hash.
Then we add no-piece to the board hash (?, no-piece, A1). Then we remove no-piece from the board
hash (?, no-piece, A3). Finally, we add (white, pawn, A3) to the board hash. Initial board hash
is calculated via calling method .InitHash(CongoBoard board) on the table instance. Initial hash
will contain only hash addition operations. All no-pieces (ground and river) are considered black.
For each triple (color, piece, square) retrieve random number and applies hash := XOR(hash, number).
Removing pieces is done via repeated xor-application. New board hash is adjusted directly in Negamax
recursive procedure.
Evaluating board by Negamax algorithm could be resource and time-consuming and some kind of
a parallelization would be helpful.
Note that static class Algorithm defines the global private static CongoHashTable hT and
accessing table cells is thread-safe. Furthermore, instances of the game are immutable. We use
ThreadPool and divide possible moves between several tasks evenly.
All this enables speeding up of the board evaluation.
Theory behind the algorithm could be studied at BitScan.
The algorithm takes a 64-bit word with exactly one bit set and returns its index using bitwise
operations. This technique is used for fast iterating over pieces on the board, see
Congo.Core/BitScan.cs.