## Xiangqi

We like board games here at the SI, and the latest craze sweeping the office is xiangqi – Chinese chess.

Xiangqi is played on a nine-by-nine grid, and is similar to Western chess in many ways: it is turn-based, zero-sum, and is won by checkmating the opponent’s king (or ‘general’). It is easy to see how the two games might share a common ancestor. Many of the pieces move in similar ways – the pieces called ‘chariots’ move exactly like castles, the ‘horses’ almost exactly like knights, the ‘soldiers’ and ‘elephants’ a little bit like pawns and bishops. Some pieces have no equivalent in Western chess – ‘fireworks’ capture by jumping over exactly one other piece, and ‘advisors’ protect the general – but, rather pleasingly, once the pieces’ moves have been learnt, the tactics and strategy of chess carry over very well. If you are good at chess, you’re not too bad at xiangqi either, even if you don’t know it yet.

One important difference is that the xiangqi’s general is confined to a small space – a three-by-three grid. This has the effect that checkmate is much easier to achieve in xiangqi than in chess.

We may define this exactly. Consider the set of all possible combinations of up to 32 pieces on an 8×8 chessboard – a huge number, call it C. Now imagine the much smaller (though still gigantic) set of possible combinations of pieces that are checkmates for back. Call this smaller number C+. Now consider the equivalent numbers in xiangqi – the set of all possible positions, X, and the subset of all possible checkmates, X+. When we say that checkmate is easier in xiangqi than in chess, we mean that (X+ / X) is much bigger than (C+ / C) – checkmates make up a much bigger proportion of the available positions.

We’re talking about huge numbers when we discuss X and C, but still finite – Dennett fans would call them Vast. The number of possible positions is an upper bound, a kind of mathematical worst-case scenario. In fact the number can be made smaller by realising that some positions are unreachable. In chess, the set of positions in which a pawn sits on the first row may be removed from C; likewise in xiangqi the positions in which the two generals illegally face each other. These legally accessible positions are called the *state spaces* of xiangqi and chess.

State space sizes are difficult to calculate. People begin with an upper bound, then whittle this Vast figure down by working out the mathematical consequences of the games’ rules. Exact answers have been obtained with simple games like noughts and crosses: 765. Chess’s has been estimated as 100,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000, xiangi’s as ten times bigger, but take these as approximations. The set of all possible *games*, of course, is much, much higher.

Don’t bother playing draughts, by the way. It’s been solved. The entire decision tree of a game draughts has been worked out, in 2007. From the starting position, draughts will always end in a draw if played perfectly. The game only becomes interesting because people make mistakes.

REFERENCES

http://fragrieu.free.fr/SearchingForSolutions.pdf

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

You know, now that I’ve uploaded this, I’m increasingly nervous about whether or not (X+ / X) > (C+ / C) is actually true. I think that it is, but if anyone mathsy out there knows how to go about proving it, or disproving it, I’d be very interested to hear it.

The S INovember 4, 2011 at 7:24 pm