Check out Symmetric Chess, our featured variant for March, 2024.

Enter Your Reply

The Comment You're Replying To
ChessAndXiangqiPlaye wrote on Sat, Aug 29, 2009 12:43 PM UTC:Excellent ★★★★★
I've been thinking about the question of whether Chess or Xiangqi (Chinese
Chess) is strictly speaking the more complex game when viewed from the
perspective of complexity theory.

For more information on Chess and Xiangqi, see

Chess:

http://en.wikipedia.org/wiki/Chess
http://www.chessvariants.org/d.chess/chess.html

Xiangqi:

http://en.wikipedia.org/wiki/Chinese_chess
http://www.chessvariants.com/xiangqi.html

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 Chess 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, I think 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').

Personally despite being an ethnic Chinese and proud of Chinese culture in
general, I think Chess is a better game than Xiangqi and I'm a better
player in Chess than in Xiangqi. Though of course the Chinese game of
Weiqi/Go is far more complex than either of these games mentioned here.

Edit Form

Comment on the page Xiangqi: Chinese Chess

Quick Markdown Guide

By default, new comments may be entered as Markdown, simple markup syntax designed to be readable and not look like markup. Comments stored as Markdown will be converted to HTML by Parsedown before displaying them. This follows the Github Flavored Markdown Spec with support for Markdown Extra. For a good overview of Markdown in general, check out the Markdown Guide. Here is a quick comparison of some commonly used Markdown with the rendered result:

Top level header: <H1>

Block quote

Second paragraph in block quote

First Paragraph of response. Italics, bold, and bold italics.

Second Paragraph after blank line. Here is some HTML code mixed in with the Markdown, and here is the same <U>HTML code</U> enclosed by backticks.

Secondary Header: <H2>

  • Unordered list item
  • Second unordered list item
  • New unordered list
    • Nested list item

Third Level header <H3>

  1. An ordered list item.
  2. A second ordered list item with the same number.
  3. A third ordered list item.
Here is some preformatted text.
  This line begins with some indentation.
    This begins with even more indentation.
And this line has no indentation.

Alt text for a graphic image

A definition list
A list of terms, each with one or more definitions following it.
An HTML construct using the tags <DL>, <DT> and <DD>.
A term
Its definition after a colon.
A second definition.
A third definition.
Another term following a blank line
The definition of that term.