Performance Analysis

Using performance analysis tools to identify engine performance bottlenecks:

Sampling analysis: Sample the program’s call stack at a fixed frequency to count execution time of each function. Instrumentation analysis: Insert analysis points in the code to accurately measure execution time of each function.

Performance bottleneck identification:

1. Computation load of the evaluation function
2. Overhead of move generation
3. Overhead of transposition table access
4. Overhead of thread synchronization

Priority of performance optimization:

1. Evaluation function (typically 50-80% of computation time)
2. Move generation (about 10-20% of computation time)
3. Search logic (about 10-20% of computation time)
4. Transposition table (about 5-10% of computation time)

Volume XVII: Mathematical Principles of Xiangqi Engines

Possibility Search

In Alpha-Beta search, when the evaluation function has uncertainty, probabilistic methods are used to handle these uncertainties.

Problem formalization: Given a position s, there is an error between its true evaluation V(s) and the engine’s evaluation E(s). By establishing a probabilistic model of the error, pruning decisions can be handled more flexibly in the search.

Application scenarios:

1. Considering evaluation uncertainty in pruning decisions
2. Selecting the optimal variation based on probabilities among multiple variations
3. Focusing search on high-probability regions in time management

Lower Bound of Game Tree Complexity

Theoretical lower bound of Xiangqi game tree complexity:

State Space Complexity: The state space complexity of Xiangqi is estimated at approximately 10^40 to 10^50. This estimate considers all possible positions and moves of the pieces.

Game Tree Complexity: The game tree complexity of Xiangqi (estimate of game length) is approximately 10^150. This estimate is based on an average branching factor of about 40 and an average game length of about 60 moves.

These numbers indicate: Complete analysis of Xiangqi is infeasible for the foreseeable future. All engines are “approximately optimal”; no engine can claim to have “completely solved” Xiangqi.

Formalization of Xiangqi Optimization Problem

Xiangqi engine search can be formalized as an optimization problem:

Given board state s, find a move m* from the legal move set M(s) that maximizes the expected future evaluation value: m* = argmax_{m in M(s)} V(s’)

where s’ is the position after playing m, and V is the evaluation function.

Due to the imprecision of the evaluation function V and the limitations of search depth, the engine actually solves an approximate solution: m*approx = argmax{m in M(s)} V_search(s’, depth)

where V_search is the approximate evaluation function of depth-limited search.

Volume XVIII: Xiangqi Engines and Game Theory

Conditions for Zermelo’s Theorem in Xiangqi

Zermelo’s Theorem states: In a perfect-information, finite-position, two-player zero-sum game, either the first player has a winning strategy, the second player has a winning strategy, or both players have a drawing strategy.

Xiangqi clearly satisfies the conditions of Zermelo’s Theorem: perfect information (both sides can see the board), finite positions (limited board and piece types), two-player zero-sum (one side wins and the other loses, or both draw).

Xiangqi’s game value: According to Zermelo’s Theorem, the game value of Xiangqi is either “Red wins”, “Black wins”, or “Draw”. However, theoretically, Xiangqi has not been completely analyzed, and the actual game value is unknown.

Xiangqi engines approach this theoretical game value through search within limited depth.