Xiangqi EGT

[h.g.muller]

I have started building End-Game Tables for Xiangqi (Chinese Chess), to enhance my engine for the upcoming computer Olympiad. It turns out that Xiangqi exngines tend to require a lot of technical skill. Quite unlike Chess, where end-games with a significant material advantage tend to 'win themselves'. The problem in Xiangqi is that there is no real promotion. So Pawns, which are lower in numbers at the game start anyway, and tend to disappear faster too than in Chess because they do not form chains in which they protect each other, remain pretty weak pieces always. So you don't have this amplifying mechanism like in Chess, where a tiny advantage leads to promotion, which gains you a piece, which then facilitates another promotion, etc. Instead you have to work with whatever advantage you have in attacking material, and try to break down whatever defensive material (the Advisers and Elephants that cannot leave their own half) he has left.

The situation is futher complicated by the fact that the strong side usually has defensive pieces left too. These are then worse than useless,because there is nothing to defend against, and they cannot cross into the other half to assist the attack. They can stand in your way, however, so you have to account for them. And if you have to rely on the use of a Cannon for winning, they can still be important as Cannon mounts, as a Cannon can only capture after jumping over something. The Palaces also break the symmetry in the sameway asPawns break it in Chess, so there never ismore than left-right symmetry, even when all pieces have the usual 8-fold symmetry (which all non-Pawns have).

One of the simplest non-trivial wins in Chess is KPK (I consider KQK and KRK trivial), and the Xiangqi equivalent is KRdKAAEE, where the 'd' stands for any combination of (redundant) defensive material. This can amount to an 11-men end-game, when d=AAEE! Now it is true that many of these men have only access to a very restricted part of the board. There are 119 possible constellations of KAA+KA+K (the 'Palace' state), and 29 constellations of EE+E+nothing, and these don't interfere with each other much more than two pieces on an 8x8 board. That gives 3,451 constellations of King + defenders, (some broken because of a King coinciding with an Elephant) about the same as 2 men in Chess. Attacking pieces like Rook can roam a 90-squares board, though, 40% larger than an 8x8 board. So the 3-11-men KRdKd is similar in size to a 5-men EGT with Pawns in Chess, which is of course still quite doable. But we are basically talking about only a single 'ergodic' piece here (i.e. able to access the entire board).

There is a lot of 'redundancy' in the full 11-men table: the positioning of the strong-side defenders becomes irrelevant when they are not obstructing the strong King's forward look and lateral motion (still relevant due to the rule that Kings cannot stare each other in the face along a file). There also is never any need for the Rook to access its own board half (as all lateral motion can be made on the rank passing just in front of the enemy Palace, where no defender can go, and which thus is never obstructed). In that case the positioning of strong-side defenders is also not relevant for Rook moving. It is therefore possible to generate a partial ('core') EGT, which contains only positions with the Rook on the enemy board half, and which reduces the strong King location to just its file coordinate. The data in this subset of the 11-men EGT would exactly repeat itself for every constellation of strong-side defenders that has the Elephants not on the central file (but on one of the other 6 squares where Elephants can venture, or no Elephants at all), and has the King on a rank in front of all Advisers. So it can be used for probing all positions that satisfy these conditions on the strong-side's KRd. It can never take very many moves to reach such a position from an arbitrary one, and the opponent can never prevent the strong side from making these moves. So the partial KRKd 7-men EGT (450K positions) is already extremely useful.

Because of the restricted access the defensive pieces have to the board, the pieces that can access the entire board often do not have to do so, as many locations will be completely equivalent. E.g. in KCPEKd the Cannon does have to visit its own board half, in order to use the King or Elephant as mount when aiming at the enemy Palace. But it can always do that from the back rank, when the King stays away from that. The other 4 ranks on its own board half might as well not exist, as far as the Cannon is concerned. And in fact that also holds for the first rank across the River, and for the two edge files. There just is nothing to do for the Cannon there. The whole end-game can be played with the Cannon on these 7x5 squares. And the Pawn only starts toplay a role when it is on squares in or adjacent to the Palace, and should not be on the last rank (which would leave no reachable checkmate positions), that is only a 5x3 area. So it should be possible to build a partial EGT with just 35 Cannon locations, 15 Pawn locations, 3 locations for the strong-side King and 3 for the strong-side Elephant, in addition to the 3,451 weak-side constellations. That is 16M positions in total, still modest for an EGT. (Like a Chess 4-men, and left-right symmetry can still reduce this by a factor 2.) One would never have to search very deep from an arbitrary KCPEKd position to reach this 'core' EGT: perhaps step the King and Elephant forward once, move the Cannon to one of the 5 'registered' ranks, and then march the Pawn upto the Palace.

That is all trivial, except for the marching up the Pawn, which could be obstructed by the Elephant if it is a c-or g-Pawn that has not yet crossed the River (other Pawns can avoid the Elephant squares, walking around them to reach the core area). So it might be better to tabulate a 5x4 area for the Pawn, plus the two squares just before the River where it could be stopped. Then the tactics for getting these Pawns safely across the River would also be embodied in the EGT.