Chinese Dark Chess AI

I developed a series of C++ solvers and game-playing agents for Chinese Dark Chess in NTU’s Theory of Computer Games course. Starting with a puzzle solver, I progressed to an agent for fully visible boards and then a final agent that handles hidden pieces and uncertain outcomes.

The course provided the game framework; I wrote the search algorithms and evaluation functions.

Course: Theory of Computer Games, Fall 2025 Tools: C++, Make, GDB Code: Project repository

Final agent: playing with hidden information

In standard Chinese Dark Chess, pieces begin face down. On each turn, an agent must choose between moving a revealed piece and flipping a hidden one. Moving requires anticipating an opponent’s response; flipping also requires considering which piece might appear.

I combined alpha-beta pruning, NegaScout, and Star1 to handle these decisions. Alpha-beta pruning skips branches that cannot improve the current choice. NegaScout first tests alternative moves with a narrow search window, expanding the search when a move appears promising. Star1 handles the possible outcomes of a flip, weighting them by the remaining hidden-piece counts and using score bounds to prune chance branches.

To make better use of a roughly five-second search budget, I added:

• Iterative deepening: search progressively deeper while retaining a candidate move to return when time runs out.
• Cached search results: use a transposition table and incrementally updated Zobrist hashes to reuse work when a position appears again.
• Move ordering: prioritize cached moves, captures, flips, and moves that previously produced useful cutoffs.
• Material and positional evaluation: combine a precomputed material-score table with distance bonuses that encourage pieces to approach capturable opponents.

Building toward the final agent

Finding capture sequences with A*

The first assignment was a puzzle: capture all red pieces in as few moves as possible. I implemented A* with a priority queue, a record of previously visited positions, and parent links for reconstructing the move sequence.

The main design task was the heuristic. I estimated capture costs using the distance from each target to a black piece capable of capturing it, accounting for different movement rules and cases where one piece could capture several targets. This let the search prioritize promising positions beyond simply counting the pieces left on the board.

Choosing moves with Monte Carlo Tree Search

The second assignment introduced an opponent, with all pieces face up. I implemented Monte Carlo Tree Search (MCTS), using simulated games to estimate the value of candidate moves. UCB selection balanced exploring less-visited moves with revisiting promising ones, while weighted rollouts favored captures. I also added the All-Moves-As-First (AMAF) heuristic to share information about moves encountered during simulations.

One practical problem was endgame wandering: the agent could hold a strong material advantage without closing out the game. I added an alpha-beta endgame search with a distance-based evaluation to encourage pursuit and captures in selected endgame positions.

Testing also showed that increasing the simulation batch size did not consistently improve play. Under the move deadline, spending more time simulating one part of the tree left less time to explore elsewhere.

Watch the MCTS agent play against Euler and UwU.

Debugging misleading results

During MCTS development, an enhanced configuration initially appeared weaker than the simpler baseline. Inspecting a replay and reproducing the failure in GDB revealed a null-pointer access in the AMAF update logic: terminal positions triggered an update without a simulation-move record. I added a guard before accessing that record. After the fix, the comparison favored the enhanced configuration.

The final agent exposed a different issue. It inferred hidden-piece counts from the pieces visible on the board, so it counted captured pieces as if they were still face down. Those incorrect counts distorted the probabilities used in chance-node search. I revised the tracking across turns and temporarily updated the counts during hypothetical flips, restoring them when returning from each search branch.

Testing individual changes

For the final project, I played each new version against the one before it. The table shows selected comparisons, with wins and losses counted from the newer version’s side.

The flip budget and cooldown limited how often the search considered revealing pieces. Although that version won more games than it lost, 93 of 120 games ended in draws, and I observed reluctance to flip and prolonged wandering. I discarded the restriction.

What I learned

A more expensive evaluation or a larger simulation batch could reduce the search completed before the deadline, and a small state-tracking error could undermine a more advanced search method. I learned to evaluate each change through both match results and concrete game behavior, and to investigate unexpected results before using them to choose the next design.

Code and reports