Research Report on the History of Computer Chinese Chess (Xiangqi) Game-Playing

Chapter 1: The Evolution of Position Representation Technology

1.1 Array Representation

The earliest Chinese Chess engines (Zun Zu / Chess Master, Chess1 / Qi Yin, early ElephantEye, etc.) used a 10x9 two-dimensional array to represent the board. Each array element stores an integer indicating the piece type and color at that position.

A typical array representation encoding scheme:

• 0: Empty position
• Positive numbers (1-7): Red pieces (King, Advisor, Bishop, Knight, Rook, Cannon, Pawn)
• Negative numbers (-1 to -7): Black pieces (King, Advisor, Bishop, Knight, Rook, Cannon, Pawn)

Advantages of array representation: Intuitive and easy to understand, simple to implement, convenient for debugging. Disadvantages: Low efficiency, cache-unfriendly, poor parallel performance.

1.2 Bitboard Representation

Modern engines (such as Pikafish) use bitboard representation. Bitboards use multiple 64-bit integers to represent the board state, with each bit representing an intersection point on the board.

A Chinese Chess board has 90 intersection points, and 14 piece types (7 red + 7 black) each use one 64-bit bitboard. Bit 0 of the bitboard represents the top-left corner of the board, bit 9 represents the bottom-left corner, and bit 81 represents the top-right corner.

Advantages of bitboards:

1. Fast move generation — through precomputation and bitwise operations
2. Efficient memory access — compact data structure, cache-friendly
3. Good parallelism — bitwise operations naturally support parallel execution
4. Easy incremental updates — AND/OR/XOR bitwise operations on bitboards

Challenges of bitboards: Difficult to debug (bitboard values are binary integers, not intuitive); the Chinese Chess board dimensions do not perfectly align with 64-bit integers (90 bits vs 64 bits).

Chapter 2: In-depth Analysis of the Move Generator

2.1 Movement Rules for Chinese Chess Pieces

The movement rules for the 7 types of Chinese Chess pieces each differ:

King (Shuai / Jiang): Moves one step within the palace (rows 0-2 or 7-9, columns 3-5) in orthogonal directions (up, down, left, right). The two Kings cannot face each other on the same file with no pieces in between (the “flying general” rule).

Advisor (Shi): Moves one step diagonally within the palace, restricted to the 5 intersection points of the palace.

Bishop (Xiang): Moves diagonally in a “field” pattern (2 steps), with the constraint of “blocking the elephant’s eye,” and cannot cross the river.

Knight (Ma): Moves in an “L” shape (combination of 2 steps + 1 step), with the constraint of “hobbling the horse’s leg.”

Rook (Che): Moves any number of steps along a straight line (horizontally or vertically), and cannot jump over other pieces.

Cannon (Pao): For non-capturing moves, moves any number of steps along a straight line without jumping; for capturing moves, moves along a straight line, jumps over exactly one piece (the “screen”), and captures the first enemy piece encountered after the screen.

Pawn (Bing / Zu): Before crossing the river, can only move one step forward. After crossing the river, can move one step forward or horizontally, but cannot move backward.

2.2 Move Generation Pseudocode

The move generation logic for each Chinese Chess piece:

Rook move generation: For each direction (up, down, left, right), enumerate step by step from the current position along the direction. If the square is empty, add a non-capturing move and continue; if the square contains an enemy piece, add a capturing move and stop; if the square contains a friendly piece, stop. Stop when the square is outside the board boundaries.

Cannon move generation: For each direction, enumerate step by step along the direction. Use a screen counter: when the counter is 0, add a non-capturing move for an empty square, set the counter to 1 if a piece is present; when the counter is 1, add a capturing move for an enemy piece and stop, stop for a friendly piece, and continue for an empty square.

Knight move generation: For the 8 target directions of the Knight, calculate the target position and the blocking position. If the blocking position has a piece (hobbled leg), skip; if the target position has a friendly piece, skip; if the target position has an enemy piece, add a capturing move; if the target is empty, add a non-capturing move.

Pawn move generation: Determine the forward direction; add a move if the target is empty or contains an enemy piece. When the Pawn has crossed the river, the same rule applies for left and right directions.

2.3 Priority Generation Mechanism for Capturing Moves

In PVS search, the generation order of capturing moves has a significant impact on search efficiency. Engines use the following priority:

1. Transposition table best move (if present in the transposition table)
2. Winning captures (captures evaluated as positive by SEE)
3. Profitable captures (capturing a high-value piece with a low-value piece)
4. Equal captures (capturing an equal-value piece with an equal-value piece)
5. Losing captures (capturing a low-value piece with a high-value piece)
6. Non-capturing moves (killer moves first, history heuristic moves, then other moves)

Chapter 3: In-depth Analysis of the Evaluation Function

3.1 Design of the Handcrafted Evaluation Function

The handcrafted evaluation function of a Chinese Chess engine is a linear combination of a series of positional features. A typical evaluation function includes: material value evaluation, positional value evaluation, piece activity evaluation, King safety evaluation, positional structure evaluation, piece coordination evaluation, and tactical adjustments.

In material value evaluation, the basic values of different pieces are as follows:

• King: 10000 (non-quantifiable value)
• Rook: 600
• Knight: 270
• Cannon: 285
• Advisor/Bishop: 120
• Pawn: 30-150 (varies with game phase)

The position value table assigns a preset value for each piece at each position on the board. For example, the positional value of a Red Pawn: low score when on its own side (Pawn has not yet crossed the river), high score after crossing the river, and an especially high score on the central files (near the King).

Piece activity evaluation includes: the number of movable directions for the Knight, the number of controllable lines for the Rook, the number and quality of Cannon screens, etc.

King safety evaluation includes: the number of Advisors and Bishops protecting the King, the controlled space around the King, whether the King is exposed to enemy attack, etc.

Positional structure evaluation includes: the integrity of Advisors and Bishops, Pawn formation, and the degree of control over the river and palace.

3.2 The Tuning Process of the Evaluation Function

Tuning a handcrafted evaluation function is a systematic engineering effort:

Basic tuning: Set basic parameters based on known chess theory and experience. Run the engine in self-play for many games to collect evaluation bias, then adjust parameters based on the bias.

Position-type tuning: Collect test data for specific position types (opening, middlegame, endgame, advantageous, disadvantageous), analyze evaluation bias for each type, and adjust the corresponding parameters.

Fine-tuning: Use Fishtest or similar statistical testing frameworks for large-scale testing. Adjust one parameter at a time, observe ELO changes, keep only adjustments that yield significant ELO improvements, and repeat until parameters reach a local optimum.

3.3 Architecture of the Handcrafted Evaluation Function

The handcrafted evaluation function has a hierarchical structure:

First layer (static evaluation): Material value, positional value, piece activity.

Second layer (dynamic evaluation): Attack and defense relationships, threat detection, tactical combinations.

Third layer (positional understanding): Game phase judgment, piece exchange strategy evaluation, checkmate threat evaluation.

Fourth layer (rule constraints): King face-to-face detection, perpetual check and perpetual chase detection, stalemate detection.

3.4 Structure of the NNUE Evaluation Network

The structure of the NNUE evaluation network is as follows:

The input layer uses a sparse HalfKP feature set. The input vector dimension is approximately 40,000 (Chinese Chess adapted version). Features are (own King position, enemy piece type + position), using board symmetry to reduce the number of features.

The hidden layer consists of 1-2 fully connected layers. The first layer typically has 512 or 1024 neurons, with a Clipped ReLU activation function (clipped to the range 0-127). The second layer (if present) typically has 32 or 64 neurons. The output layer is a single neuron that outputs the position evaluation value (in units of 1/100th of a Pawn).

NNUE’s incremental update characteristic: After each move, only the input features related to the moved pieces need to be updated (typically a few to several dozen features), without recalculating the entire network. The computational complexity of this incremental update is O(number of feature changes x hidden layer width), far less than O(input dimension x hidden layer width).

3.5 The Transition from Handcrafted to NNUE Evaluation Functions

The evaluation functions of Chinese Chess engines have undergone a fundamental transition from handcrafted to NNUE:

Traditional handcrafted evaluation era (1989-2021):

• Evaluation functions were manually designed and adjusted by developers
• Limited number of features (tens to hundreds)
• Tuning relied on developer experience and understanding of chess principles
• Limited evaluation accuracy, but high search efficiency

NNUE evaluation era (2022-present):

• Evaluation functions are automatically learned by neural networks
• Massive number of features (tens of thousands of input features)
• Tuning depends on training data quality and network architecture design
• Significantly improved evaluation accuracy, but increased inference computation

Advantages of NNUE over handcrafted evaluation:

1. Higher evaluation accuracy — NNUE can discover subtle patterns that are difficult to encode manually
2. Automatic learning — no need to manually design features and weights
3. Continuous improvement — provided there is better training data, evaluation accuracy can improve
4. Strong generality — the same network architecture can adapt to different rules and position types

Disadvantages of NNUE compared to handcrafted evaluation:

1. Greater computational cost — neural network inference is slower than linear combinations
2. Data-dependent training — requires large-scale, high-quality training data
3. Poor interpretability — difficult to understand why NNUE makes a specific evaluation
4. Specific models — different position types may require different models

Chapter 4: In-depth Analysis of Search Algorithms

4.1 From Minimax to Alpha-Beta

Minimax search is the theoretical foundation of computer game-playing. Its basic idea is: in the game tree, each level represents a player’s move decision, assuming both sides choose the most favorable move for themselves. The maximizing player (MAX) chooses the move with the highest evaluation value, while the minimizing player (MIN) chooses the move with the lowest evaluation value.

Formal definition of Minimax:

Minimax(s) = 
  - If s is a terminal position: return evaluation
  - If it is MAX's turn to move: max(Minimax(s') for s' in all successor positions of s)
  - If it is MIN's turn to move: min(Minimax(s') for s' in all successor positions of s)

Alpha-Beta pruning is an optimization of Minimax. It maintains two values:

• alpha: The MAX player’s current best guaranteed value (lower bound)
• beta: The MIN player’s current best guaranteed value (upper bound)

When the search result of a branch falls outside the [alpha, beta] interval, that branch can be pruned (because it will not affect the final decision).

The ideal complexity of Alpha-Beta is O(b^(d/2)), where b is the branching factor (approximately 40 for Chinese Chess) and d is the search depth. This means that in the same amount of time, Alpha-Beta can search approximately twice the depth of positions.

4.2 Introduction of PVS (Principal Variation Search)

PVS (Principal Variation Search) is an efficient variant of Alpha-Beta. Its core idea is: assume that the first move found (the principal variation) is the best move, then use a null-window search to verify whether other branches are better than the principal variation.

The key to null-window search: When searching non-principal variation branches, use the window (alpha, alpha+1). If the search result is greater than alpha (meaning the window has been breached), it indicates that this branch might be better than the principal variation, and a full window search (alpha, beta) is then conducted.

Practical application of PVS in Chinese Chess engines: PVS improves search efficiency by approximately 10-20%. The effect is especially significant in Chinese Chess with its high branching factor.

4.3 Practice of Iterative Deepening

Iterative Deepening Search (IDS) is the standard search strategy for Chinese Chess engines. Its basic process starts from depth=1 and gradually increases the search depth layer by layer.

Advantages of iterative deepening:

1. Time-controllable: the best move can be returned at any time
2. Transposition table warm-up: results from shallow searches can be utilized by deeper searches
3. Search stability: avoids violent fluctuations in deeper searches
4. Improved move ordering: the principal variation found at shallow levels provides order references for deeper searches

Cost of iterative deepening: each deepening requires re-searching the entire tree. However, in practice, due to improved move ordering and transposition table warm-up, the total cost of iterative deepening is only about 5-15% more than direct deepest search.

4.4 Major Pruning Techniques

Null Move Pruning: Assume the opponent gets to move twice in a row while we are still not at a disadvantage; then the current position does not warrant deep search. The use of null move pruning in Chinese Chess requires setting a safety threshold (R value, typically 2-3 plies) and avoiding its use in critical positions.

LMR (Late Move Reductions): Reduce the search depth for moves ranked later in the move ordering. Because lower-ranked moves are of lower quality and do not warrant full search. The reduction amount of LMR is dynamically adjusted based on search depth, move type (capture/non-capture), and position type (whether in check).

SEE (Static Exchange Evaluation): Evaluates the net gain or loss of a capture exchange sequence. The adaptation of SEE to Chinese Chess includes: capture value ordering, handling of the Cannon’s jumping capture, and the rule constraint that the King cannot be exposed to check.

Futility pruning: At shallow depths (typically the last few plies), if the position is sufficiently advantageous or disadvantageous, terminate the search directly.

Razoring: Similar to Futility, but used at deeper levels.

Using these pruning techniques in combination, the search efficiency of Chinese Chess engines is improved by hundreds of times compared to basic Alpha-Beta.

Chapter 5: Transposition Tables and Hashing Technology

5.1 Incremental Update of Zobrist Hashing

Zobrist hashing is the most widely used position hashing technique in Chinese Chess engines. Its incremental update characteristic allows the hash value to be updated with O(1) computational complexity after each move.

Process of incremental update:

1. XOR out the random number of the moving piece at its original position from the hash value
2. If capturing, XOR out the random number of the captured piece at its original position
3. XOR in the random number of the moving piece at its new position
4. XOR the side-to-play flag (indicating it is the opponent’s turn)
5. If the King face-to-face state has changed, update the face-off flag

The efficiency of incremental updating allows the engine to quickly update the hash value during each recursive search call.

5.2 Transposition Table Management Strategies

The size and replacement strategy of the transposition table have a direct impact on search engine performance.

Entry structure: Each entry contains a hash value signature, search depth, node type (exact value/Alpha bound/Beta bound), best move, and evaluation value.

Replacement strategies:

1. Depth-preferred replacement: keep the entry with a greater search depth (even if it is older)
2. Always Replace: always replace old entries with new ones
3. Hybrid strategy: consider a weighted combination of depth and age

Pikafish uses a depth-preferred replacement strategy because entries with greater depth provide more valuable information.

Hash collision handling: Engines typically use 32-bit or 64-bit signatures to detect collisions. A larger signature space reduces the probability of collision but increases entry size.

Chapter 6: Practical Analysis of Chinese Chess Engines

6.1 Tactical Patterns in Engine Play

In Chinese Chess engine play, the following tactical patterns are especially common:

Pin: Restricting the movement of an opponent’s piece through piece arrangement. In Chinese Chess, the Rook has the strongest pinning effect, while pinning by Knight and Cannon is also common.

Fork: A single piece threatens multiple opponent pieces simultaneously. The Knight’s fork is the most typical (the Knight’s eight-directional movement allows it to attack multiple targets at once).

Block: Intercepting the opponent’s attack route or defensive configuration through piece arrangement.

Checkmate Combination: Checkmating the opponent through a continuous series of checks. Cannon checkmate combinations (such as “Iron Bolt,” “Double Cups Offering Wine,” etc.) are signature tactics in Chinese Chess.

6.2 Analysis of Engine vs. Human Master Games

After 2006, Chinese Chess engines comprehensively surpassed human Grandmasters in playing strength. The key points of comparative analysis:

Advantages:

1. Computational precision — engines do not make simple calculation errors
2. Comprehensive coverage — engines do not overlook critical variations
3. Objective evaluation — engines are not affected by emotions or psychological factors
4. Sustained endurance — engines do not fatigue during high-intensity games

Disadvantages:

1. Strategic limitations — engines find it difficult to execute long-term strategic plans
2. Insufficient creativity — engines’ playing style is relatively “mechanical”
3. Difficulty with open positions — evaluation accuracy may decrease in completely open positions

With the introduction of NNUE, the above disadvantages are gradually improving. NNUE learns strategic patterns from training data, significantly enhancing its long-term planning capabilities.