Chinese Dark Chess (CDC) Agents

This repository houses a suite of high-performance AI agents for Chinese Dark Chess (CDC), developed as part of the Theory of Computer Games course at NTU. The projects progress from single-player puzzle solving to a full-featured competitive game engine, utilizing advanced search algorithms, SIMD optimizations, and probabilistic methods.

Projects Overview

Directory	Project	Description	Key Techniques
Final/	Full Game Agent	Complete CDC engine playing the full ruleset (including flipping).	NegaScout, Star1, SIMD TT, Dynamic Time Management
HW2/	MCTS Agent	Plays the "No-Flip" variant (perfect information after setup).	MCTS, RAVE, Progressive Pruning, Bitboards
HW1/	Puzzle Solver	Solves "Capture All" scenarios (single-player shortest path).	A* Search, Floyd-Warshall, Heuristics

---

1. Final Project: The Competitive Agent

Directory: Final/

The culmination of the course, this agent plays standard Chinese Dark Chess with full rules.

Core Algorithms

• NegaScout Search: Employed as the primary search framework, utilizing null-window searches to minimize node expansion.
• Star 1 Pruning: Handles stochastic "chance nodes" (flipping unrevealed pieces) by computing expected values with sharp bounding cut-offs.
• Iterative Deepening: Ensures valid moves are always available and optimizes time usage.

Performance Engineering

• SIMD-Accelerated Transposition Table (TT):
  • Architecture: 16-way set-associative cache using 128-bit Zobrist Hashing.
  • Vectorization: Uses SIMD instructions for parallel tag matching and LRU metadata updates, achieving up to 19x faster lookups in sparse scenarios.
• Lambda-Based Move Generator: A zero-allocation design using C++ lambdas/function_ref to pipeline move generation directly into the search loop, eliminating temporary container overhead (~2x speedup over the TA's version).
• Bit-Level Optimizations: Extensive use of bit manipulation for board state analysis.

---

2. HW2: MCTS Variant (No-Flip)

Directory: HW2/

This project implements Monte Carlo Tree Search (MCTS) for a deterministic variant of CDC (no piece flipping). It focuses on solving the "Sparse Reward" problem common in board games.

Core Algorithms

• MCTS with RAVE: Integrates Rapid Action Value Estimation (RAVE) to quickly bias the search towards effective moves by sharing values across similar subtrees.
• Progressive Pruning: Statistically prunes unpromising child nodes during the selection phase based on confidence intervals (Mean/Variance analysis).
• Heuristic Simulation: Replaces random rollouts with a "Danger Zone" aware policy that prioritizes captures and escapes, producing more realistic playouts.

Technical Highlights

• SIMD Score Caching: Adapts the high-performance set-associative cache design for MCTS node storage.
• System-Level Timing: Utilizes timer_create and POSIX signals (SIGRTMIN) for precise, interrupt-driven time management without polling overhead.

---

3. HW1: Single-Player Solver

Directory: HW1/

A puzzle solver that finds the optimal (shortest) path to capture all opposing Red pieces given a specific board configuration.

• A Search*: Explores the state space using an admissible heuristic ($f(n) = g(n) + h(n)$).
• Heuristic Function: Estimates remaining moves by calculating the "Maximum of Minimum Distances" required for Black pieces to reach targets.
• Floyd-Warshall Pre-calculation: Computes all-pairs shortest paths on the board to account for obstacles and unique movement rules (e.g., Cannon vs. Pawn) instantly.

---

Prerequisites & Build Instructions

System Requirements

• OS: Linux (POSIX compliant)
• Compilers:
  • clang++ (Recommended for Final)
  • g++ (Used for HW1, HW2)
• Python: Version 3.13+ (Required for game clients and scripts)
  • Dependencies: textual, websockets, jsonschema (managed via uv)

Compilation

Each project is self-contained. Navigate to the wakasagihime directory within each project to build.

Final Project:

cd Final/wakasagihime
make        # Builds the standard agent 'wakasagi'
make full   # Builds with Star2 enabled (optional)

HW2 (MCTS):

cd HW2/wakasagihime
make        # Builds 'wakasagi'
make full   # Builds with RAVE and Progressive Pruning enabled (optional)

HW1 (Solver):

cd HW1/wakasagihime
make        # Builds 'wakasagi'

Running the Agents

All agents expects a board configuration via standard input:

./wakasagi