Complex Xiangqi

Some argue that thinking about the question of whether Chess or Xiangqi (Chinese Chess) is the more complex game, one should view it from the perspective of complexity theory. 

Using the ideas of complexity theory, the complexity of Chess and Xiangqi can be estimated and calculated quantitatively. In general, there are 3 different kinds of complexity a deterministic board game like Chess or Xiangqi may have. 

1. State-space Complexity: the maximum number of possible positions in the game. It is also possible to calculate an upper bound for state-space complexity which includes illegal positions as well. The upper bound is generally speaking much easier to calculate than the exact value, which is often only given as an accurate estimation. 

It is generally calculated that the state-space complexity of Chess is around 10^50 (10 to the power of 50, or 1 with 50 zeros after it, or one hundred trillion trillion trillion trillion different positions), while the state-space complexity of Xiangqi is around 10^48, 100 times less than that of Chess. This is because despite a larger board (9 times 10 vs. 8 times 8), Xiangqi pieces are generally speaking less powerful than their Chess equivalents and for many pieces the space over which it can potentially move is severely restricted. In Chess, the King, Queen, Rook and Knight can potentially move to every square on the board, the Pawn can potentially reach more than 6/8th of all the squares (though unlikely to move that much in a real game), and even the Bishop can reach half of all the squares. In Xiangqi the General can only stay inside the Palace and move to 9 different intersections, the Advisor can only move to 5 different intersections and the Elephant only to 7 different intersections. 

Another factor is that the Xiangqi board, having 9 files instead of Chess's 8, is symmetrical in the left-right direction. This means the left and right hand sides in Xiangqi are essentially the same, so different board positions may just be a trivial reflection of the other. This decreases the effective state-space complexity of Xiangqi by a factor of 2. In Chess on the other hand, the Kingside and the Queenside are not just a trivial reflection of each other since the distance the King has to the edge of the board is different for the left and right hand sides. 

Therefore despite having 90 intersections on the Xiangqi board vs. only 64 squares for Chess, the total number of possible positions is around 100 times more in Chess than Xiangqi, 10^50 vs. 10^48. 

2. Game-tree Complexity: roughly speaking this is the total number of possible games one can potentially play with a particular version of board game. This is different from state-space complexity and the value is generally speaking far larger because state-space complexity only takes space and position into account, while game-tree complexity analyses the actual moves in a game and hence also puts time into account. Generally speaking, there are many different ways, in terms of playing the game, to reach a particular position on the board. For instance, the opening position on the chess board with Ng1-f3 and e2-e4 (moving the King's Knight and King's Pawn out) can be reached via two different "game-trees": Nf3 first or e4 first, and the number of possible game-trees for a given board position increases dramatically as one progresses into the game and the position becomes much more complex. 

Generally it is estimated that the total number of possible games in Chess is around 10^123 (or 1 with 123 zeros after it), while for Xiangqi it is 10^150, which is 100 million billion times more than Chess. For comparison, consider that the total number of atoms in the observable universe is only around 10^80. 

There are far more possible games in Xiangqi since it is played on a larger board (90 instead of 64 spaces), and generally a game of Xiangqi lasts for more moves than a game of Chess. However, given that the Xiangqi board is left-right symmetrical and therefore left-hand side play is identical to right-hand side play, and that since Xiangqi pieces are generally less powerful and the General is restricted to within the Palace, the larger number of possible games in the purely technical sense becomes relatively trivial by the endgame stage, since real play is likely to be always focused around the General's Palace, and different moves elsewhere on the board essentially converges to the same kind of endgames. In other words, whereas in the earlier phase of the game the game-tree of possible moves branches out, by the endgame in Xiangqi they begin to converge into one-another, and Xiangqi games generally end in relatively similar positions (major pieces and pawns around the General's Palace and a relatively exposed General). 

In Chess game-trees also tend to converge more by the endgame but since the King can move to anywhere on the board and there is the possibility of pawn promotion, the game converges to a significantly smaller extent than Xiangqi. Also the approximate estimation for the game-tree complexity of Chess does not take into account the re-divergence of the game-tree if enough pawns are promoted into pieces in the endgame. Although in real play this tends to be an unlikely scenario, in technical calculations of game complexity this factor should be included. In addition, when the game-tree complexity of Xiangqi is calculated, unlikely endgame scenarios, such as the game dragging on unnecessarily for dozens of extra moves that are in practice trivial, are also included. 

Therefore effectively speaking despite the technically higher game-tree complexity of Xiangqi, Chess is actually the more complex game of the two. 

3. Computational Complexity: a third way to calculate game complexity is to consider how much computational steps are required to play a Chess or Xiangqi game by a Chess or Xiangqi engine/computer as the actual size of the game increases in space. E.g. if the Chess board size doubles, how much more computational power is required? In this both Chess and Xiangqi are very similar in that computational difficulty increases exponentially (in terms of the number of calculational steps required to play the game) with board size. Thus both games are said to be inside the complexity class called EXPTIME (stands for "exponential time"). 

More information on Game Complexity: 

http://en.wikipedia.org/wiki/Game_complexity